# Group Equivariant Subsampling

Jin Xu1 Hyunjik Kim2 Tom Rainforth1 Yee Whye Teh1,2

1 Department of Statistics, University of Oxford, UK.
2 DeepMind, UK.  Corresponding author<EMAIL_ADDRESS>
###### Abstract

Subsampling is used in convolutional neural networks (CNNs) in the form of
pooling or strided convolutions, to reduce the spatial dimensions of feature
maps and to allow the receptive fields to grow exponentially with depth.
However, it is known that such subsampling operations are not translation
equivariant, unlike convolutions that _are_ translation equivariant. Here, we
first introduce translation equivariant subsampling/upsampling layers that can
be used to construct exact translation equivariant CNNs. We then generalise
these layers beyond translations to general groups, thus proposing group
equivariant subsampling/upsampling. We use these layers to construct group
equivariant autoencoders (GAEs) that allow us to learn low-dimensional
equivariant representations. We empirically verify on images that the
representations are indeed equivariant to input translations and rotations,
and thus generalise well to unseen positions and orientations. We further use
GAEs in models that learn object-centric representations on multi-object
datasets, and show improved data efficiency and decomposition compared to non-
equivariant baselines.

##  1 Introduction

Convolutional Neural Networks (CNNs) are known to be more data efficient and
show better generalisation on perceptual tasks than fully-connected networks,
due to translation equivariance encoded in the convolutions: when the input
image/feature map is translated, the output feature map also translates by the
same amount. In typical CNNs, convolutions are used in conjunction with
subsampling operations, in the form of pooling or strided convolutions, to
reduce the spatial dimensions of feature maps and to allow receptive field to
grow exponentially with depth. Subsampling/upsampling operations are
especially necessary for convolutional autoencoders (ConvAEs) [34] because
they allow efficient dimensionality reduction. However, it is known that
subsampling operations implicit in strided convolutions or pooling layers are
not translation equivariant [51], hence CNNs that use these components are
also not translation invariant. Therefore such CNNs and ConvAEs are not
guaranteed to generalise to arbitrarily translated inputs despite their
convolutional layers being translation equivariant.

Previous work, such as [51, 3], has investigated how to enforce translation
invariance on CNNs, but does not study equivariance with respect to symmetries
beyond translations, such as rotations or reflections. In this work, we first
describe subsampling/upsampling operations that preserve exact translation
equivariance. The main idea is to sample feature maps on an input-dependent
grid rather than a fixed one as in pooling or strided convolutions, and the
grid is chosen according to a sampling index computed from the inputs (see
Figure 1). Simply replacing the subsampling/upsampling in standard CNNs with
such translation equivariant subsampling/upsampling operations leads to CNNs
and transposed CNNs that can map between spatial inputs and low-dimensional
representations in a translation equivariant manner.

We further generalise the proposed subsampling/upsampling operations from
translations to arbitrary groups, proposing group equivariant
subsampling/upsampling. In particular we identify subsampling as mapping
features on groups $G$ to features on subgroups $K$ (vice versa for
upsampling), and identify the sampling index as a coset in the quotient space
$G/K$. See Appendix A for a primer on group theory that is needed to describe
this generalisation. We note that group equivariant subsampling is different
to coset pooling introduced in [5], which instead gives features on the
quotient space $G/K$, and discuss differences in detail in Section 4. Similar
to the translation equivariant subsampling/upsampling, group equivariant
subsampling/upsampling can be used with group equivariant convolutions to
produce group equivariant CNNs. Using such group equvariant CNNs we can
construct group equivariant autoencoders (GAEs) that separate representations
into an invariant part and an equivariant part.

While there is a growing body of literature on group equivariant CNNs (G-CNNs)
[5, 10, 48, 47, 46, 41, 44], such equivariant convolutions usually preserve
the spatial dimensions of the inputs (or lift them to even higher dimensions)
until the final invariant pooling layer. There is a lack of exploration on how
to reduce the spatial dimensions of such feature maps while preserving exact
equivariance, to produce low-dimensional equivariant representations. This
work attempts to fill in this gap. Such low-dimensional equivariant
representations can be employed in representation learning methods, allowing
various advantages such as interpretability, out-of-distribution
generalisation, and better sample complexity. When using such learned
representations in downstream tasks such as abstract reasoning, reinforcement
learning, video modelling, scene understanding, it is especially important for
representations to be equivariant rather than invariant in these tasks,
because transformations and how they act on feature spaces are critical
information, rather than nuisance as in image classification problems.

Figure 1: Equivariant subsampling on 1D feature maps with a scale factor
$c=2$. The input feature map has length $8$, and initially we sample from odd
positions determined by Equation 1 (top). When the original feature map is
shifted to the right by $1$ unit (bottom left), the sampling index becomes
$1$, so we instead sample from even positions. When the feature map is shifted
to the right by $2$ units (bottom right), we again sample from odd positions,
but the outputs have been shifted to the right by $1$ unit correspondingly.

In summary, we make the following contributions:  (i) We propose
subsampling/upsampling operations that preserve translational equivariance.
(ii) We generalise the proposed subsampling/upsampling operations to arbitrary
symmetry groups.  (iii) We use equivariant subsampling/upsampling operations
to construct GAEs that gives low-dimensional equivariant representations.
(iv) We empirically show that representations learned by GAEs enjoys many
advantages such as interpretability, out-of-distribution generalisation, and
better sample complexity.

##  2 Equivariant Subsampling and Upsampling

###  2.1 Translation Equivariant Subsampling for CNNs

In this section we describe the proposed translation equivariant subsampling
scheme for feature maps in standard CNNs. Later in Section 2.2, we describe
how this can be generalised to group equivariant subsampling for feature maps
on arbitrary groups.

#### Standard subsampling

Feature maps in CNNs can be seen as functions defined on the integer grid,
e.g. $\mathbb{Z}$ for 1D feature maps, and $\mathbb{Z}^{2}$ for 2D. Hence we
represent feature maps as $f:\mathbb{Z}\rightarrow R^{d}$, where $d$ is the
number of feature map channels. For simplicity, we start with 1D and move on
to the 2D case. Typically, subsampling in CNNs is implemented as either
strided convolution or (max) pooling, and they can be decomposed as

$\displaystyle\operatorname{\textsc{conv}}_{k}^{c}$
$\displaystyle=\operatorname{\textsc{subsampling}}^{c}\circ\operatorname{\textsc{conv}}_{k}^{1}$
$\displaystyle\operatorname{\textsc{maxpool}}_{k}^{c}$
$\displaystyle=\operatorname{\textsc{subsampling}}^{c}\circ\operatorname{\textsc{maxpool}}_{k}^{1}$

where subscripts denote kernel sizes and superscripts indicate strides.
$c\in\mathbb{N}$ is the scale factor for
$\operatorname{\textsc{subsampling}}$, and this operation simply restricts the
input domain of the feature map from $\mathbb{Z}$ to $c\mathbb{Z}$, without
changing the corresponding function values.

#### Translation equivariant subsampling

In our equivariant subsampling scheme, we instead restrict the input domain to
$c\mathbb{Z}+i$, the integers $\equiv i\mod c$, where $i$ is a sampling index
determined by the input feature map. The key idea is to choose $i$ such that
it is shifts by $t(\bmod c)$ when the input is translated by $t$, to ensure
that the same features are subsampled upon translation. Let $i$ be given by
the mapping
$\Phi_{c}:\mathcal{I}_{\mathbb{Z}}\rightarrow\mathbb{Z}/c\mathbb{Z}$.
$\mathcal{I}_{\mathbb{Z}}$ denotes the space of vector functions on
$\mathbb{Z}$ and $\mathbb{Z}/c\mathbb{Z}$ is the space of remainders upon
division by $c$.

$\displaystyle i=\Phi_{c}(f)=\bmod(\arg\max_{x\in\mathbb{Z}}\|f(x)\|_{1},c)$
(1)

where $\|\cdot\|_{1}$ denotes $L^{1}$-norm (other choices of norm are equally
valid). Other choices for $\Phi_{c}$ are equally valid as long as they satisfy
translation equivariance, ensuring that the same features are subsampled upon
translation of the input:

$\displaystyle\Phi_{c}(f(\cdot-t))=\bmod(\Phi_{c}(f)+t,c).$ (2)

Note that this holds for Equation 1 provided the argmax is unique, which we
assume for now (see Section B.1 for a discussion of the non-unique case). We
can decompose the subsampled feature map defined on $c\mathbb{Z}+i$ into its
values and the offset index $i$, expressing it as
$[f_{b},i]\in(\mathcal{I}_{c\mathbb{Z}},\mathbb{Z}/c\mathbb{Z})$, where
$f_{b}$ is the translated output feature map such that $f_{b}(cx)=f(cx+i)$ for
$x\in\mathbb{Z}$.

The subsampling operation described above, which maps from
$\mathcal{I}_{\mathbb{Z}}$ to
$(\mathcal{I}_{c\mathbb{Z}},\mathbb{Z}/c\mathbb{Z})$ is translation
equivariant: when the feature map $f$ is translated to the right by
$t\in\mathbb{Z}$, one can verify that $f_{b}$ will be translated to the right
by $c\lfloor\frac{i+t}{c}\rfloor$, and the sampling index for the translated
inputs would become $\bmod(i+t,c)$. We provide an illustration for $c=2$ in
Figure 1, and describe formal statements and proofs later for the general
cases in Section 2.2.

#### Multi-layer case

For the subsequent layers, the feature map $f_{b}$ is fed into the next
convolution, and the sampling index $i$ is appended to a list of outputs. When
the above translation equivariant subsampling scheme is interleaved with
convolutions in this way, we obtain an exactly translation equivariant CNN,
where each subsampling layer with scale factor $c_{k}$ produces a sampling
index $i_{k}\in\mathbb{Z}/c_{k}\mathbb{Z}$. Hence the equivariant
representation output by the CNN with $L$ subsampling layers is a final
feature map $f_{L}$ and a $L$-tuple of sampling indices
$(i_{1},\ldots,i_{L})$. This tuple can in fact be expressed equivalently as a
single integer by treating the tuple as mixed radix notation and converting to
decimal notation. We provide details of this multi-layer case in Section B.2,
including a rigorous formulation and its equivariance properties.

#### Translation equivariant upsampling

As a counterpart to subsampling, upsampling operations increase the spatial
dimensions of feature maps. We propose an equivariant upsampling operation
that takes in a feature map $f\in\mathcal{I}_{c\mathbb{Z}}$ and a sampling
index $i\in\mathbb{Z}/c\mathbb{Z}$, and outputs a feature map
$f_{u}\in\mathcal{I}_{\mathbb{Z}}$, where we set $f_{u}(cx+i)=f(cx)$ and
$\bm{0}$ everywhere else. This works well enough in practice, although in
conventional upsampling the output feature map is often a smooth interpolation
of the input feature map. To achieve this with equivariant upsampling, we can
additionally apply average pooling with stride $1$ and kernel size $>1$.

#### 2D Translation equivariant subsampling

When feature maps are $2D$, they can be represented as functions on
$\mathbb{Z}^{2}$. The sampling index becomes a $2$-element tuple given by:

$\displaystyle(x^{\ast},y^{\ast})$
$\displaystyle={\arg\max}_{(x,y)\in\mathbb{Z}^{2}}\|f(x)\|_{1}$
$\displaystyle(i,j)$ $\displaystyle=(\bmod(x^{\ast},c),\bmod(y^{\ast},c))$

and we subsample feature maps by restricting the input domain to
$c\mathbb{Z}^{2}+(i,j)$. The multi-layer construction and upsampling is
analogous to the 1D-case.

###  2.2 Group Equivariant Subsampling and Upsampling

In this section, we propose group equivariant subsampling by starting off with
the 1D-translation case in Section 2.1, and provide intuition for how each
component of this special case generalises to arbitrary discrete groups $G$.
We then proceed to mathematically formulate group equivariant subsampling, and
prove that it is indeed $G$-equivariant.

#### Feature maps on groups

First recall that the feature maps for the 1D-translation case were defined as
functions on $\mathbb{Z}$, or $f\in\mathcal{I}_{\mathbb{Z}}$ for short. To
extend this to the general case, we consider feature maps $f$ as functions on
a group $G$, i.e. $f\in\mathcal{I}_{G}=\\{f:G\to V\\}$111This is not to be
confused with the space of Mackey functions in, e.g., [9], and rather it is
the space of unconstrained functions on $G$. where $V$ is a vector space, as
is done in e.g. group equivariant CNNs (G-CNNs) [5]. Note that translating
feature maps $f$ on $\mathbb{Z}$ by displacement $u$ is effectively defining a
new feature map $f^{\prime}(\cdot)=f(\cdot-u)$. In the general case, we say
that the group action on the feature space is given by

