# A Topological Proof of the Gibbard-Satterthwaite Theorem

Yuliy Baryshnikov  Joseph Root

###### Abstract

We give a new proof of the Gibbard-Satterthwaite Theorem. We construct two
topological spaces: one for the space of preference profiles and another for
the space of outcomes. We show that social choice functions induce continuous
mappings between the two spaces. By studying the properties of this mapping,
we prove the theorem.

##  1 Introduction

The Gibbard-Satterthwaite theorem is a landmark result in social choice theory
and mechanism design. It delivers a striking message: the only voting rules
which are not vulnerable to strategic manipulation are dictatorships. This
fact not only has important implications for economics and political science,
it has served as the starting point for the theory of mechanism design. The
various branches of mechanism design correspond to the different ways to avoid
the impossibilities implied by the Gibbard-Satterthwaite theorem. Proofs of
the Gibbard-Satterthwaite theorem have primarily been combinatorial.111See for
instance gibbard1973manipulation, satterthwaite1975strategy,
barbera1983strategy, reny2001arrow, and sen2001another. An exception comes
from mossel2012quantitative who recently gave a “quantitative” proof using
analytic techniques.

In this paper, we provide a new proof of the Gibbard-Satterthwaite theorem
using tools from algebraic topology. The key idea is to view the set of
preference profiles and the set of outcomes as topological spaces. The social
choice function then induces a continuous map between these spaces which can
be analyzed using topological techniques. By viewing the problem from this
lens, we provide a richer geometric view of the impossibility result of
Gibbard and Satterthwaite.

This note contributes to the literature on topological social choice theory.
This area of research began with the publication of chichilnisky1980social
which used topological techniques to establish an impossibility result for the
aggregation of cardinal preferences. baryshnikov1993unifying gave a unified
proof of both Arrow’s impossibility theorem and the impossibility of
Chichilnisky. While a large literature has since developed studying
“topological social choice,” to our knowledge, no proof of the Gibbard-
Satterthwaite theorem has yet appeared.

We start by proving the Muller-Satterthwaite theorem [muller1977equivalence]
which states that the only monotonic and unanimous social choice functions are
dictatorships. We construct two topological spaces $N_{\mathscr{P}}$ and
$N_{A}$, for the set of preference profiles and the set of outcomes
respectively. A monotonic and unanimous social choice function $f$ induces a
continuous map between $N_{\mathscr{P}}$ and $N_{A}$. $N_{A}$ is easily seen
to be homotopy equivalent to a $(n-2)$-sphere. baryshnikov1993unifying showed
that, in dimension $n-2$, the space $N_{\mathscr{P}}$ has the same homology
groups as the Cartesian product of $N$ spheres. We show that the homomorphism
between the homologies of $N_{\mathscr{P}}$ and $N_{A}$ induced by $f$ must be
a projection onto one of the coordinates, proving the theorem.

##  2 Preliminaries

Let $A=\\{a_{1},\dots,a_{n}\\}$ be a finite set of alternatives. Let $P$
denote the set of linear orders on $A$. The symbol $\succ$ will be used to
denote a generic element of $P$. For a given $\succ$, let $\text{top}(\succ)$
be the $a\in A$ such that $a\succ b$ for all $b\neq a$. Let $N\geq 1$, denote
the number of agents. Elements of $P^{N}$ are called preference profiles. The
set of preference profiles will be denoted $\mathscr{P}$. A function
$f:\mathscr{P}\rightarrow A$ is called a social choice function. $f$ is said
to be monotonic if $f(\succ_{1},\dots,\succ_{N})=a$ and for each $i$,
$\succ_{i}^{\prime}$ is a linear order such that $a\succ_{i}b$ implies that
$a\succ^{\prime}_{i}b$ for all $b$ then
$f(\succ_{1}^{\prime},\dots,\succ_{N}^{\prime})=a$. $f$ is said to be
unanimous if whenever all agents top-rank some alternative $a$,
$f(\succ_{1},\dots,\succ_{N})=a$. $f$ is said to be dictatorial if there is an
agent $i$ such that $f(\succ_{1},\dots,\succ_{N})=\text{top}(\succ_{i})$ for
any $(\succ_{1},\dots,\succ_{N})$. Finally, $f$ is said to be strategy-proof
if for every agent $i$, either
$f(\succ_{1},\dots,\succ_{i},\dots,\succ_{N})\succ_{i}f(\succ_{1},\dots,\succ_{i}^{\prime},\dots,\succ_{N})$
or
$f(\succ_{1},\dots,\succ_{i},\dots,\succ_{N})=f(\succ_{1},\dots,\succ_{i}^{\prime},\dots,\succ_{N})$
for every profile $(\succ_{1},\dots,\succ_{i},\dots,\succ_{N})$ and every
$\succ_{i}^{\prime}$.

The aim is to prove the following theorem:

######  Theorem 1 (Gibbard-Satterthwaite).

If $n\geq 3$, a social choice function $f$ is surjective and strategy-proof if
and only if it is dictatorial.

##  3 Topological Background

We assume familiarity with basic notions from algebraic topology.222See
hatcher2002algebraic for a good introduction. For the reader’s convenience, we
briefly review a few concepts that will be central to our proof.

An abstract simplicial complex is a set $V$ together with a collection of
subsets $\Delta$ of $V$ such that if $\sigma\in\Delta$ and
$\sigma^{\prime}\subset\sigma$ then $\sigma^{\prime}\in\Delta$. Any $v\in V$
such that $\\{v\\}\in\Delta$ is called a vertex of $\Delta$. We write
$V(\Delta)$ for the set of vertices of $\Delta$. If $\sigma\in\Delta$ contains
$m+1$ elements, it is referred to as a m simplex of $\Delta$.

We will restrict attention to finite complexes where $V$ is a finite set.

The topology of abstract simplicial complexes is derived from their so-called
geometric realizations. Given a finite abstract simplicial complex $S$,
consider $\mathbb{R}^{V(S)}$, the vector space whose coordinates are indexed
by the vertices of $S$. For any $\sigma\in S$, we can define the standard
$\sigma$-simplex in $\mathbb{R}^{V(S)}$ as the convex hull of the unit vectors
indexed by an element from $\sigma$. The standard geometric realization $|S|$
of the abstract simplicial complex $S$ is the union of the standard
$\sigma$-simplices in $\mathbb{R}^{V(S)}$ for all $\sigma\in S$. When we refer
to the topology of a simplicial complex, we mean the topology of its standard
geometric realization.

Given two simplicial complexes $S$ and $T$. A function $f:V(S)\rightarrow
V(T)$ is called a simplicial map if for any $\sigma\in S$ we have
$f(\sigma)\subset T$. A simplicial map $f:V(S)\rightarrow V(T)$ induces a
continuous map between the geometric realizations of $S$ and $T$ as follows.
Any $s\in|S|$ can be written as a convex combination of the vertices of $S$,
i.e. $\sum_{v\in V(S)}\beta_{v}v$. By sending $s=\sum_{v\in V(S)}\beta_{v}v$
to $\sum_{v\in V(S)}\beta_{v}f(v)$, we get a continuous map
$f:|S|\rightarrow|T|$.

Given a set $X$ and an indexed collection of its subsets
$\\{U_{\alpha}\\}_{\alpha\in A}$ the nerve of $\\{U_{\alpha}\\}_{\alpha\in A}$
is the abstract simplicial complex $N$ where $\sigma\subset A$ is in $N$ if
and only if $\bigcap_{\alpha\in\sigma}U_{\alpha}$ is nonempty.

Nerves are commonly associated with covers of a topological space. A
collection of open sets $U$ in a topological space $X$ is called a good
covering if the union of the sets in $U$ is all of $X$ and if every
intersection of open sets in $U$ is either contractible (i.e., is homotopy
equivalent to a point) or empty.

######  Lemma 1 (Nerve lemma).

Given a topological space $X$ and a good covering $U$, let $N_{U}$ be the
nerve associated to this covering. Then $N_{U}$ and $X$ are homotopy
equivalent.

##  4 Results

###  4.1 The setup

We first prove the Muller-Satterthwaite Theorem [muller1977equivalence]. As is
well-known, the Gibbard-Satterthwaite Theorem
[gibbard1973manipulation][satterthwaite1975strategy] can easily be deduced as
a corollary.

######  Theorem 2 (Muller-Satterthwaite).

Suppose $n\geq 3$. A social choice function is monotonic and unanimous if and
only if it is dictatorial.

Our approach will be to construct covers of both $\mathscr{P}$ and $A$ such
that a monotonic and unanimous social choice function will result in a
simplicial map between the nerve of the cover of $\mathscr{P}$ and the nerve
of the cover of $A$.

Let $1\leq i<j\leq n$. Define

$U_{ij}^{+}=\\{\succ\in P:a_{i}\succ a_{j}\\}\hskip
56.9055ptU_{ij}^{-}=\\{\succ\in P:a_{i}\prec a_{j}\\}$

The sets $U_{ij}^{+}$ and $U_{ij}^{-}$ cover $P$. Denote by
$I_{P}=\\{(i,j,x):1\leq i<j\leq n,x\in\\{+,-\\}\\}$ the index set. Let $N_{P}$
be the nerve of this covering, so that $J\subset I_{P}$ is in $N_{P}$ if and
only if $\bigcap_{(i,j,x)\in J}U_{ij}^{x}$ is nonempty.

Let $\sigma=(\sigma_{1},\dots,\sigma_{N})\in\\{-,+\\}^{N}$. Define

$U_{ij}^{\sigma}=\\{(\succ_{1},\dots,\succ_{N}):\hskip 2.84544pt\succ_{l}\in
U_{ij}^{\sigma_{l}}\text{ for all }l\\}$

The sets $U_{ij}^{\sigma}$ cover $\mathscr{P}$. Again, denote by
$I_{\mathscr{P}}=\\{(i,j,\sigma):1\leq i<j\leq n,\sigma\in\\{+,-\\}^{N}\\}$
the index set of this covering. Let $N_{\mathscr{P}}$ be its nerve so that
$J\subset I_{\mathscr{P}}$ is in $N_{\mathscr{P}}$ if and only if
$\bigcap_{(i,j,\sigma)\in J}U_{ij}^{\sigma}$ is nonempty.

Finally, the sets $U_{i}:=A-\\{a_{i}\\}$ ranging over $1\leq i\leq n$ cover
$A$. Let $N_{A}$ be the nerve of this covering so that
$J\subset\\{1,\dots,n\\}$ is in $N_{A}$ if and only if $\bigcap_{j\in J}U_{j}$
is nonempty.

######  Lemma 2.

If $f$ is monotonic and unanimous, it induces a well-defined simplicial map
$f^{s}:N_{\mathscr{P}}\rightarrow N_{A}$ where $(i,j,\sigma)\mapsto i$ if
$f(U_{ij}^{\sigma})\subset U_{i}$ and $(i,j,\sigma)\mapsto j$ if
$f(U_{ij}^{\sigma})\subset U_{j}$.

###### Proof.

