# Element order versus minimal degree in permutation groups: an old lemma with
new applications

László Babai and Ákos Seress University of Chicago.
http://people.cs.uchicago.edu/l̃aci/people.cs.uchicago.edu/$\sim$laciOhio
State University. Deceased February 13, 2013.

###### Abstract

In this note we present a simplified and slightly generalized version of a
lemma the authors published in 1987. The lemma as stated here asserts that if
the order of a permutation of $n$ elements is greater than $n^{\alpha}$ then
some nonidentity power of the permutation has support size less than
$n/\alpha$. The original version made an unnecessary additional assumption on
the cycle structure of the permutation; the proof of the present cleaner
version follows the original proof verbatim. Application areas include
parallel and sequential algorithms for permutation groups, the diameter of
Cayley graphs of permutation groups, and the automorphisms of combinatorial
structures with regularity constraints such as Latin squares, Steiner
2-designs, and strongly regular graphs. This note also serves as a modest
tribute to the junior author whose untimely passing is deeply mourned.

##  1 The lemma

For a permutation $\pi$ on the set $K$, the _support_ of $\pi$ is defined as
the set $\operatorname{supp}(\pi)=\\{x\in K\mid x^{\pi}\neq x\\}$. $S_{n}$
denotes the symmetric group of degree $n$ (and order $n!$). The _degree_ of a
permutation is the size of its support, and the _minimal degree_ of a
permutation group is the smallest degree of its non-identity elements. The
following lemma shows that if there are elements of large order in a
permutation group then its minimal degree is small.

Lemma. Let $\pi\in S_{n}$ have order $\geq n^{\alpha}$ for some $\alpha>0$.
Then $|\operatorname{supp}(\pi^{m})|\leq n/\alpha$ for some power $\pi^{m}\neq
1$.

###### Proof.

Let $\pi$ act on the set $K$ where $|K|=n$. Let the order of $\pi$ be
$N=n^{\alpha}=\prod_{i=1}^{r}q_{i}$ where $q_{i}=p_{i}^{\beta_{i}}>1$ are
powers of distinct primes $p_{i}$. For each $x\in K$, let us consider the set
$P(x)$ of those $i$ for which $q_{i}$ divides the length of the $\pi$-cycle
through $x$. Clearly, for each $x\in K$,

$\prod_{i\in P(x)}q_{i}\leq n.$ (1)

Let $n(i)$ denote the number of points $x\in K$ such that $i\in P(x)$. Let us
estimate the weighted average $W$ of the $n(i)$ with weights $\log q_{i}$.
Recall that the sum of weights is $\sum\log q_{i}=\log N\geq\alpha\log n$,
therefore (using Eq. (1))

$W\leq\sum_{x\in K}\sum_{i\in P(x)}\log q_{i}/(\alpha\log n)\leq(n\log
n)/(\alpha\log n)=n/\alpha.$ (2)

Thus we infer that $n(i)\leq n/\alpha$ for some $i\leq r$. Now let $m=N/p_{i}$
be the corresponding maximal divisor of $N$. Clearly $\pi^{m}$ is not the
identity and it fixes all but $n(i)$ points. ∎

##  2 History and applications

The original version of this lemma, published as [BS1, Lemma 3], assumed that
the permutation $\pi$ involved cycles of prime lengths $p_{i}$ such that
$\prod p_{i}\geq n^{\alpha}$. As we have seen, this assumption is unnecessary.
The proof of the above cleaner form requires no new ideas, however; it is an
essentially verbatim copy of the original proof.

Applications of this lemma are manifold, both old and new.

###  2.1 Degree of transitivity, diameter, parallel and sequential complexity
of permutation groups

In [BS1], the authors used this lemma to obtain a short proof of a theorem of
Jordan [Jo1, Jo2] on the degree of transitivity of permutation groups. In
another simultaneous paper [BS2], the authors used this lemma to prove an
$\exp(\sqrt{n\ln n}(1+o(1)))$ upper bound on the diameter of all Cayley graphs
of $S_{n}$; this bound was not improved until very recently [HS]. The
breakthrough 2013 paper [HS] by Helfgott and Seress that reduced the diameter
bound to quasipolynomial (exponential in a constant power of $\log n$) makes
substantial use of a slight generalization of the lemma. In [BS3] the present
authors, again using the Lemma, extended the $\exp(\sqrt{n\ln n}(1+o(1)))$
bound to all permutation groups of degree $n$ (subgroups of $S_{n}$), which in
this form is tight since $S_{n}$ has cyclic subgroups of order
$\exp(\sqrt{n\ln n}(1+o(1)))$ (product of small prime length cycles). In
[BLS1], the Lemma played a key role in settling the parallel complexity of the
permutation group membership problem; the subsequent papers [BLS2, BLS3] used
the Lemma to design and analyze improved sequential algorithms for the same
problem.

###  2.2 Latin squares

The present note was prompted by a conversation between Babai and Ian Wanless
in July 2013 at a conference celebrating Peter Cameron at Queen Mary,
University of London. Wanless mentioned the following recent result of his
with Brendan McKay and Xiande Zhang. Recall that a _quasigroup_ is a set with
a binary operation such that all equations of the form $ax=b$ and $ya=b$ are
uniquely solvable. In other words, a quasigroup is a set with a binary
operation of which the multiplication table is a Latin square.

######  Theorem 2.1 (McKay, Wanless, Zhang [MWZ]).

No automorphism of a quasigroup of order $n$ has order greater than $n^{2}/4.$

We show that a slightly weaker bound, $n^{2}$, is immediate from the Lemma.
Indeed, let $\pi$ be a non-identity automorphism of some quasigroup $G$ of
order $n$. Assume the order of $\pi$ is greater than $n^{2}$. Then some power
$\pi^{m}\neq 1$ fixes more than half the elements of $G$. But the set of fixed
points of a non-identity automorphism is a proper sub-quasigroup and therefore
has order $\leq n/2$, a contradiction. ∎

The McKay–Wanless–Zhang argument is not dissimilar to ours. They in fact prove
the following stronger result.

######  Theorem 2.2 (McKay, Wanless, Zhang [MWZ]).

No autotopism of a quasigroup of order $n$ has order greater than $n^{2}/4.$

An _autotopism_ of a quasigroup $G$ is a triple $(\alpha,\beta,\gamma)$ of
permutations of the set $G$ such that for all $g,h\in G$ we have
$\alpha(g)\beta(h)=\gamma(gh)$.

Wanless pointed out that a quadratic bound, $9n^{2}$, on the order of
autotopisms of quasigroups of order $n$ also follows quickly from the Lemma.
Slightly modifying his argument, we infer a bound of $4n^{2}$ on the order of
any autotopism. (Of course this is still a factor of 16 worse than their
result.)

Indeed, assume $\theta=(\alpha,\beta,\gamma)$ is an autotopism of order
greater than $(2n)^{2}$. We can view the autotopisms as acting on the union
$G_{1}\,\dot{\cup}\,G_{2}\,\dot{\cup}\,G_{3}$ of three disjoint copies of $G$.
In fact, the action on $U=G_{1}\,\dot{\cup}\,G_{2}$ is faithful; let us
consider this action. By the Lemma, some power $\theta^{m}\neq 1$ has more
than $n$ fixed points on $U$. Therefore it has at least one fixed point in
each of $G_{1}$ and $G_{2}$. A result by McKay, Meynert, and Myrvold [MMM]
asserts that if a non-identity autotopism has a fixed point in $G_{1}$ and a
fixed point in $G_{2}$ then the number of fixed points in each part is the
same and that number cannot exceed $n/2$, a contradiction. ∎

We do not expect the quadratic rate of growth in these results to be optimal.
Let $f(n)$ denote the maximum of the orders of automorphisms of quasigroups of
order $\leq n$. By the above, we have $f(n)=O(n^{2})$.

######  Conjecture 2.1.

$f(n)=o(n^{2}).$

On the other hand, McKay et al. [MWZ] conjecture that 2 is the best possible
exponent.

######  Conjecture 2.2 ([MWZ]).

For every $\epsilon>0$ and for infinitely many values of $n$,

$f(n)>n^{2-\epsilon}.$

The construction of quasigroups with automorphisms of nearly quadratic order
seems to face significant obstacles; currently, no superlinear examples are
known (cf. [MWZ]).

It is noted in [MWZ] that the quadratic upper bound on the order of
automorphisms holds in particular for Steiner Triple Systems (STSs) because
such systems can be viewed as quasigroups: if $x,y$ are distinct points of an
STS then define $xy$ as the third point in the unique triple containing $x,y$;
and set $xx=x$.

We observe that the quadratic upper bound for STSs extends to all Steiner
2-designs. A Steiner 2-design (also called a “regular linear space”) is an
incidence geometry with lines of uniform length and exactly one line through
every pair of points. If it has $n$ points and each line has $k$ points then
this is a $2-(n,k,1)$-design.

######  Proposition 2.3.

Let $X$ be a Steiner 2-design with $n$ points and with lines of length $k\geq
3$. Let $m$ be the maximum order of automorphisms of $X$. Then

  * (a)

$m<n^{2}$

  * (b)

$m=O\left(n^{1+\frac{1}{k-2}}\right)$ where the implied constant is absolute.

The proof follows by combining the Lemma with a bound on the number of fixed
points of automorphisms of a Steiner 2-design by Davies [Da]. The details will
appear in [Ba2].

###  2.3 Strongly regular graphs

In another paper [Ba1], the Lemma is used to establish strong structural
constraints on the automorphism groups of strongly regular (SR) graphs.

Recall that a SR graph with parameters $(n,k,\lambda,\mu)$ has $n$ vertices,
is regular of degree $k$, each pair of adjacent vertices has $\lambda$ common
neighbors, and each pair of distinct, non-adjacent vertices has $\mu$ common
neighbors. Disjoint unions of cliques of equal size and their complements are
_trivial_ examples of SR graphs. The line graphs of complete graphs and of
complete bipartite graphs with equal parts are also SR; we refer to them and
to their complements as _graphic_ SR graphs.

The senior author has long suspected that the automorphism groups of non-
trivial, non-graphic SR graphs are “small.” The following result gives a
specific interpretation to this statement.

We say that a group $H$ is _involved_ in a group $G$ if $G$ has
subgroups$L\triangleleft K\leq G$ such that $H\cong K/L$ ($H$ is isomorphic to
a quotient of a subgroup of $G$). We note that the automorphism groups of the
trivial and the graphic SR graphs involve alternating groups of degree
$\geq\sqrt{n}$. It turns out that in all other cases, the alternating groups
involved are tiny. This has significant implications to attempts at
subexponential and possibly even quasi-polynomial-time isomorphism tests for
SR graphs, and it limits the possible primitive group actions on SR graphs. We
state the result.

