Neural Discovery of Permutation Subgroups

Pavan Karjol Rohan Kashyap Prathosh A P

Department of Electrical Communication Engineering, Indian Institute of
Science, Bengaluru, Karnataka

###### Abstract

We consider the problem of discovering subgroup $H$ of permutation group
$S_{n}$. Unlike the traditional $H$-invariant networks wherein $H$ is assumed
to be known, we present a method to discover the underlying subgroup, given
that it satisfies certain conditions. Our results show that one could discover
any subgroup of type $S_{k}(k\leq n)$ by learning an $S_{n}$-invariant
function and a linear transformation. We also prove similar results for cyclic
and dihedral subgroups. Finally, we provide a general theorem that can be
extended to discover other subgroups of $S_{n}$. We also demonstrate the
applicability of our results through numerical experiments on image-digit sum
and symmetric polynomial regression tasks.

##  1 INTRODUCTION

###  1.1 Background

Deep Learning has proven to be a successful paradigm for learning the
underlying regularities of sensory data such as images, text, and audio (Brown
et al.,, 2020; He et al.,, 2016; Ramesh et al.,, 2022). The data in the
physical world possess a predefined structure with a low-dimensional manifold
approximation within a higher dimensional euclidean space (Cayton,, 2005;
Schölkopf et al.,, 1998). However, the task of supervised learning in such a
high-dimensional data space demands a large number of data points to counter
the curse of dimensionality. Thus, universal function approximations using
neural networks in such a setting can be prohibitively expensive to curate
large datasets for diverse applications such as medical imaging. This calls
for the need for inductive bias to be incorporated into our networks such that
they can utilize these priors for learning valuable representations in the
feature space. Convolutional Neural Networks proposed by (LeCun et al.,, 1995)
incorporate translation equivariance and thus preserve translation symmetry.
This is highly effective for perception tasks since it enables the model with
a notion of locality and symmetry, i.e., the input and label are both
invariant to shifts (preserves this property across layers), and has likewise
shown substantial gains in image recognition tasks as demonstrated in (Szegedy
et al.,, 2017; He et al.,, 2016). However, from a group-theoretic perspective,
CNN happens to represent a particular case of invariance under the action of a
specific group. This leads to studying and understanding its usability when
extended to a more general setting, i.e., equivariance or invariance to any
generic group action. Thus, learning such representations across neural nets
ensures preserving symmetry across the network and efficiently discovering the
underlying factors of data variations by utilizing these priors.

###  1.2 Group Invariance and Equivariance

Learning symmetries from data has been studied extensively in (Senior et al.,,
2020; Raviv et al.,, 2007; Monti et al.,, 2017; Rossi et al.,, 2022).
Invariant and equivariant classes of functions impose a powerful inductive
prior to our models in a statistically efficient manner which aids in learning
useful representations on a wide range of data (Bogatskiy et al.,, 2020;
Esteves,, 2020). Group equivariant or invariant networks (Cohen et al.,, 2018;
Esteves et al.,, 2018) exploit the inherent symmetrical structure in the data,
i.e., equivariance or invariance to a certain set of group operations
(geometric priors) and can thus result in a significant reduction in the
sample complexity and lead to better generalization. This has ubiquitous
applications in various tasks such as predicting protein interactions (Gainza
et al.,, 2020) and estimating population statistics (Zaheer et al.,, 2017).

One of the important classes of group invariance networks corresponds to the
permutation group $(S_{n})$, i.e., the group of all permutations of a set of
cardinality $n$. Zaheer et al., (2017) have focused extensively on the
applicability of permutation equivariance and invariance functions on
arbitrary objects such as sets. Whereas, (Kicki et al.,, 2020) proposes a
$G$-invariant network to approximate functions that are invariant under the
action of any given permutation subgroup of $S_{n}$. Moreover, it is crucial
to consider subgroups of $S_{n}$, since any finite group is isomorphic to a
subgroup of $S_{n}$ (Cayley’s theorem) for some $n$. For example, the
Quarternanian group $Q_{8}$ is isomorphic to a subgroup of $S_{8}$. In
addition, other interesting applications of functions correspond to subgroups
of $S_{n}$. For instance, the area of an $n$-polygon is a
$\mathbb{Z}_{n}$-invariant function of the polygon’s vertices (Kicki et al.,,
2020).

###  1.3 Contributions

In most of the works mentioned earlier, the group (or subgroup) is assumed to
be known a priori. This restricted form of modeling choice leads to reduced
flexibility (also restrictions). It makes incorporating symmetries into our
networks highly infeasible for real-world applications where the underlying
structure is unknown. Motivated by this, we demonstrate a general framework,
i.e., $G$-invariant network and a linear transformation for discovering the
underlying subgroup of $S_{n}$ under certain conditions. Our main
contributions can be summarized as follows:

In this work, we propose a general framework to discover the underlying
subgroup of $S_{n}$ under a broad set of conditions.

  * •

We prove that we could learn any conjugate group (with respect to $G$) via a
linear transformation and $G$-invariant network.

  * •

We extend this approach, i.e., a linear transformation and $G$-invariant
network to different classes of subgroups such as permutation group of $k$
(out of $n$) elements $S_{k}$, cyclic subgroups $\mathbb{Z}_{k}$ and dihedral
subgroups $D_{2k}$. The $G$-invariant networks for the above families are
$S_{n},\mathbb{Z}_{n}$ and $D_{2n}$ respectively. In the latter two cases, $k$
should divide $n$.

  * •

We prove a general theorem that can guide us to discover other classes of
subgroups.

  * •

We substantiate the above results through experiments on image-digit sum and
symmetric polynomial regression tasks.

##  2 PRIOR WORK

###  2.1 Group Invariant and Equivariant Networks

Significant progress has been made in incorporating invariances to deep neural
nets in the last decade (Cohen et al.,, 2019; Cohen and Welling, 2016b, ;
Ravanbakhsh et al.,, 2017; Ravanbakhsh,, 2020; Wang et al.,, 2020). We observe
that most of the invariant neural networks proposed in the literature assume
the knowledge of the underlying symmetry group. Various generalizations, i.e.,
group equivariant or invariant neural networks, are presented in (Cohen et
al.,, 2019; Kondor et al.,, 2018).

Cohen and Welling, 2016a  introduce Group Equivariant Convolutional Neural
Networks (G-CNNs) as a natural extension of the Convolutional Neural Network
to construct a representation with the structure of a linear G-space. Further,
Cohen et al., (2019) presents a general theory for studying G-CNNs on
homogeneous spaces and illustrates a one-to-one correspondence between linear
equivariant maps of feature spaces and convolutions kernels. Cohen and
Welling, 2016b  provides a theoretical framework to study steerable
representations in convolutional neural networks and establish mathematical
connections between representation learning and representation theory.
Ravanbakhsh, (2020) presents the universality of invariant and equivariant
MLPs with a single hidden layer. Additionally, they show the unconditional
universality result for Abelian groups. Kondor and Trivedi, (2018) utilize
both representation theory and noncommutative harmonic analysis to establish
the convolution formulae in a more general setting, i.e., invariance under the
action of any compact group.

###  2.2 Permutation Invariant and Equivariant Networks

Zaheer et al., (2017) demonstrates the applicability of equivariant and
invariant networks on various set-like objects. Further, they show that any
permutation invariant function can be expressed in a standard form, i.e.,
$\rho\left(\sum_{i}\phi\left(x_{i}\right)\right)$, which corresponds to an
elegant deep neural network architecture. Janossy pooling (Murphy et al.,,
2018) extends the same to build permutation invariant functions using a
generic class of functions. The works, as mentioned earlier, focus mainly on
the permutation group $S_{n}$.

Recent works by Kicki et al., (2020) and Maron et al., (2019) provide a
general architecture invariant to any given subgroup of $S_{n}$. Kicki et al.,
(2020) design a $G$-invariant neural network for approximating functions (can
specifically approximate any G-invariant function) $f:X\rightarrow R$ using
$G$-equivariant network and sum-product formulation, where $X$ is a compact
subset of $R^{n\times m}$, for some $n$, $m>0$) for any given permutation
subgroup $G$ of $S_{n}$. They extend this work to study the invariance
properties of hierarchical groups $G<H\leq S_{n}$. However, in most cases, the
underlying subgroup is generally unknown.

###  2.3 Automatic Symmetry Discovery

Dehmamy et al., (2021) introduces the Lie algebra convolutional network
(L-Conv), an infinitesimal version of G-Conv, for automatic symmetric
discovery. Their framework for continuous symmetries relies on Lie algebras
rather than Lie groups and can thus encode an infinite group without
discretizing (Cohen and Welling, 2016a, ) or summing over irreps. They show
that the $L$-Conv network can serve as a building block for constructing any
group equivariant feedforward architecture. They also unveil interesting
connections between equivariant loss and Lagrangians in field theory and
robustness and Euler-Lagrange equations. However, these apply only to Lie
groups and are not specific to subgroups of the permutation groups. Anselmi et
al., (2019) proposes to learn symmetry-adapted representations and also deduce
a regularization scheme for learning these representations without assuming
the knowledge of the underlying subgroup (of $S_{n}$). However, their proposed
solution is implemented in an unsupervised way. Benton et al., (2020) and Zhou
et al., (2020) also propose different methods for learning symmetries when the
group $G$ is unknown.

##  3 PRELIMINARIES

This section gives a brief overview of various mathematical concepts used in
our work. Let $G$ be a group.

  1. 1.

Group action :- The action of $G$ on a set $X$ is defined using the following
map (written as $g\cdot x,\;\forall g\in G\text{ and }x\in X$) :

$\theta:G\times X\rightarrow X,$ (1)

satisfying the following properties :

     * •

$g_{1}\cdot(g_{2}\cdot x)=(g_{1}g_{2})\cdot x\quad\forall g_{1},g_{2}\in
G\text{ and }x\in X$,

     * •

$1\cdot x=x,\quad\forall x\in X$

where $1$ is the identity element of $G$.

  2. 2.

Group invariant function :- A function $f:X\rightarrow Y$ is said to be group
invariant with respect to $G$, if,

$f(x)=f(g\cdot x),\quad\forall g\in G\text{ and }x\in X$ (2)

We call $f$ a $G$-invariant function.

  3. 3.

Group equivariant function :- A function $f:X\rightarrow Y$ is said to be
group equivariant with respect to $G$, if for any $g\in G$, $\exists$
$\tilde{g}\in G$, such that

$f(g\cdot x)=\tilde{g}\cdot f(x),\forall x\in X$ (3)

We call $f$ a $G$-equivariant function.

  4. 4.

Conjugate subgroups :- Two subgroups $G_{1}$ and $G_{2}$ of $G$ are said to be
conjugates, if $\exists g\in G$ such that,

$G_{2}=gG_{1}g^{-1}:=\\{gkg^{-1}:k\in G_{1}\\}$ (4)

  5. 5.

Normal subgroup :- A subgroup $N$ is said to be normal in $G$, if $\forall
g\in G$

$gNg^{-1}=N$ (5)

i.e., there are no subgroups that are conjugate to $N$.

We describe the notations used for various subgroups of $S_{n}$ in Table (1).
Henceforth, unless explicitly mentioned, we follow the notations mentioned in
Table (1).

Table 1: Descriptions of notations Symbol |  Description
---|---
$S_{n}$ |  Permutation group of $n$ elements
$S^{(0)}_{k}$ |  Permutation subgroup of first $k$ elements
$S_{k}$ |  Permutation subgroup of random $k$ elements
$\mathbb{Z}_{n}$ |  Cyclic subgroup of $n$ elements
$\mathbb{Z}^{(0)}_{k}$ |  Cyclic subgroup of first $k$ elements
$\mathbb{Z}_{k}$ |  Cyclic subgroup of random $k$ elements
$D_{2n}$ |  Dihedral subgroup of $n$ elements
$D^{(0)}_{2k}$ |  Dihedral subgroup of first $k$ elements
$D_{k}$ |  Dihedral subgroup of random $k$ elements
$A_{n}$ |  Alternating subgroup of $n$ elements
$A_{k}$ |  Alternating subgroup of random $k$ elements