$\displaystyle[\pi(u)f](g)=f(u^{-1}g)$ (3)

where $\pi$ is a group representation describing how $u\in G$ acts on the
feature space.

#### Recap: translation equivariant subsampling

Recall that standard subsampling that occurs in pooling or strided
convolutions for 1D translations amounts to restricting the domain of the
feature map from $\mathbb{Z}$ to $c\mathbb{Z}$, whereas equivariant
subsampling also produces a sampling index $i\in\mathbb{Z}/c\mathbb{Z}$, an
integer mod $c$, and that this is equivalent to restricting the input domain
to $c\mathbb{Z}+i$. $i$ is given by the translation equivariant mapping
$\Phi_{c}:\mathcal{I}_{\mathbb{Z}}\rightarrow\mathbb{Z}/c\mathbb{Z}$. We can
translate the input domain back to $c\mathbb{Z}$, and represent the output of
subsampling as
$[f_{b},i]\in(\mathcal{I}_{c\mathbb{Z}},\mathbb{Z}/c\mathbb{Z})$, where
$f_{b}$ is the translated output feature map and $f_{b}(cx)=f(cx+i)$ for
$x\in\mathbb{Z}$.

#### Group equivariant subsampling

Similarly in the general case, for a feature map $f\in\mathcal{I}_{G}$,
standard subsampling can be seen as restricting the domain from the group $G$
to a subgroup $K$, whereas equivariant subsampling additionally produces a
sampling index $pK\in G/K$, where the quotient space $G/K=\\{gK:g\in G\\}$ is
the set of (left) cosets of $K$ in $G$. Note that we have rewritten $i$ as $p$
to distinguish between the 1D translation case and the general group case.
This is equivalent to restricting the $f$ to the coset $pK$. The choice of the
coset $pK$ is given by equivariant map $\Phi:\mathcal{I}_{G}\rightarrow G/K$
(the action of $G$ on $G/K$ is given by $u(gK)=(ug)K$ for $u,g\in G$), such
that $pK=\Phi(f)$. This restriction of $f$ to $pK$ can also be thought of as
having an output feature map $f_{b}$ on $K$ and choosing a coset
representative element $\bar{p}\in pK$, such that $f_{b}(k)=f(\bar{p}k)$. This
choice of coset representative is described by a function $s:G/K\to G$, such
that $\bar{p}=s(pK)$. The function $s$ is called a section and should satisfy
$s(pK)K=pK$.

Now let us formulate subsampling and upsampling operations
$S_{b}{\downarrow}_{K}^{G}$ and $S_{u}{\uparrow}_{K}^{G}$ mathematically and
prove its $G$-equivariance. Let $\mathcal{I}_{K}=\\{f:K\to V^{\prime}\\}$ be
the space of feature map on $K$. $S_{b}{\downarrow}_{K}^{G}$ takes in a
feature map $f\in\mathcal{I}_{G}$ and produces a feature map
$f_{b}\in\mathcal{I}_{K}$ and a coset in $G/K$. In reverse, the upsampling
operation $S_{u}{\uparrow}_{K}^{G}$ takes in a feature map in
$\mathcal{I}_{K}$, a coset in $G/K$, and produces a feature map in
$\mathcal{I}_{G}$. We use a section $s:G/K\rightarrow G$ to represent a coset
with a representative element in $G$, and point out that equivariance holds
for any choice of $s$.

Formally, given an equivariant map $\Phi:\mathcal{I}_{G}\rightarrow G/K$ (we
will discuss how to construct such a map in Section 2.3), and a fixed section
$s:G/K\rightarrow G$ such that $\bar{p}=s(pK)$, the subsampling operation
$S_{b}{\downarrow}_{K}^{G}:\mathcal{I}_{G}\rightarrow\mathcal{I}_{K}\times
G/K$ is defined as:

$\displaystyle pK$ $\displaystyle=\Phi(f),\hskip
8.53581ptf_{b}(k)=f(\bar{p}k)\;\text{for}\;k\in K$ $\displaystyle[f_{b},pK]$
$\displaystyle=S_{b}{\downarrow}_{K}^{G}(f;\Phi),$ (4)

while the upsampling operation $S_{u}{\uparrow}_{K}^{G}:\mathcal{I}_{K}\times
G/K\rightarrow\mathcal{I}_{G}$ is defined as:

$\displaystyle f_{u}(g)$ $\displaystyle=f(\bar{p}^{-1}g)\text{\;if\;}g\in
K\text{\;else\;}\bm{0}$ $\displaystyle f_{u}$
$\displaystyle=S_{u}{\uparrow}_{K}^{G}(f,pK).$ (5)

To make the output of the upsampling dense rather than sparse, one can apply
arbitrary equivariant smoothing functions such as average pooling with stride
$1$ and kernel size $>1$, to compensate for the fact that we extend with
$\bm{0}$s rather than values close to their neighbours. In practice, we
observe that upsampling without any smoothing function works well enough.

The statement on the equivariance of $S_{b}{\downarrow}_{K}^{G}$ and
$S_{u}{\uparrow}_{K}^{G}$ requires we specify the action of $G$ on the space
$\mathcal{I}_{K}\times G/K$, which we denote as $\pi^{\prime}$. For any $u\in
G$,

$\displaystyle p^{\prime}K$ $\displaystyle=upK,\hskip
8.53581ptf^{\prime}_{b}=\pi(\bar{p}^{\prime-1}u\bar{p})f_{b}$
$\displaystyle[f^{\prime}_{b},\;p^{\prime}K]$
$\displaystyle=\pi^{\prime}(u)[f_{b},\;pK]$ (6)

######  Lemma 2.1.

$\pi^{\prime}$ defines a valid group action of $G$ on the space
$\mathcal{I}_{K}\times G/K$.

We can now state the following equivariance property (See Appendix D for a
proof):

######  Proposition 2.2.

If the action of group $G$ on the space $\mathcal{I}_{G}$ and
$\mathcal{I}_{K}\times G/K$ are specified by $\pi,\pi^{\prime}$ (as defined in
Equations 3 and 2.2), and $\Phi:\mathcal{I}_{G}\rightarrow G/K$ is an
equivariant map, then the operations $S_{b}{\downarrow}_{K}^{G}$ and
$S_{u}{\uparrow}_{K}^{G}$ as defined in Sections 2.2 and 2.2 are equivariant
maps between $\mathcal{I}_{G}$ and $\mathcal{I}_{K}\times G/K$.

###  2.3 Constructing $\Phi$

We use the following simple construction of the equivariant mapping
$\Phi:\mathcal{I}_{G}\to G/K$ for subsampling/upsampling operations, although
any equivariant mapping would suffice. For an input feature map
$f\in\mathcal{I}_{G}$, we define

$\displaystyle pK=\Phi(f)\coloneqq(\arg\max_{g\in G}\|f(g)\|_{1})K$ (7)

Provided that the argmax is unique, it is easy to show that $(up)\cdot
K=\Phi(\pi(u)f)$, hence $\Phi$ is equivariant. In practice one can insert
arbitrary equivariant layers to $f$ before and after we take the norm
$\|\cdot\|_{1}$ to avoid a non-unique argmax (see Appendix E).

In theory, there could exist cases where the argmax is always non-unique. We
provide a more complex construction of $\Phi$ that deals with this case in
Section B.1.

##  3 Application: Group Equivariant Autoencoders

Group equivariant autoencoders (GAEs) are composed of alternating
G-convolutional layers and equivariant subsampling/upsampling operations for
the encoder/decoder. One important property of GAEs is that the final
subsampling layer of the encoder subsamples to a feature map defined on the
trivial group $\\{e\\}$, outputting a vector (instead of a feature map) that
is invariant. For the 1D-translation case, suppose the input to the final
subsampling layer is a feature map $f$ defined on $\mathbb{Z}$. Then the final
layer produces an invariant vector $f_{b}(0)=f(i_{L})$ where
$i_{L}=\arg\max_{x\in\mathbb{Z}}\|f(x)\|_{1}$. Note that there is no scale
factor $c_{L}$ here. Intuitively we can think of this as setting the scale
factor $c_{L}=\infty$. Hence the encoder of the GAE outputs a representation
that is disentangled into an invariant part $z_{\text{inv}}=f_{b}(0)$ (the
vector output by the final subsampling layer) and an equivariant part
$z_{\text{eq}}=(i_{1},...,i_{L})$.

For the general group case, instead of specifying scale factors as in Section
2.1, we specify a sequence of nested subgroups $G=G_{0}\geq G_{1}\geq\dots\geq
G_{L}=\\{e\\}$, where the feature map for layer $l$ is defined on subgroup
$G_{L}$. For example, for the $p4$ group $G=\mathbb{Z}\rtimes\mathsf{C}_{4}$,
we can use the following sequence for subsampling:
$\mathbb{Z}\rtimes\mathsf{C}_{4}\geq 2\mathbb{Z}\rtimes\mathsf{C}_{4}\geq
4\mathbb{Z}\rtimes\mathsf{C}_{4}\geq
8\mathbb{Z}\rtimes\mathsf{C}_{2}\geq\\{e\\}$. Note that for the final two
layers of this example, we are subsampling translations and rotations jointly.

We lift the input defined on the homogeneous input space to $\mathcal{I}_{G}$
(see Appendix A.3 for details on homogeneous spaces and lifting), and treat
$f_{0}\in\mathcal{I}_{G}$ as inputs to the autoencoders. The group equivariant
encoder $\operatorname{\textsc{enc}}$ can be described as follows:

$\displaystyle[f_{l},\;p_{l}G_{l}]$
$\displaystyle=S_{b}{\downarrow}_{G_{l}}^{G_{l-1}}(\operatorname{\textsc{g-cnn}}_{l-1}^{E}(f_{l-1});\Phi_{l})$
$\displaystyle[z_{\text{inv}},z_{\text{eq}}]$
$\displaystyle=[f_{L}(e),\;(p_{1}G_{1},p_{2}G_{2},\ldots,p_{L}G_{L})]$ (8)

where $l=1,\dots,L$ and $\operatorname{\textsc{g-cnn}}_{l}(\cdot)$ denotes
G-convolutional layers before the $l$th subsampling layer.

The decoder $\operatorname{\textsc{dec}}$ simply goes in the opposite
direction, and can be written formally as:

$\displaystyle f_{L}$ $\displaystyle\text{ is defined on }G_{L}=\\{e\\}\text{
and }f_{L}(e)=z_{\text{inv}}$ $\displaystyle f_{l-1}$
$\displaystyle=\operatorname{\textsc{g-cnn}}_{l-1}^{D}(S_{u}{\uparrow}_{G_{l}}^{G_{l-1}}(f_{l},\;p_{l}G_{l}))$
(9)

where $l=L,\dots,1$ and $\hat{f}=f_{0}$ gives the final reconstruction.

Recall from Section 2.1 that the tuple $(i_{1},\ldots,i_{L})$ can be expressed
equivalently as a single integer. Similarly, the tuple
$(p_{1}G_{1},p_{2}G_{2},\ldots,p_{L}G_{L})$ can be expressed as a single group
element in $G$. We show in Section B.2 that the action implicitly defined on
the tuple via Section 2.2 simplifies elegantly to the left-action on the
single group element in $G$.

We now have the following properties for the learned representations (see
Appendix D for a proof):

######  Proposition 3.1.

When $\operatorname{\textsc{enc}}$ and $\operatorname{\textsc{dec}}$ are given
by Sections 3 and 3, and the group actions are specified as in Equation 3 and
Section 2.2, for any $g\in G$ and $f\in\mathcal{I}_{G}$, we have

$\displaystyle[z_{\text{inv}},g\cdot z_{\text{eq}}]$
$\displaystyle=\operatorname{\textsc{enc}}(\pi(g)f)$
$\displaystyle\pi(g)\hat{f}$
$\displaystyle=\operatorname{\textsc{dec}}(z_{\text{inv}},g\cdot
z_{\text{eq}})$

##  4 Related Work

#### Group equivariant neural networks

