# Computing Permanents and Counting Hamiltonian Cycles Faster

Baitian Li<EMAIL_ADDRESS>Institute for Interdisciplinary
Information Sciences, Tsinghua University

###### Abstract.

We show that the permanent of an $n\times n$ matrix of
$\operatorname{poly}(n)$-bit integers and the number of Hamiltonian cycles of
an $n$-vertex graph can both be computed in time $2^{n-\Omega(\sqrt{n})}$,
improving an earlier algorithm of Björklund, Kaski, and Williams (Algorithmica
2019) that runs in time $2^{n-\Omega\left(\sqrt{n/\log\log n}\right)}$.

A key tool of our approach is to design a data structure that supports fast
“$r$-order evaluation” of permanent and Hamiltonian cycles, which cooperates
with the new approach on multivariate multipoint evaluation by Bhargava,
Ghosh, Guo, Kumar, and Umans (FOCS 2022).

##  1\. Introduction

Given an $n\times n$ matrix $A$ over a commutative ring $R$, the $R$-Permanent
is defined by

$\operatorname{per}A=\sum_{\sigma\in S_{n}}\prod_{i=1}^{n}A_{i,\sigma(i)},$

where $S_{n}$ denotes the permutations of order $n$. Similarly, the
$R$-HamCycles is defined by

$\operatorname{hc}A=\sum_{\begin{subarray}{c}\sigma\in S_{n}\\\
c(\sigma)=1\end{subarray}}\prod_{i=1}^{n}A_{i,\sigma(i)},$

where $c(\sigma)$ denotes the number of cycles in $\sigma$.

The permanent and Hamiltonian cycles are two fundamental problems in computer
science. The problem of deciding whether a given graph has a Hamiltonian cycle
is one of Karp’s 21 -complete problems [11]. Valiant proved that over the
integers, the problem computing permanent is $\\#\P$-complete, even the
entries of the matrix are restricted to $0$ and $1$ [15], and counting
Hamiltonian cycles is also $\\#\P$-complete [16].

Ryser’s formula [14] shows that the permanent can be computed with $O(n2^{n})$
arithmetic operations. It remains a prominent open problem whether the
permanent can be computed within less than $2^{n}$ sized arithmetic circuits,
as mentioned by Knuth in _the Art of Computer Programming_ [13, Exercise
4.6.4.11].

Indeed, beyond the confines of arithmetic operations, faster algorithms for
computing the permanent have emerged. Bax and Franklin [1] gave an algorithm
that computes $01$-permanent in $2^{n-\Omega(n^{1/3}/\log n)}$ expected time.
Björklund [4] introduced the self-reduction paradigm for both the permanent
and Hamiltonian cycles. Leveraging tabulation and the Chinese remainder
theorem, Björklund’s algorithm achieved time complexity
$2^{n-\Omega\left(\sqrt{n/\log n}\right)}$. His work is subsequently improved
by Björklund, Kaski and Williams [6] by applying the construction of Kakeya
set to reduce the tabulation size for multivariate polynomial evaluation, and
give an algorithm of time $2^{n-\Omega\left(\sqrt{n/\log\log n}\right)}$,
furthermore, their algorithm applies to a more generalized kind of polynomial
called fermionant.

###  1.1. Our Result

In this paper, we further improve the algorithm of Björklund, Kaski and
Williams [6], removing the $\log\log n$ term in the exponent.

######  Theorem 1.

There is an algorithm that computes the permanent $\operatorname{per}(A)$ and
Hamiltonian cycles $\operatorname{hc}(A)$ of a given matrix
$A\in\mathbb{F}_{q}^{n\times n}$ in time $2^{n-\Omega(\sqrt{n})}q^{O(1)}$.

The Chinese remainder theorem and a simple estimate of prime products yield
the following corollary for integer-valued permanents.

######  Corollary 1.

Given an $n\times n$ matrix with integer entries absolute value bounded by
$M$, can compute $\operatorname{per}(A)$ and $\operatorname{hc}(A)$ in time
$2^{n-\Omega(\sqrt{n})}(\log M)^{O(1)}$.

###  1.2. Related Works

_Multivariate Multipoint Evaluation._ Our algorithm is inspired by recent
progress on multivariate multipoint evaluation. In the seminal work of Kedlaya
and Umans [12], they used Chinese remainder theorem and tabulation to give a
non-algebraic algorithm for multipoint evaluation of multivariate polynomials,
which becomes a key ingredient of their breakthrough on fast polynomial
composition and factorization, in time $n^{1+o(1)}$ and $n^{1.5+o(1)}$
respectively. Consider a polynomial $f$ defined over the finite field
$\mathbb{F}_{q}$ with $m$ indeterminates, each having partial degree less than
$d$ in each variable. The multivariate multipoint evaluation problem is to
evaluate $f$ over $N$ points. Under a moderate assumption on the number of
variables ($m\leq d^{o(1)}$), their algorithm runs in time
$(d^{m}+N)^{1+o(1)}\operatorname{poly}(m,d,\log q)$. In subsequent works [3,
2], the use of Hasse derivatives and Hermite interpolation is developed to
replace Lagrange interpolation. For the time complexity
$(d^{m}+N)^{1+o(1)}\operatorname{poly}(m,d,\log q)$ on multivariate multipoint
evaluation, the assumption that $m\leq d^{o(1)}$ is replaced to a weaker
assumption that $d$ is sufficiently large.

_Permanents._ There exists faster algorithms for computing permanent in other
settings. For sparse matrices, Cygan and Pilipczuk [9] gave a
$2^{n-\Omega(n/d)}$ time algorithm, where $d$ is the average degree of non-
zero entries per row. Björklund and Williams [7] gave a
$2^{n-\Omega(n/d^{3/4})}$ time algorithm for $d$-regular bipartite graphs, and
a $2^{n-\Omega(n/r)}$ time algorithm that runs over a finite ring with $r$
elements. Björklund, Husfeldt and Lyckberg [5] gave a $2^{n-\Omega(n/(p\log
p))}$ time algorithm computing the permanent modulo a prime power $p^{\lambda
n/p}$, for any constant $\lambda<1$.

###  1.3. Technical Overview

We first consider the permanent case.

We firstly follow the self-reduction and Chinese remaindering paradigm of
Björklund [4] to reduce the problem into computing $2^{n-k}n^{O(1)}$ many
instances of permanent over $k\times k$ matrices, where $k=c\sqrt{n}$, over a
small finite field $\mathbb{F}_{q}$. We still use the construction of Kakeya
sets to reduce the tabulation size, as in [6], but with different parameters.
With a $O(\delta^{k^{2}})$ sized Kakeya set, for any instance
$\bm{a}\in\mathbb{F}_{q}^{k^{2}}$, there is a curve $C_{\bm{a}}$ of degree
$q/\delta$ that the whole curve lies in the Kakeya set, and the coefficients
of the curve parametrize $\bm{a}$. As shown in [2], evaluating
$\operatorname{per}(C_{\bm{a}}(t))$ at each point of $\mathbb{F}_{q}$, with
higher order derivative of degree $k/\delta$ are enough to reveal the
permanent. Note that precomputing all the Hasse derivatives doesn’t work,
since there are $2^{O((k/\delta)\log(k/\delta))}$ many terms to aggregate when
handling each instance. However, due to the structure of permanent, we can use
dynamic programming to compute the higher order information faster, in time
$2^{O(k/\delta)}$, when $\delta$ is a large enough constant, this overcomes
the number of instances $2^{n-k}n^{O(1)}$.

For Hamiltonian cycles, our algorithm is based on a characterization of
Hamiltonian cycles via determinant by [8], which helps us to design a dynamic
programming that computes the higher order derivative in time
$2^{O(k/\delta)}$.

##  2\. Preliminaries

###  2.1. Notation

We use $\tilde{O}(f(n))$ to denote $O(f(n)\operatorname{poly}\log(f(n)))$.

For a positive integer $n$, we use $[n]$ denote $\\{1,\dots,n\\}$.

We use Iverson’s bracket notation. Let $p$ be a logical proposition, we let
$[p]$ be $1$ if $p$ is true and $0$ otherwise.

For an $n\times m$ matrix $A$, for subsets $S\subseteq[n]$ and
$T\subseteq[m]$, we use $A_{S,T}$ to denote the submatrix of $A$ with rows
indexed by $S$ and columns indexed by $T$.

Let $\binom{n}{\downarrow m}$ to denote the partial sum of binomials, i.e.,

$\binom{n}{\downarrow m}=\sum_{0\leq i\leq m}\binom{n}{i}.$

###  2.2. Inequality for Binomial

We need the estimate of the partial sum of binomials, see [10, Lemma 3.13] for
a proof.

######  Lemma 1.

For $\alpha\in(0,1/2)$, we have

$\binom{n}{\downarrow\alpha n}\leq 2^{nH(\alpha)},$

where $H(\alpha)=-\log_{2}(\alpha^{\alpha}(1-\alpha)^{1-\alpha})$.

###  2.3. Hermite Interpolation

We need the following lemma for Hermite interpolation, see [17, Section 5.6]
for a proof.

######  Lemma 2.

Let $f(t)\in\mathbb{F}[t]$ be a polynomial of degree less than $d$, and $m$
distinct points $\tau_{1},\dots,\tau$ in $\mathbb{F}$, with multiplicities
$e_{1},\dots,e_{m}$ be positive integers such that $e_{1}+\cdots+e_{m}=d$.
Given $f\bmod(t-\tau_{i})^{e_{i}}$ for each $i\in[m]$, $f$ can be recovered in
$\operatorname{poly}(d)$ $\mathbb{F}$-operations.

In particular, our algorithm use the case where $\alpha$ contains all elements
of a finite field $\mathbb{F}_{q}$, and $e_{i}=r$ for all $i$.

######  Corollary 2.

