# Demystification of Few-shot and One-shot Learning
††thanks: The work was supported by the UKRI Alan Turing AI Acceleration
Fellowship grant EP/V025295/1 and by the grant of the Ministry of Science and
Higher Education of Russian Federation (Project No. 14.Y26.31.0022).

1st Ivan Y. Tyukin  School of Mathematics
and Actuarial Science
University of Leicester
and Norwegian University
of Science and Technology
and Saint-Petersburg State
Electrotechnical University

Leicester, United Kingdom
and Trondheim, Norway
and Saint-Petersburg, Russia
<EMAIL_ADDRESS>2nd Alexander N. Gorban  School of Mathematics
and Actuarial Science
University of Leicester
and Lobachevsky University

Leicester, United Kingdom
and Nizhny Novgorod, Russia
<EMAIL_ADDRESS>3rd Muhammad H. Alkhudaydi  School of Mathematics
and Actuarial Science
University of Leicester

Leicester, United Kingdom
<EMAIL_ADDRESS>4th Qinghua Zhou  School of Informatics
University of Leicester

Leicester, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

Few-shot and one-shot learning have been the subject of active and intensive
research in recent years, with mounting evidence pointing to successful
implementation and exploitation of few-shot learning algorithms in practice.
Classical statistical learning theories do not fully explain why few- or one-
shot learning is at all possible since traditional generalisation bounds
normally require large training and testing samples to be meaningful. This
sharply contrasts with numerous examples of successful one- and few-shot
learning systems and applications.

In this work we present mathematical foundations for a theory of one-shot and
few-shot learning and reveal conditions specifying when such learning schemes
are likely to succeed. Our theory is based on intrinsic properties of high-
dimensional spaces. We show that if the ambient or latent decision space of a
learning machine is sufficiently high-dimensional than a large class of
objects in this space can indeed be easily learned from few examples provided
that certain data non-concentration conditions are met.

###### Index Terms:

Few-shot learning, one-shot learning, generalisation, stochastic separation
theorems

## Notation

  * •

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

  * •

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

  * •

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

  * •

$(\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}$;

  * •

$\mathbb{B}_{n}$ denotes the unit ball in $\mathbb{R}^{n}$ centered at the
origin:

$\mathbb{B}_{n}=\\{\boldsymbol{x}\in\mathbb{R}^{n}|\ {\|\boldsymbol{x}\|\leq
1}\\};$

  * •

$\mathbb{B}_{n}(r,\boldsymbol{y})$ stands for the ball in $\mathbb{R}^{n}$ of
radius ${r>0}$ centered at $\boldsymbol{y}$:

$\mathbb{B}_{n}(r,\boldsymbol{y})=\\{\boldsymbol{x}\in\mathbb{R}^{n}|\
{\|\boldsymbol{x}-\boldsymbol{y}\|\leq r}\\};$

  * •

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

##  I Introduction

The fundamental question of learning from few examples is one of the
fascinating and central questions in both the theory and practice of modern
large-scale data-driven AI systems. These systems have many millions of
adjustable parameters [1], whose numbers often exceed those of the datasets
used in their training. And yet, performance of these large-scaled models
trained on modestly-sized datasets in practical tasks is remarkably good [2].

Classical generalisation bounds stemming from the Vapnik-Chervonenkis theory
[3] alone do not explain these successes due to their combinatorial and
extremely conservative nature. What is even more striking, as has been
demonstrated in [4], absolutely identical deep neural networks are capable of
exhibiting both sides of the learning spectrum: to successfully generalise
from meaningful training data and, at the same time, “memorise” random
assignments of labels without any generalisation. Results like these motivate
persistent ongoing inquiries into unreasonable effectiveness of modern deep
learning models [5].

The phenomenon of few-shot learning is perhaps one of the most acute
manifestations of this challenge. Various few-shot learning schemes and
empirically successful algorithms and models such as matching [6] and
prototypical networks [7] provide ample evidence that good generalisation may
indeed occur in extreme settings with just few elements in the training set.
The theory, however, which may explain why is this at all possible is lacking.

In this paper, we lay out mathematical foundations of such theory. We provide,
for the first time, formal statements of different versions of the problem of
few-shot learning and present solutions of these problems. These solutions are
remarkably consistent with heuristic algorithms described in the current
literature [6], [7]. At the core of our approach are stochastic separation
theorems [8], [9] linking high-dimensional geometry with the concentration of
measure. In this work, we make an additional departure from the classical
“fully agnostic” machine learning problem statement. In particular, we propose
that a mild hypothesis on “compactness” of an object’s/class’s representation
in the network’s latent space, expressed as existence of a finite sub-cover of
the object to be learned by $n$-balls not containing the origin, could hold
the key to understanding and resolving the challenge of generalisation, few-
shot, and single-shot learning.

The rest of the paper is organised as follows. In Section II we describe a
general setting of the problem of few-shot learning considered in the paper
and present its formal mathematical statements. Section III presents main
mathematical results and their discussion, and Section IV provides a brief
summary and conclusion.

##  II Problem formulation

###  II-A General setting

To set the scene for a more formal analysis, let us first outline key
components of few-shot learning. In many relevant few-shot learning cases one
would normally have an existing system with all its inputs, outputs, states
and dependencies (potentially unknown) between these. This existing system
would also operate in a specific regime (recognise a new person in a room,
learn a new gesture, fix an error) which can be termed as an operational
situation. Performance of the system in the task of learning in this situation
is then assessed by some evaluation procedure.

Complexity of all processes presented in this rather generic picture could be
extremely high. In modern large-scale AI and deep learning models, one of the
major contributors to this complexity is an inherently and irreducibly high
dimensionality of signals involved in the definition of the operational
situation at hand. Defining meaningful probability spaces for such data is not
a trivial task due to enormously large datasets required to gain appropriate
knowledge and intuition. At the same time, as we will show later, this high
dimensionality may hold the key to develop some understanding of the
phenomenon of few-shot learning.

In order to reveal the link between dimensionality of the appropriate data and
few-shot learning we will need to make some simplifying assumptions
constraining the general setting above. These assumptions, however, would
enable us to define the problem formally and focus on the most relevant
elements of the general problem which are important for this contribution. In
the next section we provide a formal, albeit simplified, description of the
problem (II-B), formalise the problem of few-shot learning (II-C), and list
some specific technical assumptions (II-D).

###  II-B Background

Let $\mathcal{U}$, $\mathcal{U}\subset\mathbb{R}^{d}$ be the set of inputs
modeling or representing objects of interests such as images, pieces of sound,
or records in a database, and let $\mathcal{L}$ be the set of labels.
Following classical statistical learning settings [10], [3], we suppose that
for each element $\boldsymbol{u}\in\mathcal{U}$ there is an associated label
$\ell\in\mathcal{L}$, and that the pairs
$(\boldsymbol{u}_{i},\ell_{i})\in\mathcal{U}\times\mathcal{L}$, $i=1,\dots,N$,
$N\in\mathbb{N}$ are observations drawn from some joint probability
distribution. For convenience, we shall assume that there exist some
corresponding distributions $P_{u}$ and $P_{\ell|u}$ such that the joint
distribution of $\boldsymbol{u}$ and $\ell$ is expressed as:
$P_{\ell|u}(\ell|\boldsymbol{u})P_{u}(\boldsymbol{u})$.

