arXiv:1802.02172v3 [] 24 Mar 2018

Augmented Artificial Intelligence:
a Conceptual Framework
1st Alexander N Gorban

2nd Bogdan Grechuk

3rd Ivan Y Tyukin

University of Leicester
and Lobachevsky University
Leicester, UK, and Nizhni Novgorod, Russia
a.n.gorban@le.ac.uk

University of Leicester
Leicester, UK
bg83@le.ac.uk

University of Leicester
and Lobachevsky University
Leicester, UK, and Nizhni Novgorod, Russia
i.tyukin@le.ac.uk

Abstract—All artificial Intelligence (AI) systems make errors.
These errors are unexpected, and differ often from the typical
human mistakes (“non-human” errors). The AI errors should
be corrected without damage of existing skills and, hopefully,
avoiding direct human expertise. This paper presents an initial
summary report of project taking new and systematic approach
to improving the intellectual effectiveness of the individual AI
by communities of AIs. We combine some ideas of learning
in heterogeneous multiagent systems with new and original
mathematical approaches for non-iterative corrections of errors
of legacy AI systems. The mathematical foundations of AI nondestructive correction are presented and a series of new stochastic
separation theorems is proven. These theorems provide a new
instrument for the development, analysis, and assessment of
machine learning methods and algorithms in high dimension.
They demonstrate that in high dimensions and even for exponentially large samples, linear classifiers in their classical
Fisher’s form are powerful enough to separate errors from
correct responses with high probability and to provide efficient
solution to the non-destructive corrector problem. In particular,
we prove some hypotheses formulated in our paper ‘Stochastic
Separation Theorems’ (Neural Networks, 94, 255–259, 2017), and
answer one general problem published by Donoho and Tanner
in 2009.
Index Terms—multiscale experts, knowledge transfer, noniterative learning, error correction, measure concentration, blessing of dimensionality

I. I NTRODUCTION
The history of neural networks research can be represented
as a series of explosions or waves of inventions and expectations. This history ensures us that the popular Gartner’s hype
cycle for emerging technologies presented by the solid curve
on Fig. 1 (see, for example [1]) should be supplemented by
the new peak of expectation explosion (dashed line). Some
expectations from the previous peak are realized and move to
the “Plateau of Productivity” but the majority of them jump
to the next “Peak of Inflated Expectations”. This observation
relates not only to neural technologies but perhaps to majority
of IT innovations. It is surprising to see, how expectations
reappear in the new wave from the previous peak often without
modifications, just changing the human carriers.
ANG and IYT were Supported by Innovate UK (KTP009890 and
KTP010522) and Ministry of science and education, Russia (14.Y26.31.0022).
BG thanks the University of Leicester for granting him academic study leave
to do this research.

Expectations Peak of

Inflated
Expectations

Plateau of
Productivity

Time

Figure 1. Gartner’s Hype Cycle for emerging technologies supplemented by
a new peak.

Computers and networks have been expected to augment
the human intelligence [2]. In 1998 one of the authors had
been inspired by 8 years of success of knowledge discovery
by deep learning neural network and by the transformation
of their hidden knowledge into explicit knowledge in the
form of “logically transparent networks” [3] by means of
pruning, binarization and other simplification procedures [4],
[5], and wrote: “I am sure that the neural network technology
of knowledge discovery is a ”point of growth”, which will
remodel neuroinformatics, transform many areas of information technologies and create new approaches” [6]. Now it
seems that this prediction will not be fulfilled: most customers
do not care about gaining knowledge but prefer the “one
button solutions”, which exclude humans from the process as
far as it is possible. This is not a new situation in history.
New intellectual technologies increase intellectual abilities
of mankind, but not the knowledge of individual humans.
Here, we can refer to Plato “There is an old Egyptian tale
of Theuth, the inventor of writing, showing his invention to
the god Thamus, who told him that he would only spoil
men’s memories and take away their understandings” [7]. The
adequate model of future Artificial Intelligence (AI) usage
should include large communities of AI systems. Knowledge
should circulate and grow in these communities. Participation

of humans in these processes should be minimized. In the
course of this technical revolution not the “Augmented human
intellect” but the continuously augmenting AI will be created.
In this work, we propose the conceptual framework for
augmenting AI in communities or “social networks” of AIs.
For construction of such social networks, we employ several
ideas in addition to the classical machine learning. The first of
them is separation of the problem areas between small local
(neural) experts, their competitive and collaborative learning,
and conflict resolution. In 1991, two first papers with this
idea were published simultaneously [8], [9]. The techniques
for distribution of tasks between small local experts were
developed. In our version of this technology [8] and in all our
applied software [3], [10]–[12] the neural network answers
were always complemented by the evaluation of the network
self-confidence. This self-confidence level is an important
instrument for community learning.
The second idea is the blessing of dimensionality [13]–[17]
and the AI correction method [21] based on stochastic separation theorems [20]. The “sparsity” of high-dimensional spaces
and concentration of measure phenomena make some lowdimensional approaches impossible in high dimensions. This
problem is widely known as the “curse of dimensionality”.
Surprisingly, the same phenomena can be efficiently employed
for creation of new, high-dimensional methods, which seem to
be much simpler than in low dimensions. This is the “blessing
of dimensionality”.
The classical theorems about concentration of measure state
that random points in a highly-dimensional data distribution
are concentrated in a thin layer near an average or median
level set of a Lipschitz function (for introduction into this area
we refer to [18]). The newly discovered stochastic separation
theorems [?]017 revealed the fine structure of these thin
layers: the random points are all linearly separable from the
rest of the set even for exponentially large random sets.
Of course, the probability distribution should be ‘genuinely’
high-dimensional for all these concentration and separation
theorems.
Linear separability of exponentially large random subsets in
high dimension allows us to solve the problem of nondestructive correction of legacy AI systems: the linear classifiers in
their simplest Fishers form can separate errors from correct
responses with high probability [21]. It is possible to avoid
the standard assumption about independence and identical
distribution of data points (i.i.d.). The non-iterative and nondestructive correctors can be employed for skills transfer in
communities of AI systems [22].
These two ideas are joined in a special organisational
environment of community learning which is organized in
several phases:
• Initial supervising learning where community of newborn
experts assimilate the knowledge hidden in labeled tasks
from a problem-book (the problem-book is a continuously
growing and transforming collection of samples);
• Non-iterative learning of community with self-labeling
of real-life or additional training samples on the basis

out2
1
Class 2,
I am sure

Class 1, but
I am not sure

Class 2

Class 1,
I am sure
Class 1
ε

out1
1

Figure 2. Answers and assurance; s is the deviation from the diagonal.

of separation of expertise between local experts, their
continuous adaptation and mutual correction for the assimilation of gradual changes in reality.
• Interiorisaton of the results of the self-supervising learning of community in the internal skills of experts.
• Development and learning of special network manager
that evaluates the level of expertise of the local experts for
a problem and distributes the incoming task flow between
them.
• Using an “ultimate auditor” to assimilate qualitative
changes in the environment and correct collective errors;
it may be human inspection, a feedback from real life,
or another system of interference into the self-labeling
process.
We describe the main constructions of this approach using
the example of classification problems and simple linear correctors. The correctors with higher abilities can be constructed
on the basis of small neural networks with uncorrelated
neurons [21] but already single-neuron correctors (Fisher’s
discriminants) can help in explanation of a wealth of empirical
evidence related to in-vivo recordings of “Grandmother” cells
and “concept” cells [17], [23]. We pay special attention to
the mathematical backgrounds of the technology and prove
a series of new stochastic separation theorems. In particular,
we find that the hypothesis about stochastic separability for
general log-concave distribution [22] is true and describe a
general class of probability measures with linear stochastic
separability, the question was asked in 2009 by Donoho and
Tanner [19].
II. S UPERVISING STAGE : P ROBLEM OWNERS , M ARGINS ,
S ELF - CONFIDENCE , AND E RROR FUNCTIONS
Consider binary classification problems. The neural experts
with arbitrary internal structure have two outputs, out1 and
out2, with interpretation: the sample belongs to class 1 if
out1≥out2 and it belongs to class 2 if out1<out2. For any
given ε > 0 we can define the level of (self-)confidence in the

