Stochastic Separation Theorems

Abstract

The problem of non-iterative one-shot and non-destructive correction of unavoidable mistakes arises in all Artificial Intelligence applications in the real world. Its solution requires robust separation of samples with errors from samples where the system works properly. We demonstrate that in (moderately) high dimension this separation could be achieved with probability close to one by linear discriminants. Surprisingly, separation of a new image from a very large set of known images is almost always possible even in moderately high dimensions by linear functionals, and coefficients of these functionals can be found explicitly. Based on fundamental properties of measure concentration, we show that for $M<a\exp (bn)$ random $M$-element sets in ${\mathbb{R}}^n$ are linearly separable with probability $p$, $p>1-\vartheta$, where $1>\vartheta >0$ is a given small constant. Exact values of $a,b>0$ depend on the probability distribution that determines how the random $M$-element sets are drawn, and on the constant $\vartheta$. These {\em stochastic separation theorems} provide a new instrument for the development, analysis, and assessment of machine learning methods and algorithms in high dimension. Theoretical statements are illustrated with numerical examples.

6 pages, accepted for publication in Neural Networks (Letter section)

References in corpus (1)

• One-Trial Correction of Legacy AI Systems and Stochastic Separation Theorems

Cited by in corpus (18)

• Blessing of dimensionality: mathematical foundations of the statistical physics of data
• Robust And Scalable Learning Of Complex Dataset Topologies Via Elpigraph
• 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
• Knowledge Transfer Between Artificial Intelligence Systems
• High-dimensional brain. A tool for encoding and rapid learning of memories by single neurons
• Ultra-High-Resolution Detector Simulation with Intra-Event Aware GAN and Self-Supervised Relational Reasoning
• General stochastic separation theorems with optimal bounds
• Fast Construction of Correcting Ensembles for Legacy Artificial Intelligence Systems: Algorithms and a Case Study
• High-dimensional separability for one- and few-shot learning
• Augmented Artificial Intelligence: a Conceptual Framework
• Blessing of dimensionality at the edge
• The Boundaries of Verifiable Accuracy, Robustness, and Generalisation in Deep Learning
• Symphony of high-dimensional brain
• Linear and Fisher Separability of Random Points in the d-dimensional Spherical Layer
• Relative intrinsic dimensionality is intrinsic to learning