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 (5)

• An ensemble-based system for automatic screening of diabetic retinopathy
• 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