# Fast Construction of Correcting Ensembles for Legacy Artificial Intelligence
Systems: Algorithms and a Case Study

Ivan Yu. Tyukin111The work was supported by the Ministry of Education and
Science of Russia (Project No. 14.Y26.31.0022) and Innovate UK Knowledge
Transfer Partnership grants KTP009890 and KTP010522<EMAIL_ADDRESS>Alexander N. Gorban<EMAIL_ADDRESS>Stephen Green<EMAIL_ADDRESS>Danil
Prokhorov<EMAIL_ADDRESS>University of Leicester, Department of
Mathematics, University Road, Leicester, LE1 7RH, UK  Department of Automation
and Control Processes, St. Petersburg State University of Electrical
Engineering, Prof. Popova str. 5, Saint-Petersburg, 197376, Russian Federation
Lobachevsky State University of Nizhnij Novgorod, Prospekt Gagarina 23,
Nizhnij Novgorod,603022, Russian Federation  Toyota R $\&$ D, Ann-Arbor, MI,
USA

###### Abstract

This paper presents a new approach for constructing simple and computationally
efficient improvements of generic Artificial Intelligence (AI) systems,
including Multilayer and Deep Learning neural networks. The improvements are
small network ensembles added to the existing AI architectures. Theoretical
foundations of the approach are based on stochastic separation theorems and
the ideas of the concentration of measure. We show that, subject to mild
technical assumptions on statistical properties of internal signals in the
original AI system, the approach enables fast removal of the AI’s errors with
probability close to one on the datasets which may be exponentially large in
dimension. The approach is illustrated with numerical examples and a case
study of digits recognition in American Sign Language.

###### keywords:

Neural Ensembles , Stochastic Separation Theorems , Perceptron , Artificial
Intelligence , Measure Concentration

###### MSC:

[2010] 68T05 , 68T42 , 97R40 , 60F05

##  1 Introduction

Artificial Intelligence (AI) systems have risen dramatically from being the
subject of niche academic and practical interests to a commonly accepted and
widely-spread facet of modern life. Industrial giants such as Google, Amazon,
IBM, and Microsoft offer a broad range of AI-based services, including
intelligent image and sound processing and recognition.

Deep Learning and related computational technologies [8], [27] are currently
perceived as state-of-the art tools for producing various AI systems. In
visual recognition tasks, these systems deliver unprecedented accuracy [40] at
reasonable computational costs [29]. Despite these advances, several
fundamental challenges hinder further progress of these technologies.

All data-driven AI systems make mistakes, regardless of how well an AI system
is trained. Some examples of these have already received global public
attention [6], [15]. Mistakes may arise due to uncertainty in empirical data,
data misrepresentation, and imprecise or inaccurate training. Conventional
approaches to reducing spurious errors include altering training data and
improving design procedures [33], [35], [37], [49], transfer learning [10],
[36], [48] and privileged learning [44]. These approaches invoke extensive
training procedures. The training itself, whilst eradicating some errors, may
introduce new errors by the very nature of the steps involved (e.g. randomized
sampling of mini-batches, randomized training sets etc).

In this work, we propose a training approach and a technology whereby errors
of the original legacy AI are removed, with high probability, via
incorporation of small neuronal ensembles and their cascades into the original
AI’s decision-making. Ensembles methods and classifiers’ cascades (see e.g.
[16], [17], [38], [45] and references therein) constitute a well-known
framework for improving performance of classifiers. Here we demonstrate that
geometry of high-dimensional spaces, in agreement with “blessing of
dimensionality” [12], [21], [31] enables efficient construction of AI error
correctors and their ensembles with guaranteed performance bounds.

The technology bears similarity with neurogenesis deep learning [13],
classical cascade correlation [14], greedy approximation [5], and randomized
methods for training neural networks [41], including deep stochastic
configuration networks [46], [47]. The proposed technology, however, does not
require computationally expensive training or pre-conditioning, and in some
instances can be set up as a non-iterative procedure. In the latter case the
technology’s computational complexity scales at most linearly with the size of
the training set.

At the core of the technology is the concentration of measure phenomenon [18],
[19], [24], [25], [34], a view on the problem of learning in AI systems that
is stemming from conventional probabilistic settings [11], [43], and
stochastic separation theorems [20], [21], [22]. Main building blocks of the
technology are simple threshold, perceptron-type [39] classifiers. The
original AI system, however, needs not be a classifier itself. We show that,
subject to mild assumptions on statistical properties of signals in the
original AI system, small neuronal ensembles consisting of cascades of simple
linear classifiers are an efficient tool for learning away spurious and
systematic errors. These cascades can be used for learning new tasks too.

The paper is organized as follows: Section 2 contains a formal statement of
the problem, Section 3 presents main results: namely, the algorithms for
constructing correcting ensembles (Section 3.2) preceded by their mathematical
justification (Section 3.1). Section 4 presents a case study on American Sign
Language recognition illustrating the concept, and Section 5 concludes the
paper. Proofs of theorems and other statements as well as additional technical
results are provided in A and B.

## Notation

The following notational agreements are used throughout the paper:

  * 1.

$\mathbb{R}$ denotes the field of real numbers;

  * 2.

$\mathbb{N}$ is the set of natural numbers;

  * 3.

$\mathbb{R}^{n}$ stands for the $n$-dimensional real space; unless stated
otherwise symbol $n$ is reserved to denote dimension of the underlying linear
space;

  * 4.

let $\boldsymbol{x},\boldsymbol{y}$ be elements of $\mathbb{R}^{n}$, then
$\langle\boldsymbol{x},\boldsymbol{y}\rangle=\sum_{i=1}^{n}x_{i}y_{i}$ is
their inner product;

  * 5.

let $\boldsymbol{x}\in\mathbb{R}^{n}$, then $\|\boldsymbol{x}\|$ is the
Euclidean norm of $\boldsymbol{x}$:
$\|\boldsymbol{x}\|=\sqrt{\langle\boldsymbol{x},\boldsymbol{x}\rangle}$;

  * 6.

$B_{n}(R)$ denotes a $n$-ball of radius $R$ centered at $0$:
$B_{n}(R)=\\{\boldsymbol{x}\in\mathbb{R}^{n}|\ \|\boldsymbol{x}\|\leq R\\}$;

  * 7.

if $\mathcal{S}$ is a finite set then $|\mathcal{S}|$ stands for its
cardinality;

  * 8.

$\mathcal{V}(\Xi)$ is the Lebesgue volume of $\Xi\subset\mathbb{R}^{n}$;

  * 9.

if $X$ is a random variable then $E[X]$ is its expected value.

##  2 Problem Statement

In what follows we suppose that an AI system is an operator mapping elements
of its input set, $\mathcal{U}$, to the set of outputs, $\mathcal{Q}$.
Examples of inputs $\boldsymbol{u}\in\mathcal{U}$ are images, temporal or
spatiotemporal signals, and the outputs $\boldsymbol{q}\in\mathcal{Q}$
correspond to labels, classes, or some quantitative characteristics of the
inputs. Inputs $\boldsymbol{u}$, outputs $\boldsymbol{q}$, and internal
variables $\boldsymbol{z}\in\mathcal{Z}$ of the system represent the system’s
state. The state itself may not be available for observation but some of its
variables or relations may be accessed. In other words, we assume that there
is a process which assigns an element of $\boldsymbol{x}\in\mathbb{R}^{n}$ to
the triple $(\boldsymbol{u},\boldsymbol{z},\boldsymbol{q})$. A diagram
illustrating the setup for a generic AI system is shown in Fig. 1.

Figure 1: Functional diagram of correcting neuronal ensembles for a generic
Artificial Intelligence system.

In addition to the core AI system we consider an add-on ensemble mapping
samples $\boldsymbol{x}$ into auxiliary signals $\boldsymbol{s}\in\mathcal{S}$
(shown as improvement signals in Fig. 1) which are then used to improve
performance of the original core AI. An example of such an improvement signal
could be an indication that the current state of the core AI system
represented by $\boldsymbol{x}$ corresponds to an erroneous decision of the
core AI. At the integration stage, this information will alter the overall
response.

With regards to the operations $f_{i}$ performed at the individual nodes
(circles in the diagram on Fig. 1), we will focus on the following relevant
class

$f_{i}(\boldsymbol{x})=f\left(\langle\boldsymbol{w}_{i},\boldsymbol{x}\rangle-
c_{i}\right),$ (1)

where the function $f:\mathbb{R}\rightarrow\mathbb{R}$ is piece-wise
continuous, $\boldsymbol{w}_{i}\in\mathbb{R}^{n}$, and $c_{i}\in\mathbb{R}$.
This class of functions is broad enough to enable the ensemble to function as
a universal approximation device (e.g. by choosing the function $f$ in the
class satisfying conditions discussed in [5]) as well as to fit into a wide
range of common AI architectures including decision trees, multilayer neural
networks and perceptions, and deep learning convolutional neuronal networks.
Additional insight into “isolation” properties of elements (1) in comparison
with more natural choices such as e.g. ellipsoids or balls (cf. [1]) is
provided in B.

Over a relevant period of time, the AI system generates a finite but large set
of measurements $\boldsymbol{x}_{i}$. This set is assessed by an external
supervisor and is partitioned into the union of the sets $\mathcal{M}$ and
$\mathcal{Y}$:

$\mathcal{M}=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\},\
\mathcal{Y}=\\{\boldsymbol{x}_{M+1},\dots,\boldsymbol{x}_{M+k}\\}.$

The set $\mathcal{M}$ may contain measurements corresponding to expected
operation of the AI, whereas elements from $\mathcal{Y}$ constitute core AI’s
performance singularities. These singularities may be both desired (related
e.g. to “important” inputs $\boldsymbol{u}$) and undesired (related e.g. to
errors of the AI). The function of the ensemble is to respond to these
singularities selectively by producing improvement signals $\boldsymbol{s}$ in
response to elements from the set $\mathcal{Y}$.