To formally specify the problem of few-shot learning and its relevant
variants, we need to determine a system that would be subjected to such
learning. For the sake of simplicity, here we will assume that this system is
a classifier. In general, however, this latter assumption may be dropped, and
the problem of few-shot learning could be extended to much broader classes of
AI systems.

Let $F:\mathcal{U}\rightarrow\mathcal{L}$ be such classifier assigning a
unique label from the set $\mathcal{L}$ (the set defining all possible lables)
to an element from $\mathcal{U}$. In what follows we shall assume that
$F=g\circ f$ (and denoted as $F[g\circ f]$ ) where

$f:\mathcal{U}\rightarrow\mathcal{X},\ \mathcal{X}\subset\mathbb{R}^{n}$ (1)

defines the classifier’s $F$ latent space $\mathcal{X}$, and

$g:\mathcal{X}\rightarrow\mathcal{L}$

determines how the classifier $F$ assigns a label to an input $\boldsymbol{u}$
having the the corresponding latent representation
$\boldsymbol{x}=f(\boldsymbol{u})$. A diagram showing schematic representation
of the classifier’s workflow is shown in Fig. 1.

Figure 1: Assumed input-output workflow of the classifier subject to few-shot
learning tasks

The above structure is very general and covers the majority of existing
classification models. We are now ready for formal definitions of the relevant
few-shot learning problems.

###  II-C Few-shot learning problems

In what follows we consider two classes of few-shot learning problems:
learning new examples from their single representation, and learning a new
class from few examples. These problems have different uses and aims. The
latter focuses primarily on generalising from a limited number of data points,
whereas the former aims at memorising new data without destroying existing
knowledge in the system.

####  II-C1 Learning a finite number of new examples

We begin with the first version of the problem, where the task is to learn, or
memorise, a given finite set. This task is formally introduced as Problem 1
below.

######  Problem 1 (Learning few examples)

Consider a classifier $F$ defined by (1), and let
$\mathcal{U}_{\mathrm{new}}=\\{\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{k}\\}$,
$k\in\mathbb{N}$, $\boldsymbol{u}_{i}\in\mathcal{U}_{\mathrm{new}}$, be a
given finite set to be learned by $F$. Let $\ell_{\mathrm{new}}\in\mathcal{L}$
be a label associated with the new set $\mathcal{U}_{\mathrm{new}}$. Let
$p_{e}$ be a given positive number in the interval $(0,1]$ determining the
quality of learning.

Find an algorithm $\mathcal{A}(\mathcal{U}_{\mathrm{new}})$ producing a
function $g^{\ast}:\mathcal{X}\rightarrow\mathcal{L}$ such that

$F[g^{\ast}\circ f(\boldsymbol{u})]=\ell_{\mathrm{new}}\ \mbox{for all}\
\boldsymbol{u}\in\mathcal{U}_{\mathrm{new}}$ (2)

and

$P\big{(}F[g^{\ast}\circ f(\boldsymbol{u})]=F[g\circ
f(\boldsymbol{u})]\big{)}\geq p_{e}$ (3)

for $\boldsymbol{u}$ drawn from the distribution $P_{u}$.

####  II-C2 Learning from an arbitrary finite number of examples

Let us now consider a different version of the problem where the system is to
learn a new class from few examples. The key difference here from the case
considered in Problem 1 is that we will no longer require that all new
examples are memorised. Instead, we will request that all  elements of the new
class are assigned a correct label with some a-priori defined probability. At
the same time, we will request that performance of the classifier on elements
from other classes does not drop below a given predefined and acceptable
level.

Extending our earlier conventions, we will suppose that the new class can be
described by a corresponding probability distribution $P_{\mathrm{new}}$ and
will be associated with a new label $\ell_{\mathrm{new}}$. Formal statement of
this task is provided in Problem 2.

######  Problem 2 (Learning from few examples)

Consider a classifier $F$ defined by (1), and let
$\mathcal{U}_{\mathrm{new}}=\\{\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{k}\\}$,
$k\in\mathbb{N}$, $\boldsymbol{u}_{i}\in\mathcal{U}_{\mathrm{new}}$, be a
finite independent and identically distributed (i.i.d.) sample from a
distribution $P_{\mathrm{new}}$, and $\ell_{\mathrm{new}}\in\mathcal{L}$ be a
corresponding new label to be associated with the elements drawn from
$P_{\mathrm{new}}$. Let $p_{e},p_{n}$ be given positive numbers in the
interval $(0,1]$ determining the quality of learning.

Find an algorithm $\mathcal{A}(\mathcal{U}_{\mathrm{new}})$ producing a
function $g^{\ast}:\mathcal{X}\rightarrow\mathcal{L}$ such that

$P\big{(}F[g^{\ast}\circ f(\boldsymbol{u})]=\ell_{\mathrm{new}}\big{)}\geq
p_{n}$ (4)

for $\boldsymbol{u}$ drawn from $P_{\mathrm{new}}$, and

$P\big{(}F[g^{\ast}\circ f(\boldsymbol{u})]=F[g\circ
f(\boldsymbol{u})]\big{)}\geq p_{e}$ (5)

for $\boldsymbol{u}$ drawn from the distribution $P_{u}$.

###### Remark 1

Note that Problems 1, 2 do not rely upon standard relationships between
expected and empirical risks to characterise generalisation and learning.
Instead, they impose stronger requirements: lower bounds on probabilities of
success.

These stronger requirements have clear practical benefits in terms of
understanding limitations and capabilities of few-shot learning algorithms
$\mathcal{A}$. Potential downsides, however, are that knowledge of some
general properties of the data distributions (support, non-degeneracy, etc)
may be needed to guarantee that these stronger requirements could be met.

###  II-D Assumptions

In agreement with existing literature on few-shot learning [6], [7], we will
primarily be dealing with representations $\boldsymbol{x}=f(\boldsymbol{u})$
of inputs $\boldsymbol{u}\in\mathcal{U}$ in the system’s latent space
$\mathcal{X}$ as opposed to working directly with $\mathcal{U}$ (see Fig. 1
for a diagram of the workflow). We will hence assume that the distributions
$P_{u}$, $P_{\ell|u}$, $P_{\mathrm{new}}$, and the function $f$ in (1) – (5)
induce their corresponding distributions $P_{x}$, $P_{\ell|x}$,
$P_{\mathrm{new},x}$ in the system’s latent space $\mathcal{X}$.

We will further assume that distributions $P_{x}$, $P_{\mathrm{new},x}$ are
supported on some balls in $\mathbb{R}^{n}$ and admit probability density
functions satisfying some non-degeneracy constraints. Formally these
requirements are formulated in Assumptions 1, 2.

###### Assumption 1

The probability density function $p_{x}$ associated with $P_{x}$ exists, is
defined on the unit ball $\mathbb{B}_{n}$, and there exist constants
$C_{x},r>0$ such that

$p_{x}(\boldsymbol{x})\leq\frac{C_{x}}{V_{n}(\mathbb{B}_{n})}r^{n}.$

###### Assumption 2

The probability density function $p_{\mathrm{new},x}$ associated with
$P_{\mathrm{new},x}$ exists, is defined on a ball
$\mathbb{B}_{n}(v,\boldsymbol{c})$, and there exist constants
$C_{\mathrm{new},x},\rho>0$ such that