The equivariant subsampling/upsampling that we propose deals with feature maps
(functions) defined on the space of the group $G$ or its subgroups $K$, which
transform under the regular representation with the group action. Hence our
equivariant subsampling/upsampling is compatible with lifting-based group
equivariant neural networks defined on discrete groups [5, 22, 38, 37] that
define a mapping between feature maps on $G$. We also discuss the extension of
group equivariant subsampling to be compatible with those defined on
continuous/Lie groups [6, 14, 16, 1, 24] in Section 6. This is in contrast to
group equivariant neural networks that do not use lifting and use irreducible
representations, defining mappings between feature maps on the input space
$\mathbf{X}$. [10, 48, 41, 30, 47, 46, 44, 15, 17].

#### Coset pooling

In particular, [5] propose coset pooling, which is also a method for
equivariant subsampling. Here a feature map $f$ on $G$ is mapped onto a
feature map $\Phi(f)$ on $G/K$ (as opposed to $K$, for our equivariant
subsampling) as follows:

$\Phi(f)(gK)=\textsc{pool}_{k\in K}f(gk)$ (10)

such that the feature values on the coset $gK$ are pooled. For the
1D-translation case, where $G=\mathbb{Z},K=c\mathbb{Z}$, this amounts to
pooling over every $c$th pixel, which disrupts the locality of features as
opposed to our equivariant subsampling that preserves locality, and hence is
more suitable to use with convolutions for translation equivariance. See
Figure 2 for a visual comparison. As such, the $p4$-CNNs in [5] use standard
max pooling with stride=2 rather than coset pooling for $\mathbb{Z}^{2}$, and
coset-pooling is only used in the final layer to pool over feature maps across
90-degree rotations, achieving exact rotation equivariance but imperfect
translation equivariance. In our work, we use translation equivariant
subsampling in the earlier layers and rotation equivariant subsampling in the
final layers to achieve exact roto-translation equivariance.

Figure 2: Coset (max) pooling vs. equivariant subsampling.

#### Unsupervised disentangling and object discovery

GAEs produce equivariant ($z_{\text{eq}}$) and invariant ($z_{\text{inv}}$)
representations, effectively separating position and pose information with
other semantic information. This relates to unsupervised disentangling [21, 4,
28, 52] where different factors of variation in the data are separated in
different dimensions of a low-dimensional representation. However unlike
equivariant subsampling, there is no guarantee of any equivariance in the low-
dimensional representation, making the resulting disentangled representations
less interpretable. Works on unsupervised object discovery [2, 19, 13, 32]
learn object-centric representations, and we showcase GAEs in MONet [2] where
we replace their VAE with a V-GAE in order to separate position and pose
information and learn more interpretable representations of objects in a data-
efficient manner.

#### Shift-invariance in CNNs

As early as [40], it has been discussed that shift-invariance cannot hold for
conventional subsampling. Although standard subsampling operations such as
pooling or strided convolutions are not exactly shift invariant, they do not
prevent strong performance on classification tasks [39]. Nonetheless, [51]
integrates anti-aliasing to improve shift-invariance, showing that it leads to
better performance and generalisation on classification tasks. [3] explore a
similar strategy to our equivariant subsampling by partitioning feature maps
into polyphase components and select the component with the highest norm.
However, unlike the proposed group equivariant subsampling/upsampling which
tackle general equivariance for arbitrary discrete groups, both works focus
only on translation invariance.

##  5 Experiments

In this section, we compare the performance of GAEs with equivariant
subsampling to their non-equivariant counterparts that use standard
subsampling/upsampling in object-centric representation learning. We show that
GAEs give rise to more interpretable representations that show better sample
complexity and generalisation than their non-equivariant counterparts.

#### Models and Baselines

(G-)Convolutional autoencoders (G)ConvAE are composed of alternating
(G-)convolutional layers and subsampling/upsampling operations with a final
MLPs applied to the flattened feature maps. We categorize models by the types
of equivariance preserved by the convolutional layers. We consider three
different discrete symmetry groups: $p1$ (only translations), $p4$
(composition of translations and $90$ degree rotations), $p4m$ (composition of
translations, $90$ degree rotations and mirror reflection). The baseline
models are: ConvAE-$p1$ (standard convolutional autoencoders), GConvAE-$p4$,
GConvAE-$p4m$, where the corresponding equivariance is preserved in the
(G-)convolutional layers but not in the subsampling/upsampling operations. The
equivariant counterparts of these baseline models are GAE-$p1$, GAE-$p4$,
GAE-$p4m$, where the subsampling/upsampling operations are also equivariant.
For baseline models, we use a scale factor of $2$ for all
subsampling/upsampling layers. For GAEs, we subsample first the translations,
then rotations, followed by reflections, all with scale factor 2. e.g. for
GAE-$p4m$, the feature maps at each layer are defined on the following chain
of nested subgroups:
$\mathbb{Z}^{2}\rtimes(\mathsf{C}_{4}\rtimes\mathsf{C}_{2})\geq(2\mathbb{Z})^{2}\rtimes(\mathsf{C}_{4}\rtimes\mathsf{C}_{2})\geq(4\mathbb{Z})^{2}\rtimes(\mathsf{C}_{4}\rtimes\mathsf{C}_{2})\geq(8\mathbb{Z})^{2}\rtimes(\mathsf{C}_{4}\rtimes\mathsf{C}_{2})\geq(16\mathbb{Z})^{2}\rtimes(\mathsf{C}_{2}\rtimes\mathsf{C}_{2})\geq\\{e\\}$.
As in [5], we rescale the number of channels such that the total number of
parameters of these models roughly match each other.

#### Data

To demonstrate basic properties of GAEs and compare sample complexity under
the single object scenario, we use Colored-dSprite [35] and a modification of
FashionMNIST [49], where we first apply zero-padding to reach a size of
$64\times 64$, followed by random shifts, rotations and coloring. For multi-
object datasets, we use Multi-dSprites [26] and CLEVR6 which is a variant of
CLEVR [25] with up to $6$ objects. All input images are resized to a
resolution of $64\times 64$.

See Appendix E and our reference implementation
222https://github.com/jinxu06/gsubsampling for more details on hyperparameters
and data preprocessing. Our implementation is built upon open source projects
[20, 36, 50, 45, 13, 23, 42].

###  5.1 Basic Properties: Equivariance, Disentanglement and Out-of-
Distribution Generalization

#### Equivariance

The encoder-decoder pipeline in GAEs is exactly equivariant. In Figure 3, we
train GAE-$p4m$ on $6400$ examples from Colored-dSprites, and we show how to
manipulate reconstructions by manipulating the equivariant representation
$z_{\text{eq}}$ (left). If an image $x$ is encoded into
$[z_{\text{inv}},z_{\text{eq}}]$, then decoding $[z_{\text{inv}},g\cdot
z_{\text{eq}}]$ will give $g\cdot\hat{x}$ where $\hat{x}$ is the
reconstruction of $x$.

Figure 3: (Left) Manipulating reconstructions by modifying the equivariant
part $z_{\text{eq}}$. The second column are the original reconstructions,
which match the inputs well. The subsequent columns are reconstructions
decoded from modified $z_{\text{eq}}$. We transform $z_{\text{eq}}$ with a
sequence of group elements, and show the resulting reconstructions. (Right)
Manipulating reconstruction shape by modifying $z_{\text{inv}}$.

#### Disentanglement

The learned representations in GAEs are disentangled into an invariant part
$z_{\text{inv}}$ and an equivariant part $z_{\text{eq}}$. In Figure 3 (left),
we vary the equivariant part while the invariant part remains the same. In
Figure 3 (right), we show the frames of a movie of a heart, and show its
reconstruction after replacing $z_{\text{inv}}$ representing a heart with that
of an ellipse. Note that the ellipse shape undergoes the same sequence of
transformations as the heart.

#### Out-of-distribution generalisation

GAEs can generalise to data with unseen object locations and poses. We train
an GAE-$p4$ on $6400$ constrained training examples, where we only use
examples with locations in the top-left quarter and orientations within
$[0,90]$ degrees, as shown in Figure 4. During test time, we evaluate mean
squared error (MSE) of reconstructions on unfiltered test data to see how
models generalise to unseen location and poses. Both ConvAE-$p1$ and
GConvAE-$p4$ cannot generalise well to object poses out of their training
distribution. In contrast, GAE-$p1$ generalise to any locations without
performance degradation but not to unseen orientations, while GAE-$p4$, which
encodes both translation and rotation equivariance, generalises well to all
locations and orientations. We only use heart shapes for evaluation, because
the square and ellipse have inherent symmetries.

Figure 4: Generalisation to out-of-distribution object locations and poses.
During training, we constrain shapes to be in the top-left quarter, and the
orientation to be always less than $90$ degrees. On the right, we compare the
error of reconstructions of different models generalise on objects at unseen
locations in the first row, and how they generalise to unseen orientations in
the second row.

Figure 5: Reconstruction error on single object datasets

###  5.2 Single Object

Since GAEs are fully equivariant and can generalize to unseen object poses, it
is natural to conjecture that such models can significantly improve data
efficiency when symmetry-transformed data points are also plausible samples
from the data distribution. We test this hypothesis on Colored-dSprites and
transformed FashionMNIST, and the results are shown in Figure 5. On both
datasets, equivariant autoencoders significantly outperform their non-
equivariant counterparts for all considered training set sizes. In fact, as
shown in the figure, equivariant models trained with a smaller training set
size is often comparable to baseline models trained on a larger training set.
Furthermore, the results demonstrate that it is beneficial to consider
symmetries beyond translations in these problems: for both non-equivariant and
equivariant models, variants that encode rotation and reflection symmetries
consistently show better performance compared to models that only consider the
translation symmetry.

###  5.3 Multiple Objects

In multi-object scenes, it is often more interesting to consider local
symmetries associated with objects rather than the global symmetry for the
whole image. To exploit object symmetries in image data, one needs to first
discover objects and separate them from the background, which is a challenging
problem on its own. Currently, GAEs do not have inherent capability to solve
these problems. In order to investigate whether our models could improve data
efficiency in multi-object settings, we rely on recent work on unsupervised
object discovery and only use GAEs to model object components. More
specifically, we explored replacing component VAEs in MONet [2] with V-GAEs
(probabilistic version of our GAEs, where a standard Gaussian prior is put on
$z_{\text{inv}}$ and $z_{\text{eq}}$ remains deterministic), and train models
end-to-end. Again we study the low data regime to show results on data
efficiency.

[]  Dataset Multi-dSprites CLEVR6 Training Set Size 3200 6400 12800 3200 6400
12800 MONet $2.661(0.382)$ $1.385(0.235)$ $0.326(0.076)$ $0.673(0.059)$
$0.562(0.057)$ $0.546(0.056)$1 MONet-GAE-$p1$ $0.659(0.103)$ $0.359(0.025)$
$0.264(0.042)$ $0.473(0.064)$ $0.432(0.052)$ $0.388(0.016)$ MONet-GAE-$p4$
$0.563(0.195)$ $0.317(0.060)$ $0.231(0.067)$ $0.461(0.025)$ $0.414(0.022)$
$0.413(0.018)$

Table 1: Reconstruction error MSE ($\times 10^{-3}$) (mean(stddev) across $5$
seeds) on multi-object datasets

[]  Dataset Multi-dSprites CLEVR6 Training Set Size 3200 6400 12800 3200 6400
12800 MONet $0.597(0.022)$ $0.747(0.049)$ $0.891(0.009)$ $0.829(0.055)$
$0.878(0.023)$ $0.865(0.033)$1 MONet-GAE-$p1$ $0.762(0.049)$ $0.823(0.042)$
$0.889(0.013)$ $0.921(0.015)$ $0.917(0.032)$ $0.920(0.025)$ MONet-GAE-$p4$
$0.753(0.089)$ $0.833(0.072)$ $0.902(0.025)$ $0.878(0.055)$ $0.914(0.012)$
$0.910(0.011)$

Table 2: Foreground segmentation performance in terms of ARI (mean(stddev)
across $5$ seeds)

  * 1

We excluded $2$ outliers here as the baseline MONet occasionally fails during
late-phase training.

