Blessing of dimensionality: mathematical foundations of the statistical physics of data

Abstract

The concentration of measure phenomena were discovered as the mathematical background of statistical mechanics at the end of the XIX - beginning of the XX century and were then explored in mathematics of the XX-XXI centuries. At the beginning of the XXI century, it became clear that the proper utilisation of these phenomena in machine learning might transform the curse of dimensionality into the blessing of dimensionality. This paper summarises recently discovered phenomena of measure concentration which drastically simplify some machine learning problems in high dimension, and allow us to correct legacy artificial intelligence systems. The classical concentration of measure theorems state that i.i.d. random points are concentrated in a thin layer near a surface (a sphere or equators of a sphere, an average or median level set of energy or another Lipschitz function, etc.). The new stochastic separation theorems describe the thin structure of these thin layers: the random points are not only concentrated in a thin layer but are all linearly separable from the rest of the set, even for exponentially large random sets. The linear functionals for separation of points can be selected in the form of the linear Fisher's discriminant. All artificial intelligence systems make errors. Non-destructive correction requires separation of the situations (samples) with errors from the samples corresponding to correct behaviour by a simple and robust classifier. The stochastic separation theorems provide us by such classifiers and a non-iterative (one-shot) procedure for learning.

Accepted for publication in Philosophical Transactions of the Royal Society A, 2018. Comprises of 17 pages and 4 figures

References in corpus (1)

• Data complexity measured by principal graphs

Cited by in corpus (20)

• High-NA Achromatic Metalenses by Inverse Design
• A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations
• Robust And Scalable Learning Of Complex Dataset Topologies Via Elpigraph
• Scikit-dimension: a Python package for intrinsic dimension estimation
• Correction of AI systems by linear discriminants: Probabilistic foundations
• The unreasonable effectiveness of small neural ensembles in high-dimensional brain
• High--Dimensional Brain in a High-Dimensional World: Blessing of Dimensionality
• Fractional norms and quasinorms do not help to overcome the curse of dimensionality
• Detecting the ultra low dimensionality of real networks
• High-dimensional brain. A tool for encoding and rapid learning of memories by single neurons
• Hilbert's Sixth Problem: the endless road to rigour
• Fast Construction of Correcting Ensembles for Legacy Artificial Intelligence Systems: Algorithms and a Case Study
• Random geometric graphs in high dimension
• High-dimensional separability for one- and few-shot learning
• Blessing of dimensionality at the edge
• Tensor train based isogeometric analysis for PDE approximation on parameter dependent geometries
• Symphony of high-dimensional brain
• Divergence Regulated Encoder Network for Joint Dimensionality Reduction and Classification
• Unsupervised Extractive Dialogue Summarization in Hyperdimensional Space
• Higher-Order LaSDI: Reduced Order Modeling with Multiple Time Derivatives