A straightforward approach to derive such ensembles is to use standard
optimization facilities such as e.g. error back-propagation and its various
modifications, or use other iterative procedures similar to greedy
approximation [5], stochastic configuration networks [47] (cf. [13]). This
approach, however, requires computational resources and time that may not
necessarily be available. Even in the simplest case of a single-element add-on
system that is to separate the entire set $\mathcal{X}$ from $\mathcal{Y}$,
determining the best possible solution, in the form of e.g. support vector
machines [43], is non-trivial computationally. Indeed, theoretical worst-case
estimates of computational complexity for determining parameters of the
single-element system are of the order $O((M+k)^{3})$ [9].

The question, therefore is: if there exists a computationally efficient
procedure for determining ensembles or add-on networks such that

  * 1)

they are able to “improve” performance of a generic AI system with guaranteed
probability, and

  * 2)

they consist of elements (1)?

Preferably, computational complexity of the procedure is to be linear or even
sub-linear in $M+k$.

In the next sections we show that, subject to some mild technical assumptions
on the way the sets $\mathcal{M}$ and $\mathcal{Y}$ are generated, a family of
simple algorithms with the required characteristics can indeed be derived.
These algorithms are motivated by Stochastic Separation Theorems [20], [21],
[22]. For consistency, adapted version of these theorems are presented and
discussed in Section 3.1. The algorithms themselves are presented and
discussed in Section 3.2.

##  3 Main Results

###  3.1 Mathematical Preliminaries

Following standard assumptions (see e.g. [11], [43]), we suppose that all
$\boldsymbol{x}$ are generated in accordance with some distribution, and the
actual measurements $\boldsymbol{x}_{i}$ are samples from this distribution.
For simplicity, we adopt a traditional setting in which all such samples be
identically and independently distributed (i.i.d.) [11]. With regards to the
elements of $\boldsymbol{x}_{i}$, the following technical condition is
assumed:

###### Assumption 1

Elements $\boldsymbol{x}_{i}$ are random i.i.d. vectors drawn from a product
measure distribution:

  * A1)

their $x_{ij}$-th components are independent and bounded random variables
$X_{j}$: $-1\leq X_{j}\leq 1$, $j=1,\dots,n$,

  * A2)

$E[X_{j}]=0$, and $E[X_{j}^{2}]=\sigma_{j}^{2}$.

The distribution itself, however, is supposed to be unknown. Let

$R_{0}^{2}=\sum_{i=1}^{n}\sigma_{i}^{2}>0.$

Then the following result holds (cf. [20]).

###### Theorem 1

Let $\boldsymbol{x}_{i}\in\mathcal{M}\cup\mathcal{Y}$ be i.i.d. random points
from the product distribution satisfying Assumption 1, $0<\delta<1$,
$0<\varepsilon<1$ and $R_{0}>0$. Then

  * 1)

for any $i$,

$\begin{split}&P\left(1-\varepsilon\leq\frac{\|\boldsymbol{x}_{i}\|^{2}}{R^{2}_{0}}\leq
1+\varepsilon\right)\geq
1-2\exp\left(-\frac{2R_{0}^{4}\varepsilon^{2}}{n}\right);\\\
&P\left(\frac{\|\boldsymbol{x}_{i}\|^{2}}{R^{2}_{0}}\geq
1-\varepsilon\right)\geq
1-\exp\left(-\frac{2R_{0}^{4}\varepsilon^{2}}{n}\right);\end{split}$ (2)

  * 2)

for any $i,j,\ i\neq j$,

$\begin{split}&P\left(\left\langle\frac{\boldsymbol{x}_{i}}{R_{0}},\frac{\boldsymbol{x}_{j}}{R_{0}}\right\rangle<\delta\right)\geq
1-\exp\left(-\frac{R_{0}^{4}\delta^{2}}{2n}\right);\\\
&P\left(\left\langle\frac{\boldsymbol{x}_{i}}{R_{0}},\frac{\boldsymbol{x}_{j}}{R_{0}}\right\rangle>-\delta\right)\geq
1-\exp\left(-\frac{R_{0}^{4}\delta^{2}}{2n}\right);\end{split}$ (3)

  * 3)

for any given $\boldsymbol{y}\in[-1,1]^{n}$ and any $i$

$\begin{split}&P\left(\left\langle\frac{\boldsymbol{x}_{i}}{R_{0}},\frac{\boldsymbol{y}}{R_{0}}\right\rangle<\delta\right)\geq
1-\exp\left(-\frac{R_{0}^{4}\delta^{2}}{2n}\right).\end{split}$ (4)

Proof of Theorem 1 as well as those of other technical statements are provided
in A.

###### Remark 1

Notice that if $\sigma_{i}^{2}>0$ then
$R_{0}^{2}>n\min_{i}\\{\sigma_{i}^{2}\\}$. Hence the r.h.s. of (2)–(4) become
exponentially close to $1$ for $n$ large enough.

The following Theorem is now immediate.

######  Theorem 2 ($1$-Element separation)

Let elements of the set $\mathcal{M}\cup\mathcal{Y}$ be i.i.d. random points
from the product distribution satisfying Assumption 1, $0<\varepsilon<1$, and
$R_{0}>0$. Consider $\boldsymbol{x}_{M+1}\in\mathcal{Y}$ and let

$\ell_{1}(\boldsymbol{x})=\left\langle\frac{\boldsymbol{x}}{R_{0}},\frac{\boldsymbol{x}_{M+1}}{R_{0}}\right\rangle,\
h_{1}(\boldsymbol{x})=\ell_{1}(\boldsymbol{x})-1+\varepsilon.$ (5)

Then

$\begin{split}&P\left(h_{1}(\boldsymbol{x}_{M+1})\geq 0\ \mbox{and}\
h_{1}(\boldsymbol{x}_{i})<0\ \mbox{for all}\
\boldsymbol{x}_{i}\in\mathcal{M}\right)\\\ &\geq
1-\exp\left(-\frac{2R_{0}^{4}\varepsilon^{2}}{n}\right)-M\exp\left(-\frac{R_{0}^{4}(1-\varepsilon)^{2}}{2n}\right).\end{split}$
(6)

(The proof is provided in A.)

###### Remark 2

Theorem 2 not only establishes the fact that the set $\mathcal{M}$ can be
separated away from $\mathcal{Y}$ by a linear functional with reasonably high
probability. It also specifies the separating hyperplane, (5), and provides an
estimate from below of the probability of such an event, (6). The estimate, as
a function of $n$, approaches $1$ exponentially fast. Note that the result is
intrinsically related to the work [32] on quasiorthogonal dimension of
Euclidian spaces.

Let us now move to the case when the set $\mathcal{Y}$ contains more than one
element. Theorem 3 below summarizes the result.

######  Theorem 3 ($k$-Element separation. Case 1)

Let elements of the set $\mathcal{M}\cup\mathcal{Y}$ be i.i.d. random points
from the product distribution satisfying Assumption 1, and $R_{0}>0$. Let,
additionally,

$\left\langle\frac{\boldsymbol{x}_{i}}{R_{0}},\frac{\boldsymbol{x}_{j}}{R_{0}}\right\rangle\geq\beta$
(7)

for all $\boldsymbol{x}_{i},\boldsymbol{x}_{j}\in\mathcal{Y}$,
$\boldsymbol{x}_{i}\neq\boldsymbol{x}_{j}$. Pick

$0<\varepsilon<1,\ 1-\varepsilon+\beta(k-1)>0,$

and consider

$\begin{split}\ell_{k}(\boldsymbol{x})=&\left\langle\frac{\boldsymbol{x}}{R_{0}},\frac{\overline{\boldsymbol{x}}}{R_{0}}\right\rangle,\
\overline{\boldsymbol{x}}=\frac{1}{k}\sum_{i=1}^{k}\boldsymbol{x}_{M+i},\\\
h_{k}(\boldsymbol{x})=&\ell_{k}(\boldsymbol{x})-\frac{1-\varepsilon+\beta(k-1)}{k}.\end{split}$
(8)

Then

$\begin{split}&P\left(h_{k}(\boldsymbol{x}_{j})\geq 0\ \&\
h_{k}(\boldsymbol{x}_{i})<0\ \mbox{for all}\
\boldsymbol{x}_{i}\in\mathcal{M},\ \boldsymbol{x}_{j}\in\mathcal{Y}\right)\\\
&\geq
1-k\exp\left(-\frac{2R_{0}^{4}\varepsilon^{2}}{n}\right)-M\exp\left(-\frac{R_{0}^{4}(1-\varepsilon+\beta(k-1))^{2}}{2k^{2}n}\right).\end{split}$
(9)

(The proof is provided in A.)

The value of $\beta$ in estimate (7) may not necessarily be available
a-priori. If this is the case then the following corollaries from Theorems 2
and 3 may be invoked.

######  Corollary 1 ($k$-Element separation. Case 1)

Let elements of the set $\mathcal{M}\cup\mathcal{Y}$ be i.i.d. random points
from the product distribution satisfying Assumption 1, and $R_{0}>0$. Pick

$0<\delta,\ 0<\varepsilon<1,\ 1-\varepsilon-\delta(k-1)>0,$

and let

$\begin{split}\ell_{k}(\boldsymbol{x})=&\left\langle\frac{\boldsymbol{x}}{R_{0}},\frac{\overline{\boldsymbol{x}}}{R_{0}}\right\rangle,\
\overline{\boldsymbol{x}}=\frac{1}{k}\sum_{i=1}^{k}\boldsymbol{x}_{M+i},\\\
h_{k}(\boldsymbol{x})=&\ell_{k}(\boldsymbol{x})-\frac{1-\varepsilon-\delta(k-1)}{k}.\end{split}$
(10)

Then

$\begin{split}&P\left(h_{k}(\boldsymbol{x}_{j})\geq 0\ \&\
h_{k}(\boldsymbol{x}_{i})<0\ \mbox{for all}\
\boldsymbol{x}_{i}\in\mathcal{M},\ \boldsymbol{x}_{j}\in\mathcal{Y}\right)\\\
&\geq
1-k\exp\left(-\frac{2R_{0}^{4}\varepsilon^{2}}{n}\right)-\frac{k(k-1)}{2}\exp\left(-\frac{R_{0}^{4}\delta^{2}}{2n}\right)\\\
&-M\exp\left(-\frac{R_{0}^{4}(1-\varepsilon-\delta(k-1))^{2}}{2k^{2}n}\right).\end{split}$
(11)

######  Corollary 2 ($k$-Element separation. Case 2)