##  4 PROPOSED WORK

###  4.1 Problem statement

We consider the problem of learning an $H$-invariant function
$f:X\rightarrow\mathbb{R}$, where $X=[0,1]^{n}\subset R^{n}$ and $H$ is the
unknown subgroup of $S_{n}$. In general, learning such a function is
intractable. However, we show that it is possible to learn such a function,
i.e., discover the underlying subgroup $H$, where $H$ belongs to a certain
class of subgroups (we explicitly state our conditions in Theorem 4.3, 4.4 and
4.5). The general consequence of our analysis is that learning a $H$-invariant
function is thus equivalent to learning a $G$-invariant function along with a
linear transformation, given that $G$ and $H$ satisfy certain conditions.
Since any given $G$ can have several such subgroups, we propose to learn the
underlying subgroup $H$ by exploiting the existing structures using a family
of $G$-invariant functions (such as the one mentioned in Zaheer et al., (2017)
for the permutation group $S_{n}$) and a learnable linear transformation. We
formalize these ideas in the coming subsections.

To prove our results, we employ the following theorem regarding
$S_{n}$-invariant functions (Zaheer et al.,, 2017), which shows that any such
function can be expressed in a canonical form.

######  Theorem 4.1 (Deep sets).

$f:X=[0,1]^{n}\rightarrow\mathbb{R}$ is a permutation invariant
($S_{n}$-invariant) continuous function iff if has the representation,

$f(x)=\rho\left(\sum_{i=1}^{n}\gamma(x_{i})\right),\;x=[x_{1},x_{2},\dots
x_{n}]^{T}$ (6)

for some continuous outer and inner functions
$\rho:\mathbb{R}^{n+1}\rightarrow\mathbb{R}$,
$\gamma:[0,1]\rightarrow\mathbb{R}^{n+1}$.

We get the following result if we consider the permutations of the first $k$
elements.

######  Corollary 4.1.1.

$f:[0,1]^{n}\rightarrow\mathbb{R}$ be an $S_{k}^{0}$-invariant continuous
function iff it has the representation,

$f(x)=\rho\left(\sum_{i=1}^{k}\gamma(x_{i}),\;x_{k+1},\dots,x_{n}\right)$ (7)

###### Proof.

To prove Theorem 4.1, it has been shown that (Zaheer et al.,, 2017),
$\mathcal{X}^{(n)}=\\{x_{1},x_{2},\dots,x_{n}\subset[0,1]^{n}:x_{1}\leq
x_{2}\leq x_{3}\dots\leq x_{n}\\}$ is homeomorphic to
$\sum_{i=1}^{n}\gamma(X_{i})$, where

$\gamma(t)=\big{[}1,t,t^{2},\dots t^{n}\big{]}^{T}$ (8)

Hence,
$\mathcal{X}^{(n:k)}=\\{x_{1},x_{2},\dots,x_{n}\subset[0,1]^{n}:x_{1}\leq
x_{2}\leq x_{3}\dots\leq x_{k}\\}$ is homeomorphic to
$\sum_{i=1}^{k}\gamma(X_{i})\times[0,1]^{n-k}$. Let,
$E(x)=\Big{[}\sum_{i=1}^{k}\gamma(x_{i}),\;x_{k+1},\dots,x_{n}\Big{]}^{T}$.
Then, it is an homeomorphism from $\mathcal{X}^{(n:k)}$ to $Im(E)$ (Image of
E). If we set $\rho=fE^{-1}$, we get $\rho\left(E(x)\right)=f(x)$. ∎

We use the same definition of $\gamma$ (Zaheer et al.,, 2017) provided in the
eq. (8) in the subsequent results as well. Now, we state our first result
using the conjugacy relation between subgroups.

######  Lemma 4.2.

Any $S_{k}$-invariant function $\psi$, can be realized through composition of
an $S_{k}^{(0)}$-invariant function $\phi$ and a linear transformation $M$,
i.e., $\psi=\phi\cdot M$. In addition, $\psi$ can be realised through the
following form,

$\psi(x)=\rho\left(\sum_{i=1}^{k}\gamma\left(m_{i}^{T}x\right),\;m_{k+1}^{T}x,\dots,m_{n}^{T}x\right),$
(9)

where $m_{i}$ is the $i^{th}$ row of $M$.

###### Proof.

Note that any $S_{k}$ is conjugate to $S_{k}^{(0)}$. Thus, $\exists$ $g\in
S_{n}$ such that

$S_{k}^{(0)}=gS_{k}g^{-1}$ (10)

Let $\psi:X\rightarrow R$ be an $S_{k}$-invariant function, i.e.,

$\displaystyle\psi(x)$ $\displaystyle=\psi(h\cdot x),\quad\forall h\in
S_{k},x\in X$ $\displaystyle\psi(\left(g^{-1}g\right)\cdot x)$
$\displaystyle=\psi(\left(g^{-1}ug\right)\cdot x),\quad\forall u\in
S_{k}^{(0)}$ $\displaystyle(\psi g^{-1})(g\cdot x)$ $\displaystyle=(\psi
g^{-1})(u\cdot(g\cdot x))$ $\displaystyle(\psi g^{-1})\left(Mx\right)$
$\displaystyle=(\psi g^{-1})(u\cdot\left(Mx\right))$ (11)

From eq. (11), we see that $\phi=\psi\cdot g^{-1}$ and $M=g$ are the desired
$S_{k}^{(0)}$\- invariant function and the linear transformation respectively
and $\phi=\psi\cdot M$. We get the second part of the result by applying
Corollary 7 to $\phi$. ∎

We could also relax the conjugacy condition, i.e., discover subgroups of type
$S_{k}$ when $k$ itself is unknown. This is formalized in the following
result.

######  Theorem 4.3 (Subgroups of type $S_{k}$).

Any $S_{k}$-invariant function ($k\leq n$) $\psi$, can be realised using an
$S_{n}$-invariant function and a linear transformation, in specific, it can be
realised through the following form,

$\psi(x)=\left(\phi\cdot\hat{M}\right)(x)=\rho\left(\begin{bmatrix}(I-M)x\\\
\sum_{i=1}^{n}\gamma\left(m_{i}^{T}x\right)\end{bmatrix}\right)$ (12)

where $\hat{M}=\begin{bmatrix}I-M\\\ M\end{bmatrix}$ and
$\phi(y)=\Big{[}y_{1},\dots,y_{n},\;\sum_{i=1}^{n}\gamma(y_{n+i})\Big{]}^{T}$

###### Proof.

Since $S_{k}$ is conjugate to $S_{k}^{0}$, it is enough to prove the result
for $S_{k}^{0}$-invariant function. Hence, the goal is to show that
$(I-M)X\times\sum_{i=1}^{n}\gamma\left(m_{i}^{T}X\right)$is homeomorphic to
$\sum_{m=1}^{k}\gamma(X_{m})\times[0,1]^{n-k}$ (from Corollary 7 and Lemma
4.2) for some linear transformation $M$. Suppose,

$M=\begin{bmatrix}I_{k\times k}&0\\\ 0&0\end{bmatrix},$ (13)

then,

$\begin{bmatrix}(I-M)x\\\
\sum_{i=1}^{n}\gamma\left(m_{i}^{T}x\right)\end{bmatrix}=\begin{bmatrix}\textbf{0}^{(k)}\\\
x_{k+1}\\\ .\\\ .\\\ x_{n}\\\
B+\sum_{i=1}^{k}\gamma\left(x_{i}\right)\end{bmatrix},$ (14)

where $B=(n-k)\gamma(0)$ and $\textbf{0}^{(k)}$ is $k$-dimensional zero
vector. Thus, from RHS of the eq. (14), the above claim follows. (Note that,
the function $Mx\mapsto\sum_{i=1}^{n}\gamma\left(m_{i}^{T}x\right)$ is
$S_{n}$-invariant and $\phi$ is $S_{2n}^{n}$-invariant function). ∎

We now extend our method to cyclic and dihedral subgroups of $S_{n}$ and state
the following result.

######  Theorem 4.4 (Cyclic and Dihedral subgroups).

If $k|n$, any $\mathbb{Z}_{k}$-invariant (or $D_{2k}$-invariant) function
$\psi$, can be realised using a $\mathbb{Z}_{n}$-invariant (or
$D_{2n}$-invariant) function $\phi$ and a linear transformation, in specific,
it can be realised through the following form,

$\psi(x)=\left(\phi\cdot\hat{M}\right)(x)$ (15)

where $\hat{M}=\begin{bmatrix}M\\\ I-L\end{bmatrix}$ for some
$M,L\in\mathbb{R}^{n\times n}$.

###### Proof.

In this proof, without loss of generality, we prove the result for
$\mathbb{Z}_{k}^{(0)}$-invariant function. Suppose,

$M=\begin{bmatrix}I_{k\times k}&0\\\ I_{k\times k}&0\\\ \vdots&\vdots\\\
I_{k\times k}&0\end{bmatrix},\quad L=\begin{bmatrix}I_{k\times k}&0\\\
0&0\end{bmatrix},$ (16)

Since $k|n$, we can stack the $I_{k\times k}$ matrices as shown in eq. (16).
Then, $M:X\rightarrow X$ is defined as,

$\displaystyle x=[x_{1},x_{2}\dots x_{n}]^{T}\longmapsto Mx=$
$\displaystyle[x_{1},x_{2},\dots x_{k},$ $\displaystyle
x_{1},x_{2},\dots,x_{k},$ $\displaystyle\vdots$ $\displaystyle
x_{1},x_{2},\dots,x_{k}]^{T}$ (17)

Under the action of $\mathbb{Z}_{k}$ ($h\cdot x$, for some
$h\in\mathbb{Z}_{k}$), we get that,

$x\xmapsto{h}x^{\prime}=[x_{u},x_{u+1},\dots,x_{k},x_{1},\dots,x_{u-1}]^{T}$
(18)

which corresponds to ($g\cdot\left(Mx\right)$, for some $g\in\mathbb{Z}_{n}$),

$\displaystyle Mx\xmapsto{g}$ $\displaystyle
Mx^{\prime}=[x_{u},x_{u+1},\dots,x_{k},x_{1},\dots,x_{u-1}$ $\displaystyle
x_{u},x_{u+1},\dots,x_{k},x_{1},\dots,x_{u-1}$ $\displaystyle\vdots$
$\displaystyle x_{u},x_{u+1},\dots,x_{k},x_{1},\dots,x_{u-1}]^{T}$ (19)

Similarly, the converse is also true, i.e., $\mathbb{Z}_{n}$-action on $Mx$
corresponds to $\mathbb{Z}_{k}$-action on $x$. Hence, the
$\mathbb{Z}_{k}$-invariant function of $x$ corresponds to
$\mathbb{Z}_{n}$-invariance of $Mx$. Note that, the
$\mathbb{Z}_{n}$-invariance of the function $\phi$ is with respect to the
first $n$ elements (out of $2n$) of its input vector. Similar proof holds for
dihedral groups ($D_{2k}$ and $D_{2n}$). ∎

The above set of techniques can also be extended to other classes of
subgroups. In this regard, we state the following general result.

######  Theorem 4.5.

Any $H$-invariant function $\psi$ can be learnt through composing a
$G$-invariant function $\phi$ with a linear transformation $M$, i.e.,
$\psi=\phi\cdot M$ if the following conditions hold,

  1. 1.