######  Theorem 2.4 ([Ba1]).

If the alternating group $A_{t}$ is involved in the automorphism group of a
non-trivial, non-graphic SR graph with $n$ vertices then$t=O((\ln
n)^{2}/\ln\ln n)$.

Theorem 2.4 is derived from a lemma that limits the number of fixed points of
any non-identity automorphism of a regular graph in terms of its combinatorial
and spectral parameters; from this, a bound on the orders of automorphisms
follows via the Lemma above, and a bound on $t$ is then immediate. To apply
this general result to SR graphs, bounds on the second largest eigenvalue and
on the parameters $\lambda,\mu$ are derived from known results.

##  3 Ákos Seress
(November 24, 1958 – February 13, 2013)

Apart from minor updates, this note was written in August 2013, about six
months after the untimely passing of Ákos Seress [BO13]. I (Babai) had known
Ákos, 8 years my junior, from his undergraduate years in the late 70s at
Eötvös University, Budapest, where I was teaching at the time and he was a
star student, already active in research. But our real meeting of minds
occurred at a conference in Szeged, Hungary, in summer 1986, when by
serendipity both of us missed the boat for a scenic afternoon ride. It was
there, on the banks of the Tisza river, that I began to introduce Ákos, then a
fresh Ph. D. in combinatorics, to asymptotic group theory and algorithmic
group theory. That conversation evolved into a lifelong collaboration that
produced 15 joint papers spanning a quarter century. I count several of our
joint papers among the best of my career; this includes our last paper [BBS].
Ákos became a leader in algorithmic and computational group theory, an author
of the definitive monograph on the subject [Ser1], a major contributor to the
GAP symbolic algebra package, and a speaker at ICM 2006 in the algebra
section.

Ákos was a most generous friend and colleague. He died at the age of 54 of
renal cell carcinoma, a particularly aggressive form of cancer, diagnosed only
six months earlier. The disease struck at the height of his creative powers,
shortly after he had finished two breakthrough papers, one mathematical and
one computational: the above-mentioned paper [HS] with Helfgott, a _tour de
force_ in the combinatorial theory of permutation groups, and a computational
work on the Monster group [Ser2] that received the “Distinguished paper award”
at the ISSAC 2012 conference and was hailed as “a groundbreaking work” that
“marks a turning point in Majorana Theory.”

The Lemma discussed in this note was the fruit of the first hours of our
collaboration, conceived even before the return of the boat, so I find it most
appropriate to list Ákos as a coauthor.

Acknowledgment. I wish to thank Ian Wanless for the inspiring conversation at
the CameronFest last July and for his helpful comments on earlier versions of
this note.

## References

  * [Ba1] László Babai: On the automorphisms of strongly regular graphs I. _Proc. 5th Innovations in Theoretical Computer Science conf. (ITCS 2014)_ , ACM Press, to appear.
  * [Ba2] László Babai: On the automorphisms of strongly regular graphs II. In preparation.
  * [BBS] László Babai, Robert Beals, Ákos Seress: Polynomial-time theory of matrix groups. In _Proc. 41st STOC_ , pp. 55–64. ACM Press, 2009. DOI: 10.1145/1536414.1536425.
  * [BLS1] László Babai, Eugene M. Luks, Ákos Seress: Permutation groups in NC. In: _Proc. 19th STOC_ , pp. 409–420. ACM Press, 1987
  * [BLS2] László Babai, Eugene M. Luks, Ákos Seress: Fast management of permutation groups. In _Proc. 29th FOCS_ , pp. 272–282. IEEE Comp. Soc. 1988
  * [BLS3] László Babai, Eugene M. Luks, Ákos Seress: Fast management of permutation groups I. _SIAM J. Comput._ 26 (1997), 1310–1342
  * [BO13] László Babai, Eamonn O’Brien: Ákos Seress (1958–2013). Obituary on the GAP Forum, Feb. 15, 2013.
  * [BS1] László Babai, Ákos Seress: On the degree of transitivity of permutation groups: a short proof. _J. Combinatorial Theory-A_ 45 (1987), 310–315
  * [BS2] László Babai, Ákos Seress: On the diameter of Cayley graphs of the symmetric group. _J. Combinatorial Theory-A_ 49 (1988), 175–179
  * [BS3] László Babai, Ákos Seress: On the diameter of permutation groups. _Europ. J. Comb._ 13 (1992), 231–243
  * [CNP] Alan R. Camina, Peter M. Neumann, Cheryl E. Praeger: Alternating groups acting on finite linear spaces. Proc. London Math. Soc. (3) 87 (2003) 29–53.
  * [Da] D. Huw Davies: _Automorphisms of Designs._ Ph. D. Thesis, University of East Anglia, 1987. Cited by [CNP].
  * [HS] Harald Helfgott, Ákos Seress: On the diameter of permutation groups. _Annals of Mathematics._ To appear
  * [Jo1] Camille Jordan: Sur la limite de transitivité des groupes non alternés. _Bull. Soc. Math. France_ 1 (1873), 40–71
  * [Jo2] Camille Jordan: Nouvelles recherches sur la limite de transitivité des groupes qui ne continennent pas le groupe alterné. _J. Math._ 1 (1895), 35–60
  * [MMM] Brendan D. McKay, Alison Meynert, Wendy Myrvold: Small Latin squares, quasigroups, and loops. _Journal of Combinatorial Designs._ 15 (2007), 98–119.
  * [MWZ] Brendan D. McKay, Ian M. Wanless, Xiande Zhang: The order of automorphisms of quasigroups. _Journal of Combinatorial Designs._ To appear.
  * [Ser1] Ákos Seress: _Permutation Group Algorithms._ Cambridge Univ. Press, 2003
  * [Ser2] Ákos Seress: Construction of 2-closed M-representations. In: _Proc. Internat. Symp. on Symbolic and Algebraic Computation (ISSAC’12)_ , pp. 311–318. ACM Press, 2012


# Blessing of dimensionality at the edge

Ivan Y. Tyukin<EMAIL_ADDRESS>Alexander N. Gorban<EMAIL_ADDRESS>Alistair A. McEwan<EMAIL_ADDRESS>Sepehr Meshkinfamfard
<EMAIL_ADDRESS>Lixin Tang<EMAIL_ADDRESS>University of
Leicester, UK  Lobachevsky University, Russia  St Petersburg State
Electrotechnical University, Russia  University College London, UK  Key
Laboratory of Data Analytics and Optimization for Smart Industry (Northeastern
University), Ministry of Education, People Republic of China

###### Abstract

In this paper we present theory and algorithms enabling classes of Artificial
Intelligence (AI) systems to continuously and incrementally improve with
a-priori quantifiable guarantees – or more specifically remove classification
errors – over time. This is distinct from state-of-the-art machine learning,
AI, and software approaches. Another feature of this approach is that, in the
supervised setting, the computational complexity of training is linear in the
number of training samples. At the time of classification, the computational
complexity is bounded by few inner product calculations. Moreover, the
implementation is shown to be very scalable. This makes it viable for
deployment in applications where computational power and memory are limited,
such as embedded environments. It enables the possibility for fast on-line
optimisation using improved training samples. The approach is based on the
concentration of measure effects and stochastic separation theorems and is
illustrated with an example on the identification faulty processes in Computer
Numerical Control (CNC) milling and with a case study on adaptive removal of
false positives in an industrial video surveillance and analytics system.

###### keywords:

Stochastic separation theorems , artificial intelligence , machine learning ,
computer vision

††journal: Information Sciences

##  1 Introduction

The past decade has seen extraordinary growth and advances in technologies for
collecting and processing very large data streams and data sets. Central to
these advances has been the field of Artificial Intelligence (AI), built on
Machine Learning (ML) and Data Analytics theories. Exploitation of AI is
becoming overwhelmingly ubiquitous. For instance, end users and consumers use
mobile phone apps with AI capabilities, security systems may employ AI to
identify unwanted intrusions and infringements, heathcare systems may use AI
to assist clinical diagnosis or processes, and mechatronic systems may use AI
to implement control including autonomous and semi-autonomous functionality.
Examples of these in literature include those reported in [23], [32]. Whilst
this increase in application areas is due in part to advances in AI and ML, it
is also due to advances in hardware and supporting platforms. The emergence of
devices such as Nvidia GPUs and Google TPUs have meant that power of server-
or super-computer platforms are no longer necessarily required for deployment
of deep learning systems.

Whilst state-of-the-art AI systems are capable of vastly outperforming both
human and other data mining approaches in identifying minute patterns in very
large data sets, their conclusions are vulnerable to data inconsistencies,
poor data quality, and the uncertainty inherent to any data. This uncertainty,
together with engineering constraints on implementation and systems
integration, leads to inevitable and unavoidable errors.

Consequences of error resulting from AI range from minor inconveniences to
safety-critical risks: incorrect cancer treatment options by IBM Watson and
several Tesla and Uber crashes in 2018 are a few examples of the latter.
However the solution to ameliorating or eliminating errors is non-trivial. The
field of Software Engineering has provided numerous approaches for
understanding the behaviours and misbehaviours of software based systems
ranging from efficient scenario based testing techniques through to formal
verification—see for instance [14]. However these software architectures
typically do not contain the inherent uncertainties of data driven AI—although
this is rapidly changing with the push towards higher levels of driver assist
and autonomy. Recent examples that consider autonomous vehicle control systems
that incorporating AI include [22] and [24], although common to these
approaches is to look at systems level behaviours rather than the correctness
of the AI component.

Whilst structuring data, improving the quality of data, and removing
uncertainty is known to improve quality, it is too resource intensive in the
general case and thus unsustainable across sectors and industries. Moreover,
whilst it may improve the quality of high-assurance or safety-critical
systems, it does not provide a measure of understanding of quality and
consistency of output. More fundamentally, constraints on implementations such
as quantization errors and memory limits present challenges to AI performance
in resource constrained embedded settings—referred to as “at the edge”.

###  1.1 Background and related work

Significant efforts have been applied to address errors in AI systems. Using
ensembles [15], [16], [17], augmenting training data [20], [25], [27],
enforcing continuity [38], and AI knowledge transfer [26], [3], [36] have been
extensively discussed in the literature. These measures, however, do not
warrant error-free behaviour as AIs based on empirical data are expected to
make mistakes.

Recently in [7], [4], [34], [8], [9], [33] we have shown that spurious errors
of AI systems operating in high-dimensional spaces (convolutional and deep
learning neural networks being the canonical examples) can be efficiently
removed by Fisher discriminants. The advantage of this approach over, for
instance, Support Vector Machines (SVM) [35] is that the computational
complexity for constructing Fisher discriminants is at most linear in the
number of points in the training set whereas the worst-case complexity for SVM
scales as a cubic function of the training set size [2].