Let elements of the set $\mathcal{M}\cup\mathcal{Y}$ be i.i.d. random points
from the product distribution satisfying Assumption 1, $0<\varepsilon<1$,
$0<\mu<1-\varepsilon$ and $R_{0}>0$. Pick $\boldsymbol{x}_{j}\in\mathcal{Y}$
and consider

$\begin{split}\ell_{k}(\boldsymbol{x})=&\left\langle\frac{\boldsymbol{x}}{R_{0}},\frac{\boldsymbol{x}_{j}}{R_{0}}\right\rangle,\
h_{k}(\boldsymbol{x})=\ell_{k}(\boldsymbol{x})-1+\varepsilon+\mu,\\\
\Omega=&\left\\{\boldsymbol{x}\in\mathbb{R}^{n}\
\left|\left\langle\frac{\boldsymbol{x}_{j}}{R_{0}},\frac{\boldsymbol{x}_{j}-\boldsymbol{x}}{R_{0}}\right\rangle\leq\mu\right.\right\\}\end{split}$
(12)

Then

$\begin{split}&P\left(h_{k}(\boldsymbol{x})\geq 0\ \mbox{and}\
h_{k}(\boldsymbol{x}_{i})<0\ \mbox{for all}\
\boldsymbol{x}_{i}\in\mathcal{M},\boldsymbol{x}\in\Omega\right)\\\ &\geq
1-k\exp\left(-\frac{2R_{0}^{4}\varepsilon^{2}}{n}\right)-M\exp\left(-\frac{R_{0}^{4}(1-\varepsilon-\mu)^{2}}{2n}\right).\end{split}$
(13)

Proofs of the corollaries are provided in A.

Theorems 1 – 3 and Corollaries 1, 2 suggest that simple elements (1) with $f$
being mere threshold elements

$f(s)=\mathrm{Step}(s)=\left\\{\begin{array}[]{l}1,\ s\geq 0\\\ 0,\
s<0\end{array}\right.,$

posses remarkable selectivity. For example, according to Theorem 2, the
element

$f\left(\left\langle\boldsymbol{x},\boldsymbol{w}\right\rangle-c\right),\
\boldsymbol{w}=\frac{\boldsymbol{x}_{M+1}}{R_{0}^{2}},\
c=\frac{\|\boldsymbol{x}_{M+1}\|^{2}}{R_{0}^{2}}$

assigns “$1$” to $\boldsymbol{x}_{M+1}$ and “$0$” to all
$\boldsymbol{x}_{i}\in\mathcal{M}$ with probability that is exponentially (in
$n$) close to $1$. To illustrate this point, consider a simple test case with
a set comprising of $10^{4}$ i.i.d. samples from the (uniform) product
distribution in $[-1,1]^{n}$. For this distribution, $R_{0}=\sqrt{n/3}$,
$|\mathcal{M}|=M=9999$, and estimate (6) becomes:

$\begin{split}&P\left(h_{1}(\boldsymbol{x}_{M+1})\geq 0\ \mbox{and}\
h_{1}(\boldsymbol{x}_{i})<0\ \mbox{for all}\
\boldsymbol{x}_{i}\in\mathcal{M}\right)\\\ &\geq
1-\exp\left(-\frac{2}{9}n\varepsilon^{2}\right)-M\exp\left(-\frac{1}{18}n(1-\varepsilon)^{2}\right).\end{split}$
(14)

The right-hand side rapidly approaches $1$ as $n$ grows. The estimate,
however, could be rather conservative as is illustrated with Fig. 2.

Figure 2: The probability (frequency) that an element of the set $\mathcal{M}$
(formed by random i.i.d. vectors drawn from the n-cube $[-1,1]^{n}$) is
separable from the rest by hyperplanes (5) (and their variants) as a function
of $n$; $M=|\mathcal{M}|=10^{4}$. Red stars correspond to empirical
frequencies of the events $A_{i}$:
$\langle\boldsymbol{x}_{i},\boldsymbol{x}_{j}\rangle<\|\boldsymbol{x}_{i}\|^{2}$
for all $\boldsymbol{x}_{j}\in\mathcal{M}$,
$\boldsymbol{x}_{i}\neq\boldsymbol{x}_{j}$. Blue circles show frequencies of
the events $B_{i}$: $\|\boldsymbol{x}_{i}\|^{2}/R_{0}^{2}\geq 1-\varepsilon$
and
$\langle\boldsymbol{x}_{i}/R_{0},\boldsymbol{x}_{j}/R_{0}\rangle<1-\varepsilon$
for all $\boldsymbol{x}_{j}\in\mathcal{M}$,
$\boldsymbol{x}_{i}\neq\boldsymbol{x}_{j}$, $\varepsilon=0.2$. Black squares
show the right-hand side of (14) for the same value of $\varepsilon=0.2$.

A somewhat more relaxed approach could be to allow a small margin of error by
determining a hyperplane separating the set $\mathcal{Y}$ from “nearly all”
elements $\boldsymbol{x}\in\mathcal{M}$. An estimate of success for the latter
case follows from Lemma 1 below

###### Lemma 1

Let elements of the set $\mathcal{M}$ be i.i.d. random points, and let

$\begin{split}\ell(\boldsymbol{x})=&\left\langle\boldsymbol{x},\boldsymbol{w}\right\rangle,\
h(\boldsymbol{x})=\ell(\boldsymbol{x})-c\end{split}$

and $0\leq p_{\ast}\leq 1$ be such that

$P\left(h(\boldsymbol{x}_{i})\geq 0\right)\leq p_{\ast}$

for an arbitrary element $\boldsymbol{x}_{i}\in\mathcal{M}$. Then

$\begin{split}&P\left(h(\boldsymbol{x})\geq 0\ \mbox{for at most}\ m\
\mbox{elements}\ \boldsymbol{x}\in\mathcal{M}\right)\geq\\\ &\ \ \ \
(1-p_{\ast})^{M}\exp\left(\frac{(M-m+1)p_{\ast}}{1-p_{\ast}}\right)\left(1-\frac{1}{m!}\left(\frac{(M-m+1)p_{\ast}}{(1-p_{\ast})}\right)^{m}\right).\end{split}$

(The proof is provided in A.)

According to Lemma 1 and Theorem 1,

$\begin{split}&P\left(h_{1}(\boldsymbol{x}_{M+1})\geq 0\ \mbox{and}\
h_{1}(\boldsymbol{x}_{i})\geq 0\ \mbox{for at most}\ n\
\boldsymbol{x}_{i}\in\mathcal{M}\right)\\\
&\geq(1-p_{\ast})^{M}\exp\left(\frac{(M-n+1)p_{\ast}}{1-p_{\ast}}\right)\left(1-\frac{1}{n!}\left(\frac{(M-n+1)p_{\ast}}{(1-p_{\ast})}\right)^{n}\right)\\\
&-\exp\left(-\frac{2R_{0}^{4}\varepsilon^{2}}{n}\right),\
p_{\ast}=\exp\left(-\frac{R_{0}^{4}(1-\varepsilon)^{2}}{2n}\right).\end{split}$
(15)

Observe, however, that $n+1$ random points (in general position) are linearly
separable with probability $1$. Thus, with probability $1$, spurious $n$
points can be separated away from $\boldsymbol{x}_{M+1}$ by a second
hyperplane. Fig. 3 compares separation probability estimate for such a pair
with that of for $h_{1}$ (Theorem 2, (6)).

Figure 3: Probability estimates (14) (black squares) and (15) (magenta
triangles) as functions of $n$ for the set $\mathcal{M}$ formed by random
i.i.d. vectors drawn from the n-cube $[-1,1]^{n}$ and $\varepsilon=0.2$.

###  3.2 Fast AI up-training algorithms

Theorem 3 as well as Corollaries 1, 2 and Lemma 1 motivate a simple
computational framework for construction of networks and cascades of elements
(1). Following the setup presented in Section 2, recall that the data is
sampled from the core AI system and is partitioned into the sets $\mathcal{M}$
and $\mathcal{Y}$. The latter set $\mathcal{Y}$ corresponds to singular events
which are to be picked by the cascade. Their union,
$\mathcal{S}=\mathcal{M}\cup\mathcal{Y}$, is the entire data that is available
for the cascade construction.

We are now ready to proceed with the algorithms for fast construction of the
correcting ensembles. The first algorithm is a recursion of which each
iteration is a multi-step process. The algorithm is provided below.

######  Algorithm 1 (Correcting Ensembles)

Initialization: set $\mathcal{M}^{1}$ $=$ $\mathcal{M}$,
$\mathcal{Y}^{1}=\mathcal{Y}$, and $\mathcal{S}^{1}=\mathcal{S}$, define a
list or a model of correcting actions – formalized alternations of the core AI
in response to an error/error type.

  1. Input to the $i$-th iteration: Sets $\mathcal{M}^{i}$, $\mathcal{Y}^{i}$, and $\mathcal{S}^{i}=\mathcal{M}^{i}\cup\mathcal{Y}^{i}$; the number of clusters, $p$, and the value of filtering threshold, $\theta$.

  2. 1.

Centering. All current data available is centered. The centered sets are
denoted as $\mathcal{S}_{c}^{i}$ and $\mathcal{Y}_{c}^{i}$ and are formed by
subtracting the mean $\overline{\boldsymbol{x}}(\mathcal{S}^{i})$ from the
elements of $\mathcal{S}^{i}$ and $\mathcal{Y}^{i}$, respectively:

$\mathcal{S}_{c}^{i}=\\{\boldsymbol{x}\in\mathbb{R}^{n}|\boldsymbol{x}=\xi-\overline{\boldsymbol{x}}(\mathcal{S}^{i})\text{,
}\xi\in\mathcal{S}^{i}\\}$
$\mathcal{Y}_{c}^{i}=\\{\boldsymbol{x}\in\mathbb{R}^{n}|\boldsymbol{x}=\xi-\overline{\boldsymbol{x}}(\mathcal{S}^{i})\text{,
}\xi\in\mathcal{Y}^{i}\\}.$

  3. 2.

Regularization. The covariance matrix, $\mathrm{Cov}(\mathcal{S}^{i})$, of
$\mathcal{S}^{i}$ is calculated along with the corresponding eigenvalues and
eigenvectors. New regularized sets $\mathcal{S}_{r}$, $\mathcal{Y}_{r}$ are
produced as follows. All eigenvectors $h_{1},h_{2},\dots,h_{m}$ that
correspond to the eigenvalues $\lambda_{1},\lambda_{2},\dots,\lambda_{m}$
which are above a given threshold are combined into a single matrix
$H=(h_{1}|h_{2}|\cdots|h_{m})$. The threshold could be chosen on the basis of
the Kaiser-Guttman test [30] or otherwise (e.g. by keeping the ratio of the
maximal to the minimal in the set of retained eigenvalues within a given
bound). The new sets are defined as:

$\mathcal{S}_{r}^{i}=\\{\boldsymbol{x}\in\mathbb{R}^{m}|\boldsymbol{x}=H^{T}\xi\text{,
}\xi\in\mathcal{S}_{c}^{i}\\}$
$\mathcal{Y}_{r}^{i}=\\{\boldsymbol{x}\in\mathbb{R}^{m}|\boldsymbol{x}=H^{T}\xi\text{,
}\xi\in\mathcal{Y}_{c}^{i}\\}.$

  4. 3.

Whitening. The two sets then undergo a whitening coordinate transformation
ensuring that the covariance matrix of the transformed data is the identity
matrix:

$\mathcal{S}_{w}^{i}=\\{\boldsymbol{x}\in\mathbb{R}^{m}|\boldsymbol{x}=W\xi\text{,
}\xi\in\mathcal{S}_{r}^{i},\
W=\mathrm{Cov}(\mathcal{S}_{r}^{i})^{-\frac{1}{2}}\\}$
$\mathcal{Y}_{w}^{i}=\\{\boldsymbol{x}\in\mathbb{R}^{m}|\boldsymbol{x}=W\xi\text{,
}\xi\in\mathcal{Y}_{r}^{i},\
W=\mathrm{Cov}(\mathcal{S}_{r}^{i})^{-\frac{1}{2}}\\}.$

  5. 4.

Projection (optional). Project elements of $\mathcal{S}_{w}^{i}$,
$\mathcal{Y}_{w}^{i}$ onto the unit sphere by scaling them to the unit length:
$\boldsymbol{x}\mapsto\varphi(\boldsymbol{x}),\
\varphi(\boldsymbol{x})=\boldsymbol{x}/\|\boldsymbol{x}\|$.

  6. 5.

Training: Clustering. The set $\mathcal{Y}_{w}^{i}$ (the set of errors) is
then partitioned into $p$ clusters
$\mathcal{Y}_{w,1}^{i},\dots,\mathcal{Y}_{w,p}^{i}$ that’s elements are
pairwise positively correlated.

  7. 6.

Training: Nodes creation and aggregation. For each $\mathcal{Y}_{w,j}^{i}$,
$j=1,\dots,p$ and its complement
$\mathcal{S}_{w}^{i}\setminus\mathcal{Y}_{w\text{, }j}^{i}$ we construct the
following separating hyperplanes:

$\begin{split}h_{j}(\boldsymbol{x})=&\ell_{j}(\boldsymbol{x})-c_{j},\\\
\ell_{j}(\boldsymbol{x})=&\left\langle\frac{\boldsymbol{w}_{j}}{\|\boldsymbol{w}_{j}\|}\text{,
}\boldsymbol{x}\right\rangle,\ c_{j}=\min_{\xi\in\mathcal{Y}_{w\text{,
}j}^{i}}\left\langle\frac{\boldsymbol{w}_{j}}{\|\boldsymbol{w}_{j}\|}\text{,
}\xi\right\rangle\\\
\boldsymbol{w}_{j}=&(\mathrm{Cov}(\mathcal{S}_{w}^{i}\setminus\mathcal{Y}_{w\text{,}j}^{i})+\mathrm{Cov}(\mathcal{Y}_{w\text{,}j}^{i}))^{-1}(\overline{\boldsymbol{x}}(\mathcal{Y}_{w\text{,}j}^{i})-\overline{\boldsymbol{x}}(\mathcal{S}_{w}^{i}\setminus\mathcal{Y}_{w\text{,}j}^{i})).\end{split}$

Retain only those hyperplanes for which $c_{j}>\theta$. For each retained
hyperplane, create a corresponding element (1)

$f_{j}(\boldsymbol{x})=f\left(\left\langle
WH^{T}(\boldsymbol{x}-\overline{\boldsymbol{x}}(\mathcal{S}^{i})),\frac{\boldsymbol{w}_{j}}{\|\boldsymbol{w}_{j}\|}\right\rangle-
c_{j}\right),$ (16)

with $f$ being a function that satisfies: $f(s)>0$ for all $s\geq 0$ and
$f(s)\leq 0$ for all $s<0$, and add it to the ensemble. If optional step 4 was
used then the functional definition of $f_{j}$ becomes:

$f_{j}(\boldsymbol{x})=f\left(\left\langle\varphi\left(WH^{T}(\boldsymbol{x}-\overline{\boldsymbol{x}}(\mathcal{S}^{i}))\right),\frac{\boldsymbol{w}_{j}}{\|\boldsymbol{w}_{j}\|}\right\rangle-
c_{j}\right),$ (17)

where $\varphi$ is the mapping implementing projection onto the unit sphere.

  8. 7.

Integration/Deployment. Any $\boldsymbol{x}$ that is generated by the original
core AI is put through the ensemble of $f_{j}(\cdot)$. If for some
$\boldsymbol{x}$ any of the values of $f_{j}(\boldsymbol{x})>0$ then a
correcting action is performed on the core AI. The action is dependent on the
purpose of correction as well as on the problem at hand. It could include
label swapping, signalling an alarm, ignoring/not reporting etc. The combined
system becomes new core AI.

  9. 8.

Testing. Assess performance of new core AI on a relevant data set. If needed,
generate new sets $\mathcal{M}^{i+1}$, $\mathcal{Y}^{i+1}$,
$\mathcal{S}^{i+1}$ (with possibly different error types and definitions), and
repeat the procedure.

Steps 1–3 of the algorithm are standard pre-processing routines. In the
context of Theorems 1–3, step 1 aims to ensure that the first part of A2) in
Assumption 1 holds, and step 2, in addition to regularization, results in that
all components of $\boldsymbol{x}_{i}$ are uncorrelated (a necessary condition
for part A1) of Assumption 1 to hold). Whitening transformation, step 3,
normalizes the data in the sense that $\sigma_{i}^{2}=1$ for all $i$ relevant.
Step 4 (optional) is introduced to account for data irregularities and
clustering that may negatively affect data separability. An illustration of
potential utility of this step is shown in Fig. 4.

