General stochastic separation theorems with optimal bounds

Abstract

Phenomenon of stochastic separability was revealed and used in machine learning to correct errors of Artificial Intelligence (AI) systems and analyze AI instabilities. In high-dimensional datasets under broad assumptions each point can be separated from the rest of the set by simple and robust Fisher's discriminant (is Fisher separable). Errors or clusters of errors can be separated from the rest of the data. The ability to correct an AI system also opens up the possibility of an attack on it, and the high dimensionality induces vulnerabilities caused by the same stochastic separability that holds the keys to understanding the fundamentals of robustness and adaptivity in high-dimensional data-driven AI. To manage errors and analyze vulnerabilities, the stochastic separation theorems should evaluate the probability that the dataset will be Fisher separable in given dimensionality and for a given class of distributions. Explicit and optimal estimates of these separation probabilities are required, and this problem is solved in present work. The general stochastic separation theorems with optimal probability estimates are obtained for important classes of distributions: log-concave distribution, their convex combinations and product distributions. The standard i.i.d. assumption was significantly relaxed. These theorems and estimates can be used both for correction of high-dimensional data driven AI systems and for analysis of their vulnerabilities. The third area of application is the emergence of memories in ensembles of neurons, the phenomena of grandmother's cells and sparse coding in the brain, and explanation of unexpected effectiveness of small neural ensembles in high-dimensional brain.

arXiv commentNumerical examples and illustrations are added, minor corrections extended discussion and the bibliography

References in corpus (14)

• Prototypical Networks for Few-shot Learning
• Understanding deep learning requires rethinking generalization
• Matching Networks for One Shot Learning
• Stochastic Configuration Networks: Fundamentals and Algorithms
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Principal manifolds and graphs in practice: from molecular biology to dynamical systems
• Approximation with Random Bases: Pro et Contra
• Correction of AI systems by linear discriminants: Probabilistic foundations
• The unreasonable effectiveness of small neural ensembles in high-dimensional brain
• Stochastic Separation Theorems
• On Adversarial Examples and Stealth Attacks in Artificial Intelligence Systems
• Knowledge Transfer Between Artificial Intelligence Systems
• High-dimensional brain. A tool for encoding and rapid learning of memories by single neurons
• Linear and Fisher Separability of Random Points in the d-dimensional Spherical Layer

Cited by in corpus (5)

• Scikit-dimension: a Python package for intrinsic dimension estimation
• Rolling the dice for better deep learning performance: A study of randomness techniques in deep neural networks
• High-dimensional separability for one- and few-shot learning
• Blessing of dimensionality at the edge
• Linear and Fisher Separability of Random Points in the d-dimensional Spherical Layer