The most selfconfident answer:
Winner takes all
Class 2

Diagonal

The answer
we accepted

Class 1
s

The range
of answers
Incorrect class

Figure 3. Interpretation of community answer: Most self-confident winner
takes all. Dots correspond to the various agents’ answers, s is defined in
Fig. 2.

-δ

Ideal solutions
for owners
Correct class
s
ε

Diagonal

Ideal solutions for non-owners

Figure 5. Soft margin error function for owners and non-owners (one owner).

Correct,
Correct,
Incorrect,
for sure
Incorrect,
with
with
without
doubt
doubt
doubt
-ε

ε

k most self-confident answers

Class 2
s

s

Figure 4. Histogram of answers for trained community of agents: they should
give a correct self-confident answer to the samples they own, and do not make
large mistakes on all other examples they never met before.

classification answer as it demonstrated in Fig. 2. The owner
of a sample is an expert that gives the best (correct and most
confident) answer for this sample. If we assume the single
owner for every sample then in the community functioning
for problem solving this single owner gives the final result
(Fig. 3).
We aim to train the community of agents in such a way that
they will give correct self-confident answers to the samples
they own, and do not make large mistakes on all other
examples they never met before. The desired histogram of
answers is presented in Fig. 3.
Learning is minimisation of error functionals, which is
defined for any selected sample and any local expert. This
error function should be different for owners and non-ofners
of the sample. If we assume that each smalpe has a single
owner then the error function presented in Fig. 5 can be used.
Voting of k most self-confident experts (Fig. 6) can make
the decision more stable. This voting may be organised with
weights of votes, which depend on the individual experts’ level
of confidence, or without weights, just as a simple voting. The
modified error function for system with collective ownership
(each sample has k owners) is needed (Fig. 7). This function
is constructed to provide proper answers of all k owners.
III. S ELF - LEARNING S TAGE : C OMMUNITIES AND
R ECOMMENDER S YSTEMS
After the stage of supervising learning, community of local
experts can start working with new, previously unlabeled data.

The answer
we accepted
after voting

Diagonal

Class 1
s

The range of answers

Figure 6. Interperation of community answer with collective ownership:
Voting of k most self-confident winners.

For a new example, the owners will be identified and the
task will be solved by the owners following decision from
Figs. 3, 6 or similar rules with distribution of responsibility
between the most self-confident experts. After such labeling
steps the learning cycles should follow with improvement
of experts’ performance (they should give the correct selfconfident answers to the samples they own, and do not make
large mistakes for all other examples).
This regular alternation, solving new tasks – learning –
solving new task – ..., provides adaptation to the graduate
change in reality and assimilation of growing data. It is not
compulsory that all local experts are answering the same tasks.
A sort of soft biclustering systems of experts and problems
should be implemented to link a problem to potential experts

1st owner estimate
2nd owner estimate
………………………….
kth owner estimate

Incorrect class

-δ

Diagonal

Ideal solutions
for owners
Correct class
s
ε

Ideal solutions for non-owners

Figure 7. Soft margin error function for owners and non-owners ( k owners).

and an expert to tasks it can own. Selection of experts should
be done with some excess to guarantee sufficient number
of selected skilled experts for correct solution. Originally
[8], a version of neural network associative memory was
proposed to calculate the relative weight of an expert for
solution of a problem (we can call it “affinity of an expert to
a problem”). A well-developed technology of recommender
systems [24] includes many solutions potentially usable for
recommendations of local experts to problems and problems
to local experts. Implementation of a recommender system for
the assignment of local experts to solve problems transforms
the community of agents into hierarchical “social network”
with various nodes and groups.

Inputs

Legacy AI System 1
Internal Signals

Outputs
Outputs

Corrector 1

Correction

Objectives of the community self-learning are:
• Assimilation of incrementally growing data;
• Adaptation to graduate change in reality;
• Non-iterative knowledge transfer from the locally best
experts to other agents;
In the community self-learning process for each sample the
locally best experts (owners) find the label. After the labeling,
the skills should be improved. The supervised learning of
large multiagent system requires large resources. It should no
destroy the previous skills and, therefore, the large labeled
data base of previous tasks should be used. It can require
large memory and many iterations, which involve all the local
experts. It is desirable to correct the errors (or increase the
level of confidence, if it is too low) without destroying of
previously learned skills. It is also very desirable to avoid
usage of large database and long iterative process.
Communities of AI systems in real world will work on
the basis of heterogeneous networks of computational devices
and in heterogeneous infrastructure. Real-time correction of
mistakes in such heterogeneous systems by re-training is not
always viable due to the resources involved. We can, therefore, formulate the technical requirements for the correction
procedures [17]. Corrector should:
• be simple;
• not destroy the existing skills of the AI systems;
• allow fast non-iterative learning;
• allow correction of new mistakes without destroying of
previous corrections.
Surprisingly, all these requirements can be met in sufficiently
high dimensions. For this purpose, we propose to employ the
concept of corrector of legacy AI systems, developed recently
[16], [21] on the basis of stochastic separation theorems [20].
For high-dimensional distributions in n-dimensional space
every point from a large finite set can be separated from all
other points by a simple linear discriminant. The size of this
finite set can grow exponentially with n. For example, for the
equidistribution in an 100-dimensional ball, with probability
> 0.99 every point in 2.7 · 106 independently chosen random
points is linearly separable from the set of all other points.

Legacy AI System 2

Inputs

Correction

IV. C ORRECTORS , K NOWLEDGE T RANSFER , AND
I NTERIORISATION

Figure 8. Corrector of AI errors.

Corrector 2

Figure 9. Cascade of AI correctors

The idea of a corrector is simple. It corrects an error of
a single local expert. Separate the sample with error from
all other samples by a simple discriminant. This discriminant
splits the space of samples into two subsets: the sample with
errors belongs to one of them, and all other samples belong
to “another half”. Modify the decision rule for the set, which
includes the erroneous sample. This is corrector of a legacy
AI system (Fig. 8). Inputs for this corrector may include input
signals, and any internal or output signal of the AI system.
One corrector can correct several errors (it is useful to
cluster them before corrections). For correction of many errors,
cascades of correctors are employed [17]: the AI system with
the first corrector is a new legacy AI system and can be
corrected further, as presented in Fig. 9. In this diagram, the
original legacy AI system (shown as Legacy AI System 1) is
supplied with a corrector altering its responses. The combined
new AI system can in turn be augmented by another corrector,
leading to a cascade of AI correctors.
Fast knowledge transfer between AI systems can be organised using correctors [22]. The “teacher” AI labels the
samples, and a “student” AI also attempts to label them. If
their decisions coincide (with the desired level of confidence)
then nothing happens. If they do not coincide (or the level of
confidence of a student is too low) then a corrector is created