$p_{\mathrm{new},x}(\boldsymbol{x})\leq\frac{C_{\mathrm{new},x}}{V_{n}(\mathbb{B}_{n})}\rho^{n}.$

In the next section we present main theoretical findings and quantifying
success of few- and one-shot learning schemes. These results join together
various ideas presented in earlier works [11], [12], [13], [14], [15], [16],
and reveal intrinsic links between data dimensionality, partial knowledge
about data models, and generalisation bounds.

##  III Main Results

###  III-A Learning an arbitrary finite number of examples

Our first result concerns Problem 1 and is formally expressed in Theorem 1
below

###### Theorem 1

[Learning few examples] Consider a classifier $F$ defined by (1), and let
$\mathcal{U}_{\mathrm{new}}=\\{\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{k}\\}$,
$k\in\mathbb{N}$, $\boldsymbol{u}_{i}\in\mathcal{U}_{\mathrm{new}}$, be a
finite set, and $\ell_{\mathrm{new}}\in\mathcal{L}$ be a corresponding new
label to be associated with the elements from this new set.

Let $\mathcal{Y}=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{k}\\}$,
$\boldsymbol{x}_{i}=f(\boldsymbol{u}_{i})$, $i=1,\dots,k$ be a representation
of the set $\mathcal{U}_{\mathrm{new}}$ in the classifier’s latent space,

$\bar{\boldsymbol{x}}=\frac{1}{k}\sum_{i}\boldsymbol{x}_{i},$

be the empirical mean of the representation with

$(\bar{\boldsymbol{x}},\boldsymbol{x}_{i})\geq 0\ \mbox{for all}\
\boldsymbol{x}_{i}\in\mathcal{Y},$

and let Assumption 1 hold.

Then the map

$g^{\ast}:\
g^{\ast}(\boldsymbol{x})=\left\\{\begin{array}[]{ll}\ell_{\mathrm{new}},&\mbox{if}\
\left(\frac{\bar{\boldsymbol{x}}}{\|\bar{\boldsymbol{x}}\|},\boldsymbol{x}\right)-\theta\geq
0\\\ g(\boldsymbol{x}),&\mbox{otherwise}\end{array}\right.$ (6)

parameterised by

$\theta=\min_{i\in\\{1,\dots,k\\}}\left\\{\left(\frac{\bar{\boldsymbol{x}}}{\|\bar{\boldsymbol{x}}\|},\boldsymbol{x}_{i}\right)\right\\}$

is a solution of Problem 1 with

$p_{e}=1-\frac{C_{x}}{2}\left[r\left(1-\theta^{2}\right)^{1/2}\right]^{n}.$
(7)

Proof of Theorem 1. According to the definition of the map $g^{\ast}$ and the
fact that $\boldsymbol{x}_{i}=f(\boldsymbol{u}_{i})$,

$\left(\frac{\bar{\boldsymbol{x}}}{\|\bar{\boldsymbol{x}}\|},\boldsymbol{x}_{i}\right)-\theta\geq
0$

and as a result

$F[g^{\ast}\circ f(\boldsymbol{u}_{i})]=\ell_{\mathrm{new}}$

for any $\boldsymbol{u}_{i}\in\mathcal{U}_{\mathrm{new}}$.

Let $\boldsymbol{u}$ be drawn from the distribution $P_{u}$. This vector has a
latent representation $\boldsymbol{x}=f(\boldsymbol{u})$ and a corresponding
induced distribution $P_{x}$ satisfying Assumption 1. Let

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

Then

$\begin{split}&P(F[g^{\ast}\circ
f(\boldsymbol{u})]=\ell_{\mathrm{new}})=\int_{\mathcal{C}_{n}(\bar{\boldsymbol{x}},\theta)}p_{x}(\boldsymbol{x})d\boldsymbol{x}\\\
\leq&\frac{C_{x}}{V_{n}(\mathbb{B}_{n})}r^{n}\int_{\mathcal{C}_{n}(\bar{\boldsymbol{x}},\theta)}d\boldsymbol{x}\leq\frac{C_{x}}{2}r^{n}[(1-\theta^{2})^{1/2}]^{n}.\end{split}$

The statement now follows. $\square$

###### Remark 2

Note that if $r(1-\theta^{2})^{1/2}<1$ then the bound $p_{e}$ approaches $1$
exponentially fast as $n$ grows. This implies that learning a single or few
examples can be efficiently accomplished by an exceptionally simple map (6).

Performance of this learning scheme depends on the values of $r$ and $\theta$.
The closer the value of $\theta$ is to $1$, however, the broader the range of
$r$ for which solution (6) of Problem 1 is appropriate.

###### Remark 3

One can easily verify that few-shot learning scheme (6) assigns the label
$\ell_{\mathrm{new}}$ to all convex combinations of
$\boldsymbol{u}_{i}\in\mathcal{U}_{\mathrm{new}}$. In this respect, the entire
convex hull of $\mathcal{U}_{\mathrm{new}}$ is learnt by (6).

In the next subsection we will show that, under appropriate assumptions,
learning schemes which are very similar to (6) have a capacity to generalise
beyond finite sets and their convex hulls from just few examples.

###  III-B Learning from few examples

Let us now turn attention to Problem 2. Our main theoretical statement
specifying a simple solution of this problem is presented in Theorem 2.
Similarly to Theorem 1, we show that performance of the proposed scheme to
learn from $k$ examples is closely related to 1) dimension $n$ of the
classifier’s latent space and 2) non-degeneracy of probability distributions
of the inputs’ representations in that space.

The theorem is largely based on Lemmas 1, 2 which we present below.

###### Lemma 1

Let
$\mathcal{Y}=\\{\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{k}\\}$
be a set of $k$ i.i.d. random vectors drawn from a distribution satisfying
Assumption 2, and let $\delta,\varepsilon\in(0,1)$. Consider event $A_{1}$:

$A_{1}:\
|(\boldsymbol{x}_{i}-\boldsymbol{c},\boldsymbol{x}_{j}-\boldsymbol{c})|\leq{\delta
v},\ \forall\ i\neq j$ (8)

and event $A_{2}$:

$A_{2}:\ \|\boldsymbol{x}_{i}-\boldsymbol{c}\|\geq(1-\varepsilon)v\ \forall\
i.$ (9)

Then

$P(A_{1})\geq 1-C_{\mathrm{new}}\frac{k(k-1)}{2}\left[\rho
v(1-\delta^{2})^{1/2}\right]^{n},$ (10)

and

$\begin{split}&P\left(A_{1}\wedge A_{2}\right)\geq\\\
&1-C_{\mathrm{new}}k[\rho
v(1-\varepsilon)]^{n}-C_{\mathrm{new}}\frac{k(k-1)}{2}\left[\rho
v(1-\delta^{2})^{1/2}\right]^{n}.\end{split}$ (11)

Proof of Lemma 1. Let us denote
$\tilde{\boldsymbol{x}}_{i}=\boldsymbol{x}_{i}-\boldsymbol{c}$. Consider
events