We train models on Multi-dSprites and CLEVR6 with training set sizes $3200$,
$6400$ and $12800$. We consider two evaluation metrics: mean squared error
(MSE) to measure the overall reconstruction quality, and adjusted rand index
(ARI), which is a clustering similarity measure ranging from $0$ (random) to
$1$ (perfect) to measure object segmentation. As in [2], we only use
foreground pixels to compute ARI. Component VAEs in MONet use spatial
broadcast decoders [43] that broadcast the latent representation to a full
scale feature map before feeding them into the decoders, and the decoders
therefore do not need upsampling. It has the implicit effect of encouraging
the smoothness of the decoder outputs. To encourage similar behaviour, we add
average pooling layers with stride $1$ and kernel size $3$ to our equivariant
decoders. As shown in Table 1, using GAEs to model object components
significantly improves reconstruction quality, which is consistent with our
findings in single-object scenario. As shown in Table 2, using GAEs to model
object components also leads to better object discovery in the low data
regimes, but this advantage seems to diminish as the dataset becomes
sufficiently large.

##  6 Conclusions, Limitations and Future Work

#### Conclusions

We have proposed subsampling/upsampling operations that exactly preserve
translation equivariance, and generalised them to define exact group
equivariant subsampling/upsampling for discrete groups. We have used these
layers in GAEs that allow learning low-dimensional representations that can be
used to reliably manipulate pose and position of objects, and further showed
how GAEs can be used to improve data efficiency in multi-object representation
learning models.

#### Limitations and Future work

Although the equivariance properties of subsampling layers also hold for Lie
groups, we have not discussed the practical complexities that arise with the
continuous case, where feature maps are only defined on a finite subset of the
group rather than the whole group. We leave this as important future work, as
well as application of equivariant subsampling for tasks other than
representation learning where equivariance/invariance is desirable e.g. object
classification, localization. Another limitation is that our work focuses on
global equivariance, like most other works in the literature. An important
direction is to extend to the case of local equivariances e.g. object-specific
symmetries for multi-object scenes.

## Acknowledgments and Disclosure of Funding

We would like to thank Adam R. Kosiorek for valuable discussion. We also thank
Lewis Smith, Desi Ivanova, Sheheryar Zaidi, Neil Band, Fabian Fuchs, Ning
Miao, and Matthew Willetts for providing feedback on earlier versions of the
paper. JX gratefully acknowledges funding from Tencent AI Labs through the
Oxford-Tencent Collaboration on Large Scale Machine Learning.

## References

  * Bekkers, [2020] Bekkers, E. J. (2020).  B-spline CNNs on Lie groups.  In ICLR.
  * Burgess et al., [2019] Burgess, C. P., Matthey, L., Watters, N., Kabra, R., Higgins, I., Botvinick, M., and Lerchner, A. (2019).  Monet: Unsupervised scene decomposition and representation.  arXiv preprint arXiv:1901.11390.
  * Chaman and Dokmanić, [2020] Chaman, A. and Dokmanić, I. (2020).  Truly shift-invariant convolutional neural networks.  arXiv preprint arXiv:2011.14214.
  * Chen et al., [2018] Chen, T. Q., Li, X., Grosse, R., and Duvenaud, D. (2018).  Isolating sources of disentanglement in variational autoencoders.  In International Conference on Learning Representations.
  * Cohen and Welling, [2016] Cohen, T. and Welling, M. (2016).  Group equivariant convolutional networks.  In International conference on machine learning, pages 2990–2999.
  * [6] Cohen, T. S., Geiger, M., Köhler, J., and Welling, M. (2018a).  Spherical CNNs.  In ICLR.
  * [7] Cohen, T. S., Geiger, M., Köhler, J., and Welling, M. (2018b).  Spherical CNNs.  In International Conference on Learning Representations.
  * [8] Cohen, T. S., Geiger, M., and Weiler, M. (2018c).  Intertwiners between induced representations (with applications to the theory of equivariant neural networks).  arXiv preprint arXiv:1803.10743.
  * 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:9145–9156.
  * Cohen and Welling, [2017] Cohen, T. S. and Welling, M. (2017).  Steerable cnns.  In International Conference on Learning Representations.
  * Dieleman et al., [2016] Dieleman, S., De Fauw, J., and Kavukcuoglu, K. (2016).  Exploiting cyclic symmetry in convolutional neural networks.  In International Conference on Machine Learning, pages 1889–1898.
  * Dieleman et al., [2015] Dieleman, S., Willett, K. W., and Dambre, J. (2015).  Rotation-invariant convolutional neural networks for galaxy morphology prediction.  Monthly notices of the royal astronomical society, 450(2):1441–1459.
  * Engelcke et al., [2020] Engelcke, M., Kosiorek, A. R., Parker Jones, O., and Posner, I. (2020).  GENESIS: Generative Scene Inference and Sampling of Object-Centric Latent Representations.  International Conference on Learning Representations (ICLR).
  * Esteves et al., [2018] Esteves, C., Allen-Blanchette, C., Makadia, A., and Daniilidis, K. (2018).  Learning SO(3) equivariant representations with spherical CNNs.  In ECCV.
  * Esteves et al., [2020] Esteves, C., Makadia, A., and Daniilidis, K. (2020).  Spin-weighted spherical CNNs.  In NeurIPS.
  * Finzi et al., [2020] Finzi, M., Stanton, S., Izmailov, P., and Wilson, A. G. (2020).  Generalizing convolutional neural networks for equivariance to Lie groups on arbitrary continuous data.  In ICML.
  * Fuchs et al., [2020] Fuchs, F. B., Worrall, D. E., Fischer, V., and Welling, M. (2020).  SE(3)-Transformers: 3D roto-translation equivariant attention networks.  In NeurIPS.
  * Gens and Domingos, [2014] Gens, R. and Domingos, P. M. (2014).  Deep symmetry networks.  Advances in neural information processing systems, 27:2537–2545.
  * Greff et al., [2019] Greff, K., Kaufman, R. L., Kabra, R., Watters, N., Burgess, C., Zoran, D., Matthey, L., Botvinick, M., and Lerchner, A. (2019).  Multi-object representation learning with iterative variational inference.  In International Conference on Machine Learning, pages 2424–2433. PMLR.
  * Harris et al., [2020] Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del Río, J. F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E. (2020).  Array programming with NumPy.  Nature, 585(7825):357–362.
  * Higgins et al., [2017] Higgins, I., Matthey, L., Pal, A., Burgess, C., Glorot, X., Botvinick, M., Mohamed, S., and Lerchner, A. (2017).  beta-VAE: Learning basic visual concepts with a constrained variational framework.  In International Conference on Learning Representations.
  * Hoogeboom et al., [2018] Hoogeboom, E., Peters, J. W., Cohen, T. S., and Welling, M. (2018).  HexaConv.  In ICLR.
  * Hunter, [2007] Hunter, J. D. (2007).  Matplotlib: A 2d graphics environment.  Computing in Science & Engineering, 9(3):90–95.
  * Hutchinson et al., [2021] Hutchinson, M., Le Lan, C., Zaidi, S., Dupont, E., Teh, Y. W., and Kim, H. (2021).  Lietransformer: Equivariant self-attention for lie groups.  In Proceedings of the 38th International Conference on Machine Learning (ICML).
  * Johnson et al., [2017] Johnson, J., Hariharan, B., Van Der Maaten, L., Fei-Fei, L., Lawrence Zitnick, C., and Girshick, R. (2017).  Clevr: A diagnostic dataset for compositional language and elementary visual reasoning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2901–2910.
  * Kabra et al., [2019] Kabra, R., Burgess, C., Matthey, L., Kaufman, R. L., Greff, K., Reynolds, M., and Lerchner, A. (2019).  Multi-object datasets.  https://github.com/deepmind/multi-object-datasets/.
  * Kanazawa et al., [2014] Kanazawa, A., Sharma, A., and Jacobs, D. (2014).  Locally scale-invariant convolutional neural networks.  arXiv preprint arXiv:1412.5104.
  * Kim and Mnih, [2018] Kim, H. and Mnih, A. (2018).  Disentangling by factorising.  In International Conference on Learning Representations.
  * Kingma and Ba, [2015] Kingma, D. P. and Ba, J. (2015).  Adam: A method for stochastic optimization.  In Bengio, Y. and LeCun, Y., editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
  * Kondor et al., [2018] Kondor, R., Lin, Z., and Trivedi, S. (2018).  Clebsch–Gordan nets: a fully Fourier space spherical convolutional neural network.  In NeurIPS.
  * Locatello et al., [2019] Locatello, F., Bauer, S., Lucic, M., Raetsch, G., Gelly, S., Schölkopf, B., and Bachem, O. (2019).  Challenging common assumptions in the unsupervised learning of disentangled representations.  In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4114–4124. PMLR.
  * Locatello et al., [2020] Locatello, F., Weissenborn, D., Unterthiner, T., Mahendran, A., Heigold, G., Uszkoreit, J., Dosovitskiy, A., and Kipf, T. (2020).  Object-centric learning with slot attention.  arXiv preprint arXiv:2006.15055.
  * Marcos et al., [2016] Marcos, D., Volpi, M., and Tuia, D. (2016).  Learning rotation invariant convolutional filters for texture classification.  In 2016 23rd International Conference on Pattern Recognition (ICPR), pages 2012–2017. IEEE.
  * Masci et al., [2011] Masci, J., Meier, U., Ciresan, D., and Schmidhuber, J. (2011).  Stacked convolutional auto-encoders for hierarchical feature extraction.  In ICANN.
  * Matthey et al., [2017] Matthey, L., Higgins, I., Hassabis, D., and Lerchner, A. (2017).  dsprites: Disentanglement testing sprites dataset.  https://github.com/deepmind/dsprites-dataset/.
  * Paszke et al., [2019] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. (2019).  Pytorch: An imperative style, high-performance deep learning library.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc.
  * Romero et al., [2020] Romero, D. W., Bekkers, E. J., Tomczak, J. M., and Hoogendoorn, M. (2020).  Attentive group equivariant convolutional networks.  In ICML.
  * Romero and Hoogendoorn, [2020] Romero, D. W. and Hoogendoorn, M. (2020).  Co-attentive equivariant neural networks: Focusing equivariance on transformations co-occurring in data.  In ICLR.
  * Scherer et al., [2010] Scherer, D., Müller, A., and Behnke, S. (2010).  Evaluation of pooling operations in convolutional architectures for object recognition.  In Diamantaras, K., Duch, W., and Iliadis, L. S., editors, Artificial Neural Networks – ICANN 2010, pages 92–101, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Simoncelli et al., [1992] Simoncelli, E., Freeman, W., Adelson, E., and Heeger, D. (1992).  Shiftable multiscale transforms.  IEEE Transactions on Information Theory, 38(2):587–607.
  * Thomas et al., [2018] Thomas, N., Smidt, T., Kearnes, S., Yang, L., Li, L., Kohlhoff, K., and Riley, P. (2018).  Tensor field networks: Rotation-and translation-equivariant neural networks for 3d point clouds.  arXiv preprint arXiv:1802.08219.
  * Waskom, [2021] Waskom, M. L. (2021).  seaborn: statistical data visualization.  Journal of Open Source Software, 6(60):3021.
  * Watters et al., [2019] Watters, N., Matthey, L., Burgess, C. P., and Lerchner, A. (2019).  Spatial broadcast decoder: A simple architecture for learning disentangled representations in vaes.  arXiv preprint arXiv:1901.07017.
  * [44] Weiler, M. and Cesa, G. (2019a).  General e (2)-equivariant steerable cnns.  In Advances in Neural Information Processing Systems, pages 14334–14345.
  * [45] Weiler, M. and Cesa, G. (2019b).  General E(2)-Equivariant Steerable CNNs.  In Conference on Neural Information Processing Systems (NeurIPS).
  * [46] Weiler, M., Geiger, M., Welling, M., Boomsma, W., and Cohen, T. S. (2018a).  3d steerable cnns: Learning rotationally equivariant features in volumetric data.  In Advances in Neural Information Processing Systems, pages 10381–10392.
  * [47] Weiler, M., Hamprecht, F. A., and Storath, M. (2018b).  Learning steerable filters for rotation equivariant cnns.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 849–858.
  * Worrall et al., [2017] Worrall, D. E., Garbin, S. J., Turmukhambetov, D., and Brostow, G. J. (2017).  Harmonic networks: Deep translation and rotation equivariance.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5028–5037.
  * Xiao et al., [2017] Xiao, H., Rasul, K., and Vollgraf, R. (2017).  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.
  * Yadan, [2019] Yadan, O. (2019).  Hydra - a framework for elegantly configuring complex applications.  Github.
  * Zhang, [2019] Zhang, R. (2019).  Making convolutional networks shift-invariant again.  In International Conference on Machine Learning, pages 7324–7334.
  * Zhao et al., [2017] Zhao, S., Song, J., and Ermon, S. (2017).  Infovae: Information maximizing variational autoencoders.  arXiv preprint arXiv:1706.02262.