Figure 4: Linear separability via projection onto a sphere. Sets $A$ (shown as
a shaded gray domain) and $B$ (depicted as a blue filled hexagon) are not
linearly separable in the original coordinates. Their projections onto the
sphere, however, are separable (the separating hyperplane is shown in red).

Note that individual components of the data vectors may no longer satisfy the
independence assumption. Nevertheless, if the data is reasonably distributed,
different versions of separation theorems may apply to this case too [21],
[22]. In Section 4 we illustrate the effect of this step in an example
application.

Step 5, clustering, is motivated by Theorem 3 and Corollaries 1, 2 suggesting
that the rate of success in isolating multiple points from the background set
$\mathcal{M}$ increases when these multiple points are positively correlated
or are spatially close to each other.

Step 6 is a version of (8), albeit with a different normalization and a slight
perturbation of weights. The choice of this particular normalization is
motivated by the experiments shown in Fig. 2. As for the choice of weights,
these hyperplanes are standard Fisher discriminants. Yet, they are not far
from (8). In view of the previous steps,
$\mathrm{Cov}(\mathcal{S}_{w}^{i}\setminus\mathcal{Y}_{w\text{,}j}^{i})+\mathrm{Cov}(\mathcal{Y}_{w\text{,}j}^{i})$
is diagonally dominated and close to the identity matrix. When
$|\mathcal{S}_{w}^{i}|\gg|\mathcal{Y}_{w\text{,}j}^{i}|$, term
$\overline{\boldsymbol{x}}(\mathcal{S}_{w}^{i}\setminus\mathcal{Y}_{w\text{,}j}^{i})$
is nearly zero, and hence $\boldsymbol{w}_{j}$ is approximately at the
centroid of the cluster. Filtering of the nodes is necessitated by the
concentration of measure effects as exemplified by Theorem 1.

Functions $f$ in step 7 can be implemented using a range of ReLU, threshold,
$\tanh(\cdot)$, sigmoidal functions etc.; these are available in the majority
of standard core AI systems.

Computational complexity of each step in the recursion, except for step 5, is
at most $M+k$. Complexity of the clustering step may generally be
superpolynomial (worst case) as is e.g. the case for standard k-means
clustering [2]. If, however, sub-optimal solutions are accepted [26] then the
complexity of this step scales linearly with $M+k$. Further speed-ups are
possible through randomized procedures such as e.g. in k-means++ [3].

Algorithm 1 is based primarily on the intuition and rationale stemming from
Theorem 2, 3 and their corollaries. It can be modified to take advantage of
the possibility offered by Lemma 1 and the subsequent discussion. The
modification is that each node added in step 6 is assessed and “corrected” by
an additional hyperplane if required. The modified algorithm is summarized as
Algorithm 2 below.

######  Algorithm 2 (With cascaded pairs)

Initialization: set $\mathcal{M}^{1}=\mathcal{M}$,
$\mathcal{Y}^{1}=\mathcal{Y}$, and $\mathcal{S}^{1}=\mathcal{S}$, define a
list or a model of correcting actions – formalized alternations of the core AI
in response in response to an error/error type.

  1. Input to the $i$-th iteration: Sets $\mathcal{M}^{i}$, $\mathcal{Y}^{i}$, and $\mathcal{S}^{i}=\mathcal{M}^{i}\cup\mathcal{Y}^{i}$; the number of clusters, $p$, and the value of filtering threshold, $\theta$.

  2. 1-5.

As in Algorithm 1.

  3. 6.