This method is applicable to identified singular spurious errors as well as to
moderate-sized clusters. The question then naturally arises as to what happens
if the volume of errors produced is similar to the volume of correct
responses? Moreover, if it is possible for a deployed AI to keep improving its
performance with limited resources available for supervision and re-training?
Both of these questions are fundamentally relevant across the spectrum of AI
applications. Notably, given the computational complexity properties that they
enjoy, they are particularly acute for embedded and resource-constrained
systems often referred to as “at the edge”.

###  1.2 Contribution and structure of this paper

In this paper we show that stochastic separation theorems, or the blessing of
dimensionality [5], [19], stemming from the concentration of measure effects
[6], [18], [13], can be adapted and applied to address these questions. We
present and justify both mathematically and experimentally an algorithm
capable of delivering the removal of errors at computational costs compatible
with deployment at the edge. The algorithm has both supervised and
unsupervised components which enables it to adapt to data without additional
supervisory inputs. As compared to previously proposed stochastic separation-
based algorithms [34], [33], current algorithm was shown to consistently learn
from large volumes of errors making its deployment in applications with
uncertainty and bias in training data particularly attractive.

The paper is organized as follows. Section 2 sets out the notation we use in
this paper. Section 3 contains necessary theoretical preliminaries and formal
statement of the problem. In Section 4 we present a new algorithm for
improving AIs “at the edge”. Section 5 illustrates an application of the
proposed algorithms in two industrial applications: product quality prediction
in milling machines and automated edge-based object detection in large-scale
survaliance systems; Section 6 concludes the paper.

##  2 Notation

The following notational agreements are used throughout the text:

  * 1.

$\mathbb{R}^{n}$ stands for the $n$-dimensional linear real vector space, and
$\mathbb{R}_{\geq 0}=\\{x\in\mathbb{R}|\ x\geq 0\\}$;

  * 2.

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

  * 3.

symbols $\boldsymbol{x}=(x_{1},\dots,x_{n})$ will denote elements of
$\mathbb{R}^{n}$;

  * 4.

$(\boldsymbol{x},\boldsymbol{y})=\sum_{k}x_{k}y_{k}$ is the inner product of
$\boldsymbol{x}$ and $\boldsymbol{y}$, and
$\|\boldsymbol{x}\|=\sqrt{(\boldsymbol{x},\boldsymbol{x})}$ is the standard
Euclidean norm in $\mathbb{R}^{n}$;

  * 5.

$\mathbb{B}_{n}(r,\boldsymbol{y})$ stands for the ball in $\mathbb{R}^{n}$ of
radius $r$ centered at $\boldsymbol{y}$ :
$\mathbb{B}_{n}(r,\boldsymbol{y})=\\{\boldsymbol{x}\in\mathbb{R}^{n}|\
\left(\boldsymbol{x}-\boldsymbol{y},\boldsymbol{x}-\boldsymbol{y}\right)\leq
r^{2}\\}$;

  * 6.

$\mathbb{B}_{n}$ denotes for the unit ball in $\mathbb{R}^{n}$ centered at the
origin: $\mathbb{B}_{n}=\\{\boldsymbol{x}\in\mathbb{R}^{n}|\
\left(\boldsymbol{x},\boldsymbol{x}\right)\leq 1\\}$;

  * 7.

$V_{n}$ is the $n$-dimensional Lebesgue measure, and $V_{n}(\mathbb{B}_{n})$
is the volume of unit ball;

  * 8.

if $\mathcal{Y}$ is a finite set then the number of elements in $\mathcal{Y}$
(cardinality of $\mathcal{Y}$) is denoted by $|\mathcal{Y}|$.

##  3 Problem Formulation and Mathematical Preliminaries

###  3.1 Problem formulation

Following [9], we consider a generic AI system that processes some input
signals, produces internal representations of the input and returns some
outputs. We assume that there is a sampling process whereby some relevant
information about the input, internal signals, and outputs are combined into a
common vector, $\boldsymbol{x}$, representing, but not necessarily defining,
the state of the AI system.

Depending on the sampling process, the vector $\boldsymbol{x}$ may have
various numbers of elements. But generally, the objects $\boldsymbol{x}$ are
assumed to be elements of $\mathbb{R}^{n}$, with $n$ depending on the sampling
process. Over a period of activity the AI system generates a set
$\mathcal{X}=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ of
representations $\boldsymbol{x}$. In agreement with standard assumptions in
machine learning literature [35], we assume that the set $\mathcal{X}$ is is a
random sample drawn from some distribution. The distribution that generates
vectors $\boldsymbol{x}$ is supposed to be unknown. We will, however, impose
some mild technical assumption on the generating probability distribution.

The central question we would like to address here is how to create algorithms
capable of producing a single or an esemple of linear functionals suitable for
decision-making at-the-edge. The focus on linear functionals is motivated by
computational efficiency of their implementation in embedded settings. We
would like to avoid using the framework of Support Vector Machines due to the
computational costs involved which may present an obstable for embedded
deployment.

###### Assumption 1

The probability density function, $p$, associated with the probability
distribution of the random variable $\boldsymbol{x}$ exists, is defined on the
unit ball $\mathbb{B}_{n}$, and there exist $C>0$ and $r\in(0,2)$ such that

$\int_{\mathbb{B}_{n}(1/2,\boldsymbol{z})}p(\boldsymbol{x})d\boldsymbol{x}\leq
C\left(\frac{r}{2}\right)^{n}\ \mbox{for all}\
\boldsymbol{z}\in\mathbb{B}_{n},\ \|\boldsymbol{z}\|=1/2.$ (1)

The assumption requires that the random variable $\boldsymbol{x}$ is in
$\mathbb{B}_{n}$ which is consistent with the scope of our applications. The
other part of the assumption, condition (1), is a version of the Smeared
Absolute Continuity (SmAC) property introduced in [8], [10]. Awareness of the
latter property will be important for the algorithms that follow. In addition
to Assumption 1 it will be convenient to consider alternative specifications
of the data probability distribution which are captured in Assumption 2 below.

###### Assumption 2

The probability density function, $p$, associated with the probability
distribution of the random variable $\boldsymbol{x}$ exists, is defined on the
unit ball $\mathbb{B}_{n}$, and there exist $C>0$ and $r\in\mathbb{R}_{\geq
0}$ such that

$p(\boldsymbol{x})<\frac{Cr^{n}}{V_{n}(\mathbb{B}_{n})},$ (2)

for all $\boldsymbol{x}\in\mathbb{B}_{n}$.

Note that if Assumption 2 holds with $r\in(0,2)$ then it automatically implies
that Assumption 1 holds true too. In case of Assumption 2 we do not wish yet
to specify exact values of $C$ and $r$. We would, however, like to formalise a
particularly useful form of its dependence on dimension $n$ and the volume of
the unit ball $\mathbb{B}_{n}$ captured by (2).

###### Definition 1

A point $\boldsymbol{x}\in\mathbb{R}^{n}$ is linearly separable from a set
$\mathcal{Y}\subset\mathbb{R}^{n}$, if there exists a linear functional
$l(\cdot)$ such that

$l(\boldsymbol{x})>l(\boldsymbol{y})$

for all $\boldsymbol{y}\in\mathcal{Y}$.

###### Definition 2

A set $\mathcal{X}\subset\mathbb{R}^{n}$ is linearly separable from a set
$\mathcal{Y}\subset\mathbb{R}^{n}$, if there exists a linear functional
$l(\cdot)$ such that

$l(\boldsymbol{x})>l(\boldsymbol{y})$

for all $\boldsymbol{y}\in\mathcal{Y}$ and $\boldsymbol{x}\in\mathcal{X}$.

In addition to these standard notions of linear separability, we adopt the
notion of Fisher separability [8], [10]. Observe that the classical Fisher
separability requires Maholonoibs inner product or whitening.

###### Definition 3

A point $\boldsymbol{x}\in\mathbb{R}^{n}$ is Fisher separable from a set
$\mathcal{Y}\subset\mathbb{R}^{n}$, if

$(\boldsymbol{x},\boldsymbol{x})>(\boldsymbol{x},\boldsymbol{y})$ (3)

for all $\boldsymbol{y}\in\mathcal{Y}$. The point is Fisher separable from the
set $\mathcal{Y}$ with a threshold $\kappa\in[0,1)$ if

$(\boldsymbol{x},\boldsymbol{x})>\kappa(\boldsymbol{x},\boldsymbol{y})$ (4)

Having introduced all relevant assumptions and notions, we are now ready to
proceed with results underpinning our algorithmic developments.

###  3.2 Mathematical Preliminaries

Our first result is provided in Theorem 1 (cf. [11], [8])

###### Theorem 1

Let $\mathcal{X}=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ be given,
$\boldsymbol{x}_{i}\in\mathbb{B}_{n}$, and let $\boldsymbol{x}$ be drawn from
a distribution satisfying Assumption 1. Then $\boldsymbol{x}$ is Fisher
separable from the set $\mathcal{X}$ with probability

$P\geq 1-MC\left(\frac{r}{2}\right)^{n},\ r\in(0,2).$ (5)

Proof of Theorem 1. Consider events

$A_{i}:\ \boldsymbol{x}\ \mbox{is Fisher separable from}\ \boldsymbol{x}_{i}.$

According to Definition 3, this is equivalent to that
$(\boldsymbol{x},\boldsymbol{x})-(\boldsymbol{x},\boldsymbol{x}_{i})>0$.
Therefore

$P(\mbox{not}\
A_{i})=\int_{(\boldsymbol{x},\boldsymbol{x})-(\boldsymbol{x},\boldsymbol{x}_{i})\leq
0}p(\boldsymbol{x})d\boldsymbol{x}.$

According to the De Morgan’s law,

${\bigwedge_{i=1}^{M}A_{i}}=\mbox{not}\ \left({\bigvee_{i=1}^{M}(\mbox{not}\
{A_{i}})}\right).$

Hence

$P(A_{1}\land A_{2}\land\cdots\land A_{M})=1-P((\mbox{not}\
A_{1})\lor(\mbox{not}\ A_{2})\lor\cdots(\mbox{not}\ A_{M})),$

and consequently

$P(A_{1}\land A_{2}\land\cdots\land A_{M})\geq 1-\sum_{i=1}^{M}P(\mbox{not}\
A_{i}).$ (6)

Consider the set

$\Omega_{i}=\\{\boldsymbol{x}\in\mathbb{B}_{n}\
|(\boldsymbol{x},\boldsymbol{x})-(\boldsymbol{x},\boldsymbol{x}_{i})\leq
0\\}=\mathbb{B}_{n}(\|\boldsymbol{x}_{i}\|/2,\boldsymbol{x}_{i}/2).$