Fix $i,j,\sigma$ and let $(\succ^{*}_{1},\dots,\succ^{*}_{N})$ be any profile
in $U_{ij}^{\sigma}$ where all agents rank $a_{i}$ and $a_{j}$ above all other
alternatives. Let $(\succ^{**}_{1},\dots,\succ^{**}_{N})$ be the profile
derived from $(\succ^{*}_{1},\dots,\succ^{*}_{N})$ by moving $a_{i}$ to the
top of all rankings. First note that
$f(\succ^{*}_{1},\dots,\succ^{*}_{N})\in\\{a_{i},a_{j}\\}$ since otherwise by
monotonicity we would have $f(\succ^{**}_{1},\dots,\succ^{**}_{N})\neq a_{i}$,
a violation of unanimity. If, say $f(\succ^{*}_{1},\dots,\succ^{*}_{N})=a_{i}$
then $f(U_{ij}^{\sigma})\subset A-\\{a_{j}\\}$ since any
$(\succ_{1},\dots,\succ_{N})\in U_{ij}^{\sigma}$ with
$f(\succ_{1},\dots,\succ_{N})=a_{j}$ would violate monotonicity as we should
have $f(\succ_{1},\dots,\succ_{N})=f(\succ^{*}_{1},\dots,\succ^{*}_{N})$.
Finally, it is clear that $f^{s}$ is a simplicial map since for any $J\in
N_{\mathscr{P}}$ if $(\succ_{1},\dots,\succ_{N})\in\bigcap_{(i,j,\sigma)\in
J}U_{ij}^{\sigma}$ then
$f(\succ_{1},\dots,\succ_{N})\in\bigcap_{(i,j,\sigma)\in
J}f(U_{ij}^{\sigma})$. ∎

Since $f$ induces a simplicial map from $N_{\mathscr{P}}$ to $N_{A}$, it also
induces homomorphisms $f_{*}$ from the homology groups of $N_{\mathscr{P}}$ to
the homology groups $N_{A}$. Likewise it induces homomorphisms $f^{*}$ from
the cohomology groups of $N_{A}$ to those of $N_{\mathscr{P}}$. By studying
these maps, we will deduce the theorem.

###  4.2 The topology of $N_{\mathscr{P}}$ and $N_{A}$

The topology of $N_{A}$ is simple.

######  Lemma 3.

The simplicial complex $N_{A}$ is homotopy equivalent to the $(n-2)$-sphere.

###### Proof.

The only intersection of the $U_{i}$ which is empty is the intersection of all
the $U_{i}$ so the simplicial complex $N_{A}$ is isomorphic to the boundary of
the standard $(n-1)$-simplex. ∎

There are $n$ maximal faces of $N_{A}$ corresponding to $\cap_{y\neq x}U_{y}$
for each $x\in A$. Denote these faces $F_{x}$.

The topology of $N_{\mathscr{P}}$ has already been described in
[baryshnikov1993unifying]. We include the calculations here for completeness.

To calculate the topology of $N_{\mathscr{P}}$ we first construct a manifold
$M$ with a good covering $\\{V_{\alpha}\\}$. These are constructed so that the
nerve $N_{M}$ of the covering is identical to $N_{\mathscr{P}}$. In this case,
the homotopy types of $M$ and $N_{M}$ (and therefore $N_{\mathscr{P}}$)
coincide by lemma 1, and the focus shifts to figuring out the topology of $M$.

Let $W=\\{(x_{1},\dots,x_{n})\in\mathbb{R}^{n}:\sum_{i}x_{i}=0\\}$. The
manifold $M$ will be an open subset of the $N(n-1)$-dimensional vector space
$V:=W^{N}$.

Let $1\leq i<j\leq n$. Denote the intersection of the open halfspaces with $W$

$K_{ij}^{+}=\\{(x_{1},\dots,x_{n})\in W:x_{i}>x_{j}\\}\hskip
56.9055ptK_{ij}^{-}=\\{(x_{1},\dots,x_{n})\in W:x_{i}<x_{j}\\},$

and define, for a vector of signs
$\sigma=(\sigma_{1},\dots,\sigma_{N})\in\\{-,+\\}^{N}$ the open polyhedral
cones

$K_{ij}^{\sigma}=\\{(\bar{x}^{1},\dots,\bar{x}^{N}):\hskip
2.84544pt\bar{x}^{l}\in K_{ij}^{\sigma_{l}}\text{ for all }l\\}$

as products of such halfspaces over voters.

Now we can introduce $M$ as the union of these cones:

$M=\bigcup_{(i,j,\sigma)\in I_{\mathscr{P}}}K_{ij}^{\sigma}.$

The sets $K_{ij}^{\sigma}$ are convex open polyhedra so their nonempty
intersections are again convex open polyhedra and are therefore contractible.
Let $N_{M}$ be the nerve of the covering by $M$ of these sets so that
$J\subset I_{\mathscr{P}}$ is in $N_{M}$ if and only if
$\bigcap_{(i,j,\sigma)\in J}K_{ij}^{\sigma}$ is nonempty.

######  Lemma 4.

$N_{M}=N_{\mathscr{P}}$.

###### Proof.

Suppose $J\in N_{M}$ so that there is some $(\bar{x}^{1},\dots,\bar{x}^{N})$
in $K^{\sigma}_{ij}$ for all $(i,j,\sigma)\in J$. For each $l$, let
$\epsilon_{l}$ be the smallest distance between any two distinct entries of
$\bar{x}^{l}$ and let $\epsilon=\min\epsilon_{l}$. Choose
$(\bar{y}^{1},\dots,\bar{y}^{N})$ so that
$|\bar{y}^{l}_{i}-\bar{x}^{l}_{i}|<\epsilon/2$ for all $i,l$ and such that
each entry of $\bar{y}^{l}$ is distinct for each $l$. Let
$(\succ_{1},\dots,\succ_{N})$ be such that $a_{i}\succ_{l}a_{j}$ if and only
if $\bar{x}^{l}_{i}>\bar{x}^{l}_{j}$ for all $i,j,l$.
$(\bar{y}^{1},\dots,\bar{y}^{N})$ breaks the indifferences of
$(\bar{x}^{1},\dots,\bar{x}^{N})$ so that
$(\succ_{1},\dots,\succ_{N})\in\bigcap_{(i,j,\sigma)\in J}U_{ij}^{\sigma}$ and
$J\in N_{\mathscr{P}}$.

Conversely, suppose $J\in N_{\mathscr{P}}$ so that there is some
$(\succ_{1},\dots,\succ_{N})\in U_{ij}^{\sigma}$ for every $(i,j,\sigma)\in
J$. Let $(\bar{x}^{1},\dots,\bar{x}^{N})$ be any vector of utility
representations. Without loss, we can rescale each $\bar{x}^{i}$ so that the
utilites for each agent sum to zero. Then for each $(i,j,\sigma)\in J$ we have
$(\bar{x}^{1},\dots,\bar{x}^{N})\in K^{\sigma}_{ij}$ and $J\in N_{M}$. ∎

The nerve lemma states that $N_{M}$ is homotopic to the manifold $M$. To
further describe $M$, let $\Lambda$ be the set of functions from
$\\{(i,j):\hskip 2.84544pt1\leq i<j\leq n\\}$ to the integers
$\\{1,2,\dots,N\\}$. For any $\lambda\in\Lambda$, let

$R^{\lambda}=\\{(\bar{x}^{1},\dots,\bar{x}^{N})\in V:\text{ for all }1\leq
i<j\leq n,\hskip
2.84544pt\bar{x}^{\lambda(i,j)}_{i}=\bar{x}^{\lambda(i,j)}_{j}\\}$

######  Claim 1.

The manifold $M$ is the complement $V-\cup_{\lambda\in\Lambda}R^{\lambda}$.

###### Proof.

Fix $i<j$ and $\sigma$. Any $(\bar{x}^{1},\dots,\bar{x}^{N})$ in
$K_{ij}^{\sigma}$ is not in $\cup_{\lambda\in\Lambda}R^{\lambda}$ since for
any $(\bar{y}^{1},\dots,\bar{y}^{N})$ in $\cup_{\lambda\in\Lambda}R^{\lambda}$
there is some $l$ such that $\bar{y}^{l}_{i}=\bar{y}^{l}_{j}$. This proves
that $M\subset V-\cup_{\lambda\in\Lambda}R^{\lambda}.$ Conversely, for any
$(\bar{y}^{1},\dots,\bar{y}^{N})$ in $V-\cup_{\lambda\in\Lambda}R^{\lambda}$
there is some $i<j$ such that $\bar{y}^{l}_{i}\neq\bar{y}^{l}_{j}$ for all
$l$. In this case,
$(\bar{y}^{1},\dots,\bar{y}^{N})\subset\cup_{\sigma}K_{ij}^{\sigma}\subset\cup_{\sigma}\cup_{i<j}K_{ij}^{\sigma}=M$.
∎

Thus the manifold $M=V-\cup_{\lambda\in\Lambda}R^{\lambda}$ is the complement
to the union of a collection of finitely many linear spaces in $V$, a
construct often referred to as the arrangement of linear subspaces
[bjorner1994subspace].

######  Theorem 3.

The cohomology groups $H^{k}(N_{M})$ are $0$ in positive dimensions less than
$n-2$ and $H^{n-2}(N_{M})\cong\mathbb{Z}^{N}$.

###### Proof.

The mapping $\lambda$ which associates voter $k=\lambda(ij)$ to each unordered
pair $(ij)$ can be interpreted as the coloring edges of the complete graph on
$n$ vertices $A$ with $N$ colors.

For a color $k$, consider the graph $\Gamma_{k}$ with vertex set $A$ and the
edges colored $k$. For a point in $R^{\lambda}$, the coordinates in its $k$-th
component are the same if they lie in the same connected component of
$\Gamma_{k}$ (and generically different, otherwise).

This implies that the dimension of the linear subspace $R^{\lambda}$ is equal
to the sum over colors $k$ of the numbers of connected components of
$\Gamma_{k}$, minus 1 (to reflect the constraint that the coordinates sum up
to $0$).

Equivalently, that dimension is given by

$d(\lambda)=\sum_{k}\left(n-|E(\Gamma_{k})|+h_{1}(\Gamma_{k})-1\right),$

where $|E(\Gamma_{k})|$ is the number of edges of color $k$, and
$h_{1}(\Gamma_{k})$ is the rank of the $1$st homology group of $\Gamma_{k}$
(this follows from two definitions of Euler characteristics of a graph, via
numbers of simplices and ranks of homologies).

Collecting all the terms, we obtain

$d(\lambda)=(n-1)N-\binom{n}{2}+\sum_{k}h_{1}(\Gamma_{k}).$

We notice that each $h_{1}(\Gamma_{k})$ is the sum of the ranks of $1$st
homology groups over edge-connected components of $\Gamma_{k}$.

We claim that the $\sum_{k}h_{1}(\Gamma_{k})$ is maximized when all edges are
of the same color. Indeed, one can see that if one repaints a connected
component in $\Gamma_{k}$ into some other color $l$, the $1$-cycles in that
component of $\Gamma_{k}$ becomes $1$-cycles of $\Gamma_{l}$, while new
$1$-cycles might appear, hence non-decreasing the total $h_{1}$. Iterating, we
obtain that all the dimensions of $R^{\lambda}$ do not exceed those of
constant $\lambda$. It remains to notice that at the last repainting step, at
lease one new $1$-cycle is introduced.