##  Appendix A Preliminaries

###  A.1 Group, Coset and Quotient Space

A _group_ $G$ is a set of elements equipped with a binary operation (denoted
as $\cdot$) that satisfies the following group axioms:

  1. 1.

(Closure) For all $a,b\in G$, $a\cdot b\in G$.

  2. 2.

(Associative) For all $a,b,c\in G$, $(a\cdot b)\cdot c=a\cdot(b\cdot c)$.

  3. 3.

(Identity element) There exists an identity element $e$ in $G$ such that, for
any $a\in G$ we have $e\cdot a=a\cdot e=a$.

  4. 4.

(Inverse element) For each $a\in G$, there exists an element $b\in G$ such
that $a\cdot b=b\cdot a=e$ where $e$ is the identity element.

The centered dot $\cdot$ can sometimes be omitted if there is no ambiguity.

In this work, we are mainly interested in symmetry groups where each group
element is associated with a symmetry of a pattern, which is a transformation
that leaves the pattern invariant. In symmetry groups, the binary operation
corresponds to composition of transformations.

A subset $H$ contained within $G$ is a _subgroup_ of $G$ if it forms a group
on its own under the same binary operation. Given a subgroup $H$ and an
arbitrary group element $g\in G$, one can define _left cosets_ of $H$ as
follows:

$\displaystyle gH$ $\displaystyle=\\{g\cdot h\;|\;h\in H\\}$

The left cosets of $H$ form a partition of $G$ for any choice of $H$, i.e. the
union of all cosets is $G$ and all cosets defined above are either identical
or have empty interception. The set of all left cosets is called the _quotient
space_ and is denoted as $G/H=\\{gH\;|\;g\in G\\}$.

As an example, all integers $\mathbb{Z}$ under addition forms a group and all
multiples of $n$, denoted as $n\mathbb{Z}$ is a subgroup of $\mathbb{Z}$. For
any integer $k\in\mathbb{Z}$, the set $n\mathbb{Z}+k$ containing all integers
that has the remainder as $k$ divided by $n$, is a coset of $n\mathbb{Z}$.
There are $n$ distinct cosets like this, and they form the quotient space
$\mathbb{Z}/n\mathbb{Z}$.

###  A.2 Group Homomorphism, Group Actions and Group Equivariance

Given two groups $(G,\cdot_{G})$ and $(H,\cdot_{H})$, a _group homomorphism_
from $G$ to $H$ is function $f:G\rightarrow H$ such that for any $u,v\in G$

$f(u\cdot_{G}v)=f(u)\cdot_{H}f(v).$

It is a special mapping between two groups that is compatible with group
structures. If $f$ is an one-to-one mapping, we call it a _group isomorphism_.
Two groups $G_{1}$ and $G_{2}$ are isomporphic if there is an isomorphism
between them, and this is written as $G_{1}\cong G_{2}$.

A _group action_ is a group homomorphism from a given group $G$ to the group
of transformations on a space $\mathbf{X}$. We say the group $G$ acts on the
space $\mathbf{X}$ and the transformation corresponding to $g\in G$ is a
bijection on $\mathbf{X}$ that maps $x$ to $g\cdot x$.

If the group actions of $G$ on spaces $\mathbf{X}$ and $\mathbf{Y}$ are both
defined, a function $f:\mathbf{X}\rightarrow\mathbf{Y}$ is said to be _group
equivariant_ if

$\displaystyle g\cdot f(x)=f(g\cdot x)$

###  A.3 Homogeneous Spaces and Lifting Feature Maps

If the action of a group $G$ on the space $\mathbf{X}$ is defined, and the
action is transitive (i.e. $\forall x,x^{\prime}\in\mathbf{X},\exists g\in G$,
s.t. $x^{\prime}=g\cdot x$), we refer to $\mathbf{X}$ as being a homogeneous
space for $G$. There is a natural one-to-one correspondence between the
homogeneous space $\mathbf{X}$ and disjoint subsets of the group $G$. Given an
arbitrary origin $x_{0}\in\mathbf{X}$, $H=\\{g\in G|g\cdot x_{0}=x_{0}\\}$ is
a subgroup of $G$, where $H$ is called the stabiliser of the origin. Because
the group action on $\mathbf{X}$ is transitive, every element $x\in\mathbf{X}$
corresponds to a left coset in $s(x;x_{0})H\in G/H$, where $s(x;x_{0})$ is
(any) group element that transforms $x_{0}$ to $x$. It can be shown that for
$x,x^{\prime}\in\mathbf{X},x\neq x^{\prime}$, $s(x;x_{0})$ and
$s(x^{\prime};x_{0})$ are disjoint.

Because spatial data is often represented as functions on the homogeneous
space $f_{\mathbf{X}}:x_{i}\mapsto f_{i}$, while lifting-based group
equivariant neural networks operate on feature maps defined on the group,
there is usually an operation called lifting, that maps the data to the
feature space of functions on the group, before applying equivariant modules.
Using the correspondence between $\mathbf{X}$ and the quotient space $G/H$, we
can map each pair $(x_{i},f_{i})$ to the set $\\{(g,f_{i})|g\in
s(x_{i};x_{0})H\\}$. It can be seen as lifting the input feature map
$f_{\mathbf{X}}:x_{i}\mapsto f_{i}$ to the feature map
$\operatorname{\textsc{lift}}(f_{\mathbf{X}}):g\mapsto f_{i}$ for $g\in
s(x_{i};x_{0})H$. In this work, we assume all input feature maps have been
lifted to feature maps on the group.

###  A.4 Wallpaper Groups

Wallpaper groups categorise symmetries of repetitive patterns on a 2D plane.
For simplicity, we only considered $3$ different types of wallpaper symmetry
groups $p1$, $p4$, and $p4m$ in this work following [5]. These groups are
named using the crystallographic notation, where $p$ standards for primitive
cells, the next digit indicates the highest order of rotational symmetries,
and $m$ stands for mirror reflection. All symmetries contained in these groups
can be deduced from their name:

  * •

$p1$: All 2D integer translations.

  * •

$p4$: All compositions of 2D integer translations and rotations by a multiple
of $90$ degrees.

  * •

$p4m$: All compositions of elements in $p4$ and the mirror reflection.

All three groups $p1$, $p4$, and $p4m$ can be constructed from basic additive
groups of integers $\mathbb{Z}$ and cyclic groups $\mathsf{C}_{n}$ using the
inner semi-direct product. Given a group $G$ with a normal subgroup $N$ (i.e.
$\forall n\in N,g\in G$, $gng^{-1}\in N$), a subgroup $H$ (not necessarily a
normal subgroup), if $G$ is the product of subgroups $G=NH=\\{nh|n\in N,h\in
H\\}$, and $N\cap H=\\{e\\}$, we say $G$ is a inner semi-direct product of $N$
and $H$, written as $G=N\rtimes H$. Using semi-direct product, $p1$, $p4$, and
$p4m$ can be expressed as:

$\displaystyle p1$ $\displaystyle\cong\mathbb{Z}^{2}$ $\displaystyle p4$
$\displaystyle\cong\mathbb{Z}^{2}\rtimes\mathsf{C}_{4}$ $\displaystyle p4m$
$\displaystyle\cong\mathbb{Z}^{2}\rtimes(\mathsf{C}_{4}\rtimes\mathsf{C}_{2})$
(11)

If $G\cong N\rtimes H$, the binary and inverse operations for $G$ can be
determined from its subgroups $N$ and $H$. We represent group elements in $G$
as a tuple $(n,h)$ where $n\in N$ and $h\in H$. Let $\phi_{h}(n)=hnh^{-1}$,
the binary operation on $G$ can be given by:

$\displaystyle(n_{1},h_{1})\cdot(n_{2},h_{2})=(n_{1}\phi_{h_{1}}(n_{2}),h_{1}h_{2})$

and the inverse for element in $G$ can also be derived from the above:

$\displaystyle(n,h)^{-1}=(\phi_{h^{-1}}(n^{-1}),h^{-1})$

These properties can be used to simplify the implementation of the considered
groups $p1$, $p4$, and $p4m$ following the decomposition in Section A.4, and
the operations for basic groups $\mathbb{Z}$ and $\mathsf{C}_{n}$ are easy to
implement.

###  A.5 Feature Maps in G-CNNs

A general mathematical framework is introduced in [9] to specify convolutional
feature spaces used in G-CNNs, and feature maps are treated as fields over a
homogeneous space. It covers most previous works on equivariant neural
networks including [5, 10, 7, 44]. Under this framework, one way to represent
fields is through constrained functions defined on the whole symmetry group,
also known as Mackey functions [9].

Formally, let $G$ be a symmetry group, and $H\leq G$ together with $G$
determines the homogeneous space $G/H$. For a group representation $(\rho,V)$
of $H$, the action of the whole group $G$ on fields can be described by an
induced representation $\pi=\text{Ind}_{H}^{G}\rho$, whose realisation depends
on how we represent these fields. Below we specify the feature space
$\mathcal{I}_{M}$ 333$\mathcal{I}_{M}$ corresponds to $\mathcal{I}_{G}$ in [9]
for the Mackey function field representation discussed in [8, 9]:

$\displaystyle\mathcal{I}_{M}$ $\displaystyle=\\{f:G\to
V|f(gh)=\rho(h^{-1})f(g),\forall g\in G,h\in H\\}$ (12)

which forms a vector space. Moreover, when $\rho$ is a _regular
representation_ , which is the implicit choice of [18, 27, 12, 11, 5, 33],
fields can also be represented as unconstrained functions on $G$ and the
feature space can be written as

$\displaystyle\mathcal{I}_{G}=\\{f:G\to V^{\prime}\\}$

with $V^{\prime}$ being a different vector space from $V$. If $\rho$ is a
regular representation.

Feature maps are represented as functions on $G$ in both $\mathcal{I}_{M}$ and
$\mathcal{I}_{G}$, even though $\mathcal{I}_{M}$ have additional conditions
given in Equation 12. Moreover, the induced representation
$\pi=\text{Ind}_{H}^{G}\rho$ for them have the same form:

$\displaystyle[\pi(u)f](g)=f(u^{-1}g)$

##  Appendix B Equivariant Subsampling and Upsampling

###  B.1 Constructing $\Phi$

In Section 2.3, we provide a simple construction of the equivariant map
$\Phi:\mathcal{I}_{G}\rightarrow G/K$ which gives the sampling indexes. The
construction is a valid one if the argmax is unique. In practice one can
insert arbitrary equivariant layers to $f$ before and after we take the norm
$\|\cdot\|_{1}$ to avoid a non-unique argmax (see Appendix E). However, in
theory, there could be cases that the argmax is always non-unique. We discuss
this case below and provide a more complex construction for it.

One cannot avoid a non-unique argmax in Equation 7 when the input feature map
$f\in\mathcal{I}_{G}$ has inherent symmetries, i.e. there exists $u\in G,u\neq
e$, such that $f=\pi(u)f$. Assuming there is a unique argmax $g^{\ast}$ such
that $g^{\ast}=\arg\max_{g\in G}\|f(g)\|_{1}$, we would have:

$\displaystyle f(u\cdot g^{\ast})=f(g^{\ast})=\max_{g\in G}\|f(g)\|_{1}$

Therefore $u\cdot g^{\ast}$ is also a valid argmax, hence the argmax is not
unique. For example, when $f$ is a feature map representing a center-aligned
circle, we would have $f=\pi(u)f$, where $u\in\mathit{O}(2)$ is associated
with an arbitrary rotation around the center. One cannot find a unique argmax
$g^{\ast}$ for this example, because the feature map would take the same
function values at $u\cdot g^{\ast}$.

Under the circumstance described above, the argmax operation would return a
set of elements where each one attains the function’s largest values. We
denote it as $S^{\ast}=\arg\max_{g\in G}\|f(g)\|_{1}$, where $S^{\ast}$ is a
subset of $G$. To obtain the sampling index (a coset) $pK$, we sample
uniformly from the set $S^{\ast}$, and let $\Phi$ outputs $pK$ where $p\sim
S^{\ast}$. In this case, the map $\Phi$ is still equivariant in distribution
even though it is now a stochastic map.