Since $\boldsymbol{x}_{i}\in\mathbb{B}_{n}$, it follows that
$\Omega_{i}\subseteq\mathbb{B}_{n}(1/2,\boldsymbol{x}_{i}/2)$. This and
Assumption 1 imply that

$\int_{(\boldsymbol{x},\boldsymbol{x})-(\boldsymbol{x},\boldsymbol{x}_{i})\leq
0}p(\boldsymbol{x})d\boldsymbol{x}\leq\int_{\mathbb{B}_{n}(1/2,\boldsymbol{x}_{i}/2)}p(\boldsymbol{x})d\boldsymbol{x}\leq
C\left(\frac{r}{2}\right)^{n}$ (7)

Combining (7) and (6) we can conclude that the probability that
$\boldsymbol{x}$ is separable from all $\boldsymbol{x}_{i}$ is bounded from
below by the expression in (5). $\square$

###### Remark 1

According to Theorem 1, a single-point set $\mathcal{Y}$ under some mild
hypotheses can be separated from $\mathcal{X}$ by a simple Fisher discriminant
with probability close to one. Denoting

$\delta=MC\left(\frac{r}{2}\right)^{n}$

one can conclude that $\mathcal{Y}$ is Fisher separable from a given set
$\mathcal{X}\subset\mathbb{B}_{n}$ with probability grater or equal to
$1-\delta$ if

$n\geq\frac{\log M+\log C-\log{\delta}}{\log 2-\log r}.$

For $M=10^{4}$, $C=10^{2}$, $\delta=10^{-3}$, and $r=1$, the above inequality
holds for all $n\geq 30$.

In practice, however, we may be interested in a situation when the set
$\mathcal{Y}$ contains several elements which may or may not have some
inherent clustering structure or concentrations. In what follows we derive a
generalization of Theorem 1 enabling us to formally address the latter case
too.

Consider two random sets
$\mathcal{X}=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ and
$\mathcal{Y}=\\{\boldsymbol{y}_{1},\dots,\boldsymbol{y}_{K}\\}$. Let there be
a process (e.g. a learning algorithm) which, for the given $\mathcal{X}$,
$\mathcal{Y}$ or their subsets, produces a classifier

$f(\cdot)=\sum_{i=1}^{d}\alpha_{i}(\boldsymbol{z}_{i},\cdot),\
\alpha_{j}\in\mathbb{R}.$

The vectors $\boldsymbol{z}_{i}$, $i=1,\dots,d$ are supposed to be known.
Furthermore, we suppose that the function $f$ is such that

$f(\boldsymbol{y}_{j})>\sum_{m,k=1}^{d}\alpha_{m}\alpha_{k}(\boldsymbol{z}_{m},\boldsymbol{z}_{k})$
(8)

for all $\boldsymbol{y}_{j}\in\mathcal{Y}$. In other words, if we denote
$\boldsymbol{w}=\sum_{i=1}^{d}\alpha_{i}\boldsymbol{z}_{i}$, the following
holds true:

$(\boldsymbol{w},\boldsymbol{w})<(\boldsymbol{w},\boldsymbol{y}_{i})\
\mbox{for all}\ i=1,\dots,K.$ (9)

Note that since the $\mathcal{Y},\mathcal{X}$ are random, it is natural to
expect that the vector $\boldsymbol{\alpha}=(\alpha_{1},\dots,\alpha_{d})$ is
also random. The following statement can now be formulated:

###### Theorem 2

Consider sets $\mathcal{X}=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$
and $\mathcal{Y}=\\{\boldsymbol{y}_{1},\dots,\boldsymbol{y}_{K}\\}$. Let
$p_{\alpha}(\boldsymbol{\alpha})$ be the probability density function
associated with the random vector $\boldsymbol{\alpha}$, and
$\boldsymbol{\alpha}$ satisfies condition (8) with probability $1$. Then the
set $\mathcal{X}$ is separable from the set $\mathcal{Y}$ with probability

$P\geq 1-\sum_{i=1}^{M}\int_{H(\boldsymbol{\alpha},\boldsymbol{x}_{i})\leq
0}p_{\alpha}(\boldsymbol{\alpha})d\boldsymbol{\alpha},$ (10)

where

$H(\boldsymbol{\alpha},\boldsymbol{x}_{i})=\sum_{k,m=1}^{d}\alpha_{k}\alpha_{m}(\boldsymbol{z}_{k},\boldsymbol{z}_{m})-\sum_{m=1}^{d}\alpha_{m}(\boldsymbol{z}_{m},\boldsymbol{x}_{i}).$

Proof of Theorem 2. Consider events

$A_{i}:\ (\boldsymbol{w},\boldsymbol{w})>(\boldsymbol{w},\boldsymbol{x}_{i}).$

Event $A_{i}$ is equivalent to that the inequality

$H(\boldsymbol{\alpha},\boldsymbol{x}_{i})=\left(\sum_{k=1}^{d}\alpha_{k}\boldsymbol{z}_{k},\sum_{k=m}^{d}\alpha_{m}\boldsymbol{z}_{m}\right)-\sum_{m=1}^{d}\alpha_{m}(\boldsymbol{z}_{m},\boldsymbol{x}_{i})>0$

holds true. According to (6), equation (10) is a lower bound for the
probability that all these events hold. Recall that vectors
$\boldsymbol{\alpha}$ satisfy (9), and hence

$\displaystyle\sum_{m=1}^{d}\alpha_{m}(\boldsymbol{z}_{m},\boldsymbol{x}_{i})=$
$\displaystyle(\boldsymbol{w},\boldsymbol{x}_{i})$
$\displaystyle<(\boldsymbol{w},\boldsymbol{y}_{j})=\sum_{m=1}^{d}\alpha_{m}(\boldsymbol{z}_{m},\boldsymbol{y}_{j})$

for all $\boldsymbol{x}_{i}\in\mathcal{X}$ and
$\boldsymbol{y}_{j}\in\mathcal{Y}$ with probability at least (10). The
statement now follows immediately from Definition 2. $\square$

###### Remark 2

Theorem 2 generalizes earlier $k$-tuple separation theorems [34] to a very
general class of practically relevant distributions. No independence
assumptions are imposed on the components of vectors $\boldsymbol{x}_{i}$ and
$\boldsymbol{y}_{i}$. We do, however, require that some information about
distribution of the classifier parameters, $\boldsymbol{\alpha}$, is
available.

Observe, for example, that if there exist $L>0$, $\lambda\in(0,1)$ and a
function $\beta:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{R}$ such that

$\int_{H(\boldsymbol{\alpha},\boldsymbol{y})\leq
0}p_{\alpha}(\boldsymbol{\alpha})d\boldsymbol{\alpha}\leq
L\lambda^{\beta(d,n)}$

for any $\boldsymbol{y}\in\mathbb{R}^{n}$ then (10) becomes

$P\geq 1-ML\lambda^{\beta(d,n)}.$

If $d=n$ and elements of the set $\mathcal{Y}$ are sufficiently strongly
correlated, then the above bound becomes similar to (5) from Theorem 1. The
latter provides a good approximation of the separability probability bound for
a simple separating function in which $\boldsymbol{w}$ is just a scaled
centroid of the set $\mathcal{Y}$.

Theorems 1 and 2 link dimensionality of the decision-making space with
opportunities for quick and fast learning by mere Fisher discriminants.
Before, however, moving on to the actual algorithms for either improving
legacy data-driven AI systems or generating new edge-based classifiers or
both, let us examine another useful property of data in high dimension. This
property is summarised in Theorem 3.

###### Theorem 3

Let $\mathcal{X}=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ be a
finite sample of elements $\boldsymbol{x}_{i}$ drawn identically and
independently from a distribution satisfying Assumption 2. Let
$\boldsymbol{y}$ be an element of $\mathbb{B}_{n}$.

Then

  * 1)

$\boldsymbol{y}$ is Fisher separable from the set $\mathcal{X}$ with
probability

$P\geq 1-MC\left((1-\|\boldsymbol{y}\|^{2})^{\frac{1}{2}}r\right)^{n}$

  * 2)

every $\boldsymbol{x}\in\mathcal{X}$ is Fisher separable from $\boldsymbol{y}$
with probability

$P\geq 1-MC\left(\|\boldsymbol{y}\|r\right)^{n}.$

Proof of Theorem 3. Consider first statement 1) of the theorem. According to
Definition 3, the point $\boldsymbol{y}$ is Fisher separable from
$\mathcal{X}$ if

$\|y\|^{2}=(\boldsymbol{y},\boldsymbol{y})>(\boldsymbol{y},\boldsymbol{x})\
\forall\ \boldsymbol{x}\in\mathcal{X}$

Given that $\mathcal{X}\in\mathbb{B}_{n}$, this is equivalent to the fact that
no element of $\mathcal{X}$ belongs to the spherical cap

$\mathcal{C}_{n}(\boldsymbol{y})=\left\\{\boldsymbol{z}\in\mathbb{B}_{n}\ |\
\left(\frac{\boldsymbol{y}}{\|\boldsymbol{y}\|},\boldsymbol{z}\right)-\|\boldsymbol{y}\|\geq
0\right\\}.$

The probability that an $\boldsymbol{x}\in\mathcal{X}$ ends up in the cap is

$\int_{\mathcal{C}_{n}(\boldsymbol{y})}p(\boldsymbol{x})d\boldsymbol{x}\leq\int_{\mathbb{B}_{n}(\sqrt{1-\|\boldsymbol{y}\|^{2}},\boldsymbol{y})}p(\boldsymbol{x})d\boldsymbol{x}\leq\left((1-\|\boldsymbol{y}\|^{2})^{\frac{1}{2}}r\right)^{n}.$

Combining this with (6) gives the required bound.

Statement 2) follows from the observation that all
$\boldsymbol{x}\in\mathcal{X}$ that are outside of the ball
$\mathbb{B}_{n}(\|\boldsymbol{y}\|,0)$ are Fisher separable from
$\boldsymbol{y}$:

$\|\boldsymbol{x}\|>\|\boldsymbol{y}\|\Rightarrow(\boldsymbol{x},\boldsymbol{x})-(\boldsymbol{x},\boldsymbol{y})\geq\|\boldsymbol{x}\|\|\boldsymbol{y}\|-(\boldsymbol{x},\boldsymbol{y})>0.$

$\square$

Theorem 3 enables us to formulate a simple corollary revealing an interesting
dichotomy of datasets in high-dimensional spaces. More precisely

###### Corollary 1