Training: Nodes creation and aggregation. For each $\mathcal{Y}_{w,j}^{i}$,
$j=1,\dots,p$ and its complement
$\mathcal{S}_{w}^{i}\setminus\mathcal{Y}_{w\text{, }j}^{i}$ construct the
following separating hyperplanes:

$\begin{split}h_{j}(\boldsymbol{x})=&\ell_{j}(\boldsymbol{x})-c_{j},\\\
\ell_{j}(\boldsymbol{x})=&\left\langle\frac{\boldsymbol{w}_{j}}{\|\boldsymbol{w}_{j}\|}\text{,
}\boldsymbol{x}\right\rangle,\ c_{j}=\min_{\xi\in\mathcal{Y}_{w\text{,
}j}^{i}}\left\langle\frac{\boldsymbol{w}_{j}}{\|\boldsymbol{w}_{j}\|}\text{,
}\xi\right\rangle\\\
\boldsymbol{w}_{j}=&(\mathrm{Cov}(\mathcal{S}_{w}^{i}\setminus\mathcal{Y}_{w\text{,}j}^{i})+\mathrm{Cov}(\mathcal{Y}_{w\text{,}j}^{i}))^{-1}(\overline{\boldsymbol{x}}(\mathcal{Y}_{w\text{,}j}^{i})-\overline{\boldsymbol{x}}(\mathcal{S}_{w}^{i}\setminus\mathcal{Y}_{w\text{,}j}^{i})).\end{split}$

Retain only those hyperplanes for which $c_{j}>\theta$. For each retained
hyperplane, create a corresponding element $f_{j}(\cdot)$ in accordance to
(16) or, if step 4 was used, then (17). For each retained hyperplane,

     * (a)

determine the complementary set $\mathcal{C}_{j}$ comprised of elements
$\boldsymbol{x}\in\mathcal{S}_{w}^{i}\setminus\mathcal{Y}_{w}^{i}$ for which
$h_{j}(\boldsymbol{x})\geq 0$ (the set of points that are accidentally picked
up by the $f_{j}$ “by mistake”)

     * (b)

project elements of the set $\mathcal{C}_{j}\cup\mathcal{Y}_{w\text{,}j}^{i}$
orthogonally onto the hyperplane
$h_{j}(\boldsymbol{x})=\ell_{j}(\boldsymbol{x})-c_{j}$ as

$\boldsymbol{x}\mapsto\left(I-\frac{1}{\|\boldsymbol{w}_{j}\|^{2}}\boldsymbol{w}_{j}\boldsymbol{w}_{j}^{T}\right)\boldsymbol{x}+c_{j}\frac{\boldsymbol{w}_{j}}{\|\boldsymbol{w}_{j}\|}=P(\boldsymbol{w}_{j})\boldsymbol{x}+b(\boldsymbol{w}_{j},c_{j});$

     * (c)

determine a hyperplane

$h_{j,2}(\boldsymbol{x})=\ell_{j,2}(\boldsymbol{x})-c_{j,2},\
\ell_{j,2}(\boldsymbol{x})=\langle\boldsymbol{w}_{j,2},\boldsymbol{x}\rangle;$

separating projections of $\mathcal{C}_{j}$ from that of
$\mathcal{Y}_{w\text{,}j}^{i}$ so that $h_{j,2}(\boldsymbol{x})<0$ for all
projections from $\mathcal{C}_{j}$ and $h_{j,2}(\boldsymbol{x})\geq 0$ for all
projections from $\mathcal{Y}_{w\text{,}j}^{i}$. If no such planes exist, use
linear Fisher discriminant or any other relevant computational procedure

     * (d)

create a node

$f^{\perp}_{j}(\boldsymbol{x})=f\left(\left\langle
P(\boldsymbol{w}_{j})WH^{T}(\boldsymbol{x}-\overline{\boldsymbol{x}}(\mathcal{S}^{i}))+b(\boldsymbol{w}_{j},c_{j}),\boldsymbol{w}_{j,2}\right\rangle-
c_{j,2}\right)$

or, in case step 4 was used

$f^{\perp}_{j}(\boldsymbol{x})=f\left(\left\langle
P(\boldsymbol{w}_{j})\varphi(WH^{T}(\boldsymbol{x}-\overline{\boldsymbol{x}}(\mathcal{S}^{i})))+b(\boldsymbol{w}_{j},c_{j}),\boldsymbol{w}_{j,2}\right\rangle-
c_{j,2}\right);$

     * (e)

create the pair’s response node, $f_{j}^{\mathrm{c}}$, so that a non-negative
response is generated only when both nodes produce a non-negative response

$\begin{split}f_{j}^{\mathrm{c}}(\boldsymbol{x})=&f\big{(}\mathrm{Step}(f_{j}(\boldsymbol{x}))+\mathrm{Step}(f^{\perp}_{j}(\boldsymbol{x}))-2\big{)};\end{split}$

     * (f)

add the combined $f_{j}^{\mathrm{c}}(\cdot)$ to the ensemble.

  4. 7\.

Integration/Deployment. Any $\boldsymbol{x}$ that is generated by the original
core AI is put through the ensemble of $f_{j}^{\mathrm{c}}(\cdot)$. If for
some $\boldsymbol{x}$ any of the values of
$f_{j}^{\mathrm{c}}(\boldsymbol{x})>0$ then a correcting action is performed
on the core AI. The action is dependent on the purpose of correction as well
as on the problem at hand. It could include label swapping, signalling an
alarm, ignoring/not reporting etc. The combined system becomes new core AI.

  5. 8\.

Testing. Assess performance of new core AI on a relevant data set. If needed,
generate new sets $\mathcal{M}^{i+1}$, $\mathcal{Y}^{i+1}$,
$\mathcal{S}^{i+1}$ (with possibly different error types and definitions), and
repeat the procedure.

In the next section we illustrate how the proposed algorithms work in a case
study example involving a core AI in the form of a reasonably large
convolutional network trained on a moderate-size dataset.

##  4 Distinguishing the Ten Digits in American Sign Language: a Case Study

###  4.1 Setup and Datasets

In this case study we investigated and tested the approach on a challenging
problem of gestures recognition in the framework of distinguishing ten digits
in American Sign Language. To apply the approach a core AI had to be generated
first. As our core AI we picked a version of Inception deep neural network
model [42] whose architecture is shown in Fig. 5. The model was
trained222https://www.tensorflow.org/tutorials/image_retraining on ten sets of
images that correspond to the American Sign Language pictures for 0-9 (see
Fig. 6).

Figure 5: Architecture of the adopted Inception deep neural network model.

Each set contained 1000 unique images consisting of profile shots of the
person’s hand, along with 3/4 profiles and shots from above and below.

Figure 6: Examples of the sort of images that appear in the current model’s
data set of the American Sign Language single hand positions for 0 (top left)
to 9 (bottom right)

The states $\boldsymbol{x}_{i}$ are the vectors containing the values of pre-
softmax layer bottlenecks of size $n$ for however many neurons are in the
penultimate layer. Schematically the network’s layer whose outputs are
$\boldsymbol{x}_{i}$ is shown in the Diagram in Fig. 5 as the fully connected
(bottleneck layer) in Unit H. Elements of this set that gave incorrect
readings are noted and copied into the set $\mathcal{Y}$.

###  4.2 Experiments and results

Once the network was trained, additional 10000 images of the same ratio were
evaluated using the trained system. For these experiments the classification
decision rule was to return a gesture number that corresponds to the network
output with the highest score (winner-takes-all) if the highest score exceeds
a given threshold, $\gamma\in[0,1]$. Ties are broken arbitrarily at random. If
the highest score is smaller than or equal to the threshold then no responses
are returned.

To assess performance of the resulting classifier, we used the following
indicators as functions of threshold $\gamma$:

$\begin{split}&\mbox{True Positive Rate
}(\gamma)=\frac{TP(\gamma)}{FN(\gamma)+TP(\gamma)},\\\
&\mbox{Missclassification Rate }(\gamma)=\frac{FP(\gamma)}{FP(0)},\end{split}$
(18)

where $TP(\gamma)$ is the number of true positives, $FN(\gamma)$ is the number
of false negatives, and $FP(\gamma)$ is the number of false positives. The
definitions of these variables are provided in Table 1.

Table 1: Error types in the system. Stars mark instances/events that are not accounted for. Presence of | System’s | Error
---|---|---
a gesture | response | Type
Yes | Correctly classified | True Positive
Incorrectly classified | False Positive
Not reported | False Negative
No | Reported | False Positive*
Not reported | True Negative*

In our experiments we did not add any negatives to the test set, as the
original focus was to illustrate how the approach may cope with
misclassification errors. This implies that the number of True Negatives is
$0$ for any threshold $\gamma\in[0,1]$ and, consequently, the rate of false
positives is always $1$. Therefore, instead of using traditional ROC curves
showing the rate of true positives against the rate of false positives, we
employed a different family of curves in which the rate of false positives is
replaced with the rate of misclassification as defined by (18).

A corresponding performance curve for this Core AI system is shown in Fig. 7.

Figure 7: Performance curve for the Core AI system (Inception) on the testing
set of 10000 images. Threshold $\gamma$ was varying from $1$ (bottom left
corner) to $0$ (top right corner)

At $\gamma=0$ the result was an 82.4% success rate for the adapted algorithm.
At this end of the curve, the observed performance was comparable/similar to
that reported in e.g. [7] (see also references therein). The numbers of errors
per each gesture in the trained system are shown in Table 2.

Table 2: Errors per gesture (misclassifications). Top row corresponds to the gesture number, the bottom row indicates the number of errors for each gesture. 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
10 | 52 | 235 | 62 | 410 | 80 | 269 | 327 | 207 | 108

The variance of errors is mostly consistent among the ten classes with very
few errors for the “0” gesture, likely due to its unique shape among the
classes.

Once the errors were isolated, we used Algorithms 1 and 2 to construct
correcting ensembles improving the original core AI. To train the ensembles,
the testing data set of 10000 images that has been used to assess performance
of Inception was split into two non-overlapping subsets. The first subset,
comprised of 6592 records of data points corresponding to correct responses
and 1408 records corresponding to errors, was used to train the correcting
ensembles. This subset was the ensemble’s training set, and it accounted for
80$\%$ of the data. The second subset, the ensemble’s testing set, combining
1648 data points of correct responses and 352 elements labelled as errors was
used to test the ensemble.

