Stochastic Separation Theorems
This addresses the challenge of error correction in real-world AI applications, offering a foundational tool for improving machine learning robustness, though it appears incremental in applying known concentration principles to this specific problem.
The paper tackles the problem of non-iterative, one-shot correction of errors in AI systems by showing that linear discriminants can robustly separate erroneous samples from correct ones with high probability in moderately high dimensions. It demonstrates that for random sets in high-dimensional spaces, linear separability holds with probability close to one, providing explicit coefficients and theoretical bounds.
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(b{n})$ 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.