For any $h\in H,$ $\exists g\in G$ such that $M(h\cdot
x)=g\cdot\left(Mx\right),\>\forall x\in X$

  2. 2.

For any $g\in G$ such that $g\cdot\left(Mx\right)\in R(M)$, $\exists h\in H$
such that $M(h\cdot x)=g\cdot\left(Mx\right),\>\forall x\in X$, where $R(M)$
is the range of $M$.

###### Proof.

The claim directly follows from the following observations.

Condition (1) states that, any action $h\cdot x$ (action of $H$ on $X$)
corresponds to an action $g\cdot(Mx)$ (action of $G$ on $R(M)$).

Similarly, condition (2) states that, any action $g\cdot(Mx)$ corresponds to
an action $h\cdot x$. ∎

##  5 DISCUSSION

The underlying theme from the results stated in the previous section is that
we could discover any subgroup belonging to a particular class of subgroups by
learning a $G$-invariant function and a linear transformation. Depending on
the class, the chosen G varies. We further elaborate on these observations in
the following subsections.

Figure 1: Generic framework for learning $H$-invariant function. The dotted
arrows point towards specific examples of linear and $G$-invariant functions.
The corresponding $H$-invariant functions are $S_{k}$-invariant and
$\mathbb{Z}_{k}$-invariant.

###  5.1 Conjugate Groups

In Lemma 4.2, the class of subgroups corresponds to those of type $S_{k}$
(fixed $k$) and the corresponding $G$ can be $S_{k}^{0}$. We observe that, for
a fixed $k$, even if we don’t know the exact underlying subgroup $S_{k}$(a
total of $\binom{n}{k}$ possibilities), we could learn this unknown subgroup.
In addition, we also incorporate the canonical form of permutation invariant
functions in the resulting architecture. Moreover, this result can be
generalized to any class of conjugate subgroups, and the corresponding $G$ is
one of these conjugate groups. The significance of this result lies in the
fact that a variety of subgroups are related through conjugation. For
instance, all $\mathbb{Z}_{k}$ form one conjugacy class for a given $k$, and
so does $A_{k}$’s.

This result is not entirely helpful if the underlying subgroup is normal since
it is not conjugate to any other subgroup. However, this is not much of a
hindrance since the only non-trivial proper normal subgroup of $S_{n}$ is
$A_{n},\;\forall n\geq 5$.

###  5.2 $S_{k}$, $\mathbb{Z}_{k}$ and $D_{2k}$ Subgroups

Theorem 4.3 focuses on subgroups of type $S_{k}$ (varying $k$ and
$k\in\\{1,2,\dots,n\\}$), and the corresponding $G$ is $S_{n}$ itself. We
incorporate the canonical form of permutation invariant functions here as
well. We observe that the number of such subgroups is $2^{n}-1$ for a given
$n$. Hence, we could learn any of these subgroups with the standard
architecture of an $S_{n}$-invariant function and a linear transformation.
Note that if $k$ is fixed, either of the architectural forms given by Lemma
4.2 and Theorem 4.3 is applicable. We will discuss the corresponding empirical
results in the coming sections. Theorem 4.4 considers subgroups of the cyclic
$\mathbb{Z}_{k}$ and dihedral group $D_{2k}$. The corresponding $G$-invariant
functions are of $\mathbb{Z}_{n}$ and $D_{2n}$, respectively.

###  5.3 Generalization

Theorem 4.5 presents a general set of conditions to be satisfied to learn any
$H$-invariant function using a $G$ invariant function and a linear
transformation. As such, the previous results are specific cases of this
Theorem. However, they provide explicit structures of the linear
transformation $M$. These can help design appropriate training techniques to
learn the optimum $M$, while the general result of Theorem 4.5 can guide us
towards discovering results for new classes of subgroups.

###  5.4 Limitations

The proposed framework presumes the knowledge of the underlying class of
subgroups apriori (but not the exact subgroup) and an appropriate value of $n$
for $S_{n}$, $\mathbb{Z}_{n}$ or $D_{2n}$ invariant functions. The drawbacks
mentioned here are interesting research directions to pursue in the future.

##  6 EXPERIMENTS

We evaluate the accuracy of our proposed method on image-digit sum and
symmetric polynomial regression tasks. The problem of image-digit sum can be
modified and cast as learning an $S_{k}$-invariant function, while the
polynomial regression task intrinsically corresponds to learning a
$G$-invariant function. These are summarized in the following subsections.

###  6.1 Image-Digit Sum

This task aims to find the sum of $k$ digits using the MNISTm (Loosli et al.,
(2007)) handwritten digits dataset. It consists of $8$ million gray scale
$28\times 28$ images of digits $\\{0,1,...,9\\}$. We employ a training set of
$150k$ samples and a test set of $30k$ samples. We consider the following
approaches for evaluation.

  1. 1.

Deep Sets-$S_{k}$:- $S_{k}$-invariant neural network proposed by Zaheer et
al., (2017).

  2. 2.

LSTM:- LSTM network as mentioned in Zaheer et al., (2017).

  3. 3.

Proposed method:- A linear layer followed by an $S_{n}$-invariant network.

For the LSTM network and the proposed method, the input is a random sample of
$n$ ($n$ = 10) images, and the target is the sum of $k$ ($k$ less than $n$)
digit labels. We run separate experiments for each of $k\in\\{1,3,5,7,9\\}$.
Since all $n$ images are given as input, the two approaches are agnostic of
the underlying subgroup. However, we feed only these $k$ of these images as
input for the first approach, while the target output remains the same. As
such, this task is equivalent to learning an $S_{k}$-invariant function.

###  6.2 Symmetric Polynomial Regression

We evaluate the performance of our method on symmetric polynomial regression
tasks as discussed in Kicki et al., (2020), primarily for subgroups of
$\mathbb{Z}_{10}$ and $\mathbb{Z}_{16}$. For all our experiments, we utilize a
$\mathbb{Z}_{n}$-invariant neural network with a Sum-Product layer as
discussed in Kicki et al., (2020) and a linear layer. First, we run our
experiments for subgroups of $\mathbb{Z}_{10}$, i.e., $\mathbb{Z}_{5}$ and the
group itself (trivial subgroup). We then access the performance for subgroups
of $\mathbb{Z}_{16}$, namely $\mathbb{Z}_{2}$, $\mathbb{Z}_{4}$,
$\mathbb{Z}_{8}$, $\mathbb{Z}_{16}$ using a similar architectural design. We
consider the following approaches for evaluation.

  1. 1.

G-invariant:- $\mathbb{Z}_{k}$-invariant neural network proposed by Kicki et
al., (2020). In this context, $G=\mathbb{Z}_{k}$.

  2. 2.

Simple-FC:- A stack of fully-connected feedforward layers.

  3. 3.

Conv-1D:- A simple convolutional neural network and feedforward layers.

  4. 4.

Proposed method:- A linear layer followed by a $\mathbb{Z}_{n}$-invariant
network.

The architectural details of the models considered in our experiments are
discussed in the appendix section.

##  7 RESULTS

###  7.1 Image-Digit Sum

The test mean absolute errors (MAEs) for the image-digit sum task are shown in
Table 2. We observe that the proposed method outperforms the LSTM baseline and
is competitive with respect to the Deep Sets method (k input images) when the
underlying subgroup $S_{k}$ is known. In addition, our method converges faster
when compared to the LSTM network, which is apparent from the plots for the
training and validation errors in Figure 2.

Table 2: MAE [$\times 10^{-2}$] for Image Digit-Sum task

Method | $S_{1}$ | $S_{3}$ | $S_{5}$ | $S_{7}$ | $S_{9}$
---|---|---|---|---|---
Deep Sets-$S_{k}$ | $5.61\pm 0.35$ | $7.66\pm 0.26$ | $8.02\pm 0.2$ | $7.68\pm 0.43$ | $6.97\pm 0.39$
Proposed | $5.73\pm 0.39$ | $7.78\pm 0.49$ | $8.19\pm 0.36$ | $7.84\pm 0.41$ | $7.26\pm 0.58$
LSTM | $6.23\pm 0.53$ | $9.65\pm 0.57$ | $11.98\pm 0.46$ | $13.35\pm 1.02$ | $12.92\pm 1.42$

Figure 2: Training and Validation loss (MAE) for Image-Digit Sum using MNIST
dataset.

###  7.2 Symmetric Polynomial Regression

In the $\mathbb{Z}_{k}$-invariant polynomial regression task, we train our
models for 2500 epochs for each of the subgroups of $\mathbb{Z}_{5}$ and
$\mathbb{Z}_{10}$.

In Table 3, 4 and 5 we compare the given baselines with our proposed method
for the task of discovering unknown subgroups. Our method outperforms the
Simple-FC and Conv-1D baseline networks for each of the given subgroups. As
expected, it does not match the baseline architecture, the
$\mathbb{Z}_{k}$-invariant network (the subgroup is known apriori for this
baseline) by a significant margin for each of the diverse set of subgroups we
have considered in this task. However, in a few cases, we observe large
standard deviations and attribute such values to outliers. A detailed version
of our results and the mathematical definition of the polynomials is presented
in the appendix section.

From Figure 3, it is evident that the $\mathbb{Z}_{5}$-invariant function
outperforms both our method and the baselines by a significant margin. The
Simple FC and Conv-1D networks have very similar performances and show no
prominent effect, even with an increase in data size.

Table 3: MAE $[\times 10^{-2}]$ for $\mathbb{Z}_{5}:\mathbb{Z}_{10}$

Method | Train | Validation | Test
---|---|---|---
$\mathbb{Z}_{5}$-invariant | $2.65\pm 0.91$ | $7.32\pm 0.55$ | $7.53\pm 0.576$
Proposed | $4.48\pm 1.25$ | $24.56\pm 6.93$ | $24.78\pm 6.45$
Conv-1D | $20.90\pm 4.91$ | $32.96\pm 1.31$ | $32.33\pm 1.18$
Simple-FC | $23.86\pm 3.87$ | $33.57\pm 2.07$ | $33.14\pm 2.11$

Table 4: MAE $[\times 10^{-2}]$ for $\mathbb{Z}_{10}:\mathbb{Z}_{10}$

Method | Train | Validation | Test
---|---|---|---
$\mathbb{Z}_{10}$-invariant | $6.89\pm 1.31$ | $16.68\pm 0.55$ | $17.16\pm 0.56$
Proposed | $14.52\pm 1.72$ | $39.69\pm 4.13$ | $40.11\pm 4.17$
Conv-1D | $35.71\pm 2.71$ | $52.96\pm 0.70$ | $50.63\pm 1.33$
Simple-FC | $46.13\pm 2.27$ | $54.62\pm 1.34$ | $51.64\pm 0.89$

Table 5: MAE $[\times 10^{-2}]$ for $\mathbb{Z}_{4}:\mathbb{Z}_{16}$

Method | Train | Validation | Test
---|---|---|---
$\mathbb{Z}_{4}$-invariant | $1.21\pm 0.25$ | $3.41\pm 0.4$ | $3.54\pm 0.39$
Proposed | $3.32\pm 1.65$ | $23.70\pm 4.87$ | $24.69\pm 5.25$
Conv-1D | $8.39\pm 3.02$ | $31.34\pm 0.77$ | $31.10\pm 0.87$
Simple-FC | $7.27\pm 5.03$ | $30.82\pm 1.74$ | $30.83\pm 1.61$

###  7.3 Effect of the data size on the performance