It follows that there are $N$ linear spaces of maximal dimension equal to
$(n-1)N-n+1=(N-1)(n-1)$ among linear subspaces $R^{\lambda}$: the $k$-th
subspace corresponds to all edges $(ij)$ colored in color $k$. For such
constant $\lambda\equiv k$,
$R^{\lambda}=\\{(\bar{x}^{1},\dots,\bar{x}^{N}):\bar{x}^{k}_{1}=\cdots=\bar{x}^{k}_{n}\\}$.
All subspaces $R^{\lambda}$ with non-constant $\lambda$’s have smaller
dimensions.

Denote the union of the linear subspaces $R^{\lambda}$ of maximal dimensions
as

$R^{\prime}:=\cup_{\mbox{\tiny\bf constant
}\lambda}R^{\lambda}\subset\cup_{\lambda}R^{\lambda}=:R.$

One can easily verify that $V-R^{\prime}$ is the product of $N$
$(n-1)$-dimensional real spaces with the origins removed, and thus has the
homotopy type of the product of $N$ spheres of dimension $(n-2)$. In
particular, its cohomologies are zero in the dimensions between $0$ and
$(n-2)$, and the rank of $H^{n-2}(V-R^{\prime})$ is $N$.

Comparing the cohomologies of $V-R^{\prime}$ and $V-R$ is easier using
Alexander duality. Consider the $(N-1)(n-1)$-dimensional sphere
$S=p_{\infty}\cup V$; and compactify $R,R^{\prime}$ by adding the point
$p_{\infty}$ at infinity to these arrangements. Then Alexander duality asserts
that

$H^{l}(V-R)\cong
H_{(N-1)(n-1)-l-1}(R+p_{\infty},p_{\infty}),H^{l}(V-R^{\prime})\cong
H_{(N-1)(n-1)-l-1}(R^{\prime}+p_{\infty},p_{\infty}).$

Consider the long exact sequence for the triple $\\{p_{\infty}\\}\subset
R^{\prime}+p_{\infty}\subset R+p_{\infty}$

$\cdots\rightarrow H_{l}(R^{\prime}+p_{\infty},p_{\infty})\rightarrow
H_{l}(R+p_{\infty},p_{\infty})\rightarrow
H_{l}(R+p_{\infty},R^{\prime}+p_{\infty})\rightarrow
H_{l-1}(R^{\prime}+p_{\infty},p_{\infty})\rightarrow\cdots$

The fact that $R,R^{\prime}$ has no cells in dimensions above maximal (i.e.,
$(N-1)(n-1)-(n-2)-1$), and that the pair $R,R^{\prime}$ has no cells in the
maximal dimension, one arrives at the desired conclusion. ∎

It will be useful to have a basis for $H_{n-2}(N_{\mathscr{P}})$ and
$H^{n-2}(N_{\mathscr{P}})$. To that end, we will first calculate the basis for
the case when $N=1$. In this case, $N_{\mathscr{P}}=N_{P}$ and $M$ is simply
$\mathbb{R}^{n}$ minus the diagonal $D$ where
$D=\\{x\in\mathbb{R}^{n}:x_{i}=x_{j}\text{ for all }i,j\\}$.

Let $\Delta_{P}$ be the $n(n-1)-1$ simplex with the same vertices as $N_{P}$.
Consider the unoriented cyclic graph $g^{\circ}$ with vertices
$\\{1,2,\dots,n\\}$ and edges $(1,2),(2,3),\dots,(n-1,n),(n,1)$. Any
orientation $g$ of the edges of $g^{\circ}$, gives a face in $\Delta_{P}$
including the vertices $(i,j,x)$ such that $x=+$ if $i\leftarrow i+1$ and
$x=-$ if $i\rightarrow i+1$ in $g$. We denote this simplex as $\delta(g)$ and
write its boundary as $h(g)$.

######  Lemma 5.

If $g$ is an oriented cycle, $h(g)$ generates $H_{n-2}(N_{P})$. Otherwise it
is zero.

###### Proof.

Suppose that
$\delta(g)=\\{(1,2,\alpha_{1}),\dots,(n-1,n,\alpha_{n-1}),(1,n,\alpha_{n})\\}$.
Any $n-1$ give rise to an acyclic binary relation on $\\{1,2,\dots,n\\}$ which
can be extended to a strict order so the corresponding face is in $N_{P}$.
Since $h(g)=\partial\delta(g)$, it is in $H^{n-1}(N_{P})$. If $g$ is acyclic,
$\delta(g)\in N_{P}$ so that $h(g)=0$ in $H_{n-2}(N_{P})$. Next, let $g$ be an
oriented cycle, for example $\alpha_{k}=+$ for all $k<n$ and $\alpha_{n}=-$.
The sets $R_{12}^{+},\dots,R_{n-1n}^{+},R_{1n}^{-}$ cover $R^{n}-D$ since any
$x$ not in their union has $x_{1}\leq x_{2}\leq\dots\leq x_{n}\leq x_{1}$.
Then the inclusion of the subcomplex of $N_{P}$ whose maximal faces are the
$(n-1)$-subsets of $\delta(g)$ is a homotopy equivalence and $h(g)$ is a
generator for $H_{n-1}(N_{P})$. ∎

Going forward, fix an oriented cycle $\hat{g}$ and let $c$ be the associated
generator from above. The universal coefficient theorem says that
$H_{n-2}(N_{P})\cong H^{n-2}(N_{P})$ and that we can find an element $c^{*}$
of $H^{n-2}(N_{P})$ where $(c,c^{*})=1$ and $c^{*}$ is a generator for
$H^{n-2}(N_{P})$.333$(c,c^{*})$ here denotes the pairing between homology and
cohomology.

Now we’re ready to give a basis for $H^{n-2}(N_{P})$. Let
$\Delta_{\mathscr{P}}$ be the simplex with the same vertices as
$N_{\mathscr{P}}$. Any collection $(g_{1},\dots,g_{N})$ of orientations of
$g^{0}$ gives a face in $\Delta_{\mathscr{P}}$ including the $(i,j,\sigma)$
where $\sigma_{l}=+$ if $i\rightarrow i+1$ in $g_{l}$ and $\sigma_{l}=-$ if
$i\leftarrow i+1$ in $g_{l}$. We denote this simplex as
$\delta(g_{1},\dots,g_{N})$ and write its boundary as $h(g_{1},\dots,g_{N})$.

For each $l$, let $p_{l}$ be the simplicial map from $N_{\mathscr{P}}$ to
$N_{P}$ sending $(i,j,\sigma)$ to $(i,j,\sigma_{l})$. Let $p_{l}^{*}$ be the
induced homomorphism $H^{n-2}(N_{P})\rightarrow H^{n-2}(N_{\mathscr{P}})$.

For each $l$, fix some $(g^{l}_{1},\dots,g^{l}_{N})$ where $g^{k}_{l}$ is
acylic if $k\neq l$ and $g^{l}_{l}=\hat{g}$ let
$h_{l}=h(g^{l}_{1},\dots,g^{l}_{N})$.

######  Lemma 6.

The collection $\\{h_{1},\dots,h_{N}\\}$ is a basis for
$H_{n-2}(N_{\mathscr{P}})$ and $\\{p_{1}^{*}(c^{*}),\dots,p_{N}^{*}(c^{*})\\}$
is the dual basis for $H^{n-2}(N_{\mathscr{P}})$.

###### Proof.

From the universal coefficient theorem, $H_{n-2}(N_{\mathscr{P}})\cong
H^{n-2}(N_{\mathscr{P}})$. For any $k$ and $l$, $(h_{k},p_{l}^{*}(c^{*}))$ is
$1$ if $k=l$ and is zero otherwise. It is a simple exercise to verify that
both must then be bases. ∎

This allows us to conclude the following.

######  Corollary 1.

For any two tuples of orientations $(g_{1},\dots,g_{N})$ and
$(g_{1}^{\prime},\dots,g_{N}^{\prime})$ where for some $k$, (1)
$g_{k}=g_{k}^{\prime}$ (2) both $g_{k}$ and $g_{k}^{\prime}$ are acyclic and
(3) $g_{l}$ and $g_{l}^{\prime}$ are acyclic for all $l\neq k$ then
$h(g_{1},\dots,g_{N})=h(g_{1}^{\prime},\dots,g_{N}^{\prime})$ in
$H_{n-2}(N_{\mathscr{P}})$.

###  4.3 The Topology of a Social Choice Function

Let $d^{*}$ be a generator of $H^{n-2}(N_{A})$.

######  Proposition 1.

Suppose $f$ is monotonic and unanimous. $(f_{\star}(h_{l}),d^{*})=1$ if and
only if $l$ is a dictator of $f$. Otherwise it is zero.

###### Proof.

Let $(1,2,\sigma^{1}),\dots(n-1,n,\sigma^{n-1}),(1,n,\sigma^{n})$ be the
vertices of $\delta(g^{l}_{1},\dots,g^{l}_{N})$. $f^{s}$ maps each of these
vertices onto a vertex of $N_{A}$. If $f^{s}$ maps any two vertices of
$\delta(g^{l}_{1},\dots,g^{l}_{N})$ to the same vertex of $N_{A}$ then
$(f_{\star}(h_{l}),d^{*})=0$ and $l$ is not a dictator since in this case
there is some $a\in A$ which is not chosen even when $l$ top-ranks it.

Conversely, suppose that $f^{s}$ is injective on the vertices of
$\delta(g^{l}_{1},\dots,g^{l}_{N})$. Consider some $g^{\prime}$ derived from
$g^{l}_{k}$ by swapping one of the arrows without forming a cycle. All but one
of the vertices of $\delta(g^{l}_{1},\dots,g^{\prime},\dots g^{l}_{N})$ are
vertices of $\delta(g^{l}_{1},\dots,g^{l}_{N})$. Let
$h_{l}^{\prime}=h(g^{l}_{1},\dots,g^{\prime},\dots g^{l}_{N})$. Corollary 1
implies $h_{l}=h_{l}^{\prime}$. The new vertex of
$\delta(g^{l}_{1},\dots,g^{\prime},\dots g^{l}_{N})$ must mapped to the same
vertex of $N_{A}$ as the one it replaced in
$\delta(g^{l}_{1},\dots,g^{l}_{N})$ since otherwise,
$(f_{\star}(h_{l}),d^{*})\neq 0$ and $(f_{\star}(h_{l}),d^{*})=0$. Repeating
this process, changing one arrow at a time, for any $i$ we can reach the a
tuple of orientations where $i\leftarrow i+1$ for all orientations. ∎

Finally, consider $h(\hat{g},\dots,\hat{g})$. Unanimity implies that
$(f_{\star}(h(\hat{g},\dots,\hat{g})),d^{*})=1$. Together with proposition 1,
we see that there must be exactly one dictator, concluding the proof of the
Muller-Satterthwaite theorem.

To prove the Gibbard-Satterthwaite theorem, we need the following simple fact,
well-known in social choice theory (see for example muller1977equivalence).

######  Proposition 2.

A social choice function is monotonic and unanimous if and only if it is
surjective and strategy-proof.

###### Proof.

