Please use this identifier to cite or link to this item:
Title: Stochastic Separation Theorems
Authors: Gorban, A. N.
Tyukin, I. Y.
First Published: 31-Jul-2017
Publisher: Elsevier for European Neural Network Society (ENNS), International Neural Network Society (INNS), Japanese Neural Network Society (JNNS)
Citation: Neural Networks, 2017, 94, pp. 255-259
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(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.
DOI Link: 10.1016/j.neunet.2017.07.014
ISSN: 0893-6080
eISSN: 1879-2782
Embargo on file until: 31-Jul-2018
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © 2017, Elsevier. Deposited with reference to the publisher’s open access archiving policy.
Description: The file associated with this record is under embargo until 12 months after publication, in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
Appears in Collections:Published Articles, Dept. of Mathematics

Files in This Item:
File Description SizeFormat 
1703.01203v3.pdfPost-review (final submitted author manuscript)167.14 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.