This section aims to assess the effect of the dataset size in learning
$\mathbb{Z}_{k}$-invariant functions using our proposed method and hope to
gain a better understanding in such a setting. To analyze our model
performance with respect to data size, we use 16, 32, and 64 data points for
training (as mentioned in Kicki et al., (2020), we randomly sample these
values from [0,1]) and use 480 and 4800 as validation and test sets
respectively to assess the generalization ability for each of these methods as
mentioned above. We report the mean and standard deviation values across 10
randomly initialized iterations.

Figure 3: The MAE value comparisons using the test dataset for all the models
we have considered for the $\mathbb{Z}_{5}:\mathbb{Z}_{10}$ task. The $X$-axis
represents the size of the training set $(16,32,64)$.

We also examine the Simple-FC and Conv-1D network by increasing its parameter
count, i.e., varying the number of neurons in each layer. However, we observe
no significant gains in doing so, as mentioned in the appendix section for at
least a few subgroups.

###  7.4 Interpretability

(a) $S_{5}$

(b) $S_{9}$

Figure 4: $M$ matrices for $S_{5}$ and $S_{9}$ after training.

####  7.4.1 Image-Digit Sum

The resulting M matrix is interpretable, and we consistently observe the
expected pattern for the image-digit sum task. Note that any row-permuted
version of the matrix structure, as shown in eq.  (13) will work since the
transformed space is still homeomorphic. The $M$ matrices for $S_{5}$ and
$S_{9}$ (extracted after training) are depicted in Figure 4. The columns with
dark green squares match the actual indices.

Figure 5: (a) $M$ matrix for $\mathbb{Z}_{4}:\mathbb{Z}_{16}$ (b) Reference
matrix.

####  7.4.2 Polynomial Regression

We observe that the $M$-matrix extracted after training (Figure (5.a)) does
not exactly capture the expected pattern, i.e., a stack of identity matrices
(Figure (5.b)), even though it nearly masks most of the irrelevant columns
($n-k$). The former behavior (lack of exact structure) explains the difference
in performance with respect to the $\mathbb{Z}_{k}$-invariant network, while
the latter (masking behavior) describes the superior model performance
compared to other baselines. Also, the masking of irrelevant columns already
conveys the underlying subgroup; thus, we use this information to estimate the
true indices. We estimate the significant indices using the $L1$-norm of
columns of $M$ and the mean as the threshold. The results (for different
number of training data points $N$ and different
$\mathbb{Z}_{k}:\mathbb{Z}_{n}$’s) of the success rate of the estimation are
given in Table 6, where we count the estimation as success when the estimated
indices exactly match the true indices; otherwise, as a failure. We run each
experiment for $10$ trials. We get high estimation accuracy in most of the
cases except for $N=16$. The estimated indices can be used to run a
$\mathbb{Z}_{k}$-invariant network (or proposed method with fixed $M$) and
obtain better performance on regression tasks.

Table 6: Estimation Accuracy (in %) ${Z}_{k}:{Z}_{n}$ | $16$ | $32$ | $64$
---|---|---|---
${Z}_{4}:{Z}_{16}$ | $100$ | $100$ | $100$
${Z}_{5}:{Z}_{10}$ | $80$ | $100$ | $100$
${Z}_{8}:{Z}_{16}$ | $30$ | $80$ | $100$

##  8 CONCLUSION

In this work, we studied the problem of discovering the underlying subgroup of
$S_{n}$, i.e., learning a $H$-invariant function where $H$ is an unknown
subgroup of $S_{n}$. We proved that we could learn any $H$-invariant function
using a $G$-invariant function and a linear transformation provided $H$
belongs to a specific class of subgroups. We considered various subgroups,
such as conjugate subgroups, permutation subgroups of $k$ elements, and cyclic
and dihedral subgroups, and illustrated unique structures of the corresponding
linear transformations. We demonstrated the validity of our theoretical
analysis through empirical results. We also discussed the limitations of our
method, which may lead to exciting research directions in the future.

## References

  * Anselmi et al., (2019) Anselmi, F., Evangelopoulos, G., Rosasco, L., and Poggio, T. (2019).  Symmetry-adapted representation learning.  Pattern Recognition, 86:201–208.
  * Benton et al., (2020) Benton, G., Finzi, M., Izmailov, P., and Wilson, A. G. (2020).  Learning invariances in neural networks from training data.  Advances in neural information processing systems, 33:17605–17616.
  * Bogatskiy et al., (2020) Bogatskiy, A., Anderson, B., Offermann, J., Roussi, M., Miller, D., and Kondor, R. (2020).  Lorentz group equivariant neural network for particle physics.  In International Conference on Machine Learning, pages 992–1002. PMLR.
  * Brown et al., (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020).  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901.
  * Cayton, (2005) Cayton, L. (2005).  Algorithms for manifold learning.  Univ. of California at San Diego Tech. Rep, 12(1-17):1.
  * (6) Cohen, T. and Welling, M. (2016a).  Group equivariant convolutional networks.  In International conference on machine learning, pages 2990–2999. PMLR.
  * Cohen et al., (2018) Cohen, T. S., Geiger, M., Köhler, J., and Welling, M. (2018).  Spherical cnns.  arXiv preprint arXiv:1801.10130.
  * Cohen et al., (2019) Cohen, T. S., Geiger, M., and Weiler, M. (2019).  A general theory of equivariant cnns on homogeneous spaces.  Advances in neural information processing systems, 32.
  * (9) Cohen, T. S. and Welling, M. (2016b).  Steerable cnns.  arXiv preprint arXiv:1612.08498.
  * Dehmamy et al., (2021) Dehmamy, N., Walters, R., Liu, Y., Wang, D., and Yu, R. (2021).  Automatic symmetry discovery with lie algebra convolutional network.  Advances in Neural Information Processing Systems, 34:2503–2515.
  * Derksen and Kemper, (2001) Derksen, H. and Kemper, G. (2001).  Computational invariant theory.  Book manuscript.
  * Esteves, (2020) Esteves, C. (2020).  Theoretical aspects of group equivariant neural networks.  arXiv preprint arXiv:2004.05154.
  * Esteves et al., (2018) Esteves, C., Allen-Blanchette, C., Makadia, A., and Daniilidis, K. (2018).  Learning so (3) equivariant representations with spherical cnns.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 52–68.
  * Gainza et al., (2020) Gainza, P., Sverrisson, F., Monti, F., Rodola, E., Boscaini, D., Bronstein, M., and Correia, B. (2020).  Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning.  Nature Methods, 17(2):184–192.
  * He et al., (2016) He, K., Zhang, X., Ren, S., and Sun, J. (2016).  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778.
  * Kicki et al., (2020) Kicki, P., Ozay, M., and Skrzypczyński, P. (2020).  A computationally efficient neural network invariant to the action of symmetry subgroups.  arXiv preprint arXiv:2002.07528.
  * Kondor et al., (2018) Kondor, R., Lin, Z., and Trivedi, S. (2018).  Clebsch–gordan nets: a fully fourier space spherical convolutional neural network.  Advances in Neural Information Processing Systems, 31.
  * Kondor and Trivedi, (2018) Kondor, R. and Trivedi, S. (2018).  On the generalization of equivariance and convolution in neural networks to the action of compact groups.  In International Conference on Machine Learning, pages 2747–2755. PMLR.
  * LeCun et al., (1995) LeCun, Y., Bengio, Y., et al. (1995).  Convolutional networks for images, speech, and time series.  The handbook of brain theory and neural networks, 3361(10):1995.
  * Loosli et al., (2007) Loosli, G., Canu, S., and Bottou, L. (2007).  Training invariant support vector machines using selective sampling.  Large scale kernel machines, 2.
  * Maron et al., (2019) Maron, H., Fetaya, E., Segol, N., and Lipman, Y. (2019).  On the universality of invariant networks.  In International conference on machine learning, pages 4363–4371. PMLR.
  * Monti et al., (2017) Monti, F., Boscaini, D., Masci, J., Rodola, E., Svoboda, J., and Bronstein, M. M. (2017).  Geometric deep learning on graphs and manifolds using mixture model cnns.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115–5124.
  * Murphy et al., (2018) Murphy, R. L., Srinivasan, B., Rao, V., and Ribeiro, B. (2018).  Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs.  arXiv preprint arXiv:1811.01900.
  * Ramesh et al., (2022) Ramesh, A., Dhariwal, P., Nichol, A., Chu, C., and Chen, M. (2022).  Hierarchical text-conditional image generation with clip latents.  arXiv preprint arXiv:2204.06125.
  * Ravanbakhsh, (2020) Ravanbakhsh, S. (2020).  Universal equivariant multilayer perceptrons.  In International Conference on Machine Learning, pages 7996–8006. PMLR.
  * Ravanbakhsh et al., (2017) Ravanbakhsh, S., Schneider, J., and Poczos, B. (2017).  Equivariance through parameter-sharing.  In International conference on machine learning, pages 2892–2901. PMLR.
  * Raviv et al., (2007) Raviv, D., Bronstein, A. M., Bronstein, M. M., and Kimmel, R. (2007).  Symmetries of non-rigid shapes.  In 2007 IEEE 11th International Conference on Computer Vision, pages 1–7. IEEE.
  * Rossi et al., (2022) Rossi, E., Monti, F., Leng, Y., Bronstein, M., and Dong, X. (2022).  Learning to infer structures of network games.  In International Conference on Machine Learning, pages 18809–18827. PMLR.
  * Schölkopf et al., (1998) Schölkopf, B., Smola, A., and Müller, K.-R. (1998).  Nonlinear component analysis as a kernel eigenvalue problem.  Neural computation, 10(5):1299–1319.
  * Senior et al., (2020) Senior, A. W., Evans, R., Jumper, J., Kirkpatrick, J., Sifre, L., Green, T., Qin, C., Žídek, A., Nelson, A. W., Bridgland, A., et al. (2020).  Improved protein structure prediction using potentials from deep learning.  Nature, 577(7792):706–710.
  * Szegedy et al., (2017) Szegedy, C., Ioffe, S., Vanhoucke, V., and Alemi, A. A. (2017).  Inception-v4, inception-resnet and the impact of residual connections on learning.  In Thirty-first AAAI conference on artificial intelligence.
  * Wang et al., (2020) Wang, R., Walters, R., and Yu, R. (2020).  Incorporating symmetry into deep dynamics models for improved generalization.  arXiv preprint arXiv:2002.03061.
  * Zaheer et al., (2017) Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, A. J. (2017).  Deep sets.  Advances in neural information processing systems, 30.
  * Zhou et al., (2020) Zhou, A., Knowles, T., and Finn, C. (2020).  Meta-learning symmetries by reparameterization.  arXiv preprint arXiv:2007.02933.

Supplementary Materials

##  9 Appendix

###  9.1 Remarks regarding theoretical results

  * •

To obtain the function $\rho$ mentioned in Lemma 4.2, Theorem 4.3, and Theorem
4.4 of the main paper, we use the same technique presented in the proof of
Corollary 7, i.e., $\rho=\psi E^{-1}$, where $E$ is the corresponding
homeomorphism.

  * •

Lemma 4.2, Theorem 4.3, and Theorem 4.4 are special cases of Theorem 4.5. This
claim directly follows once we specify the corresponding group actions. As
such, the proofs of Lemma 4.2 and Theorem 4.4 already describe the required
group actions. However, this is not obvious in Theorem 4.3. In that case, we
observe the following:

$\displaystyle x=[x_{1},x_{2}\dots x_{n}]^{T}\longmapsto Mx=$
$\displaystyle[0,0,\;\overset{k}{\dots}\;,0,\;x_{k+1},x_{k+2},\dots x_{n},$
$\displaystyle x_{1},x_{2},\dots x_{k},\;0,0,\;\overset{n-k}{\dots}\;,0]^{T},$
(20)

where $M=\begin{bmatrix}I_{k\times k}&0\\\ 0&0\end{bmatrix}$ as mentioned in
eq. (13) of the main paper.