for the student. From the technological point of view it is more
efficient to collect samples with student’s errors, then cluster
these samples and create correctors for the clusters, not for the
individual mistakes. Moreover, new real-world samples are not
compulsory needed in the knowledge transfer process. Just a
large set of randomly generated (simulated) samples labeled
by the teacher AI and the student AI can be used for correction
of the student AI with skill transfer from the teacher AI.
Correctors assimilate new knowledge in the course of the
community self-learning process (Fig. 10). After collection
of a sufficiently large cascade of correctors, a local expert
needs to assimilate this knowledge in its internal structure.
The main reason for such interiorisation is restoring of the
regular essentially high-dimensional structure of the distribution of preprocessed samples with preservation of skills.
This process can be iterative but it is much simpler that the
initial supervising learning. The local expert with the cascade
of correctors becomes the teacher AI, and the same expert
without correctors becomes the student AI (see Fig. 10).
Available real dataset can be supplemented by the randomly
simulated samples and, after iterative learning the skills from
the teacher are transferred to the student (if the capacity of the
student is sufficient). The student with updated skills returns
to the community of local experts.
Two important subsystems are not present in Fig. 10):
the manager – recommender and the ultimate auditor. The
manager – recommender distributes tasks to local experts and
local experts to tasks. It takes decisions on the basis of the
previous experience of problem solving and assigns experts
to problems with an adequate surplus, for reliability, and with
some stochastisation, for the training of various experts and
for the extension of experts’ pool.
In practice, the self-learning and self-labeling of samples
performed by the selected local experts is supplemented by
the labeling of samples and critics of decisions by an ultimate
auditor. First of all, this auditor is the real practice itself:
the real consequences of the decisions return to the systems.
Secondly, the ultimate audit may include inspection by a
qualified human or by a special AI audit system with additional
skills.
V. M ATHEMATICAL FOUNDATIONS OF NON - DESTRUCTIVE
AI CORRECTION
A. General stochastic separation theorem
Bárány and Zoltán [25] studied properties of highdimensional polytopes deriving from uniform distribution in
the n-dimensional unit ball. They found that in the envelope of
M random points all of the points are on the boundary of their
convex hull and none belong to the interior (with probability
greater than 1 − c2 , provided that M ≤ c2n/2 , where c > 0
in an arbitrary constant). They also show that the bound on
M is nearly tight, up to polynomial factor in n. Donoho and
Tanner [19] derived a similar result for i.i.d. points from the
Gaussian distribution. They also mentioned that in applications
it often seems that Gaussianity is not required and stated the
problem of characterisation of ensembles leading to the same

qualitative effects (‘phase transitions’), which are found for
Gaussian polytopes.
Recently, we noticed that these results could be proven for
many other distributions, indeed, and one more important (and
surprising) property is also typical: every point in this M point random set can be separated from all other points of
this set by the simplest linear Fisher discriminant [16], [20].
This observation allowed us to create the corrector technology
for legacy AI systems [21]. We used the ‘thin shell’ measure
concentration inequalities to prove these results [17], [20].
Separation by linear Fisher’s discriminant is practically most
important Surprise 4 in addition to three surprises mentioned
in [19].
The standard approach assumes that the random set consists
of independent identically distributed (i.i.d.) random vectors.
The new stochastic separation theorem presented below does
not assume that the points are identically distributed. It can
be very important: in the real practice the new datapoints
are not compulsory taken from the same distribution that the
previous points. In that sense the typical situation with the
real data flow is far from an i.i.d. sample (we are grateful to
G. Hinton for this important remark). This new theorem gives
also an answer to the open problem from [19]: it gives the
general characterisation of the wide class of distributions with
stochastic separation theorems (the SmAC condition below).
Roughly speaking, this class consists of distributions without
sharp peaks in sets with exponentially small volume (the
precise formulation is below). We call this property “Smeared
Absolute Continuity” (or SmAC for short) with respect to
the Lebesgue measure: the absolute continuity means that the
sets of zero measure have zero probability, and the SmAC
condition below requires that the sets with exponentially small
volume should not have high probability. Below Bn is a
unit ball in Rn and Vn denotes the n-dimensional Lebesgue
measure.
Consider a family of distributions, one for each pair of
positive integers M and n. The general SmAC condition is
Definition 1. The joint distribution of x1 , x2 , . . . , xM has
SmAC property if there are exist constants A > 0, B ∈ (0, 1),
and C > 0, such that for every positive integer n, any convex
set S ∈ Rn such that
Vn (S)
≤ An ,
Vn (Bn )
any index i
∈
{1, 2, . . . , M }, and
y 1 , . . . , y i−1 , y i+1 , . . . , y M in Rn , we have

any

P(xi ∈ Bn \ S | xj = y j , ∀j 6= i) ≥ 1 − CB n .

points
(1)

We remark that
• We do not require for SmAC condition to hold for all
A < 1, just for some A > 0. However, constants A, B,
and C should be independent from M and n.
• We do not require that xi are independent. If they are,
(1) simplifies to
P(xi ∈ Bn \ S) ≥ 1 − CB n .

Correctors

Agents
`

`

Community learning
`

`
`

Interiorisation

Supervisor

`

