# Energy spectrum and effective mass using a non-local 3-body interaction

Alexandros Gezerlis1 and G. F. Bertsch1,2 1Department of Physics, University
of Washington, Seattle, WA 98195–1560 USA  2Institute for Nuclear Theory,
University of Washington, Seattle, WA 98195–1560 USA

###### Abstract

We recently proposed a nonlocal form for the 3-body induced interaction that
is consistent with the Fock space representation of interaction operators but
leads to a fractional power dependence on the density. Here we examine the
implications of the nonlocality for the excitation spectrum. In the two-
component weakly interacting Fermi gas, we find that it gives an effective
mass that is comparable to the one in many-body perturbation theory. Applying
the interaction to nuclear matter, it predicts a huge enhancement to the
effective mass. Since the saturation of nuclear matter is partly due to the
induced 3-body interaction, fitted functionals should treat the effective mass
as a free parameter, unless the two- and three-body contributions are
determined from basic theory.

Zero- and finite-range nuclear energy-density functionals have a long history
and a successful track record, allowing the description of heavy nuclei
without region-specific parametrizations.Bender:2003  The most popular
functionals use interactions that depend on fractional powers of density,
which causes serious problems when one tries to extend the theory to include
correlations Duguet:2003 ; Robledo:2007 ; Duguet:2009 . Ideally, to avoid
these problems the effective theory should be based on a Fock-space
Hamiltonian operator. As a partial solution, one can consider energy
functionals of integral powers of the density; there have been a number of
attempts to construct functionals of this kind Baldo:2010 ; Erler:2010 .

With this in mind, we recently proposed a nonlocal effective three-body
interaction that achieves a fractional dependence on density using only
integral powers of the density matrix Gezerlis:2010a . This was derived using
the many-body perturbation theory of the dilute, weakly interacting Fermi gas.
By construction, the interaction gives the correct Lee-Yang contribution
Lee:1957  to the Fermi-gas energy to order $\rho^{7/3}$. The interaction was
validated for finite systems in a harmonic trap by comparing with numerically
accurate calculations performed by the Green’s Function Monte Carlo method. At
very weak coupling, the new operator led to results that are identical with
the Lee-Yang dependence, while for stronger coupling the contribution of the
new 3-body operator turned out to be more repulsive than in Lee-Yang (though
with the same power-law behavior), thus providing a more accurate description
of the microscopic simulation.

Using the new interaction, the internal energy of the dilute Fermi gas can be
expressed in terms of the one-body density matrix as:

$\begin{split}E&=\frac{\hbar^{2}k_{F}^{2}}{m}\int
d^{3}r_{1}\,\left(\frac{\nabla_{r_{1}}\cdot\nabla_{r_{2}}}{2}\rho({\bf
r_{1},r_{2}})|_{{\bf r_{1}=r_{2}}}+4\pi a\rho_{\downarrow}({\bf r_{1}},{\bf
r_{1}})\rho_{\uparrow}({\bf r_{1}},{\bf r_{1}})\right)\\\ &+C\int
d^{3}r_{1}d^{3}r_{2}\,\frac{\rho_{\uparrow}({\bf
r_{1},r_{2}})\rho_{\downarrow}({\bf r_{1},r_{2}})\rho({\bf
r_{1},r_{2}})}{|{\mathbf{r}_{1}}-{\mathbf{r}_{2}}|}.\end{split}$ (1)

The subscript $i$ on $\rho_{i}$ denotes the spin state, $\rho$ without a
subscript is the total density. Also, if $a$ is the scattering length
associated with the two-body interaction, $C$ is a constant proportional to
$a^{2}$. The value of $C$ was derived in Ref. Gezerlis:2010a  by demanding
that the formula reproduce the Lee-Yang energy in the uniform Fermi gas. The
energy $E$ or energy density $\cal E$ is given by

$\frac{E}{A}=\frac{\cal
E}{\cal\rho}=\frac{\hbar^{2}k_{F}^{2}}{2m}\left(\frac{3}{5}+\frac{2}{3\pi}ak_{F}+\frac{4}{35\pi^{2}}\left(11-2\ln
2\right)\left(ak_{F}\right)^{2}\right)~{}.$ (2)

It is convenient for later use to rederive from Eq. (1) the formula for $C$,
which was originally derived from the perturbation theory in a momentum space
representation. We insert in Eq. (1) the free Fermi gas density matrix and
drop one of the integrals to get the energy density. The Fermi gas density
matrix only depends on the relative coordinate ${\bf r}={\bf r_{1}}-{\bf
r_{2}}$ and can be written

$\rho_{0i}({\bf r})=\int_{0}^{k_{F}}\frac{d^{3}k}{(2\pi)^{3}}e^{i{\bf
k}\cdot{\bf r}}=\rho_{0i}(0)F(k_{F}r)$ (3)

where $F(x)=3j_{1}(x)/x$. The integral to be evaluated may be expressed

$\frac{E_{3}}{A}=C\frac{24\pi^{3}}{k_{F}^{5}}\rho_{0i}^{3}(0)\int_{0}^{\infty}xdxF^{3}(x)$
(4)

The integration can be performed analytically; the final result for the
strength parameter $C$ is

$C={\hbar^{2}a^{2}\over m}{64\pi(11-\ln 2)\over 3(92-27\ln 3)}$ (5)

We now calculate the single-particle energy with functional Eq. (1) and the
value of $C$ fixed by Eq. (5). The density matrix with a particle added to the
Fermi sea is

$\rho_{i}({\bf r)}=\rho_{0i}({\bf r})+\rho_{ki}e^{i{\bf k}\cdot{\bf r}}$ (6)

The second term represents a particle of momentum $k$ in spin state $i$; the
coefficient $\rho_{ki}$ has dimensions of density. With this definition the
single-particle energy may be computed as

$\varepsilon_{i}(k)=\frac{d{\cal E}}{d\rho_{ki}}\Big{|}_{\rho_{ki}=0}.$ (7)

Carrying out the differentiation on the energy expression Eq. (1), the first
term gives the usual kinetic energy and the second term is independent of $k$.
The third term is rather complicated. Assuming equal populations of spin up
and spin down in $\rho_{0}$, the derivative is given by the integral:

$\varepsilon_{3}(k)=3C\int d^{3}r\,e^{i{\bf k}\cdot({\bf
r})}\frac{\rho_{0i}^{2}({\bf r})}{r}=3C{4\pi\over
k_{F}^{2}}\rho_{0i}^{2}(0)\int_{0}^{\infty}dx~{}x\,\,j_{0}\Big{(}{k\over
k_{F}}x\Big{)}F^{2}(x).$ (8)

The factor of 3 is a direct consequence of the spin structure of the numerator
in the third term of Eq. (1). The integral can also be expressed analytically:

$\begin{split}\int_{0}^{\infty}dx~{}x\,j_{0}(yx)F^{2}(x)&=\frac{3}{160}\Big{[}4(22+y^{2})+\frac{(y-2)^{3}}{y}(y^{2}+6y+4)\log(2-y)\\\
&-2y^{2}(y^{2}-20)\log
y+\frac{(y+2)^{3}}{y}(y^{2}-6y+4)\log(2+y)\Big{]},\end{split}$ (9)

where $y=k/k_{F}$. The 3-body contribution to the single-particle energy
$\varepsilon_{3}$ is plotted in Fig. 1, with the dimensionful factors divided
out.

Figure 1: Single-particle energy in the dilute Fermi gas, normalized to
$\hbar^{2}a^{2}\rho_{0i}^{2}(0)/mk_{F}^{2}$. The solid line shows result using
the effective 3-body interaction, Eq. (8). The dashed line shows the
contribution to the quasiparticle energy obtained by Galitskii. The dotted
line is the slope of the Galitskii expression.

Galitskii’s expression for the real part of the quasiparticle energy
(Galitskii:1958, , Eq. (34)) is plotted with the same normalization on the
graph. The perfect agreement of the two at the Fermi momentum is not
accidental: the single-particle energy at the Fermi surface is identical to
the chemical potential $\mu$, which can be extracted from the interaction
energy by the formula $\mu=\partial{\cal E}/\partial\rho$. Since we fit the
total 3-body interaction energy to the dilute Fermi gas, the chemical
potential must agree as well.

The momentum-dependence of the single-particle energy gives rise to an
effective mass $m^{*}$ for the quasiparticle spectrum,

$\frac{m^{*}}{m}=\left(1+{m\over\hbar^{2}k_{F}}{\partial\epsilon_{3}(k)\over\partial
k}\Big{|}_{k=k_{F}}\right)^{-1}$ (10)

The derivative in this expression is negative, implying that the effective
mass will be larger than $m$. Fig. 1 also shows the derivative for Galitskii’s
quasiparticle energy, as the straight line (see also Ref. Fetter:1971 ). We
note that the slope for the 3-body single-particle energy is smaller, implying
less of an effective-mass enhancement. Even so, the two results are close
enough in magnitude to motivate the application of the new operator to a
nuclear energy functional.

As stated in the introduction, our main interest is to find an improved
effective Hamiltonian for nuclear structure theory. There is no reliable low-
density expansion in the nuclear many-body problem, and in fact one must
impose some length scale in the interactions to avoid collapse. Nevertheless,
in some formulations there will be a contribution to saturation coming from
the Pauli effects that we are concerned with here. To assess the importance of
the nonlocality, we take $C$ as an adjustable parameter to be fitted in the
functional, similar to the parameter $t_{3}$ of the Skyrme interaction. The
counting of the contributing graphs is different in the four-component Fermi
system than in the two-component case treated by Galitskii, but the scaling
between the total energy and the single-particle energy remains the same under
plausible assumptions about the spin-isospin character of the interaction.
Thus we may use the same formulas, only remembering that in the nuclear
context $\rho_{0i}$ is the density associated with a specific spin-isospin
projection, e.g. neutrons with spin up.

Table 1: Contributions to the energy of 208Pb in density functional theory. The numbers for the Skyrme Ska and Gogny D1S functionals were obtained with the ev8 code Bonche:2005  and the HFBaxial code robledo , respectively. | Ska | D1S
---|---|---
Kinetic | 3863 | 3920
Coulomb direct/exchange | 831/-31 | 832/-31
Spin-orbit | -97 | -105
Central 2B | -12480 | -12783
$t_{3}$ | 6274 | 6530
Total | -1640 | -1637

While we cannot calculate $C$, we can at least put a bound on its value using
the magnitude of the 3-body interaction energy that is obtained from
phenomenological energy functionals. With our form for the interaction, the
relation between the 3-body energy and the effective mass is

$\frac{m^{*}}{m}=\left(1+d\frac{E_{3}/A}{\hbar^{2}k_{F}^{2}/(2m)}\right)^{-1}$
(11)

where $d\approx-1.32$, and the two-body contribution has been omitted.

To see what the scale of the effect would be, we show in Table 1 the various
contributions to the energy of 208Pb found using the Ska Skyrme functional and
the D1S Gogny functional. Both these functionals have the same $\rho^{1/3}$
density-dependent interaction as in the Lee-Yang expansion. One sees that the
decomposition into the two-body and three-body contributions is quite similar,
although the two-body interactions have a very different construction. Eq.
(11) gives a negative effective mass for both functionals, which is of course
unphysical. The two-body nonlocality gives a contribution of the opposite
sign, but not enough to produce an effective mass in the physical range
($m^{*}/m\sim 1$). As mentioned earlier, there must be other 3-body
contributions containing intrinsic length scales in order to achieve nuclear
saturation. However, unless the nonlocalities can be calculated in detail, it
does not seem feasible to derive a theoretical effective mass to be used with
an effective Hamiltonian. The extreme sensitivity to the induced 3-body
interaction suggests that the effective mass may need to be an unconstrained
free parameter when constructing an effective Hamiltonian for mean-field
theory and its extensions.