A unanimous social choice function is clearly surjective. A monotonic social
choice function is also strategy-proof: if there were some
$f(\succ_{i},\succ_{-i})\prec_{i}f(\succ_{i}^{\prime},\succ_{-i})$, letting
$\succ_{i}^{*}$ be the preference derived from $\succ_{i}$ by pushing
$f(\succ_{i}^{\prime},\succ_{-i})$ to the top, monotonicity implies
$f(\succ_{i},\succ_{-i})=f(\succ_{i}^{*},\succ_{-i})=f(\succ_{i}^{\prime},\succ_{-i})$,
a contradiction.

For the converse, suppose that $f$ is strategy-proof and surjective. Let
$f(\succ_{1},\dots,\succ_{N})=a$ and for each $i$, $\succ_{i}^{\prime}$ is a
linear order such that $a\succ_{i}b$ implies that $a\succ^{\prime}_{i}b$ for
all $b$. We have that
$f(\succ_{1},\succ_{2},\dots,\succ_{N})=f(\succ_{1}^{\prime},\succ_{2},\dots,\succ_{N})=f(\succ_{1}^{\prime},\succ_{2}^{\prime},\dots,\succ_{N})=\cdots=f(\succ_{1}^{\prime},\succ_{2}^{\prime},\dots,\succ_{N}^{\prime})$,
so that $f$ is monotonic. If $f$ is strategy-proof and surjective it is also
unanimous since for any $a$ there is some $(\succ_{1},\dots,\succ_{N})$ such
that $f(\succ_{1},\dots,\succ_{N})=a$ and for any profile
$(\succ^{\prime}_{1},\dots,\succ^{\prime}_{N})$ where all agents top-rank $a$,
we have $f(\succ^{\prime}_{1},\dots,\succ^{\prime}_{N})$ by monotonicity. ∎

This proves the Gibbard-Satterthwaite Theorem.

## References

  * [1] [Barberá]Barberá1983barbera1983strategy Barberá, S. (1983): “Strategy-proofness and pivotal voters: a direct proof of the Gibbard-Satterthwaite theorem,” _International Economic Review_ , 24(2), 413–417.
  * [2] [Baryshnikov]Baryshnikov1993baryshnikov1993unifying Baryshnikov, Y. M. (1993): “Unifying impossibility theorems: a topological approach,” _Advances in Applied Mathematics_ , 14(4), 404–415.
  * [3] [Björner]Björner1994bjorner1994subspace Björner, A. (1994): “Subspace arrangements,” in _First European Congress of Mathematics: Paris, July 6-10, 1992 Volume I Invited Lectures (Part 1)_ , pp. 321–370. Springer.
  * [4] [Chichilnisky]Chichilnisky1980chichilnisky1980social Chichilnisky, G. (1980): “Social choice and the topology of spaces of preferences,” _Available at SSRN 1367741_.
  * [5] [Gibbard]Gibbard1973gibbard1973manipulation Gibbard, A. (1973): “Manipulation of voting schemes: a general result,” _Econometrica: journal of the Econometric Society_ , pp. 587–601.
  * [6] [Hatcher]Hatcher2002hatcher2002algebraic Hatcher, A. (2002): _Algebraic Topology_. Cambridge University Press.
  * [7] [Mossel and Rácz]Mossel and Rácz2012mossel2012quantitative Mossel, E., and M. Z. Rácz (2012): “A quantitative Gibbard-Satterthwaite theorem without neutrality,” in _Proceedings of the forty-fourth annual ACM symposium on Theory of computing_ , pp. 1041–1060.
  * [8] [Muller and Satterthwaite]Muller and Satterthwaite1977muller1977equivalence Muller, E., and M. A. Satterthwaite (1977): “The equivalence of strong positive association and strategy-proofness,” _Journal of Economic Theory_ , 14(2), 412–418.
  * [9] [Reny]Reny2001reny2001arrow Reny, P. J. (2001): “Arrow’s theorem and the Gibbard-Satterthwaite theorem: a unified approach,” _Economics letters_ , 70(1), 99–105.
  * [10] [Satterthwaite]Satterthwaite1975satterthwaite1975strategy Satterthwaite, M. A. (1975): “Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions,” _Journal of economic theory_ , 10(2), 187–217.
  * [11] [Sen]Sen2001sen2001another Sen, A. (2001): “Another direct proof of the Gibbard–Satterthwaite theorem,” _Economics Letters_ , 70(3), 381–385.
  * [12]


11institutetext: Indian Association for the Cultivation of Science, Jadavpur
700032, India 11email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Improving Neural Topic Models with Wasserstein Knowledge Distillation

Suman Adhya  0000-0001-6568-2020 Debarshi Kumar Sanyal  0000-0001-8723-5002

###### Abstract

Topic modeling is a dominant method for exploring document collections on the
web and in digital libraries. Recent approaches to topic modeling use
pretrained contextualized language models and variational autoencoders.
However, large neural topic models have a considerable memory footprint. In
this paper, we propose a knowledge distillation framework to compress a
contextualized topic model without loss in topic quality. In particular, the
proposed distillation objective is to minimize the cross-entropy of the soft
labels produced by the teacher and the student models, as well as to minimize
the squared 2-Wasserstein distance between the latent distributions learned by
the two models. Experiments on two publicly available datasets show that the
student trained with knowledge distillation achieves topic coherence much
higher than that of the original student model, and even surpasses the teacher
while containing far fewer parameters than the teacher’s. The distilled model
also outperforms several other competitive topic models on topic coherence.

###### Keywords:

Topic modeling Knowledge distillation Wasserstein distance Contextualized
topic model Variational autoencoder.

##  1 Introduction

Topic modeling has come up as an important technique to analyze large document
corpora and extract their themes automatically [1], [30], [26]. Therefore,
they are frequently used to obtain an overview of the topics in document
archives and web search results, match queries and documents, and diversify
search results [28, 11]. While latent Dirichlet allocation (LDA) [5] is the
classical topic modeling algorithm, recent approaches exploit deep neural
networks, specifically, variational autoencoders (VAEs) [13]. ProdLDA [24] is
a well-known VAE-based topic model that uses a product of experts and a
Laplace approximation to the Dirichlet prior. Bianchi et al. [3] recently
proposed CombinedTM, a contextualized topic model that feeds into the VAE of
ProdLDA a distributed representation of the document built with a pre-trained
language model (PLM) like sentence-BERT (SBERT) [22] along with a bag-of-words
(BoW) representation of the document. It achieves state-of-the-art topic
coherence on many benchmark data sets. Given a VAE-based topic model pre-
trained on a corpus, one can pass a document from the corpus through the VAE
encoder and recover its topics. A remarkable feature of contextualized topic
models is that, if the PLM is multilingual and the input to the encoder solely
consists of contextualized representations from the PLM, it is possible to
train the model in one language and test it in another, making it a zero-shot
topic model, also called ZeroShotTM [4]. Increasing the network complexity
like the depth or width of the neural networks in the VAE might improve the
coherence of the generated topics but produces a larger memory footprint,
thereby making it difficult to store and use the topic models on resource-
constrained devices. Using only contextualized embeddings in the input would
also reduce the model size but could hit the topic quality as well.

In this paper, we investigate if a VAE-based topic model can be compressed
without compromising topic coherence. For this purpose, we use knowledge
distillation (KD), which involves a teacher model to improve the performance
of a smaller student model [12]. While KD has been used for classification
tasks in image [10] and text processing [17], this paper tackles an
unsupervised learning problem for a generative model. Specifically, we distill
knowledge from a CombinedTM teacher to a smaller ZeroShotTM student. In
standard KD [12], the aim is to minimize the cross-entropy between the soft
labels produced by the student and the teacher models along with the Kullback-
Leibler (KL) divergence between their respective output distributions. But
even if the two distributions have very little dissimilarity with each other,
the KL-divergence may reach a very high value, and if the two distributions
are not overlapping at all, it explodes to infinity [19]. To avoid these
issues, we choose 2-Wasserstein distance [18] instead of KL-divergence in
distillation loss. Our distillation process minimizes the cross-entropy
between the soft labels produced by the teacher and the student, and the
square of the 2-Wasserstein distance between the latent distributions learned
by the two models. Wasserstein distance arises in the theory of optimal
transport and measures how ‘close’ two distributions are [21, 27, 9]. Unlike
the KL divergence, if the Wasserstein between two distributions is high, this
actually represents that the underlying distributions are very different from
each other.

In summary, our contributions are: (1) We propose a 2-Wasserstein distance-
based knowledge distillation framework for neural topic models. We call our
method Wasserstein knowledge distillation. To the best of our knowledge, this
is the first work on inter-VAE knowledge distillation for topic modeling. (2)
Experiments on two public datasets show that in terms of topic coherence, the
distilled model significantly outperforms the student and even scores better
than the teacher. The distilled model also beats several strong baselines on
topic coherence. This demonstrates the efficacy of our approach. We have made
our code publicly available111https://github.com/AdhyaSuman/CTMKD.

##  2 Background on Wasserstein Distance

Let $(\mathcal{X},d)$ be a complete separable metric space with metric $d$ and
equipped with a Borel $\sigma$-algebra. Let $\mathcal{P}(\mathcal{X})$ denote
the space of all probability measures defined on $\mathcal{X}$ with finite
$p$-th moment for $p\geq 1$. If
$\mathbb{P}_{1},\mathbb{P}_{2}\in\mathcal{P}(\mathcal{X})$, then
$\operatorname{\Pi}(\mathbb{P}_{1},\mathbb{P}_{2})$ is defined to be the set
of measures ${\pi}\in\mathcal{P}(\mathcal{X}^{2})$ having $\mathbb{P}_{1}$ and
$\mathbb{P}_{2}$ as marginals. The $p^{\text{th}}$ Wasserstein distance
between the two probability measures $\mathbb{P}_{1}$ and $\mathbb{P}_{2}$ in
$\mathcal{P}(\mathcal{X})$ is defined as

$\displaystyle W_{p}(\mathbb{P}_{1},\mathbb{P}_{2})$
$\displaystyle=\left(\inf_{{\pi}\in\operatorname{\Pi}(\mathbb{P}_{1},\mathbb{P}_{2})}\int_{\mathcal{X}^{2}}d({x},{y})^{p}\operatorname{d}{{\pi}}({x},{y})\right)^{1/p}$
(1)

$W_{p}(\mathbb{P}_{1},\mathbb{P}_{2})$ is intuitively the minimum ‘cost’ of
transforming $\mathbb{P}_{1}$ to $\mathbb{P}_{2}$ (or vice versa) [27].
Consider $\mathcal{X}=\mathbb{R}^{n}$ with $d$ as the Euclidean norm. Suppose
$\mathbb{P}_{1}=\mathcal{N}(\mu_{1},\Sigma_{1})$, and
$\mathbb{P}_{2}=\mathcal{N}(\mu_{2},\Sigma_{2})$ are normal distributions with
means $\mu_{1},\mu_{2}\in\mathbb{R}^{n}$ and symmetric positive semi-definite
covariance matrices $\Sigma_{1},\Sigma_{2}\in\mathbb{R}^{n\times n}$. From
[18], the squared 2-Wasserstein distance between $\mathbb{P}_{1}$ and
$\mathbb{P}_{2}$ is given by:

$\displaystyle
W_{2}(\mathbb{P}_{1},\mathbb{P}_{1})^{2}=\lVert{\mu}_{1}-{\mu}_{2}\rVert_{2}^{2}+\operatorname{trace}\big{(}{\Sigma}_{1}+{\Sigma}_{2}-2({\Sigma}_{2}^{1/2}{\Sigma}_{1}{\Sigma}_{2}^{1/2})^{1/2}\big{)}$
(2)

Wasserstein distance has been used to train various machine learning models
including classifiers [7], Boltzmann machines [16], and generative adversarial
networks [2], where it is found to be a better loss metric than KL-divergence.

##  3 Proposed Framework for Knowledge Distillation

Figure 1: Framework for knowledge distillation from CombinedTM to ZeroShotTM.

Our framework for KD is shown in Figure 1. The teacher and the student models
are both VAEs. The teacher $T$ is a CombinedTM [3] that takes as input ${x}$ a
document encoded as the concatenation of the document’s normalized BoW
representation ${x}_{\text{BoW}}\in\mathbb{R}^{V}$, where $V$ is the
vocabulary size, and its contextualized embedding ${x}_{\text{ctx}}$ scaled to
dimension $V$ by a linear layer. The student is a ZeroShotTM [4]. While the
student’s encoder takes only the document’s contextualized representation, its
decoder still needs the BoW vector during training, but it is not necessary
when we use only its trained encoder to infer the topics for a given document.
The teacher’s encoder is a multi-layer feed-forward neural network (FFNN)
while we make the student’s encoder an FFNN with one hidden layer.

A VAE-based topic model works as follows [24]. Suppose it has to learn $K$
topics from a corpus. The VAE encoder having weights $W$ learns the
approximate posterior distribution $q_{{W}}({z}|{x})$ represented by mean
$\mu\in\mathbb{R}^{K}$ and variance $\sigma^{2}\in\mathbb{R}^{K}$ for an input
instance ${x}$. The decoder samples a vector ${z}\sim q_{W}({z}|{x})$ using
the reparameterization trick [13], and produces the document-topic vector
${\theta}=\operatorname{\texttt{softmax}}({z})$, which is passed through a
shallow FFNN with weight matrix $\beta_{K\times V}$ to learn a distribution
$p_{{\beta}}({x}|{z})$. The VAE is trained by backpropagation to minimize the
following loss $\mathcal{L}_{\operatorname{VAE}}$:

$\displaystyle\mathcal{L}_{\operatorname{VAE}}$
$\displaystyle=\mathcal{L}_{\operatorname{NLL}}+\mathcal{L}_{\operatorname{KL}}\equiv-\mathbb{E}_{{z}\sim
q_{W}({z}|{x})}\big{[}\log
p_{{\beta}}({x}|{z})\big{]}+D_{\operatorname{KL}}\big{(}q_{W}({z}|{x})\parallel
p({z})\big{)}$ (3)

where $\mathcal{L}_{\operatorname{NLL}}$ is the expected negative log-
likelihood of the reconstructed BoW, and $\mathcal{L}_{\operatorname{KL}}$ is
a regularizer measuring the KL-divergence of the encoder’s output
$q_{{W}}({z}|{x})$ from the assumed prior $p({z})$ of the latent distribution.

Now suppose that the teacher has been already trained on a dataset to learn
$K$ topics, and that, after training, the weights of its encoder and decoder
are ${W}^{\ast}_{T}$ and ${\beta}^{\ast}_{T}$, respectively. We will use this
frozen teacher model to train the student with KD to learn $K$ topics from the
same dataset and the same vocabulary. We denote this KD-trained student by
$S^{\prime}$. Let the weights in its encoder and decoder be ${W}_{S^{\prime}}$
and ${\beta}_{S^{\prime}}$, respectively, at the start of some iteration
during the training of $S^{\prime}$. Given an input instance $x$, the
student’s loss function has two components:

(i) Loss associated with student VAE: The VAE loss
$\mathcal{L}_{\operatorname{VAE}}$ is given by Eq. (3).

(ii) Loss associated with knowledge distillation: While training $S^{\prime}$,
every instance ${x}$ is passed through both $T$ and $S^{\prime}$. Suppose the
teacher’s encoder outputs the $K$-variate Gaussian
$\mathcal{N}({z}|{\mu}_{T},{\sigma}_{T}^{2})$ while the student’s encoder
outputs the $K$-variate Gaussian
$\mathcal{N}({z}|{\mu}_{S^{\prime}},{\sigma}_{S^{\prime}}^{2})$. Note that
instead of a full covariance matrix, a diagonal covariance matrix (encoded as
a vector) is learned [3], [4]. Let
${\Sigma}_{T}=\operatorname{\texttt{diag}}(\sigma^{2}_{T})$ and
${\Sigma}_{S^{\prime}}=\operatorname{\texttt{diag}}(\sigma^{2}_{S^{\prime}})$,
which are easily observed to be symmetric positive semi-definite. We calculate
the squared 2-Wasserstein distance between the distributions learned by $T$
and $S^{\prime}$ using Eq. (2):

$\displaystyle\mathcal{L}_{\text{KD-2W}}=$
$\displaystyle\lVert{\mu}_{T}-{\mu}_{S^{\prime}}\rVert_{2}^{2}+\operatorname{trace}\big{(}{\Sigma}_{T}+{\Sigma}_{S^{\prime}}-2({\Sigma}_{S^{\prime}}^{1/2}{\Sigma}_{T}{\Sigma}_{S^{\prime}}^{1/2})^{1/2}\big{)}$
(4)

We propose to minimize $\mathcal{L}_{\text{KD-2W}}$ so that the distribution
learned by the student is pulled close to that of the teacher. The decoder of
the teacher and that of the student produce unnormalized logits
$u_{T}=\beta_{T}^{\top}\theta$ and
$u_{S^{\prime}}=\beta_{S^{\prime}}^{\top}\theta$, respectively. We compute the
cross-entropy loss $\mathcal{L}_{\text{KD-CE}}$ between the soft labels
$\operatorname{\texttt{softmax}}({u}_{T}/t)$ and
$\operatorname{\texttt{softmax}}({u}_{S^{\prime}}/t)$ where $t$ is the softmax
temperature (hyperparameter) [12]. In addition to identifying the most
probable class, the soft labels formed by a higher softmax temperature ($t>1$)
capture the correlation between the labels, which is desired in the
distillation framework. The total loss due to KD is

$\displaystyle\mathcal{L}_{\operatorname{KD}}=\mathcal{L}_{\text{KD-2W}}+t^{2}\mathcal{L}_{\text{KD-
CE}}$ (5)

Finally, with $\alpha\in[0,1]$ as a hyperparameter, the total loss for the
student $S^{\prime}$ is

$\displaystyle\mathcal{L}_{S^{\prime}}=(1-\alpha)\mathcal{L}_{\text{VAE}}+\alpha\mathcal{L}_{\text{KD}}$
(6)

##  4 Experimental Setup

We have performed all experiments in OCTIS [25], which is an integrated
framework for topic modeling. We use the following datasets from OCTIS: 20NG,
which contains $16,309$ newsgroup documents on $20$ different subjects [25],
and M10 comprising 8355 scientific publications from 10 distinct research
areas [20]. For each dataset, the vocabulary contains the 2K most common words
in the corpus. We represent each topic by its top-10 words. We use Normalized
Pointwise Mutual Information (NPMI) [15] and Coherence Value (CV) [23, 14] to
measure topic coherence. NPMI of a topic is high if the words in the topic
tend to co-occur. CV is calculated using an indirect cosine measure along with
the NPMI score over a boolean sliding window. Higher values of NPMI and CV are
better.

The experiments are done for topic counts $K\in\\{20,50,100\\}$ on the 20NG
dataset and for topic counts $K\in\\{10,20,50,100\\}$ on the M10 dataset,
where 20 and 10 are the golden number of categories for 20NG and M10,
respectively. We denote the teacher (CombinedTM) by T, the student
(ZeroShotTM) by S, and the distilled student model (ZeroShotTM) by SKD. The
encoder in T uses 768-dimensional contextualized sentence embeddings (SBERT)
from paraphrase-distilroberta-base-v2. The encoders in S and SKD use
384-dimensional SBERT embeddings from all-MiniLM-L6-v2 model.

Table 1: The optimal number of hidden layers $H$ in the encoder of the teacher
T for each dataset and different topic counts $K$.

Dataset K H Dataset K H 20NG 20 50 100 1 1 5 M10 10 4 20 5 50 2 100 3

Using the Bayesian optimization framework of OCTIS, we have calculated the
optimal number of hidden layers $H$ in the teacher’s encoder (which takes as
input the concatenation of a document’s contextualized and BoW
representations) from the set $\\{1,2,\ldots,10\\}$ that maximizes the NPMI
for the teacher. As shown in Table 1, on 20NG dataset, we found $H=1$ for
topic count $K\in\\{20,50\\}$ and $H=5$ for $K=100$; on M10, we observed $H=4$
for $K=10$, $H=5$ for $K=20$, $H=2$ for $K=50$, and $H=3$ for $K=100$. Each
hidden layer of the teacher contains 100 neurons.

We have tuned the hyperparameters $\alpha\in[0,1]$ and
$t\in\\{1,2,\ldots,5\\}$ for SKD in OCTIS. For performance analysis, we
compare these models with ProdLDA [24], NeuralLDA [24], Embedded Topic Model
(ETM) [6] and LDA [5], already implemented in OCTIS. We use the default
parameters unless otherwise mentioned. All models are trained for 100 epochs
with a batch size of 64. Each reported performance score is the median over 5
runs (except for T, where we use a single run as it must be frozen for KD).

Figure 2: Coherence scores (NPMI and CV) for different topic models on two
datasets: 20NG and M10. The X-axis is marked with the topic counts used for
each dataset.

##  5 Results

Models S and SKD contain the same number of parameters, which is smaller than
that of T. The sizes of all the models depend on the SBERT dimension, the
number and size of hidden layers, the number of topics, and the vocabulary
size. For example, for 20 topics in 20NG, T takes 6.14 MB while SKD 2.74 MB
(for parameters and buffers) – a reduction in model size by $55.4\%$. In
general, the compression ranged from $37.6\%$ to $56.3\%$.

Fig. 2 shows the coherence scores for each topic model for all topic settings
and datasets. SKD achieves the highest NPMI and CV scores. Among T, S, and
SKD, we find SKD performs much better than S and even modestly better than T.
On 20NG, the NPMI scores of (T, S, SKD) are $(0.125,0.106,0.132)$ for $K=20$,
$(0.121,0.098,0.130)$ for $K=50$, and $(0.098,0.076,0.105)$ for $K=100$, so
the maximum gain of SKD over S is $38.2\%$ and that over T is $7.4\%$.
Similarly on M10, the NPMI scores are $(0.073,0.046,0.084)$ for $K=10$,
$(0.076,0.037,0.08)$ for $K=20$, $(0.053,-0.027,0.073)$ for $K=50$, and
$(0.059,-0.06,0.07)$ for $K=100$. Thus, on M10, SKD improves NPMI of S by over
$100\%$ for $K\in\\{50,100\\}$, and that of T by at most $37.7\%$. Student
outperforming the teacher is surprising but has been reported earlier for
supervised tasks [8, 29].

