Practical stochastic separation theorems for product distributions
Bogdan Grechuk · 2019
Stochastic separation theorems provide mathematical foundation for construction an extremely efficient mechanism for error correction in artificial intelligence systems. They imply that this mechanism works even if the number of points in the dataset is exponentially large in terms of dimension of the underlying space. However, in most such theorems in the literature, the bound for the size of the dataset in terms of dimension is either inexplicit or impractical for large but not extremely large dimensions (such as few hundreds or one thousand). In this work, we derive much less restrictive estimates for dataset size in terms of dimension, which still sufficient to guarantee Fisher separability with large probability, provided that data follow product distributions in the unit cube.