`
Figure 10. Community learning, self-learning, and interiorisation of knowledge.

We do not require that xi are identically distributed.
The unit ball Bn in SmAC condition can be replaced by
an arbitrary ball, due to rescaling.
• We do not require the distribution to have a bounded
support - points xi are allowed to be outside the ball, but
with exponentially small probability.
The following proposition establishes a sufficient condition
for SmAC condition to hold.
•

•

Proposition 1. Assume that x1 , x2 , . . . , xM are continuously
distributed in Bn with conditional density satisfying
ρn (xi | xj = y j , ∀j 6= i) ≤

C
rn Vn (Bn )

(2)

for any n, any index i ∈ {1, 2, . . . , M }, and any points
y 1 , . . . , y i−1 , y i+1 , . . . , y M in Rn , where C > 0 and r > 0
are some constants. Then SmAC condition holds with the same
C, any B ∈ (0, 1), and A = Br.
Proof.
Z
P(xi ∈ S | xj = y j , ∀j 6= i) =

ρn (xi | xj = y j , ∀j 6= i)dV
S

Z
≤

C
C
dV = Vn (S) n
rn Vn (Bn )
r Vn (Bn )

S

≤ An Vn (Bn )

C
= CB n .
rn Vn (Bn )

If x1 , x2 , . . . , xM are independent with xi having density
ρi,n : Bn → [0, ∞), (2) simplifies to
ρi,n (x) ≤

C
,
rn Vn (Bn )

∀n, ∀i, ∀x ∈ Bn ,

(3)

where C > 0 and r > 0 are some constants.
With r = 1, (3) implies that SmAC condition holds
for probability distributions whose density is bounded by a
1
constant times density ρuni
:= Vn (B
of uniform distribution
n
n)
in the unit ball. With arbitrary r > 0, (3) implies that SmAC
condition holds whenever ration ρi,n /ρuni
grows at most
n
exponentially in n. This condition is general enough to hold
for many distributions of practical interest.
Example 1. (Unit ball) If x1 , x2 , . . . , xM are i.i.d random
points from the equidistribution in the unit ball, then (3) holds
with C = r = 1.
Example 2. (Randomly perturbed data) Fix parameter  ∈
(0, 1) (random perturbation parameter). Let y 1 , y 2 , . . . , y M
be the set of M arbitrary (non-random) points inside the ball
with radius 1 −  in Rn . They might be clustered in arbitrary
way, all belong to a subspace of very low dimension, etc. Let
xi , i = 1, 2, . . . , M be a point, selected uniformly at random
from a ball with center y i and radius . We think about xi

as “perturbed” version of y i . In this model, (3) holds with
C = 1, r = .
Example 3. (Uniform distribution in a cube) Let
x1 , x2 , . . . , xM be i.i.d random points from the
equidistribution in the unit cube. Without loss of
pgenerality,
4/n. Then
we can scale the cube
to
have
side
length
s
=
q

(3) holds with r <

Proof. If n < N (b), then M ≤ abn ≤ b−N (b) bn < 1, a
contradiction. Let n ≥ N (b), and let F = {x1 , x2 , . . . , xM }.
Then
P(F ⊂ Bn ) ≥ 1 −

2
πe .

≥1−

i=1
M
X

P(xi 6∈ Bn )
CB n = 1 − M CB n ,

i=1

Remark 1. In this case,
π n/2 /Γ(n/2 + 1)
Vn (Bn )
=
Vn (Bn )ρi,n (x) = p
(4/n)n/2
( 4/n)n
r n
n/2 n/2
n/2 n/2
(π/4) n
1
πe
(π/4) n
<
≤ √
≈p
,
n/2
Γ(n/2)
2
2 π
4π/n(n/2e)
where ≈ means Stirling’s approximation for gamma function
Γ.
Example 4. (Product distribution in unit cube) Let
x1 , x2 , . . . , xM be independent random points from the product distribution in the unit cube, with component j of point xi
having a continuous distribution with density ρi,j . Assume that
all ρi,j are bounded from above
q by some absolute constant K.

Then (3) holds with r <
the cube).

M
X

1
K

2
πe

where the second inequality follows from (1). Next,
P(F is linearly separable | F ⊂ Bn )
≥1−

P(xi ∈ conv(F \ {xi }) | F ⊂ Bn ).

i=1

For set S = conv(F \ {xi })
Vn (S)
≤ V (n, M − 1) ≤ V (n, bn )
Vn (Bn )
n
 p
< 3 log(b) ≤ An ,
where we have used (4) and inequalities a ≤ 1, b ≤
exp((A/3)2 ). Then SmAC condition implies that

(after appropriate scaling of

P(xi ∈ conv(F \ {xi }) | F ⊂ Bn )
= P(xi ∈ S | F ⊂ Bn ) ≤ CB n .

n

A finite set F ⊂ R is called linearly separable if the
following equivalent conditions hold.
• For each x ∈ F there exists a linear functional l such
that l(x) > l(y) for all y ∈ F , y 6= x;
• Each x ∈ F is an extreme point (vertex) of convex hull
of F .
Below we prove the separation theorem for distributions satisfying SmAC condition. The proof is based on the following
result, see [26]

M
X

Hence,
P(F is linearly separable | F ⊂ Bn ) ≥ 1 − M CB n ,
and
P(F is linearly separable) ≥ (1 − M CB n )2
≥ 1 − 2M CB n ≥ 1 − 2abn CB n ≥ 1 − δ,
where the last inequality follows from a ≤ δ/2C, b ≤ 1/B.

Proposition 2. Let
V (n, M ) =

1
max
Vn (conv{x1 , . . . , xM }),
Vn (Bn ) x1 ,...,xM ∈Bn

B. Stochastic separation by Fisher’s linear discriminant

According to the general stochastic separation theorems
there exist linear functionals, which separate points in a
where conv denotes the convex hull. Then
random set (with high probability and under some condin 1/n
1/2
tions). Such a linear functional can be found by various
V (n, c )
< (2e log c) (1 + o(1)), 1 < c < 1.05.
iterative methods, from the Rosenblatt perceptron learning rule
Proposition 2 implies that for every c ∈ (1, 1.05), there to support vector machines. This existence is nice but for
exists a constant N (c), such that
applications we need the non-iterative learning. It would be
p
very desirable to have an explicit expression for separating
V (n, cn ) < (3 log c)n , n > N (c).
(4) functionals.
There exists a general scheme for creation of linear discrimTheorem 1. Let {x1 , . . . , xM } be a set of random points
n
inants
[17], [22]. For separation of single points from a data
in R from distribution satisfying SmAC condition. Then
cloud
it
is necessary:
{x1 , . . . , xM } is linearly separable with probability greater
1) Centralise the cloud (subtract the mean point from all
than 1 − δ, δ > 0, provided that
data vectors).
M ≤ abn ,
2) Escape strong multicollinearity, for example, by principal component analysis and deleting minor components,
where
which correspond to the small eigenvalues of empiric
b = min{1.05, 1/B, exp((A/3)2 )}, a = min{1, δ/2C, b−N (b) }.
covariance matrix.

3) Perform whitening (or spheric transformation), that is
a linear transformation, after that the covariance matrix
becomes a unit matrix. In principal components whitening is simply the normalisation of coordinates to unit
variance.
4) The linear inequality for separation of a point x from
the cloud Y in new coordinates is
(x, y) ≤ α(x, x), for all y ∈ Y.

(5)

where α ∈ (0, 1) is a threshold, and (•, •) is the standard
Euclidean inner product in new coordinates.
In real applied problems, it could be difficult to perform
the precise whitening but a rough approximation to this
transformation could also create useful discriminants (5). We
will call ‘Fisher’s discriminants’ all the discriminants created
non-iteratively by inner products (5), with some extension of
meaning.
Formally, we say that finite set F ⊂ Rn is Fisher-separable
if
(x, x) > (x, y),
(6)
holds for all x, y ∈ F such that x 6= y.
Two following theorems demonstrate that Fisher’s discriminants are powerful in high dimensions.
Theorem 2 (Equidistribution in Bn [16], [20]). Let
{x1 , . . . , xM } be a set of M i.i.d. random points from the
equidustribution
in the unit ball Bn . Let 0 < r < 1, and
√
ρ = 1 − r2 . Then




xM
P kxM k > r and xi ,
< r for all i 6= M
kxM k
(7)
n
n
≥ 1 − r − 0.5(M − 1)ρ ;




xj
P kxj k > r and xi ,
< r for all i, j, i 6= j
kxj k
(8)
n
n
≥ 1 − M r − 0.5M (M − 1)ρ ;




xj
xi
,
< r for all i, j, i 6= j
P kxj k > r and
kxi k kxj k
n
≥ 1 − M r − M (M − 1)ρn .
(9)
According to Theorem 2, the probability that a single
element xM from the sample S = {x1 , . . . , xM } is linearly
separated from the set S \ {xM } by the hyperplane l(x) = r
is at least
n
1 − rn − 0.5(M − 1) 1 − r2 2 .
This probability estimate depends on both M = |S| and
dimensionality n. An interesting consequence of the theorem
is that if one picks a probability value, say 1 − ϑ, then the
maximal possible values of M for which the set S remains
linearly separable with probability that is no less than 1 − ϑ
grows at least exponentially with n. In particular, the following
holds

Corollary 1. Let {x1 , . . . , xM } be a set of M i.i.d. random
points from the equidustribution
in the unit ball Bn . Let 0 <
√
r, ϑ < 1, and ρ = 1 − r2 . If
M < 2(ϑ − rn )/ρn ,

(10)

then P((xi , xM ) < rkxM k for all i = 1, . . . , M −1) > 1−ϑ.
If


p
M < (r/ρ)n −1 + 1 + 2ϑρn /r2n ,
(11)
then P((xi , xj ) < rkxi k for all i, j = 1, . . . , M, i 6= j) ≥
1 − ϑ.
In particular, if inequality (11) holds then the set
{x1 , . . . , xM } is Fisher-separable with probability p > 1 − ϑ.
Note that (9) implies that elements of the set {x1 , . . . , xM }
are pair-wise almost or ε-orthogonal, i.e. | cos(xi , xj )| ≤ ε
for all i 6= j, 1 ≤ i, j ≤ M , with probability larger or equal
than 1 − 2M rn − 2M (M − 1)ρn . Similar to Corollary 1, one
can conclude that the cardinality M of samples with such
properties grows at least exponentially with n. Existence of
the phenomenon has been demonstrated in [27]. Theorem 2,
Eq. (9), shows that the phenomenon is typical in some sense
(cf. [28], [29]).
The linear separability property of finite but exponentially
large samples of random i.i.d. elements is not restricted to
equidistributions in Bn . As has been noted in [21], it holds
for equidistributions in ellipsoids as well as for the Gaussian
distributions. Moreover, it can be generalized to product distributions in a unit cube. Consider, e.g. the case when coordinates
of the vectors x = (X1 , . . . , Xn ) in the set S are independent
random variables Xi , i = 1, . . . , n with expectations X i and
variances σi2 > σ02 > 0. Let 0 ≤ Xi ≤ 1 for all i = 1, . . . , n.
The following analogue of Theorem 2 can now be stated.
Theorem 3 (Product distribution in a cube [20]). Let
{x1 , . . . , xM } be i.i.d. random points from the product distribution in a unit cube. Let
X
R02 =
σi2 ≥ nσ02 .
i

Assume that data are centralised and 0 < δ < 2/3. Then

(xi , xM ) √
kxj k2
≤ 1 + δ and
< 1−δ
P 1−δ ≤
2
R0
R0 kxM k

 (12)
for all i, j, i 6= M ≥ 1 − 2M exp −2δ 2 R04 /n

− (M − 1) exp −2R04 (2 − 3δ)2 /n ;

kxj k2
(xi , xj ) √
P 1−δ ≤
≤ 1 + δ and
< 1−δ
2
R0
R0 kxj k


(13)
for all i, j, i 6= j ≥ 1 − 2M exp −2δ 2 R04 /n

− M (M − 1) exp −2R04 (2 − 3δ)2 /n .
In particular, under the conditions of Theorem 3, set
{x1 , . . . , xM } is Fisher-separable with probability p > 1 − ϑ,
provided that M ≤ abn , where a > 0 and b > 1 are some
constants depending only on ϑ and σ0 .

Figure 11. Point x should not belong to the filled ball (excluded volume) to
be separable from y by the linear discriminant (5). Here, c is the centre of
data cloud, and Lx is the hyperplane such that (x, z) = (x, x) for z ∈ Lx .

The proof of Theorem 3 is based on concentration inequalities in product spaces [30]. Numerous generalisations of Theorems 2, 3 are possible for different classes of distributions,
for example, for weakly dependent variables, etc.
We can see from Theorem 3 that the discriminant (5) works
without precise whitening. Just the absence of strong degeneration is required: the support of the distribution contains in
the unit cube (that is bounding from above) and, at the same
time, the variance of each coordinate is bounded from below
by σ0 > 0.
Linear separability, as an inherent property of data sets in
high dimension, is not necessarily confined to cases whereby
a linear functional separates a single element of a set from the
rest. Theorems 2, 3 be generalized to account for m-tuples,
m > 1 too [17], [22].
Let us make several remarks for the general distributions.
For each data point y the probability that a randomly chosen
point x is not separated from y by the discriminant (6) (i.e.
that the inequality (6) is false) is (Fig. 11)
Z
p = py =
ρ(z)dz,
(14)
kz− y2 k≤ kyk
2
where ρ(z)dz is the probability measure. We need to evaluate
the probability of finding a random point outside the union
of N such excluded volumes. For example, for the equidistribution in a ball Bn , py < 1/2n for all y from the ball. The
probability to select a point inside the union of N ‘forbidden
balls’ is less than N/2n for any position of N points y in Bn .
Inequalities (7), (8), and (9) are closely related to that fact.
Instead of equidistribution in a ball Bn , we can take
probability distributions with bounded density ρ in a ball Bn
ρ(y) <

C
,
rn Vn (Bn )

(15)

where C > 0 is an arbitrary constant, Vn (Bn ) is the volume
of the ball, and radius r > 1/2. This inequality guarantees
that the probability of each ball with radius less or equal than
1/2 exponentially decays for n → ∞. It should be stressed
that in asymptotic analysis for large n the constant C > 0 is
arbitrary but does not depend on n.

For the bounded distributions (15) the separability by linear
discriminants (5) is similar to separability for the equidistributions. The proof through the estimation of the probability
to avoid the excluded volume is straightforward.
For the practical needs, the number of points N is large.
We have to evaluate the sum py for N points y. For most
estimates, evaluation of the expectations and variances of py
(14) will be sufficient, if points y are independently chosen.
If the distribution is unknown and exists just in the form
of the sample of empirical points, we can evaluate E(p) and
var(p) (14) from the sample directly, without knowledge of
theoretical probabilities.
Bound (15) is the special case of (3) with r > 1/2, and it
is more restrictive: in Examples 2, 3, and 4, the distributions
satisfy (3) with some r < 1, but fail to satisfy (15) if
r < 1/2. Such distributions has the SmAC property and the
corresponding set of points {x1 , . . . , xM } is linearly separable
by Theorem 1, but different technique is needed to establish its
Fisher-separability. One option is to estimate the distribution
of p in (14). Another technique is based on concentration
inequalities. For some distributions, one can prove that, with
exponentially high probability, random point x satisfies
r1 (n) ≤ kxk ≤ r2 (n),

(16)

where k • k denotes the Euclidean norm in Rn , and r1 (n) and
r2 (n) are some lower and upper bounds, depending on n. If
r2 (n) − r1 (n) is small comparing to r1 (n), it means that the
distribution is concentrated in a thin shell between the two
spheres. If x and y satisfy (16), inequality
p (6) may fail only
if y belongs to a ball with radius R = r22 (n) − r12 (n). If R
is much lower than r1 (n)/2, this method may provide much
better probability estimate than (14). This is how Theorem 3
was proved in [20].
VI. S EPARATION THEOREM FOR LOG - CONCAVE
DISTRIBUTIONS

A. Log-concave distributions
In [20] we proposed several possible generalisations of
Theorems 2, 3. One of them is the hypothesis that for the
uniformly log-concave distributions the similar result can be
formulated and proved. Below we demonstrate that this hypothesis is true, formulate and prove the stochastic separation
theorems for several classes of log-concave distributions. Additionally, we prove the comparison (domination) Theorem 5
that allows to extend the proven theorems to wider classes of
distributions.
In this subsection, we introduce several classes of logconcave distributions and prove some useful properties of these
distributions.
Let P = {Pn , n = 1, 2, . . . } be a family of probability
measures with densities ρn : Rn → [0, ∞), n = 1, 2, . . . .
Below, x is Ra random variable (r.v) with density ρn , and
En [f (x)] := Rn f (z)ρn (z)dz is the expectation of f (x).
We say that density ρn : Rn → [0, ∞) (and the corresponding probability measure Pn ):

•

is whitened, or isotropic, if En [x] = 0, and
En [(x, θ)2 )] = 1

•

•

for all t, s > 0 such that t + s = 1, then inequality

∀θ ∈ S n−1 ,

(17)

where S n−1 is the unit sphere in Rn , and (•, •) is
the standard Euclidean inner product in Rn . The last
condition is equivalent to the fact that the covariance
matrix of the components of x is the identity matrix,
see [32].
is log-concave, if set Dn = {z ∈ Rn | ρn (z) > 0} is
convex and g(z) = − log(ρn (z)) is a convex function on
Dn .
is strongly log-concave (SLC), if g(z) = − log(ρn (z))
is strongly convex, that is, there exists a constant c > 0
such that


u+v
g(u) + g(v)
−g
≥ c||u−v||2 ,
∀u, v ∈ Dn .
2
2

For example, density ρG (z) = √ 1 n exp − 12 ||z||2
(2π)

•

•

•

of n-dimensional standard normal distribution is strongly
log-concave with c = 81 .
has sub-Gaussian decay for the norm (SGDN), if there
exists a constant  > 0 such that

En [exp ||x||2 ] < +∞.
(18)
In particular, (18) holds for ρG with any  < 12 . However,
unlike SLC, (18) is an asymptotic property, and is not
affected by local modifications of the underlying density.
For example, density ρ(z) = C1 exp(−g(||z||)), z ∈
1
n
2
RR , where g(t) = 2 max{1, t }, t ∈ R and 1C =
exp(−g(||z||))dz has SGDN with any  < 2 , but
Rn
it is not strongly log-concave.
has sub-Gaussian decay in every direction (SGDD), if
there exists a constant B > 0 such that inequality

2
t
Pn [(x, θ) ≥ t] ≤ 2 exp −
B
holds for every θ ∈ S n−1 and t > 0.
is ψα with constant Bα > 0, α ∈ [1, 2], if
(En |(x, θ)|p )

1/p

≤ Bα p1/α En |(x, θ)|2

holds for every for every θ ∈ S

n−1

1/2

(19)

and all p ≥ 2.

Proposition 3. Let ρn : Rn → [0, ∞) be an isotropic logconcave density, and let α ∈ [1, 2]. The following implications
hold.
ρn is SLC ⇒ ρn has SGDN ⇒ ρn has SGDD ⇔
⇔ ρn is ψ2 ⇒ ρn is ψα ⇒ ρn is ψ1 ⇔ ALL ,
where the last ⇔ means the class of isotropic log-concave
densities which are ψ1 actually coincides with the class of all
isotropic log-concave densities.
Proof. Proposition 3.1 in [33] states that if there exists c1 > 0
such that g(x) = − log(ρn (x)) satisfies
c1 ts
tg(u) + sg(v) − g (tu + sv) ≥
||u − v||2 , ∀u, v ∈ Dn .
2
(20)

En [f 2 (x) log f 2 (x)] − En [f 2 (x)]En [log f 2 (x)] ≤
2
≤ En [||∇f (x)||2 ]
c1

(21)

holds for every smooth function f on Rn . As remarked in
[33, p. 1035], “it is actually enough that (20) holds for some
t, s > 0, t + s = 1”. With t = s = 1/2, this implies
that (21) holds for every strongly log-concave distribution,
with c1 = 8c. By [34, Theorem 3.1], (21) holds for ρn
if and only if it has has sub-Gaussian decay for the norm,
and the implication ρn is SLC ⇒ ρn has SGDN follows.
Also, by [37, Theorem 1(i)], if√(21) holds for ρn , then it
is ψ2 with constant B2 = d/ c, where d is a universal
constant, hence ρn has SGDN ⇒ ρn is ψ2 . The equivalence ρn has SGDD ⇔ ρn is ψ2 follows from (17) and [35,
Lemma 2.2.4]. The implications ρn is ψ2 ⇒ ρn is ψα ⇒
ρn is ψ1 follow from (19). Finally, [35, Theorem 2.4.6]
implies that every log-concave density ρn is ψ1 with some
universal constant.
B. Fisher-separability for log-concave distributions
Below we prove Fisher-separability for i.i.d samples from
isotropic log-concave ψα distributions, using the the technique
based on concentration inequalities.
Theorem 4. Let α ∈ [1, 2], and let P = {Pn , n = 1, 2, . . . }
be a family of probability measures with densities ρn : Rn →
[0, ∞), n = 1, 2, . . . , which are ψα with constant Bα > 0,
independent from n. Let {x1 , . . . , xM } be a set of M i.i.d.
random points from ρn . Then there exist constants a > 0 and
b > 0, which depends only on α and Bα , such that, for any
i, j ∈ {1, 2, . . . , M }, inequality
(xi , xi ) > (xi , xj )
holds with probability at least 1 − a exp(−bnα/2 ). Hence,
for any δ > 0, set {x1 , . . . , xM } is Fisher-separable with
probability greater than 1 − δ, provided that
r


2δ
b α/2
M≤
.
(22)
exp
n
a
2
Proof. Let x and y be two points, selected independently at
random from the distribution with density ρn . [31, Theorem
1.1], (applied with A = In , where In is n × n identity
matrix) states that,
for any t ∈ √(0, 1), (16) holds with
√
r1 (n) = (1 − t) n, r2 (n) = (1 + t) n, and with probability
at least 1 − A exp(−Bt2+α nα/2 ), where A, B > 0 are
constants depending only on α. If (16) holds for x and y,
inequality (6)pmay fail only if √y belongs to a ball with
radius Rn = r22 (n) − r12 (n) = 4tn. Theorem 6.2 in [36],
applied with A = In , states that, for any  ∈ (0, 0√
), y does
not belong to a ball with any center and radius  n, with
α/2
probability at least 1 − Cn
for some constants √0 > 0
and C > 0. By selecting t = 20 /8, and  =
4t =
0 /2, we conclude that (6) holds with probability at least

√
α/2
1 − 2A exp(−Bt2+α nα/2 ) − ( 4t)Cn . This is greater than
α/2
1 − a exp(−bn ) for some constants a > 0 and b > 0.
Hence, x1 , x2 , . . . , xM are Fisher-separable with probability
greater than 1 − M (M2 −1) a exp(−bnα/2 ). This is greater than
1 − δ provided that M satisfies (22).
Corollary 2. Let {x1 , . . . , xM } be a set of M i.i.d. random
points from an isotropic log-concave distribution in Rn . Then
set {x1 , . . . , xM } is Fisher-separable with probability greater
than 1 − δ, δ > 0, provided that
√

M ≤ ac

n

,

where a > 0 and c > 1 are constants, depending only on δ.
Proof. This follows from Theorem 4 with α = 1 and the
fact that all log-concave densities are ψ1 with some universal
constant, see Proposition 3.
We say that family P = {Pn , n = 1, 2, . . . } of probability
measure has exponential Fisher separability if there exist
constants a > 0 and b ∈ (0, 1) such that, for all n, inequality
(6) holds with probability at least 1 − abn , where x and y are
i.i.d vectors in Rn selected with respect to Pn . In this case, for
any δ > 0, M i.i.d vectors {x1 , . . . , xM } are Fisher-separable
with probability at least 1 − δ provided that
r 
n
1
2δ
√
M≤
.
a
b
Corollary 3. Let P = {Pn , n = 1, 2, . . . } be a family of
isotropic log-concave probability measures which are all ψ2
with the same constant B2 > 0. Then P has exponential Fisher
separability.
Proof. This follows from Theorem 4 with α = 2 .
Corollary 4. Let P = {Pn , n = 1, 2, . . . } be a family
of isotropic probability measures which are all strongly logconcave with the same constant c > 0. Then P has exponential
Fisher separability.
Proof. The proof of Proposition 3√implies that Pn are all ψ2
with the same constant B2 = d/ c, where d is a universal
constant. The statement then follows from Corollary 3.
Example 5. Because standard normal distribution in Rn is
strongly log-concave with c = 81 , Corollary 4 implies that the
family of standard normal distributions has exponential Fisher
separability.
C. Domination
0

{P0n ,

We say that family P =
n = 1, 2, . . . } dominates
family P = {Pn , n = 1, 2, . . . } if there exists a constant C
such that
Pn (S) ≤ C · P0n (S)
(23)
holds for all n and all measurable subsets S ⊂ Rn . In
particular, if P0n and Pn have densities ρ0n : Rn → [0, ∞)
and ρn : Rn → [0, ∞), respectively, then (23) is equivalent to
ρn (x) ≤ C · ρ0n (x),

∀x ∈ Rn .

(24)

Theorem 5. If family P 0 has exponential Fisher separability,
and P 0 dominates P, then P has exponential Fisher separability.
Proof. For every x = (x1 , . . . , xn ) ∈ Rn and y =
(y1 , . . . , yn ) ∈ Rn , let x×y be a point in R2n with coordinates
(x1 , . . . , xn , y1 , . . . , yn ). Let Qn be the product measure of
Pn with itself, that is, for every measurable set S ⊂ R2n ,
Qn (S) denotes the probability that x × y belongs to S, where
vectors x and y are i.i.d vectors selected with respect to Pn .
Similarly, let Q0n be the product measure of P0n with itself.
Inequality (23) implies that
Qn (S) ≤ C 2 · Q0n (S),

∀S ⊂ R2n .

Let An ⊂ R2n be the set of all x×y such that (x, x) ≤ (x, y).
Because P 0 has exponential Fisher separability, Q0n (An ) ≤
abn for some a > 0, b ∈ (0, 1). Hence,
Qn (An ) ≤ C 2 · Q0n (An ) ≤ (aC 2 )bn ,
and exponential Fisher separability of P follows.
Corollary 5. Let P = {Pn , n = 1, 2, . . . } be a family
of distributions which is dominated by a family of (possibly
scaled) standard normal distributions. Then P has exponential
Fisher separability.
Proof. This follows from Example 5, Theorem 5, and the fact
that scaling does not change Fisher separability.
VII. Q UASIORTHOGONAL SETS AND F ISHER
SEPARABILITY OF NOT I . I . D . DATA
The technique based on concentration inequalities usually
fails if the data are not identically distributed, because, in this
case, each xi may be concentrated in its own spherical shell.
An alternative approach to prove separation theorems is to use
the fact that, in high dimension, almost all vectors are almost
orthogonal [28], which implies that (x, y) in (6) is typically
“small”. Below we apply this idea to prove Fisher separability
of exponentially large families in the “randomly perturbed”
model described in Example 2.
Consider the “randomly perturbed” model from Example 2.
In this model, Fisher’s hyperplane for separation each point
xi will be calculated assuming that coordinate center is the
corresponding cluster centre y i .
Theorem 6. Let {x1 , . . . , xM } be a set of M random points
in the “randomly perturbed” model (see Example 2) with
random perturbation parameter  > 0. For any √1n < δ < 1,
set {x1 , . . . , xM } is Fisher-separable with probability at least
 n
n+1
2M 2 p
2δ
2
−M
1− √
1−δ
.

δ n
In particular, set {x1 , . . . , xM } is Fisher-separable with probability at least 1 − v, v > 0, provided that M < abn , where
a, b are constants depending only on v and .

Proof. Let x ∈ Rn be an arbitrary non-zero vector, and let
u be a vector selected uniformly at random from a unit ball.
Then, for any √1n < δ < 1,

P

x
u
,
||x|| ||u||




≥δ

n+1
2 p
≤ √
1 − δ2
,
δ n

(25)

see [32, Lemma 4.1].
Applying (25) to u = xi − y i , we get



n+1
2 p
xj
u
≥δ ≤ √
,
1 − δ2
, j 6= i,
P
||xj || ||u||
δ n
and also



n+1
yi
2 p
u
1 − δ2
.
P
≥δ ≤ √
,
||y i || ||u||
δ n
On the other hand

P (||xi − y i || ≤ 2δ) =

2δ


n
.

If none of the listed events happen, then projections of
all points xj , j 6= i, on u have length at most δ (because
||xj || ≤ 1, ∀j), while the length of projection of xi on u is
greater than δ, hence xi is separable from other points by
Fisher discriminant (with center y i ). Hence, the probability
that xi is not separable is at most
n+1  2δ n
2M p
√
1 − δ2
+

δ n
The probability that there exist some index i such that xi
is not separable is at most the same expression multiplied by
M.
Theorem 6 is yet another illustration of why randomization
and randomized approaches to learning may improve performance of AI systems (see e.g. [40], [41] for more detailed
discussion on the randomized approaches and supervisory
mechanisms for random parameter assignment).
Moreover, Theorem 6 shows that the cluster structure of
data is not an insurmountable obstacle for separation theorems.
The practical experience ensures us that combination of cluster
analysis with stochastic separation theorems works much
better than the stochastic separation theorems directly, if there
exists a pronounced cluster structure in data. The preferable
way of action is:
•
•
•

Find clusters in data clouds;
Create classifiers for distribution of newly coming data
between clusters;
Apply stochastic separation theorems with discriminant
(5) for each cluster separately.

This is a particular case of the general rule about complementarity between low-dimensional non-linear structures and
high-dimensional stochastic separation [17].

VIII. C ONCLUSION
The continuous development of numerous automated AI
systems for data mining is inevitable. Well-known AI products
capable of responding, at least partially, to elements of the Big
Data Challenge have already been developed by technological
giants such as Amazon, IBM, Google, Facebook, SoftBank
and many others. State-of-the art AI systems for data mining
consume huge and fast-growing collections of heterogeneous
data. Multiple versions of these huge-size systems have been
deployed to date on millions of computers and gadgets across
many various platforms. Inherent uncertainties in data result
in unavoidable mistakes (e.g. mislabelling, false alarms, misdetections, wrong predictions etc.) of the AI data mining
systems, which require judicious use. The successful operation
of any AI system dictates that mistakes must be detected and
corrected immediately and locally in the networks. However,
it is prohibitively expensive and even dangerous to reconfigure
big AI systems in real time.
The future development of sustainable large AI systems
for mining of big data requires creation of technology and
methods for fast non-iterative, non-destructive, and reversible
corrections of Big Data analytics systems and for fast assimilation of new skills by the network of AI. This process should
exclude human expertise as far as it is possible. In this paper
we presented a brief outline of an approach to Augmented AI.
This approach uses communities of interacting AI systems,
fast non-destructive and non-iterative correctors of mistakes,
knowledge transfer between AIs, a recommender system for
distribution of problems to experts and experts to problems,
and various types of audit systems. Some parts and versions
of this technology have been implemented and tested.
Linear Fisher’s discriminant is very convenient and efficiently separates data for many distributions in high dimensions. The cascades of independent linear discriminants are
also very simple and more efficient [16], [21]. We have systematically tested linear and cascade correctors with simulated
data and on the processing of real videostream data [21].
The combination of low-dimensional non-linear decision rules
with the high-dimensional simple linear discriminants is a
promising direction of the future development of algorithms.
New stochastic separation theorems demonstrate that the
corrector technology can be used to handle errors in data flows
with very general probability distributions and far away from
the classical i.i.d. hypothesis.
The technology of Augmented AI is necessary for prevention of the deep failure from the current peak of inflated
interest to intellectual solutions (Fig. 1) into the gorge of
deceived expectations.
ACKNOWLEDGMENT
The proposed corrector methodology was implemented and
successfully tested with videostream data and security tasks
in collaboration with industrial partners: Apical, ARM, and
VMS under support of InnovateUK. We are grateful to them
and personally to I. Romanenko, R. Burton, and K. Sofeikov.
We are grateful to M. Gromov, who attracted our attention to

the seminal question about product distributions in a multidimensional cube, and to G. Hinton for the important remark
that the typical situation with the real data flow is far from
an i.i.d. sample (the points we care about seem to be from
different distributions).
R EFERENCES
[1] L. Columbus, “Gartner’s hype cycle for emerging technologies, 2017
adds 5G and deep learning for first time,” Forbes / Tech / #CuttingEdge,
August 15, 2017.
[2] D.C. Engelbart, “Augmenting human intellect: a conceptual framework,”
Stanford Research Institute, Summary Report, AFOSR-3223, Contract
AF 49(638)-1024. 144 pp. 1962.
[3] A.N. Gorban, E.M. Mirkes, V.G. Tsaregorodtsev, “Generation of explicit
knowledge from empirical data through pruning of trainable neural
networks.” In Neural Networks, 1999. IJCNN’99. International Joint
Conference on 1999 Jul (Vol. 6, pp. 4393-4398). IEEE.
[4] A.N. Gorban, Training Neural Networks, Moscow: USSR-USA JV
“ParaGraph”. 1990.
[5] Y. LeCun, J.S. Denker, S.A. Solla, “Optimal brain damage,” In Advances
in Neural Information Processing Systems, pp. 598–605, 1990.
[6] A.N. Gorban, “Neuroinformatics and applications”, Otkrytye Sistemy,
SUBD [Open Systems, DBMS], 4, 1998. https://www.osp.ru/os/1998/
04/179540/
[7] Plato, “Phaedrus”, translated by B. Jowett,The Project Gutenberg
EBook of Phaedrus, by Plato, 2013. http://www.gutenberg.org/files/
1636/1636-h/1636-h.htm
[8] S.E. Gilev, A.N. Gorban, E.M. Mirkes, “Small experts and internal
conflicts in learning neural networks,” Akademiia Nauk SSSR, Doklady,
vol. 320 (1), pp. 220-223, 1991.
[9] R.A. Jacobs, M.I. Jordan, S..J. Nowlan, G.E. Hinton, “Adaptive mixtures
of local experts,” Neural computation, vol. 3 (1), pp. 79-87, 1991.
[10] S.E. Gilev, A.N. Gorban, D.A. Kochenov, Y.M. Mirkes, S.E. Golovenkin,
S.A. Dogadin, E.V. Maslennikova, G.V. Matyushin, K.G. Nozdrachev,
D.A. Rossiev, V.A. Shulman, “MultiNeuron neural simulator and its
medical applications.” In Proceedings of International Conference On
Neural Information Processing, ICONIP1994, Vol. 3, No. 2, pp. 12611264.
[11] A.N. Gorban, D.A. Rossiev, S.E. Gilev, M.A. Dorrer, D.A. Kochenov,
Y.M. Mirkes, S.E. Golovenkin, S.A. Dogadin, K.G. Nozdrachev, G.V.
Matyushin, V.A. Shulman, A.A. Savchenko,“ Medical and physiological
applications of MultiNeuron neural simulator.” In: DeWitt, J.T. (ed.):
Proceedings of the WCNN’95 (World Congress on Neural Networks’95,
Washington DC, July 1995), pp. 170–175. Lawrence Erlbaum Associate,
1996.
[12] A.N. Gorban, D.A. Rossiev, E.V. Butakova, S.E. Gilev, S.E. Golovenkin,
S.A. Dogadin, M.G. Dorrer, D.A. Kochenov, A.G. Kopytov, E.V.
Maslennikova, G.V. Matyushin, Medical, psychological and physiological applications of MultiNeuron neural simulator. In Neuroinformatics
and Neurocomputers, 1995, Second International Symposium on, pp.
7–14. IEEE, 1995.
[13] P.C. Kainen,“Utilizing geometric anomalies of high dimension: when
complexity makes computation easier.” In Computer-Intensive Methods
in Control and Signal Processing: The Curse of Dimensionality. New
York, Springer, pp. 283–294. 1997.
[14] D.L. Donoho,“ High-dimensional data analysis: The curses and blessings
of dimensionality.” AMS Math Challenges Lecture, 1, 32 pp., 2000.
http://statweb.stanford.edu/∼donoho/Lectures/AMS2000/Curses.pdf
[15] J. Anderson, M. Belkin, N. Goyal, L. Rademacher, J. Voss, “The
More, the Merrier: the Blessing of dimensionality for learning large
Gaussian mixtures,” Journal of Machine Learning Research: Workshop
and Conference Proceedings 35, pp. 1–30, 2014.
[16] A.N. Gorban, I.Y. Tyukin, I. Romanenko, “The Blessing of Dimensionality: Separation Theorems in the Thermodynamic Limit,” IFACPapersOnLine 49-24 , 064–069, 2016.
[17] A. N. Gorban, I.Y. Tyukin, “Blessing of dimensionality: mathematical
foundations of the statistical physics of data,” Phil. Trans. R. Soc. A,
2018. DOI 10.1098/rsta.2017.0237, https://arxiv.org/abs/1801.03421
[18] Ledoux M. 2001 The Concentration of Measure Phenomenon. (Mathematical Surveys & Monographs No. 89). Providence: AMS.

[19] D. Donoho, J. Tanner, “Observed universality of phase transitions in
high-dimensional geometry, with implications for modern data analysis
and signal processing.” Phil. Trans. R. Soc. A 367(1906), 4273-4293,
2009.
[20] A. N. Gorban, I.Y. Tyukin, “Stochastic separation theorems.” Neural
Netw. 94, pp. 255–259, 2017.
[21] A. N. Gorban, I. Romanenko, R. Burton, I.Y. Tyukin. “One-trial correction of legacy AI systems and stochastic separation theorems.” 2016
https://arxiv.org/abs/1610.00494
[22] I.Y. Tyukin, A. N. Gorban, K. Sofeikov, I. Romanenko. “Knowledge
transfer between artificial intelligence systems.” 2017 https://arxiv.org/
abs/1709.01547
[23] I.Y. Tyukin, A. N. Gorban, C. Calvo, J. Makarova, V.A. Makarov. “Highdimensional brain. A tool for encoding and rapid learning of memories
by single neurons.” 2017 https://arxiv.org/abs/1710.11227
[24] F. Ricci, L. Rokach, B. Shapira (Eds.), Recommender Systems Handbook, Springer, 2015.
[25] I. Bárány, F. Zoltán . “On the shape of the convex hull of random points.”
Probability theory and related fields, 77(2), (1988): 231-240.
[26] I. Bárány, F. Zoltán. “Approximation of the sphere by polytopes having
few vertices.” Proceedings of the American Mathematical Society,
102(3), (1988): 651-659.
[27] P. Kainen, V. Kůrková. “Quasiorthogonal dimension of Euclidian
spaces”. Appl. Math. Lett., 6, (1993): 7-10.
[28] A.N. Gorban, I.Y. Tyukin, D.V. Prokhorov, K.I. Sofeikov. “Approximation with random bases: Pro et contra.” Information Sciences, 364,
(2016): 129-145.
[29] V. Kůrková, M. Sanguineti. “Probabilistic lower bounds for approximation by shallow perceptron networks.” Neural Networks 91, (2017):
34-41.
[30] M. Talagrand, “Concentration of measure and isoperimetric inequalities
in product spaces.” Publications Mathematiques de l’IHES 81, 73–205,
1995 (doi:10.1007/BF02699376)
[31] O. Guédon, E. Milman. “Interpolating thin-shell and sharp largedeviation estimates for lsotropic log-concave measures.” Geometric and
Functional Analysis, 21(5), (2011): 1043-1068.
[32] L. Lovász, S. Vempala. “The geometry of logconcave functions and
sampling algorithms.” Random Structures & Algorithms 30(3), (2007):
307-358.
[33] S. Bobkov, M. Ledoux. “From Brunn-Minkowski to Brascamp-Lieb and
to logarithmic sobolev inequalities.” Geometric & Functional Analysis
10(5) (2000): 1028-1052.
[34] S. Bobkov, “Isoperimetric and analytic inequalities for log-concave
probability measures.” The Annals of Probability 27(4) (1999): 19031921.
[35] S. Brazitikos, Giannopoulos, A., Valettas, P., Vritsiou, B. “Geometry of
isotropic convex bodies.” Mathematical Surveys and Monographs, vol.
196. American Mathematical Soc., 2014.
[36] G. Paouris. “Small ball probability estimates for log-concave measures.”
Transactions of the American Mathematical Society 364(1), (2012): 287308.
[37] P. Stavrakakis and P. Valettas. “On the geometry of log-concave
probability measures with bounded log-Sobolev constant.” In: Ludwig
M., Milman V., Pestov V., Tomczak-Jaegermann N. (eds) Asymptotic
Geometric Analysis. Fields Institute Communications, vol 68, 2013.
359–380.
[38] Berwald, L. “Verallgemeinerung eines Mittelwertsatzes von J. Favard fűr
positive konkave Funktionen.” Acta Mathematica 79(1) (1947): 17–37.
[39] B. Klartag, E. Milman. “Inner regularization of log-concave measures
and small-ball estimates.” In: Klartag B., Mendelson S., Milman V.
(eds) Geometric Aspects of Functional Analysis. Lecture Notes in
Mathematics, vol 2050. Springer, Berlin, Heidelberg, 2012. 267–278.
[40] D. Wang, M. Li. “Stochastic configuration networks: Fundamentals and
algorithms.” IEEE Trans. On Cybernetics, 47(10) (2017): 3466–3479.
[41] S. Scardapane, D. Wang. “Randomness in neural networks: an overview.”
Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, (2017) 7(2).