Let $\mathcal{X}=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}\\}$ be a
finite sample of elements $\boldsymbol{x}_{i}$ drawn identically and
independently from a distribution satisfying Assumption 2 with $r<\sqrt{2}$.
Let $\boldsymbol{y}$ be an element of $\mathbb{B}_{n}$. Then, with probability

$P\geq 1-MC\left(\frac{r}{\sqrt{2}}\right)^{n},$

either

  * 1)

$\boldsymbol{y}$ is Fisher separable from $\mathcal{X}$

or

  * 2)

every $\boldsymbol{x}\in\mathcal{X}$ is Fisher separable from $\boldsymbol{y}$
and $\boldsymbol{y}$ is inside the ball $\mathbb{B}_{n}(1/\sqrt{2},0)$.

Proof of Corollary 1. Let $\boldsymbol{y}$ be an arbitrary element of
$\mathbb{B}_{n}$. Then either
$1-\|\boldsymbol{y}\|^{2}\leq\|\boldsymbol{y}\|^{2}$ or
$1-\|\boldsymbol{y}\|^{2}>\|\boldsymbol{y}\|^{2}$. If the first alternative
holds true then $1-\|\boldsymbol{y}\|^{2}\leq 1/2$ and statement 1) follows
from Theorem 3, alternative 1. If the opposite holds true then statement 2)
follows from Theorem 3, alternative 2. $\square$

Corollary 1 formalizes an interesting dichotomy of high-dimensional data: for
sufficiently large dimension $n$, a finite sample $\mathcal{X}$ drawn from a
class of distributions (Assumption 2 with $r<\sqrt{2}$ and suitable $C$), with
probability close to $1$, a given point in $\mathbb{B}_{n}$ (regardless of a
distribution it has been drawn from) is either inside the ball
$\mathbb{B}_{n}(1/\sqrt{2},0)$ or it is Fisher-separable from the sample
$\mathcal{X}$.

We will exploit this and other relevant properties formulated in Theorems 1 \-
3 in the next section.

##  4 Fast removal of AI errors

Consider two finite sets, the set $\mathcal{X}\subset\mathbb{R}^{n}$, and
$\mathcal{Y}\subset\mathbb{R}^{n}$. The task is to efficiently construct a
classifier separating the set $\mathcal{X}$ from $\mathcal{Y}$.

According to theoretical constructions presented in the previous section, the
following is an advantage for successful and efficient separation of random
sets in high dimension: one of the sets (set $\mathcal{Y}$) should be
sufficiently concentrated (spatially localized and have an exponentially
smaller volume relative to the other [Theorems 1, 2]). If this is the case
then, successful separability of this set of smaller volume depends on absence
of unexpected concentrations in the probability distributions. Importantly,
the probability of success approaches one exponentially fast, as a function of
the data dimensionality.

In practice, however, the assumption that one of the sets is spatially
localized in a small volume is too restrictive. To overcome this issue, we
propose to partition/cluster the set $\mathcal{Y}$ into a union of spatially
localized subsets. Presence of local concentrations and separability issues
have been linked and analyzed in [11], [8], [1]. The proposed clustering of
the set $\mathcal{Y}$ aims at addressing these issues too.

Below we present an algorithm for fast and efficient error correction of AI
systems which is motivated by these observations and intuition stemming from
our theoretical results.

###### Algorithm 1

($1-nn$ removal of AI errors. Training). Input: sets $\mathcal{X}$,
$\mathcal{Y}$, the number of clusters, $k$, threshold, $\theta$ (or thresholds
$\theta_{1},\dots,\theta_{k}$).

  1. 1.

Determining the centroid $\bar{\boldsymbol{x}}$ of the $\mathcal{X}$. Generate
two sets, $\mathcal{X}_{c}$, the centralized set $\mathcal{X}$, and
$\mathcal{Y}^{\ast}$, the set obtained from $\mathcal{Y}$ by subtracting
$\bar{\boldsymbol{x}}$ from each of its elements.

  2. 2.

Construct Principal Components for the centralized set $\mathcal{X}_{c}$.

  3. 3.

Using Kaiser, broken stick, conditioning rule, or otherwise, select $m\leq n$
Principal Components, $h_{1},\dots,h_{m}$, corresponding to the first largest
eivenvalues $\lambda_{1}\geq\cdots\geq\lambda_{m}>0$ of the covariance matrix
of the set $\mathcal{X}_{c}$, and project the centralized set
$\mathcal{X}_{c}$ as well as $\mathcal{Y}^{\ast}$ onto these vectors. The
operation returns sets $\mathcal{X}_{r}$ and $\mathcal{Y}_{r}^{\ast}$,
respectively:

$\displaystyle\mathcal{X}_{r}$
$\displaystyle=\\{\boldsymbol{x}|\boldsymbol{x}=H\boldsymbol{z},\
\boldsymbol{z}\in\mathcal{X}_{c}\\}$ $\displaystyle\mathcal{Y}_{r}^{\ast}$
$\displaystyle=\\{\boldsymbol{y}|\boldsymbol{y}=H\boldsymbol{z},\
\boldsymbol{z}\in\mathcal{Y}^{\ast}\\},\
H=\left(\begin{array}[]{c}h_{1}^{T}\\\ \vdots\\\ h_{m}^{T}\end{array}\right).$

  4. 4.

Construct matrix $W$

$W=\mathrm{diag}\left(\frac{1}{\sqrt{\lambda_{1}}},\dots,\frac{1}{\sqrt{\lambda_{m}}}\right)$

corresponding to the whitening transformation for the set $\mathcal{X}_{r}$.
Apply the whitening transformation to sets $\mathcal{X}_{r}$ and
$\mathcal{Y}_{r}^{\ast}$. This returns sets $\mathcal{X}_{w}$ and
$\mathcal{Y}_{w}^{\ast}$:

$\displaystyle\mathcal{X}_{w}$
$\displaystyle=\\{\boldsymbol{x}|\boldsymbol{x}=W\boldsymbol{z},\
\boldsymbol{z}\in\mathcal{X}_{r}\\}$ $\displaystyle\mathcal{Y}_{w}^{\ast}$
$\displaystyle=\\{\boldsymbol{y}|\boldsymbol{y}=W\boldsymbol{z},\
\boldsymbol{z}\in\mathcal{Y}_{r}^{\ast}\\}.$

  5. 5.

Cluster the set $\mathcal{Y}_{w}^{\ast}$ into $k$ clusters
$\mathcal{Y}_{w,1}^{\ast},\dots,\mathcal{Y}_{w,k}^{\ast}$ . Let
$\bar{\boldsymbol{y}}_{1},\dots,\bar{\boldsymbol{y}}_{k}$ be their
corresponding centroids.

  6. 6.

For each pair $(\mathcal{X}_{w},\mathcal{Y}_{w,i}^{\ast})$, $i=1,\dots,k$,
construct (normalized) Fisher discriminants
$\boldsymbol{w}_{1},\dots,\boldsymbol{w}_{k}$:

$\boldsymbol{w}_{i}=-\frac{(\mathrm{Cov}(\mathcal{X}_{w})+\mathrm{Cov}(\mathcal{Y}_{w,i}^{\ast}))^{-1}\bar{\boldsymbol{y}}_{i}}{\|(\mathrm{Cov}(\mathcal{X}_{w})+\mathrm{Cov}(\mathcal{Y}_{w,i}^{\ast}))^{-1}\bar{\boldsymbol{y}}_{i}\|}.$

An element $\boldsymbol{z}$ is associated with the set
$\mathcal{Y}_{w,i}^{\ast}$ if $(\boldsymbol{w}_{i},\boldsymbol{z})<\theta$ and
with the set $\mathcal{X}_{w}$ if
$(\boldsymbol{w}_{r},\boldsymbol{z})\geq\theta$.

If multiple thresholds are given then an element $\boldsymbol{z}$ is
associated with the set $\mathcal{Y}_{w,i}^{\ast}$ if
$(\boldsymbol{w}_{i},\boldsymbol{z})<\theta_{i}$ and with the set
$\mathcal{X}_{w}$ if $(\boldsymbol{w}_{r},\boldsymbol{z})\geq\theta_{i}$.

Output: vectors $\boldsymbol{w}_{i}$, $i=1,\dots,k$, matrices $H$ and $W$.

The deployment/application part of the algorithm is as follows:

###### Algorithm 2

($1-nn$ removal of AI errors. Deployment). Input: a data vector
$\boldsymbol{x}$, the set’s $\mathcal{X}$ centroid vector
$\bar{\boldsymbol{x}}$, matrices $H$, $W$, the number of clusters, $k$,
cluster centroids $\bar{\boldsymbol{y}}_{1},\dots,\bar{\boldsymbol{y}}_{k}$,
threshold, $\theta$ (or thresholds $\theta_{1},\dots,\theta_{k}$),
discriminant vectors, $\boldsymbol{w}_{i}$, $i=1,\dots,k$.

  1. 1.

Compute

$\boldsymbol{x}_{w}=WH(\boldsymbol{x}-\bar{\boldsymbol{x}})$

  2. 2.

Determine

$\ell=\arg\min_{i}\|\boldsymbol{x}_{w}-\bar{\boldsymbol{y}}_{i}\|.$

  3. 3.

Associate the vector $\boldsymbol{x}$ with the set $\mathcal{Y}$ if
$(\boldsymbol{w}_{\ell},\boldsymbol{x}_{w})<\theta$ and with the set
$\mathcal{X}$ otherwise.

If multiple thresholds are given then associate the vector $\boldsymbol{x}$
with the set $\mathcal{Y}$ if
$(\boldsymbol{w}_{\ell},\boldsymbol{x}_{w})<\theta_{\ell}$ and with the set
$\mathcal{X}$ otherwise.

Output: a label attributed to the vector $\boldsymbol{x}$.

In contrast to previously proposed approaches using stochastic separation
effects [34], Algorithm 2 mitigates the presence of clusters whose centroids
are close to the origin. If such clusters do occur and the fraction of the set
$\mathcal{X}$ located in their vicinity is not overwhelmingly large (which is
ensured by Theorem 3 and Corollary 1) then, at the stage of deployment, the
corresponding correcting discriminants will be triggered by elements from
$\mathcal{X}$ infrequently.

###### Remark 3

According to Theorem 1, a single-point set $\mathcal{Y}$ under some mild
hypotheses would be separated from $\mathcal{X}$ with probability close to
one.

If the set $\mathcal{Y}$ consists of multiple correlated subsets then, as the
number of clusters increases, one would expect that the algorithm’s
performance in separating the sets $\mathcal{X}$, $\mathcal{Y}$ improves.