Both algorithms have been run on the first subset, the ensemble’s training
set. For simplicity of comparison and evaluation, we iterated the algorithms
only once (i.e. did not build cascades of ensembles). In the regularization
step, step 2, we used Kaiser-Guttman test. This returned $174$ principal
components reducing the original dimensionality more than 10 times. After the
whitening transformation, step 3, we assessed the values of
$|\langle\boldsymbol{x}_{i}/\|\boldsymbol{x}_{i}\|,\boldsymbol{x}_{j}/\|\boldsymbol{x}_{j}\|\rangle|$
(shown in Fig. 8).

Figure 8: Values of
$|\langle\boldsymbol{x}_{i}/\|\boldsymbol{x}_{i}\|,\boldsymbol{x}_{j}/\|\boldsymbol{x}_{j}\|\rangle|$
(color-coded) for the data points labelled as errors.

According to Fig. 8, data points labelled as errors are largely orthogonal to
each other apart from few modestly-sized groups.

The number of clusters, parameter $p$ in step 5, was varied from 2 to 1408 in
regular increments. As a clustering algorithm we used standard k-means routine
(k-means ++) supplied with MATLAB 2016a. For each value of $p$, we run the
k-means algorithm 10 times. For each clustering pass we constructed the
corresponding nodes $f_{j}$ (or their pairs for Algorithm 2) as prescribed in
step 6, and combined them into a single correcting ensemble in accordance with
step 7.

Before assessing performance of the ensemble, we evaluated filtering
properties of the ensemble as a function of the number of clusters used. For
consistency with predictions provided in Theorems 1 – 3, Algorithm 1 was used
in this exercise. Results of the test are shown in Fig 9.

Figure 9: True Positive rate at $\gamma=0$ for the combined system as a
function of the number of clusters, $p$. Left panel corresponds to Algorithm 1
with the optional projection step. Right panel corresponds to Algorithm 1
without the projection step.

Note that as the number $p$ of clusters increases, the True Positive Rate at
$\gamma=0$ as a function of $p$, approaches 1 regardless of the projection
step. This is in agreement with theoretical predictions stemming from Theorem
2. We also observed that performance drops rapidly with the average number of
elements assigned to a cluster. In view of our earlier observation that
vectors labelled as “errors” appear to be nearly orthogonal to each other,
this drop is consistent with the bound provided in Corollary 1.

Next we assessed performance of Algorithms 1, 2 and resulting ensembles on the
training and testing sets for $p=76,150,224,298$. In both algorithms, optional
projection step was used. The value of threshold $\theta$ was set to $0.2$. In
general, the value of threshold $\theta$ can be selected arbitrarily in an
interval of feasible values of $c_{j}$. When the optional projection step is
used, this interval is $(0,1)$. Here we set the value of $\theta$ so that the
hyperplanes $h_{j,2}$ in step 6 of Algorithm 2 produced by standard perceptron
algorithm [39] consistently yielded perfect separation. Results are shown in
Figs. 10 and 11.

Figure 10: Performance of the combined system after application of Algorithms
1 (red triangles) and 2 (green circles) on the training set for different
numbers of clusters/nodes $p$ in step 5. Blue squares show performance of core
AI system.

Figure 11: Performance of the combined system after application of Algorithms
1 (red triangles) and 2 (green circles) on the testing set for different
numbers of clusters/nodes $p$ in step 5. Blue squares show performance of core
AI system.

According to Fig. 10, performance on the training set grows with $p$, as
expected. This is aligned with theoretical results presented in Section 3.1.
The ensembles rapidly remove misclassification errors from the system, albeit
at some cost to True Positive Rate. The latter cost for Algorithm 2 appears to
be negligible. On the testing set, the picture changes. We see that, as the
number $p$ of clusters/nodes grows, performance of the ensemble saturates,
with Algorithm 1 catching-up with Algorithm 2. This signals an over-fit and
indicates a point where further increases in the number of nodes do not
translate into expected improvements of the combined systems’s performance.
Apparent lack of correlations between feature vectors corresponding to errors
(illustrated with Fig. 8) may also contribute to the observed performance
saturation on the testing set.

Notably, for $\gamma$ small both algorithms removed significant proportions of
misclassification errors. This could be due to that training and testing sets
for Algorithms 1 and 2 have been created from the performance analysis of the
original core AI system at $\gamma=0$.

##  5 Conclusion

In this work we presented a novel technology for computationally efficient
improvements of generic AI systems, including sophisticated Multilayer and
Deep Learning neural networks. These improvements are easy-to-train ensembles
of elementary nodes. After the ensembles are constructed, a possible next step
could be to further optimize the system via e.g. error back-propagation.
Mathematical operations at the nodes involve computations of inner products
followed by standard non-linear operations like ReLU, step functions,
sigmoidal functions etc. The technology was illustrated with a simple case
study confirming its viability. We note that the proposed ensembles can be
employed for learning new tasks too.

The proposed concept builds on our previous work [23] and complements results
for equidistributions in a unit ball to product measure distributions. When
the clustering structure is fixed, the method is inherently one-shot and non-
iterative, and its computational complexity scales at most linearly with the
size of the training set. Sub-linear computational complexity of the ensembles
construction makes the technology particularly suitable for large AI systems
that have already been deployed and are in operation.

An intriguing and interesting feature of the approach is that training of the
ensembles is largely achieved via Fisher linear discriminants. This, combined
with the ideas from [22], paves the way for a potential relaxation of the
i.i.d. assumption for the sampled data. Dealing with this as well as exploring
the proposed technology on a range of different AI architectures and
applications is the focus of our future work.

##  6 Acknowledgement

The work is supported by Innovate UK Technology Strategy Board (Knowledge
Transfer Partnership grants KTP009890 and KTP010522) and by the Ministry of
Education and Science of Russian Federation (Project No. 14.Y26.31.0022). The
authors are thankful to Tatiana Tyukina for help and assistance with preparing
the manuscript and artwork.

## References