When we deleted any one of the two loss terms from
$\mathcal{L}_{\operatorname{KD}}$ in Eq. (5), NPMI and CV of SKD dropped (see
Table 2). Thus, although the simpler model and weaker SBERT lower the
student’s performance, the knowledge distilled from the teacher’s encoder and
decoder vastly improves it.

Table 2: Ablation study for the distillation loss term defined in Eq. (5). For
each metric, the median over five independent runs for each topic count is
mentioned.

KD-loss ($\mathcal{L}_{\operatorname{KD}}$) 20NG M10 NPMI CV NPMI CV
$\mathbf{20}$ 50 $\mathbf{100}$ $\mathbf{20}$ 50 $\mathbf{100}$ $\mathbf{10}$
$\mathbf{20}$ 50 $\mathbf{100}$ $\mathbf{10}$ $\mathbf{20}$ 50 $\mathbf{100}$
$\mathcal{L}_{\text{KD-2W}}+\mathcal{L}_{\text{KD-CE}}$ 0.132 0.130 0.105
0.687 0.657 0.638 0.084 0.080 0.073 0.070 0.522 0.499 0.485 0.475
$\mathcal{L}_{\text{KD-2W}}$ 0.109 0.114 0.089 0.659 0.638 0.615 0.051 0.049
0.037 0.043 0.498 0.479 0.459 0.452 $\mathcal{L}_{\text{KD-CE}}$ 0.110 0.105
0.083 0.653 0.629 0.588 0.042 0.052 0.016 0.023 0.485 0.464 0.425 0.425

The higher performance of the contextualized topic models over other topic
models agrees with similar results in [3, 4]. In Table 3, we compare
qualitatively some aligned topics learned by T, S, and SKD from the 20NG
corpus. For the first three topics, SKD displays more word overlap than S with
the corresponding topics from T, showing that T and SKD learn similar topic-
word distributions. Interestingly, the fourth topic from SKD contains more
healthcare-related words than the fourth topic from T although the latter is
also primarily on healthcare; this shows that SKD can produce more coherent
topics than T.

Table 3: Some selected topics output when T, S, and SKD models are run on the
20NG corpus for 20 topics. If a word in a topic from S or SKD is shared with
the corresponding topic in T, then it is in bold otherwise it is in italic.

Model ID Topics T $0$ gun, law, firearm, crime, weapon, assault, amendment,
state, police, permit $11$ russian, turkish, people, village, genocide,
armenian, muslim, population, greek, army $17$ oil, engine, ride, front, road,
chain, bike, motorcycle, water, gas $3$ health, make, president, patient,
medical, people, doctor, disease, work, year S $0$ law, people, state,
government, gun, amendment, constitution, firearm, crime, privacy $1$
armenian, village, soldier, soviet, muslim, troop, turkish, russian, genocide,
land $17$ engine, car, mile, ride, bike, oil, front, wheel, motorcycle, tire
$7$ medical, disease, study, treatment, doctor, patient, health, food, risk,
percent SKD $0$ gun, law, weapon, firearm, amendment, crime, bill, assault,
constitution, police $11$ turkish, genocide, armenian, russian, village,
population, israeli, war, attack, muslim $17$ ride, engine, car, bike,
motorcycle, front, oil, motor, road, seat $3$ health, medical, doctor,
disease, patient, insurance, treatment, drug, care, risk

##  6 Conclusion

We have proposed a 2-Wasserstein loss-based knowledge distillation framework
to compress a contextualized topic model. Experiments on two datasets show
that the pruned topic model produces topics with coherence better than that of
the topics produced by the student and even the larger teacher model. This is
a new method for neural topic distillation. In the future, we would like to
study it analytically and apply it to distill knowledge across other neural
topic models.

## References

  * [1] Adhya, S., Sanyal, D.K.: What does the Indian Parliament discuss? an exploratory analysis of the question hour in the Lok Sabha. In: Proceedings of the LREC 2022 workshop on Natural Language Processing for Political Sciences. pp. 72–78. European Language Resources Association, Marseille, France (Jun 2022), https://aclanthology.org/2022.politicalnlp-1.10
  * [2] Arjovsky, M., Chintala, S., Bottou, L.: Wasserstein generative adversarial networks. In: Proceedings of the International Conference on Machine Learning. pp. 214–223. PMLR (2017), https://proceedings.mlr.press/v70/arjovsky17a.html
  * [3] Bianchi, F., Terragni, S., Hovy, D.: Pre-training is a hot topic: Contextualized document embeddings improve topic coherence. In: Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers). pp. 759–766 (2021), https://aclanthology.org/2021.acl-short.96/
  * [4] Bianchi, F., Terragni, S., Hovy, D., Nozza, D., Fersini, E.: Cross-lingual contextualized topic models with zero-shot learning. In: The 16th Conference of the European Chapter of the Association for Computational Linguistics. Association for Computational Linguistics (2021), https://aclanthology.org/2021.eacl-main.143/
  * [5] Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent Dirichlet allocation. Journal of Machine Learning Research 3(Jan), 993–1022 (2003), https://www.jmlr.org/papers/volume3/blei03a/blei03a.pdf
  * [6] Dieng, A.B., Ruiz, F.J., Blei, D.M.: Topic modeling in embedding spaces. Transactions of the Association for Computational Linguistics 8, 439–453 (2020), https://doi.org/10.1162/tacl_a_00325
  * [7] Frogner, C., Zhang, C., Mobahi, H., Araya-Polo, M., Poggio, T.: Learning with a wasserstein loss. In: Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2. p. 2053–2061. NIPS’15, MIT Press, Cambridge, MA, USA (2015), http://papers.neurips.cc/paper/5679-learning-with-a-wasserstein-loss.pdf
  * [8] Furlanello, T., Lipton, Z., Tschannen, M., Itti, L., Anandkumar, A.: Born again neural networks. In: Proceedings of the International Conference on Machine Learning. pp. 1607–1616. PMLR (2018), http://proceedings.mlr.press/v80/furlanello18a.html
  * [9] Gao, R., Kleywegt, A.: Distributionally robust stochastic optimization with wasserstein distance. Mathematics of Operations Research (2022), https://doi.org/10.1287/moor.2022.1275
  * [10] Gou, J., Yu, B., Maybank, S.J., Tao, D.: Knowledge distillation: A survey. International Journal of Computer Vision 129(6), 1789–1819 (2021), https://doi.org/10.1007/s11263-021-01453-z
  * [11] Guo, J., Cai, Y., Fan, Y., Sun, F., Zhang, R., Cheng, X.: Semantic models for the first-stage retrieval: A comprehensive review. ACM Transactions on Information Systems (TOIS) 40(4), 1–42 (2022), https://doi.org/10.1145/3486250
  * [12] Hinton, G., Vinyals, O., Dean, J.: Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531 2(7) (2015), https://arxiv.org/abs/1503.02531
  * [13] Kingma, D.P., Welling, M.: Auto-encoding variational Bayes. In: Proceedings of the International Conference on Learning Representations (2014), https://arxiv.org/abs/1312.6114
  * [14] Krasnashchok, K., Jouili, S.: Improving topic quality by promoting named entities in topic modeling. In: Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers). pp. 247–253 (2018), https://aclanthology.org/P18-2040/
  * [15] Lau, J.H., Newman, D., Baldwin, T.: Machine reading tea leaves: Automatically evaluating topic coherence and topic model quality. In: Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics. pp. 530–539. Association for Computational Linguistics, Gothenburg, Sweden (Apr 2014), https://aclanthology.org/E14-1056
  * [16] Montavon, G., Müller, K.R., Cuturi, M.: Wasserstein training of restricted boltzmann machines. Advances in Neural Information Processing Systems 29 (2016), https://papers.nips.cc/paper/6248-wasserstein-training-of-restricted-boltzmann-machines
  * [17] Nityasya, M.N., Wibowo, H.A., Chevi, R., Prasojo, R.E., Aji, A.F.: Which student is best? a comprehensive knowledge distillation exam for task-specific BERT models. arXiv preprint arXiv:2201.00558 (2022), https://arxiv.org/abs/2201.00558
  * [18] Olkin, I., Pukelsheim, F.: The distance between two random vectors with given dispersion matrices. Linear Algebra and its Applications 48, 257–263 (1982), https://doi.org/10.1016/0024-3795(82)90112-4
  * [19] Ozair, S., Lynch, C., Bengio, Y., van den Oord, A., Levine, S., Sermanet, P.: Wasserstein dependency measure for representation learning. In: Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 32. Curran Associates, Inc. (2019), https://proceedings.neurips.cc/paper/2019/file/f9209b7866c9f69823201c1732cc8645-Paper.pdf
  * [20] Pan, S., Wu, J., Zhu, X., Zhang, C., Wang, Y.: Tri-party deep network representation. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. p. 1895–1901. IJCAI’16, AAAI Press (2016), https://www.ijcai.org/Proceedings/16/Papers/271.pdf
  * [21] Panaretos, V.M., Zemel, Y.: Statistical aspects of wasserstein distances. Annual Review of Statistics and its Application 6, 405–431 (2019), https://doi.org/10.1146/annurev-statistics-030718-104938
  * [22] Reimers, N., Gurevych, I., Reimers, N., Gurevych, I., Thakur, N., Reimers, N., Daxenberger, J., Gurevych, I., Reimers, N., Gurevych, I., et al.: Sentence-BERT: Sentence embeddings using siamese bert-networks. In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). pp. 3982–3992. Association for Computational Linguistics (2019), https://aclanthology.org/D19-1410
  * [23] Röder, M., Both, A., Hinneburg, A.: Exploring the space of topic coherence measures. In: Proceedings of the Eighth ACM International Conference on Web Search and Data Mining. pp. 399–408 (2015), https://doi.org/10.1145/2684822.2685324
  * [24] Srivastava, A., Sutton, C.: Autoencoding variational inference for topic models. In: International Conference on Learning Representations (2017), https://openreview.net/forum?id=BybtVK9lg
  * [25] Terragni, S., Fersini, E., Galuzzi, B.G., Tropeano, P., Candelieri, A.: OCTIS: Comparing and optimizing topic models is simple! In: Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: System Demonstrations. pp. 263–270 (2021), https://aclanthology.org/2021.eacl-demos.31/
  * [26] Vayansky, I., Kumar, S.A.: A review of topic modeling methods. Information Systems 94, 101582 (2020), https://doi.org/10.1016/j.is.2020.101582
  * [27] Villani, C.: Topics in optimal transportation, vol. 58. American Mathematical Soc. (2021), https://www.math.ucla.edu/~wgangbo/Cedric-Villani.pdf
  * [28] Zhai, C., Geigle, C.: A tutorial on probabilistic topic models for text data retrieval and analysis. In: The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval. pp. 1395–1398 (2018), https://doi.org/10.1145/3209978.3210189
  * [29] Zhang, L., Song, J., Gao, A., Chen, J., Bao, C., Ma, K.: Be your own teacher: Improve the performance of convolutional neural networks via self distillation. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 3713–3722 (2019), https://doi.ieeecomputersociety.org/10.1109/ICCV.2019.00381
  * [30] Zhang, Y., Jiang, T., Yang, T., Li, X., Wang, S.: HTKG: Deep keyphrase generation with neural hierarchical topic guidance. In: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. p. 1044–1054. SIGIR ’22, Association for Computing Machinery, New York, NY, USA (2022), https://doi.org/10.1145/3477495.3531990