In summary, we have applied our newly proposed non-local effective 3-body
operator to the study of the single-particle excitation spectrum, both at weak
coupling and at strong coupling. At weak coupling we see that the new operator
has similar behavior to that found by Galitskii. We also applied the new
operator to the nuclear case. The effects pointed to are very large, implying
that the effective mass cannot be simply taken to be reduced from the bare
mass based on mean-field theory: as long as no dependable ab initio results
are available, the effective mass should also be treated like an undetermined
parameter.

We would like to thank L. Robledo for providing us with the energies of 208Pb
for the Gogny D1S interaction. This work was supported by DOE Grant Nos. DE-
FG02-97ER41014 and DE-FG02-00ER41132.

## References

  * (1) M. Bender, P.-H. Heenen, and P.-G. Reinhard, Rev. Mod. Phys. 75, 121 (2003).
  * (2) T. Duguet and P. Bonche, Phys. Rev. C 67, 054308 (2003).
  * (3) L. M. Robledo, Int. J. Mod. Phys. E 16, 337 (2007).
  * (4) T. Duguet, M. Bender, K. Bennaceur, D. Lacroix, and T. Lesinski, Phys. Rev. C 79, 044320 (2009).
  * (5) M. Baldo, L. M. Robledo, P. Schuck, X. Viñas, J. Phys. G 37, 064015 (2010).
  * (6) J. Erler, P. Klüpfel, P.-G. Reinhard, Phys. Rev. C 82, 044307 (2010).
  * (7) A. Gezerlis and G. F. Bertsch, Phys. Rev. Lett. 105, 212501 (2010).
  * (8) T. D. Lee and C. N. Yang, Phys. Rev. 105, 1119 (1957).
  * (9) V. M. Galitskii, Sov. Phys. (JETP) 34, 151 (1958).
  * (10) A. L. Fetter and J. D. Walecka, Quantum Theory of Many-Particle Systems (McGraw-Hill, New York, 1971).
  * (11) P. Bonche, H. Flocard, and P.H. Heenen, Comp. Phys. Comm. 171, 49 (2005).
  * (12) ??


# Toughness and normalized Laplacian eigenvalues of graphs