## References

  * Anderson et al. [2014] J. Anderson, M. Belkin, N. Goyal, L. Rademacher, and 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:1–30, 2014.
  * Arthur and Vassilvitskii [2006] D. Arthur and S. Vassilvitskii.  How slow is the k-means method?  In _Proceedings of the twenty-second annual symposium on Computational geometry_ , pages 144–153. ACM, 2006.
  * Arthur and Vassilvitskii [2007] D. Arthur and S. Vassilvitskii.  k-means++: The advantages of careful seeding.  In _Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms_ , pages 1027–1035. Society for Industrial and Applied Mathematics, 2007.
  * Ball [1997] K. Ball.  An elementary introduction to modern convex geometry.  _Flavors of geometry_ , 31:1–58, 1997.
  * Barron [1993] A. R. Barron.  Universal approximation bounds for superposition of a sigmoidal function.  _IEEE Trans. on Information Theory_ , 39(3):930–945, 1993.
  * Beene et al. [2018] R. Beene, A. Levin, and E. Newcomer.  Uber self-driving test car in crash wasn’t programmed to brake.  https://www.bloomberg.com/news/articles/2018-05-24/uber-self-driving-system-saw-pedestrian-killed-but-didn-t-stop, 2018\.
  * Bheda and Radpour [2017] V. Bheda and D. Radpour.  Using deep convolutional networks for gesture recognition in american sign language.  _arXiv preprint arXiv:1710.06836_ , 2017.
  * Brahma et al. [2016] P. P. Brahma, D. Wu, and Y. She.  Why deep learning works: a manifold disentanglement perspective.  _IEEE Transactions On Neural Networks And Learning Systems_ , 27(10):1997–2008, 2016.
  * Chapelle [2007] O. Chapelle.  Training a support vector machine in the primal.  _Neural computation_ , 19(5):1155–1178, 2007\.
  * Chen et al. [2015] T. Chen, I. Goodfellow, and J. Shlens.  Net2net: Accelerating learning via knowledge transfer.  _ICLR 2016_ , 2015.
  * Cucker and Smale [2002] F. Cucker and S. Smale.  On the mathematical foundations of learning.  _Bulletin of the American mathematical society_ , 39(1):1–49, 2002.
  * Donoho [2000] D. Donoho.  High-dimensional data analysis: The curses and blessings of dimensionality.  _AMS math challenges lecture_ , 1(2000):32, 2000\.
  * Draelos et al. [2017] T. J. Draelos, N. E. Miner, C. C. Lamb, C. M. Vineyard, K. D. Carlson, C. D. James, and J. B. Aimone.  Neurogenesis deep learning.  In _IEEE International Joint Conference on Neural Networks (IJCNN)_ , pages 526–533. IEEE, 2017.
  * Fahlman and Lebiere [1990] S. E. Fahlman and C. Lebiere.  The cascade-correlation learning architecture.  In _Advances in neural information processing systems_ , pages 524–532, 1990.
  * Foxx [2018] C. Foxx.  Face recognition police tools “staggeringly inaccurate”.  http://www.bbc.co.uk/news/technology-44089161, 2018.
  * Freund and Schapire [1997] Y. Freund and R. E. Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _Journal of computer and system sciences_ , 55(1):119–139, 1997.
  * Gama and Brazdil [2000] J. Gama and P. Brazdil.  Cascade generalization.  _Machine learning_ , 41(3):315–343, 2000.
  * Gibbs [1960 (1902] J. Gibbs.  _Elementary Principles in Statistical Mechanics, developed with especial reference to the rational foundation of thermodynamics_.  Dover Publications, New York, 1960 (1902).
  * Gorban [2007] A. N. Gorban.  Order-disorder separation: Geometric revision.  _Physica A_ , 374:85–102, 2007.
  * Gorban and Tyukin [2017] A. N. Gorban and I. Y. Tyukin.  Stochastic separation theorems.  _Neural Networks_ , 94:255–259, 2017.
  * Gorban and Tyukin [2018] A. N. Gorban and I. Y. Tyukin.  Blessing of dimensionality: mathematical foundations of the statistical physics of data.  _Philosophical Transactions of the Royal Society A_ , 376, 2018.
  * Gorban et al. [2018] A. N. Gorban, A. Golubkov, B. Grechuk, E. M. Mirkes, and I. Y. Tyukin.  Correction of ai systems by linear discriminants: Probabilistic foundations.  _Information Sciences_ , 466:303–322, 2018.
  * Gorban et al. [2019] A. N. Gorban, R. Burton, I. Romanenko, and I. Y. Tyukin.  One-trial correction of legacy AI systems and stochastic separation theorems.  _Information Sciences_ , 484:237–254, 2019.
  * Gromov [1999] M. Gromov.  _Metric Structures for Riemannian and non-Riemannian Spaces. With appendices by M. Katz, P. Pansu, S. Semmes. Translated from the French by Sean Muchael Bates_.  Birkhauser, Boston, MA, 1999.
  * Gromov [2003] M. Gromov.  Isoperimetry of waists and concentration of maps.  _GAFA, Geomteric and Functional Analysis_ , 13:178–215, 2003.
  * Hartigan and Wong [1979] J. A. Hartigan and M. A. Wong.  A K-Means clustering algorithm.  _Journal of the Royal Statistical Society. Series C (Applied Statistics)_ , 28(1):100–108, 1979.
  * He et al. [2016] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 770–778, 2016.
  * Hoeffding [1963] W. Hoeffding.  Probability inequalities for sums of bounded random variables.  _Journal of the American statistical association_ , 58(301):13–30, 1963.
  * Iandola et al. [2016] F. N. Iandola, S. Han, M. W. Moskewicz, K. Ashraf, W. J. Dally, and K. Keutzer.  Squeezenet: Alexnet-level accuracy with 50x fewer parameters and $<$ 0.5mb model size.  _arXiv preprint, arXiv:1602.07360_ , 2016.
  * Jackson [1993] D. Jackson.  Stopping rules in principal components analysis: A comparison of heuristical and statistical approaches.  _Ecology_ , 74(8):2204–2214, 1993.
  * Kainen [1997] P. C. Kainen.  Utilizing geometric anomalies of high dimension: When complexity makes computation easier.  In _Computer Intensive Methods in Control and Signal Processing_ , pages 283–294. Springer, 1997.
  * Kainen and Kurkova [1993] P. C. Kainen and V. Kurkova.  Quasiorthogonal dimension of euclidian spaces.  _Appl. Math. Lett._ , 6(3):7–10, 1993.
  * Kuznetsova et al. [2015] A. Kuznetsova, S. Hwang, B. Rosenhahn, and L. Sigal.  Expanding object detector’s horizon: Incremental learning framework for object detection in videos.  In _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 28–36, 2015.
  * Lévy [1951] P. Lévy.  _Problèmes concrets d’analyse fonctionnelle_.  Gauthier-Villars, Paris, second edition, 1951.
  * Misra et al. [2015] I. Misra, A. Shrivastava, and M. Hebert.  Semi-supervised learning for object detectors from video.  In _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3594–3602, 2015.
  * Pratt [1992] L. Pratt.  Discriminability-based transfer between neural networks.  _Advances in Neural Information Processing_ , (5):204–211, 1992.
  * Prest et al. [2012] A. Prest, C. Leistner, J. Civera, C. Schmid, and V. Ferrari.  Learning object class detectors from weakly annotated video.  In _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3282–3289, 2012.
  * Rokach [2010] L. Rokach.  Ensemble-based classifiers.  _Artificial Intelligence Review_ , 33(1-2):1–39, 2010.
  * Rosenblatt [1962] F. Rosenblatt.  _Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms_.  Spartan Books, 1962.
  * Russakovsky et al. [2014] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei.  Imagenet large scale visual recognition challenge.  _Int. J. Comput. Vis._ , pages 1–42, 2014.  DOI:10.1007/s11263-015-0816-y.
  * Scardapane and Wang [2017] S. Scardapane and D. Wang.  Randomness in neural networks: an overview.  _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ , 7(2), 2017.
  * Szegedy et al. [2015] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich.  Going deeper with convolutions.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1–9, 2015.
  * Vapnik and Chapelle [2000] V. Vapnik and O. Chapelle.  Bounds on error expectation for support vector machines.  _Neural Computation_ , 12(9):2013–2036, 2000\.
  * Vapnik and Izmailov [2017] V. Vapnik and R. Izmailov.  Knowledge transfer in svm and neural networks.  _Annals of Mathematics and Artificial Intelligence_ , pages 1–17, 2017.
  * Wang and Cui [2017] D. Wang and C. Cui.  Stochastic configuration networks ensemble with heterogeneous features for large-scale data analytics.  _Information Sciences_ , 417:55–71, 2017.
  * Wang and Li [2017a] D. Wang and M. Li.  Deep stochastic configuration networks with universal approximation property.  _arXiv preprint arXiv: 1702.05639. 2017_ , 2017a.  (An updated version of this work has been published in the Proceedings of 2018 IJCNN).
  * Wang and Li [2017b] D. Wang and M. Li.  Stochastic configuration networks: Fundamentals and algorithms.  _IEEE transactions on cybernetics_ , 47(10):3466–3479, 2017b.
  * Yosinski et al. [2014] J. Yosinski, J. Clune, Y. Bengio, and H. Lipson.  How transferable are features in deep neural networks?  In _Advances in neural information processing systems_ , pages 3320–3328, 2014.
  * Zheng et al. [2016] S. Zheng, Y. Song, T. Leung, and I. Goodfellow.  Improving the robustness of deep neural networks via stability training.  In _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 4480–4488, 2016.  https://arxiv.org/abs/1604.04326.

##  Appendix A Proofs of theorems and other technical statements

### Proof of Theorem 1

The proof follows immediately from Theorem 2 in [20] and Hoeffding inequality
[28]. Indeed, if $t>0$, $X_{i}$ are independent bounded random variables, i.e.
$a_{i}\leq X_{i}\leq b_{i}$, $i=1,\dots,n$, and
$\overline{X}=1/n\sum_{i=1}^{n}X_{i}$ then (Hoeffding inequality)

$\begin{split}P\left(\overline{X}-E[\overline{X}]\geq
t\right)\leq\exp\left(-\frac{2n^{2}t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right)\\\
P\left(|\overline{X}-E[\overline{X}]|\geq t\right)\leq
2\exp\left(-\frac{2n^{2}t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).\end{split}$

Given that $x_{ij}=X_{j}$ where $X_{j}$ are independent random variables with
$-1\leq X_{j}\leq 1$, $E[X_{j}^{2}]=\sigma_{j}^{2}$ (Assumption 1), we observe
that $\|\boldsymbol{x}_{i}\|^{2}=\sum_{j=1}^{n}X_{j}^{2}$

$\begin{split}&P\left(\left|\frac{\sum_{j=1}^{n}X_{j}^{2}}{n}-E\left[\frac{\sum_{j=1}^{n}X_{j}^{2}}{n}\right]\right|\geq
t\right)=\\\
&P\left(\left|\frac{\sum_{j=1}^{n}X_{j}^{2}}{n}-\frac{R_{0}^{2}}{n}\right|\geq
t\right)=P\left(\left|\frac{\|\boldsymbol{x}_{i}\|^{2}}{R_{0}^{2}}-1\right|\geq\frac{tn}{R_{0}^{2}}\right)\\\
&\leq 2\exp\left(-2nt^{2}\right).\end{split}$

Denoting $\varepsilon={tn}/{R_{0}^{2}}$ and recalling that $0\leq
X_{j}^{2}\leq 1$ we conclude that (2) holds true.

Noticing that $E[x_{ik}x_{jk}]=E[x_{ik}]E[x_{jk}]=0$, $E[y_{k}x_{ik}]=0$,
$-1\leq x_{ik}\leq 1$, $-1\leq x_{jk}\leq 1$, and $-1\leq y_{k}x_{ik}\leq 1$,
we observe that estimates (3) and (4) follow. $\square$

### Proof of Theorem 2

Recall that for any events $A_{1},\dots,A_{k}$ the following estimate holds:

$P(A_{1}\&A_{2}\&\cdots\&A_{k})\geq 1-\sum_{i=1}^{k}(1-P(A_{i})).$ (19)

Let

$\frac{\|\boldsymbol{x}_{M+1}\|^{2}}{R_{0}^{2}}\geq 1-\varepsilon\ \
\mbox{(event}\ A_{1}\mbox{)},$

and

$\left\langle\frac{\boldsymbol{x}_{M+1}}{R_{0}},\frac{\boldsymbol{x}_{i}}{R_{0}}\right\rangle<1-\varepsilon\
\ \mbox{(events}\ A_{2},\dots A_{M+1}\mbox{)}.$

The statement now follows from (2) and (3) with $\delta=1-\varepsilon$, and
(19). $\square$

### Proof of Theorem 3

Suppose that $\|\boldsymbol{x}_{i}\|^{2}/R_{0}^{2}\geq 1-\varepsilon$ for all
$\boldsymbol{x}_{i}\in\mathcal{Y}$ (event $A_{1}$). Then

$\begin{split}\ell_{k}(\boldsymbol{x}_{i})=&\frac{1}{k}\left(\frac{\|\boldsymbol{x}_{i}\|^{2}}{R_{0}^{2}}+\sum_{\boldsymbol{x}_{j}\in\mathcal{Y},\
\boldsymbol{x}_{j}\neq\boldsymbol{x}_{i}}\left\langle\frac{\boldsymbol{x}_{i}}{R_{0}},\frac{\boldsymbol{x}_{j}}{R_{0}}\right\rangle\right)\geq\frac{1-\varepsilon+\beta(k-1)}{k}\\\
&\ \mbox{for all }\boldsymbol{x}_{i}\in\mathcal{Y}.\end{split}$

Note that $\overline{\boldsymbol{x}}\in[-1,1]^{n}$ by construction. Consider
events

$\ell_{k}(\boldsymbol{x}_{j})=\left\langle\frac{\boldsymbol{x}_{j}}{R_{0}},\frac{\overline{\boldsymbol{x}}}{R_{0}}\right\rangle<\frac{1-\varepsilon+\beta(k-1)}{k}\
\mbox{(events}\ A_{1+j}\mbox{)}$

$j=1,\dots,M$. According to Theorem 1 and (19)

$\begin{split}&P(A_{1})\geq
1-k\exp\left(-\frac{2R_{0}^{4}\varepsilon^{2}}{n}\right)\\\ &P(A_{1+j})\geq
1-\exp\left(-\frac{R_{0}^{4}(1-\varepsilon+\beta(k-1))^{2}}{2k^{2}n}\right).\end{split}$

Hence

$\begin{split}&P(A_{1}\&\cdots\&A_{1+M})\geq\\\
&1-k\exp\left(-\frac{2R_{0}^{4}\varepsilon^{2}}{n}\right)-M\exp\left(-\frac{R_{0}^{4}(1-\varepsilon+\beta(k-1))^{2}}{2k^{2}n}\right).\end{split}$

The result now follows $\square$.

### Proof of Corollary 1

Let $\|\boldsymbol{x}_{i}\|^{2}/R_{0}^{2}\geq 1-\varepsilon$ for all
$\boldsymbol{x}_{i}\in\mathcal{Y}$ (event $A_{1}$), and

$\left\langle\frac{\boldsymbol{x}_{i}}{R_{0}},\frac{\boldsymbol{x}_{j}}{R_{0}}\right\rangle\geq-\delta\
\mbox{for all}\ \boldsymbol{x}_{i},\boldsymbol{x}_{j}\in\mathcal{Y},\
\boldsymbol{x}_{i}\neq\boldsymbol{x}_{j}\ \mbox{(event }\ A_{2}\mbox{)}.$

The corollary follows immediately from (19) and Theorem 1 (equations (2), (3))
$\square$.

### Proof of Corollary 2

Let $\|\boldsymbol{x}_{j}\|^{2}\geq 1-\varepsilon$. Then
$h(\boldsymbol{x})\geq 0$ for all $\boldsymbol{x}\in\Omega$. Estimate (13)
hence follows from Theorem 1 and (19). $\square$.

### Proof of Lemma 1

The proof follows that of Theorem 3 in [23]. Let $\boldsymbol{x}$ be an
element of $\mathcal{M}$ and $p_{h}$ be the probability of the event
$h(\boldsymbol{x})\geq 0$. Then the probability of the event that
$h(\boldsymbol{x})\geq 0$ for at most $m$ elements from $\mathcal{M}$ is

$P(M,m)=\sum_{k=0}^{m-1}\left(\begin{array}[]{c}M\\\
k\end{array}\right)(1-p_{h})^{M-k}p_{h}^{k}.$

Observe that ${P}(M,m)$, as a function of $p_{h}$, is monotone and non-
increasing on the interval $[0,1]$, with ${P}(M,m)=0$ at $p_{h}=1$ and
${P}(M,n)=1$ at $p_{h}=0$. Hence

${P}(M,m)\geq\sum_{k=0}^{m-1}\left(\begin{array}[]{c}M\\\
k\end{array}\right)(1-p_{\ast})^{M-k}p_{\ast}^{k}=(1-p_{\ast})^{M}\sum_{k=0}^{m-1}\left(\begin{array}[]{c}M\\\
k\end{array}\right)\left(\frac{p_{\ast}}{1-p_{\ast}}\right)^{k}.$

Given that $\frac{(M-m+1)^{k}}{k!}\leq\left(\begin{array}[]{c}M\\\
k\end{array}\right)\leq\frac{M^{k}}{k!}$ for $0\leq k\leq m-1$, we obtain

${P}({M},m)\geq(1-p_{\ast})^{M}\sum_{k=0}^{m-1}\frac{1}{k!}\left(\frac{(M-m+1)p_{\ast}}{1-p_{\ast}}\right)^{k}.$

Expanding $e^{x}$ at $x=0$ with the Lagrange remainder term:

$e^{x}=\sum_{k=0}^{m-1}\frac{x^{k}}{k!}+\frac{x^{m}}{m!}e^{\xi},\
\xi\in[0,x],$

results in the estimate

$\sum_{k=0}^{m-1}\frac{x^{k}}{k!}\geq e^{x}\left(1-\frac{x^{m}}{m!}\right)\
\mbox{for all}\ x\geq 0.$

Hence

$\begin{split}&{P}({M},m)\geq\\\
&(1-p_{\ast})^{M}\exp\left(\frac{(M-m+1)p_{\ast}}{1-p_{\ast}}\right)\left(1-\frac{1}{m!}\left(\frac{(M-m+1)p_{\ast}}{(1-p_{\ast})}\right)^{m}\right).\end{split}$

$\square$

##  Appendix B Hyperplanes vs ellipsoids for error isolation

Consider

$C_{n}(\varepsilon)=B_{n}(1)\cap\left\\{\xi\in\mathbb{R}^{n}\left|\
\left\langle\frac{\boldsymbol{x}}{\|\boldsymbol{x}\|},\xi\right\rangle\geq
1-\varepsilon\right\\}\right..$ (20)

Let

${\rho}(\varepsilon)=(1-(1-\varepsilon)^{2})^{\frac{1}{2}}.$

Note that ${\rho}(\varepsilon)$ is the radius of the ball containing the
spherical cup $C_{n}$. Lemma 2 estimates volumes of spherical caps
$C_{n}(\varepsilon)$ relative to relevant $n$-balls of radius
${\rho}(\varepsilon)$.

###### Lemma 2

Let $C_{n}(\varepsilon)$ be a spherical cap defined as in (20),
$\varepsilon\in(0,1)$. Then

$\frac{\rho(\varepsilon)^{n+1}}{2}\left[\frac{1}{\pi^{\frac{1}{2}}}\frac{\Gamma\left(\frac{n}{2}+1\right)}{\Gamma\left(\frac{n}{2}+\frac{3}{2}\right)}\right]<\frac{\mathcal{V}(C_{n}(\varepsilon))}{\mathcal{V}(B_{n}(1))}\leq\frac{\rho(\varepsilon)^{n}}{2}.$

Note that [4] $\mathcal{V}(B_{n}(r))=r^{n}\mathcal{V}(B_{n}(1))$ for all
$n\in\mathbb{N}$ $r>0$. Hence the estimate of
$\mathcal{V}(C_{n}(\varepsilon))$ from above is:

$\mathcal{V}(C_{n}(\varepsilon))\leq\frac{1}{2}\mathcal{V}(B_{n}(1))\rho(\varepsilon)^{n}.$
(21)

Let us calculate the estimate of $\mathcal{V}(C_{n}(\varepsilon))$ from below.
It is clear that

$\mathcal{V}(C_{n}(\varepsilon))=V(B_{n-1}(1))\int_{1-\varepsilon}^{1}(1-x^{2})^{\frac{n-1}{2}}dx$

The integral in the right-hand side of the above expression can be estimated
from below as

$\begin{split}&\int_{1-\varepsilon}^{1}(1-x^{2})^{\frac{n-1}{2}}dx>\int_{1-\varepsilon}^{1}(1-x^{2})^{\frac{n-1}{2}}xdx\\\
&=\frac{1}{2}\cdot\frac{1}{\frac{n}{2}+\frac{1}{2}}\cdot(1-(1-\varepsilon)^{2})^{\frac{n+1}{2}}=\frac{1}{2}\cdot\frac{1}{\frac{n}{2}+\frac{1}{2}}\cdot\rho(\varepsilon)^{n+1}\end{split}$

Recall that
$B_{n}(1)=\frac{\pi^{\frac{n}{2}}}{\Gamma\left(\frac{n}{2}+1\right)}$,
$\Gamma(x+1)=x\Gamma(x)$. Hence

$\begin{split}&B_{n-1}(1)\cdot\frac{1}{\frac{n}{2}+\frac{1}{2}}=\frac{\pi^{\frac{n-1}{2}}}{\Gamma\left(\frac{n}{2}+\frac{1}{2}\right)}\frac{1}{\frac{n}{2}+\frac{1}{2}}\\\
&=\frac{\pi^{\frac{n-1}{2}}}{\Gamma\left(\frac{n+1}{2}+1\right)},\end{split}$

and

$\int_{1-\varepsilon}^{1}(1-x^{2})^{\frac{n-1}{2}}dx>\frac{1}{2}\mathcal{V}(B_{n}(1))\rho(\varepsilon)^{n+1}\left[\frac{1}{\pi^{\frac{1}{2}}}\frac{\Gamma\left(\frac{n}{2}+1\right)}{\Gamma\left(\frac{n}{2}+\frac{3}{2}\right)}\right]$

$\square$

###### Corollary 3

Let $C_{n}(\varepsilon)$ be a spherical cap defined as in (20),
$\varepsilon\in(0,1)$, and $B_{n}(k\rho(\varepsilon))$ be an $n$-ball with
radius $k\rho(\varepsilon)$, $k\in\mathbb{R}_{>0}$. Then

$\frac{\mathcal{V}(B_{n}(k\rho(\varepsilon)))}{\mathcal{V}(C_{n}(\varepsilon))}<k^{n}\frac{2\pi^{\frac{1}{2}}}{\rho(\varepsilon)}\left[\frac{\Gamma\left(\frac{n}{2}+1\right)}{\Gamma\left(\frac{n}{2}+\frac{3}{2}\right)}\right]^{-1}$

###### Remark 3

Using Stirling’s approximation we observe that

$\frac{\Gamma\left(\frac{n}{2}+1\right)}{\Gamma\left(\frac{n}{2}+\frac{3}{2}\right)}=O\left(n^{-\frac{1}{2}}\right).$

Thus
$\frac{\mathcal{V}(B_{n}(\varepsilon))}{\mathcal{V}(C_{n}(\varepsilon))}<k^{n}H(n,\varepsilon)$
where $H(n,\varepsilon)=O\left(\frac{n^{1/2}}{\rho(\varepsilon)}\right)$.

According to Corollary 3 the volumes of $B_{n}(\varepsilon)$,
$B_{n}(\kappa\rho(\varepsilon))$, $\kappa\in(0,1)$ decay exponentially with
dimension $n$ relative to that of $C_{n}(\varepsilon)$. This implies that
distance-based detectors are extremely localized, and in comparison with
simple perceptrons, the proportion of points to which they respond positively
is negligibly small. On the other hand, filtering properties of hyperplanes
are extreme in high dimension (see Theorems 2, 3 in Section 3.1). This
combination of properties makes perceptrons and their ensembles particularly
attractive for fine-tuning of existing AI systems.