At the same time, one may not necessarily require a near-perfect separability.
For example, removal of $90\%$ of all errors at the cost of a slight
performance degradation of the AI’s basic functionality may be an acceptable
compromise in many applications. If the data dimensionality is sufficiently
high then the desired separation might be achieved with just a single linear
functional, provided that the centroid $\bar{\boldsymbol{y}}$ of the set
$\mathcal{Y}$ is separated away from the centroid $\bar{\boldsymbol{x}}$ of
the set $\mathcal{X}$.

The rationale behind this observation is as follows. Let $\mathcal{X}$ be
equidistributed in $\mathbb{B}_{n}$ and $\mathcal{Y}$ be drawn from another
equidistribution in a unit $n$-ball but centered at a point whose Euclidean
norm is $0<\varepsilon\ll 1$ (see Fig. 1). Let
$\boldsymbol{w}=(\bar{\boldsymbol{x}}-\bar{\boldsymbol{y}})/\|\bar{\boldsymbol{x}}-\bar{\boldsymbol{y}}\|=-\varepsilon^{-1}\bar{\boldsymbol{y}}$.
Let $\kappa\in(0,1)$, and let
$h(\boldsymbol{x})=(\boldsymbol{x},\boldsymbol{w})+\kappa\varepsilon$ be the
separating hyperplane so that if $h(\boldsymbol{z})>0$ then the vector
$\boldsymbol{z}$ is associated with $\mathcal{X}$, and $\boldsymbol{z}$ is
associated with the set $\mathcal{Y}$ if $h(\boldsymbol{z})\leq 0$. Then the
fraction of elements from $\mathcal{X}$ “missed” (false negative response) by
this rule is bounded from above by

$\rho_{x}=\left(1-\kappa^{2}{\varepsilon}^{2}\right)^{\frac{n}{2}},$

and the fraction of elements from $\mathcal{Y}$ incorrectly attributed to
$\mathcal{X}$ (false positive response) is bounded from above by

$\rho_{y}=\left(1-(1-\kappa)^{2}{\varepsilon}^{2}\right)^{\frac{n}{2}}.$

Hence, when $n$ is sufficiently large, both $\rho_{x}$, $\rho_{y}$ may be made
acceptably small even if $\varepsilon$ is small too (cf [12]).

Figure 1: Separation of a non-isolated set $\mathcal{Y}$ from $\mathcal{X}$.
Black circle represents the set $\mathcal{X}$, red circle represents the set
$\mathcal{Y}$. Filled disks represent centres of the sets $\mathcal{X}$ and
$\mathcal{Y}$, respectively. Left panel. Single-cluster case. Right panel.
Multiple-cluster case. According to Theorem 3, the classes are “hollow” inside
if Assumption 2 with appropriate parameters holds for their corresponding
distributions.

###### Remark 4

Note that if the clustering step in Algorithm 1 is performed so that, for
every $i$

$\boldsymbol{z}\in\mathcal{Y}_{w,i}^{\ast}\Rightarrow\|\boldsymbol{z}-\bar{\boldsymbol{y}}_{i}\|<\|\boldsymbol{z}-\bar{\boldsymbol{y}}_{j}\|,\
\mbox{for all}\ j\neq i$

then the proposed 1-nn integration logic, as in Algorithm 2, correctly assigns
elements from $\mathcal{Y}$ to their corresponding discriminants
$\boldsymbol{w}_{i}$. For each query point, only one of the linear
discriminants is active. This is markedly different from the more aggressive
“union” integration logic (OR rule) proposed in [33] in which, for a single
query point, all discriminants are active simultaneously leading to higher
chances of producing false negative errors. In this respect, the 1-nn rule is
somewhat tighter than the OR rule.

###### Remark 5

It may sometimes be computationally advantageous to perform the clustering
step in Algorithm 1 (step 5) prior to dimensionality reduction. This will
result in that the deployment part of the algorithm, Algorithm 2 changes as
follows

###### Algorithm 3

($1-nn$ removal of AI errors. Deployment) Input: a data vector
$\boldsymbol{x}$, the set’s $\mathcal{X}$ centroid vector
$\bar{\boldsymbol{x}}$, matrices $H$, $W$, the number of clusters, $k$,
cluster centroids $\bar{\boldsymbol{y}}_{1},\dots,\bar{\boldsymbol{y}}_{k}$,
threshold, $\theta$ (or thresholds $\theta_{1},\dots,\theta_{k}$),
discriminant vectors, $\boldsymbol{w}_{i}$, $i=1,\dots,k$.

Pre-compute vectors

$\boldsymbol{w}^{\ast}_{i}=H^{T}W\boldsymbol{w}_{i}.$

  1. 1.

Determine

$\ell=\arg\min_{i}\|\boldsymbol{x}-\bar{\boldsymbol{x}}-\bar{\boldsymbol{y}}_{i}\|.$

  2. 2.

Associate the vector $\boldsymbol{x}$ with the set $\mathcal{Y}$ if
$(\boldsymbol{w}_{\ell}^{\ast},(\boldsymbol{x}-\bar{\boldsymbol{x}}))<\theta$
and with the set $\mathcal{X}$ otherwise.

If multiple thresholds are given then associate the vector $\boldsymbol{x}$
with the set $\mathcal{Y}$ if
$(\boldsymbol{w}_{\ell}^{\ast},(\boldsymbol{x}-\bar{\boldsymbol{x}}))<\theta_{\ell}$
and with the set $\mathcal{X}$ otherwise.

The difference between Algorithm 2 and 3 is that the data point
$\boldsymbol{x}$ no longer needs to be projected onto the principal
components. This may be computationally advantageous when the number of
components on which the data is projected is larger than the number of
clusters $k$.

Next section illustrates application of the algorithms with in two practical
scenarios of edge-based AI deployment.

##  5 Examples

The choice of examples is motivated primarily by our intention to illustrate
the application of the new algorithm with and without clustering. The first
example illustrates how one can take advantage of high-dimensional data for
constructing a single discriminant. The second example enables us to show
advantages of clustering for a problem where the feature space is genuinely
high-dimensional and where the number of errors made by edge-based systems
necessitates automated and computationally efficient interventions to be
deployed at the edge.

###  5.1 Real-time Tool Wear and Product Quality Prediction for Computer
Numerical Controlled (CNC) Milling Machines

####  5.1.1 System overview and setup

Milling is a process of removing excess material by advancing a cutter into a
work piece. It is one of the most commonly used processes for machining
freeform surfaces and custom parts [21]. Quality of the final part depends on
on many factors including tool path, tool orientation, tool geometry, tool
wear and security of the part fixing. Here we focused on real-time prediction
of part quality from the measurements characterizing electrical and mechanical
state of the CNC machine.

To build a data-driven quality detector we used the CNC Milling Dataset from
the University of Michigan Smart Lab [31]. The dataset contains a series of
machining experiments run on 2” x 2” x 1.5” wax blocks. Machining data was
collected from a CNC machine for variations of tool condition, feed rate, and
clamping pressure. An example of a finished wax part with an ”S” shape - S for
smart manufacturing - carved into the top face is shown in Fig. 2.

Figure 2: An example of a part produced by the CNC milling machine [31].

Time series data from the machine was collected from $18$ experiments with a
sampling rate of $100$ ms, and each instantaneous measurement vector contained
$48$ attributes. The task was to predict the output quality of the part, as
confirmed by visual inspection, from the instantaneous measurements.

####  5.1.2 Automated Part Quality Prediction

In this problem, we used Algorithms 1, 2 with a single cluster. We also used a
slightly modified Step 3 in 1 in which we retained $21$ Principal Components:
from the $20$th to the $40$th. Note that we did not use the first $19$
components as in this particular problem inclusion of these components did
translate into noticeable changes of the model’s performance.

Training and validation datasets. To train the model we used $9$ experiments
(out of the total $18$) in which $5$ experiments corresponded to machining
with unworn tool and which passed a visual inspection (experiments $1$, $3$,
$4$,$5$,$11$) and $4$ experiments contained data corresponding to runs that
either did not finish or where the part did not pass visual inspection
(experiments $6$, $7$, $8$, $9$); $3$ experiments were used for testing
(experiments $2$ and $17$ corresponding to successful runs where parts passed
visual inspection, and experiment $10$ in which the part failed the
inspection).

Experiments and results. Each measurement in both training and testing
datasets have been labeled as “pass” or “fail” depending on whether the run
from which this measurement was taken passed the visual inspection (and hence
the point was labeled as a “pass”) or failed (resulting in the label “fail”).
Training of the model took $0.16$ to $0.2$ seconds on a core i7 laptop, and a
summary of the model performance is summarized in Fig. 3.

Figure 3: ROC curves for detecting a faulty run from a single measurement in a
run.

To better integrate the model’s decision and filter spurious errors we
averaged the model’s binary output (computed with the threshold of $-1.5$)
over a sliding window of $200$ measurements. The resulting value for each
window was recorded and shown as “Score” in Fig. 4. Outcomes of these
experiments on the entire training and test sets, where the data from several
runs was simply concatenated, are presented in Fig. 4.

Figure 4: Averaged prediction “Score” for training (top panel) and testing
runs (bottom panel). Green and black curves in the top panel show correct and
failed machining for the training set, respectively. Blue and red curves
correspond to correct and failed runs in the test set, respectively.

As one can see from these figures, the model correctly identifies failed runs.
Good generalization performance of this simple model can be explained by the
concentration effects captured in Fig. 1: relatively small differences of
class means are apparently sufficient to ensure reasonable class separation by
a Fisher discriminant if the data dimension is sufficiently large.

In addition to this, we notw that not every single dimension is equally
important either. To illustrate this point, let $\bar{\boldsymbol{x}}$ and
$\bar{\boldsymbol{y}}$ be empirical class means for the “pass” and “fail”
classes. We calculated

$\mbox{Relative
relevance}_{i}=\left|\frac{\bar{\boldsymbol{x}}-\bar{\boldsymbol{y}}}{\|\bar{\boldsymbol{x}}-\bar{\boldsymbol{y}}\|}\frac{h_{i}}{\|h_{i}|}\right|,\
i=20,\dots,40,$

where $h_{i}$ are the corresponding Principal Components (Algorithm 1). The
relative relevance indices for each $i$-th component and the contribution of
that component to the total empirical data variance are shown in Fig. 5.

Figure 5: Relative relevance of Principal Components for class discrimination.

As we can see from Fig. 5, a large proportion of principal components only
marginally project onto the vector $\bar{\boldsymbol{x}}-\bar{\boldsymbol{y}}$
which further contributes to separability.

###  5.2 Adaptive Removal of False Positives in Video Surveillance and
Analytics Systems: A Case Study

####  5.2.1 System overview and setup

All UK airports are expected to ensure that the average passenger spends no
longer than twelve minutes going through the security area.