Note that it is possible to consider more sophisticated solutions or even use
learnable modules for $\Phi$, which we leave for future work.

###  B.2 Multiple Subsampling Layers

#### Translation equivariant subsampling

We can stack convolutional and translation equivariant subsampling layers to
construct exactly translation equivariant CNNs. Unlike standard CNNs, each
translation equivariant subsampling layer with a scale factor $c_{k}$ outputs
a subsampling index $i_{k}$ in addition to the feature maps. Hence the
equivariant representation output by the CNN with $L$ subsampling layers is a
final feature map $f_{L}$ and a $L$-tuple of sampling indices
$(i_{1},...,i_{L})$.

In the multi-layer case, the $l$-th subsampling layer takes in a feature map
$f$ on $\prod_{k=1}^{l-1}c_{k}\mathbb{Z}$ and outputs: 1) a feature map on
$\prod_{k=1}^{l}c_{k}\mathbb{Z}$ and 2) a subsampling index
$i_{l}\in\prod_{k=1}^{l-1}c_{k}\mathbb{Z}/\prod_{k=1}^{l}c_{k}\mathbb{Z}\cong\mathbb{Z}/c_{l}\mathbb{Z}$
given by:

$\displaystyle(\prod_{k=1}^{l-1}c_{k})\cdot
i_{l}=p_{l}=\Phi_{c}(f)=\bmod({\arg\max}_{x\in(\prod_{k=1}^{l-1}c_{k})\mathbb{Z}}\|f(x)\|_{1},\prod_{k=1}^{l}c_{k})$

This is equivalent to treating the input feature map $f$ as a feature map
$f^{\prime}$ defined on $\mathbb{Z}$ (i.e. mapping the support of $f$ from
$\prod_{k=1}^{l-1}c_{k}\mathbb{Z}$ to $\mathbb{Z}$ via division by
$\prod_{k=1}^{l-1}c_{k}$), and the subsampling layer outputting: 1) a feature
map on $c_{l}\mathbb{Z}$ and 2) a subsampling index
$i_{l}\in\mathbb{Z}/c_{l}\mathbb{Z}$ given by:

$\displaystyle
i_{l}=\bmod({\arg\max}_{x\in\mathbb{Z}}\|f^{\prime}(x)\|_{1},c_{l})$

Hence the tuple $(i_{1},...,i_{L})$ that contains the sampling indices of all
layers can be expressed equivalently as a single integer:

$\displaystyle
r_{\text{eq}}=\sum_{l=1}^{L}p_{l}=\sum_{l=1}^{L}(\prod_{k=1}^{l-1}c_{k})\cdot
i_{l}$

where $r_{\text{eq}}\in\mathbb{Z}/(\prod_{k=1}^{L}c_{k})\mathbb{Z}$. Note that
the conversion between $r_{\text{eq}}$ and $(i_{1},...,i_{L})$ can be seen as
the conversion between _mixed radix notation_ and decimal notation. Mixed
radix notation is a mixed base numeral system where the numerical base varies
from position to position, as opposed to base-n systems that have the same
base for all positions444A commonly used example of mixed radix notation is to
express time, where e.g. 12:34:56 has a base of 24 for the hour digit, base 60
for the minute digit and base 60 for the second digit.. Thus there is an one-
to-one correspondence between the two. Moreover, when the input feature map is
translated to the right by $t\in\mathbb{Z}$, $r_{\text{eq}}$ would become
$\bmod(r_{\text{eq}}+t,\prod_{k=1}^{L}c_{k})$. See the statement of this
result for the general group case in Proposition B.1 and its proof in Section
D.3.

#### Group equivariant subsampling

Similarly, given an input feature map $f\in\mathcal{I}_{G}$, we can construct
CNNs/G-CNNs with multiple equivariant subsampling layers by specifying a
sequence of nested subgroups $G=G_{0}\geq G_{1}\geq\dots\geq G_{L}$. The
$l$-th subsampling layer takes in a feature map on $G_{l-1}$, outputs a
feature map on $G_{l}$ and a sampling index $p_{l}G_{l}\in G_{l-1}/G_{l}$.
Formally, the $l$-th subsampling layer can be written as:

$\displaystyle
S_{b}{\downarrow}_{G_{l}}^{G_{l-1}}:\mathcal{I}_{G_{l-1}}\rightarrow\mathcal{I}_{G_{l}}\times
G_{l-1}/G_{l}$

The equivariant representation output by the CNNs/G-CNNs with $L$ subsampling
layers is a feature map in $f_{L}\in G_{L}$ and a $L$-tuple
$(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})$.

Similar to the 1D translation case, the sampling index tuple
$(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})$ can be expressed equivalently as a
single element in the quotient space $G/G_{L}$:

$\displaystyle
r_{\text{eq}}=(\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{L})G_{L}=\nu(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})$
(13)

where $\bar{p}_{l}$ denote the coset representive for the quotient space
$G_{l-1}/G_{l}$. $\nu$ is a bijection from $r_{\text{eq}}$ to the tuple, whose
inverse can be computed by the following recursive procedure:

$\displaystyle p^{\prime}_{1}G_{L}$ $\displaystyle=r_{\text{eq}}$
$\displaystyle p^{\prime}_{l}$ $\displaystyle=\bar{p}_{l-1}^{\prime-1}\cdot
p^{\prime}_{l-1}$
$\displaystyle(p^{\prime}_{1}G_{1},p^{\prime}_{2}G_{2},\dots,p^{\prime}_{L}G_{L})$
$\displaystyle=\nu^{-1}(r_{\text{eq}})$ (14)

######  Proposition B.1.

$\nu^{-1}$ is the inverse of $\nu$, hence $\nu$ is bijective. And $\forall
u\in G$ we have:

$\displaystyle
u\cdot\nu(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})=\nu(u\cdot(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})).$

##  Appendix C Group Equivariant Autoencoders

In Section B.2 we discussed that we can stack multiple subsampling layers by
specifying a sequence of nested groups $G=G_{0}\geq G_{1}\geq\dots\geq G_{L}$,
and the CNN/G-CNNs with $L$ subsampling layers would produce a feature map on
$G_{L}$ and a tuple $z_{\text{eq}}=(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})$.
Furthermore, we know from Proposition B.1 that there is an one-to-one
correspondence between the tuple representation $z_{\text{eq}}$ and the single
group element representation $r_{\text{eq}}=\nu(z_{\text{eq}})\in G/G_{L}$.
For group equivariant autoencoders, we specify a sequence of subgroups but
with $G_{L}=\\{e\\}$. In this case, $r_{\text{eq}}$ would simply become a
group element in $G$. And the group action simplifies to left-multiplying the
corresponding group elements.

Although one can simply use the tuple output by the encoder to perform
upsampling in the decoder (and hence use the same sequence of nested
subgroups), this is not strictly necessary as one can use a different sequence
of nested subgroups for the decoder and obtain the tuple using the
decomposition procedure in Section B.2. Moreover, for more efficient
implementation of GAEs, one does not need to pass through $\Phi$ in Equation 7
for every subsampling layer. It would suffice to obtain the tuple of
subsampling indexes from the first subsampling layer using:

$\displaystyle(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})=\nu^{-1}(\arg\max_{g\in
G}\|f(g)\|_{1})$ (15)

##  Appendix D Proofs

###  D.1 Proof of Lemma 2.1 (See page 2.1)

See 2.1

###### Proof.

Since $\bar{p}$ and $\overline{up}$ are coset representives for $pK$ and
$(up)K$, we can let $p=\bar{p}k_{p}$, $up=\overline{up}k_{up}$, where
$k_{p},k_{up}\in K$. From Section 2.2, note that
$\bar{p}^{\prime}=\overline{up}=upk_{up}^{-1}$. Hence

$\displaystyle\bar{p}^{\prime-1}u\bar{p}$
$\displaystyle=(upk_{up}^{-1})^{-1}u(pk_{p}^{-1})$
$\displaystyle=k_{up}p^{-1}u^{-1}upk_{p}^{-1}$
$\displaystyle=k_{up}k_{p}^{-1}\in K$ (16)

Hence $\pi^{\prime}(u)$ (as defined in Section 2.2) defines a transformation
from the space $\mathcal{I}_{K}\times G/K$ to itself.

To prove $\pi^{\prime}$ is a group action, we would like to show that for all
$u,u^{\prime}\in G$

$\displaystyle\pi^{\prime}(u^{\prime})(\pi^{\prime}(u)[f_{b},\;pK])=\pi^{\prime}(u^{\prime}u)[f_{b},\;pK]$

Let $[f^{\prime}_{b},\;p^{\prime}K]=\pi^{\prime}(u)[f_{b},\;pK]$ and
$[f^{\prime\prime}_{b},\;p^{\prime\prime}K]=\pi^{\prime}(u^{\prime}u)[f_{b},\;pK]$,
by the definition of $\pi^{\prime}$ in Section 2.2, we have

$\displaystyle p^{\prime\prime}K$
$\displaystyle=((u^{\prime}u)p)K=u^{\prime}(upK)=u^{\prime}(p^{\prime}K)$

and

$\displaystyle f^{\prime\prime}_{b}$
$\displaystyle=\pi(\bar{p}^{\prime\prime-1}(u^{\prime}u)\bar{p})f_{b}=\pi(\bar{p}^{\prime\prime-1}u^{\prime}\bar{p}^{\prime})\pi(\bar{p}^{\prime-1}u\bar{p})f_{b}=\pi(\bar{p}^{\prime\prime-1}u^{\prime}\bar{p}^{\prime})f^{\prime}_{b}.$

Hence

$\displaystyle[f^{\prime\prime}_{b},\;p^{\prime\prime}K]=\pi^{\prime}(u^{\prime})[f^{\prime}_{b},\;p^{\prime}K]$

It is easy to also check that

$\displaystyle[f_{b},\;pK]=\pi^{\prime}(e)[f_{b},\;pK]$

Therefore $\pi^{\prime}$ defines a valid group action. ∎

###  D.2 Proof of Proposition 2.2 (See page 2.2)

See 2.2

###### Proof.

We first define a _restrict_ operation on $f\in\mathcal{I}_{G}$ and an
_extend_ operation on $f_{1}\in\mathcal{I}_{K}$:

$\displaystyle f{\downarrow}_{K}^{G}(k)$ $\displaystyle=f(k),\hskip
11.38109ptk\in K$ $\displaystyle f_{1}{\uparrow}_{K}^{G}(g)$
$\displaystyle=\begin{cases}f_{1}(g)&g\in K\\\ \bm{0}&g\notin K\end{cases}$

where $f{\downarrow}_{K}^{G}\in\mathcal{I}_{K}$ and
$f_{1}{\uparrow}_{K}^{G}\in\mathcal{I}_{G}$.

Recall that $s:G/K\rightarrow G$ is a function choosing a coset representive
$\bar{p}$ for each coset $pK$. Using the restrict operation, the subsampling
operation $S_{b}{\downarrow}_{K}^{G}(f;\Phi)$ in Section 2.2 can equivalently
be described as:

$\displaystyle pK$ $\displaystyle=\Phi(f)$ $\displaystyle f_{b}$
$\displaystyle=[\pi(\bar{p}^{-1})f]{\downarrow}_{K}^{G}$
$\displaystyle[f_{b},\;pK]$ $\displaystyle=S_{b}{\downarrow}_{K}^{G}(f;\Phi)$

And the upsampling operation $S_{u}{\uparrow}_{K}^{G}$ can be rewritten using
the extend operation as:

$\displaystyle f_{u}$
$\displaystyle=S_{u}{\uparrow}_{K}^{G}(f_{1},pK)=\pi(\bar{p})(f_{1}{\uparrow}_{K}^{G})$

For any $u\in G$ let $f^{\prime}=\pi(u)f$ and
$[f^{\prime}_{b},\;p^{\prime}K]=\pi^{\prime}(u)[f_{b},\;pK]$ where $\pi$ and
$\pi^{\prime}$ are specified in Equation 3 and Section 2.2 respectively. Since
$\Phi$ is equivariant, we have

$\displaystyle\Phi(f^{\prime})=\Phi(\pi(u)f)=u\cdot\Phi(f)=u\cdot
pK=p^{\prime}K$ (17)