# Scattering amplitude and its soft decomposition

Andriniaina Narindra Rasoanaivo  Sciences Expérimentales et des Mathématiques,
Ecole Normale Supérieure d’Antananarivo,
Complexe Scolaire Ampefiloha BP 881, Université d’Antananarivo, Madagascar
<EMAIL_ADDRESS>
###### Abstract

In the pure scattering theory, the universality of the soft limit has been
studied for a long time. In this talk we review the property of soft limit to
relate an $n$-point amplitude to an $(n-1)$-point amplitude. We show how this
property can be used to decompose amplitudes into different complementary soft
channel. The existence of such decomposition provides a new way to understand
how to construct amplitude solely from them soft limit.

##  1 Introduction

Many progress has been made to unravel the mathematical structure of
scattering amplitudes in gauge theories and gravity. These mathematical
structure are often hidden in the complexity of the traditional Feynman
diagram expansion computation. During the past few decades, the development of
modern techniques was so popular to make the different mathematical structure
of amplitudes manifests: Britto Cachazo Fen Witten (BCFW) recursion, MHV
rules, generalized unitarity cut, …The most popular among these approaches is
the BCFW recursion relations, they were developed allowing any tree level
helicity amplitude to be calculated using a simple on-shell recursion
relation. The on-shell recursion is used recursively to link higher points
amplitudes to the lower points, in which three points are the seeds of the
recursion [1]. Central to this construction have been unitarity, locality and
the Wigner’s little group which is the subgroup of the Lorentz group that
leaves a momentum invariant.

In this work, we will focus our attention on the factorization structure of
amplitudes in the case where one gluon is going soft, i.e. the energy of the
single gluon approaches zero. Such factorization is well understood from the
Weinberg’s theorem in which the physical properties of the low energy
contribution are factorized out from the main amplitudes [2, 3, 4]. The soft
contribution is known to be an operator acting on the lower point amplitude
emerges from the factorization such that

$A_{n}(p_{1},\ldots,p_{n})\xrightarrow{\quad p_{n}\to
0\quad}\hat{S}(p_{n})\times A_{n-1}(p_{1},\ldots,p_{n-1}),$ (1)

where $A_{n}$ is the main amplitude, $A_{n-1}$ is the emerged lower amplitude
and $\hat{S}(p_{n})$ is the soft operator associated to the soft particle of
momentum $p_{n}$.

This soft factorization is an universal property of amplitudes in which the
soft operator is proven to be computable directly from the asymptotic
symmetries of the associated soft particle [5, 6]. The main objective of this
work is to investigate the possibility of constructing any tree-level helicity
amplitude of gluons from them asymptotic symmetries by inverting the soft
factorization. Such approach is also known as the invert soft limit (ISL)
which is a well defined construction for super Young Mills theory [7], however
in [8] they showed that for the case of gluon amplitudes the inverse soft
limit construction constructed form BCFW recursion is only possible up to
7-points for any given helicity configuration.

We expect that if we understand the underline structure of amplitudes, which
makes the soft factorization manifest, we might able to reconstruct any given
amplitude from them asymptotic symmetries. To achieve that goal we will
present in this work how a given amplitude can be decomposed in two pieces
around one of its soft factorization; and we will use this decomposition to
show the possibility to compute higher point amplitude from them lower points
through inverse soft limits. In the section 2 we will give a short review on
Weinberg’s theorem and soft operators, then in section 3 we will present the
idea of soft decomposition of a given amplitude, and we will conclude this
work in section 4.

##  2 Weinberg’s theorem and the helicity soft operators

For simplicity, we will use spinor variables to describe Weinberg’s theorem.
It is important to mention that this choice of variables will not change our
description due to the universality of the theorem [2, 9]. Therefore, through
this work, we consider scattering amplitudes of gluons with external state
labeled by $i=\\{\lambda_{i}^{a},\bar{\lambda}_{i}^{\dot{a}}\\}$ and $h_{i}$.
The variables $\lambda$ and $\bar{\lambda}$ are respectively a left and a
right handed spinors such that
$p_{i}^{\mu}(\sigma_{\mu})^{a\dot{a}}=\lambda^{a}_{i}\bar{\lambda}^{\dot{a}}_{i}$,
and $h_{i}$ is the helicity of the $i$-th external state which is either equal
to $``+1"$ or $``-1"$, review on spinor variables [10, 11, 12]. With these
spinor variables, we can introduce two new invariant products

$\braket{ij}=\varepsilon_{ab}\lambda_{i}^{a}\lambda^{b}_{j}\quad\text{and}\quad[ij]=\varepsilon_{\dot{a}\dot{b}}\bar{\lambda}_{i}^{\dot{a}}\bar{\lambda}_{j}^{\dot{b}}\;,$
(2)

where $\varepsilon_{ab}$ and $\varepsilon_{\dot{a}\dot{b}}$ are the Kronecker
symbols contracted with the spinor variables.

The Weinberg’s soft theorem is an universal property of scattering amplitudes,
in which the soft contribution of the amplitude is factorize out from the high
energy contribution through the relation (1). The soft contribution, denoted
by $\hat{S}(p_{s})$, is known to be an operator acting on the hard
contribution the lower point amplitude emerged from the factorization. The
soft operator is know to be a composition of the terms: _the Weinberg soft
factor_ known as the leading term from the perturbative computation of
$\hat{S}$, and _a translation operator_ represented as $\hat{U}$ which shifts
the two adjacent momenta to the soft particle in the emergent lower point
amplitude

$\hat{S}(p_{s})=S^{(0)}(p_{s})\times\hat{U}(\delta_{i},\delta_{j}).$ (3)

In this equation, $i$ and $j$ are the labels of the momenta adjacent to the
soft particle of momentum $p_{s}$, and $\delta_{i}$ and $\delta_{j}$ are the
parameters of the translation such that $p_{i}\to p_{i}+\delta_{i}$ and
$p_{j}\to p_{j}+\delta_{j}$. Depending on the helicity $h_{s}$ of the soft
momenta the soft operator and the parameters of the shifts are given by [8]

  * $\bullet$

for $h_{s}=+1$ we have

$S^{(0)}(p_{s}^{+})=\frac{\braket{ij}}{\braket{is}\braket{sj}}\quad\text{and}\quad\left\\{\begin{aligned}
\delta_{i}=\frac{\braket{js}}{\braket{ji}}\lambda_{i}\bar{\lambda}_{s}\\\
\delta_{j}=\frac{\braket{is}}{\braket{ij}}\lambda_{j}\bar{\lambda}_{s}\end{aligned}\right.$
(4)

  * $\bullet$

for $h_{s}=-1$ we have

$S^{(0)}(p_{s}^{-})=\frac{[ij]}{[is][sj]}\quad\text{and}\quad\left\\{\begin{aligned}
\delta_{i}=\frac{[js]}{[ji]}\lambda_{s}\bar{\lambda}_{i}\\\
\delta_{j}=\frac{[is]}{[ij]}\lambda_{s}\bar{\lambda}_{j}\end{aligned}\right.$
(5)

here the momenta $p_{i}$, $p_{j}$ and $p_{s}$ are represented by them
respective spinor variables $\lambda_{i}\bar{\lambda}_{i}$,
$\lambda_{j}\bar{\lambda}_{j}$ and $\lambda_{s}\bar{\lambda}_{s}$. The
Weinberg soft theorem is therefore a map from higher point amplitude to a
lower points by factorizing the associated soft operator through the relation
(1). From the description of the soft operator, applying the soft operator
$\hat{S}$ on a lower point amplitude seems to invert the factorization and
leads to the higher points which is not the case as we will discus in the
following section.

##  3 Soft decomposition

###  3.1 Soft structure of amplitudes

In order to introduce the idea of soft decomposition of an amplitude, let us
consider the six-point helicity amplitude of gluons in (6). With the six-point
amplitude, we are going to investigate what happen when we perform the
following limits: first we take one of the particle soft then, as a second
step, we inverse the soft limit as in [8] using the soft operators defined
from the previews section.

The derivation of the six-point gluon amplitude can be found in [1] which is
given by

$A_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})=\frac{1}{[2|3+4|5\rangle}\left(\frac{[4|5+6|1\rangle^{3}}{[34][23]\braket{56}\braket{61}S_{234}}+\frac{[6|1+2|3\rangle^{3}}{[61][12]\braket{34}\braket{45}S_{612}}\right),$
(6)

where the other invariant quantities $S_{ijk}$ and $[i|j+k|l\rangle$ are
defined as

$S_{ijk}=(p_{i}+p_{j}+p_{k})^{2}\quad\text{and}\quad[i|j+k|l\rangle=[ij]\braket{jl}+[ik]\braket{kl}.$
(7)

In this configuration of helicity, we can take any of six momenta to be soft.
In our case, let us focus on the sixth momentum with which we will
successively perform a soft then then an inverse soft limits. We know that
taking a soft limit will factorize the soft behavior from the high energy
regime, this is nothing than a map from the six-point to a five point
amplitude

$A_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})\xrightarrow{\quad\text{soft
}S(6^{+})\quad}A_{5}(1^{-},2^{-},3^{-},4^{+},5^{+}).$ (8)

The $A_{5}(1^{-},2^{-},3^{-},4^{+},5^{+})$ is known to be a MHV amplitude and
its expression is given by the Park-Taylor formula [10]. In the expression
(6), when we take sixth particle to go soft and as the momentum $p_{6}$ goes
to zero, the second term tend to zero while the first term tend to factorize
as Weinberg described in the theorem, i.e. only the first part contributes in
the soft factorization of the sixth particle.

Now we can invert the soft limit on the five-point amplitude in which we act
the soft operator defined in (3) on the amplitude
$A_{5}(1^{-},2^{-},3^{-},4^{+},5^{+})$. That means we multiply the amplitude
with the Weinberg soft factor $S^{(0)}(6^{+})$ and shifts the momenta $p_{5}$
and $p_{1}$ according to the relation (4)

$A_{5}(1^{-},2^{-},3^{-},4^{+},5^{+})\xrightarrow{\quad\text{inverse soft
}S(6^{+})\quad}\frac{1}{[2|3+4|5\rangle}\times\frac{[4|5+6|1\rangle^{3}}{[34][23]\braket{56}\braket{61}S_{234}}.$
(9)

This above relation shows that the inverse soft limit of the sixth particle
doesn’t give us the original amplitude, however it only gives the first term
in the expression of six-point amplitude back. The information on the term
that tend to zero in soft limit was lost, and it can not be restored by
inverting the soft limit. So viewed from the soft/inverse soft limit of the
sixth particle the amplitude can be decomposed as follow

$A_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})=A_{6}^{[6]}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})+R_{6}^{[6]}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+}).$
(10)

The $A_{6}^{[6]}$ is the central piece of the amplitude from the sixth
particle’s soft limit, and $R_{6}^{[6]}$ is the negligible term that tends to
zero as the six goes soft,