Let $f(t)$ be a polynomial of degree less than $qr$, and given
$f\bmod(t-\alpha)^{r}$ for all $\alpha\in\mathbb{F}_{q}$, $f$ can be recovered
in $\operatorname{poly}(qr)$ $\mathbb{F}_{q}$-operations.

###  2.4. Multimodular Reduction

Our algorithm uses the Chinese remainder theorem to reduce the problem to
small finite fields.

######  Theorem 2.

Let $p_{1},\dots,p_{n}$ be distinct primes, and $a_{1},\dots,a_{n}$ be
integers such that $0\leq a_{i}\leq p_{i}$. Let $M=p_{1}\cdots p_{n}$. Then
there exists a unique integer $a$ such that $0\leq a<M$ such that $a\equiv
a_{i}\pmod{p_{i}}$ for every $i\in[n]$. Moreover, $a$ can be computed in time
$\operatorname{poly}(\log M)$.

See [17, Section 10.3] for a proof.

We also need an estimate on the product of primes.

######  Lemma 3.

For an integer $N\geq 2$, the product of the primes $\leq 16\log N$ is greater
than $N$.

See [12, Lemma 2.4] for a proof.

##  3\. Common Framework

In this section, we set up the common framework for computing permanents and
counting Hamiltonian cycles.

###  3.1. Self Reduction

We borrow the following two lemmas from [4, Lemma 3, Lemma 4].

######  Lemma 4.

Suppose $|\mathbb{F}|\geq k^{2}+1$, given a matrix $A\in\mathbb{F}^{n\times
n}$, one can compute $m=2^{n-k}n^{O(1)}$ instances
$a_{i}\in\mathbb{F},F_{i}\in\mathbb{F}^{k\times k}$ such that

$\operatorname{per}(A)=\sum_{i=1}^{m}a_{i}\operatorname{per}(F_{i}).$

And the computation of these instances takes $2^{n-k}n^{O(1)}$
$\mathbb{F}$-operations.

######  Lemma 5.

Suppose $|\mathbb{F}|\geq k^{2}+1$, given a matrix $A\in\mathbb{F}^{n\times
n}$, one can compute $m=2^{n-k}n^{O(1)}$ instances
$a_{i}\in\mathbb{F},F_{i}\in\mathbb{F}^{k\times k}$ such that

$\operatorname{hc}(A)=\sum_{i=1}^{m}a_{i}\operatorname{hc}(F_{i}).$

And the computation of these instances takes $2^{n-k}n^{O(1)}$
$\mathbb{F}$-operations.

###  3.2. Kakeya Set

We borrow the definition and construction of Kakeya sets mentioned in [6].

######  Definition 1.

A set $K\subseteq\mathbb{F}_{q}^{m}$ is said to be a _Kakeya set_ of degree
$u$, if for every $a_{1},\dots,a_{m}\in\mathbb{F}_{q}$, there exists degree
$u$-polynomials $g_{1},\dots,g_{m}$, such that the degree $u$ coefficient of
$g_{i}$ is $a_{i}$, and the set

$\\{(g_{1}(\tau),\dots,g_{m}(\tau)):\tau\in\mathbb{F}_{q}\\}$

is a subset of $K$.

######  Theorem 3.

Let $u$ be a positive integer such that $u+1$ divides $q-1$. Then there is a
Kakeya set $K$ of degree $u$ in $\mathbb{F}_{q}^{m}$ of size at most
$(\frac{q-1}{u+1}+1)^{m+1}$. Such $K$ can be constructed in time $O(q|K|)$ and
for each point $\bm{a}=(a_{1},\dots,a_{m})\in\mathbb{F}_{q}^{m}$, the
coefficients of the corresponding polynomials $g_{1},\dots,g_{m}$ can be
computed in time $\operatorname{poly}(u,m)$.

###  3.3. Reveal Information From Derivative

We first define $r$-order evaluation.

######  Definition 2.

Let $P$ be a polynomial over $m$ indeterminates. We call a data structure that
supports the following operation a _$r$ -order evaluation_ of $P$ at
$\bm{a}\in\mathbb{F}_{q}^{m}$: Given a polynomial
$\bm{f}(t)=(f_{1}(t),\dots,f_{m}(t))$, where each
$f_{i}(t)\in\mathbb{F}_{q}[t]$ is a polynomial with degree less than $r$, and
$\bm{f}(0)=\bm{a}$. Compute $P(\bm{f}(t))\bmod t^{r}$.

We rephrase the idea of [2] to reveal information from derivative in the
language of $r$-order evaluation.

######  Theorem 4.

Let $P$ be a homogenous degree $k$ polynomial over $m$ indeterminates, $b$ be
a positive integer such that $q\equiv 1\pmod{b}$. Let $u=(q-1)/b-1$ and
$r=\lceil k/b\rceil$. Let $K$ be a Kakeya set of degree $u$, with constructed
data structures for $r$-order evaluation at all points of $K$, given any point
$\bm{a}$ and the associated curve $C_{\bm{a}}(t)=(g_{1}(t),\dots,g_{m}(t))$,
we can compute $P(\bm{a})$ within $q$ queries of $r$-order evaluation, and
$\operatorname{poly}(k,q)$ arithmetic operations over $\mathbb{F}_{q}$.

###### Proof.

By the definition of Kakeya sets, it’s guaranteed that $C_{\bm{a}}(\tau)\in K$
for all $\tau\in\mathbb{F}_{q}$. The polynomial $P(C_{\bm{a}}(t))$ is of
degree $ku$. Write $P(x_{1},\dots,x_{m})$ with

$P(x_{1},\dots,x_{m})=\sum_{\begin{subarray}{c}i_{1},\dots,i_{m}\in\mathbb{N}\\\
i_{1}+\cdots+i_{m}=k\end{subarray}}p_{i_{1},\dots,i_{m}}x_{1}^{i_{1}}\cdots
x_{m}^{i_{m}},$

since $g_{i}(t)=a_{i}t^{u}+O(t^{u-1})$, we have

$\displaystyle P(C_{\bm{a}}(t))$
$\displaystyle=\sum_{\begin{subarray}{c}i_{1},\dots,i_{m}\in\mathbb{N}\\\
i_{1}+\cdots+i_{m}=k\end{subarray}}p_{i_{1},\dots,i_{m}}g_{1}(t)^{i_{1}}\cdots
g_{m}(t)^{i_{m}}$
$\displaystyle=\sum_{\begin{subarray}{c}i_{1},\dots,i_{m}\in\mathbb{N}\\\
i_{1}+\cdots+i_{m}=k\end{subarray}}p_{i_{1},\dots,i_{m}}(a_{1}t^{u}+O(t^{u-1}))^{i_{1}}\cdots(a_{m}t^{u}+O(t^{u-1}))^{i_{m}}$
$\displaystyle=\sum_{\begin{subarray}{c}i_{1},\dots,i_{m}\in\mathbb{N}\\\
i_{1}+\cdots+i_{m}=k\end{subarray}}p_{i_{1},\dots,i_{m}}(a_{1}^{i_{m}}\cdots
a_{m}^{i_{m}}t^{ku}+O(t^{ku-1}))$ $\displaystyle=P(\bm{a})t^{ku}+O(t^{ku-1}),$

we have the coefficient of $t^{ku}$ in $P(C_{\bm{a}}(t))$ is $P(\bm{a})$.

By the choice of $u$, we have $ku=k((q-1)/b-1)<qk/b\leq qr$. Let
$Q(t)=P(C_{\bm{a}}(t))$. If we are given $Q\bmod(t-\tau)^{r}$ for each
$\tau\in\mathbb{F}_{q}$, by Hermite interpolation, we can recover $Q$ in
$\operatorname{poly}(qr)$ time. So the problem reduces to compute
$P(C_{\bm{a}}(t))\bmod(t-\tau)^{r}$ for each $\tau\in\mathbb{F}_{q}$.

In order to compute $Q(t)\bmod(t-\tau)^{r}$, one can write
$Q(t)=R(t)+(t-\tau)^{r}D(t)$ where $\deg R<r$, then $R(t)$ is the desired
result. Thus we have $Q(t+\tau)=R(t+\tau)+t^{r}D(t+r)$, so we can compute
$Q(t+\tau)\bmod t^{r}$, and then reveal $Q(t)\bmod(t-\tau)^{r}$ by
substituting $t\leftarrow t-\tau$. The conversion of coefficients only takes
$\operatorname{poly}(r)$ arithmetic operations over $\mathbb{F}_{q}$. Thus we
only need to compute $P(C_{\bm{a}}(t+\tau))\bmod t^{r}$ for each
$\tau\in\mathbb{F}_{q}$, this is exactly an $r$-order evaluation at
$C_{\bm{a}}(\tau)$. ∎

##  4\. Data Structure for Permanent

######  Lemma 6.

For a commutative ring $R$ and matrices $A,B\in R^{n\times n}$, we have

$\operatorname{per}(A+B)=\sum_{\begin{subarray}{c}S,T\subseteq[n]\\\
|S|=|T|\end{subarray}}\operatorname{per}(B_{S,T})\operatorname{per}(A_{[n]\setminus
S,[n]\setminus T}).$

###### Proof.

We gave a combinatorial proof. The permanent $\operatorname{per}(A+B)$ takes
the summation over the perfect matchings of the complete bipartite graph
$K_{n,n}$ with the product of edge weights. By expanding the product of each
$(A+B)_{i,j}$, this is equivalent to coloring each selected edge with one of
two colors $A$ and $B$, and taking the product of the weights of edges with
the selected color. On another hand, we can first determine the vertices that
their matching edge is colored by $B$, let those vertices in the left side be
$S$ and those in the right side be $T$, then the contribution of such coloring
is $\operatorname{per}(B_{S,T})\operatorname{per}(A_{[n]\setminus
S,[n]\setminus T})$. ∎

######  Theorem 5.