$\begin{split}E_{1}:&\
\left|\left(\frac{\tilde{\boldsymbol{x}}_{1}}{\|\tilde{\boldsymbol{x}}_{1}\|},\tilde{\boldsymbol{x}}_{2}\right)\right|>\delta\\\
E_{2}:&\
\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{1}}{\|\tilde{\boldsymbol{x}}_{1}\|},\tilde{\boldsymbol{x}}_{3}\right)\right|>\delta\right]\vee\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{2}}{\|\tilde{\boldsymbol{x}}_{2}\|},\tilde{\boldsymbol{x}}_{3}\right)\right|>\delta\right]\\\
\vdots&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\\ E_{k-1}:&\
\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{1}}{\|\tilde{\boldsymbol{x}}_{1}\|},\tilde{\boldsymbol{x}}_{k}\right)\right|>\delta\right]\vee\cdots\vee\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{k-1}}{\|\tilde{\boldsymbol{x}}_{k-1}\|},\tilde{\boldsymbol{x}}_{k}\right)\right|>\delta\right]\\\
&\\\ B_{1}:&\ \|\tilde{\boldsymbol{x}}_{1}\|<(1-\varepsilon)v\\\ \vdots&\ \ \
\ \ \ \ \ \ \ \ \ \ \ \vdots\\\ B_{k}:&\
\|\tilde{\boldsymbol{x}}_{k}\|<(1-\varepsilon)v\end{split}$

Let

$\mathcal{C}_{n}(\boldsymbol{z},\boldsymbol{c},v,\delta)=\left\\{\boldsymbol{x}\in\mathbb{B}_{n}(v,\boldsymbol{c})\left|\
\left(\frac{\boldsymbol{z}}{\|\boldsymbol{z}\|},\boldsymbol{x}-\boldsymbol{c}\right)>\delta\right.\right\\}.$

According to Assumption 2 and the fact that $\boldsymbol{x}_{1}$ and
$\boldsymbol{x}_{2}$ are drawn independently from the same distribution, the
probability that event $E_{1}$ occurs can be bounded from above as

$\begin{split}P(E_{1})=&\int_{\mathcal{C}_{n}(\tilde{\boldsymbol{x}}_{1},\boldsymbol{c},v,\delta)}p_{\mathrm{new},x}(\boldsymbol{x})d\boldsymbol{x}\\\
&\ \ \ \ \ \ \ \ \ \ \ \
+\int_{\mathcal{C}_{n}(-\tilde{\boldsymbol{x}}_{1},\boldsymbol{c},v,\delta)}p_{\mathrm{new},x}(\boldsymbol{x})d\boldsymbol{x}\\\
<&\frac{C_{\mathrm{new},x}\rho^{n}}{V_{n}(\mathbb{B}_{n})}\int_{\mathcal{C}_{n}(\tilde{\boldsymbol{x}}_{1},\boldsymbol{c},v,\delta)}d\boldsymbol{x}\\\
&\ \ \ \ \ \ \ \ \ \ \ \
+\frac{C_{\mathrm{new},x}\rho^{n}}{V_{n}(\mathbb{B}_{n})}\int_{\mathcal{C}_{n}(-\tilde{\boldsymbol{x}}_{1},\boldsymbol{c},v,\delta)}d\boldsymbol{x}\\\
=&\frac{C_{\mathrm{new},x}\rho^{n}}{V_{n}(\mathbb{B}_{n})}2V_{n}(\mathcal{C}_{n}(\tilde{\boldsymbol{x}}_{1},\boldsymbol{c},v,\delta)).\end{split}$
(12)

Observe that

$2V_{n}\big{(}\mathcal{C}_{n}(\tilde{\boldsymbol{x}}_{1},\boldsymbol{c},v,\delta)\big{)}\leq
V_{n}(\mathbb{B}_{n})[v(1-\delta^{2})^{1/2}]^{n}.$ (13)

Combining (12), (13) we obtain:

$P(E_{1})<C_{\mathrm{new},x}[\rho v(1-\delta^{2})^{1/2}]^{n}.$ (14)

Recall that for any events $A_{1},\dots,A_{k}$ the following probability union
bound holds true (also known as the Boole’s inequality):

$P(\bigcup_{i=1}^{k}A_{i})\leq\sum_{i=1}^{k}P(A_{i}).$ (15)

Hence

$\begin{split}P(E_{2})=&P\left(\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{1}}{\|\tilde{\boldsymbol{x}}_{1}\|},\tilde{\boldsymbol{x}}_{3}\right)\right|>\delta\right]\vee\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{2}}{\|\tilde{\boldsymbol{x}}_{2}\|},\tilde{\boldsymbol{x}}_{3}\right)\right|>\delta\right]\right)\\\
\leq&\sum_{i=1}^{2}P\left(\left|\left(\frac{\tilde{\boldsymbol{x}}_{i}}{\|\tilde{\boldsymbol{x}}_{i}\|},\tilde{\boldsymbol{x}}_{3}\right)\right|>\delta\right).\end{split}$

Using the same argument as in (12)–(14) we can derive that

$P(E_{2})<2C_{\mathrm{new},x}[\rho v(1-\delta^{2})^{1/2}]^{n},$

and that

$P(E_{i})<i\cdot C_{\mathrm{new},x}[\rho v(1-\delta^{2})^{1/2}]^{n}\ \mbox{for
all}\ i=1,\dots,k.$ (16)

Consider now events $B_{1},\dots B_{k}$ and evalutate $P(B_{i})$,
$i=1,\dots,k$:

$\displaystyle
P(B_{i})=\int_{\mathbb{B}_{n}(v(1-\varepsilon),\boldsymbol{c})}p_{\mathrm{new},x}(\boldsymbol{x})d\boldsymbol{x}$
(17)
$\displaystyle\leq\frac{C_{\mathrm{new},x}\rho^{n}}{V_{n}(\mathbb{B}_{n})}\int_{\mathbb{B}_{n}(v(1-\varepsilon),\boldsymbol{c})}d\boldsymbol{x}$
$\displaystyle=C_{\mathrm{new},x}\rho^{n}\frac{V_{n}(\mathbb{B}_{n}(v(1-\varepsilon),\boldsymbol{c})}{V_{n}(\mathbb{B}_{n})}=C_{\mathrm{new},x}[\rho
v(1-\varepsilon)]^{n}.$

Recall that, for any sets $A_{1},\dots,A_{d}$, De Morgan’s law states that:

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

Therefore

$\begin{split}&P(A_{1}\land A_{2}\land\cdots\land A_{d})=\\\ &\ \ \ \ \ \ \ \
\ \ \ 1-P((\mbox{not}\ A_{1})\lor(\mbox{not}\ A_{2})\lor\cdots(\mbox{not}\
A_{d})).\end{split}$

Using the union bound rule (15), one can derive that

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

To complete the lemma, consider events

$\begin{split}\mbox{not}\ E_{1}:&\
\left|\left(\frac{\tilde{\boldsymbol{x}}_{1}}{\|\tilde{\boldsymbol{x}}_{1}\|},\tilde{\boldsymbol{x}}_{2}\right)\right|\leq\delta\\\
\mbox{not}\ E_{2}:&\
\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{1}}{\|\tilde{\boldsymbol{x}}_{1}\|},\tilde{\boldsymbol{x}}_{3}\right)\right|\leq\delta\right]\wedge\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{2}}{\|\tilde{\boldsymbol{x}}_{2}\|},\tilde{\boldsymbol{x}}_{3}\right)\right|\leq\delta\right]\\\
\vdots&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\\ \mbox{not}\ E_{k-1}:&\
\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{1}}{\|\tilde{\boldsymbol{x}}_{1}\|},\tilde{\boldsymbol{x}}_{k}\right)\right|\leq\delta\right]\wedge\cdots\\\
&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\wedge\left[\left|\left(\frac{\tilde{\boldsymbol{x}}_{k-1}}{\|\tilde{\boldsymbol{x}}_{k-1}\|},\tilde{\boldsymbol{x}}_{k}\right)\right|\leq\delta\right]\\\
\mbox{not}\ B_{1}:&\ \|\tilde{\boldsymbol{x}}_{1}\|\geq(1-\varepsilon)v\\\
\vdots&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\\ \mbox{not}\ B_{k}:&\
\|\tilde{\boldsymbol{x}}_{k}\|\geq(1-\varepsilon)v\end{split}$