Recall that $\bar{p}^{\prime-1}u\bar{p}=k_{up}k_{p}^{-1}$ from Section D.1.
Hence $\bar{p}^{\prime-1}=k_{up}k_{p}^{-1}\bar{p}^{-1}u^{-1}$ and we have

$\displaystyle[\pi(\bar{p}^{\prime-1})f^{\prime}]{\downarrow}_{K}^{G}$
$\displaystyle=[\pi(k_{up}k_{p}^{-1}\bar{p}^{-1}u^{-1})f^{\prime}]{\downarrow}_{K}^{G}$
$\displaystyle=\pi(k_{up}k_{p}^{-1})[\pi(\bar{p}^{-1})\pi(u^{-1})f^{\prime}]{\downarrow}_{K}^{G}$
$\displaystyle=\pi(k_{up}k_{p}^{-1})[\pi(\bar{p}^{-1})f]{\downarrow}_{K}^{G}$
$\displaystyle=\pi(k_{up}k_{p}^{-1})f_{b}=f^{\prime}_{b}$ (18)

From Equations 17 and D.2, $S_{b}{\downarrow}_{K}^{G}$ is equivariant, i,e.

$\displaystyle\pi^{\prime}(u)S_{b}{\downarrow}_{K}^{G}(f;\Phi)=S_{b}{\downarrow}_{K}^{G}(\pi(u)f;\Phi)$

For the upsampling operation, let
$[f^{\prime}_{1},p^{\prime}_{1}K]=\pi^{\prime}(u)[f_{1},p_{1}K]$ and
$f^{\prime}_{u}=\pi(u)f_{u}$. From Section 2.2 we have
$f^{\prime}_{1}=\pi(\bar{p}^{\prime-1}u\bar{p})f_{1}$. Hence

$\displaystyle S_{u}{\uparrow}_{K}^{G}(f^{\prime}_{1},p^{\prime}K)$
$\displaystyle=\pi(\bar{p}^{\prime})f^{\prime}_{1}{\uparrow}_{H}^{G}$
$\displaystyle=\pi(\bar{p}^{\prime})[\pi(\bar{p}^{\prime-1}u\bar{p})f_{1}]{\uparrow}_{H}^{G}$
$\displaystyle=\pi(\bar{p}^{\prime})\pi(\bar{p}^{\prime-1}u\bar{p})(f_{1}{\uparrow}_{H}^{G})$
$\displaystyle=\pi(u\bar{p})f_{1}{\uparrow}_{H}^{G}=\pi(u)f_{u}=f^{\prime}_{u}$

Therefore, $S_{u}{\uparrow}_{K}^{G}$ is equivariant, i.e.

$\displaystyle\pi(u)S_{u}{\uparrow}_{K}^{G}([f_{1},p_{1}K])=S_{u}{\uparrow}_{K}^{G}(\pi^{\prime}(u)[f_{1},p_{1}K])$

∎

###  D.3 Proof of Proposition B.1 (See page B.1)

See B.1

###### Proof.

Firstly, we prove that $\nu^{-1}\circ\nu$ is an identity map, i.e.
$\nu^{-1}\circ\nu=\mathds{1}_{z}$. Let
$r_{\text{eq}}=\nu(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})=(\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{L})G_{L}$
and
$(p^{\prime}_{1}G_{1},p^{\prime}_{2}G_{2},\dots,p^{\prime}_{L}G_{L})=\nu^{-1}(r_{\text{eq}})$.
From Section B.2, we know that $p^{\prime}_{1}G_{L}=r_{\text{eq}}$. Hence we
can let $p^{\prime}_{1}=\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{L}g_{L}$ where
$g_{L}\in G_{L}$. Since $(\bar{p}_{2}\bar{p}_{3}\dots\bar{p}_{L})\in G_{1}$,
for $l=1$ we have

$\displaystyle\bar{p}^{\prime}_{1}$ $\displaystyle=\bar{p}_{1}$ $\displaystyle
p^{\prime}_{2}=\bar{p}_{1}^{\prime-1}\cdot p^{\prime}_{1}$
$\displaystyle=\bar{p}_{2}\bar{p}_{3}\dots\bar{p}_{L}g_{L}$

And recursively, for $l=1,\dots,L$ we would have

$\displaystyle\bar{p}^{\prime}_{l}$ $\displaystyle=\bar{p}_{l}$ $\displaystyle
p^{\prime}_{l+1}$ $\displaystyle=\bar{p}_{l+1}\dots\bar{p}_{L}g_{L}$

Hence
$(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})=(p^{\prime}_{1}G_{1},p^{\prime}_{2}G_{2},\dots,p^{\prime}_{L}G_{L})$
and $\nu^{-1}\circ\nu=\mathds{1}_{z}$.

Secondly, we prove that $\nu\circ\nu^{-1}$ is also an identity map, i.e.
$\nu\circ\nu^{-1}=\mathds{1}_{r}$. Let
$(p^{\prime}_{1}G_{1},p^{\prime}_{2}G_{2},\dots,p^{\prime}_{L}G_{L})=\nu^{-1}(r_{\text{eq}})$
and
$r^{\prime}_{\text{eq}}=\nu(p^{\prime}_{1}G_{1},p^{\prime}_{2}G_{2},\dots,p^{\prime}_{L}G_{L})$.
From Section B.2, we have $r_{\text{eq}}=p^{\prime}_{1}G_{L}$ and
$p^{\prime}_{l}=\bar{p}_{l-1}^{\prime-1}\cdot p_{l-1}$. Hence

$\displaystyle r_{\text{eq}}$
$\displaystyle=p^{\prime}_{1}G_{L}=\bar{p}^{\prime}_{1}p^{\prime}_{2}G_{L}=\cdots=\bar{p}^{\prime}_{1}\bar{p}^{\prime}_{2}\dots\bar{p}^{\prime}_{L-1}p^{\prime}_{L}G_{L}=\bar{p}^{\prime}_{1}\bar{p}^{\prime}_{2}\dots\bar{p}^{\prime}_{L}G_{L}=r^{\prime}_{\text{eq}}$

Therefore $\nu\circ\nu^{-1}=\mathds{1}_{r}$ and $\nu$ is bijective.

Lastly, we prove $\nu$ is equivariant. Let
$(p^{\prime}_{1}G_{1},p^{\prime}_{2}G_{2},\dots,p^{\prime}_{L}G_{L})=u\cdot(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})$
where the group action is implied by Section 2.2. From Section D.1, we know
that when $u\in G$, $\pi(\bar{p}_{1}^{\prime-1}u\bar{p}_{1})\in G_{1}$.
Recursively, we have

$\displaystyle\bar{p}_{l}^{\prime-1}\dots\bar{p}_{2}^{\prime-1}\bar{p}_{1}^{\prime-1}u\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{l}\in
G_{l}$ (19)

for $l=1,\dots,L$. When $l=L$, from
$\bar{p}_{L}^{\prime-1}\dots\bar{p}_{2}^{\prime-1}\bar{p}_{1}^{\prime-1}u\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{l}\in
G_{L}$, we have

$\displaystyle\bar{p}^{\prime}_{1}\bar{p}^{\prime}_{2}\dots\bar{p}^{\prime}_{L}G_{L}=u\cdot(\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{L}G_{L})$

Hence
$u\cdot\nu(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L})=\nu(u\cdot(p_{1}G_{1},p_{2}G_{2},\dots,p_{L}G_{L}))$.
So that the group action given by Section 2.2 is simplified to the left-action
on the single group element. ∎

###  D.4 Proof of Proposition 3.1 (See page 3.1)

See 3.1

###### Proof.

Let $f,f^{\prime}\in\mathcal{I}_{G}$ be the input feature maps where
$f^{\prime}=\pi(g)f$. Let $[f_{l},\;p_{l}G_{l}]$ and
$[f^{\prime}_{l},\;p^{\prime}_{l}G_{l}]$ be the feature maps and subsampling
indexes output by the $l$-th subsampling layer for $f$ and $f^{\prime}$
respectively. Let
$[z_{\text{inv}},z_{\text{eq}}]=\operatorname{\textsc{enc}}(f)$ and
$[z^{\prime}_{\text{inv}},z^{\prime}_{\text{eq}}]=\operatorname{\textsc{enc}}(f^{\prime})$
and let $r_{\text{eq}}=\nu(z_{\text{eq}})$,
$r^{\prime}_{\text{eq}}=\nu(z^{\prime}_{\text{eq}})$ where $\nu$ is given in
Equation 13.

From Section 2.2 and the equivariance of
$\operatorname{\textsc{g-cnn}}_{l}(\cdot)$, we have

$\displaystyle f^{\prime}_{1}=\pi(\bar{p}_{1}^{\prime-1}g\bar{p}_{1})f_{1}$

and recursively:

$\displaystyle
f^{\prime}_{l}=\pi((\bar{p}^{\prime}_{1}\bar{p}^{\prime}_{2}\dots\bar{p}^{\prime}_{l})^{-1}g(\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{l}))f_{l}$
(20)

where $l=1,\dots,L$ and
$(\bar{p}^{\prime}_{1}\bar{p}^{\prime}_{2}\dots\bar{p}^{\prime}_{l})^{-1}g(\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{l})\in
G_{l}$ (see Equation 19).

Since $G_{L}=\\{e\\}$ when $l=L$, we have

$\displaystyle(\bar{p}^{\prime}_{1}\bar{p}^{\prime}_{2}\dots\bar{p}^{\prime}_{L})^{-1}g(\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{L})=e$

Hence

$\displaystyle f^{\prime}(e)$ $\displaystyle=f(e)$
$\displaystyle(\bar{p}^{\prime}_{1}\bar{p}^{\prime}_{2}\dots\bar{p}^{\prime}_{L})$
$\displaystyle=g\cdot(\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{L})$

which can be rewritten as

$\displaystyle z^{\prime}_{\text{inv}}$ $\displaystyle=z_{\text{inv}}$
$\displaystyle r^{\prime}_{\text{eq}}$ $\displaystyle=g\cdot r_{\text{eq}}$

From Proposition B.1 we have

$\displaystyle
z^{\prime}_{\text{eq}}=\nu^{-1}(r^{\prime}_{\text{eq}})=\nu^{-1}(ur_{\text{eq}})=g\cdot\nu^{-1}(r_{\text{eq}})=g\cdot
z_{\text{eq}}$

Therefore, for the encoders we have $[z_{\text{inv}},g\cdot
z_{\text{eq}}]=\operatorname{\textsc{enc}}(\pi(g)f)$.

For the decoders, let

$\displaystyle z^{\prime}_{\text{eq}}$
$\displaystyle=(p^{\prime}_{1}G_{1},p^{\prime}_{2}G_{2},\dots,p^{\prime}_{L}G_{L})=g\cdot
z_{\text{eq}}$

Since the feature map at the $l$-th subsampling layer is transformed according
to Equation 20, the sampling index is transformed accordingly:

$\displaystyle
p^{\prime}_{l}G_{l}=(\bar{p}_{l-1}^{\prime-1}\dots\bar{p}_{2}^{\prime-1}\bar{p}_{1}^{\prime-1}g\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{l-1})p_{l}G_{L}$

fFrom the definition of equivariant upsampling in Section 2.2, we have

$\displaystyle
f^{\prime}_{l-1}=\pi(\bar{p}_{l-1}^{\prime-1}\dots\bar{p}_{2}^{\prime-1}\bar{p}_{1}^{\prime-1}g\bar{p}_{1}\bar{p}_{2}\dots\bar{p}_{l-1})f_{l-1}$

where $l=L,\dots,1$. When $l=1$, we have $f^{\prime}_{0}=\pi(g)f_{0}$ so that
$\pi(g)\hat{f}=\operatorname{\textsc{dec}}(z_{\text{inv}},g\cdot
z_{\text{eq}})$.

∎

##  Appendix E Implementation Details

In this section, we outline a few important implementation details, and leave
other details to the reference code at
https://github.com/jinxu06/gsubsampling.

###  E.1 Data