Given a matrix $A\in\mathbb{F}^{k\times k}$ and a positive integer $r$, can
precompute with time $\tilde{O}\left(\binom{k}{\downarrow r}^{2}2^{k}\right)$,
and answer the $r$-order evaluation $\operatorname{per}(F(t))\bmod t^{r}$ in
time $\tilde{O}\left(\binom{k}{\downarrow r}^{2}\right)$. Both are measured in
$\mathbb{F}$-operations.

###### Proof.

We write $F(t)=A+B(t)$, where $B(t)$ has no constant term.

Note that when $|S|\geq r$, the term $\operatorname{per}(B_{S,T})$ does not
contribute to the result. Let $f(S,T)=\operatorname{per}(B_{S,T})$, those
$f(S,T)$ can be computed via dynamic programming, described as follows.

For the base case, we have $f(\emptyset,\emptyset)=1$.

For $0<|S|=|T|<r$, let $s$ be a member of $S$, by enumerating the matching
vertex $t$ of $s$, we have

$f(S,T)=\sum_{t\in T}B_{s,t}f(S\setminus\\{s\\},T\setminus\\{t\\}).$

After computing all $f(S,T)$, we can compute

$\operatorname{per}(A+B)=\sum_{\begin{subarray}{c}S,T\subseteq[n]\\\
|S|=|T|<r\end{subarray}}f(S,T)g_{S,T}$

where the $g_{S,T}=\operatorname{per}(A_{[n]\setminus S,[n]\setminus T})$ can
be precomputed via Ryser’s formula [14] in time $\tilde{O}(2^{k})$.

The precomputation time is

$\sum_{0\leq j<r}\binom{k}{j}^{2}\cdot\tilde{O}(2^{k})\leq\left(\sum_{0\leq
j<r}\binom{k}{j}\right)^{2}\cdot\tilde{O}(2^{k})=\tilde{O}\left(\binom{k}{\downarrow
r}^{2}2^{k}\right),$

and each query takes time

$\tilde{O}\left(\sum_{0\leq
j<r}\binom{k}{j}^{2}\right)=\tilde{O}\left(\binom{k}{\downarrow
r}^{2}\right).\qed$

Note that when $r=\alpha k$ for some $0<\alpha<1/2$, by Lemma 1, precompuation
takes time $\tilde{O}(2^{(1+2H(\alpha))k})$, and each query takes time
$\tilde{O}(2^{2H(\alpha)k})$.

##  5\. Data Structure for Hamiltonian Cycles

In [8] they considered that Hamiltonian cycles can be counted as spanning
trees with degree restricted and used it to count undirected Hamiltonian
cycles in time exponential of treewidth. We give a directed version.

Let $\sigma\in S_{n}$ be a permutation, let $P_{\sigma}$ denote the
permutation matrix associated with $\sigma$, such that
$(P_{\sigma})_{i,j}=[j=\sigma(i)]$.

######  Lemma 7.

For a permutation $\sigma\in S_{n}$,

$\det(I-P_{\sigma})_{[n]\setminus\\{1\\},[n]\setminus\\{1\\}}=[c(\sigma)=1].$

###### Proof.

Consider a directed graph $G$ with directed edges $(i,\sigma(i))$, then
$L=I-P_{\sigma}$ is exactly the Laplacian of the graph $G$. By the directed
version of matrix tree theorem,
$\det(L_{[n]\setminus\\{1\\},[n]\setminus\\{1\\}})$ is the number of directed
spanning trees rooted at vertex $1$. When $c(\sigma)=1$, then clearly there is
exactly one spanning tree, otherwise there is no spanning tree. Thus we can
conclude the claimed equality. ∎

Therefore, we use the above characterization of Hamiltonian cycles to help
computing HamCycles.

######  Theorem 6.

Given a matrix $A\in\mathbb{F}^{k\times k}$ and a positive integer $r$, can
precompute with time $\tilde{O}\left(\binom{k}{\downarrow r}4^{k}\right)$, and
answer the $r$-order evaluation $\operatorname{hc}(F(t))\bmod t^{r}$ in time
$\tilde{O}\left(\binom{k}{\downarrow r}^{3}\right)$. Both are measured in
$\mathbb{F}$-operations.

###### Proof.

By the definition of HamCycles and Lemma 7, we have

$\operatorname{hc}(A)=\sum_{\sigma\in
S_{k}}\left(\prod_{i=1}^{k}A_{i,\sigma(i)}\right)\det(I-P_{\sigma})_{[n]\setminus\\{1\\},[n]\setminus\\{1\\}}.$

We also expand $\det(I-P_{\sigma})_{[n]\setminus\\{1\\},[n]\setminus\\{1\\}}$
by Leibniz formula, i.e.,

$\det(I-P_{\sigma})_{[n]\setminus\\{1\\},[n]\setminus\\{1\\}}=\sum_{\begin{subarray}{c}\tau\in
S_{k}\\\
\tau(1)=1\end{subarray}}\operatorname{sgn}(\tau)\prod_{i=2}^{k}(I-P_{\sigma})_{i,\tau(i)}.$

Combining the above two equations, and interpret $\operatorname{sgn}(\tau)$ as
$(-1)^{\operatorname{inv}(\tau)}$, where $\operatorname{inv}(a)$ denotes the
number of inversions for a sequence $a$, we have

$\displaystyle\det(I-P_{\sigma})_{[n]\setminus\\{1\\},[n]\setminus\\{1\\}}$
$\displaystyle=\sum_{\begin{subarray}{c}\sigma,\tau\in S_{k}\\\
\tau(1)=1\end{subarray}}\operatorname{sgn}(\tau)\left(\prod_{i=1}^{k}A_{i,\sigma(i)}\right)\left(\prod_{i=2}^{k}(I-P_{\sigma})_{i,\tau(i)}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}\sigma,\tau\in S_{k}\\\
\tau(1)=1\end{subarray}}(-1)^{\operatorname{inv}(\tau)}\left(\prod_{i=1}^{k}A_{i,\sigma(i)}\right)\left(\prod_{i=2}^{k}[i=\tau(i)]-[\sigma(i)=\tau(i)]\right).$

Now consider dynamic programming. For
$S\subseteq[k]\setminus\\{1\\},T\subseteq[k]$ and say $s=|S|=|T|$, let
$f(S,T)$ only count in the last $s$ values of $\sigma$ and $\tau$, with domain
$\\{\tau(k-s+1),\dots,\tau(k)\\}=S$ and
$\\{\sigma(k-s+1),\dots,\sigma(k)\\}=T$, and the inversions of $\tau$ in the
last $s$ values are counted, i.e.,

(1)
$f(S,T)=\sum_{\sigma,\tau}(-1)^{\operatorname{inv}(\tau)}\left(\prod_{i=k-s+1}^{k}A_{i,\sigma(i)}\right)\left(\prod_{i=k-s+1}^{k}[i=\tau(i)]-[\sigma(i)=\tau(i)]\right).$

We let $a\leftarrow^{+}b$ denote $a\leftarrow a+b$ for simplicity in
describing the updating rules. The base case is simply
$f(\emptyset,\emptyset)=1$, and for each $s<k-1$, we use the computed values
of $f(S,T)$ with $|S|=|T|=s$ to compute $f(S,T)$ with $|S|=|T|=s+1$ by the
following rules. Let $i=k-s$. For each $j\notin T$, we can choose $\sigma(i)$
to be $j$, then there are two choices of $\tau(i)$:

  * •

If $i\notin S$, update with

$f(S\cup\\{i\\},T\cup\\{j\\})\leftarrow^{+}(-1)^{\operatorname{inv}(i,S)}A_{i,j}f(S,T),$

denoting the choice that the contribution of term $[i=\tau(i)]$ in Eqn. 1.

  * •

If $j\notin S$, update with

$f(S\cup\\{j\\},T\cup\\{j\\})\leftarrow^{+}(-1)^{1+\operatorname{inv}(j,S)}A_{i,j}f(S,T),$

denoting the choice that the contribution of term $[\sigma(i)=\tau(i)]$ in
Eqn. 1.

Here $\operatorname{inv}(v,S)$ means the number of elements $x\in S$ such that
$v>x$.

At last, we have the choice of $\sigma(1)$, thus

$\operatorname{hc}(A)=\sum_{i=1}^{k}A_{1,i}f([k]\setminus\\{1\\},[k]\setminus\\{i\\}).$

This dynamic programming takes $\tilde{O}(4^{k})$, which is slower than the
usual one, but its dependence on the rows of $A$ is explicitly graded by $s$,
so is useful for our purpose.

Now suppose the first $j$ rows are left undetermined, we can first preprocess
all the $f(S,T)$ for $s\leq k-j$ in time $\tilde{O}(4^{k})$, since their value
does not depend on the first $j$ rows. Then for each query, i.e., given the
first $j$ rows, can be computed in time

$\tilde{O}\left(\sum_{i=1}^{j}\binom{k}{i}\binom{k}{i-1}\right)=\tilde{O}\left(\binom{k}{\downarrow
j}^{2}\right).$

Write $F=A+B(t)$, where $B(t)$ has no constant term, by the multilinearity on
rows of $\operatorname{hc}(\cdot)$, we have

$\operatorname{hc}(F(t))=\operatorname{hc}(A+B)=\sum_{S\subseteq[k]}\operatorname{hc}(\operatorname{rep}_{S}(A,B)),$

where $\operatorname{rep}_{S}(A,B)$ denote the matrix obtained by replacing
the rows indexed in $S$ of $A$ by those rows of $B$. The terms $|S|\geq r$ do
not contribute to the result. For each $|S|<r$, we can reorder the rows and
columns simultaneously to make $S$ be the first $|S|$ rows, and use the above
dynamic programming to do precomputation and handle queries.

There are $\binom{k}{\downarrow r}$ ways to choose $S$, so the precomputation
needs $\tilde{O}\left(\binom{k}{\downarrow r}4^{k}\right)$ time, and
$\tilde{O}\left(\binom{k}{\downarrow r}^{3}\right)$ for each query. ∎