Given that $\boldsymbol{x}_{i}\in\mathbb{B}_{n}(v,\boldsymbol{c})$, we have
that $\|\tilde{\boldsymbol{x}_{i}}\|\leq v$. It is hence clear that the event
$[\mbox{not}\ E_{1}\wedge\cdots\wedge\mbox{not}\ E_{k-1}]$ is contained in the
event $A_{1}$ defined by (8) in the sense that any
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{k}\in\mathbb{B}_{n}(v,\boldsymbol{c})$
for which

$\mbox{not}\ E_{1}\wedge\cdots\wedge\mbox{not}\ E_{k-1}$

holds true must necessarily satisfy (8).

Therefore, according to (9), (18), we can write:

$P(A_{1})\geq P(\mbox{not}\ E_{1}\wedge\dots\wedge\mbox{not}\ E_{k-1})\geq
1-\sum_{i=1}^{k-1}P(E_{i}),$

and

$\begin{split}&P(A_{1}\wedge A_{2})=P(A_{1}\wedge\mbox{not}\
B_{1}\wedge\cdots\mbox{not}\ B_{k})\\\ &\geq P(\mbox{not}\
E_{1}\wedge\dots\wedge\mbox{not}\ E_{k-1}\wedge\mbox{not}\
B_{1}\wedge\dots\wedge\mbox{not}\ B_{k}\cdots)\\\ &\geq
1-\sum_{i=1}^{k-1}P(E_{i})-\sum_{i=1}^{k}P(B_{i}).\end{split}$

Substituting (16), (17) into the latter expressions one can now conclude that
the lemma holds true. $\square$

###### Remark 4

Lemma 1 reveals, in a general setting, the typicality of large “almost” or
quasi- orthogonal bases in high-dimension (cf. [12]). Indeed, according to
(11), if $\rho v(1-\varepsilon)<1$, $\rho v(1-\delta^{2})^{1/2}<1$ then

$\begin{split}&|\cos(\boldsymbol{x}_{i}-\boldsymbol{c},\boldsymbol{x}_{j}-\boldsymbol{c})|=\frac{|(\boldsymbol{x}_{i}-\boldsymbol{c},\boldsymbol{x}_{j}-\boldsymbol{c})|}{\|\boldsymbol{x}_{i}-\boldsymbol{c}\|\|\boldsymbol{x}_{j}-\boldsymbol{c}\|}\\\
&\leq\frac{\delta
v}{v^{2}(1-\varepsilon)^{2}}=\frac{\delta}{v(1-\varepsilon)^{2}}\end{split}$

with probability close to $1$ if $n$ is sufficiently large. Earlier works [17]
(see also [18], [19]) showed that large ($k\gg n$) quasi-orthogonal bases
exist. Here we follow our earlier results [12] and prove that almost
orthogonal corteges of vectors whose cardinalily $k$ grows exponentially with
dimension $n$ are typical in high dimension.

Our next result, Lemma 2 shows how this almost or quasi-orthogonality property
can be used to estimate centroids of data clusters in high-dimensional
datasets from few observations.

###### Lemma 2

Let
$\mathcal{Y}=\\{\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{k}\\}$
be a set of $k$ i.i.d. random vectors drawn from a distribution satisfying
Assumption 2, and let $\delta,\varepsilon\in(0,1)$. Let

$\bar{\boldsymbol{x}}=\frac{1}{k}\sum_{i=1}^{k}\boldsymbol{x}_{i}$

be the empirical mean of the sample.

Then

$\begin{split}&P\left(L(k,\delta,\varepsilon)\leq\|\bar{\boldsymbol{x}}-\boldsymbol{c}\|^{2}\leq
U(k,\delta)\right)\\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \geq
1-R_{\varepsilon,\delta}(n,k,v,\rho,\delta,\varepsilon),\end{split}$ (19)

and

$P\left(\|\bar{\boldsymbol{x}}-\boldsymbol{c}\|^{2}\leq U(k,\delta)\right)\geq
1-R_{\delta}(n,k,v,\rho,\delta),$ (20)

where

$\begin{split}U(k,\delta)=\frac{v^{2}}{k}+\frac{k-1}{k}v\delta\\\
L(k,\delta,\varepsilon)=\frac{(1-\varepsilon)^{2}v^{2}}{k}-\frac{k-1}{k}v\delta\end{split}$

and

$\begin{split}R_{\varepsilon,\delta}(n,k,v,\delta,\rho,\varepsilon)=&C_{\mathrm{new}}k[\rho
v(1-\varepsilon)]^{n}\\\ &+C_{\mathrm{new}}\frac{k(k-1)}{2}\left[\rho
v(1-\delta^{2})^{1/2}\right]^{n},\\\
R_{\delta}(n,k,v,\rho,\delta)=&C_{\mathrm{new}}\frac{k(k-1)}{2}\left[\rho
v(1-\delta^{2})^{1/2}\right]^{n}.\end{split}$

Proof of Lemma 2. The Lemma is essentially contained in Lemma 1. Indeed,
consider

$\begin{split}&\|\bar{\boldsymbol{x}}-\boldsymbol{c}\|^{2}=(\bar{\boldsymbol{x}}-\boldsymbol{c},\bar{\boldsymbol{x}}-\boldsymbol{c})=\left(\frac{1}{k}\sum_{i=1}^{k}\boldsymbol{x}_{i}-\boldsymbol{c},\frac{1}{k}\sum_{i=1}^{k}\boldsymbol{x}_{i}-\boldsymbol{c}\right)\\\
&=\frac{1}{k^{2}}\sum_{i=1}^{k}\|\boldsymbol{x}_{i}-\boldsymbol{c}\|^{2}+\frac{1}{k^{2}}\sum_{i\neq
j}(\boldsymbol{x}_{i}-\boldsymbol{c},\boldsymbol{x}_{j}-\boldsymbol{c}).\end{split}$

According to Lemma 1 (statement (10)), the term

$\left|\frac{1}{k^{2}}\sum_{i\neq
j}(\boldsymbol{x}_{i}-\boldsymbol{c},\boldsymbol{x}_{j}-\boldsymbol{c})\right|\leq\frac{k-1}{k}v\delta$