The current boarding gates can measure the number of passengers coming through
the security area via passenger boarding passes. However there is no way of
determining whether an individual passenger has left the security area. The
current solution involves a member of staff manually keeping track of a small
sample of passengers passing from the boarding gates to the security scanners
and logging the time taken.

Knowledge about the length of these queues, as well as the number of
passengers getting through the airport, helps airports to manage their
resources in an efficient way by enabling them to decide how many security
stations should be open. It also provides passengers with valuable information
on the amount of time they can expect to spend inside the queues thereby
allowing them to manage their time inside the airport more efficiently. Thus,
knowing the time taken for a passenger since entering boarding-pass gates
until leaving security gates, in almost real time, would be very beneficial.
However, the current practices aimed at addressing this specific problem are
far from being efficient.

To address the efficiency issue, various Queue Management System (QMS) are
being developed. Here we provide a short description of a system which has
been developed by the Visual Management Systems Ltd within the scope of the
Innovate UK Knowledge Transfer Partnership project (KTP 10522).

The system consists of two major components: the hardware that is in charge of
detecting faces, and the back-end server that processes the data streamed from
the hardware unit and calculates the average, fastest and slowest security
queue times. A front-end web-page is served by the back-end to display the
aforementioned statistical data as well as producing historical reports. As
mentioned before, security queue time is the time a passenger spends in queues
for the Boarding Pass Gates (BPG) and Security Gates (SG).

For the hardware, shown in Figure 6, we utilise two (or more) high-definiton
cameras streaming in H.264, one for BPG and one for SG, connected to two
_Processing Modules TM_ (PM) via two mini PC’s.

Figure 6: Queue Management System

The function of the PMs is to detect and track faces from the video feeds and
output relevant metadata (face coordinates, time stamp, bitmap/image of the
face etc) to the processing server. The metadata are then received by the
back-end server for processing. The back-end includes four different sections;
parsing, image pre-processing, feature extraction and the data base. In the
parsing section, the encoded face bimap is extractedl together with all other
metadata. This is followed by the pre-processing unit in which each thumbnail
is encoded to JPG format and saved to the local hard disk before passing
through the Dlib library to generate a face score. Then, the thumbnail will
pass through a Convolutional Neural Network, e.g. VGG-16 [30], for feature
extraction. Finally, features of the thumbnail together with all related
metadata will be stored in the database.

The system has been trialled over a period of $3$ months in a major UK
airport. The trials revealed that, depending on operational conditions, PMs
based on propriertrary algorithms, occasionally return false positive detects
These false positive detects if left untreated, have a capacity to slow down
the entire processing pipeline. As the system scales up, dealing with these
false posiive detects on the side of the server becomes computationally
prohibitive. Moreover, the false positive detects, are camera and place-
specific, in general. Thus there is a need and a rationale to address these
false positive detects at their source.

####  5.2.2 Adaptive Removal of False Positives

In order to address the problem of false positives, we implemented and tested
the proposed algorithms in this setup. For the purposes of avoiding issues
with reproducibility as well as due to the data protection, in what follows we
present a detailed account of this implementation in which the PM was an
OpenCV implementation of the Haar face detector. The detector has been applied
to a publically accessible video footage capturing traffic and pedestrians
walking on the streets of Montreal. For the purposes of testing and
validation, we used the MTCNN face detector as a vehicle to generate ground
truth data. All the data as well as the code generating true positive and
false positive images can be provided by request.

For this particular dataset, the total number of true positives was $21896$,
and the total number of false positives was $9372$. All the detects have been
resized to $64\times 64$ crops (in RGB encoding). Each crop produces a
$12288$-dimensional vector. From this dataset, we generated a training set
containing $50$ percent of positive and false positives, and passed this
training set to Algorithm 1. In the algorithm, true positives have been
associated with the set $\mathcal{X}$, and false positives were associated
with the set $\mathcal{Y}_{\ast}$. The number of Principal Components was
limited to $200$. We tried the algorithm for the following numbers of
clusters: $1$, $5$,$10$, and $100$ . At the deployment stage, we used
Algorithm 2. Training took, on average, about $180$ seconds on a Core i7
laptop, and the outcomes of the process as well as performance on the testing
set are summarized in Fig. 7 where curves corresponding to different numbers
of clusters ($1$, $5$,$10$, and $100$) are annotated by arrows with numbers
$1$, $5$,$10$, and $100$, respectively.

Figure 7: ROC curves after the application of the AI error correcting
algorithm with 200 Pricipal Components

As we can see from this figure, even a single-cluster implementation of
Algorithm 1 allows one to filter 90 percent of all errors at the cost of
missing circa 5 percent of true positives. This is consistent with
expectations discussed in Remark 3. Implementation of the single-cluster
correcting functional on an ARM Cortex-A53 processor took less than 1
millisecond per each 12288-dimensional vector implying significant capacity of
the approach for embedded near-edge applications.

A notable classification performance gain is observed for a $100$-cluster
version of the algorithm. This, however, comes at additional computational
costs at the stage of deployment. Having said this, the deployment part of the
algorithm is extremely scalable leading to significant expected reductions of
computation times in the case of parallel execution of the code and is hence
amenable to massively parallel implementations.

It is also worthwhile to mention that the concentration effects, as formulated
in Theorems 1, 2, and which are at the backbone of Algorithms 1 – 3, may
negatively effect the overall system’s performance if the dimensionality is
excessively high and the cardinality of the set $\mathcal{Y}$ is comparable to
that of the set $\mathcal{X}$. To illustrate this point, we used Algorithms 1,
2 with the $6000$ Principal Components. Results are shown in Fig. 8

Figure 8: ROC curves after the application of the AI error correcting
algorithm with 6000 Principal Components. Blue curves correspond to the
baseline case with a single cluster. Red and green curves show behavior of the
system for $100$ clusters.

As we can see from this figure, if the retained dimensionality of the
decision-making space is too large, the algorithms tend to overfit and hence
special consideration needs to be given to the choice of the numbers of
projections used and the volume of training data.

##  6 Conclusion

In this work we presented a novel approach for equipping edge-based or near-
edge devices with capabilities to quickly learn on-the-job and continuously
improve over time in presence of spurious as well as a rather overwhelming
number of errors. The approach is based on stochastic separation theorems [4],
[7], [9], [34], [8], [33] and the concentration of measure phenomena.

Our results demonstrate that the new capability can be delivered to the edge
and deployed in a fully automated way, whereby a more sophisticated AI system
monitors performance of a less powerful counterpart. The approach, for the
first time uses $1-nn$ integration rule for error correction, as opposed to
mere disjunctions. The $1-nn$ rule is justified by the dichotomy of high-
dimensional datasets captured in Theorem 3 and Corollary 1. Experimentally, we
investigated the sensitivity of the algorithm to change of its meta-parameters
like the number of clusters and projections used. The results directly respond
to the fundamental challenge of removing AI errors in industrial applications
at minimal computational costs, and some elements of the theory already
underpin two US patents [29], [28].

Theoretical results are illustrated with two industrial applications:
performance monitoring of the CNC milling processes and edge-based object
detection. An application field of the approach could be the class of
randomized computational architectures such as stochastic configuration
networks [37], and in particular the employment of the measure concentration
effects for estimating their approximation convergence rates. This will be the
subject of our future work.

## Acknowledgment

The work was supported by Innovate UK Knowledge Transfer Partnership grant
KTP010522, by the grant of the Russian Science Foundation (Project No.
19-19-00566), and by a 111 Project (B16009).