Under the action of $S_{k}^{(0)}$ ($h\cdot x,\;$ for some $h\in S_{k}^{(0)}$
), we get,

$x\xmapsto{h}x^{\prime}=[x_{h(1)},x_{h(2)},\dots,x_{h(k)},x_{k+1},\dots,x_{n}]^{T}$
(21)

which corresponds to ($g\cdot\left(Mx\right)$, for some $g\in S^{n}_{2n}$ )
($S^{n}_{2n}$ is the group of permutations of first $n$ elements out of $2n$
elements),

$\displaystyle Mx\xmapsto{g}Mx^{\prime}=$
$\displaystyle[0,0,\;\overset{k}{\dots}\;0,\;x_{k+1},x_{k+2},\dots,x_{n},$
$\displaystyle
x_{g(1)},x_{g(2)},\dots,x_{g(k)},\;0,0,\;\overset{n-k}{\dots}\;,0]^{T}$ (22)

Similary, the action of $S^{n}_{2n}$ on $R(M)$ (range of M) corresponds to the
action of $S_{k}^{(0)}$ on $X$.

In the following subsections, we describe the architectures of various models
and additional resutls considered in our experiments.

Table 7: MAE [$\times 10^{-2}$] Image Digit-Sum task

Method | $S_{1}$ | $S_{3}$ | $S_{5}$ | $S_{7}$ | $S_{9}$
---|---|---|---|---|---
LSTM | $6.23\pm 0.53$ | $9.65\pm 0.57$ | $11.98\pm 0.46$ | $13.35\pm 1.02$ | $12.92\pm 1.42$
Conv-1D | $36.32\pm 0.12$ | $19.11\pm 0.49$ | $27.92\pm 0.41$ | $35.42\pm 0.19$ | $40.83\pm 0.11$
Simple FC | $25.26\pm 0.01$ | $18.18\pm 0.15$ | $35.27\pm 0.07$ | $44.51\pm 0.58$ | $51.79\pm 0.89$

###  9.2 Image-Digit sum

  1. 1.

Deep Sets-$S_{k}$:- $S_{k}$-invariant neural network proposed by Zaheer et
al., (2017). It consists of two networks, $\gamma$, and $\rho$. Each element
in the input is passed through the $\gamma$ network, followed by the sum
operation. The result is then fed to the second network $\rho$. The network
$\gamma$ is a feed-forward network consisting of three dense layers with tanh
activation, and the second network is a dense layer.

  2. 2.

LSTM:- The LSTM network used for comparison in Zaheer et al., (2017). It
consists of two dense layers, an LSTM layer followed by two dense layers. The
activation used is tanh function.

  3. 3.

Proposed method:- An $S_{n}$-invariant network follows a linear layer. The
$S_{n}$-invariant network has the same architecture as Deep Sets (the first
approach) except the input layer.

Table 8: Definitions of the various polynomials used in the main paper.

INVARIANCE | POLYNOMIAL
---|---
$\mathbb{Z}_{2}:\mathbb{Z}_{16}$ | $x_{1}x_{2}^{2}+x_{2}x_{1}^{2}$
$\mathbb{Z}_{4}:\mathbb{Z}_{16}$ | $x_{1}x_{2}^{2}+x_{2}x_{3}^{2}+x_{3}x_{4}^{2}+x_{4}x_{1}^{2}$
$\mathbb{Z}_{5}:\mathbb{Z}_{10}$ | $x_{1}x_{2}^{2}+x_{2}x_{3}^{2}+x_{3}x_{4}^{2}+x_{4}x_{5}^{2}+x_{5}x_{1}^{2}$
$\mathbb{Z}_{8}:\mathbb{Z}_{16}$ | $x_{1}x_{2}^{2}+x_{2}x_{3}^{2}+...+x_{7}x_{8}^{2}+x_{8}x_{1}^{2}$
$\mathbb{Z}_{10}:\mathbb{Z}_{10}$ | $x_{1}x_{2}^{2}+x_{2}x_{3}^{2}+...+x_{9}x_{10}^{2}+x_{10}x_{1}^{2}$
$\mathbb{Z}_{16}:\mathbb{Z}_{16}$ | $x_{1}x_{2}^{2}+x_{2}x_{3}^{2}+...+x_{15}x_{16}^{2}+x_{16}x_{1}^{2}$