Xueyi Huanga,b, Kinkar Chandra Dasb,111Corresponding author.000 _E-mail
address:_<EMAIL_ADDRESS>(X. Huang<EMAIL_ADDRESS>(K. C. Das),
<EMAIL_ADDRESS>(S. Zhu). and Shunlai Zhua
aSchool of Mathematics, East China University of Science and Technology,
Shanghai 200237, P.R. China
bDepartment of Mathematics, Sungkyunkwan University,
Suwon 16419, Republic of Korea

###### Abstract

Given a connected graph $G$, the toughness $\tau_{G}$ is defined as the
minimum value of the ratio $|S|/\omega_{G-S}$, where $S$ ranges over all
vertex cut sets of $G$, and $\omega_{G-S}$ is the number of connected
components in the subgraph $G-S$ obtained by deleting all vertices of $S$ from
$G$. In this paper, we provide a lower bound for the toughness $\tau_{G}$ in
terms of the maximum degree, minimum degree and normalized Laplacian
eigenvalues of $G$. This can be viewed as a slight generalization of Brouwer’s
toughness conjecture, which was confirmed by Gu (2021). Furthermore, we give a
characterization of those graphs attaining the two lower bounds regarding
toughness and Laplacian eigenvalues provided by Gu and Haemers (2022).

Keywords: Toughness, Normalized Laplacian eigenvalue, Algebraic connectivity.

2010 MSC: 05C50, 05C42

##  1 Introduction

Let $G$ be an undirected simple graph with vertex set $V_{G}$ ($|V_{G}|=n$).
For any $v\in V_{G}$, we denote by $d_{v}$ the degree of $v$, that is, the
number of vertices adjacent to $v$ in $G$. In particular, let $\Delta_{G}$ and
$\delta_{G}$ denote the maximum degree and minimum degree of vertices of $G$,
respectively. For any subset $S$ of $V_{G}$, we denote by $\nu_{S}=\sum_{v\in
S}d_{v}$ the volume of $S$ in $G$, $G[S]$ the subgraph of $G$ induced by $S$,
and $G-S$ the subgraph of $G$ induced by $V_{G}\setminus S$. For $X,Y\subseteq
V_{G}$, we denote by $e_{X,Y}$ the number of edges between $X$ and $Y$
(counting each edge with both ends in $X\cap Y$ twice), and $e_{X}$ the number
of edges of which the both ends are contained in $X$. Clearly,
$e_{X,X}=2e_{X}$. Also, the join of two graphs $G$ and $H$, denoted by $G\vee
H$, is the graph obtained from $G\cup H$ by connecting each vertex of $G$ to
all vertices of $H$.

The adjacency matrix of $G$ is the $(0,1)$-matrix $A_{G}=(a_{uv})_{u,v\in
V_{G}}$ with $a_{uv}=1$ if and only if $u,v$ are distinct and adjacent. Let
$D_{G}=\mathrm{diag}\\{d_{v}:v\in V_{G}\\}$ denote the diagonal degree matrix
of $G$. Then we call $L_{G}=D_{G}-A_{G}$ and
$\mathcal{L}_{G}=D_{G}^{-1/2}L_{G}D_{G}^{-1/2}$ the Laplacian matrix and
normalized Laplacian matrix of $G$, respectively. Here we always take
$(D_{G}^{-1/2})_{vv}=0$ if $v$ is an isolated vertex of $G$. The eigenvalues
of $A_{G}$, $L_{G}$ and $\mathcal{L}_{G}$ are called the adjacency
eigenvalues, Laplacian eigenvalues and normalized Laplacian eigenvalues of
$G$, and denoted by
$\lambda_{1}^{G}\geq\lambda_{2}^{G}\geq\cdots\geq\lambda_{n}^{G}$,
$\mu_{1}^{G}\geq\mu_{2}^{G}\geq\cdots\geq\mu_{n}^{G}$ and
$\xi_{1}^{G}\geq\xi_{2}^{G}\geq\cdots\geq\xi_{n}^{G}$, respectively. It is
easy to see that $\mu_{n}^{G}=\xi_{n}^{G}=0$, and $\xi_{1}^{G}\leq 2$ with
equality if and only if $G$ contains at least one nontrivial bipartite
component [6]. Additionally, $\mu_{1}^{G}$ and $\mu_{n-1}^{G}$ are called the
Laplacian spectral radius and algebraic connectivity of $G$, respectively.

In 1973, Chvátal [8] proposed the concept of graph toughness. For a non-
complete connected graph $G$, the toughness $\tau_{G}$ is defined as
$\tau_{G}=\min_{S\subseteq V_{G},\,\omega_{G-S}\geq 2}{|S|/\omega_{G-S}}$,
where $\omega_{G-S}$ represents the number of connected components in $G-S$.
For convention, we define the toughness of a complete graph $K_{n}$ as
$\tau_{K_{n}}=\infty$. In the original paper [8], Chvátal proved that
$\tau_{G}\geq 1$ if $G$ is a hamiltonian graph. Over the past decades,
toughness has been shown to be closely related to cycles, matchings, factors,
spanning trees, and various structural parameters of graphs [2].

In 1995, Alon [1] first introduced adjacency eigenvalues to the study of graph
toughness. He proved that $\tau_{G}>(d^{2}/(d\lambda+\lambda^{2})-1)/3$ if $G$
is a connected $d$-regular graph, where
$\lambda=\max\\{|\lambda_{2}^{G}|,|\lambda_{n}^{G}|\\}$. Almost at the same
time, Brouwer [3, 4] showed that every connected $d$-regular graph $G$
satisfies $\tau_{G}>d/\lambda-2$, and further conjectured that $\tau_{G}\geq
d/\lambda-1$, which is known as Brouwer’s toughness conjecture. After then,
some efforts of several researchers were made for solving this conjecture [9,
10, 14]. Very recently, Gu [15] confirmed Brouwer’s toughness conjecture.

In this paper, inspired by the work of Gu [15], we first consider to provide a
lower bound for the toughness of general graphs in terms of the maximum
degree, minimum degree and normalized Laplacian eigenvalues.

######  Theorem 1.1.

Let $G$ be a connected graph on $n$ vertices with $\Delta_{G}=\Delta$ and
$\delta_{G}=\delta$. Then

$\tau_{G}\geq\max\left\\{\frac{1}{\Delta},\frac{\Delta+\delta}{\Delta
n},\frac{\delta(\xi+1)}{\Delta\xi}-2\right\\},$

where $\xi=\max\\{|1-\xi_{1}^{G}|,|1-\xi_{n-1}^{G}|\\}$.

If $G$ is $d$-regular, then $\Delta=\delta=d$ and $\xi=\lambda/d$. By Theorem
1.1,

$\tau_{G}\geq\frac{\delta(\xi+1)}{\Delta\xi}-2=\frac{1}{\xi}-1=\frac{d}{\lambda}-1,$

which coincides with the result of Brouwer’s toughness conjecture. This
suggests that Theorem 1.1 can be viewed as a slight generalization of
Brouwer’s toughness conjecture.

Recently, Gu and Haemers [16] presented two lower bounds for the toughness of
a graph by using Laplacian eigenvalues.

######  Theorem 1.2 ([16]).

Let $G$ be a connected graph on $n$ vertices with $\delta_{G}=\delta$. Then

$\tau_{G}\geq\frac{\mu_{1}^{G}\mu_{n-1}^{G}}{n(\mu_{1}^{G}-\delta)}$ (1)

and

$\tau_{G}\geq\frac{\mu_{n-1}^{G}}{\mu_{1}^{G}-\mu_{n-1}^{G}}.$ (2)

In the second part of this paper, we focus on giving a characterization of
those graphs attaining the lower bounds of Theorem 1.2.

######  Theorem 1.3.

Let $G$ be a connected graph of order $n$ with $\delta_{G}=\delta$. Then each
equality in (1) and (2) holds if and only if $G\cong H\vee(n-\delta)K_{1}$,
where $1\leq\delta\leq n-2$ and $H$ is any graph of order $\delta$ with
$\mu_{\delta-1}^{H}\geq 2\delta-n$.

According to (2) and Theorem 1.3, we obtain an upper bound for the algebraic
connectivity of a graph in terms of the toughness and Laplacian spectral
radius, and characterize the extremal graphs.

######  Corollary 1.1.

Let $G$ be a connected graph on $n$ vertices with Laplacian spectral radius
$\mu_{1}^{G}$ and toughness $\tau_{G}$. Then

$\mu_{n-1}^{G}\leq\frac{\tau_{G}}{\tau_{G}+1}\,\mu_{1}^{G}$

with equality if and only if $G\cong H\vee(n-\delta)K_{1}$, where
$1\leq\delta\leq n-2$ and $H$ is any graph of order $\delta$ with
$\mu_{\delta-1}^{H}\geq 2\delta-n$.

##  2 Preliminaries

In this section, we review some basic lemmas for latter use.

######  Lemma 2.1 ([5, 15]).

Let $n_{1},\ldots,n_{p}$ be positive integers such that
$\sum_{i=1}^{p}n_{i}\leq 2p-1$. Then for every integer $\ell$ with
$0\leq\ell\leq\sum_{i=1}^{p}n_{i}$, there exists some
$\mathcal{I}\subset\\{1,\ldots,p\\}$ such that
$\sum_{i\in\mathcal{I}}n_{i}=\ell$.

Recall that $\nu_{S}(S)=\sum_{v\in S}d_{v}$ denotes the volume of $S$
($S\subseteq V_{G}$) in $G$.

######  Lemma 2.2 (Irregular Expander Mixing Lemma, [7]).

Let $G$ be a graph on $n$ vertices. For any two subsets $X$ and $Y$ of
$V=V_{G}$, we have

$\left|e_{X,Y}-\frac{\nu_{X}\nu_{Y}}{\nu_{V}}\right|\leq\xi\cdot\sqrt{\nu_{X}\nu_{Y}\left(1-\frac{\nu_{X}}{\nu_{V}}\right)\left(1-\frac{\nu_{Y}}{\nu_{V}}\right)},$

where $\xi=\max\\{|1-\xi_{1}^{G}|,|1-\xi_{n-1}^{G}|\\}$. In particular,

$\left|2e_{X}-\frac{\nu_{X}^{2}}{\nu_{V}}\right|\leq\xi\cdot\nu_{X}\left(1-\frac{\nu_{X}}{\nu_{V}}\right).$

Let $G$ be a graph. An independent set of $G$ is a set of vertices which are
pairwise non-adjacent. The independent number $\alpha_{G}$ is the maximum
cardinality among all independent sets of $G$. The following three lemmas
provide different kinds of upper bounds for $\alpha_{G}$.

######  Lemma 2.3 ([21], Theorem 3.2).

Let $G$ be a graph on $n$ vertices with $\Delta_{G}=\Delta$ and
$\delta_{G}=\delta$. Then

$\alpha_{G}\leq\frac{n\Delta}{\Delta+\delta}.$

######  Lemma 2.4.

Let $G$ be a graph on $n$ vertices and $m$ edges with $\delta_{G}=\delta$.
Then

$\alpha_{G}\leq\frac{2m\xi}{\delta(\xi+1)},$

where $\xi=\max\\{|1-\xi_{1}^{G}|,|1-\xi_{n-1}^{G}|\\}$.

###### Proof.

Let $I$ be a maximum independent set of $G$, that is, $|I|=\alpha_{G}$. Then
$e_{I}=0$, and by Lemma 2.2,

$\frac{\nu_{I}^{2}}{\nu_{V}}\leq\xi\cdot\nu_{I}\left(1-\frac{\nu_{I}}{\nu_{V}}\right),$

which implies that

$\nu_{I}\leq\frac{\xi}{\xi+1}\cdot\nu_{V}.$

Combining this with $\nu_{I}\geq\delta|I|=\delta\alpha_{G}$ and $\nu_{V}=2m$
yields that

$|I|\leq\frac{2m\xi}{\delta(\xi+1)}.$

The result follows. $\Box$

######  Remark 2.1.

It is worth mentioning that Lemma 2.4 can be also deduced from the main result
of [18].

######  Lemma 2.5 ([13, 20]).

Let $G$ be a graph on $n$ vertices with at least one edge and
$\delta_{G}=\delta$. Then

$\alpha_{G}\leq\frac{n(\mu_{1}^{G}-\delta)}{\mu_{1}^{G}}.$ (3)

Furthermore, if $I$ is an independent set of $G$ such that the equality in (3)
holds, then the bipartite subgraph $G_{1}$ of $G$ induced by those edges
between $I$ and $V_{G}\setminus I$ is
$(\delta,\mu_{1}^{G}-\delta)$-semiregular, that is, each vertex of $I$ has
degree $\delta$ and each vertex of $V_{G}\setminus I$ has degree
$\mu_{1}^{G}-\delta$ in $G_{1}$.

The vertex connectivity $\kappa_{G}$ of a non-complete graph $G$ is the
minimum cardinality of $S$ ($S\subset V_{G}$) such that $G-S$ is disconnected.
Clearly, $\kappa_{G}\leq\delta_{G}$. A well-known result of Fiedler [12]
states that each non-complete connected graph $G$ of order $n$ satisfies
$\mu_{n-1}^{G}\leq\kappa_{G}$. In [19], Kirkland, Molitierno, Neumann and
Shader characterized the structure of the graphs satisfying
$\mu_{n-1}^{G}=\kappa_{G}$. From their proof, we can deduce the following
result.

######  Lemma 2.6 ([19], Theorem 2.1).

Let $G$ be a non-complete connected graph on $n$ vertices. If
$\mu_{n-1}^{G}=\kappa_{G}=\kappa$, then for any vertex cut set $S$ of size
$\kappa$, we have $G=G[S]\vee(G-S)$ and $\mu_{\kappa-1}^{G[S]}\geq 2\kappa-n$.
Conversely, if $G$ is of the form $G_{1}\vee G_{2}$, where $G_{1}$ is a graph
on $\kappa$ vertices with $\mu_{\kappa-1}^{G_{1}}\geq 2\kappa-n$ and $G_{2}$
is a disconnected graph on $n-\kappa$ vertices, then
$\mu_{n-1}^{G}=\kappa_{G}=\kappa$.

######  Lemma 2.7 ([11], Theorem 7.1.9).

Let $G$ be a graph of order $n$ and $H$ be a graph of order $n^{\prime}$. Then
the Laplacian eigenvalues of $G\vee H$ are
$n+n^{\prime},\mu_{1}^{G}+n^{\prime},\ldots,\mu_{n-1}^{G}+n^{\prime},n+\mu_{1}^{H},\ldots,n+\mu_{n^{\prime}-1}^{H},0$.

######  Lemma 2.8 ([16, 17]).

Let $G$ be a graph of order $n$, and let $S$ be a vertex cut set of $G$.
Suppose that $V_{G}\setminus S=X\cup Y$ with $X\cap Y=\emptyset$ and
$|X|\leq|Y|$. Then

$|X|\leq\frac{\mu_{1}^{G}-\mu_{n-1}^{G}}{2\mu_{1}^{G}}\cdot
n~{}\mbox{and}~{}|S|\geq\frac{2\mu_{n-1}^{G}}{\mu_{1}^{G}-\mu_{n-1}^{G}}\cdot|X|,$

where each equality holds only if $|X|=|Y|$.

##  3 Proof of Theorems 1.1 and 1.3

Proof of Theorem 1.1. As $\tau_{K_{n}}=\infty$ by definition, we can assume
that $G\not\cong K_{n}$. Let $S$ be a vertex cut set of $G$ such that
$\tau_{G}=|S|/\omega_{G-S}$. Let $\tau=\tau_{G}$, $\omega=\omega_{G-S}$ and
$U=V_{G-S}$. Then $\omega\geq 2$, $|S|=\tau\omega\leq n-2$ and
$|U|=n-\tau\omega$. Clearly, $\omega\leq
e_{S,U}\leq|S|\cdot\Delta=\tau\omega\cdot\Delta$, we have

$\tau\geq\frac{1}{\Delta}.$

Also, by taking exactly one vertex from each component of $G-S$, we obtain an
independent set of size $\omega$. Then, by Lemma 2.3,

$\omega\leq\alpha_{G}\leq\frac{n\Delta}{\Delta+\delta},$

which gives that

$\tau=\frac{|S|}{\omega}\geq\frac{1}{\omega}\geq\frac{\Delta+\delta}{n\Delta}.$

Thus it remains to prove that

$\tau\geq\frac{\delta(\xi+1)}{\Delta\xi}-2.$

If $\xi\geq\displaystyle{\frac{\delta}{2\Delta-\delta}}$, then
$\displaystyle{\frac{\delta(\xi+1)}{\Delta\xi}}\leq 2$ and there is nothing to
prove. In what follows, we always assume that
$\xi<\displaystyle{\frac{\delta}{2\Delta-\delta}}$, i.e.,
$\displaystyle{\frac{\delta(\xi+1)}{\Delta\xi}}>2$. By Lemma 2.4,

$\omega\leq\alpha_{G}\leq\frac{2m\xi}{\delta(\xi+1)}\leq\frac{n\Delta\xi}{\delta(\xi+1)}<\frac{n}{2}.$
(4)

If $|U|\leq\displaystyle{\frac{2n\Delta\xi}{\delta(\xi+1)}}$, then from (4) we
obtain

$\tau=\frac{n-|U|}{\omega}\geq\left(n-\frac{2n\Delta\xi}{\delta(\xi+1)}\right)\cdot\frac{\delta(\xi+1)}{n\Delta\xi}=\frac{\delta(\xi+1)}{\Delta\xi}-2,$

as desired. Now suppose
$|U|>\displaystyle{\frac{2n\Delta\xi}{\delta(\xi+1)}}$. Then it follows from
(4) that

$|U|\geq 2\omega+1.$ (5)

Let $U_{1},U_{2},\ldots,U_{\omega}$
($|U_{1}|\leq|U_{2}|\leq\cdots\leq|U_{\omega}|$) be the sets of vertices of
the connected components of $G-S$. The following discussion is divided into
two cases.

Case 1. $\sum_{i=1}^{\omega-1}|U_{i}|=\omega-1$.

In this situation, each $U_{i}$ ($1\leq i\leq\omega-1$) contains only one
vertex. Let $W=\cup_{i=1}^{\omega-1}U_{i}$. Then $|W|=\omega-1$ and
$e_{W,U}=0$. By Lemma 2.2,

$\frac{\nu_{W}\nu_{U}}{\nu_{V}}\leq\xi\cdot\sqrt{\nu_{W}\nu_{U}\left(1-\frac{\nu_{W}}{\nu_{V}}\right)\left(1-\frac{\nu_{U}}{\nu_{V}}\right)}\leq\xi\cdot\sqrt{\nu_{W}\nu_{U}\left(1-\frac{\nu_{U}}{\nu_{V}}\right)},$

which leads to

$\frac{\nu_{W}\nu_{U}}{\nu_{V}\cdot\xi^{2}}\leq\nu_{V}-\nu_{U}=\nu_{S}.$ (6)

Note that $\nu_{W}\geq\delta|W|$, $\nu_{U}\geq\delta|U|$, $\nu_{V}\leq\Delta
n$ and $\nu_{S}\leq\Delta|S|=\Delta\tau\omega$. According to (6), we obtain

$\tau\geq\frac{\delta^{2}|W||U|}{n\Delta^{2}\xi^{2}\omega}=\frac{\omega-1}{\omega}\cdot\frac{\delta^{2}|U|}{n\Delta^{2}\xi^{2}}=\left(1-\frac{1}{\omega}\right)\cdot\frac{\delta^{2}|U|}{n\Delta^{2}\xi^{2}}\geq\frac{\delta^{2}|U|}{2n\Delta^{2}\xi^{2}}.$

Combining this with $|U|>\displaystyle{\frac{2n\Delta\xi}{\delta(\xi+1)}}$
yields that

$\displaystyle\tau$
$\displaystyle>\frac{\delta^{2}}{2n\Delta^{2}\xi^{2}}\cdot\frac{2n\Delta\xi}{\delta(\xi+1)}=\frac{\delta}{\Delta}\left(\frac{1}{\xi}-\frac{1}{\xi+1}\right)\geq\frac{\delta}{\Delta}\left(\frac{1}{\xi}-1\right)$
$\displaystyle\geq\frac{\delta}{\Delta}\left(\frac{1}{\xi}-\left(\frac{2\Delta}{\delta}-1\right)\right)=\frac{\delta(\xi+1)}{\Delta\xi}-2,$

as desired.

Case 2. $\sum_{i=1}^{\omega-1}|U_{i}|\geq\omega$.

By using the same method as in [15, Claim 2], we can obtain the following
claim. For the purpose of review, we write the proof again.

######  Claim 1.

There exists some $\mathcal{I}\subset[\omega]=\\{1,2,\cdots,\omega\\}$ such
that $R_{\mathcal{I}}=\cup_{i\in\mathcal{I}}U_{i}$ and
$T_{\mathcal{I}}=U\setminus
R_{\mathcal{I}}=\cup_{i\in[\omega]\setminus\mathcal{I}}U_{i}$ satisfy
$e_{R_{\mathcal{I}},T_{\mathcal{I}}}=0$ and
$|R_{\mathcal{I}}|,|T_{\mathcal{I}}|\geq\omega$.

Proof of Claim 1. We assert that $|U_{\omega}|\geq 3$, since otherwise we have
$|U|\leq 2\omega$, contrary to (5). Also, if $|U_{\omega}|\geq\omega$ then we
can take $\mathcal{I}=\\{1,\ldots,\omega-1\\}$, and the result follows
immediately. Thus it remains to consider that $3\leq|U_{\omega}|\leq\omega-1$.
Let $\ell=\omega-|U_{\omega}|$. Then $1\leq\ell\leq\omega-3$. If
$\sum_{i=1}^{\omega-1}|U_{i}|\leq 2\omega-3$, by Lemma 2.1, there exists some
$\mathcal{I}_{1}\subset\\{1,\ldots,\omega-1\\}$ such that
$\sum_{i\in\mathcal{I}_{1}}|U_{i}|=\ell$. Take
$\mathcal{I}=\mathcal{I}_{1}\cup\\{\omega\\}$. Then we see that
$|R_{\mathcal{I}}|=\ell+|U_{\omega}|=\omega$,
$|T_{\mathcal{I}}|=|U|-|R_{\mathcal{I}}|\geq\omega+1$ by (5), and
$e_{R_{\mathcal{I}},T_{\mathcal{I}}}=0$, as required. If
$\sum_{i=1}^{\omega-1}|U_{i}|>2\omega-3$, let $U_{i}^{\prime}$ be a nonempty
subset of $U_{i}$ ($i=1,\ldots,\omega-1$) such that
$\sum_{i=1}^{\omega-1}|U_{i}^{\prime}|=2\omega-3$. Again by Lemma 2.1, there
exists some $\mathcal{I}_{1}\subset\\{1,\ldots,\omega-1\\}$ such that
$\sum_{i\in\mathcal{I}_{1}}|U_{i}^{\prime}|=\ell$. Let
$\mathcal{I}=\mathcal{I}_{1}\cup\\{\omega\\}$. Then we see that
$|R_{\mathcal{I}}|=\sum_{i\in\mathcal{I}_{1}}|U_{i}|+|U_{\omega}|\geq\sum_{i\in\mathcal{I}_{1}}|U_{i}^{\prime}|+|U_{\omega}|=\ell+|U_{\omega}|=\omega$,
$|T_{\mathcal{I}}|=\sum_{i\in[\omega]\setminus\mathcal{I}}|U_{i}|\geq\sum_{i\in[\omega]\setminus\mathcal{I}}|U_{i}^{\prime}|=2\omega-3-\ell\geq
2\omega-3-(\omega-3)=\omega$, and $e_{R_{\mathcal{I}},T_{\mathcal{I}}}=0$, as
desired. $\Box$

Let $\mathcal{I}$ be the subset of $[\omega]$ guaranteed by Claim 1, and let
$R=R_{\mathcal{I}}$ and $T=T_{\mathcal{I}}$. Since $e_{R,T}=0$, by Lemma 2.2,
we have

$\frac{\nu_{R}\nu_{T}}{\nu_{V}}\leq\xi\cdot\sqrt{\nu_{R}\nu_{T}\left(1-\frac{\nu_{R}}{\nu_{V}}\right)\left(1-\frac{\nu_{T}}{\nu_{V}}\right)},$

or equivalently,

$\nu_{R}\,\nu_{T}\leq\xi^{2}(\nu_{V}-\nu_{R})\,(\nu_{V}-\nu_{T}).$ (7)

Without loss of generality, suppose that $\nu_{R}\leq\nu_{T}$. Then (7)
implies that

$\nu_{R}^{2}\leq\xi^{2}(\nu_{V}-\nu_{R})^{2},$

that is,

$\nu_{R}\leq\xi(\nu_{V}-\nu_{R}).$

Therefore,

$\nu_{R}\leq\frac{\xi}{\xi+1}\nu_{V}.$ (8)

Note that $\nu_{T}=\nu_{V}-\nu_{S}-\nu_{R}$. Again by (7),

$\nu_{R}(\nu_{V}-\nu_{S}-\nu_{R})\leq\xi^{2}(\nu_{V}-\nu_{R})(\nu_{S}+\nu_{R}),$

which gives that

$\nu_{R}\nu_{V}\leq(\xi^{2}\nu_{V}+(1-\xi^{2})\nu_{R})(\nu_{S}+\nu_{R}).$ (9)

By (8), we see that $(1-\xi^{2})\nu_{R}\leq\xi(1-\xi)\nu_{V}$. Then from (9)
we obtain

$\nu_{R}\nu_{V}\leq\xi\,\nu_{V}(\nu_{S}+\nu_{R}),$

which implies that

$\nu_{S}\geq\left(\frac{1}{\xi}-1\right)\nu_{R}.$

Combining this with $\nu_{S}\leq\Delta|S|$ and $\nu_{R}\geq\delta|R|$ yields
that

$\tau\omega=|S|\geq\left(\frac{1}{\xi}-1\right)\frac{\delta}{\Delta}|R|.$

Hence,

$\tau\geq\left(\frac{1}{\xi}-1\right)\frac{\delta}{\Delta}\cdot\frac{|R|}{\omega}\geq\left(\frac{1}{\xi}-1\right)\frac{\delta}{\Delta}\geq\left(\frac{1}{\xi}-\left(\frac{2\Delta}{\delta}-1\right)\right)\frac{\delta}{\Delta}=\frac{\delta(\xi+1)}{\Delta\xi}-2.$

Therefore, for all situations, we obtain

$\tau\geq\frac{\delta(\xi+1)}{\Delta\xi}-2,$

and the result follows. $\Box$

We now prove Theorem 1.3.

Proof of Theorem 1.3. Let $S$ be a vertex cut set of $G$ such that
$\tau_{G}=|S|/\omega_{G-S}$. Let $\tau=\tau_{G}$, $\omega=\omega_{G-S}$ and
$\kappa=\kappa_{G}$.

If the equality in (1) holds, according to the proof of Theorem 1.2 in [16],
we have $|S|=\kappa=\mu_{n-1}^{G}$ and
$\omega=\alpha_{G}=n(\mu_{1}^{G}-\delta)/\mu_{1}^{G}$. Since
$\mu_{n-1}^{G}=\kappa$, by Lemma 2.6, $G$ is of the form $G[S]\vee(G-S)$,
where $\mu_{\kappa-1}^{G[S]}\geq 2\kappa-n$ and $1\leq\kappa\leq n-2$. Then
$\mu_{1}^{G}=n$ by Lemma 2.7. Also, by taking exactly one vertex from each
component of $G-S$, we obtain an independent set $I$ of size
$\omega=\alpha_{G}=n(\mu_{1}^{G}-\delta)/\mu_{1}^{G}=n-\delta$. Then, by Lemma
2.5, the edges between $I$ and $\bar{I}=V_{G}\setminus I$ induce a
$(\delta,n-\delta)$-semiregular bipartite graph. Considering that
$S\subset\bar{I}$ and $\omega\geq 2$, we claim that all components of $G-S$
are singletons and $\delta=|S|=\kappa=n-\omega$. Thus $G$ can be written as
$H\vee(n-\delta)K_{1}$, where $H=G[S]$ has order $\delta$ ($1\leq\delta\leq
n-2$) and $\mu_{\delta-1}^{H}\geq 2\delta-n$. Conversely, suppose that $G\cong
H\vee(n-\delta)K_{1}$ for some graph $H$ of order $\delta$ ($1\leq\delta\leq
n-2$) with $\mu_{\delta-1}^{H}\geq 2\delta-n$. Then $\delta_{G}=\delta$, and
it is easy to verify that $\mu_{n-1}^{G}=\delta=\kappa_{G}$, $\mu_{1}^{G}=n$
and

$\tau_{G}=\frac{\delta}{n-\delta}=\frac{\mu_{1}^{G}\mu_{n-1}^{G}}{n(\mu_{1}^{G}-\delta)},$

as desired.

Now assume that the equality in (2) holds. We claim that all components of
$G-S$ must be singletons, that is, $n-|S|=\omega$. In fact, if
$n-|S|\geq\omega+1$, according to the proof of Theorem 1.2 in [16], we see
that the components of $G-S$ can be partitioned into two disjoint sets $X$ and
$Y$ such that $|Y|\geq|X|\geq\omega/2$, and the equality in (2) implies that
$|X|=\omega/2$ and $|S|=2\mu_{n-1}^{G}/(\mu_{1}^{G}-\mu_{n-1}^{G})\cdot|X|$.
Then, by Lemma 2.8, we must have $|Y|=|X|$, and so $n-|S|=|X|+|Y|=\omega$, a
contradiction. Therefore,

$\tau_{G}=\frac{\mu_{n-1}^{G}}{\mu_{1}^{G}-\mu_{n-1}^{G}}=\frac{|S|}{\omega}=\frac{n-\omega}{\omega},$

with gives that

$\omega=\frac{n(\mu_{1}^{G}-\mu_{n-1}^{G})}{\mu_{1}^{G}}.$ (10)

Also, by Lemma 2.5,

$\omega\leq\alpha_{G}\leq\frac{n(\mu_{1}^{G}-\delta)}{\mu_{1}^{G}}.$ (11)

Combining (10) and (11), we obtain $\mu_{n-1}^{G}\geq\delta\geq\kappa$, and so
$\mu_{n-1}^{G}=\delta=\kappa$ because we have known that
$\mu_{n-1}^{G}\leq\kappa$. By Lemma 2.6, $G$ must be the join of two graphs.
Then $\mu_{1}^{G}=n$, and $|S|=n-\omega=\kappa=\delta$ by (10). Thus, again by
Lemma 2.6, $G$ is of the form $H\vee(n-\delta)K_{1}$, where $H=G[S]$ has order
$\delta$ ($1\leq\delta\leq n-2$) and $\mu_{\delta-1}^{H}\geq 2\delta-n$.
Conversely, if $G\cong H\vee(n-\delta)K_{1}$ for some graph $H$ of order
$\delta$ ($1\leq\delta\leq n-2$) with $\mu_{\delta-1}^{H}\geq 2\delta-n$, then
$\delta_{G}=\delta$, $\mu_{n-1}^{G}=\delta=\kappa_{G}$, $\mu_{1}^{G}=n$, and

$\tau_{G}=\frac{\delta}{n-\delta}=\frac{\mu_{n-1}^{G}}{\mu_{1}^{G}-\mu_{n-1}^{G}},$

as desired. $\Box$

## Author Contributions

Conceptualization, X.H., K.C.D.; investigation, X.H., K.C.D. and S.Z.; writing
– original draft preparation, X.H., K.C.D. and S.Z.; writing – review and
editing, X.H., K.C.D.

## Declaration of competing interest

The authors declared that they have no conflicts of interest to this work.

## Acknowledgements

The authors are much grateful to two anonymous referees for their valuable
comments on our paper, which have considerably improved the presentation of
this paper. X. Huang is supported by the National Natural Science Foundation
of China (Grant No. 11901540). K. C. Das is supported by National Research
Foundation funded by the Korean government (Grant No. 2021R1F1A1050646). S.
Zhu is supported by the Undergraduate Training Program on Innovation and
Entrepreneurship (Grant No. X202110251335).

## References

  * [1] N. Alon, Tough Ramsey graphs without short cycles, J. Algebraic Combin. 4 (1995) 189–195.
  * [2] D. Bauer, H. J. Broersma, and E. Schmeichel, Toughness of graphs – a survey, Graphs Combin. 22 (2006) 1–35.
  * [3] A. E. Brouwer, Toughness and spectrum of a graph, Linear Algebra Appl. 226/228 (1995) 267–271.
  * [4] A. E. Brouwer, Spectrum and connectivity of graphs, CWI Quarterly 9 (1996) 37–40.
  * [5] A. E. Brouwer, W. H. Haemers, Eigenvalues and perfect matchings, Linear Algebra Appl. 395 (2005) 155–162.
  * [6] F. R. K. Chung, Spectral Graph Theory, Vol. 92 of CBMS Regional Conference Series in Mathematics, AMS Bookstore, 1997.
  * [7] F. Chung, Discrete Isoperimetric Inequalities, in: A. Grigor’yan, S. T. Yau (Eds.), Surveys in Differential Geometry: Eigenvalues of Laplacians and Other Geometric Operators, vol. IX, International Press, 2004, pp. 53–82.
  * [8] V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
  * [9] S. M. Cioabă, X. Gu, Connectivity, toughness, spanning trees of bounded degrees, and spectrum of regular graphs, Czechoslovak Math. J. 66 (2016) 913–924.
  * [10] S. M. Cioabă, W. Wong, The spectrum and toughness of regular graphs, Discrete Appl. Math. 176 (2014) 43–52.
  * [11] D. M. Cvetković, P. Rowlinson, and S. K. Simić, An Introduction to the Theory of Graph Spectra, London Mathematical Society Student Texts 75, Cambridge Univ. Press, Cambridge, 2010.
  * [12] M. Fiedler, Algebraic Connectivity of Graphs, Czechoslovak Math. J. 23 (1973) 298–305.
  * [13] C. D. Godsil, M. W. Newman, Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B 98 (2008) 721–734.
  * [14] X. Gu, Toughness in pseudo-random graphs, European J. Combin. 92 (2021) 103255.
  * [15] X. Gu, A proof of Brouwer’s toughness conjecture, SIAM J. Discrete Math. 35(2) (2021) 948–952.
  * [16] X. Gu, W. H. Haemers, Graph toughness from Laplacian eigenvalues, Algebraic Combin. 5(1) (2022) 53–61.
  * [17] X. Gu, M. Liu, A tight lower bound on the matching number of graphs via Laplacian eigenvalues, European J. Combin. 101 (2022) 103468.
  * [18] J. Harant, S. Richter, A new eigenvalue bound for independent sets, Discrete Math. 338 (10) (2015) 1763–1765.
  * [19] S. Kirkland, J. J. Molitierno, M. Neumann, and B. L. Shader, On graphs with equal algebraic and vertex connectivity, Linear Algebra Appl. 341 (2002) 45–56.
  * [20] M. Lu, H. Liu, and F. Tian, Laplacian spectral bounds for clique and independence numbers of graphs, J. Combin. Theory Ser. B 97 (2007) 726–732.
  * [21] S. O, Y. Shi, and Z. Taoqiu, Sharp upper bounds on the $k$-independence number in graphs with given minimum and maximum degree, Graphs Combin. 37 (2021) 393–408.


# An Overview of Deep Learning Architectures in Few-Shot Learning Domain

Shruti Jadon This work has been as part of writing ”Hands on one-shot Learning
using Python” book. IEEE Member
<EMAIL_ADDRESS>
###### Abstract

Since 2012, Deep learning has revolutionized Artificial Intelligence and has
achieved state-of-the-art outcomes in different domains, ranging from Image
Classification to Speech Generation. Though it has many potentials, our
current architectures come with the pre-requisite of large amounts of data.
Few-Shot Learning (also known as one-shot learning) is a sub-field of machine
learning that aims to create such models that can learn the desired objective
with less data, similar to how humans learn. In this paper, we have reviewed
some of the well-known deep learning-based approaches towards few-shot
learning. We have discussed the recent achievements, challenges, and
possibilities of improvement of few-shot learning based deep learning
architectures. Our aim for this paper is threefold: (i) Give a brief
introduction to deep learning architectures for few-shot learning with
pointers to core references. (ii) Indicate how deep learning has been applied
to the low-data regime, from data preparation to model training. and, (iii)
Provide a starting point for people interested in experimenting and perhaps
contributing to the field of few-shot learning by pointing out some useful
resources and open-source code. Our code is available at
Github:https://github.com/shruti-jadon/Hands-on-One-Shot-Learning

###### Index Terms:

Deep Learning, Neural Networks, Computer Vision, Architectures, Few-Shot
Learning, Siamese Networks, Matching Networks, Optimization, Meta Networks,
Model Agnostic Meta Learning, LSTM Meta learner, Memory Augmented Neural
Networks.

##  I Introduction

Humans learn new things with a very small set of examples e.g. a child can
generalize the concept of a ”Dog” from a single picture but a machine learning
system needs a lot of examples to learn its features. In particular, when
presented with stimuli, people seem to be able to understand new concepts
quickly and then recognize variations on these concepts in future precepts.
Machine learning as a field has been highly successful at a variety of tasks
such as classification, web search, image and speech recognition. Often times
however, these models do not do very well in the regime of low data. This is
the primary motivation behind Few Shot Learning; to train a model with fewer
examples but generalize to unfamiliar categories without extensive retraining.
Deep learning has played an important role in the advancement of machine
learning, but it also requires large data-sets. Different techniques such as
regularization reduces over-fitting in low data regimes, but do not solve the
inherent problem that comes with fewer training examples. Furthermore, the
large size of data-sets leads to slow learning, requiring many weight updates
using stochastic gradient descent. This is mostly due to the parametric aspect
of the model, in which training examples need to be slowly learned by the
model into its parameters. In contrast, many known non-parametric models like
nearest neighbors do not require any training but performance depends on a
sometimes arbitrarily chosen distance metric like the L2 distance.few-shot
learning is an object categorization problem in computer vision. Whereas most
machine learning based object categorization algorithms require training on
hundreds or thousands of images and very large data-sets, few-shot learning
aims to learn information about object categories from one, or only a few,
training images [1].

Figure 1: Sample images of widely used few-Shot learning data-sets:mini-
Imagenet and Omniglot data-set

###  I-A Data-sets for Few-shot learning

Most commonly used data-sets for few shots learning are Mini-ImageNet, and
Omniglot data-set. Omniglot is a data-set is specially designed to compare and
contrast the learning abilities of humans and machines. The data-set contains
handwritten characters of 50 languages (alphabets) with 1623 total characters.
The data-set is divided into a background set and an evaluation set.
Background set contains 30 alphabets (964 characters) and only this set should
be used to perform all learning (e.g. hyper-parameter inference or feature
learning). The remaining 20 alphabets are for pure evaluation purposes only.
Each character is a 105 x 105 greyscale image. There are only 20 samples for
each character, each drawn by a distinct individual(Refer Figure 2).
Mini-Imagenet as the name suggests if the small version of Image-Net data-set,
specifically designed for Few-Shots Learning Image Classification Task, Refer
Figure 1.

##  II Types of Few-Shot Learning Approaches

In recent years, Deep Learning field has advanced a lot, It grew from a simple
Artificial Neural Network classification to LSTM Networks for Language
Modeling and Convolutional Neural Networks for Image processing. Though Deep
Learning has provided many solutions for various problems such as face
recognition, speech recognition etc; but there are still major industries,
which faces the constraints of smaller data-set are yet to experience all the
advantages of Deep Learning, such as the medical and manufacturing industries.
A lot of research has been done in figuring out architectures to learn from
less data regime. In this paper we have explained some widely used few-shot
deep learning architectures and attempted to explain the intuition and logic
behind these architectures. In broader sense, deep learning based few-shot
learning approaches majorly can be divided in 4 categories:

  * •

Data Augmentation Methods.

  * •

Metrics Based Methods.

  * •

Models Based Methods.

  * •

Optimization Based Methods.

##  III Data Augmentation Methods

Data Augmentation is a technique to enhance the amount and enrich the quality
of training data-sets. It has been majorly appreciated by vision deep learning
community to build better models. Image Augmentation methods have evolved in
recent years from simple geometric transformations, color space augmentations
to generative adversarial networks, neural style transfer methods. At present,
a lot of research is being conducted in application of augmentation methods
based on GANs for their practical use-case in medical field community [2]. In
addition to general augmentation techniques, use of Data Augmentation can also
improve the performance of models and expand limited data-sets to take
advantage of the capabilities of big data. Though Data Augmentation is a good
approach to solve less data problem, but it also have some limitations, for
example, If your current data distribution is skewed, that will result in
augmented data distribution to be skewed as well. There is also a high chance
of over-fitting with data augmentation.

##  IV Metrics Based Methods

Metrics Based Methods, as the name suggests is based upon metrics. Metrics
play a very important role in our models, as we know the underlying idea of
all machine learning or deep learning models is mathematics, we convey our
data and objective to machines through the mathematical representation of
data, but this representation [3] can have many forms especially if we go in
higher dimensions, or if we wish to learn these representations based on our
different objectives; for example, to calculate similarity between 2 images,
we can calculate both Euclidean distance or cosine similarity. The key
question is how to learn which embeddings are better representation of our
task, or which loss function is good for our objective. In this section, we
have summarized two well known metrics based approaches: Siamese Networks and
Matching Networks, which attempts to improve the task representative embedding
through different architecture and training procedure.

Figure 2: Sample Siamese Network Architecture

###  IV-A Siamese Networks

A Siamese network[4], as the name suggests, is an architecture with two
parallel layers. In this architecture, instead of a model learning to classify
its inputs using classification loss functions, the model learns to
differentiate between two given inputs. It compares two inputs based on a
similarity metric, and checks whether they are same or not. This network
consists of two identical neural networks, which share similar parameters,
each head taking one input data point (see fig. 2). In the middle layer, we
extract similar kinds of features, as weights and biases are the same. The
last layers of these networks are fed to a loss function layer, which
calculates the similarity between the two inputs. The whole idea of using
Siamese architecture[5] [1] is not to classify between classes but to learn to
discriminate between inputs. So, it needed a differentiating form of loss
function such as the contrastive loss function.

Figure 3: In the following sample architecture for matching networks, input to
g($\theta$) are randomly sampled data (support set) from already existing
examples, and input to f($\theta$) is input test data point

####  IV-A1 Understanding the data processing for Siamese Networks

is really important. For training Siamese network, we need a special kind of
pre-processing the data-set. We have to create pairs of data points:

  * •

pair of similar images, and

  * •

pair of dissimilar images.

We also need to create labels accordingly for similar($y=1$), and dissimilar
data points($y=0$); then, each pair is fed to the Siamese architecture. At the
end of the layer, Siamese Network uses a differentiating form of loss function
known as Contrastive Loss Function.

####  IV-A2 Understanding Contrastive loss function

As the whole idea of using Siamese architecture is not to classify between
classes but to learn to discriminate between inputs. So, it needed a
differentiating form of loss function known as contrastive loss function. It
is given as follows:

$Loss=(1-Y)\frac{1}{2}D_{w}^{2}+(Y)\frac{1}{2}(max(0,m-D_{w})^{2}$
Here, $D_{w}=\sqrt{{G_{w}(X1)-G_{w}(X2}}$ and $G_{w}$ is the output from one
of sister networks, $X1,X2$ are input data pair.

If we carefully look into the equation of Contrastive Loss Function, we will
observe that it consists of dual terms:

  * •

first part to decrease the energy of like pairs and,

  * •

second increase the energy of unlike pairs.

The first part of the loss function is simply Mean Squared Error multiplied
with their respective labels; whereas, the second part of loss function
resembles Hinge Loss, with m as a threshold. Here $m$ is a margin value which
is greater than 0. It indicates that dissimilar pairs with Root Mean Squared
Value greater than $m$, won’t contribute in the dissimilar pair loss function.
This also holds up logically as you would only want to optimize the network
based on pairs that are actually dissimilar, which network thinks are similar.

Many times a problem can be solved using various approaches, for example, Face
Detection in our phones, Signature verification, etc. Image Classification is
one of the approaches but that will need a lot of data points; whereas, if we
use the Siamese network architecture of One-shot learning, we can achieve
greater accuracy with only a few data points. Siamese Network Architecture
became one of the popular One-shot learning architecture, which industry has
adopted and are using for various other applications, such as Face Detection,
Handwriting Detection, Spam Detection, and so on. But there is still a lot of
scope of improvement, for example, for Contrastive Loss Function itself. In
other modfied versions of Siamese Networks Architecture, it was discussed that
contrastive loss functions, wasn’t able to learn through decision boundaries
very clearly, so a new loss function was suggested known as Triplet Loss,
which helped the architecture to advance.

Note: Transfer learning using Siamese Network Approach is only valid for
similar domain dataset [6]. If the domain aren’t similar, we also needs to
take care of domain adaption, that is, try to ensure that our training and
testing data-sets are close in terms of data distribution. For example, if one
wants to create a system to test whether two hand writings are of the same
person, what they can do is train Siamese Network Architecture on MNIST data-
set through which it will learn handwriting specific features such as curves,
strokes of any character.

###  IV-B Matching Networks

Matching networks [7], in general, proposes a framework which learns a network
that maps a small data-set and an unlabeled example to its label. When it
comes to a small data-set, we come across the problem of over-fitting and
under-fitting which can be alleviated using regularization and data
augmentation respectively; but still, it doesn’t solve the root cause of the
issue. The other problem is that learning of parameters is very slow,
requiring various weight updates using stochastic gradient descent; whereas
many non-parametric models, such as k-nearest neighbor, doesn’t even require
any form of training; it stores data-set and makes a decision based on a
metric. Matching networks incorporate the best characteristic of both
parametric and non-parametric models, also famously known as Differential
Nearest neighbor. Matching networks are designed to be two-fold:

  1. 1.

Modeling level: At Modeling level, they proposed Matching nets, which uses
advances made in attention and memory that enable fast and efficient learning.

  2. 2.

Training procedure: At Training Level, they have one condition that
distribution of training and test set must be same. For example: show a few
examples per class, switching the task from mini-batch to mini-batch, similar
to how it will be tested when presented with a few examples of a new task.

In simpler terms, matching networks learn the proper embeddings representation
and use cosine similarity measure to ensure whether a test data point is
something ever seen or not.

Matching Networks is a neural network model that implements an end-to-end
training procedure that combines feature extraction and differentiable k-NN
with cosine similarity. Matching network’s architecture is majorly inspired by
the attention model and memory-based networks. In all these models, a neural
attention mechanism is defined to access a memory matrix, which stores useful
information to solve the task at hand. To begin with, first we need to
understand certain terminologies of Matching Network:

  1. 1.

Label Set: This is the sample set of all possible categories. For example, if
we have 1,000 categories and as part of sampling from the database we only use
only 5 categories.

  2. 2.

Support Set: This is the sampled input data points (for example, images) of
label set categories.

  3. 3.

Batch: Similar to support set, batch is also a sampled set consisting of input
data points of Label Set Categories.

  4. 4.

N-way K-Shot Method: Here, N is the size of the support set. In simpler terms,
the number of possible categories in the training set. For example, in the
figure that follows, we have four different types of dog breeds, and we are
planning to do 5-shot learning method, that is, have at least five examples of
each category. This will make Matching Network Architecture as 4 way 5 shot
learning.

The key idea of Matching networks is to map images to an embeddings space,
which also encapsulates the label distribution and then project test image in
the same embedding space using different architecture; later, use cosine
similarity to measure the similarity metric.

####  IV-B1 Understanding data processing for Matching Networks

For Matching networks architecture, we need to sample N labels from training
dataset, and then according to those labels, sample K examples for sample-set,
and B examples for batch-set. As part of pre-processing data, a support set S
of k examples will be created as $(x_{i},y_{i})$ as shown in fig 2. After
obtaining Support Set, it passes through a standard feature extraction layer
($g$), followed by bidirectional LSTM architecture, it helps us learn the
probabilistic distribution of labels present in support set, by switching from
batch to batch. These extracted embeddings are called Fully Contextual
Embeddings.

Similarly, for the query image $\hat{x}$ also go through similar path and
obtain Full Context Embeddings in same embedding space as that of Support set.
After obtaining the outcomes from both support set and query image, they get
feeded into a kernel followed by our cosine similarity function.

####  IV-B2 Understanding Training Process of Matching Networks

Training process of matching networks is a bit different from traditional deep
learning approaches. It tries to replicate data distribution of test-data in
training data as well. In simpler terms, as we have observed as part of data
pre-processing step, Matching Networks actually create sample sets from
training examples too and try to re-create scenario similar to test-sets.
Matching Networks learns its parameters through training-set by creating small
subsets [8] as that of a test-sets; that is, it is actually training the model
as a few-shot learning model.

##  V Models Based Methods

Models Based Methods are majorly inspired from how humans store prior
information in memory units, and have access while learning new objectives.
Model-Based Meta-Learning models depend upon architecture design for rapid
generalization of few-shot learning tasks. As Humans, we always have access to
a large amount of memory for any task, and a majority of the times, how humans
learn a new task is through recalling some memory and adapt to the new task in
short span. In this chapter, we will be studying about such deep learning
architectures, which are able to learn parameters with only a few training
steps with the help of external memory, such for of architectures are known as
Model-Based methods.

Figure 4: Neural Turing Machine[9] Figure 5: Memory Augmented Neural Network
Approach

###  V-A Neural Turing Machine

The early development stages of the field of Artificial Intelligence was
heavily dominated with the symbolic approach - which attempted to explain how
information processing systems like human brain might work in terms of
symbols, structures and rules to manipulate those symbols and structures. It
wasn’t until about 1980s when the field of AI took a different approach -
connectionism, neural networks being the most promising modeling technique of
connectionism. The advent of neural networks met with two heavy criticisms.
First neural networks typically accept fixed sized inputs and won’t be much
useful as most of the input in real life problems is variable length (sequence
of frames in video, text, speech). Second, neural networks seem unable to bind
values to specific locations within data structures which is heavily employed
by two information systems we know of - human brain and computers. The first
criticism about variable length input was answered by Recurrent Neural
Networks (RNNs) which have achieved state-of-the-art performance on many
tasks. Neural Turing Machines [9], the topic of discussion in this section
tries to answer second criticism by giving external memory to neural networks
and a method to learn to use it. We will discuss the overall architecture of
Neural Turing Machine (NTM) in this section which is foundational to
understanding Memory-Augmented Neural Networks (MANN) [10] which modifies NMT
architecture and adapt it for few-shot learning task.

Modern computers have advanced a lot over past 50 years but they are still
composed of three systems - memory, control flow and arithmetic/logic
operations. There’s also biological evidence that working memory is crucial in
quick and meaningful store and retrieval of information. The same is also
established extensively by the computational neuroscience field. Taking
inspirations from this, A NTM [9] is fundamentally composed of a neural
network - controller and a 2D matrix called the memory bank (or memory
matrix). At each time step, the neural network receives some input and
generates some output corresponding to that input. In the process of doing so,
it also accesses the internal memory bank and performs read and/or write
operations on it. Drawing inspiration from traditional turing machines, NMT
uses the term ’head’ to specify the memory location(s). The overall
architecture is shown in Figure 4. There’s one challenge in this architecture,
If we access the memory location by specifying row and column index in the
memory matrix, we can’t take gradient of that index. This operation is not
back-propagable and would restrict the training of NMT using standard back-
propagation and gradient descent based optimization techniques. To circumvent
this problem, the controller of the NTM [11] interacts with memory using
’blurry’ read and write operations that interacts with all elements of the
memory to varying degrees. More precisely the controller produces weights over
all memory locations in a differentiable manner which helps in training the
network end-to-end using standard gradient based optimization methods.

  1. 1.

Modeling: The memory matrix at time step $t(M_{t})$ has $R$ rows and $C$
columns. There’s an attention mechanism which dictates where the head should
read/write from. This attention vector, generated by controller is a length-
$R$ vector called weight vector $W_{t}$ where each entry of this vector
$W_{t}(i)$ is the weight for the $i^{th}$ row of the memory bank. The weight
vector is normalized which means it satisfies following conditions:

$0\leq w_{t}(i)\leq 1$ and , $\sum_{i=1}{R}w_{t}(i)=1$

  2. 2.

Reading: The read head will return a length- $C$ vector $r_{t}$ that is a
linear combination of the memory’s rows $M_{t}(i)$ scaled by the weight
vector:

$r_{t}\leftarrow\sum_{i=1}{R}(w_{t}(i)M_{t}(i))$

  3. 3.

Writing: Writing is a combination of two steps: erasing and adding. In order
to erase old data the write head uses an additional length- $C$ erase vector,
$e_{t}$ along with the weight vector. The following equations defines the
intermediate step of erasing the rows.

$M_{t}^{erased}(i)\leftarrow M_{t-1}(i)[1-w_{t}(i)e_{t})$ Finally, the write
head uses length- $C$ add vector $a_{t}$ along with $M^{erased}$ from above
and weight vector to update the rows of the memory matrix. $M_{t}(i)\leftarrow
M_{t}^{erased}+w_{t}(i)a_{t}$

  4. 4.

Addressing: The key to read and write operation is the weight vector which
indicates which rows to read/write from/to. The controller produces this
weight vector in four stages. Each stage produces in an intermediate vector
which gets passed to the next stage. The first stage is content-based
addressing, the goal of which is to generate a weight vector based on how
similar each row is to some key vector $k_{t}$ of length $C$. More precisely,
controller emits vector $k_{t}$ which is compared to each row of $M_{t}$ using
cosine similarity measure, defined below

$K(u,v)=\frac{u.v}{||u||.||v||}$

The content weight vector is not normalized yet, so its normalized with the
following operation.

$w_{t}^{c}(i)=\frac{exp(\beta_{t}K(k_{t},M_{t}(i)))}{\sum_{j}\exp(\beta_{t}K(k_{t},M_{t}(j)))}$

The next stage is the location based addressing which focuses on read/write
from specific memory locations as opposed to read/write specific location
values done by stage 1. In the second stage, a scalar parameter
$g_{t}\in(0,1)$ called the interpolation gate, blends the content weight
vector $w_{t}^{c}$ with the previous time step’s weight vector $w_{t-1}$ to
produce the gated weighting $w_{t}^{g}$ . This allows the system learn when to
use (or ignore) content-based addressing.

$w_{t}^{g}\leftarrow g_{t}w_{t}^{c}+(1-g_{t})w_{t-1}$

In the third stage, after interpolation, the head emits a normalized shift
weighting $s_{t}$ to perform shift modulo $R$ operation (i.e. move rows
upwards or downwards). This is defined by the operation below.

$\tilde{w_{t}}(i)\leftarrow\sum_{j=0}^{R-1}w_{t}^{g}(j)s_{t}(i-j)$

The fourth and final stage, sharpening, is used to prevent the shifted weight
$\tilde{w_{t}}$ from blurring. This is done with a scalar $\gamma\geq 1$ and
applying the operation.

$w_{t}(i)\leftarrow\frac{\tilde{w_{t}}(i)^{\gamma_{t}}}{\sum_{j}\tilde{w_{t}}(j)^{\gamma_{t}}}$

All the operations, including read, write and four stages of addressing are
differentiable and thus the entire NMT model could be trained end-to-end with
back-propagation and any gradient descent based optimizer. The controller is a
neural network which could be a feed-forward network or even a recurrent
neural network like LSTMs. Now that we understand the architecture and the
working of NTM, we can dive into Memory Augmented Neural Networks which is a
modification of NMT and has been modified to excel at few-shot learning.

###  V-B Memory Augmented Neural Networks

The goal of Memory Augmented Neural Network (MANN) [10] is to excel at few-
shot learning task. The NMT controller, as we read earlier uses both content-
based addressing and location-based addressing. On the other hand, the MANN
controller uses only content-based addressing. There are two reasons to do
this. One reason is that location-based addressing is not required for the
few-shot learning task. In this task, for a given input, there are only two
actions a controller might need to take and both actions are content dependent
and not location dependent. One action is that the input is very similar to
previously seen input in which case we might what to update whatever is there
in memory. The other action is that current input is not similar to previously
seen inputs in which case we don’t want to overwrite the recent information
but the least used memory location. The memory module, in this case, is called
Least Recently Used Access (LRUA) module.

  1. 1.

Reading: The read operation of MANN is very similar to the read operation of
NTMs, with a minor difference that the weight vector here uses only content
bases addressing (stage -1 of NMT addressing). More precisely, the controller
uses normalized read weight vector, $w_{t}^{r}$ is used along with the rows of
the $M_{t}$ to produce read vector $r_{t}$.
$r_{t}\leftarrow\sum_{i}^{R}(w_{t}^{r}(i)M_{t}(i)$ The read-weight vector
$w_{t}^{r}$ is produced by controller defined by the operations below.
$w_{t}^{r}=\frac{exp(K(k_{t},M_{t}(i))}{\sum_{j}exp((k_{t},M_{t}(j)))}$ where,
operation $K()$ is the cosine similarity , similar to the one defined for NMTs
above.

  2. 2.

Writing: To write to the memory, the controller interpolates between writing
to the most recently read memory rows and writing to least recently read
memory rows.
$w_{t}^{w}\leftarrow\sigma(\alpha)w_{t-1}^{r}+(1-\sigma(\alpha))w_{t-1}^{lu}$
$M_{t}(i)\leftarrow M_{t-1}(i)+w_{t}^{w}(i)k_{t}$ $w_{t}^{u}\leftarrow\gamma
w_{t-1}^{u}+w_{t}^{r}+w_{t}^{w}$

###  V-C Meta Networks

Meta Networks [12] as the name suggests is a form of Model-based Meta-Learning
Approach. Similar to how Meta-Learning approaches, In meta-networks also, we
have a base learner and meta-learner sharing parameters where a meta-learner
extracts common features of all tasks and a base learner learns the targeted
task. As we can see in figure 7, Meta Networks is also equipped with external
memory, similar to architecture we just read above Memory Augmented Neural
Networks. The underlying key idea of Meta Networks is to learn weights in a
fast manner for rapid generalizations, and it has been done by processing
higher order meta information. In the next section, we will go through an
understanding of architecture, extraction of meta information, and it’s
parameter optimization algorithm.

Note: Previous work on Meta-learning has formulated the problem as two-level
learning: slow learning of a meta-level model performing across tasks and
rapid learning of a base-level model acting within each task. The goal of a
meta-level learner is to acquire a general knowledge of different tasks. The
knowledge can then be transferred to the base-level learner to provide
generalization in the context of a single task. The base and meta-level models
can be framed in a single learner.

In usual Deep Learning Methods, weights of neural networks are updated by
stochastic gradient descent and many times it takes a lot of time to train, in
other words, slow weights update. In Meta Networks, one solution has been
suggested to improve upon this method: To utilize one neural network in
parallel to original neural network, to predict the parameters of another
neural network and the generated weights are called fast weights.

In MetaNet [12], loss gradients are used as meta information to enable models
that learn fast weights. Slow and fast weights are combined to make
predictions in neural networks just as shown in the figure above. Here, $sum$
means element-wise sum. Meta Networks Learning occurs at two levels in
separate spaces: meta space and task space. here, the base learner learns in
task-specific space, whereas the meta-learner learns meta-knowledge across
different tasks. After training of Meta learner, the base learner first
analyzes the input task and then provides the meta-learner with feedback in
the form of higher order meta information(gradients) to explain its own status
in the current task space.

Figure 6: Architecture of Meta Networks

There are two important components of a MetaNet as shown in figure 6:

  1. 1.

Embedding function $(f_{\theta})$: As part of Meta Net, we train Embedding
generator function, which is then used to compare features of two different
data points, very similar to what we have in Siamese Networks.

  2. 2.

Base Learner Model $g_{\phi}$: It is parameterized by weights, and completes
the actual learning task.

As we have two different types of networks trained in parallel: fast, and slow
network, therefore we also need to get Embedding Function and a Base Learner
Model for a fast network:

  1. 1.

Embedding Function$(F_{w})$: an LSTM architecture, for learning fast weights
$\theta$ of the embedding function$(f_{\theta})$ of slow network.

  2. 2.

Base Learner Model $(G_{v})$: a neural network parameterized by v learning
fast weights $\phi$ for the base learner $g_{\phi}$from its loss gradients.

For training, Meta Networks also follow a similar training procedure as of
Matching Networks. Here, also we obtain training data contains multiple pairs
of datasets: support set S = $(x_{i}^{\prime},y_{i}^{\prime})$ and training
set U= $(x_{i},y_{i})$ . So, now we have four networks and four sets of model
parameters to learn, $(\theta,\phi,w,v)$. [12] also proposed the meta learning
based algorithm to train networks as shown in figure 7

Figure 7: Algorithm for One-shot learning using Meta-Net in Supervised data
setting [12].

##  VI Optimization Based Methods

If we look into the learning method of Neural Networks architectures, it
usually consists of a lot of parameters and is optimized using Gradient
descent algorithm, which takes many iterative steps over many examples to
perform well. Gradient Descent Algorithm though provides a decent performance
of models, but fails drastically in scenarios when there is less amount of
data. There are mainly two reasons why gradient descent algorithm fails to
optimize a neural network with smaller data-set:

  1. 1.

If we look into variants of gradient descent’s weight updating step methods
(Adagrad, Adam, RMS, and so on), can’t perform well with less number of
epochs. Especially when used for non-convex optimization these algorithms
don’t have a strong guarantee of convergence.

  2. 2.

For each new task, Neural Network has to start from a random initialization of
its parameters, which results in late convergence. Transfer learning has been
used to alleviate this problem, by using a pre-trained network, but it is
limited to be of same domain task.

What can be really helpful is to learn some common initialization, which can
be used across all domains as a good point of initialization. The key idea of
a Gradient Descent Algorithm is based on the direction of the next step, which
is chosen on the basis of probabilistic distribution assumption. So, if we
somehow are able to approximate that probabilistic distribution completely, we
will be able to optimize the network, with only a few steps. This is the basic
idea of Optimization-based algorithms: Model-Agnostic Meta-Learning [13] and
LSTM-Meta Learner [14]

Figure 8: Here, $\theta$ is the model’s [13] parameters and the bold black
line is the meta-learning phase. Let’s assume that we have 3 different new
tasks 1, 2 and 3, a gradient step is taken for each task (the gray lines)
Figure 9: Optimization Algorithm for Model Agnostic Meta Learning [13].

###  VI-A Model Agnostic Meta Learning

The goal of Model Agnostic Meta-Learning [13] architecture is to quickly learn
a new task from a small amount of new data. The key idea of this approach is
to train the models’ initial parameters using a different data-set, such that
as the new task comes, the model gives maximum performance by using already
initialized parameters, to fine-tune the architecture through one or more
gradient steps. As we know that Neural Networks use Gradient descent algorithm
to train, so the method of training a model’s parameters such that a few
gradient steps can optimize loss function, and give good results, can be
viewed from a feature learning standpoint as building an internal
representation. As it is very generic, therefore can be used for various
tasks. The primary contribution of this work is a simple model and task-
agnostic algorithm that trains a model’s parameters such that a small number
of gradient updates will lead to fast learning on the new task. The Objective
of Model-Agnostic Meta-Learning (MAML) [13] is to provide a good
initialization of a model’s parameters to achieve optimal fast learning on a
new task with less number of gradient steps. It also attempts to avoid
overfitting scenarios, which happens while training a Neural Network with less
amount of data architecture.

As we can see in the figure 8 parameters $\theta$ are close to all the 3
optimal parameters of task 1, 2, and 3 which makes $\theta$ the best
parameters initialization that can quickly adapt to different new tasks. As a
result, only a small change in the parameters $\theta$ will lead to an optimal
minimization of the loss function of any task. This is the key idea of MAML,
that somehow we learn $\theta$ through the original dataset, so while fine-
tuning on the real dataset, we just have to move a small step. For One/Few
Shots Learning, first, we prepare our data. For a particular task say, $T_{i}$
we have data samples which are forming task distribution of form $P(T)$
(Probabilistic distribution across all tasks). Our aim is to train a model to
learn task $T_{i}$ from K data points and feedback generated by Loss ,
$L(T_{i})$. During meta-training, a task $T_{i}$ is sampled from $P(T)$ i.e;
training data available, then model is trained with K samples and feedback
from the corresponding loss $L(T_{i})$ from $T_{i}$ , and then tested on new
samples from $T_{i}$ . The model is then improved by considering how the test
error on new data changes with respect to the parameters. In effect, the test
error on sampled tasks $T_{i}$ serves as the training error of the meta-
learning process. At the end of the training, new tasks are sampled from
$p(T)$, and meta-performance is measured by the model’s performance after
learning from K samples.

$L_{T_{i}}(f_{\phi})=\sum_{x^{j},y^{j}\backsim
T_{i}}||f_{\phi}(x^{(j)})-y^{(j)}||_{2}^{2}$

where $x^{(j)},y^{(j)}$ are sampled from task $T_{i}$. To learn more in detail
about steps followed in maml optimization Algorithms, please take a look at
the algorithm published in the paper [13].

###  VI-B LSTM Meta Learner

As the name suggests, LSTM meta-learner [14] algorithm is specifically
designed on LSTM Architecture because a cell-state update in LSTM is similar
to gradient-based update in backpropagation, and information about the history
of gradients help in optimizing model better. This Optimization Algorithm is
trained to optimize a learner neural network classifier. It captures the
knowledge of both the short term of a particular task and common long term.

LSTM meta learner is heavily inspired from connection in logic of Gradient
descent and LSTM cell update. Ravi et al., [14] explained that iff we look
into update method of Gradient Descent, we will see an equation like this:

$\theta_{t}=\theta_{t-1}-\alpha_{t}\bigtriangledown L_{t}$

here, $\theta_{t}$ is parameters at t time step, $\bigtriangledown L_{t}$ is
gradient of Loss at t, and $\alpha_{t}$ is learning rate at time t.

One observation that authors of LSTM meta learner made was, that this update
looks very similar to how cells get updated in LSTMs.. So, The Key idea of
Meta-Learner LSTM is to learn an update rule for training a neural network.
Lets first dive in how a cell state is defined in an LSTM.

$c_{t}=f_{t}\odot c_{t-1}+i_{t}\odot\bar{c_{t}}$

If we put $f_{t}=1,c_{t-1}=\theta_{t-1},i_{t}=\alpha_{t}$ and
$\bar{c_{t}}=\bigtriangledown L_{t}$ , we will get a gradient descent update
rule. Considering this, Logically, we want to learn $i_{t}$, as that is
essentially similar to estimating the learning rate of gradient descent. so,
LSTM Meta Learner define $i_{t}$ as:

$i_{t}=\sigma(W_{I}.[\bigtriangledown
L_{t},L_{t},\theta_{t-1},i_{t-1}]+b_{I})$

i.e; a sigmoid function with a combination of current gradient, Loss, and
previous learning rate $i_{t-1}$.

For $f_{t}$, it should be 1, but to avoid problems of shrinking gradients, and
exploding gradients. It has been chosen as:

$f_{t}=\sigma(W_{F}.[\bigtriangledown
L_{t},L_{t},\theta_{t-1},f_{t-1}]+b_{F})$

i.e; sigmoid function with a combination of current gradient, Loss, and forget
gate.

####  VI-B1 Data Pre-processing

In Typical Machine Learning setting, give a data-set D, we divide into 2
parts: training set, and a test set. Whereas in Meta-Learning Setting, we have
Meta-sets say $D$ , consists of multiple sets of different task examples. For
each D $\in D$ consists of $D_{train}$ and $D_{test}$ , so for K-Shot Learning
each $D_{train}$ consists of $K\times N$ examples, where $N$ is the number of
classes. In Meta-Learning, since beginning data is divided into 3 parts:
$D_{meta-train},D_{meta-validation},$ and $D_{meta-test}$ Here the objective
is to use $D_{meta-train}$ is for training a learning procedure that can take
as input one of its training sets $D_{train}$ and produce a classifier
(learner) that achieves high average classification performance.

####  VI-B2 Model Training

Following the concept of Matching Networks, This Optimization Algorithm also
tried to match training conditions to test time conditions, as they have been
proven to perform really well at a task. To make similar conditions, when
considering each dataset D , it uses loss $L_{test}$ produced by D’s test set
$D_{test}$ , for step by step knowledge refer to Algorithm mentioned in paper
[14].

So, while iterating for T steps overall D’s training data, LSTM meta-learner
receives some parameter updates from learner. After T-steps, final parameters
are then used to evaluate Test set, and make updates on meta-learner. To
understand, a pictorial representation of architecture, refer architecture in
10

Figure 10: The architecture of LSTM Meta Networks [14] consists of 2 parts:
Learner, and Meta-Learner. Learner trains for T-steps and sends its updated
parameters to Meta-Learner, then Meta-Learner evaluates updates, and optimize
its parameters. This whole process runs for D steps.

##  VII Other Approaches for few-shot learning

As we know few-shot Learning is a sub-field of Machine Learning, there are
different relevant solutions which are very close to few-shot Learning
approach, but yet different in their solution approach. Such problems can be
solved by using few-shot Learning algorithms as well. Let’s go through each of
such fields of Machine Learning, and observe how they are close to few-shot
Learning Problem:

  1. 1.

Semi-Supervised Learning

  2. 2.

Imbalanced Learning

  3. 3.

Transfer Learning

Figure 11: Semi Supervised Learning

###  VII-A Semi-Supervised Learning

Suppose we have 10,000 data points, in which only 20,000 are labeled and rest
80,000 are unlabeled. In such cases, we can take help of Semi-Supervised
Learning. In Semi-supervised learning, we take help of unlabeled data to gain
more understanding of the population structure in general. Semi-supervised
learning [15] goes through pseudo labeling technique to increase the training
set, i.e; we train a model using 20,000 labeled data-set and use it on equally
sized test data points to create pseudo labels for them. After obtaining
pseudo labels, we concatenate real labels with pseudo labels and real features
with pseudo features. After concatenation, we train a new model, which is
proven to be more accurate than the initial model. We keep doing it, till
optimal accuracy is achieved.

###  VII-B Imbalanced Learning

In Imbalanced Learning [16] scenario, we have an imbalanced data-set i.e; we
have more samples from one class, whereas very few examples of other
categories, this is also popularly known as skewed distribution data-set.
Let’s take a look at some popular methods for dealing with a skewed data-set.

  1. 1.

Choice of Metric: There are various forms of metrics that can help in
assessing the accuracy of a model, such as Confusion Matrix, Precision,
Recall, and F1-Score.

  2. 2.

Choice of Machine Learning Algorithm: Parametric Algorithms learn their
parameters through the data-set, so if the data-set is biased, it is most
likely that the parametric model will also be biased. Non-parametric
approaches such as K-Nearest Neighbor, Decision Trees etc. Ensembles such as
Random Forest, Adaboost, XG-Boost are proven to be the best approaches when it
comes to a biased data-set.

  3. 3.

Choice of Data Sampling Methods: Data Sampling can also be considered to
ensure that data-set doesn’t remain skewed.

This is close to few-shot Learning, as the machine learning model we are
expected to create should be able to learn distribution from a few examples.

###  VII-C Transfer Learning

Transfer Learning [17], refers to the technique of using knowledge of one
domain to another domain.i.e. a Neural Network model trained on one data-set
can be used for other data-set by fine-tuning the former network just like how
we can use Siamese Networks for different domain, by training it to extract
discriminative features from one domain. Transfer Learning [17] has caught a
lot of attention from Deep learning society, though it has been proven to be
great in various applications, yet we are unable to use it in non-common
domains, such as Manufacturing, Medical, Chemical, etc. just because we don’t
have enough data-set from a domain.

##  VIII Conclusion

To create a perfect few-shot learning approach, we need access to perfect
information embeddings, optimized memory storage, and improved optimization
algorithms than gradient descent. In this paper, we have been through
different types of such algorithms, from Matching Networks to Meta Networks.
We also observed that certain algorithms are able to achieve state of the art
accuracy for Classification tasks, but for Object Detection, Image
Segmentation etc, our models still struggles. Theoretically, there were
various applications for few-shot Learning, but only recently it has started
being used in real-world scenarios too. Recent advancements have been made
using few-shot Learning such as to write SQL Codes, Improving Deformed Medical
Images, Signature Verification, etc. There are several other domains, where
they are still in research. Companies like OpenAI, Google, Microsoft, Amazon
are investing heavily in AI research. Solving few-shot Learning would mean to
create a brain with abilities as that of a human, this can save lives by
becoming a rare-disease indicator machine, solve food crisis of the world, by
optimizing supply-chain models.

## References

  * [1] S. Jadon and A. Garg, Hands-On One-shot Learning with Python.  Packt Publishing, 2020.
  * [2] S. Jadon, O. P. Leary, I. Pan, T. J. Harder, D. W. Wright, L. H. Merck, and D. L. Merck, “A comparative study of 2d image segmentation algorithms for traumatic brain lesions using ct data from the protectiii multicenter clinical trial,” in Medical Imaging 2020: Imaging Informatics for Healthcare, Research, and Applications, vol. 11318, p. 113180Q, International Society for Optics and Photonics, 2020.
  * [3] S. Jadon, “Introduction to different activation functions for deep learning,” Mar 2018.
  * [4] G. Koch, R. Zemel, and R. Salakhutdinov, “Siamese neural networks for one-shot image recognition,” in ICML deep learning workshop, vol. 2, 2015.
  * [5] S. Jadon and A. A. Srinivasan, “Improving siamese networks for one shot learning using kernel based activation functions,” arXiv preprint arXiv:1910.09798, 2019.
  * [6] C. Vargas, Q. Zhang, and E. Izquierdo, “One shot logo recognition based on siamese neural networks,” in Proceedings of the 2020 International Conference on Multimedia Retrieval, pp. 321–325, 2020.
  * [7] O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra, et al., “Matching networks for one shot learning,” in Advances in neural information processing systems, pp. 3630–3638, 2016.
  * [8] S. Jadon, “Ssm-net for plants disease identification in lowdata regime,” arXiv preprint arXiv:2005.13140, 2020.
  * [9] A. Graves, G. Wayne, and I. Danihelka, “Neural turing machines,” arXiv preprint arXiv:1410.5401, 2014.
  * [10] A. Santoro, S. Bartunov, M. Botvinick, D. Wierstra, and T. Lillicrap, “One-shot learning with memory-augmented neural networks,” arXiv preprint arXiv:1605.06065, 2016.
  * [11] M. Collier and J. Beel, “Implementing neural turing machines,” in International Conference on Artificial Neural Networks, pp. 94–104, Springer, 2018.
  * [12] T. Munkhdalai and H. Yu, “Meta networks,” Proceedings of machine learning research, vol. 70, p. 2554, 2017.
  * [13] C. Finn, P. Abbeel, and S. Levine, “Model-agnostic meta-learning for fast adaptation of deep networks,” arXiv preprint arXiv:1703.03400, 2017.
  * [14] S. Ravi and H. Larochelle, “Optimization as a model for few-shot learning,” 2016\.
  * [15] X. Zhu and A. B. Goldberg, “Introduction to semi-supervised learning,” Synthesis lectures on artificial intelligence and machine learning, vol. 3, no. 1, pp. 1–130, 2009.
  * [16] G. Haixiang, L. Yijing, J. Shang, G. Mingyun, H. Yuanyue, and G. Bing, “Learning from class-imbalanced data: Review of methods and applications,” Expert Systems with Applications, vol. 73, pp. 220–239, 2017.
  * [17] S. J. Pan and Q. Yang, “A survey on transfer learning,” IEEE Transactions on knowledge and data engineering, vol. 22, no. 10, pp. 1345–1359, 2009.
  * [18] G. Keren, M. Schmitt, T. Kehrenberg, and B. Schuller, “Weakly supervised one-shot detection with attention siamese networks,” stat, vol. 1050, p. 12, 2018.
  * [19] S. Mshir and M. Kaya, “Signature recognition using machine learning,” in 2020 8th International Symposium on Digital Forensics and Security (ISDFS), pp. 1–4, 2020.
  * [20] J. Thathachar, T. Kornuta, and A. S. Ozcan, “Encoder-decoder memory-augmented neural network architectures,” Mar. 19 2020.  US Patent App. 16/135,990.
  * [21] M. Collier and J. Beel, “Memory-augmented neural networks for machine translation,” arXiv preprint arXiv:1909.08314, 2019.
  * [22] F. Shen, S. Yan, and G. Zeng, “Meta networks for neural style transfer,” arXiv preprint arXiv:1709.04111, 2017.
  * [23] Z. Chen, Y. Fu, Y.-X. Wang, L. Ma, W. Liu, and M. Hebert, “Image deformation meta-networks for one-shot learning,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8680–8689, 2019.
  * [24] Z. Liu, R. Zhang, Y. Song, and M. Zhang, “When does maml work the best? an empirical study on model-agnostic meta-learning in nlp applications,” arXiv preprint arXiv:2005.11700, 2020.
  * [25] H. S. Behl, A. G. Baydin, and P. H. Torr, “Alpha maml: Adaptive model-agnostic meta-learning,” arXiv preprint arXiv:1905.07435, 2019.
  * [26] H. Li, D. Eigen, S. Dodge, M. Zeiler, and X. Wang, “Finding task-relevant features for few-shot learning by category traversal,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1–10, 2019.
  * [27] S.-A. Rebuffi, S. Ehrhardt, K. Han, A. Vedaldi, and A. Zisserman, “Semi-supervised learning with scarce annotations,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 762–763, 2020.
  * [28] C. Huang, Y. Li, C. C. Loy, and X. Tang, “Learning deep representation for imbalanced classification,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5375–5384, 2016.
  * [29] A. Fernández, S. García, M. Galar, R. C. Prati, B. Krawczyk, and F. Herrera, Learning from imbalanced data sets.  Springer, 2018.
  * [30] F. Zhuang, Z. Qi, K. Duan, D. Xi, Y. Zhu, H. Zhu, H. Xiong, and Q. He, “A comprehensive survey on transfer learning,” Proceedings of the IEEE, 2020\.