Fractional norms and quasinorms do not help to overcome the curse of dimensionality

Abstract

The curse of dimensionality causes the well-known and widely discussed problems for machine learning methods. There is a hypothesis that using of the Manhattan distance and even fractional quasinorms lp (for p less than 1) can help to overcome the curse of dimensionality in classification problems. In this study, we systematically test this hypothesis. We confirm that fractional quasinorms have a greater relative contrast or coefficient of variation than the Euclidean norm l2, but we also demonstrate that the distance concentration shows qualitatively the same behaviour for all tested norms and quasinorms and the difference between them decays as dimension tends to infinity. Estimation of classification quality for kNN based on different norms and quasinorms shows that a greater relative contrast does not mean better classifier performance and the worst performance for different databases was shown by different norms (quasinorms). A systematic comparison shows that the difference of the performance of kNN based on lp for p=2, 1, and 0.5 is statistically insignificant.

References in corpus (11)

• An ensemble-based system for automatic screening of diabetic retinopathy
• Fifty Years of Pulsar Candidate Selection: From simple filters to a new principled real-time classification approach
• Principal manifolds and graphs in practice: from molecular biology to dynamical systems
• Blessing of dimensionality: mathematical foundations of the statistical physics of data
• Correction of AI systems by linear discriminants: Probabilistic foundations
• The unreasonable effectiveness of small neural ensembles in high-dimensional brain
• Stochastic Separation Theorems
• High--Dimensional Brain in a High-Dimensional World: Blessing of Dimensionality
• Topological Grammars for Data Approximation
• On Adversarial Examples and Stealth Attacks in Artificial Intelligence Systems
• Data complexity measured by principal graphs

Cited by in corpus (4)

• Scikit-dimension: a Python package for intrinsic dimension estimation
• Domain Adaptation Principal Component Analysis: base linear method for learning with out-of-distribution data
• High-dimensional separability for one- and few-shot learning
• Ordinal Classification with Distance Regularization for Robust Brain Age Prediction