with probability $1-R_{\delta}(n,k,v,\delta)$. This, together with the fact
that $\|\boldsymbol{x}_{i}-\boldsymbol{c}\|\leq v$ for all $i=1,\dots,k$,
prove (19). Similarly, statement (11) of Lemma 1 implies now that bound (20)
holds true too. $\square$

###### Theorem 2

[Learning from few examples] Consider a classifier $F$ defined by (1), and let
$\mathcal{U}_{\mathrm{new}}=\\{\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{k}\\}$,
$k\in\mathbb{N}$, $\boldsymbol{u}_{i}\in\mathcal{U}_{\mathrm{new}}$, be a
finite independent and identically distributed (i.i.d.) sample from a
distribution $P_{\mathrm{new}}$, and $\ell_{\mathrm{new}}\in\mathcal{L}$ be a
corresponding new label to be associated with the elements drawn from
$P_{\mathrm{new}}$.

Let $\mathcal{Y}=\\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{k}\\}$,
$\boldsymbol{x}_{i}=f(\boldsymbol{u}_{i})$, $i=1,\dots,k$ be a representation
of the sample $\mathcal{U}_{\mathrm{new}}$ in the classifier’s latent space,

$\bar{\boldsymbol{x}}=\frac{1}{k}\sum_{i}\boldsymbol{x}_{i},$

be the empirical mean of the representation, and let Assumption 2 hold.
Finally, let $\delta\in(0,1)$ be a number satisfying

$\Delta=\|\bar{\boldsymbol{x}}\|-\left(\frac{v^{2}}{k}+\frac{k-1}{k}v\delta\right)^{1/2}>0.$

Then the map

$g^{\ast}:\
g^{\ast}(\boldsymbol{x})=\left\\{\begin{array}[]{ll}\ell_{\mathrm{new}},&\mbox{if}\
\left(\frac{\bar{\boldsymbol{x}}}{\|\bar{\boldsymbol{x}}\|},\boldsymbol{x}\right)-\theta\geq
0\\\ g(\boldsymbol{x}),&\mbox{otherwise}\end{array}\right.$ (21)

parameterised by

$\theta\in\left[\max\\{\Delta-v,0,\\},\Delta\right]$

is a solution of Problem 2 with

$\begin{split}p_{n}=&\left(1-\frac{C_{\mathrm{new},x}}{2}\left[\rho\left(v^{2}-(\Delta-\theta)^{2}\right)^{1/2}\right]^{n}\right)\times\\\
&\ \ \ \ \ \ \ \ \ \left(1-C_{\mathrm{new}}\frac{k(k-1)}{2}\left[\rho
v(1-\delta^{2})^{1/2}\right]^{n}\right),\\\
p_{e}=&1-\frac{C_{x}}{2}\left[r\left(1-\theta^{2}\right)^{1/2}\right]^{n}.\end{split}$
(22)

Proof of Theorem 2. According to Lemma 2, the probability that the centre
$\boldsymbol{c}$ is within
$\left(\frac{v^{2}}{k}+\frac{k-1}{k}v\delta\right)^{1/2}$ from the empirical
mean $\bar{\boldsymbol{x}}$ is at least

$\left(1-C_{\mathrm{new}}\frac{k(k-1)}{2}\left[\rho
v(1-\delta^{2})^{1/2}\right]^{n}\right).$

Suppose that the above event occurs. This implies that the hyperplane

$\boldsymbol{x}:\left(\frac{\bar{\boldsymbol{x}}}{\|\bar{\boldsymbol{x}}\|},\boldsymbol{x}\right)-\theta=0$

is at least $\Delta-\theta$ away from the hyperplane with the same normal,
$\frac{\bar{\boldsymbol{x}}}{\|\bar{\boldsymbol{x}}\|}$, and which is passing
through the centre $\boldsymbol{c}$ of the ball
$\mathbb{B}_{n}(v,\boldsymbol{c})$ (see Fig. 2).

Figure 2: Illustration to the proof of Theorem 2. Pink filled circle shows
$\mathbb{B}_{n}(v,\boldsymbol{c})$, blue dashed disc shows the domain where
the true centre $\boldsymbol{c}$ is located (with high probability), and blue
solid line shows the hyperplane
$\left(\frac{\bar{\boldsymbol{x}}}{\|\bar{\boldsymbol{x}}\|},\boldsymbol{x}\right)-\theta=0$.

The probability that an element drawn from the distribution $P_{\mathrm{new}}$
would have a representation $\boldsymbol{x}$ for which
$\left(\frac{\bar{\boldsymbol{x}}}{\|\bar{\boldsymbol{x}}\|},\boldsymbol{x}\right)-\theta>0$
is hence at least

$1-\frac{C_{\mathrm{new},x}}{2}\left[\rho\left(v^{2}-(\Delta-\theta)^{2}\right)^{1/2}\right]^{n}.$

This justifies the expression for $p_{n}$ in (22).

Similarly, the probability that an element drawn from the distribution $P_{u}$
would be assigned a label $\ell_{\mathrm{new}}$ is at most

$\frac{C_{x}}{2}\left[r\left(1-\theta^{2}\right)^{1/2}\right]^{n}.$

Hence the expression for $p_{e}$ follows. $\square$

###### Remark 5

According to Theorem 2 and similar to the case covered by Theorem 1, under
appropriate and reasonable assumptions, the probabilities of success in the
task of learning from few examples approach $1$ exponentially fast as $n$
grows.

###  III-C Discussion

Having introduced our main theoretical results, let us now briefly relate
these results to existing literature on few-shot learning and outline future
potential direction s.

####  III-C1 Matching and prototypical networks

Theorems 1, 2 and few-shot learning algorithms (6), (21), which these theorems
relate to, show striking similarity to approaches presented and empirically
studied in [6], [7]. In the case of one-shot learning [6], Theorem 1 with
$k=1$ applies, whereas in the case of few-shot learning, [7], Theorem 2 could
be more appropriate for explaining and interpreting why few-shot learning
works.

####  III-C2 Object models and the challenge of generalisation

Our results show that significant understanding and insights into why and when
large-scale and highly expressive AI systems, including deep neural networks,
can generalise well from just few examples can be gained if some loose
assumptions are introduced on the data models. In our case, these assumptions,
are that 1) the probability distributions of objects’ representations in the
system’s latent space are supported on some balls (or ellipsoids, subject to a
coordinate transformation), and 2) these probability distributions are not
degenerate in the sense of Assumptions 1, 2. Going forward, one can consider
further straightforward generalisations in which the objects are modeled by
mixtures of these models. These generalisations, are however, beyond the scope
of the current work.

In addition, our current work, by focusing on what can and what cannot be
learned from few examples in randomised settings, provides insights into why
stochastic configuration networks may be so successful in practice [20], [21]:
practically relevant functions we are interested to learn may have a “compact”
structure, and the process of stochastic configuration could be viewed as an
efficient mechanism that is capable to learn this structure from data step-by-
step.

####  III-C3 Learning to learn

In addition to explaining why few-shot learning models work and why large-
scale deep learning models may generalise so well, our present work presents
high-level training requirements for a model that is trained to learn from few
examples. These requirements are specified in Assumptions 1 and 2. If a
network is trained so that object representations in its latent space satisfy
Assumptions 1 and 2 with appropriate relevant constants then Theorems 1, 2
guarantee that such models can indeed learn from mere few or single examples.
Importantly, training of networks to satisfy Assumptions 1 and 2 can be posed
within the standard empirical risk minimisation framework. A very similar
approach has been pursued in [7], [6], albeit heuristically.