Note that when $r=\alpha k$ for some $0<\alpha<1/2$, by Lemma 1, precompuation
takes time $\tilde{O}(2^{(2+H(\alpha))k})$, and each query takes time
$\tilde{O}(2^{3H(\alpha)k})$.

##  6\. The Algorithms

We first prove Theorem 1 under some restrictions, and then remove the
restrictions by bootstrapping the results.

######  Lemma 8.

Let $q$ be $q\geq n^{2}+1$ and $q\equiv 1\pmod{b}$, where $b\geq 10$. There is
an algorithm that computes the permanent $\operatorname{per}(A)$ of a given
matrix $A\in\mathbb{F}_{q}^{n\times n}$ in time
$2^{n-\delta_{b}\sqrt{n}}q^{O(1)}$, for some $\delta_{b}>0$.

###### Proof.

Let $\theta=\sqrt{\log(1.9)/\log(1+b)}$ and $k=\lfloor\theta\sqrt{n}\rfloor$,
consider the following algorithm.

  1. (1)

First compute the Kakeya set by Theorem 3 over $k^{2}$ variables of degree
$u=(q-1)/b-1$.

  2. (2)

Precompute the data structure for $r$-order evaluation for $r=\lceil
k/b\rceil$ at each point of $K$.

  3. (3)

Use the self-reduction of permanent to reduce the problem to
$m=2^{n-k}n^{O(1)}$ instances of size $k\times k$.

  4. (4)

For each instance, use Theorem 4 to compute the permanent.

Then we analyze the time complexity. In the precomputation phase, by Theorem
3, the size of Kakeya set has size
$(\frac{q-1}{u+1}+1)^{k^{2}+1}\leq(b+1)^{\theta^{2}n+1}=O(1.9^{n})$, and by
Theorem 5, each data structure takes time $2^{O(k)}$ time to precompute, so
the total time of the first two steps is $1.9^{n+O(\sqrt{n})}q^{O(1)}$.

The data structure can answer $r$-order evaluation in time
$\tilde{O}(2^{2H(\alpha)k})$, here we have $\alpha=1/b\leq 0.1$, thus one can
compute $2H(\alpha)\leq 2H(0.1)<0.94$, the total time in last two steps is

$2^{n-k}n^{O(1)}\cdot
O(2^{0.94k})q^{O(1)}=2^{n-0.06k}q^{O(1)}=2^{n-0.06\theta\sqrt{n}}q^{O(1)}.$

In conclusion, we have $\delta_{b}=0.06\theta$ satisfies the requirement. ∎

######  Lemma 9.

Let $q$ be $q\geq n^{2}+1$ and $q\equiv 1\pmod{b}$, where $b\geq 17$. There is
an algorithm that computes the permanent $\operatorname{hc}(A)$ of a given
matrix $A\in\mathbb{F}_{q}^{n\times n}$ in time
$2^{n-\delta_{b}\sqrt{n}}q^{O(1)}$, for some $\delta_{b}>0$.

###### Proof.

The algorithm is similar to the proof of Lemma 8, with replacing the data
structure is for Hamiltonian cycles instead of permanent.

By Theorem 6, the data structure can answer $r$-order evaluation of
Hamiltonian cycles in time $\tilde{O}(2^{3H(\alpha)k})$, and one can compute
that now $3H(\alpha)\leq 3H(1/17)<0.97$.

Then the total time in the last two steps is

$2^{n-k}n^{O(1)}\cdot
O(2^{0.97k})q^{O(1)}=2^{n-0.03k}q^{O(1)}=2^{n-0.03\theta\sqrt{n}}q^{O(1)}.$

In conclusion, we have $\delta_{b}=0.03\theta$ satisfies the requirement. ∎

###  6.1. Proof of Theorem 1

To prove Theorem 1, we only need to remove the conditions of Lemma 8 and Lemma
9 on $q$ that $q\geq n^{2}+1$ and $q\equiv 1\pmod{m}$ for some fixed modulo
$m$.

Note that for some integer $\ell$, we can embed $\mathbb{F}_{q}$ into a larger
finite field $\mathbb{F}_{q^{\ell}}$. We only need to satisfy $q^{\ell}\geq
n^{2}+1$ and $q^{\ell}\equiv 1\pmod{m}$. When $q$ is coprime with $m$, take
$\ell=\varphi(m)$ is enough to satisfy the second condition, where $\varphi$
is the Euler totient function. Take $\ell$ be the smallest multiple of
$\varphi(m)$ such that $q^{\ell}>n^{2}$, we have $q^{\ell}\leq
q^{\varphi(m)}n^{2}$.

For permanent, since $q$ is a prime power, it must be coprime with one of
$m=10$ or $m=11$. For Hamiltonian cycles, $q$ must be coprime with one of
$m=17$ or $m=18$. Therefore, we have $q^{\ell}=q^{O(1)}n^{2}$ since we only
considered finite possibilities of $m$.

Therefore, by calling the algorithms in Lemma 8 and Lemma 9 through the finite
field $\mathbb{F}_{q^{\ell}}$, we can compute the permanent and Hamiltonian
cycles in time
$2^{n-\Omega(\sqrt{n})}(q^{\ell})^{O(1)}=2^{n-\Omega(\sqrt{n})}q^{O(1)}$.

To really support the computation in the finite field $\mathbb{F}_{q^{\ell}}$,
we need to find an irreducible polynomial $f$ and identify
$\mathbb{F}_{q^{\ell}}$ as $\mathbb{F}_{q}[t]/(f)$. We can enumerate the
polynomials of degree $\ell$ over $\mathbb{F}_{q}$ and test whether it
satisfies the conditions, by [17, Theorem 14.37], the time complexity of
testing irreducibility is $\operatorname{poly}(\ell,\log q)$. The time of
finding an irreducible polynomial is $O(q^{\ell}\operatorname{poly}(\log
q^{\ell}))$, so this is not a bottleneck. ∎

###  6.2. Proof of Corollary 1

The absolute value of $\operatorname{per}(A)$ and $\operatorname{hc}(A)$ is
trivially bounded by $C=n!M^{n}$. Let $p_{1},\dots,p_{r}$ be distinct prime
numbers such that $D:=\prod_{i}p_{i}>2C+1$, then if we can compute
$\operatorname{per}(A)$ and $\operatorname{hc}(A)$ modulo $D$, the value of
$\operatorname{per}(A)$ and $\operatorname{hc}(A)$ are uniquely determined.

By Chinese remainder theorem, we only need to compute $\operatorname{per}(A)$
and $\operatorname{hc}(A)$ modulo $p_{i}$ for each $i$, and then combine them
to get the result modulo $D$.

By Lemma 3, the primes not greater than $16\log D=O(n\log M)$ has their
product greater than $D$, so we only need to compute $\operatorname{per}(A)$
and $\operatorname{hc}(A)$ under finite fields $\mathbb{F}_{p}$ with
$p=O(n\log M)$. By Theorem 1, we can compute them in time
$2^{n-\Omega(\sqrt{n})}p^{O(1)}=2^{n-\Omega(\sqrt{n})}(\log M)^{O(1)}$. There
are $O(n\log M)$ instances to compute. Since the product of chosen primes has
$O(n\log M)$ bits, by Theorem 2, it takes $\operatorname{poly}(n\log M)$ time
to combine them, which is not a bottleneck. So the total time is
$2^{n-\Omega(\sqrt{n})}(\log M)^{O(1)}$. ∎

## References

  * [1] E. Bax and J. Franklin.  A finite-difference sieve to count paths and cycles by length.  Inform. Process. Lett., 60(4):171–176, 1996.
  * [2] V. Bhargava, S. Ghosh, Z. Guo, M. Kumar, and C. Umans.  Fast multivariate multipoint evaluation over all finite fields.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, pages 221–232. IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022.
  * [3] V. Bhargava, S. Ghosh, M. Kumar, and C. K. Mohapatra.  Fast, algebraic multivariate multipoint evaluation in small characteristic and applications.  In STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 403–415. ACM, New York, [2022] ©2022.
  * [4] A. Björklund.  Below all subsets for some permutational counting problems.  In 15th Scandinavian Symposium and Workshops on Algorithm Theory, volume 53 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 17, 11. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016.
  * [5] A. Björklund, T. Husfeldt, and I. Lyckberg.  Computing the permanent modulo a prime power.  Inform. Process. Lett., 125:20–25, 2017.
  * [6] A. Björklund, P. Kaski, and R. Williams.  Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants.  Algorithmica, 81(10):4010–4028, 2019.
  * [7] A. Björklund and R. Williams.  Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors.  In 46th International Colloquium on Automata, Languages, and Programming, volume 132 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 25, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019.
  * [8] H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof.  Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.  Inform. and Comput., 243:86–111, 2015.
  * [9] M. Cygan and M. Pilipczuk.  Faster exponential-time algorithms in graphs of bounded average degree.  Inform. and Comput., 243:75–85, 2015.
  * [10] F. V. Fomin and D. Kratsch.  Exact exponential algorithms. Texts Theor. Comput. Sci., EATCS Ser. Berlin: Springer, 2010.
  * [11] R. M. Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), The IBM Research Symposia Series, pages 85–103. Plenum, New York-London, 1972.
  * [12] K. S. Kedlaya and C. Umans.  Fast polynomial factorization and modular composition.  SIAM J. Comput., 40(6):1767–1802, 2011.
  * [13] D. E. Knuth.  The art of computer programming. Vol. 2: Seminumerical algorithms.  Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969\.
  * [14] H. J. Ryser.  Combinatorial mathematics, volume No. 14 of The Carus Mathematical Monographs.  Mathematical Association of America, ; distributed by John Wiley and Sons, Inc., New York, 1963.
  * [15] L. G. Valiant.  The complexity of computing the permanent.  Theoret. Comput. Sci., 8(2):189–201, 1979.
  * [16] L. G. Valiant.  The complexity of enumeration and reliability problems.  SIAM J. Comput., 8(3):410–421, 1979.
  * [17] J. von zur Gathen and J. Gerhard.  Modern computer algebra.  Cambridge University Press, Cambridge, third edition, 2013.