###  9.3 Comparison between $S_{k}$-invariant networks with backbone as
$S_{k}^{(0}$ and $S_{n}$

As specified in Section 5.2 of the main paper, any $S_{k}$-invariant network
can be realized through either an $S_{k}^{(0)}$ or an $S_{n}$-invariant
network and a linear layer when $k$ is fixed. In general, we observed that the
$S_{n}$-invariant network as the backbone does better than the $S_{k}^{(0)}$
network. We attribute this to the expressivity power of the linear
transformation (based on its specific structure) when an $S_{n}$ invariant
network is used.

###  9.4 Symmetric Polynomial Regression

  1. 1.

G-invariant:- $\mathbb{Z}_{k}$-invariant network implemented using the design
described in Kicki et al., (2020). As discussed in Kicki et al., (2020), it is
a composition of a $\mathbb{Z}_{k}$-equivariant network and a Sum-Product
Layer. It then uses a Multi-Layer Perceptron to process the
$\mathbb{Z}_{k}$-invariant representation of the input and thus predicts the
polynomial output. The network is thus invariant under the action of the given
permutation subgroup $\mathbb{Z}_{k}$.

  2. 2.

Simple-FC:- This is an abbreviation of a fully-connected neural network
without the Reynolds operator, i.e., group averaging for this baseline
implementation (Derksen and Kemper, (2001)).

  3. 3.

Conv-1D:- This is an abbreviation of the 1D Convolutional neural network
equipped with fully-connected layers.

  4. 4.

Proposed method:- To discover the underlying subgroup, we use a
$\mathbb{Z}_{n}$-invariant neural network with the addition of a linear layer.
The architectural design of the $\mathbb{Z}_{n}$-invariant function is the
same as the $G$-invariant network.

The hyperparameters of the above models are given in Table. (6-9) of Kicki et
al., (2020).

Table 9: MAE $[\times 10^{-2}]$ Polynomial Regression

Method | $\mathbb{Z}_{2}:\mathbb{Z}_{16}$ | $\mathbb{Z}_{8}:\mathbb{Z}_{16}$ | $\mathbb{Z}_{16}:\mathbb{Z}_{16}$
---|---|---|---
$\mathbb{Z}_{k}$-invariant | $1.26\pm 0.25$ | $14.30\pm 1.04$ | $17.16\pm 0.59$
Proposed | $22.27\pm 4.25$ | $39.31\pm 5.12$ | $40.11\pm 4.17$
Conv-1D | $21.67\pm 0.69$ | $50.15\pm 1.03$ | $68.38\pm 3.13$
Simple FC | $21.61\pm 1.54$ | $45.92\pm 2.83$ | $51.64\pm 0.89$

####  9.4.1 Additional results

The test errors for $\mathbb{Z}_{2}:\mathbb{Z}_{16}$,
$\mathbb{Z}_{8}:\mathbb{Z}_{16}$ and $\mathbb{Z}_{16}:\mathbb{Z}_{16}$
invariant functions are provided in Table 9. The details of all the
polynomials used in our work are presented in Table 8.


# On Hallucination and Predictive Uncertainty in
Conditional Language Generation

Yijun Xiao, William Yang Wang
University of California, Santa Barbara
<EMAIL_ADDRESS>

###### Abstract

Despite improvements in performances on different natural language generation
tasks, deep neural models are prone to hallucinating facts that are incorrect
or nonexistent. Different hypotheses are proposed and examined separately for
different tasks, but no systematic explanations are available across these
tasks. In this study, we draw connections between hallucinations and
predictive uncertainty in conditional language generation. We investigate
their relationship in both image captioning and data-to-text generation and
propose a simple extension to beam search to reduce hallucination. Our
analysis shows that higher predictive uncertainty corresponds to a higher
chance of hallucination. Epistemic uncertainty is more indicative of
hallucination than aleatoric or total uncertainties. It helps to achieve
better results of trading performance in standard metric for less
hallucination with the proposed beam search variant.

##  1 Introduction

Modern deep neural network models have brought drastic improvements of
generation quality measured by standard metrics on different natural language
generation (NLG) tasks. However, along with these improvements, researchers
find that neural models are more prone to a phenomenon called hallucination,
where models generate description tokens that are not supported by the source
inputs. This phenomenon seriously damages the applicability of neural language
generation models in practice where information accuracy is vital.

Hallucination has been observed in various conditional NLG tasks such as image
captioning Rohrbach et al. (2018), data-to-text generation Wiseman et al.
(2017); Nie et al. (2019); Parikh et al. (2020), abstractive summarization Cao
et al. (2018); Durmus et al. (2020), and neural machine translation (NMT)
Müller et al. (2019). These studies tackle hallucinations within a specific
task and give possible explanations of why hallucinations occur. For example,
Rohrbach et al. (2018) attributes object hallucination in image captioning to
visual misclassification and over-reliance on language priors; Nie et al.
(2019) believes hallucination in neural surface realization comes from the
misalignment between meaning representations and their corresponding
references in the dataset; Müller et al. (2019) claims that hallucinations in
NMT are mainly due to domain shift.

We believe that there is a common theme across all the hallucination
explanations in conditional NLG tasks: predictive uncertainty. In language
generation, predictive uncertainty quantifies the entropy of the token
probability distributions a model predicts. There are multiple sources of
uncertainty. Two major ones frequently studied are aleatoric and epistemic
uncertainties, where the former comes from the data or measurements, and the
latter is concerned with the model. With recent progress in Bayesian neural
networks (BNNs) Hinton and Van Camp (1993); Neal (1995) and uncertainty
quantification Blundell et al. (2015); Gal and Ghahramani (2016);
Lakshminarayanan et al. (2017), we are able to quantify both parts of
predictive uncertainty in neural NLG.

This study draws connections between hallucination and predictive uncertainty
and empirically investigates their relationship in image captioning and data-
to-text generation tasks. We propose an uncertainty-aware beam search
algorithm to reduce the chance of hallucination by penalizing parts or the
entirety of the predictive uncertainty during model decoding. We find that the
choice of uncertainty matters, and penalizing epistemic uncertainty yields
better results compared to penalizing aleatoric or total uncertainty. Our
contributions are:

  * •

We draw connections between hallucination and predictive uncertainty across
various conditional natural language generation tasks and empirically
investigate their relationship.

  * •

We propose an uncertainty-aware beam search approach for hallucination
reduction to demonstrate that lowering uncertainty can lead to less
hallucination.

  * •

We show that uncertainty decomposition helps to achieve better trade-offs
between hallucination and performance.

##  2 Hallucination and Predictive Uncertainty

###  2.1 Hallucination Probability

In general, hallucination refers to the phenomenon where the model generates
false information not supported by the input. For example, in the context of
image captioning, hallucination can be defined as generating captions that
contain descriptions not present in the given image. Let $(x,y)$ be the pair
of variables at interest where $x$ is some structured data containing facts
and $y$ is a natural language sentence based on the facts. The task is to
learn the conditional distribution of $p(y|x)$ in order to generate sentence
$y$ given any new input $x$. Most neural approaches break the probability into
a sequence of single token predictions:

$\displaystyle
p(y|x)=p(y_{1}|x)\prod_{i=2}^{k}p(y_{i}|x,y_{1},\cdots,y_{i-1})$ (1)

where $\\{y_{1},\cdots,y_{k}\\}$ is the collection of tokens in sentence $y$.
We denote $c_{i}=\\{x,y_{1},\cdots,y_{i-1}\\}$ as the context of the $i$-th
prediction in the following sections for simplicity.

Apparently, hallucination is context-dependent which means we need to look at
a certain context $c_{i}$ and determine whether the next token prediction
$y_{i}$ is hallucinated or not. Let $\mathcal{V}_{h}^{(c_{i})}$ denote the set
of tokens that are considered false information given the current context
$c_{i}$ and $\mathcal{V}$ the whole vocabulary. Consider a random sampling
decoder where a token is generated based on the predicted categorical
distribution. i.e. $\text{Cat}(|\mathcal{V}|,p(y_{i}|c_{i}))$. The probability
of hallucination at the current step is simply:

$\displaystyle
P(y_{i}\in\mathcal{V}_{h}^{(c_{i})})=\sum_{v\in\mathcal{V}_{h}^{(c_{i})}}p(y_{i}=v|c_{i})$
(2)

Practically, it is hard to automatically determine the context-dependent set
$\mathcal{V}_{h}^{(c_{i})}$. Task-specific heuristics are often used to
determine which tokens are hallucinated. In specific restrictive applications,
the context-dependent set can be relaxed to a context-independent one to
reduce the complexity of determining hallucination.

###  2.2 Relationship with Predictive Uncertainty

We use entropy to measure the predictive uncertainty in this work. The total
uncertainty of predicting token $y_{i}$ is:

$\displaystyle H(y_{i}|c_{i})$ $\displaystyle=$
$\displaystyle-\sum_{v\in\mathcal{V}}p(y_{i}=v|c_{i})\log{p(y_{i}=v|c_{i})}$
$\displaystyle=$
$\displaystyle-\sum_{v\in\mathcal{V}\setminus\mathcal{V}_{h}^{(c_{i})}}p(y_{i}=v|c_{i})\log{p(y_{i}=v|c_{i})}$
$\displaystyle-\sum_{v\in\mathcal{V}_{h}^{(c_{i})}}p(y_{i}=v|c_{i})\log{p(y_{i}=v|c_{i})}$
(3)

From Equation 2.2, we can see that there are two sources of uncertainty for
the token predictions: one from the uncertainty of choosing suitable tokens to
describe the input; another from some unsuitable tokens attaining considerable
probability mass either by being confusing in the current context or due to an
insufficiently trained system.

The second source of uncertainty is directly related to hallucination
probability. Although no monotonic relationship can be derived, a near-zero
hallucination probability requires a near-zero value of the second source of
uncertainty. This observation prompts us to investigate the relationship
between hallucination and predictive uncertainty in practice. Intuitively, the
higher the predictive uncertainty is, the more probable some of the
probability mass gets assigned to unsuitable tokens.

(a)

(b)

Figure 1: Examples of predictions with (a) high aleatoric but low epistemic
uncertainty; and (b) high epistemic but low aleatoric uncertainty.

###  2.3 Uncertainty Decomposition

There are often two types of uncertainties frequently mentioned in uncertainty
quantification literature: epistemic and aleatoric uncertainty Der Kiureghian
and Ditlevsen (2009); Kendall and Gal (2017); Depeweg et al. (2018). Epistemic
uncertainty reflects the uncertainty on model weights, and aleatoric
uncertainty concerns inherent uncertainty in the data or measurement. We are
interested in whether the relationship with hallucination is the same for both
types of uncertainties.

Bayesian deep learning approaches Blundell et al. (2015); Gal and Ghahramani
(2016); Lakshminarayanan et al. (2017) are widely studied for uncertainty
quantification with neural networks. Following the notations in Section 2.2,
the predictive distribution of $p(y_{i}|c_{i})$ can be written as:

$\displaystyle p(y_{i}|c_{i})=\int_{w}p(y_{i}|c_{i},w)q(w)dw$ (4)

where $w$ parameterizes the neural network that makes predictions and $q(w)$
denotes the approximate posterior distribution of the weights $w$ given the
training data. Notice that if we fix the weights $w$, $H(y_{i}|c_{i},w)$
represents the entropy that is unrelated to the uncertainty of the model
weights. Therefore the aleatoric part of the predictive uncertainty can be
calculated with $\mathbb{E}_{q(w)}[H(y_{i}|c_{i},w)]$. The epistemic part of
the uncertainty is the difference between the total and the aleatoric
uncertainty as shown below:

$\displaystyle u_{al}(y_{i}|c_{i})$
$\displaystyle=\mathbb{E}_{q(w)}[H(y_{i}|c_{i},w)]$ (5) $\displaystyle
u_{ep}(y_{i}|c_{i})$
$\displaystyle=H(y_{i}|c_{i})-\mathbb{E}_{q(w)}[H(y_{i}|c_{i},w)]$ (6)

In this study, the aleatoric and epistemic parts of predictive uncertainty are
estimated using deep ensembles Lakshminarayanan et al. (2017). More
concretely, denote the model predictions as
$\\{p_{m}(y_{i}|c_{i})\\}_{m=1}^{M}$ and the aggregated prediction as
$p(y_{i}|c_{i})=\frac{1}{M}\sum_{m=1}^{M}p_{m}(y_{i}=v|c_{i})$, aleatoric and
epistemic uncertainties are calculated as:

$\displaystyle u_{al}(y_{i}|c_{i})$
$\displaystyle=\frac{1}{M}\sum_{m=1}^{M}H_{m}(y_{i}|c_{i})$ (7) $\displaystyle
u_{ep}(y_{i}|c_{i})$ $\displaystyle=H(y_{i}|c_{i})-u_{al}(y_{i}|c_{i})$ (8)

where $H_{m}(y_{i}|c_{i})$ and $H(y_{i}|c_{i})$ are the entropy of
$p_{m}(y_{i}|c_{i})$ and $p(y_{i}|c_{i})$ respectively.

Intuitively, in the case of deep ensembles, aleatoric uncertainty measures the
average spread of all model predictions, while epistemic uncertainty measures
the agreement among all model predictions. Examples with three possible tokens
are illustrated in Figure 1.

Model | Action hallucination % at uncertainty level |
---|---|---
$\leq 0.8$ |  $0.8$ \- $1.6$ |  $1.6$ \- $2.4$ |  $2.4$ \- $3.2$ |  $3.2$ \- $4.0$ | $>4.0$
FC | 0.00 | 0.00 | 2.27 | 12.86 | 15.71 | 31.03
Att2In | 0.00 | 0.00 | 3.39 | 6.58 | 12.07 | 22.03
BUTD | 0.00 | 2.94 | 1.92 | 12.77 | 17.24 | 25.53
Transformer | 2.99 | 5.48 | 6.58 | 8.82 | 12.00 | 43.75
Table 1: Action hallucination percentages at different levels of predictive
uncertainty. Action predictions with higher uncertainty are more prone to
hallucination.

##  3 Case Study: Image Captioning

In this section, we analyze image captioning models trained on MSCOCO Chen et
al. (2015) data set.

###  3.1 Hallucination Probability at Different Uncertainty Levels

The first question we want to investigate is whether hallucination
probabilities change at different predictive uncertainty levels. Some
experimental settings are listed below.

#### Model architecture

We consider four different image captioning models: FC model Rennie et al.
(2017) where image features are used to initialize the RNN decoder; Att2In
model from Rennie et al. (2017) applies attention on image features and feeds
it into the decoder LSTM Hochreiter and Schmidhuber (1997) cell gate; BUTD
model from Anderson et al. (2018) uses bottom-up attention which operates at
the level of objects and other salient image regions; Transformer model where
transformers Vaswani et al. (2017) are used in the encoder-decoder structure
for generation. All models are implemented in the open source framework by Luo
et al. (2018)111https://github.com/ruotianluo/self-critical.pytorch.

#### Training

We consider the same data split from Karpathy and Fei-Fei (2015). All models
are trained with batch size 50 for 30 epochs with Adam optimizer Kingma and Ba
(2014). Evaluations are done on the Karpathy test set.

#### Hallucination and uncertainty evaluation

As in Rohrbach et al. (2018), synonyms for all possible MSCOCO objects are
used to determine whether an object generated by the captioning model is
hallucinated. Hallucination probabilities are calculated by binning all object
token prediction entropy and counting the percentage of hallucinated objects
in each bin.

Figure 2: Object hallucination chance at different predictive uncertainty
levels. Higher predictive uncertainty corresponds to a higher level of
hallucination percentage across all models.

###  3.2 Results and Discussions

Figure 2 shows the object hallucination percentages at different predictive
uncertainty levels. At higher uncertainty levels, the generated objects are
more likely to be hallucinated. The results are consistent across four
different models. The transformer model seems to have a higher hallucination
chance at high uncertainty levels than the other three models. However, this
does not indicate Transformer models hallucinate more. In fact, the
transformer model has an overall lowest hallucination percentage among all
four models.

#### Beyond object hallucination

Aside from object hallucination, we also analyze verbs generated by the models
to see whether a similar relationship holds for other types of token
generations. The same models and training procedures are adopted. We extract
all present continuous tense verbs from the generated captions using spaCy
part-of-speech tagger222https://spacy.io and manually label whether they are
suitable to describe the corresponding images. There are approximately 3500
generated captions containing verbs, and 400 are annotated for each model. We
refer to unsuitable verbs generated in the captions as action hallucinations.

Action predictions are binned according to their uncertainty values, and the
results are shown in Table 1. We can observe that action tokens with higher
predictive uncertainty are also more likely to be hallucinated. Noticeably,
the transformer model also has a higher action hallucination rate at high
uncertainty levels.

(a) a red and black motorcycle (0.58) parked in a parking lot

(b) a motorcycle (4.80) is parked on a dock with a bird perched on top of it

(c) a bride and groom cutting their wedding cake (0.09)

(d) a woman holding a cup and a cake (5.29)

(e) a man standing on a tennis court holding (0.81) a racquet

(f) a young man is holding (4.76) a skateboard in his hand

(g) a group of children sitting at a table eating (1.00) pizza

(h) a man is eating (4.01) a hot dog at a restaurant

Figure 3: Examples of token predictions generated with the BUTD model with
high and low uncertainty values for objects (top) and actions (bottom).
Numbers in italic are predictive uncertainty values for the token predictions
preceding them. The examples are cherry-picked.

#### Examples of predictions with high and low uncertainty

Figure 3 shows some example images and their captions generated from a BUTD
model on the test set. The token predictions of interests and the
corresponding uncertainty values are highlighted in bold and italic,
respectively. We observe that highly uncertain predictions often correspond to
unusual textures, features resembling the predicted tokens, or blurred images.
For example, Figure 3(b) shows a motorcycle covered in vines; Figure 3(d)
shows candles in the background which resemble cakes; Figure 3(f) is blurred.

Model | Correlation coefficient
---|---
epistemic | aleatoric
FC | 0.313 | 0.299
BUTD | 0.334 | 0.228
Att2In | 0.360 | 0.268
Transformer | 0.269 | 0.131
Table 2: Pearson correlation coefficients between hallucination and
epistemic/aleatoric uncertainty in image captioning task. Epistemic
uncertainty is more indicative of hallucination across four models.

#### Epistemic and aleatoric uncertainties

As we could decompose the total uncertainty into two parts, we are interested
in which part is more indicative of hallucination. Table 2 shows the Pearson
correlation coefficients between hallucination (binary) and
epistemic/aleatoric uncertainty for all four models. We can see that both
parts of uncertainty are weakly correlated with hallucination, while epistemic
uncertainty is more indicative of hallucination across all four models
compared to aleatoric uncertainty.

##  4 Case Study: Data-to-text Generation

Data-to-text generation Kukich (1983); McKeown (1992) is a task to generate
textual content conditioned on input content in the form of structured data
such as tables. Neural models are prone to hallucination in data-to-text
generation tasks compared to traditional template-based systems, and methods
are proposed to improve faithfulness Wiseman et al. (2017); Nie et al. (2019);
Tian et al. (2019). In this section, we discuss the relationship between
predictive uncertainty and hallucination in data-to-text generation with ToTTo
dataset Parikh et al. (2020).

###  4.1 Generation Quality and Average Uncertainty

We conduct token-level analysis in Section 3. Now we take a different route
and analyze sentence-level quality with different average predictive
uncertainty values. Experiment settings are described below.

Unc. Level | Avg Unc. | BLEU | Fluency (%) | Faithfulness (%) | Less/Neutral/More Coverage w.r.t. Ref
---|---|---|---|---|---
High | 1.83 - 3.74 | 10.2 | 46.0 | 41.3 | 79.4 / 15.9 / 04.7
Medium | 0.83 - 0.89 | 31.5 | 87.3 | 78.9 | 35.2 / 47.9 / 16.9
Low | 0.04 - 0.27 | 72.8 | 100.0 | 99.0 | 22.2 / 70.1 / 07.7
Table 3: Evaluation results for candidates with high, medium, and low average
predictive uncertainty values for ToTTo validation set. Unc. denotes
uncertainty. Higher uncertainty candidates have lower quality and higher
chance of being hallucinated/unfaithful w.r.t. the input tables.

#### Dataset

ToTTo dataset consists of tables from English Wikipedia articles with their
corresponding metadata, such as page title and section title. Candidate
description texts are modified by annotators to pair with each table. Relevant
table cells supporting the description texts are highlighted by the annotators
as well. There are 120,761 table-text pairs in training, 7,700 in validation,
and 7,700 in test. We use the baseline standard linearization approach to
represent the highlighted portions of the tables along with their
corresponding metadata (referred to as subtable with metadata in Parikh et al.
(2020)).

#### Model architecture and training

We use a standard sequence-to-sequence model with attention Bahdanau et al.
(2015); Luo et al. (2018) for analysis. LSTM with 512 hidden size is used for
both the encoder and the decoder. Adam optimizer with learning rate 1e-3 is
used for the optimization. The model is trained with cross-entropy loss for 20
epochs. The checkpoint with the best validation loss is chosen for the
evaluation. The implementation is done using fairseq Ott et al.
(2019)333https://github.com/pytorch/fairseq.

#### Evaluation

We evaluate the average predictive uncertainty for all generated sentences in
the validation set and select the top, bottom, and middle 5% for comparison.
BLEU score Papineni et al. (2002) is used as an automatic metric to evaluate
the similarity to the references; further manual annotations are done to
evaluate the fluency, faithfulness (precision), and coverage with respect to
reference (recall) of the generated sentences. Particularly, faithfulness
reflects how likely the generated sentences hallucinate facts that are not
supported by the tables. More details of the human evaluation metrics are
described in Parikh et al. (2020). The goal is to measure how different the
generation qualities are for candidates with varying average predictive
uncertainties.

###  4.2 Results and Discussions

Table 3 summarizes the evaluation results for candidates with varying
uncertainty values. It is obvious that candidates with higher average
predictive uncertainty values are less fluent and more likely to contain
hallucinations. Another interesting observation from Table 3 is that the
generated sentences with medium average uncertainty are more likely (16.9%) to
cover more table facts than the references compared to the ones with high
(4.7%) and low (7.7%) average uncertainty. One possible explanation is that
some table facts that are not always included in the references, when
generated, have higher predictive uncertainty values than the facts that are
almost always included in the references. Therefore, generated sentences with
low uncertainty tend to include less but more confident facts considered by
the model.

##  5 Reducing Hallucination

###  5.1 Uncertainty-Aware Beam Search

Because of the positive correlation between hallucination probability and
predictive uncertainty, it is straightforward to incorporate uncertainty into
the caption generation process to reduce hallucination. Beam search is the
most used approximate decoding method in language generation. It keeps track
of the top-$B$ scored candidates at each generation step and considers all
single token extensions of the current candidates.

More formally, denote the set of $B$ candidates in the beam at time step $t-1$
as $\mathcal{Y}_{t-1}=\\{\mathbf{y}^{(b)}_{t-1}\\}_{b=1}^{B}$. All possible
single token extensions of the candidates in $\mathcal{Y}_{t-1}$ form a set
$\mathcal{C}_{t}=\\{\mathbf{y}\mid\mathbf{y}_{t-1}\in\mathcal{Y}_{t-1}\land
y_{t}\in\mathcal{V}\\}$. Beam at step $t$ is then formed as:

$\displaystyle\mathcal{Y}_{t}=$
$\displaystyle\operatorname*{arg\,max}_{\mathbf{y}_{1}\cdots\mathbf{y}_{B}\in\mathcal{C}_{t}}\sum_{b=1}^{B}\log
p(\mathbf{y}_{b}|\mathbf{x})$ $\displaystyle
s.t.\quad\mathbf{y}_{i}\neq\mathbf{y}_{j}\quad\forall i\neq j$ (9)

Uncertainty-aware beam search (UABS) adds a weighted penalty term in the beam
search objective to balance between log probability and predictive uncertainty
of the selected candidates. Let $u(\mathbf{y}|\mathbf{x})$ be the function to
measure the aggregated predictive uncertainty of candidate $\mathbf{y}$ given
input $\mathbf{x}$, uncertainty-aware beam search updates the beam at step $t$
according to the following equation:

$\displaystyle\mathcal{Y}_{t}=$
$\displaystyle\operatorname*{arg\,max}_{\mathbf{y}_{1}\cdots\mathbf{y}_{B}\in\mathcal{C}_{t}}\sum_{b=1}^{B}\log
p(\mathbf{y}_{b}|\mathbf{x})-\lambda u(\mathbf{y}_{b}|\mathbf{x})$
$\displaystyle s.t.\quad\mathbf{y}_{i}\neq\mathbf{y}_{j}\quad\forall i\neq j$
(10)

where $\lambda\geq 0$ is the weight controlling the degree to which we want to
penalize decoding uncertainty. Larger $\lambda$ leads to candidates with
smaller predictive uncertainty. In practice, this can be done by subtracting
the weighted uncertainty term from the aggregated log probability scores at
each decoding step before choosing top-$B$ candidates.

An important decision in using uncertainty-aware beam search is the choice of
uncertainty term $u(\mathbf{y}|\mathbf{x})$. We could use either the aleatoric
or epistemic part of the predictive uncertainty or both. We compare these
choices and discuss the results in the next section.

(a) FC

(b) Att2In

(c) BUTD

(d) Transformer

Figure 4: CIDEr plotted against CHAIRi scores of captions generated with UABS with different uncertainty penalty weights. Lower CHAIRi score indicates less hallucination. Upper-left is better. Penalizing epistemic uncertainty in UABS achieves the best results. Image | UABS results with weight $\lambda$
---|---
0 | 20 | 80
|  a vase filled with flowers sitting on top of a table |  a vase filled with lots of white flowers |  there is a vase that has flowers in it
|  a wooden cutting board topped with lots of food |  a wooden cutting board topped with lots of food |  a cutting board that has a bunch on it
Table 4: Two examples of epistemic UABS results with varying penalty weights
on the image captioning data set. In the first example the model successfully
avoids hallucination of a table with $\lambda=20$ while in the second example
it is unable to change the generated caption until larger penalty weight is
set.

###  5.2 Image Captioning Results

With larger weights on the uncertainty penalty term, log probabilities of the
decoded sentences drop. Therefore, we expect to see a trade-off between the
quality of generated captions and the chance of hallucination.

We empirically examine the trade-offs on the image captioning models with
different uncertainty choices for the penalty term. We use a five-model
ensemble for each of the four model architectures to estimate aleatoric and
epistemic uncertainties. Due to the different magnitudes of aleatoric and
epistemic uncertainties, we choose penalty weight $\lambda$ from
$[0.1,0.2,0.4,0.8,1.0,2.0,4.0]$ for aleatoric and total uncertainty and
$[10,20,40,80]$ for epistemic uncertainty.

| $\lambda$ | avg. len. | # obj. | hal. % | gen. %
---|---|---|---|---|---
ref. |  | 10.44 | 6114 | 0 | -
base | 0 | 9.31 | 7328 | 5.5 | 0
epist. | 10 | 9.21 | 7195 | 5.2 | 0
20 | 9.16 | 7078 | 4.9 | 0.2
40 | 9.15 | 6912 | 4.2 | 1.5
80 | 9.12 | 6493 | 3.6 | 4.6
aleat. | 0.1 | 9.32 | 7250 | 5.4 | 0
0.4 | 9.32 | 7051 | 5.1 | 0
1.0 | 9.33 | 6800 | 4.7 | 1.0
4.0 | 9.43 | 4349 | 4.1 | 28.4
Table 5: Average sentence length and total number of objects detected in the captions generated by BUTD model with varying uncertainty penalty weight $\lambda$. Penalizing epistemic uncertainty leads to slightly shorter lengths. Number of objects mentioned by the captions decreases with increasing $\lambda$. gen. % denotes percentage of generic responses. It is moderate with epistemic penalized results but can be very high if aleatoric uncertainty is heavily penalized. $\lambda$ | BLEU | Fluency (%) | Faithfulness (%) | Less/Neutral/More Coverage w.r.t. Ref
---|---|---|---|---
0 | 40.1 | 92 | 79 | 34 / 60 / 6
10 | 33.6 | 83 | 84 | 41 / 51 / 8
20 | 27.4 | 73 | 80 | 52 / 42 / 6
Table 6: Evaluation results for candidates decoded with different penalty
weights for UABS on ToTTo validation set. Epistemic uncertainty is used for
uncertainty penalization. Faithfulness first increases, then decreases to the
same level as regular beam search results as we increase the penalty weight
$\lambda$.

Figure 4 shows the trade-offs between CIDEr Vedantam et al. (2015) and CHAIRi
Rohrbach et al. (2018) scores of captions generated with uncertainty-aware
beam search with different uncertainty choices and penalty weights. A smaller
value of CHAIRi indicates the model is less likely to generate hallucinated
objects, and a higher CIDEr indicates better caption quality. Therefore an
approach that is to the upper left of another is better. As the penalty weight
increases, we observe a decrease in both the CHAIRi and the CIDEr scores
across all models.

Table 4 shows two examples of different generated captions using epistemic
UABS with varying penalty weights. In the first example, we can see that a
medium penalty weight of 20 not only helps avoid the hallucination of a table
but also adds correct information about the color of the flowers. In the
second example, a medium penalty weight is unable to change the generated
caption.

Reference | UABS results with weight $\lambda$
---|---
0 | 10 | 20
barrows scored 164 net points in virgin islands at the 2008 summer olympics. |  in virgin islands at the 2008 summer olympics, barrows iii received 164 points. |  in virgin islands at the 2008 summer olympics, barrows received 164 points. |  thomas barrows received a total score of 164.
janet gaynor won the first academy award for best actress for her performance in the 7th heaven (1927 film). |  janet gaynor won the academy award for best actress for his performance in janet gaynor. |  janet gaynor won the academy award for best actress. |  janet gaynor won an academy award for best actress.
Table 7: Two examples of UABS results with varying penalty weights on the
ToTTo validation set. Blue tokens are correct table facts that are dropped by
candidates generated with larger penalty weights; red tokens are
incorrect/hallucinated facts that are dropped with larger penalty weights. In
general, UABS with larger weights tend to produce sentences with less
information that the model is more confident with.

Regarding the choice of uncertainty, it is notable that when penalizing
epistemic uncertainty, the generated captions achieve higher CIDEr scores than
penalizing aleatoric or total uncertainty. We hypothesize that epistemic
uncertainty indicates the uncertainty of model weights. By penalizing
epistemic uncertainty, we encourage the model to take the prediction path
where it is well-calibrated. On the other hand, penalizing aleatoric
uncertainty encourages the model to make low entropy predictions in all
contexts regardless of the actual data distributions.

Table 5 shows the average sentence length, the number of objects, the
percentage of hallucinations, and the percentage of generic responses in the
captions generated by the BUTD model with different uncertainty choices and
penalty weights on the test set. We can see that when penalizing epistemic
uncertainty, UABS results in slightly shorter caption candidates. Both the
number of objects and hallucination percentage decrease as we increase the
weight $\lambda$. Interestingly, when penalizing aleatoric uncertainty,
sentence length stays approximately the same despite lower CIDEr scores, as
shown in Figure 4. Further investigation shows that this is partly due to an
increasing number of generic captions such as “there is no image here to
provide a caption for”. Penalizing epistemic uncertainty is much less likely
to result in such generic captions. We can see that when increasing $\lambda$
from $1.0$ to $4.0$ with aleatoric UABS, the percentage of generic responses
jumps drastically from $1.0\%$ to $28.4\%$. In comparison, epistemic UABS
keeps the generic response rates low while achieving lower hallucination
rates.

###  5.3 Data-to-text Results

We also evaluate the effect of UABS on the ToTTo dataset. We choose to
penalize epistemic uncertainty due to its better performances than aleatoric
uncertainty, as shown in the previous section. A five-model deep ensemble is
used to quantify the epistemic uncertainty and generate results with UABS. We
compare the BLEU score and three human evaluation metrics among results
generated with different uncertainty penalty weights. 100 generation results
are randomly selected and evaluated for each penalty weight choice. The
results are shown in Table 6. We can see that a relatively small penalty
weight leads to a reduced hallucination chance (hence more faithful) with a
cost on the BLEU score and fluency.

To qualitatively examine the sentences generated with different $\lambda$
values, we show example results on the ToTTo validation set in Table 7. We can
see that with larger penalty weights, the UABS results drop certain statements
that the model deems less confident regardless of the correctness. This
results in shorter but more confident predictions for UABS results with a
larger uncertainty penalty.

##  6 Related Work

#### Hallucination

There are many pieces of anecdotal evidence of hallucination presented in
various NLG tasks. Most recently, researchers started investigating the
phenomenon systematically. Rohrbach et al. (2018) analyzes object
hallucination focusing on the objects that appeared in the MSCOCO segmentation
challenge. They propose the CHAIR metric to quantify the severity of object
hallucination. They find that the models tend to make predictions consistent
with a language model trained on the captions instead of a model trained to
predict objects in an image. Therefore hallucination is caused by an over-
reliance on the language priors. Nie et al. (2019) believes that the origin of
the hallucination problem in neural surface realization comes from the data
side. More specifically, datasets used for NLG systems often include instances
with information misalignment between the input structure and the output text.
They propose integrating a language understanding module for iterative data
refinement to better align meaning representations and output text. Müller et
al. (2019) examines hallucination in neural machine translation and observes
that the phenomenon is most common in out-of-domain settings. They empirically
compare several strategies to improve domain robustness in NMT and find that a
combination of reconstruction and a noisy channel model for reranking is most
effective.

These observations are consistent with our findings. For example, domain shift
and data misalignment are known to lead to a higher level of epistemic
uncertainty Kendall and Gal (2017) which makes hallucination a more severe
problem.

#### Uncertainty quantification

Uncertainty quantification has attracted more attention recently due to the
progress in Bayesian deep learning. Bayes by backprop Blundell et al. (2015),
Monte Carlo dropout Gal and Ghahramani (2016), and deep ensembles
Lakshminarayanan et al. (2017) are examples of popular Bayesian approaches to
evaluate uncertainty with deep neural models. Kendall and Gal (2017)
investigates the benefits of modeling epistemic and aleatoric uncertainty in
vision tasks such as semantic segmentation and depth regression. They show
that it is important to model aleatoric uncertainty with large datasets and
real-time applications and epistemic uncertainty with small datasets and
safety-critical applications. Other applications of uncertainty quantification
have been explored in the context of time series predictions Zhu and Laptev
(2017), natural language processing tasks Xiao and Wang (2019), etc. More
broadly, prediction entropy has been analyzed in different neural language
generation tasks Ott et al. (2018); Xu et al. (2020). Depeweg et al. (2018)
shows how to extract and decompose uncertainty in Bayesian neural networks
with latent variables for decision-making purposes. They show that active
learning and risk-sensitive reinforcement learning both benefit from
uncertainty decomposition.

##  7 Discussion and Conclusions

We investigate the relationship between hallucination and predictive
uncertainty in image captioning and data-to-text generation tasks and show
that predictions with higher uncertainty are more prone to hallucination. In
particular, epistemic uncertainty is more indicative of hallucination than
aleatoric uncertainty. We propose uncertainty-aware beam search to incorporate
uncertainty into the decoding process to reduce hallucination. We show that
uncertainty decomposition helps the proposed beam search variant to achieve a
better performance-hallucination trade-off. Specifically, penalizing epistemic
uncertainty yields better results compared to penalizing aleatoric or total
uncertainty.

In this work, we analyze uncertainty from the token level. This might be
restrictive because uncertainty corresponds to the current prediction context
instead of the predicted token. The relationship between hallucination and
uncertainty, therefore, can be much more complicated than a linear one. It is
still possible to produce hallucinated information with a very confident
model. The proposed UABS reduces hallucination by limiting the total
uncertainty of the generated text. As a result, it might lead to shorter
generations and lower generation quality. Devising more sophisticated
uncertainty-aware training and decoding methods with less adverse effects on
the generation quality is a future direction to explore.

## Acknowledgement

This work was supported by the National Science Foundation award #2048122. The
views expressed are those of the author and do not reflect the official policy
or position of the US government.

## References

  * Anderson et al. (2018) Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. 2018.  Bottom-up and top-down attention for image captioning and visual question answering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 6077–6086.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015.  Neural machine translation by jointly learning to align and translate.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Blundell et al. (2015) Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. 2015.  Weight uncertainty in neural networks.  _arXiv preprint arXiv:1505.05424_.
  * Cao et al. (2018) Ziqiang Cao, Furu Wei, Wenjie Li, and Sujian Li. 2018.  Faithful to the original: Fact aware neural abstractive summarization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Chen et al. (2015) Xinlei Chen, Hao Fang, Tsung-Yi Lin, Ramakrishna Vedantam, Saurabh Gupta, Piotr Dollár, and C Lawrence Zitnick. 2015.  Microsoft coco captions: Data collection and evaluation server.  _arXiv preprint arXiv:1504.00325_.
  * Depeweg et al. (2018) Stefan Depeweg, Jose-Miguel Hernandez-Lobato, Finale Doshi-Velez, and Steffen Udluft. 2018.  Decomposition of uncertainty in bayesian deep learning for efficient and risk-sensitive learning.  In _International Conference on Machine Learning_ , pages 1184–1193. PMLR.
  * Der Kiureghian and Ditlevsen (2009) Armen Der Kiureghian and Ove Ditlevsen. 2009.  Aleatory or epistemic? does it matter?  _Structural safety_ , 31(2):105–112.
  * Durmus et al. (2020) Esin Durmus, He He, and Mona Diab. 2020.  FEQA: A question answering evaluation framework for faithfulness assessment in abstractive summarization.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5055–5070, Online. Association for Computational Linguistics.
  * Gal and Ghahramani (2016) Yarin Gal and Zoubin Ghahramani. 2016.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In _international conference on machine learning_ , pages 1050–1059.
  * Hinton and Van Camp (1993) Geoffrey E Hinton and Drew Van Camp. 1993.  Keeping the neural networks simple by minimizing the description length of the weights.  In _Proceedings of the sixth annual conference on Computational learning theory_ , pages 5–13.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780.
  * Karpathy and Fei-Fei (2015) Andrej Karpathy and Li Fei-Fei. 2015.  Deep visual-semantic alignments for generating image descriptions.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3128–3137.
  * Kendall and Gal (2017) Alex Kendall and Yarin Gal. 2017.  What uncertainties do we need in bayesian deep learning for computer vision?  In _Advances in neural information processing systems_ , pages 5574–5584.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Kukich (1983) Karen Kukich. 1983.  Design of a knowledge-based report generator.  In _Proceedings of the 21st annual meeting on Association for Computational Linguistics_ , pages 145–150. Association for Computational Linguistics.
  * Lakshminarayanan et al. (2017) Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. 2017.  Simple and scalable predictive uncertainty estimation using deep ensembles.  In _Advances in neural information processing systems_ , pages 6402–6413.
  * Luo et al. (2018) Ruotian Luo, Brian Price, Scott Cohen, and Gregory Shakhnarovich. 2018.  Discriminability objective for training descriptive captions.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 6964–6974.
  * McKeown (1992) Kathleen McKeown. 1992.  _Text generation_.  Cambridge University Press.
  * Müller et al. (2019) Mathias Müller, Annette Rios, and Rico Sennrich. 2019.  Domain robustness in neural machine translation.  _arXiv preprint arXiv:1911.03109_.
  * Neal (1995) Radford M Neal. 1995.  _BAYESIAN LEARNING FOR NEURAL NETWORKS_.  Ph.D. thesis, University of Toronto.
  * Nie et al. (2019) Feng Nie, Jin-Ge Yao, Jinpeng Wang, Rong Pan, and Chin-Yew Lin. 2019.  A simple recipe towards reducing hallucination in neural surface realisation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 2673–2679.
  * Ott et al. (2018) Myle Ott, Michael Auli, David Grangier, and Marc’Aurelio Ranzato. 2018.  Analyzing uncertainty in neural machine translation.  In _International Conference on Machine Learning_ , pages 3956–3965.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of NAACL-HLT 2019: Demonstrations_.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting on association for computational linguistics_ , pages 311–318. Association for Computational Linguistics.
  * Parikh et al. (2020) Ankur P Parikh, Xuezhi Wang, Sebastian Gehrmann, Manaal Faruqui, Bhuwan Dhingra, Diyi Yang, and Dipanjan Das. 2020.  Totto: A controlled table-to-text generation dataset.  _arXiv preprint arXiv:2004.14373_.
  * Rennie et al. (2017) Steven J Rennie, Etienne Marcheret, Youssef Mroueh, Jerret Ross, and Vaibhava Goel. 2017.  Self-critical sequence training for image captioning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 7008–7024.
  * Rohrbach et al. (2018) Anna Rohrbach, Lisa Anne Hendricks, Kaylee Burns, Trevor Darrell, and Kate Saenko. 2018.  Object hallucination in image captioning.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 4035–4045.
  * Tian et al. (2019) Ran Tian, Shashi Narayan, Thibault Sellam, and Ankur P Parikh. 2019.  Sticking to the facts: Confident decoding for faithful data-to-text generation.  _arXiv preprint arXiv:1910.08684_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Vedantam et al. (2015) Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh. 2015.  Cider: Consensus-based image description evaluation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4566–4575.
  * Wiseman et al. (2017) Sam Wiseman, Stuart M Shieber, and Alexander M Rush. 2017.  Challenges in data-to-document generation.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2253–2263.
  * Xiao and Wang (2019) Yijun Xiao and William Yang Wang. 2019.  Quantifying uncertainties in natural language processing tasks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 7322–7329.
  * Xu et al. (2020) Jiacheng Xu, Shrey Desai, and Greg Durrett. 2020.  Understanding neural abstractive summarization models via uncertainty.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6275–6281.
  * Zhu and Laptev (2017) Lingxue Zhu and Nikolay Laptev. 2017.  Deep and confident prediction for time series at uber.  In _2017 IEEE International Conference on Data Mining Workshops (ICDMW)_ , pages 103–110. IEEE.