##  IV Conclusion

This work presents a formal treatment of the challenges of few-shot and one-
shot learning and generalisation in large-scale modern AI models. We provided
formal statements of these learning problems and showed that high
dimensionality and geometry of objects’ representations in the systems’ latent
spaces along with some non-degeneracy conditions are key determinants
explaining when and why such learning is possible.

Our results suggest that neural networks’ generalisation capabilities are
intrinsically linked with internal regularities in the data sets and also with
representations of these regularities in the networks’ latent spaces. The
results reveal an important characteristic of this important regularity: if an
object has a “compact” representation in the network’s latent space then such
object can be learned from just few or even single example. Absence of such
compact representations may require exponentially large training samples to
learn from.

## References

  * [1] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 4510–4520.
  * [2] O. Parkhi, A. Vedaldi, and A. Zisserman, “Deep face recognition,” in _Proceedings of the British Machine Vision Conference (BMVC)_ , X. Xianghua, M. Jones, and K. Gary, Eds. BMVA Press, September 2015, pp. 41.1–41.12. [Online]. Available: https://dx.doi.org/10.5244/C.29.41
  * [3] V. N. Vapnik, “An overview of statistical learning theory,” _IEEE Transactions on Neural Networks_ , vol. 10, no. 5, pp. 988–999, 1999.
  * [4] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals, “Understanding deep learning requires rethinking generalization,” _arXiv preprint arXiv:1611.03530_ , 2016.
  * [5] T. J. Sejnowski, “The unreasonable effectiveness of deep learning in artificial intelligence,” _Proceedings of the National Academy of Sciences_ , vol. 117, no. 48, pp. 30 033–30 038, 2020.
  * [6] O. Vinyals, C. Blundell, T. Lillicrap, K. Kavukcuoglu, and D. Wierstra, “Matching networks for one shot learning,” in _Advances in neural information processing systems_ , 2016, pp. 3630–3638.
  * [7] J. Snell, K. Swersky, and R. Zemel, “Prototypical networks for few-shot learning,” in _Advances in neural information processing systems_ , 2017, pp. 4077–4087.
  * [8] A. Gorban and I. Tyukin, “Stochastic separation theorems,” _Neural Networks_ , vol. 94, pp. 255–259, 2017.
  * [9] B. Grechuk, A. Gorban, and I. Tyukin, “General stochastic separation theorems with optimal bounds,” _Neural Networks_ , vol. 138, pp. 33–56, 2021. [Online]. Available: https://doi.org/10.1016/j.neunet.2021.01.034
  * [10] F. Cucker and S. Smale, “On the mathematical foundations of learning,” _Bulletin of the American mathematical society_ , vol. 39, no. 1, pp. 1–49, 2002.
  * [11] I. Y. Tyukin, A. N. Gorban, C. Calvo, J. Makarova, and V. A. Makarov, “High-dimensional brain. A tool for encoding and rapid learning of memories by single neurons,” _Bulletin of Mathematical Biology_ , vol. 81, pp. 4856–4888, 2019. [Online]. Available: https://doi.org/10.1007/s11538-018-0415-5
  * [12] A. Gorban, I. Tyukin, D. Prokhorov, and K. Sofeikov, “Approximation with random bases: Pro et contra,” _Information Sciences_ , vol. 364–365, pp. 129–145, 2016.
  * [13] I. Y. Tyukin, A. N. Gorban, K. Sofeikov, and I. Romanenko, “Knowledge transfer between artificial intelligence systems,” _Frontiers of Neurorobotics_ , vol. 12, Article 49, 2018.
  * [14] A. Gorban, A. Golubkov, B. Grechuk, E. Mirkes, and I. Tyukin, “Correction of AI systems by linear discriminants: Probabilistic foundations,” _Information Sciences_ , vol. 466, pp. 303–322, 2018.
  * [15] 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_ , 2018.
  * [16] A. N. Gorban, V. Makarov, and I. Tyukin, “High-dimensional brain in a high-dimensional world: Blessing of dimensionality,” _Entropy_ , vol. 22, no. 1, p. 82, 2020.
  * [17] P. Kainen and V. Kurkova, “Quasiorthogonal dimension of euclidian spaces,” _Appl. Math. Lett._ , vol. 6, no. 3, pp. 7–10, 1993.
  * [18] P. C. Kainen and V. Kurkova, “Quasiorthogonal dimension,” in _Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications_. Springer, 2020, pp. 615–629.
  * [19] P. C. Kainen, “Utilizing geometric anomalies of high dimension: When complexity makes computation easier,” in _Computer Intensive Methods in Control and Signal Processing_. Springer, 1997, pp. 283–294.
  * [20] D. Wang and M. Li, “Stochastic configuration networks: Fundamentals and algorithms,” _IEEE Transactions on Cybernetics_ , vol. 47, no. 10, pp. 3466–3479, 2017.
  * [21] C. Huang, Q. Huang, and D. Wang, “Stochastic configuration networks based adaptive storage replica management for power big data processing,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 1, pp. 373–383, 2019.


[table]capposition=top

A thesis submitted in fulfilment of the requirements
for the degree of
by

Roll No: 18104278

###### Abstract

The primary focus of this thesis is to make Sanskrit manuscripts more
accessible to the end-users through natural language technologies. The
morphological richness, compounding, free word orderliness, and low-resource
nature of Sanskrit pose significant challenges for developing deep learning
solutions. We identify four fundamental tasks, which are crucial for
developing a robust NLP technology for Sanskrit: word segmentation, dependency
parsing, compound type identification, and poetry analysis. The first task,
Sanskrit Word Segmentation (SWS), is a fundamental text processing task for
any other downstream applications. However, it is challenging due to the
sandhi phenomenon that modifies characters at word boundaries. Similarly, the
existing dependency parsing approaches struggle with morphologically rich and
low-resource languages like Sanskrit. Compound type identification is also
challenging for Sanskrit due to the context-sensitive semantic relation
between components. All these challenges result in sub-optimal performance in
NLP applications like question answering and machine translation. Finally,
Sanskrit poetry has not been extensively studied in computational linguistics.

While addressing these challenges, this thesis makes various contributions,
First, the thesis proposes linguistically-informed neural architectures for
these tasks. For the SWS task, our system accommodates language-specific
sandhi phenomenon as an inductive bias. We also propose a novel
linguistically-informed context-sensitive multi-task learning architecture for
compound type identification, with morphological tagging and dependency
parsing auxiliary tasks. Additionally, we propose a linguistically-informed
ensemble architecture for dependency parsing that augments several strategies.
Finally, we propose to build an interpretable framework consisting of 7
linguistically-informed modules to analyze and classify Sanskrit poetry into
levels of the best composition.

Second, we showcase the interpretability and multilingual extension of the
proposed systems. We conduct probing analyses on attention modules in word
segmentation and compound type identification tasks. Our findings highlight
the importance of attention modules and auxiliary tasks in NLP tasks and
emphasize the need for explainable AI systems. We also showcase the efficacy
of our systems on multiple languages for compound type identification and
dependency parsing tasks.