# Explainable Attention for Few-shot Learning and Beyond

Bahareh Nikpour1,2, Narges Armanfard1,2

###### Abstract

Attention mechanisms have exhibited promising potential in enhancing learning
models by identifying salient portions of input data. This is particularly
valuable in scenarios where limited training samples are accessible due to
challenges in data collection and labeling. Drawing inspiration from human
recognition processes, we posit that an AI baseline’s performance could be
more accurate and dependable if it is exposed to essential segments of raw
data rather than the entire input dataset, akin to human perception. However,
the task of selecting these informative data segments, referred to as hard
attention finding, presents a formidable challenge. In situations with few
training samples, existing studies struggle to locate such informative regions
due to the large number of training parameters that cannot be effectively
learned from the available limited samples. In this study, we introduce a
novel and practical framework for achieving explainable hard attention
finding, specifically tailored for few-shot learning scenarios, called FewXAT.
Our approach employs deep reinforcement learning to implement the concept of
hard attention, directly impacting raw input data and thus rendering the
process interpretable for human understanding. Through extensive
experimentation across various benchmark datasets, we demonstrate the efficacy
of our proposed method.

## Introduction

Deep learning algorithms have demonstrated effectiveness in modeling and
representing data when a substantial quantity of labeled data is accessible.
However, they struggle to adapt to scenarios where only a few examples per
class are available for training. That is while it is often expensive and
labor-intensive to prepare labeled data. Additionally, the subjective nature
of data labeling and its dependence on individual annotators presents
additional complexities. To deal with these challenges, few-shot learning is
introduced to the field of machine learning, where the goal is training a
model with limited labeled data and generalize its knowledge to new, unseen
classes (Shi et al. 2021). There are lots of practical applications for few-
shot learning methods ranging from computer vision such as image
classification (Dhillon et al. 2019), activity recognition (Kumar Dwivedi et
al. 2019), image retrieval (Wang, Gui, and Hebert 2017), and object tracking
(Majee, Agrawal, and Subramanian 2021) to robotics and medical applications
such as drug discovery (Vella and Ebejer 2022). Most of the leading few-shot
learning methods are either metric learning-based or meta learner-based (Li et
al. 2017). Prototypical Networks (ProtNet) is one of the most popular metric-
based approaches in few-shot learning, proposed by Snell et al. (Snell,
Swersky, and Zemel 2017). The main idea behind Prototypical Networks is to
learn a metric space where examples from the same class are close to each
other and examples from different classes are far apart.

Figure 1: The three attentive regions to define the class rabbit

In recent years, attention mechanisms have emerged as a powerful tool for
improving computer vision algorithms by enabling models to focus on
discriminative regions within the image (Liu, Johns, and Davison 2019). That
is because not all sections of images possess equal importance, and only
certain regions hold valuable information. Attention is particularly inspired
by the human visual system which has the ability to focus on specific parts of
a scene to rapidly comprehend it. The attention models in the literature
mainly fall under two categories: “soft attention”, where different weights
show the importance of different data parts, and “hard attention”, where only
the important parts of the data are kept and the rest are discarded, allowing
for a more interpretable process. Hard attention was first put in place by
Minh et al. (Mnih et al. 2014) to reduce computation in convolutional neural
networks. Later on, many other techniques were introduced to find hard
attention such as (Ranzato 2014; Alexe et al. 2012; Ba et al. 2015; Seifi,
Jha, and Tuytelaars 2021; Rangrej and Clark 2021). One important benefit of
hard attention over soft attention is improving computational efficiency by
reducing the data size.

Finding hard attention is advantageous in few-shot learning as there are few
samples per class and the learning method can be easily misled by noise,
background clutter, and uninformative regions. However, previous studies have
encountered difficulties in identifying these informative regions because of
the large number of parameters that cannot be learned from the available
limited samples.

In this paper, we propose a novel explainable hard attention-finding approach
for few-shot learning, called FewXAT, to detect the attentive areas and
enhance performance in few-shot learning. Our method finds hard attention,
i.e. informative regions, within an image during the few-shot learning process
utilizing deep reinforcement learning. By focusing on the attentive regions,
the model can effectively capture the essential cues necessary for accurate
classification, even with limited training samples. The proposed FewXAT
framework formulates the problem of finding and detecting attentive regions as
a Markov Decision Process (MDP), where a reinforcement learning agent is
responsible for finding the optimum locations of multiple attentive areas,
called patches, within an image. The agent receives feedback in the form of
rewards from the few-shot baseline classifier, guiding it to identify patches
that contribute most to the final classification decision. Through this
iterative process, the agent becomes adept at identifying informative patches,
which facilitates generalization and robustness in scenarios with limited
labeled data. In addition, keeping only the informative patches and discarding
the rest of the information would decrease the memory and computational
complexity of the learning model. To enhance the training process, we add an
auxiliary task, which is a contrastive learning module, to help finding a
better representation of the data.

Deep Reinforcement Learning (RL), has been very successful in several computer
vision tasks (Mnih et al. 2013; Wang et al. 2018; Yun et al. 2017; Nikpour and
Armanfard 2023a, 2021; Nikpour, Sinodinos, and Armanfard 2022; Nikpour and
Armanfard 2023b). It has also been used in several research to find hard
attention in RGB images for classification tasks such as (Ba, Mnih, and
Kavukcuoglu 2014; Elsayed, Kornblith, and Le 2019). Moreover, there are a few
methods in the literature aiming at finding soft attention in few-shot
learning (Yan et al. 2019; Ren et al. 2019; Hong et al. 2021). There is one
research exploring the idea of finding soft attention in the context of few-
shot learning, where the attention is found on the feature map extracted by
convolution layers (Hong et al. 2021). Different from this method, we aim to
find hard attention in the original image. To the best of our knowledge,
FewXAT is the first work exploring the idea of finding hard attention for the
RGB images in the context of few-shot learning. Moreover, the existing hard
attention-finding methods in the classification task have very complex
structures, making them impossible to train for few-shot learning setup.

The contributions of our method are listed below:

  * •

We discovered the novel problem of hard attention finding for RGB images in a
few-shot learning setup.

  * •

We proposed a simple framework to address this problem using deep
reinforcement learning.

  * •

We added a contrastive learning module, as an auxiliary task, to enhance the
training process.

  * •

We conducted experiments on four popular benchmark datasets and got
competitive results, despite using a small portion of the data, showing the
effectiveness of FewXAT.

  * •

By finding hard attention, i.e. attentive regions in the images, we enhance
the contextual understanding and interpretablity of the baseline’s
predictions.

  * •

By attending to only the informative parts of the image and discarding the
rest, our method can decrease the size of the data noticeably which leads to a
decrease in the baseline model’s complexity.

  * •

We explored the performance of our proposed method in the classification task,
proving the usefulness of our method in other tasks as well.

Figure 2: Block diagram of the proposed FewXAT method.

## Methodology

In the following we first begin by introducing the terminology employed in
few-shot learning, then we present our proposed method in detail.

### Problem setting

In few-shot learning, an episode111Two types of episodes are used in this
paper: the episode in the few-shot setup and the episode in the reinforcement
learning framework. To avoid confusion, we use the bold-sized word to define
the few-shot episode. refers to a single learning task where a model has to
learn from a limited amount of data. The few-shot model learns during many
episode. Typically, an episode consists of two main components: a Support set
and a Query set. To train a model, a support set and a query set are randomly
selected from the data in each episode. This approach to learning is commonly
referred to as “$N$-way, $G$-shot” classification, where there are $N$ classes
and $G$ samples for each class in the support and query sets. We denote the
support set as $SU=\\{(x_{j},y_{j})\\}_{j=1}^{N\times G}$, where $x_{j}$ is
the $j^{th}$ sample in the support set and $y_{j}$ is its corresponding label.

### Proposed method

We assume that every object can be recognized by a maximum of three important
regions. Such important regions for recognizing a rabbit are shown in Figure
1. As such, FeWXAT aims to detect three attentive image patches that can also
overlap. The size of each patch is fixed and set to $\lfloor 1/3\rfloor$ of
the overall size of the input image. So, FewXAT keeps maximum $1/3$ of an
image.
The block diagram of the proposed method is shown in Figure 2. FewXAT consists
of three main modules: an RL module, which is responsible for finding the
attentive regions, the baseline classifier module, for learning the final
classification task, and a contrastive learning module which we add as an
auxiliary task to improve the performance and generalization of the model. In
summary, in the RL module, the state is defined using the data and is fed to
the agent. The agent completes an episode of $K$ steps and gets a reward and
calculates the loss of the RL module , i.e. $L_{RL}$. The reward is generated
by applying the baseline classifier to the attentive regions of the validation
set. The agent output on the input training data, which includes the three
selected patches per image, are given to the baseline classifier to calculate
the classifier loss, i.e., $L_{BL}$. Moreover, the agent output on the
training data is used to create positive and negative pairs to be used to
calculate the contrastive loss, i.e. $L_{CL}$. At the end, these three losses
are added with different weights to generate the total loss, $L_{tot}$, that
is used to update the networks of all the three modules. The details regarding
each module are discussed in the following.