## References

  * Albergante et al. [2019] A. Albergante, J. Bac, and A. Zinovyev.  Estimating the effective dimension of large biological datasets using fisher separability analysis.  In _Proc. of the International Joint Conference on Neural Networks (IJCNN)_ , 2019.
  * 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.  _International Conference on Learning Representations (ICLR) 2016_ , 2015.
  * Gorban and Tyukin [2017] A. Gorban and I. Tyukin.  Stochastic separation theorems.  _Neural Networks_ , 94:255–259, 2017.
  * Gorban and Tyukin [2018] A. Gorban and I. Tyukin.  Blessing of dimensionality: mathematical foundations of the statistical physics of data.  _Philosophical Transactions of the Royal Society A_ , 376:20170237, 2018.  doi: 10.1098/rsta.2017.0237.
  * Gorban et al. [2016a] A. Gorban, I. Tyukin, D. Prokhorov, and K. Sofeikov.  Approximation with random bases: Pro et contra.  _Information Sciences_ , 364–365:129–145, 2016a.
  * Gorban et al. [2016b] A. Gorban, I. Tyukin, and I. Romanenko.  The blessing of dimensionality: Separation theorems in the thermodynamic limit, 09 2016b.  URL https://arxiv.org/abs/1610.00494v1.  2nd IFAC Workshop on Thermodynamic Foundations of Mathematical Systems Theory. September 28-30, 2016, Vigo, Spain.
  * Gorban et al. [2018a] A. Gorban, A. Golubkov, B. Grechuk, E. Mirkes, and I. Tyukin.  Correction of ai systems by linear discriminants: Probabilistic foundations.  _Information Sciences_ , 466:303–322, 2018a.
  * Gorban et al. [2019] A. Gorban, R. Burton, I. Romanenko, and I. Tyukin.  One-trial correction of legacy AI systems and stochastic separation theorems.  _Information Sciences_ , 484:237–254, 2019.
  * Gorban et al. [2018b] A. N. Gorban, B. Grechuk, and I. Y. Tyukin.  Augmented artificial intelligence.  _arXiv preprint arXiv:1802.02172_ , 2018b.
  * Gorban et al. [2018c] A. N. Gorban, V. A. Makarov, and I. Y. Tyukin.  The unreasonable effectiveness of small neural ensembles in high-dimensional brain.  _Physics of Life Reviews_ , 2018c.  doi: 10.1016/j.plrev.2018.09.005.
  * Gorban et al. [2020] A. N. Gorban, V. Makarov, and I. Tyukin.  High-dimensional brain in a high-dimensional world: Blessing of dimensionality.  _Entropy_ , 22(1):82, 2020.
  * Gromov [2003] M. Gromov.  Isoperimetry of waists and concentration of maps.  _GAFA, Geomteric and Functional Analysis_ , 13:178–215, 2003.
  * Hains et al. [2018] G. Hains, A. Jakobsson, and Y. Khmelevsky.  Towards formal methods and software engineering for deep learning: Security, safety and productivity for dl systems development.  In _2018 Annual IEEE International Systems Conference (SysCon)_ , pages 1–5, April 2018.  doi: 10.1109/SYSCON.2018.8369576.
  * Hansen and Salamon [1990] L. K. Hansen and P. Salamon.  Neural network ensembles.  _IEEE Transactions on Pattern Analyis and Machince Intelligence_ , 12(10):993–1001, 1990.
  * Ho [1995] T. K. Ho.  Random decision forests.  In _Proc. of the 3rd International Conference on Document Analysis and Recognition_ , pages 993–1001, 1995.
  * Ho [1998] T. K. Ho.  The random subspace method for constructing decision forests.  _IEEE Transactions on Pattern Analyis and Machince Intelligence_ , 20(8):832–844, 1998.
  * Kainen and Kurkova [1993] P. Kainen and V. Kurkova.  Quasiorthogonal dimension of euclidian spaces.  _Appl. Math. Lett._ , 6(3):7–10, 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.
  * 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.
  * Lasemi et al. [2010] A. Lasemi, D. Xue, and P. Gu.  Recent development in cnc machining of freeform surfaces: A state-of-the-art review.  _Computer-Aided Design_ , 42(7):641–654, 2010\.
  * Li et al. [2018] N. Li, D. W. Oyler, M. Zhang, Y. Yildiz, I. Kolmanovsky, and A. R. Girard.  Game theoretic modeling of driver and vehicle interactions for verification and validation of autonomous vehicle control systems.  _IEEE Transactions on Control Systems Technology_ , 26(5):1782–1797, Sep. 2018.  doi: 10.1109/TCST.2017.2723574.
  * Liang et al. [2019] H. Liang, B. Tsui, H. Ni, C. Valentim, S. Baxter, G. Liu, W. Cai, D. Kermany, K. Sun, J. Chen, L. He, J. Zhu, P. Tian, H. Shao, L. Zheng, R. Hou, S. Hewett, G. Li, P. Liang, X. Zang, Z. Zhang, L. Pan, H. Cai, R. Ling, S. Li, Y. Cui, S. Tang, H. Ye, X. Huang, W. He, W. Liang, Q. Zhang, J. Jiang, W. Yu, J. Gao, W. Ou, Y. Deng, Q. Hou, B. Wang, C. Yao, Y. Liang, S. Zhang, Y. Duan, R. Zhang, S. Gibson, C. Zhang, O. Li, E. Zhang, G. Karin, N. Nguyen, X. Wu, C. Wen, J. Xu, W. Xu, B. Wang, W. Wang, J. Li, B. Pizzato, C. Bao, D. Xiang, W. He, S. He, Y. Zhou, W. Haw, M. Goldbaum, A. Tremoulet, C.-N. Hsu, H. Carter, L. Zhu, K. Zhang, and H. Xia.  Evaluation and accurate diagnoses of pediatric diseases using artificial intelligence.  _Nature Medicine_ , 25:433–438, 2019.  doi: https://doi.org/10.1038/s41591-018-0335-9.
  * Meltz and Guterman [2019] D. Meltz and H. Guterman.  Functional safety verification for autonomous ugvs—methodology presentation and implementation on a full-scale system.  _IEEE Transactions on Intelligent Vehicles_ , 4(3):472–485, Sep. 2019.  doi: 10.1109/TIV.2019.2919460.
  * 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 Systems_ , (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.
  * Romanenko et al. [2018] I. Romanenko, I. Tyukin, A. Gorban, and K. Sofeikov.  Method of image processing. US patent US10062013B2, August, 28 2018\.  URL https://patents.google.com/patent/US10062013B2/en.
  * Romanenko et al. [2019] I. Romanenko, A. Gorban, and I. Tyukin.  Image processing. US patent US10489634B2, November, 26 2019.  URL https://patents.google.com/patent/US20180089497A1/en.
  * Simonyan and Zisserman [2015] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  In _International Conference on Learning Representations_ , 2015.  arXiv:1409.1556.
  * Sun [2018] S. Sun.  CNC mill tool wear dataset, 2018.  URL https://www.kaggle.com/shasun/tool-wear-detection-in-cnc-mill.
  * Takács et al. [2018] A. Takács, I. Rudas, D. Bösl, and T. Haidegger.  Highly automated vehicles and self-driving cars [industry tutorial].  _IEEE Robotics Automation Magazine_ , 25(4):106–112, Dec 2018.  doi: 10.1109/MRA.2018.2874301.
  * Tyukin et al. [2019] I. Tyukin, A. Gorban, S. Green, and D. Prokhorov.  Fast construction of correcting ensembles for legacy artificial intelligence systems: Algorithms and a case study.  _Information Sciences_ , 485:230–247, 2019.
  * Tyukin et al. [2018] I. Y. Tyukin, A. N. Gorban, K. Sofeikov, and I. Romanenko.  Knowledge transfer between artificial intelligence systems.  _Frontiers of Neurorobotics_ , 12, Article 49, 2018.  doi: 10.3389/fnbot.2018.00049.
  * Vapnik [2000] V. Vapnik.  _The Nature of Statistical Learning Theory_.  Springer-Verlag, 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 Li [2017] D. Wang and M. Li.  Stochastic configuration networks: Fundamentals and algorithms.  _IEEE Transactions on Cybernetics_ , 47(10):3466–3479, 2017.
  * 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)_ , 2016.  https://arxiv.org/abs/1604.04326.


# An inductive proof of the Bollobás two family theorem

Sayan Goswami
<EMAIL_ADDRESS>
The Institute of Mathematical Sciences
A CI of Homi Bhabha National Institute
CIT Campus, Taramani, Chennai 600113, India

###### Abstract

Inspired by the inductive proof of the LYM-inequality given by P. Frankl in
[3], we provide an inductive proof of the Bollobás two family theorem [2].

Keywords: Bollobas two family theorem

The LYM inequality established by Lubell [4], Yamamoto [7] and Meshalkin [5]
is one of the fundamental result in combinatorics. One can find several proofs
of this result in literature. In [3], Frankl found an inductive proof of this
result that uses elementary probability theory. In [2], Bollobás found a
generalization of this inequality known as Bollobás theorem. The known proof
uses random permutation and independence of random variables. In [1], several
results can be found towards this direction. Inspired by [3], here we provide
a relatively elementary proof of Bollobás theorem that uses elementary
probability theory and induction argument.

######  Theorem 1.

(Bollobás two family theorem) If $m\in\mathbb{N}$ and
$\mathcal{F}_{1}=\left\\{A_{1},\ldots,A_{m}\right\\}$,
$\mathcal{F}_{2}=\left\\{B_{1},\ldots,B_{m}\right\\}$ be two family of sets
over $X=\left\\{1,2,\ldots,n\right\\}$ such that $A_{i}\cap B_{i}=\emptyset$
and $A_{i}\cap B_{j}\neq\emptyset$ for all
$i,j\in\left\\{1,2,\ldots,m\right\\}$, then
$\sum_{A_{i}\in\mathcal{F}_{1}}\frac{1}{\binom{|A_{i}|+|B_{i}|}{|A_{i}|}}\leq
1.$

###### Proof.

For $n=1$, the result is true. So assume that the result is true over any set
of cardinality $n-1.$ Let $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ be two given
families. For any $x\in X,$ choose
$\mathcal{G}_{1}\left(x\right)=\left\\{A_{i}\in\mathcal{F}_{1}:x\notin
A_{i}\,\text{and}\,x\in B_{i}\right\\}.$ Note that for every pair (except the
family $\mathcal{F}_{1}=\left\\{X\right\\}$ and
$\mathcal{F}_{2}=\left\\{\emptyset\right\\}$, where the result trivially true)
of $\left(A_{i},B_{i}\right)$ one such $x\in X$ exists, infact every $x\in
B_{i}$ will work. Now choose
$\mathcal{G}_{2}\left(x\right)=\left\\{B_{i}\setminus\left\\{x\right\\}:A_{i}\in\mathcal{G}_{1}\left(x\right)\right\\}.$
Then it can be easily checked that the elements of
$\mathcal{G}_{1}\left(x\right)$ and $\mathcal{G}_{2}\left(x\right)$ satisfies
the condition of the theorem over the set $X\setminus\left\\{x\right\\}.$ So
by induction

$1\geq\mathbb{E}\left(\sum_{A_{i}\in\mathcal{G}_{1}\left(x\right)}\frac{1}{\binom{|A_{i}|+|B_{i}|-1}{|A_{i}|}}\right)$
$\qquad\qquad=\sum_{A_{i}\in\mathcal{F}_{1}}\mathbb{P}\left(A_{i}\in\mathcal{G}_{1}\left(x\right)\right)\cdot\frac{1}{\binom{|A_{i}|+|B_{i}|-1}{|A_{i}|}}$
$\qquad\>\qquad\>\,\,\quad\;\>\>\,\,=\sum_{A_{i}\in\mathcal{F}_{1}}\mathbb{P}\left(x\in
B_{i}|x\in A_{i}\cup
B_{i}\right)\cdot\frac{1}{\binom{|A_{i}|+|B_{i}|-1}{|A_{i}|}}$
$\;\qquad=\sum_{A_{i}\in\mathcal{F}_{1}}\frac{|B_{i}|}{|A_{i}|+|B_{i}|}\cdot\frac{1}{\binom{|A_{i}|+|B_{i}|-1}{|A_{i}|}}$
$\qquad\qquad\quad=\sum_{A_{i}\in\mathcal{F}_{1}}\frac{|A_{i}|+|B_{i}|-|A_{i}|}{|A_{i}|+|B_{i}|}\cdot\frac{1}{\binom{|A_{i}|+|B_{i}|-1}{|A_{i}|}}$
$\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!=\sum_{A_{i}\in\mathcal{F}_{1}}\frac{1}{\binom{|A_{i}|+|B_{i}|}{|A_{i}|}}.$

This completes the proof. ∎

## References

  * [1] B. Bollobás, Combinatorics. Set systems, hypergraphs, families of vectors and combinatorial probability. Cambridge University Press, Cambridge, 1986.
  * [2] B. Bollobás, On generalized graph, Acta Math. Acad. Sci. Hungar. 16, 447-452, 1965.
  * [3] P. Frankl, A probabilistic proof for the lym-inequality, Dicrete Mathematics. Volume 43, Issues 2–3, 1983, Page 325.
  * [4] D. Lubell, A short proof of Sperner’s theorem, J. Cambin. Theory 1 (1966) 299.
  * [5] L.D. Meshalkin, A generalization of Sperner’s theorem on the number of subsets of a finite set, Theor. Probability Appl. 8 (1963) 203-204.
  * [6] E. Sperner, Ein Satz iiber Untermengen einer endlichen Menge, Math. Z. 27 (1928) 544-548.
  * [7] K. Yamamoto, Logarithmic order of free distributive lattices, J. Math. Sot. Japan 6 (1954) 343-353.