$\left\\{\begin{aligned}
&A_{6}^{[6]}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})\xrightarrow{\quad\text{soft
}S(6^{+})\quad}A_{5}(1^{-},2^{-},3^{-},4^{+},5^{+}),\\\
&R_{6}^{[6]}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})\xrightarrow{\quad\text{soft
}S(6^{+})\quad}0.\end{aligned}\right.$ (11)

Similar decomposition can be done with any of the momentum in amplitude. In a
most general case, viewed from the softness of any $i$-th particle of a given
$n$-point amplitude, the amplitude can be decomposed as

$A_{n}(1,2,\ldots,n)=A^{[i]}_{n}(1,2,\ldots,n)+R^{[i]}_{n}(1,2,\ldots,n),$
(12)

where

  * $\bullet$

$A_{n}^{[i]}$ is the core of the soft theorem: which is central to the soft
theorem as the $i$-th particle get soft that contains the IR behavior of the
soft limit,

  * $\bullet$

and $R_{n}^{[i]}$ is the soft shell of the amplitude: which is the part of the
amplitude that is lost in the soft limit of the $i$-th particle.

This decomposition is similar to the decomposition presented in [13] but the
reconstruction in the following section differs from them soft reconstruction
of amplitudes.

###  3.2 Soft reconstruction of amplitudes

The soft decomposition (12) is not an unique decomposition, in fact for a
given $n$-point amplitude there are $n$ different decomposition respectively
to the $n$ particles. The soft decomposition also make the soft limit of a
given particle manifests in which the soft shell $R_{n}^{[i]}$ will not
contribute in the universal factorization of the amplitude. Since the core of
the soft theorem $A_{n}^{[i]}$ is the only part that can be constructed form
inverse soft limit, it is necessary to find an algorithm to reconstruct the
soft shell. The study of the six-point amplitude (6) can point us to the right
direction for reconstruct $R_{n}^{[i]}$, for that we computed all the six
different decomposition of the amplitude and found that the soft shell from
one decomposition can be found in the central core of the other decomposition.

In order to see how this works, here are the six decomposition of the six-
point amplitude

$\displaystyle A_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})$
$\displaystyle=A^{[1]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})+R^{[1]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})$
(13)
$\displaystyle=A^{[2]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})+R^{[2]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})$
$\displaystyle=A^{[3]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})+R^{[3]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})$
$\displaystyle=A^{[4]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})+R^{[4]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})$
$\displaystyle=A^{[5]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})+R^{[5]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})$
$\displaystyle=A^{[6]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})+R^{[6]}_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})$

in which we have the following expressions

$\left\\{\begin{aligned}
&A_{6}^{[1]}=A_{6}^{[4]}=R_{6}^{[3]}=R_{6}^{[6]}=\frac{1}{[2|3+4|5\rangle}\left(\frac{[6|1+2|3\rangle^{3}}{[61][12]\braket{34}\braket{45}S_{612}}\right),\\\
&A_{6}^{[3]}=A_{6}^{[6]}=R_{6}^{[1]}=R_{6}^{[4]}=\frac{1}{[2|3+4|5\rangle}\left(\frac{[4|5+6|1\rangle^{3}}{[34][23]\braket{56}\braket{61}S_{234}}\right),\\\
&A_{6}^{[2]}=A_{6}^{[5]}=\frac{1}{[1|5+6|4\rangle}\times\frac{1}{[3|1+2|6\rangle}\times\frac{S_{123}^{3}}{[12][23]\braket{45}\braket{56}}.\end{aligned}\right.$
(14)

The results from the different decomposition show that the six-point amplitude
(6) can be reconstructed from the composition of inverse soft limit, since the
central core of the soft limit of one particle turns out to be the soft shell
the others. Our six-point amplitude can be reconstructed from the combination
of two inverse soft limits of two different five-points

$A_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})=S(6^{+})A_{5}(1^{-},2^{-},3^{-},4^{+},5^{+})+S(1^{-})A_{5}(2^{-},3^{-},4^{+},5^{+},6^{+}).$
(15)

This reconstruction of the amplitude (6) can be represented in a
diagrammatically as shown in Figure 1. The investigation of the such
reconstruction have been made for different size of amplitudes and for
different helicity configurations. We found that the soft decomposition of MHV
amplitudes, helicity configurations with only two negative helicities [14],
doesn’t have a soft shell which means they can be directly constructed from
one single inverse soft limit of a lower point MHV. For higher point
amplitudes, say $n$-points, the investigation of the different soft
decomposition allows us to understand that the amplitude can be reconstructed
from $(n-1)$-point amplitudes with at most “three” linear combination of
inverse soft limits.

In Figure 2, we can see that the typical 7-point amplitude with the helicity
configuration $(1^{-},2^{-},3^{+},4^{-},5^{+},6^{+},7^{+})$ can be
reconstructed from the combination of three inverse soft limits of
$A_{6}(1^{-},2^{-},4^{-},5^{+},6^{+},7^{+})$,
$A_{6}(1^{-},3^{+},4^{-},5^{+},6^{+},7^{+})$, and
$A_{6}(1^{-},2^{-},3^{+},5^{+},6^{+},7^{+})$. And in the same diagram we can
also see that the $A_{6}(1^{-},2^{-},4^{-},5^{+},6^{+},7^{+})$ can be
reconstructed from the combination of two inverse soft limits of
$A_{5}(1^{-},2^{-},5^{+},6^{+},7^{+})$ and
$A_{5}(1^{-},2^{-},4^{-},6^{+},7^{+})$.

$A_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})$$A_{5}(1^{-},2^{-},3^{-},4^{+},5^{+})$$A_{5}(2^{-},3^{-},4^{+},5^{+},6^{+})$$S(6^{+})$$S(1^{-})$
Figure 1: Representation of the soft reconstruction of
$A_{6}(1^{-},2^{-},3^{-},4^{+},5^{+},6^{+})$
$A_{7}(1^{-},2^{-},3^{+},4^{-},5^{+},6^{+},7^{+})$$A_{6}(1^{-},2^{-},4^{-},5^{+},6^{+},7^{+})$$A_{5}(1^{-},2^{-},5^{+},6^{+},7^{+})$$A_{5}(1^{-},2^{-},4^{-},6^{+},7^{+})$$A_{6}(1^{-},3^{+},4^{-},5^{+},6^{+},7^{+})$$A_{6}(1^{-},2^{-},3^{+},5^{+},6^{+},7^{+})$$S(3^{+})$$S(4^{-})$$S({5}^{+})$$S({2}^{-})$$S({4}^{-})$
Figure 2: Representation of the soft reconstruction of
$A_{7}(1^{-},2^{-},3^{+},4^{-},5^{+},6^{+},7^{+})$

##  4 Conclusion

In this work we would like to review the possibility to compute scattering
amplitudes from them asymptotic symmetries. For that purpose we investigate
the soft structure of amplitude, we called soft decomposition. We choose the
six-point amplitude (6) as our toy subject, in which we took the soft limit of
particle and invert the limit using the inverse soft limit process. Depending
on the helicity of the soft particle, the inverse limit consist to multiply
the lower-point amplitude with the respective helicity soft factor, and to
shift the two neighbor momenta of the soft inverted particle.

The process of the taking a particle soft then inverting the limit shows that
amplitude can be decomposed as a combination of the central core of the soft
limit, which is can be reconstructed directly from inverse soft, and a soft
shell a piece that tend to zero as the particle goes soft (12). Therefore, to
construct an amplitude from inverse soft limit we need to find a way to
compute the soft shell in the decomposition. In the investigation of the
different decomposition of the amplitude, we also found that the soft shell of
a given sodt decomposition is a linear combination of the different soft core
of the different soft decomposition as show in Figure 1 and Figure 2. From
these results we found the importance of the soft cores of the different soft
decomposition of a given amplitude in its soft construction, an amplitudes is
a linear combination of its soft cores. Our next step is now to find the right
algorithm that combine the different soft decomposition in the inverse soft
limit construction of amplitudes.

## References

## References

  * [1] R. Britto, F. Cachazo and B. Feng, _“New recursion relations for tree amplitudes of gluons,”_ Nucl. Phys. B 715, 499-522 (2005) doi:10.1016/j.nuclphysb.2005.02.030 [arXiv:hep-th/0412308 [hep-th]].
  * [2] S. Weinberg, _“Infrared photons and gravitons,”_ Phys. Rev. 140, B516-B524 (1965) doi:10.1103/PhysRev.140.B516
  * [3] H. Elvang, C. R. T. Jones and S. G. Naculich, _“Soft Photon and Graviton Theorems in Effective Field Theory,”_ Phys. Rev. Lett. 118, no.23, 231601 (2017) doi:10.1103/PhysRevLett.118.231601 .
  * [4] R. Jackiw, _“Low-Energy Theorems for Massless Bosons: Photons and Gravitons,”_ Phys. Rev. 168, 1623-1633 (1968) doi:10.1103/PhysRev.168.1623
  * [5] A. N. Rasoanaivo, _“Helicity Constraints To Soft Factor Of All Spin,”_ [arXiv:2002.02120 [hep-th]].
  * [6] A. Campoleoni, D. Francia and C. Heissenberg, _“On higher-spin supertranslations and superrotations,”_ JHEP 05, 120 (2017) doi:10.1007/JHEP05(2017)120 [arXiv:1703.01351 [hep-th]].
  * [7] D. Nandan and C. Wen, _“Generating All Tree Amplitudes in N=4 SYM by Inverse Soft Limit,”_ JHEP 08, 040 (2012) doi:10.1007/JHEP08(2012)040 [arXiv:1204.4841 [hep-th]].
  * [8] C. Boucher-Veronneau and A. J. Larkoski, _“Constructing Amplitudes from Their Soft Limits,”_ JHEP 09, 130 (2011) doi:10.1007/JHEP09(2011)130 [arXiv:1108.5385 [hep-th]].
  * [9] S. Higuchi and H. Kawai, _“Universality of soft theorem from locality of soft vertex operators,”_ Nucl. Phys. B 936, 400-447 (2018) doi:10.1016/j.nuclphysb.2018.09.024 [arXiv:1805.11079 [hep-th]].
  * [10] C. Cheung, _“TASI Lectures on Scattering Amplitudes,”_ doi:10.1142/9789813233348_0008 [arXiv:1708.03872 [hep-ph]].
  * [11] R. Britto, F. Cachazo, B. Feng and E. Witten, _“Direct proof of tree-level recursion relation in Yang-Mills theory,”_ Phys. Rev. Lett. 94, 181602 (2005) doi:10.1103/PhysRevLett.94.181602 .
  * [12] N. Arkani-Hamed, T. C. Huang and Y. t. Huang, _“Scattering amplitudes for all masses and spins,”_ JHEP 11, 070 (2021) doi:10.1007/JHEP11(2021)070 [arXiv:1709.04891 [hep-th]].
  * [13] L. Rodina, _“Scattering Amplitudes from Soft Theorems and Infrared Behavior,”_ Phys. Rev. Lett. 122, no.7, 071601 (2019) doi:10.1103/PhysRevLett.122.071601 [arXiv:1807.09738 [hep-th]].
  * [14] S. J. Parke and T. R. Taylor, _“An Amplitude for $n$ Gluon Scattering,”_ Phys. Rev. Lett. 56, 2459 (1986) doi:10.1103/PhysRevLett.56.2459