1- RL Module
In our method, we model the process of finding the attentive areas in images
as a Markov decision process and solve it with the popular policy-based
reinforcement learning algorithm, Monte Carlo policy gradient (REINFORCE)
(Williams 1992). The agent in its current state takes actions that result in
changing its state and receiving a reward. The agent learns to select the
important areas in the image, i.e., it finds spatial hard attentions, by
maximizing the total expected reward. In this paper the RL agent is run for
every images in a batch with size $M$, and the $k^{th}$ step in the RL episode
for the $m^{th}$ sample in the batch is denoted by
$\mathcal{T}_{k,m}=(S_{k,m},A_{k,m},R_{k})$, where $S_{k,m}$, $A_{k,m}$, and
$R_{k}$ are state, action, and reward at the $k^{th}$ step for the $m^{th}$
image in the batch. One single episode is denoted as
$\mathcal{T}_{m}=(S_{1,m},A_{1,m},R_{1},...,S_{K,m},A_{K,m},R_{K})$. State,
agent, action, and reward in the proposed process are as follows:

State: We define the state ${S_{k,m}},m=1,...,M$ as the concatenation of the
$m^{th}$ original image in the batch, $I_{m}$, and the output of the agent
with the selected areas in the previous step of the episode, $I_{k,m}$, i.e.
${S_{k,m}}=[I_{m},I_{k,m}]$. $I_{k,m}$ has the same size as the original
$I_{m}$, where only the selected patches are present in the image and all the
remaining parts are set to zero. $I_{k,m}$ is shown in the right side of
Figure 3. In the initial state $S_{0,m}$, $I_{0,m}$ is initiated such that the
patches are located side-by-side at the top of the image as can be seen in
Figure 4.

Figure 3: The agent’s state $S_{k,m}$, which is concatenation of the original
image $I_{m}$, and the image output of the agent in the $k^{th}$ step of the
episode $I_{k,m}$, i.e. $S_{k,m}=[I_{m},I_{k,m}]$

Agent: The agent can be any neural network structure that is capable of
dealing with image data. At each step of the episode, i.e. the $k^{th}$ step,
and for the $m^{th}$ image, the agent outputs the probability matrix $P_{k,m}$
which will be used to define the actions it should take.

Figure 4: An example of $I_{k,m}$, $\\{k=0,..,K\\}$ during one episode in our
proposed method. The actions, shown in yellow arrows, for step 1 are go down
($\downarrow$), go right ($\rightarrow$), and go down ($\downarrow$) for the
first, second, and third regions respectively, which results in $I_{1,m}$.
After completing an episode, the agent outputs the regions found in $I_{K,m}$.

Action: The action defines the direction of movements of the patches.
Therefore, for each patch, five actions have been designed: go up, down, left,
right, and apply no change. The movement step size is set to $b$. In our
experiments, $b$ is set to 3 pixels for all datasets. For the $m^{th}$ image,
each action is denoted by $a_{k,m}^{l}$ where $k$ refers to the $k^{th}$ step
of the RL episode and $l\in\\{1,2,3\\}$ shows the $l^{th}$ attentive region.
The actions are sampled from a Bernoulli distribution over the probability
output of agent, $P_{k,m}=\\{p_{k,m}^{l}\\}_{l=1}^{3}$ as below:

$A_{k,m}=\\{a^{l}_{k,m}\sim\text{Bernoulli}(p^{l}_{k,m})\\}_{l=1}^{3}$ (1)

An example of one episode is depicted in Figure 4.

Reward: The reward should reflect how good the action of the agent is in
reaching its goal. In our method, the goal is improving or maintaining the
baseline’s performance while reducing the complexity (and hence improving
interpretability). Therefore, the baseline is used to evaluate the output of
the agent in step $k$ of the episode. We evaluate the agent’s performance at
the $k^{th}$ step, by applying it to a random batch of a validation set with
$N\times G$ samples for both support and query sets. Using a validation set
increases the method’s generalization ability. To obtain the reward, first, we
let the agent find the three attentive regions in each image of the validation
set; then, the three regions are concatenated next to each other, as is shown
in Figure 5. Then, it is fed to the baseline in the validation mode to get
accuracy. The validation accuracy i.e. $Acc_{val}^{k}$ is considered as the
reward as is defined below:

$R_{k}=Acc_{val}^{k}$ (2)

Figure 5: An example of validation batch after finding the attentive region in
in step $k$. To get the reward, the new batch of validation samples are given
to the baseline and the output accuracy is considered as the reward.

Training with REINFORCE: The goal of our reinforcement learning agent is
learning a policy function (which finds optimum locations of attentive areas)
by maximizing the expected reward $\mathcal{R}(\theta)$ shown below:

$\mathcal{R}(\theta)=\mathrm{E}_{p_{\theta}(a^{l}_{k,m})}[R_{k}],$ (3)

where $p_{\theta}(a^{l}_{k,m})$ is the probability distribution of the
possible actions for the $l^{th}$ patch, and $\mathrm{E}$ shows the
expectation over $l$, $m$ and $k$ where $l=\\{1,...,3\\}$, $k=\\{1,...,K\\}$
and $m=\\{1,..,M\\}$. We utilize REINFORCE, which is a popular policy gradient
algorithm(Williams 1992) to maximize the expected reward and therefore find
the optimal parameter $\theta$ for the policy. The policy is approximated by a
function that is parameterized by $\theta$. Following REINFORCE, the gradient
of the expected reward in the $k^{th}$ step of the episode, with respect to
the parameter $\theta$ is found as below:

$\begin{split}{\color[rgb]{0,0,0}\nabla_{\theta}\mathcal{R}(\theta)=\mathrm{E}_{{p_{\theta}(a^{l}_{k,m})}}[R_{k}\nabla_{\theta}\>ln\>\pi_{\theta}(a_{k,m}^{l}|{S_{k,m}})],}\end{split}$
(4)

where $\pi_{\theta}$ denotes the policy function, and $S_{k,m}$ is the state
of the $m^{th}$ image in the batch at the $k^{th}$ step as
${S_{k,m}}=[I_{m},I_{k,m}]$. As was mentioned before, during each episode, the
agent takes $K$ steps for each image in the batch. Therefore, we compute the
average gradient over $M$ samples in the batch as:

$\begin{split}\nabla_{\theta}\mathcal{R}(\theta)\approx\frac{1}{KM}\sum_{k=1}^{K}[R_{k}\sum_{m=1}^{M}\sum_{l=1}^{3}\nabla_{\theta}\>ln\>\pi_{\theta}(a_{k,m}^{l}|S_{k,m})],\end{split}$
(5)

where $a_{k,m}^{l}$ is the action for the $l^{th}$ patch of the $m^{th}$ image
in the batch in the $k^{th}$ step of the episode, and $S_{k,m}$ is state of
the $m^{th}$ image in the batch.

In order to enhance convergence and decrease variance during the training of
$\theta$, we normalize the reward by subtracting a constant baseline value
$c$. This baseline $c$ corresponds to the mean reward across episode. Hence,
the gradient becomes:

$\begin{split}\nabla_{\theta}\mathcal{R}(\theta)\approx\frac{1}{KM}\sum_{k=1}^{K}[(R_{k}-c)\sum_{m=1}^{M}\sum_{l=1}^{3}\nabla_{\theta}\>ln\>\pi_{\theta}(a_{k,m}^{l}|S_{k,m})],\end{split}$
(6)

Therefore, the loss of policy to minimize can be shown as:

$\begin{split}L_{RL}=\frac{1}{KM}\sum_{k=1}^{K}[(R_{k}-c)\sum_{m=1}^{M}\sum_{l=1}^{3}ln\>\pi_{\theta}(a_{k,m}^{l}|{S}_{k,m})]\end{split}$
(7)

2- Training the Baseline model: The baseline is responsible for learning the
desired task, which is classification of few-shot samples using only the
selected patches. We train the baseline during policy training using the train
data. To do so, the output attentive regions, provided by the policy network,
corresponding to the training data are concatenated next to each other
(similar to what was done for the validation set when obtaining the reward,
shown in Figure 5). More specifically, the concatenation of three selected
patches from each training image generates a new image that is three times the
size of a single patch. The new images are used as training data for the
baseline model. The baseline loss $L_{BL}$, defined in (LABEL:eq:LBL), is
calculated on its training data. Note that any few-shot classification method
can be used as the FewXAT baseline module. In this paper, we used the ProtoNet
algorithm as the baseline, as it is one of the most popular and well-
performing learning methods for few-shot learning (Snell, Swersky, and Zemel
2017). For each class, ProtoNet calculates a prototype vector by averaging the
embeddings (obtained from a neural network) of the support samples belonging
to that class in the feature space. The prototype represents the
characteristic features of the class. During training, ProtoNet minimizes the
distance between the embedding of a query sample and the prototype of the
query sample’s true class, while maximizing the distance from the prototypes
of other classes. This encourages the model to learn prototypes that can
effectively represent classes and differentiate them. The loss of ProtoNet is
calculated as:

$\begin{split}L_{BL}=-log(softmax(-||g(x_{q}),v_{y}||)\end{split}$ (8)

where $g(x_{q})$ is the embedded representation of the query sample, $vy$ is
the prototype representation of the correct class $y$ in the support set $SU$,
$||.||$ denotes the distance (e.g., Euclidean) between two vectors, and
$softmax()$ computes the softmax function over the negative distance.

3- Contrastive Learning Module: In general, adding auxiliary tasks is
advantageous from various perspectives. It can improve the performance of the
main task and help to increase the generalization by encouraging the model to
learn more general features. Moreover, learning the auxiliary task along with
the main task usually helps with faster convergence, by providing additional
gradients that guide the learning process and can prevent the model from
getting stuck in local minima. Lastly, the auxiliary task can force the model
to learn meaningful and disentangled representations of the input data, making
it easier to extract important features and patterns. Motivated by the
mentioned benefits, we added the contrastive learning module as an auxiliary
task to help the training procedure of our method.

Contrastive learning is a learning technique that aims to learn useful
representations by bringing similar data samples, i.e. positives, closer to
each other in the learned representation space while pushing dissimilar data
points, i.e. negatives, farther apart. In our method, we use the support set
and query set in the batch to create positive and negative pairs. Pairs from
the same class and their augmentation are considered as positive pairs, while
negative pairs are pairs from different classes. The augmentations we used for
each sample are: (1) every possible permutation of concatenating the three
selected attentive regions next to each other, as we do not want our method to
be sensitive to the concatenation order of the selected patches; (2) a random
rotation in the range -45 degrees and 45 degrees, to make our method robust to
rotation. Therefore, we have 12 augmentations,  and 12 positive pairs as a
result, for each sample as can be seen in Figure 6. After augmentation and
creating positive and negative pairs, the contrastive loss is calculated. As
the labels of data samples are available, we use the supervised contrastive
loss (SupCon loss) (Khosla et al. 2020) as follows:

$\begin{split}L_{CL}=\sum_{i\in W}\frac{-1}{|O(i)|}\sum_{o\in
O(i)}log\frac{\exp(f_{i}\cdot f_{o}/\tau)}{\sum_{u\in U(i)}\exp(f_{i}\cdot
f_{u}/\tau)}\end{split}$ (9)

where $i\in W\equiv\\{1,\dots,2Z\\}$, is the index of an arbitrary augmented
sample ($Z$ is the number of randomly sampled pairs). $O(i)$ shows the indices
of the positive pairs distinct from $i$, and $|O(i)|$ denotes its cardinality,
$U(i)\equiv W\backslash{i}$, $f_{\zeta}$ shows the output representation of
the network for the $\zeta$th index, and $\tau$ is the temperature parameter
to control the similarity scale. For more details, see (Khosla et al. 2020).

Figure 6: An example of creating positive and negative pairs in 5-way
scenario. The first row in positive samples shows every permutation of the
attentive regions. The second row shows the rotated attentive regions and
their permutation.

4- Training the algorithm

After calculation of the three losses, i.e. the policy loss, the baseline loss
and the contrastive learning loss, the total loss to be minimized is
calculated as:

$\begin{split}L_{tot}=\alpha L_{RL}+\beta L_{CL}+\gamma L_{BL}\end{split}$
(10)

where $\alpha$, $\beta$, and $\gamma$ are hyperparameters to control the
contribution of their corresponding loss term. The pseudo-code of the proposed
FewXAT framework is presented in Algorithm 1. In summary, a batch of few-shot
tasks is firstly sampled and the training data, including both support set and
query set, is given to the agent, $K$ steps are completed, and the reward
$R_{k}$ is calculated in each step $k$ of the method. The output of the agent
is the coordinated of the three patches. Using the output of the agent, the
new train set including samples with the attentive regions is created and the
loss of baseline is found using this new set. Then, the CL loss is computed
using the output embedding of the contrastive learning network on the data and
its augmentation. Having the three losses, the total loss is calculated, and
all the three networks are updated. This process is repeated for a defined
number of episodes until the three networks are trained.

Algorithm 1 The proposed FewXAT method

Input: The training and validation images and their labels
Output: Trained Agent

1: Initialize the Agent, the baseline, and the Contrastive Learning network.

2: for episodes do

3: Sample a batch of tasks

4: for $K$ steps do

5: The agent takes a step.

6: Find the reward $R_{k}$ by eq. 2.

7: end for

8: Find the agent’s loss ($L_{RL}$) using eq. 7.

9: Create the new train set and find the baseline’s loss ($L_{BL}$).

10: Create data augmentation and find the SupCon loss ($L_{CL}$) using eq. 9.

11: Find the total loss $L_{tot}$ using eq. 10

12: Update the three networks.

13: end for

14: return The trained Agent

In the testing phase, the train data is first given to the policy, the
selected patches are concatenated, and the baseline is trained on this new
train set. Then, the test data is fed to the policy and the new test data
obtained by concatanation of the selected patches is classified using the
trained baseline.

Table 1:  The accuracy results (in percent) on MiniImageNet, CIFAR-FS, FC-100, and CUB datasets before and after applying FewXAT, and with random selection for 5-shot 5-way (5-s 5-w), and 1-shot 5-way (1-s 5-w) settings. methods Dataset | MiniImageNet | CIFAR-FS | FC-100 | CUB
---|---|---|---|---
5-s 5-w | 1-s 5-w | 5-s 5-w | 1-s 5-w | 5-s 5-w | 1-s 5-w | 5-s 5-w | 1-s 5-w
Conv-4 | 66.98 | 48.12 | 77.98 | 67.12 | 48.74 | 31.47 | 75.12 | 50.46
ResNet-10 | 71.12 | 49.98 | 81.26 | 70.15 | 51.72 | 36.41 | 83.47 | 72.12
Random(Conv-4) | 48.76 | 32.11 | 65.14 | 49.67 | 42.12 | 25.69 | 68.21 | 35.12
Random(ResNet-10) | 53.76 | 36.12 | 70.06 | 55.14 | 45.22 | 29.88 | 70.32 | 37.03
FewXAT(Conv-4) | 68.32 | 48.89 | 78.23 | 67.94 | 50.21 | 31.87 | 76.11 | 53.21
FewXAT(ResNet-10) | 73.96 | 52.72 | 82.47 | 69.94 | 53.28 | 37.91 | 83.12 | 73.79
Table 2: The accuracy results of FewXAT with and without including the Contrastive Learning module on MiniImageNet, CIFAR-FS, FC-100, and CUB datasets with ProtoNet(ResNet-10) as baseline, for 5-shot 5-way (5-s 5-w), and 1-shot 5-way (1-s 5-w) settings.  methods Dataset | MiniImageNet | CIFAR-FS | FC-100 | CUB
---|---|---|---|---
5-s 5-w | 1-s 5-w | 5-s 5-w | 1-s 5-w | 5-s 5-w | 1-s 5-w | 5-s 5-w | 1-s 5-w
FewXAT with the CL module | 73.96 | 52.72 | 82.47 | 69.94 | 53.28 | 37.91 | 83.12 | 73.79
FewXAT without the CL module | 65.22 | 49.18 | 79.34 | 66.82 | 49.47 | 35.22 | 78.34 | 69.57

## Experiments

To evaluate the effectiveness of our proposed FewXAT approach, we conducted
experiments on four commonly employed datasets for few-shot learning,
MiniImageNet (Ravi and Larochelle 2016), CIFAR-FS (Krizhevsky, Hinton et al.
2009), FC-100(Krizhevsky, Hinton et al. 2009), and CUB (Welinder et al. 2010),
and as was mentioned in the previous section, we selected ProtoNet (Snell,
Swersky, and Zemel 2017) as the baseline. In the following, the details of
every experiment are explained.

### FewXAT for fewshot

To evaluate FewXAT, we used ProtoNet with two different structures including
Conv-4, and ResNet-10. The accuracy results are shown in Table 1, for the
datasets MiniImageNet, CIFAR-FS, FC-100, and CUB. The first row of the table
shows the test results of the baselines on the original data. The second row
presents the testing results of baselines after randomly picking three patches
in images from a uniform distribution. The last row gives the accuracy results
after finding the attentive areas by our proposed FewXAT method. In the cases
where the accuracy after applying FewXAT, FewXAT(baseline), is in the range
[baseline accuracy - 0.5, baseline accuracy + 0.5], i.e. the difference of the
accuracy before and after applying FewXAT is less than 0.5, we assume the
performance is maintained and in the cases where the accuracy of
FewXAT(baseline) $>$ baseline accuracy + 0.5, we assume we have improvement.
As can be seen, the accuracy is either improved or maintained in all the cases
after keeping the attentive regions and discarding the rest of the data. This
is specifically beneficial as, firstly, by down-sizing the images, the
complexity is decreased, and secondly, by keeping the important regions, the
interpretability is improved. In addition, comparing the results of FewXAT
with the random selection, all the results are remarkably better, indicating
the proposed method learns to find the optimum locations that result in
improved performance.

### Visualization of the learned hard attention

The output of our proposed FewXAT method, i.e. the detected regions for some
images from miniImageNet data is visualized in Figure 7. For example, in the
first image which belongs to the class dog, the eyes and nose of the dog are
detected as the attentive regions that can discriminate it from other classes.
Also, less than one-third of the image is kept, which decreases the data size
significantly. The visualized output of FewXAT confirms that its output is
consistent with human perception and makes the learning model interpretable.

Figure 7: Visualization of the attentive regions found by FewXAT

### Effect of Contrastive Learning module

To see how adding this auxiliary task, i.e. contrastive learning (CL), affects
the performance, we removed this module from our method and ran it for our
datasets using ProtoNet (with ResNet-10). The accuracy results are reported in
Table 2. As can be seen, adding the CL module can significantly improve the
performance by leading the model to learn better representations. It is
specifically important in a few-shot setting, where there exist few samples
leading to poor generalization ability of the classification model. Adding the
CL module helps in learning semantically meaningful features, resulting in
enhanced generalization.

Table 3: Accuracy results using different $b,K$ values. (b, K) |  (1,20) |  (1,40) |  (3,20) |  (7,15)
---|---|---|---|---
5-s 5-w |  56.98 |  68.43 |  68.32 |  53.21

### Influence of hyperparameters $b$ and $K$

As was discussed, $b$ denotes the step size of the agent to go
right/left/up/down, and $K$ is the total number of steps that the agent
completes during an episode. The choice of these hyperparameters are highly
correlated, and both should be selected in such a way that gives the agent the
capability of spanning all the image. To see their effect on the performance
of our method, we picked these parameters from the set:
$\\{(b,K):(1,20),(1,40),(3,20),(7,15)\\}$ and the results of applying FewXAT
on miniImagenet using Protonet(Conv-4) are reported in Table 3. The size of
images are $84\times 84$. As can be seen, by setting the step size to 1, which
is very small, completing 20 steps is not enough to explore all the images,
and by doubling the step size, the performance has improved significantly.
However, increasing $K$ slows down the training process, which is not desired.
Setting $b$ to 7, which is a large step size, does not yield an acceptable
result as it causes the agent to jump from some important and informative
regions and never find them. Therefore, there should be a trade-off in
selecting $b$ and $K$. The slower step size has a positive effect on the
performance, but makes the policy training too slow. On the other hand,
setting it too large can disrupt the search process. We picked $(3,20)$, as
the best values for our method.

### Run time improvement

The Proposed FewXAT method reduces the data size by keeping the maximum of
$1/3$ of the image; therefore, the number of parameters needed to train the
baseline classifier reduces, leading to faster training and testing of it. To
prove this argument, we train and test our baseline, which is ProtoNet (with
Conv-4), on miniImageNet with the original data, and with only the three
selected attentive regions and compare their run time which are presented in
Table 4. The first row shows the training and testing run time of the baseline
after selecting the attentive regions in the images while the second row shows
these run times with the original data. As was expected, by selecting the
attentive areas, the run time significantly decreases in both the training and
testing phases, which is especially beneficial for resource efficiency and
online applications. One Tesla P100-PCIE-16GB GPU is used to run these
experiments.

Table 4:  Run time (in hours) of training ProtoNet (with Conv-4) with and without FewXAT. MiniImageNet | 5-s 5-w | 1-s 5-w
---|---|---
training | testing | training | testing
With FewXAT | 10.23 | 0.15 | 4.16 | 0.03
Without FewXAT | 21.33 | 0.22 | 12.32 | 0.12

### Beyond few-shot learning

To show the effectiveness of our proposed method on other tasks rather than
few-shot learning, we chose the classification task of two popular benchmark
datasets which are ImageNet10 and ImageNetdog. The two datasets are subsets of
the popular ImageNet data. As the baseline, we selected Conv-4, and ResNet-50.
The accuracy results before and after applying FewXAT, i.e. selecting the
attentive are presented in Table 5. The last row of the table indicates our
proposed method could improve the performance of the baseline models while
removing the redundant information and reducing the data size as a result.
This experiment confirms the proposed framework is not only advantageous in
few-shot learning, but it can go beyond that and be used in other tasks such
as classification and representation learning while providing an interpretable
patch selection.

Table 5: Classification accuracy (in percent) of the two different baseline models with and without FewXAT. Method |  ImageNet10 |  ImageDog
---|---|---
Conv-4 |  66.08 |  53.21
ResNet50 |  70.23 |  58.94
FewXAT(Conv-4) |  69.27 |  56.11
FewXAT(ResNet50) |  72.18 |  60.64

## Conclusion

Our paper introduces FewXAT, a novel Explainable Attention mechanism designed
to enhance few-shot learning performance by finding hard attention. We used
deep reinforcement learning to detect attentive regions. Our hypothesis was
that by identifying informative patches within images, we could improve the
adaptability of models to new classes with limited labeled data. Experimental
results support the efficacy of our approach, showing performance improvements
or maintenance in few-shot learning tasks along with a significant decrease in
complexity and enhanced interpretability. The FewXAT method demonstrates
promising results in the classification task as well, indicating its potential
applicability in broader computer vision tasks.

## References

  * Alexe et al. (2012) Alexe, B.; Heess, N.; Teh, Y.; and Ferrari, V. 2012.  Searching for objects driven by context.  _Advances in Neural Information Processing Systems_ , 25.
  * Ba, Mnih, and Kavukcuoglu (2014) Ba, J.; Mnih, V.; and Kavukcuoglu, K. 2014.  Multiple object recognition with visual attention.  _arXiv preprint arXiv:1412.7755_.
  * Ba et al. (2015) Ba, J.; Salakhutdinov, R. R.; Grosse, R. B.; and Frey, B. J. 2015.  Learning wake-sleep recurrent attention models.  _Advances in Neural Information Processing Systems_ , 28.
  * Dhillon et al. (2019) Dhillon, G. S.; Chaudhari, P.; Ravichandran, A.; and Soatto, S. 2019.  A baseline for few-shot image classification.  _arXiv preprint arXiv:1909.02729_.
  * Elsayed, Kornblith, and Le (2019) Elsayed, G.; Kornblith, S.; and Le, Q. V. 2019.  Saccader: Improving accuracy of hard attention models for vision.  _Advances in Neural Information Processing Systems_ , 32.
  * Hong et al. (2021) Hong, J.; Fang, P.; Li, W.; Zhang, T.; Simon, C.; Harandi, M.; and Petersson, L. 2021.  Reinforced attention for few-shot learning and beyond.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 913–923.
  * Khosla et al. (2020) Khosla, P.; Teterwak, P.; Wang, C.; Sarna, A.; Tian, Y.; Isola, P.; Maschinot, A.; Liu, C.; and Krishnan, D. 2020.  Supervised contrastive learning.  _Advances in neural information processing systems_ , 33: 18661–18673.
  * Krizhevsky, Hinton et al. (2009) Krizhevsky, A.; Hinton, G.; et al. 2009.  Learning multiple layers of features from tiny images.
  * Kumar Dwivedi et al. (2019) Kumar Dwivedi, S.; Gupta, V.; Mitra, R.; Ahmed, S.; and Jain, A. 2019.  Protogan: Towards few shot learning for action recognition.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops_ , 0–0.
  * Li et al. (2017) Li, Z.; Zhou, F.; Chen, F.; and Li, H. 2017.  Meta-sgd: Learning to learn quickly for few-shot learning.  _arXiv preprint arXiv:1707.09835_.
  * Liu, Johns, and Davison (2019) Liu, S.; Johns, E.; and Davison, A. J. 2019.  End-to-end multi-task learning with attention.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 1871–1880.
  * Majee, Agrawal, and Subramanian (2021) Majee, A.; Agrawal, K.; and Subramanian, A. 2021.  Few-shot learning for road object detection.  In _AAAI Workshop on Meta-Learning and MetaDL Challenge_ , 115–126. PMLR.
  * Mnih et al. (2014) Mnih, V.; Heess, N.; Graves, A.; et al. 2014.  Recurrent models of visual attention.  _Advances in neural information processing systems_ , 27.
  * Mnih et al. (2013) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Graves, A.; Antonoglou, I.; Wierstra, D.; and Riedmiller, M. 2013.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_.
  * Nikpour and Armanfard (2021) Nikpour, B.; and Armanfard, N. 2021.  Joint selection using deep reinforcement learning for skeleton-based activity recognition.  In _2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC)_ , 1056–1061. IEEE.
  * Nikpour and Armanfard (2023a) Nikpour, B.; and Armanfard, N. 2023a.  Spatial Hard Attention Modeling via Deep Reinforcement Learning for Skeleton-Based Human Activity Recognition.  _IEEE Transactions on Systems, Man, and Cybernetics: Systems_.
  * Nikpour and Armanfard (2023b) Nikpour, B.; and Armanfard, N. 2023b.  Spatio-temporal hard attention learning for skeleton-based activity recognition.  _Pattern Recognition_ , 139: 109428.
  * Nikpour, Sinodinos, and Armanfard (2022) Nikpour, B.; Sinodinos, D.; and Armanfard, N. 2022.  Deep reinforcement learning in human activity recognition: A survey.
  * Rangrej and Clark (2021) Rangrej, S. B.; and Clark, J. J. 2021.  A probabilistic hard attention model for sequentially observed scenes.  _arXiv preprint arXiv:2111.07534_.
  * Ranzato (2014) Ranzato, M. 2014.  On learning where to look.  _arXiv preprint arXiv:1405.5488_.
  * Ravi and Larochelle (2016) Ravi, S.; and Larochelle, H. 2016.  Optimization as a model for few-shot learning.  In _International conference on learning representations_.
  * Ren et al. (2019) Ren, M.; Liao, R.; Fetaya, E.; and Zemel, R. 2019.  Incremental few-shot learning with attention attractor networks.  _Advances in neural information processing systems_ , 32.
  * Seifi, Jha, and Tuytelaars (2021) Seifi, S.; Jha, A.; and Tuytelaars, T. 2021.  Glimpse-attend-and-explore: Self-attention for active visual exploration.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 16137–16146.
  * Shi et al. (2021) Shi, G.; Chen, J.; Zhang, W.; Zhan, L.-M.; and Wu, X.-M. 2021.  Overcoming catastrophic forgetting in incremental few-shot learning by finding flat minima.  _Advances in neural information processing systems_ , 34: 6747–6761.
  * Snell, Swersky, and Zemel (2017) Snell, J.; Swersky, K.; and Zemel, R. 2017.  Prototypical networks for few-shot learning.  _Advances in neural information processing systems_ , 30.
  * Vella and Ebejer (2022) Vella, D.; and Ebejer, J.-P. 2022.  Few-shot learning for low-data drug discovery.  _Journal of Chemical Information and Modeling_ , 63(1): 27–42.
  * Wang et al. (2018) Wang, X.; Chen, W.; Wu, J.; Wang, Y.-F.; and Wang, W. Y. 2018.  Video captioning via hierarchical reinforcement learning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 4213–4222.
  * Wang, Gui, and Hebert (2017) Wang, Y.-X.; Gui, L.; and Hebert, M. 2017.  Few-shot hash learning for image retrieval.  In _Proceedings of the IEEE International Conference on Computer Vision Workshops_ , 1228–1237.
  * Welinder et al. (2010) Welinder, P.; Branson, S.; Mita, T.; Wah, C.; Schroff, F.; Belongie, S.; and Perona, P. 2010.  Caltech-UCSD birds 200.
  * Williams (1992) Williams, R. J. 1992.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8(3-4): 229–256.
  * Yan et al. (2019) Yan, S.; Zhang, S.; He, X.; et al. 2019.  A Dual Attention Network with Semantic Embedding for Few-Shot Learning.  In _AAAI_ , volume 33, 9079–9086.
  * Yun et al. (2017) Yun, S.; Choi, J.; Yoo, Y.; Yun, K.; and Young Choi, J. 2017.  Action-decision networks for visual tracking with deep reinforcement learning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2711–2720.