For Colored-dSprites and FashionMNIST datasets, we add colours to grayscale
images from [35] and [49] by sampling random scaling for each channel
uniformly between $0.5$ and $1$ following [31]. For FashionMNIST, we also
apply zero-paddings to images to reach the size of $64\times 64$. We then
translate the images with random displacements uniformly sampled from
$\\{(x,y)|-18\leq x,y\leq 18,x,y\in\mathbb{Z}\\}$, and rotate the images with
uniformly sampled degrees from $\\{\frac{360\times k}{32}|k=0,\dots,32\\}$. We
use the original Multi-dSprites dataset as provided in [26]. For CLEVR6, we
crop images from the original CLEVR [25] at y-coordinates $(29,221)$ bottom
and top, and at x-coordinates $(64,256)$ left and right as stated in [2]. We
then resize the images to $64\times 64$ so that we can use the same model for
both multi-object datasets. We only use images with up to $6$ objects in CLEVR
following [19]. For evaluation, we use a randomly sampled test set with
$10000$ examples that has no overlap with training data for all datasets. In
Figure 6, we show examples from different datasets.

(a) Colored-dSprites

(b) FashionMNIST

(c) Multi-dSprites

(d) CLEVR6

Figure 6:

###  E.2 Model Architectures

#### The equivariant map $\Phi$

One can insert arbitrary equivariant layers before and after we take the norm
$\|\cdot\|_{1}$ in Equation 7. In experiments, we apply mean subtraction
followed by average pooling with kernel size $5$ before taking the norm, and
apply Gaussian blur with kernel size $15$ after taking the norm. They are
inserted in the purpose of smoothing feature maps and avoiding non-unique
argmax when possible (in Section B.1 we discuss the case when non-unique
argmax cannot be avoided). In practice, we use Equation 15 to obtain all
subsampling indexes at the same time rather than passing through $\Phi$
multiple times.

#### Autoencoders

For all single object experiments, we use $5$ layers of ($G$-)equivariant
convolutional layers in encoders, and the decoders mirror the architecture of
the encoders except for the output layers. In baseline models, we use strided
convolution as a way to perform subsampling/upsampling, while in equivariant
models we use equivariant downsampling/upsampling. We rescale the number of
channels such that the total number of parameters of the models roughly match
one another. However, exact correspondence is not achievable because exact
equivariant models use equivariant subsampling to transform feature maps into
vectors at the final layer of the encoder, while baseline models apply
flattening. Please see the reference implementation for other details about
network architectures.

We use scale factor $2$ for all subsampling and upsampling layers in baseline
models. For GAE-$p1$, the feature maps at each layer are defined on the
following chain of nested subgroups:
$\mathbb{Z}^{2}\geq(2\mathbb{Z})^{2}\geq(4\mathbb{Z})^{2}\geq(8\mathbb{Z})^{2}\geq(16\mathbb{Z})^{2}\geq\\{e\\}$.
For For GAE-$p4$, we use
$\mathbb{Z}^{2}\rtimes\mathsf{C}_{4}\geq(2\mathbb{Z})^{2}\rtimes\mathsf{C}_{4}\geq(4\mathbb{Z})^{2}\rtimes\mathsf{C}_{4}\geq(8\mathbb{Z})^{2}\rtimes\mathsf{C}_{4}\geq(16\mathbb{Z})^{2}\rtimes\mathsf{C}_{2}\geq\\{e\\}$.
And for GAE-$p4m$, we use
$\mathbb{Z}^{2}\rtimes(\mathsf{C}_{4}\rtimes\mathsf{C}_{2})\geq(2\mathbb{Z})^{2}\rtimes(\mathsf{C}_{4}\rtimes\mathsf{C}_{2})\geq(4\mathbb{Z})^{2}\rtimes(\mathsf{C}_{4}\rtimes\mathsf{C}_{2})\geq(8\mathbb{Z})^{2}\rtimes(\mathsf{C}_{4}\rtimes\mathsf{C}_{2})\geq(16\mathbb{Z})^{2}\rtimes(\mathsf{C}_{2}\rtimes\mathsf{C}_{2})\geq\\{e\\}$.

#### Object discovery

For baseline models, we adopt the exact same architecture as the original
MONet [2] using the implementation provided by [13]. For MONet-GAEs, we simply
replace Component VAEs in the original MONet with our V-GAEs. Both Component
VAEs and V-GAEs have a latent size of $16$.

###  E.3 Hyperparameters

For all single object experiments, we use Adam optimizer [29] with a learning
rate of $0.0001$ and a batch size of $16$. We use $16$-bits precision to
enable faster training and reduce memory consumption. For experiments on
multi-object datasets, hyperparameters will match the original MONet [2]
except that we still use a batch size of $16$ instead of $64$ stated in the
original paper. This is because we observed that in the low data regime, batch
size $16$ trains faster and performs no worse than batch size $64$ for the
problems we considered here.

###  E.4 Computational Resources

In theory, the only computational overhead is caused by computing sampling
indices, which is negligible compared to the forward pass of
($G$-)Convolutional layers. In practice, our current implementation uses
torch.gather to perform subsampling, and relies on for-loops over data batches
when applying group actions to feature maps, which we believe can be made more
efficient. Hence on a single GeForce GTX $1080$ GPU card, a standard GAE-p1
takes around $30$ minutes to train for $100k$ steps, compared to $16$ minutes
for standard ConvAEs.


# An improved estimate of the inverse binary entropy function

Reginald D. Smith
Supreme Vinegar LLC
3430 Progress Dr. Suite D, Bensalem, PA 19020
<EMAIL_ADDRESS>
(May 5, 2020)

###### Abstract

Two estimates for the inverse binary entropy function are derived using the
property of information entropy to estimate combinatorics of sequences as well
as related formulas from population genetics for the effective number of
alleles. The second estimate shows close correspondence to the actual value of
the inverse binary entropy function and can be seen as a close approximation
away from low values of binary entropy where $p$ or $1-p$ are small.

##  1 The information entropy function

While the concept of entropy first originated in thermodynamics with the
German physicist Rudolf Clausius, it has reappeared and been reformulated in
similar ways across a wide variety of disciplines in science and mathematics.
Information entropy, first formulated by Claude Shannon in his seminal work on
information theory [Shannon(1948)], was derived as an expression to calculate
the capacity of a channel to transmit information given a discrete
distribution of states or symbols. Where there are $M$ symbols each with
probability $p_{k}$ for symbol, $k$, the information entropy, $H$, is defined
as

$H=-\sum_{k=1}^{M}-p_{k}\log p_{k}$ (1)

When the natural logarithm is used, the entropy is said to be measured in
‘nats’ but $\log_{2}$ is often used and entropy is said to be measured in
‘bits’ under this formulation. Where $M=2$, the entropy function is known as
the binary entropy function with a simplified expression of

$H=-p\log p-(1-p)\log(1-p)$ (2)

###  1.1 Entropy and combinatorics

Besides its nominal definition, entropy has a surprising and useful function
for determining the expected number of sequence combinations length $L$ for a
given distribution. In short, the expected number of sequences of length $L$,
$N(L)$ for a distribution with entropy $H$ is calculated as [Shannon &
Weaver(1959)]

$N(L)=e^{LH}$ (3)

###  1.2 The inverse binary entropy function

While the binary entropy is easily calculated from a distribution defined by a
Bernoulli trial, where the two possible outcomes occur with probabilities $p$
and $1-p$, calculating the inverse and finding the two values of $p$ and $1-p$
for a given value of entropy is a longstanding and unsolved problem. Despite
the simple expression of the binary entropy equation, it is unclear if a
closed form expression for the inverse, $H^{-1}(x)$ exists. Estimates have
been given such as lower and upper bounds [Calabro(2009)]. This paper will
present two estimates for the inverse entropy function, with the second being
most exact, derived using the combinatoric nature of entropy. The combinatoric
approach is inspired by formulations in population genetics where the expected
frequency of homozygous genotypes at a locus is used to estimate the expected
number of alleles at that locus; a concept analogous to that calculated in
equation 3.

###  1.3 Combinatorics and the genotype of a single locus

The key concerns of population genetics are describing and explaining the
nature of genetic variation within and between populations of the same species
and understanding the forces that affect these across generations of
inheritance. The typical starting unit of analysis is the locus, a unit of
genetic inheritance which (in diploid organisms) has two alleles, one received
from each parent, and is a discrete unit of inheritance whose basic laws were
first described by Gregor Mendel. Each allele in a locus can come in any
number of different types though often in theory and practice there are only
two common variants for the allele whose frequencies are designated as $p$ and
$q=1-p$. This is termed a bi-allelic locus.

There are many methods to measure the genetic diversity within a single
population or between two populations at one or multiple loci. For a single
bi-allelic locus, however, one of the simplest measures of genetic diversity
is to analyze its expected homozygosity (both alleles being identical) and
expected heterozygosity (both alleles being different). In bi-allelic loci,
under Hardy-Weinberg equilibrium which assumes random mating and no selection
on genotypes, the expected homozygosity for each allele variant are $p^{2}$
and $q^{2}$ and the expected heterozygosity is $2pq$.

Heterozygosity can be used as a proxy for diversity at a locus since its value
increases as the frequency of both alleles approaches 1/2. However, another
informative and more easily interpretable measure of locus diversity is the
effective number of alleles.

##  2 The effective number of alleles

###  2.1 Kimura-Crow formulation of effective number of
alleles

First derived by famed population geneticists Motoo Kimura and James Crow
[Kimura & Crow(1964)] the effective number of alleles, $N_{a}$ is simply the
inverse of the expected homozygosity at a locus.

$N_{a}=\frac{1}{p^{2}+q^{2}}=\frac{1}{p^{2}+(1-p)^{2}}$ (4)

The effective number of alleles is a measure of diversity at a bi-allelic
locus being a minimum 1 if one allele is fixed ($p$ or $q$ equals one) or a
maximum of 2 when diversity is at a maximum and $p=q=1/2$.

###  2.2 Inverse entropy estimate using Kimura-Crow
formulation

The effective number of alleles can be viewed as a combinatoric measure
analogous to $N$ for a sequence of length $L=1$ which is the effective number
of symbols given the entropy of a distribution. Therefore, we can
approximately equate $N(1)$ and $N_{a}$ using equations 3 and 4.

$e^{H}\approx\frac{1}{p^{2}+(1-p)^{2}}$ (5)

This allows us to derive an estimate for $p$ as

$H^{-1}(H)=p\approx\frac{1}{2}\pm\frac{1}{2}\sqrt{2e^{-H}-1}$ (6)

This is a rough approximation of both possible values of $p$ given the
entropy. However, as shown in Figures 1 and 2, it is only a good estimate at
the boundaries, where entropy is nearly zero, and near the maximum entropy
value of $\log 2$.

###  2.3 Improved estimate based on reduction from the
maximum possible effective number of symbols

Given the range of the effective number of symbols for $L=1$ from one to two,
another approach to estimate the effective number of symbols (alleles) is to
start with the maximum of 2 and reduce based on changes in $p$ that reflect
increased or decreased diversity. In short, increases in homozygosity reduce
diversity. Therefore, a modified expected number of symbols can be expressed
as

$N(1)\approx 2-p^{2}-(1-p)^{2}+2p(1-p)$ (7)

Using $N(1)=e^{H}$ we can then derive another estimate for inverse entropy

$H^{-1}(H)=p\approx\frac{1}{2}\pm\frac{1}{2}\sqrt{2-e^{H}}$ (8)

Figure 2, shows this is a much superior approximation with a difference of
less than 0.01 across all values and becoming nearly exact as entropy
approaches $\log 2$. Granted, the overall precision is reduced at low values
of $p$ or $1-p$ since the relative error is increased when entropy is small.

Figure 1: A graph of both branches of the inverse entropy function (points)
along with the estimate provided for by equation 6 (green) and the revised
derivation in equation 8 (black). Figure 2: Absolute value of error of
estimates of $H^{-1}$ based on the effective number of alleles derivation from
equation 6 (green) and the revised derivation in equation 8 (black).

##  3 Conclusion

This paper presents improved estimates for the inverse binary entropy
function. While neither is exact, the second estimate from equation 8 performs
very well for values of entropy significantly different from zero and could
feasibly be used in applications where approximations are acceptable.

##  4 References

## References

  * [Calabro(2009)] Calabro, C. [2009] “The Exponential Complexity of Satisfiability Problems”, Dissertation (Univesity of California, San Diego, USA).
  * [Kimura & Crow(1964)] Kimura, M., & Crow, J.F. [1964] “The number of alleles that can be maintained in a finite population.” Genetics 49, 725–738.
  * [Shannon(1948)] Shannon, C.E. [1948] “A mathematical theory of communication.” Bell system technical journal 27, 379–423.
  * [Shannon & Weaver(1959)] Shannon, C.E. & Weaver, W. [1959] The Mathematical Theory of Communication, 1st Ed. (University of Illinois Press, USA).