Third, our proposed systems report state-of-the-art performance. For instance,
our system shows an average gain of 7.2 points over the current state-of-the-
art system in word segmentation. The ensemble system used for dependency
parsing outperforms the state-of-the-art system by 1.2 points for Sanskrit,
and the context-sensitive compound type identification task reports a gain of
7.71 points compared to the current state-of-the-art.

Finally, we present a neural toolkit named SanskritShala, a web-based
application that provides real-time analysis of input for various NLP tasks.
We release the source codes, 7 word embedding models trained on publicly
available Sanskrit corpora and a multilingual code-mixed ST dataset for 25
languages. Additionally, we provide annotations for Śikṣāṣṭaka poetry and a
web application to illustrate its analysis and annotations. Overall, this
thesis contributes to making Sanskrit manuscripts more accessible by
developing robust NLP technology and releasing various resources, datasets,
and web-based toolkit.

It is certified that the work contained in this thesis entitled “” by has been
carried out under my supervision and that it has not been submitted elsewhere
for a degree.

Professor

Assistant Professor

This is to certify that the thesis titled “” has been authored by me. It
presents the research conducted by me under the supervision of and .

To the best of my knowledge, it is an original work, both in terms of research
content and narrative, and has not been submitted elsewhere, in part or in
full, for a degree. Further, due credit has been attributed to the relevant
state-of-the-art and collaborations with appropriate citations and
acknowledgments, in line with established norms and practices.
Roll No. 18104278 EE Department

Author’s Biography:

  * •

Name: Mr. Jivnesh Sandhan; Ph.D. at IIT Kanpur

  * •

Education: Dual degree in Math’s and Scientific Computing, IIT Kanpur, 2018.

  * •

Scholarship: Recipient of the TCS Research Fellowship.

  * •

Broad research area: Deep learning for Sanskrit Computational Linguistics.

  * •

Research supervisor: Dr. Laxmidhar Behera and Dr. Suvendu Samanta.

  * •

Goal: Provide access to Sanskrit literature for pedagogical and annotation
purposes.

  * •

Current research: Aesthetics of Sanskrit poetry from computational
perspective.

  1. 1.

Jivnesh Sandhan, Amruta Barbadikar, Malay Maity, Tushar Sandhan, Pawan Goyal,
Laxmidhar Behera. _Aesthetics of Sanskrit Poetry from the Perspective of
Computational Linguistics: A Case Study Analysis on śiksāṣṭaka Poetry._ ACM
Transactions on Asian and Low-Resource Language Information Processing, TALLIP
2023*. [Paper] — [Interface] (Communicated).

  2. 2.

Jivnesh Sandhan, Anshul Agarwal, Laxmidhar Behera, Tushar Sandhan, Pawan
Goyal. _SanskritShala: A Neural Sanskrit NLP Toolkit with Web-Based Interface
for Pedagogical and Annotation Purposes._ Proceedings of the Annual Meeting of
the Association for Computational Linguistics: System Demonstrations, ACL
2023*, Toronto, Canada. [Paper] — [Code]

  3. 3.

Jivnesh Sandhan, Laxmidhar Behera, Pawan Goyal. _Systematic Investigation of
Strategies Tailored for Low-Resource Settings for Low-Resource Dependency
Parsing._ Proceedings of the European Chapter of the Association for
Computational Linguistics, EACL 2023, Dubrovnik, Croatia. [Paper] — [Code]

  4. 4.

Jivnesh Sandhan, Rathin Singha, Narein Rao, Suvendu Samanta, Laxmidhar Behera,
Pawan Goyal. _TransLIST: A Transformer-Based Linguistically Informed Sanskrit
Tokenizer._ Proceedings of the Conference on Empirical Methods in Natural
Language Processing, EMNLP (Findings) 2022, Abu Dhabi. [Paper] — [Code]

  5. 5.

Jivnesh Sandhan, Ashish Gupta, Hrishikesh Terdalkar, Tushar Sandhan, Suvendu
Samanta, Laxmidhar Behera and Pawan Goyal. _A Novel Multi-Task Learning
Approach for Context-Sensitive Compound Type Identification in Sanskrit._
Proceedings of International Conference on Computational Linguistics, COLING
2022, Republic of Korea. [Paper] — [Code]

  6. 6.

Jivnesh Sandhan, Amrith Krishna, Ashim, Gupta, Pawan Goyal, and Laxmidhar
Behera. _A Little Pretraining Goes a Long Way: A Case Study on Dependency
Parsing Task for Low-resource Morphologically Rich Languages._ Proceedings of
the European Chapter of the Association for Computational Linguistics, EACL-
SRW 2021, Ukraine. [Paper] — [Code]

  7. 7.

Jivnesh Sandhan, Ayush Daksh, Om Adideva Paranjay, Laxmidhar Behera, Pawan
Goyal. _Prabhupadavani: A Code-mixed Speech Translation Data for 26
Languages._ Proceedings of International Conference on Computational
Linguistics Workshop on Computational Linguistics for Cultural Heritage,
Social Sciences, Humanities, COLING-LaTeCH-CLfL 2022, Gyeongju, Republic of
Korea. [Paper] — [Code]

  8. 8.

Jivnesh Sandhan, Om Adideva, Digumarthi Komal, Laxmidhar Behera, Pawan Goyal.
_Evaluating Neural Word Embeddings for Sanskrit._ In Proceedings of the World
Sanskrit Conference, WSC 2022, Canberra, Australia. [Paper] — [Code]

  9. 9.

Jivnesh Sandhan, Amrith Krishna, Pawan Goyal, and Laxmidhar Behera.
_Revisiting the role of feature engineering for compound type identification
in Sanskrit._ In Proceedings of the 6th International Sanskrit Computational
Linguistics Symposium, ISCLS 2019, Kharagpur, India. [Paper] — [Code]

###### Acknowledgements.

I would like to express my sincere gratitude to my advisor, Dr. Laxmidhar
Behera, for inspiring me to work in Sanskrit Computational Linguistics (SCL)
and for providing me with numerous opportunities to explore and collaborate.
Dr. Behera’s guidance, vision, and mentorship have been invaluable throughout
my journey, and without his support, this thesis would not have been possible.
Additionally, I would like to extend my gratitude to Dr. Pawan Goyal, my
mentor, for his knowledge, consideration, and easy-going nature. He has been a
constant source of support and guidance, and his contributions have been
instrumental in the completion of this thesis. My association with Dr. Amrith
Krishna during the initial phase of PhD has helped me shape my perspective
toward research. I extend my gratitude to Amba Kulkarni, Gerard Huet, and
Oliver Hellwig for their contributions to the SCL community. I am grateful to
Rathin Singha, Narein Rao, Ashish Gupta, Anshul Agarwal, Amruta Barbarikar and
other collaborators who selflessly contributed to the works discussed in this
thesis. I would also like to thank all collaborators and reviewers for their
comments and feedback. I am grateful to the Bhaktivedanta family (BVC) for
introducing me to the teachings of H.D.G. A. C. Bhaktivedanta Swami
Prabhupada. I owe a debt of gratitude to my BVC friends, and in particular, I
want to thank Hariom Birla for his invaluable help, patience, and emotional
support. In addition, I am deeply appreciative of my parents, sister-in-law,
and brother for their unwavering love and encouragement.

Dedicated to My Beloved Teachers