# Statistical Regeneration Guarantees of the Wasserstein Autoencoder with
Latent Space Consistency

Anish Chakrabarty
Statistics and Mathematics Unit
Indian Statistical Institute, Kolkata &Swagatam Das
Electronics and Communication Sciences Unit
Indian Statistical Institute, Kolkata

###### Abstract

The introduction of Variational Autoencoders (VAE) has been marked as a
breakthrough in the history of representation learning models. Besides having
several accolades of its own, VAE has successfully flagged off a series of
inventions in the form of its immediate successors. Wasserstein Autoencoder
(WAE), being an heir to that realm carries with it all of the goodness and
heightened generative promises, matching even the generative adversarial
networks (GANs). Needless to say, recent years have witnessed a remarkable
resurgence in statistical analyses of the GANs. Similar examinations for
Autoencoders, however, despite their diverse applicability and notable
empirical performance, remain largely absent. To close this gap, in this
paper, we investigate the statistical properties of WAE. Firstly, we provide
statistical guarantees that WAE achieves the target distribution in the latent
space, utilizing the Vapnik–Chervonenkis (VC) theory. The main result,
consequently ensures the regeneration of the input distribution, harnessing
the potential offered by Optimal Transport of measures under the Wasserstein
metric. This study, in turn, hints at the class of distributions WAE can
reconstruct after suffering a compression in the form of a latent law.

##  1 Introduction

Unsupervised data generation has been a time-hallowed problem in machine
learning theory. Though not its strongest suit, Variational Autoencoders (VAE)
[1] have been implemented for generative purposes to a great extent. Once
emerged as a crucial unsupervised method for representation learning, its poor
performances in this particular area somewhat depreciates its appeal. On the
contrary, generative adversarial networks (GANs) [2] have proven to be
superior when it comes to the quality of the generated image samples. The
theoretical elegance of the adversarial training method can be duly credited
for this achievement. In an attempt to adopt this merit, such ’adversarial
loss’ functions were incorporated into VAE objectives [3, 4]. The Wasserstein
metric, also being used in GANs [5] previously, was an inevitable choice,
since it brings along the beckoning of Transportation Theory. Using the same
to measure the reconstruction loss in a VAE, Wasserstein Autoencoder (WAE) [6]
was conceived. By approaching generative modeling from an Optimal Transport
(OT) point of view, it not only achieved remarkable reconstruction standards
but also strengthened the theoretical backbone.

An appropriate WAE framework consists of two components, namely an encoder
$(E)$ and a decoder $(D)$, which are represented by neural networks in
practice. Samples from an input distribution $(P_{X})$ are fed into the
encoder, which aims at resulting in a target law $(P_{Z})$ in the latent space
$(\mathcal{Z})$. The decoder deals with the reconstruction of the original
distribution from this ’encoded’ signal. Mathematically, the objective of WAEs
is to minimize $\mathcal{L}=\mathcal{R}(D,E)+\Omega(E)$ over the set of
probabilistic encoders $E$. Here, $\mathcal{R}()$ ensures the reconstruction
of samples put in whereas, $\Omega()$ ensures the attainment of the latent
distribution. Needless to say, $\mathcal{R}()$ is represented by the
Wasserstein discrepancy.

As the name suggests, our primary interest lies in investigating whether a
suitably characterized WAE can learn a distribution, which represents its
latent behaviour, without losing the memory of the initial signal it was fed.
When it comes to memorizing the input distribution in the form of
reconstruction, theoretical guarantees for adversarial training, in the
context of GANs, have been provided rigorously. In the absence of a flexible
discriminator, WAEs need more care and closer observation. Moreover, the
concurrent task of sculpting a desired latent distribution adds nuances to its
mechanism. Most of the existing literature on deep generative models, under
adversarial loss, misses out on this very point. Against such a backdrop, this
first of its kind study substantiates the simultaneous performances of WAE,
from a theoretical viewpoint.

Our analysis starts with a special family of WAEs, namely f-Wasserstein
Autoencoders (f-WAE) [7], which arises due to the specific choice of
$\Omega()$ as f-divergences (1). We follow a non-parametric approach in
defining both the networks involved and the distributions under consideration.
The transformations induced by the encoder and the decoder are conceived as
measurable functions between spaces. The nature of an ‘ideal’ encoder in our
language, is a network that preserves information. Whereas, the decoder is
characterized by a map that propagates the information retained, precisely.
Our statistical assumptions on the same reflect these very ideas. As a result,
the two concurrent objectives of f-WAE boil down to non-parametric estimation
of laws, under vastly different circumstances.

Our major findings can be summarized in the following way,

  * •

Given a non-negative margin of error, f-WAEs can learn latent space
distributions with a convergence rate of $\mathcal{O}(n^{-\frac{1}{2}})$,
under fairly gentle assumptions on the input and target law (1). The proof
involves a realistic characterization of the transformation, induced by the
encoder network.

  * •

Under a geometry preserving representation of the decoder map, Hölder
densities can be successfully reconstructed by f-WAEs up to a constant margin
(2). Our work also produces deterministic concentration bounds on the
regeneration error and hence, the rate of convergence of the empirical laws.

  * •

A particular instance of our analysis goes on to show that the input
distribution converges strongly to its latent counterpart under encoding, in
the form of empirical measures. Also, f-WAEs can exactly reproduce samples
from smooth densities in the sense of weak convergence (Remark).

  * •

Inferences, identical to that in case of f-WAE, can be drawn for the original
WAE [6], under additional assumptions on the decoder (2).

##  2 Related Work

In recent times, scrutiny of the empirical achievements of deep generative
models from a theoretical point of view has gained great momentum. GANs [2],
being at the helm, have received most of the attention [8, 9]. Possibly, the
cornerstone of success for a GAN lies in its adversarial training and the
accompanying loss functions. A plethora of GAN variants have been devised by
incorporating different losses, such as Wasserstein distance (WD) [5],
f-divergence [10], Maximum Mean Discrepancy [11] and Sobolev distances [12],
to name a few. The generative aspect, in particular, has attracted a lot of
research in the form of distributional estimation studies [13, 14].
Additionally, [15] has proved weak convergence of distributions under several
of the aforementioned adversarial losses. In a recent study, [16] has also
discussed the convergence of the empirical measures in the case of WGAN, under
parametrized network assumptions. VAEs, despite being used vastly as
generative tools, have not experienced such a level of independent theoretical
investigation, which comprehends its latent space mechanism.

In a novel approach to unify the deep generative techniques, Adversarial AEs
[3] were introduced. Subsequent work to establish resemblance [17, 4], has
only strengthened that foundation. Eventually, the formulation of WAE [6]
bridged the gap significantly by matching regeneration standards. The
equivalence in performance is a direct reflection of the similarity of its
objective to that of GANs’ [7]. This ’primal-dual relationship’ prepares a
basis to explore the generative facets of WAE, in particular, now with the
collective experience provided by GANs.

Typically, WD serves as the measure of discrepancy used to represent the
reconstruction loss in WAEs. Non-parametric density estimation under this
metric has seen the establishment of minimax bounds based on covering numbers,
under fairly general assumptions [18, 19]. The same has also been achieved by
[20], for unbounded metric spaces, assuming that some moments are finite.
Singh et al. [21] established minimax convergence rates in the same context,
under smoothness assumptions on the networks employed in the generation.
Despite being influential in their own ways, none of the above aim at
discussing the coinciding objectives of WAEs. In a recent empirical study,
Diffusion VAE [22] was introduced, which attempts at capturing arbitrary
latent manifolds using kernels of Brownian motion. However, without precise
conceptual insight. As such, the theoretical questions regarding the parallel
machinery of WAEs remain largely unanswered. Our analysis is a humble attempt
at filling this void of statistical understanding.

##  3 Preliminaries

###  3.1 Notations

We start with denoting the input space by $\mathcal{X}$, which can be assumed
to be Polish (i.e., separable and completely metrizable). We will use
$\mathcal{Z}$ for the latent space. Both may be thought of as Euclidean
spaces, since it is a typical characterization. The space of probability
measures (distributions) defined on $\mathcal{X}$ is denoted by
$\mathscr{P}(\mathcal{X})$. The set of all measurable functions from
$\mathcal{X}$ to $\mathcal{Z}$ is refered to as
$\mathscr{F}(\mathcal{X},\mathcal{Z})$. For example, observe that a
probabilistic encoder $E$ belongs to
$\mathscr{F}(\mathcal{X},\mathscr{P}(\mathcal{Z}))$. For any function
$T\mathrel{\mathop{\ordinarycolon}}\mathcal{X}\rightarrow\mathcal{Z}$, we
denote the pushforward measure of $\mu$ as
$T_{\\#}\mu\in\mathscr{P}(\mathcal{Z})$, i.e. for any measurable set
$\omega\subset\mathcal{Z}$ we have
$T_{\\#}\mu(\omega)=\mu(\\{x\in\mathcal{X}\mathrel{\mathop{\ordinarycolon}}T(x)\in\mathcal{Z}\\})=\mu(T^{-1}(\omega))$.
To denote absolute continuity of a measure $\mu$ with respect to $\lambda$, we
use the notation $\mu\ll\lambda$. The Support of $\mu$ is denoted by
$Supp(\mu)$. To indicate the Closure of $\mathcal{X}$ we use
$\bar{\mathcal{X}}$ and $Int(\mathcal{X})$ denotes the set of its Interior
Points. Given $\mathcal{S}\subseteq\mathcal{X}$, the $\mathcal{S}$-distance
between a pair of functions $f$ and $g$ is given by,
$\;\mathinner{\\!\left\lVert
f-g\right\rVert}_{\mathcal{S}}=\sup_{x\in\mathcal{S}}\mathinner{\\!\left\lvert
f(x)-g(x)\right\rvert}$. When the $\sup$ is taken over the whole space, we
call it the uniform norm. The total variation distance between probability
measures $\mu$ and $\gamma\in\mathscr{P}(\mathcal{X})$ is denoted by
$\mathinner{\\!\left\lVert\mu-\gamma\right\rVert}_{TV}$. Now we introduce some
useful concepts that are made use of later.

######  Definition 1 (f-Divergence).

Let $P,Q\in\mathscr{P}(\mathcal{X})$ such that $P\ll Q$. For a convex function
$f$ with $f(1)=0$, the f-divergence of $P$ from $Q$ is defined as

$D_{f}(P,Q)=\int_{\mathcal{X}}f\Big{(}\frac{dP}{dQ}\Big{)}dQ.$

######  Definition 2 (Yatracos Family [23]).

For a class of real-valued functions $\mathcal{F}$, defined on $\mathcal{Z}$,
the Yatracos family associated to $\mathcal{F}$ is a collection of subsets of
$\mathcal{Z}$ defined as

$\mathcal{Y}(\mathcal{F})=\\{x\in\mathcal{Z}\mathrel{\mathop{\ordinarycolon}}f(x)\geq
g(x);\;f,g\in\mathcal{F}\\}.$

######  Definition 3 (Empirical Yatracos Minimizer [24]).

The Empirical Yatracos Minimizer is a function
$\mathcal{L}^{\mathscr{P}(\mathcal{Z})}\mathrel{\mathop{\ordinarycolon}}\bigcup\limits^{\infty}_{n=1}\mathcal{Z}^{n}\longrightarrow\mathscr{P}(\mathcal{Z})$
defind as

$\mathcal{L}^{\mathscr{P}(\mathcal{Z})}_{n}=\operatorname*{argmin}_{q\in\mathscr{P}(\mathcal{Z})}\>{\mathinner{\\!\left\lVert
q-\hat{p}_{n}\right\rVert}}_{\mathcal{Y}(\mathscr{P}(\mathcal{Z}))},$

where $\hat{p}_{n}$ is an empirical distribution based on a sequence of
observations $\\{Z_{i}\\}^{n}_{i=1}$ from $\mathcal{Z}$.

######  Definition 4 ($\epsilon$-Closeness).

A pair of distributions $f,g\in\mathscr{P}(\mathcal{X})$ are said to be
$\epsilon$-close to each other with respect to the metric c if
$c(f,g)\leq\epsilon$.

######  Definition 5 (Quasi-Isometric Embedding).

A map
$f\mathrel{\mathop{\ordinarycolon}}(\mathcal{Z},d_{1})\longrightarrow(\mathcal{X},d_{2})$
is called a quasi-isometric embedding if there exists a constant $A\geq 1$
such that,

$\frac{1}{A}d_{1}(x,y)\leq d_{2}(f(x),f(y))\leq
Ad_{1}(x,y)\;\>\forall\>x,y\in\mathcal{Z}.$

######  Definition 6 (Covering Number [18]).

Let $S\subseteq\mathcal{X}$. Then, the minimum integer $m$ such that there
exists $m$ closed balls $\\{B_{i}\\}^{m}_{i=1}$ of diameter $\epsilon$ each
$\ni S\subseteq\bigcup_{1\leq i\leq m}B_{i}$, is called the
$\epsilon$-covering number of $S$. We denote it by
$\mathcal{N}_{\epsilon}(S)$.

###  3.2 Wasserstein Duality: A Brief Exposition

The equivalence relation between Wasserstein Distance and Integral Probability
Metrics (IPMs) [25] is a fairly well-studied topic in optimal transport
theory. We exploit this fact to serve our purpose. For a detailed elucidation
on this subject, one may take refuge in [26, 27].

Let $P,Q\in\mathscr{P}(\mathcal{X})$ and
$c\mathrel{\mathop{\ordinarycolon}}\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq
0}$ forms a metric. Then,

$\displaystyle W_{c}(P,Q)=$
$\displaystyle\inf_{\gamma\in\Gamma(P,Q)}\Big{\\{}\int_{\mathcal{X}\times\mathcal{X}}c(x,y)d\gamma(x,y)\Big{\\}}$
$\displaystyle=$
$\displaystyle\sup_{l\in\mathscr{L}^{1}_{c}}\Big{\\{}\int_{\mathcal{X}}l(x)dP(x)-\int_{\mathcal{X}}l(x)dQ(x)\Big{\\}}=\textrm{IPM}_{\mathscr{L}^{1}_{c}}(P,Q),$

where
$\Gamma(P,Q)=\big{\\{}\gamma\in\mathscr{P}({\mathcal{X}\times\mathcal{X}})\mathrel{\mathop{\ordinarycolon}}\int_{\mathcal{X}}\gamma(x,y)dy=P,\;\int_{\mathcal{X}}\gamma(x,y)dx=Q\big{\\}}$
denotes the coupling between $P$ and $Q$. The class of 1-Lipschitz functions
with respect to the metric $c$ is represented by $\mathscr{L}^{1}_{c}$. Later
in the study however, we will use the notation $d_{\mathscr{L}^{1}_{c}}$ for
Wasserstein metric, for clarity.

###  3.3 Problem Setup

A typical WAE architecture intends to solve the minimization problem,

$\textrm{WAE}_{c,\lambda}(P_{X},D)=\inf_{E\in\mathscr{F}(\mathcal{X},\mathscr{P}(\mathcal{Z}))}\Big{\\{}\int_{\mathcal{X}}\mathbb{E}_{z\sim
E(x)}[c(x,D(z))]dP_{X}(x)+\lambda.\Omega(E_{\\#}P_{X},P_{Z})\Big{\\}},$ (1)

where
$c\mathrel{\mathop{\ordinarycolon}}\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq
0}$ and $\lambda>0$ serves as a hyperparameter. Arbitrary divergence metrics
between measures, belonging to $\mathscr{P}(\mathcal{Z})$, are deployed in the
form of $\Omega$. In this paper however, we modify this formulation to
facilitate theoretical analyses. The reshaped objective that our study is
based on is given by,

$f\textrm{-WAE}_{c,\lambda}(P_{X},D)=\inf_{E\in\mathscr{F}(\mathcal{X},\mathscr{P}(\mathcal{Z}))}\Big{\\{}W_{c}(P_{X},(D\circ
E)_{\\#}P_{X})+\lambda.D_{f}(E_{\\#}P_{X},P_{Z})\Big{\\}}.$ (2)

This category of AEs are called f-Wasserstein Autoencoders [7]. The key
difference between this family and the ordinary WAE arises due to the choice
of the reconstruction loss. This alteration, however, does not impact the
characterization significantly. Equivalence between these two systems can be
attained by imposing mild restrictions on the decoder transformation, which we
elaborate on at a later stage. As such, this can be marked as a valid
foundation to work on.

Observe that, the regularizer metric used in (2), to measure the discrepancy
between the target latent distribution and the encoded signal is taken to be
$D_{f}$. In this analysis, our specific choice of f-Divergence is Total
Variation Distance (TV). Its rich theoretical appeal motivates us to do so. TV
as a measure of deviation is symmetric with respect to the distributions under
consideration. Moreover, it can pose both as a f-Divergence and an IPM [28].
The original WAE, in one of its characterizations, uses Jensen–Shannon
divergence (JS) to penalize the loss instead [6]. TV, on the other hand, acts
as an upper bound to JS [29], which also justifies our choice.

######  Remark.

WAEs act as a generalization to AAEs. We stress on the fact that, a specific
choice of $c$ as $L_{2}^{2}$ in (1), establishes an equivalence between the
two [6]. Keeping that in mind, our analysis does not restrict the choice of
$c$ and hence can also cater to the theory of AAEs.

##  4 Theoretical Analysis

Before moving forward, let us rewrite the minimization problem (2) in the so-
called constrained form

$\inf_{E\in\mathscr{F}(\mathcal{X},\mathscr{P}(\mathcal{Z}))}\big{\\{}W_{c}(P_{X},(D\circ
E)_{\\#}P_{X})\big{\\}}\,\,\>\textrm{subject
to}\,\>D_{f}(E_{\\#}P_{X},P_{Z})\leq t,$ (3)

for some $t\geq 0$. By Lagrangian duality [30], for every value of $t$ where
the constraint $D_{f}(E_{\\#}P_{X},P_{Z})\leq t$ holds, there exists a value
of $\lambda$ that produces the same solution from (2). Conversely, the
solution to the problem (2), say $\hat{E}$ also solves the bound version with
$t=D_{f}(\hat{E}_{\\#}P_{X},P_{Z})$. As such, there is an one-to-one
correspondence between the constrained problem (3) and the Lagrangian one (2).
This formulation gives us a direction to move ahead to establish regeneration
guarantees and consistency of measures in the latent space.

Our analysis consists of two stages, going forward. Firstly we show that
probabilistic encoders can successfully transform input densities into
realistically characterized latent space laws, under TV distance, up to a
constant margin of error. The mild assumptions imposed in the process are
fairly practical. Once the constraint of the minimization problem is met in
the form of latent space consistency, we provide deterministic upper bounds to
the empirical reconstruction loss.

Throughout our discussion, we denote with $\mu\in\mathscr{P}(\mathcal{X})$ the
input data distribution. The target distribution which characterizes the
latent space is denoted by $\rho$. For simplicity, we assume that both $\mu$
and $\rho$ happen to have corresponding densities, namely $p_{\mu}$ and
$p_{\rho}$ with respect to the Lebesgue measure $\lambda$, in their respective
spaces. Both densities need explicit characterization, which we state in the
form of certain assumptions.

######  Assumption 1.

$p_{\mu}$, (i) based on a compact and convex support is (ii) bounded away from
0 by a constant factor $c>0$, i.e. $\inf_{x}p_{\mu}(x)\geq c$.

######  Assumption 2.

$p_{\rho}$, (i) also defined on a compact support, is easy-to-sample-from and
(ii) infinitely smooth, i.e. $p_{\rho}\in C^{\infty}(\mathcal{Z})$.

The input density being far from nullity, passes on the same nature to the
reconstructed law, even under near ideal situations. This poses as a measure
to prevent the regenerated law from being a degenerated one, at zero. We point
out that, in the non-parametric approach of this work, we often use empirical
distributions corresponding to $\rho$, which are based on observations from
the same. In high-dimensional statistics, there are distributions from which
it is practically not feasible to draw samples. For example, the drawing of
uniform samples from a high dimensional unit sphere. Although in our analysis,
the need for such samples is strictly theoretical and the practical
feasibility is somewhat immaterial, we describe $\rho$ this way to avoid
complication. Given these assumptions, suppose the ‘encoded’ pushforward
measure $E_{\\#}\mu\in\mathscr{P}(\mathcal{Z})$ has density $p_{E_{\\#}\mu}$.
Then, every such $p_{E_{\\#}\mu}$ is a potential candidate to represent
$p_{\rho}$. However, our analysis does not assume the existence of a density.
We denote $Supp(p_{\rho})$ by $\mathcal{C}$ such that,

######  Assumption 3.

$\textrm{VC-dim}[\mathcal{Y}(\mathscr{P}(\mathcal{C}))]$ is finite.

This assumption too is very much plausible in its own right. For example, let
$\mathcal{G}_{d}$ and $\mathcal{A}_{d}$ denote the class of d-dimensional
Gaussian distributions and the class of d-dimensional axis-aligned Gaussian
distributions respectively. It can be shown that, $\textrm{VC-
dim}[\mathcal{Y}(\mathscr{P}(\mathcal{G}_{d}))]=\mathcal{O}(d^{2})$ and
$\textrm{VC-dim}[\mathcal{Y}(\mathscr{P}(\mathcal{A}_{d}))]=\mathcal{O}(d)$
[31]. The introduction of Yatracos class of distributions, in turn,
facilitates the search for the minimum distance estimate of a measure. For a
detailed exposition on the same, one may turn to [24].

Perhaps the most challenging of tasks in studying the theoretical aspects of
deep neural networks lies in their basic characterization. Several depictions
of networks as a collection of functions, indexed by parametric classes have
produced notable results in the past [9, 13]. This paper rather explores the
mathematical properties a network has to embody to function in a WAE system.
The following representation of an encoder map reflects our motivation. We
consider an $E\in\mathscr{F}(\mathcal{X},\mathscr{P}(\mathcal{Z}))$ such that,

######  Assumption 4.

(i) $E_{\\#}\mu$ is supported on $\mathcal{C}$ and is also easy to draw
samples from.

(ii) Given any arbitrary empirical measure $\hat{\mu}_{n}$ (based on $n$
samples) corresponding to $\mu$, there exists an empirical counterpart
$\widehat{(E_{\\#}\mu)}_{n}$ of $E_{\\#}\mu$ which is $\epsilon$-close to
$\hat{\mu}_{n}$ under E, with probability at least
$1-k\exp\\{-n^{r}\epsilon^{2}\\}$, where $r\geq 1$ and $k\geq 0$. In other
words, $\mathbb{P}\Big{(}\mathinner{\\!\left\lVert
E_{\\#}{\hat{\mu}_{n}}-\widehat{(E_{\\#}\mu)}_{n}\right\rVert}_{TV}\leq\epsilon\Big{)}\geq
1-k\exp\\{-n^{r}\epsilon^{2}\\}$.

Part (ii) of Assumption (4) is provided only to give coherence to the
definition of $E$. It suggests that the probability of the discrepancy between
the two quantities involved decreases exponentially with the r-th power of
$n$. As such, if one has a superlinear rate of increment in information in the
form of samples, the portion lost in transition decays sharply. This embodies
our idea of an encoder, that preserves information. It is often seen in
practice that AEs, with ReLU encoders, are able to reconstruct images
accurately, despite having the encoded observations to be almost degenerate.
In such a case, the two measures under consideration can always be said to be
arbitrarily close. Part (ii) is a gentler approximation of the same idea. We
now present the main result that enables one to prove consistency in
estimating the latent space distribution.

######  Theorem 1.

Let, $\widehat{(E_{\\#}\mu)}_{n}$ stands for an empirical measure based on
$n\geq 1$ i.i.d. samples from $E_{\\#}\mu$. Then, under assumptions [1(i),
2(i), 4(i)], for positive constants $c_{1},c_{2},c_{3}$ and $\delta\in(0,1)$
there exists $\lambda^{*}\geq 0$ such that,

$\mathinner{\\!\left\lVert\rho-\widehat{(E_{\\#}\mu)}_{n}\right\rVert}_{TV}-\lambda^{*}\leq\frac{1}{\sqrt{n}}\Big{\\{}c_{1}\sqrt{v}+c_{2}\sqrt{\ln{\big{(}\frac{c_{3}}{\delta}\big{)}}}\Big{\\}}$

holds with probability $\geq 1-\delta$, where $v=\textrm{VC-
dim}[\mathcal{Y}(\mathscr{P}(\mathcal{C}))]$.

To prove this theorem, we introduce some crucial results from the estimation
theory of measures. Proofs of all the lemmas stated henceforth, can be found
in the supplement.

######  Lemma 1.

For $f,g\in\mathscr{P}(\mathcal{C})$, $\mathinner{\\!\left\lVert
f-g\right\rVert}_{TV}=\>\mathinner{\\!\left\lVert
f-g\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))}.$

######  Lemma 2.

Let $\gamma\in\mathscr{P}(\mathcal{Z})$. Also, let $\hat{\gamma}_{n}$ denote
the empirical distribution based on $n\geq 0$ i.i.d. samples drawn from
$\gamma$. Then there exist positive constants $k_{1},k_{2}$ such that

$\mathbb{P}\Big{(}\mathinner{\\!\left\lVert\gamma-\hat{\gamma}_{n}\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{Z}))}\leq
k_{1}\sqrt{\frac{v}{n}}+t\Big{)}\geq 1-\exp{(-k_{2}nt^{2})},$

where $v$ stands for $\textrm{VC-dim}[\mathcal{Y}(\mathscr{P}(\mathcal{Z}))]$.

###### Proof of Theorem 1.

Given $n$ observations from $\rho$, let $\hat{\rho}_{n}$ denote the
corresponding empirical measure. Now, using the triangle inequality we have,

$\displaystyle\mathinner{\\!\left\lVert\rho-\widehat{(E_{\\#}\mu)}_{n}\right\rVert}_{TV}\leq$
$\displaystyle\;\mathinner{\\!\left\lVert\rho-
E_{\\#}\mu\right\rVert}_{TV}+\;\mathinner{\\!\left\lVert
E_{\\#}\mu-\widehat{(E_{\\#}\mu)}_{n}\right\rVert}_{TV}$ $\displaystyle\leq$
$\displaystyle\;\mathinner{\\!\left\lVert\rho-\hat{\rho}_{n}\right\rVert}_{TV}+\;\mathinner{\\!\left\lVert
E_{\\#}\mu-\widehat{(E_{\\#}\mu)}_{n}\right\rVert}_{TV}+\;\mathinner{\\!\left\lVert\hat{\rho}_{n}-E_{\\#}\mu\right\rVert}_{TV}.$
(4)

Define,

$\mathcal{L}^{*}_{n}=\operatorname*{argmin}_{q\in\mathscr{P}(\mathcal{C})}\>{\mathinner{\\!\left\lVert
q-\hat{\rho}_{n}\right\rVert}}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))}.$

Observe that,

$\displaystyle\mathinner{\\!\left\lVert\hat{\rho}_{n}-E_{\\#}\mu\right\rVert}_{TV}\leq$
$\displaystyle\;\mathinner{\\!\left\lVert\hat{\rho}_{n}-\mathcal{L}^{*}_{n}\right\rVert}_{TV}+\;\mathinner{\\!\left\lVert\mathcal{L}^{*}_{n}-E_{\\#}\mu\right\rVert}_{TV}$
$\displaystyle=$
$\displaystyle\;\mathinner{\\!\left\lVert\hat{\rho}_{n}-\mathcal{L}^{*}_{n}\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))}+\;\mathinner{\\!\left\lVert\mathcal{L}^{*}_{n}-E_{\\#}\mu\right\rVert}_{TV}$
(5) $\displaystyle\leq$
$\displaystyle\;\mathinner{\\!\left\lVert\rho-\hat{\rho}_{n}\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))}+\;\mathinner{\\!\left\lVert\mathcal{L}^{*}_{n}-E_{\\#}\mu\right\rVert}_{TV}.$
(6)

Lemma (1) ensures the equality in (5). (6) is due to the definition of
$\mathcal{L}^{*}_{n}$.

Now,

$\displaystyle\mathinner{\\!\left\lVert\mathcal{L}^{*}_{n}-E_{\\#}\mu\right\rVert}_{TV}=$
$\displaystyle\;\inf_{\tau\in\mathcal{T}(\mathcal{L}^{*}_{n},E_{\\#}\mu)}\int
c(x,y)d\tau(x,y)$ (7) $\displaystyle=$
$\displaystyle\;\inf_{\tau\in\mathcal{T}^{{}^{\prime}}(\mathcal{L}^{*}_{n},\mu)}\int
c(x,E(y))d\tau(x,y),$ (8)

where $\mathcal{T}$ and $\mathcal{T}^{{}^{\prime}}$ are couplings of measures.
The metric
$c\mathrel{\mathop{\ordinarycolon}}\mathcal{Z}\times\mathcal{Z}\rightarrow\mathbb{R}_{\geq
0}$ in (7) is the trivial metric $c(x,y)=1_{x\neq y}$ [26]. This implies, the
transformation induced by the encoder should be such that, it minimizes the
adversarial loss (8). In case $c$ is lower semi-continuous, there exists a
$\tau\in\mathcal{T}^{{}^{\prime}}$ which minimizes (8), and hence an $E$ [32].
For example, $c(x,y)=1_{C}(x,y)$, where $1_{C}(x,y)$ is the indicator on an
open set $C$. In our situation however, we can always choose a sub-optimal $E$
such that (8) $\leq\lambda^{*}$, for a non-negative $\lambda^{*}$. Villani et
al. [26] describes various ways to get hold of such a $\tau$.

Going back to (4),

$\mathinner{\\!\left\lVert\rho-\widehat{(E_{\\#}\mu)}_{n}\right\rVert}_{TV}-\lambda^{*}\leq
2\mathinner{\\!\left\lVert\rho-\hat{\rho}_{n}\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))}+\;\mathinner{\\!\left\lVert
E_{\\#}\mu-\widehat{(E_{\\#}\mu)}_{n}\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))}.$
(9)

Thus, (9) along with lemma (2) proves the theorem. ∎

It is worth mentioning that in reality however, we only have a sample of size
$n\in\mathbb{N}^{+}$ from the input distribution, say $\\{X_{i}\\}^{n}_{i=1}$.
Based on the same, an empirical distribution
$\hat{\mu}_{n}=\frac{1}{n}\sum^{n}_{i=1}\delta_{X_{i}}$ is what we have at
hand.

######  Corollary 1.

Under the additional assumptions [3, 4(ii)],

$\mathinner{\\!\left\lVert
E_{\\#}{\hat{\mu}_{n}}-\rho\right\rVert}_{TV}-\lambda^{*}=\mathcal{O}_{\mathbb{P}}{(n^{-\frac{1}{2}})}.$

######  Remark.

Despite the fact that the optimal value of (8) cannot be made arbitrarily
small directly, in case we obtain $\lambda_{n},n\in\mathbb{N}$, such that,
$\limsup_{n\rightarrow\infty}\lambda_{n}=\lambda^{*}$; the same conclusion can
be drawn. We call Corollary (1) ’consistency up to $\lambda^{*}$’ in this
light. Note that, for a given margin of error $\lambda$ in the latent space,
$E$ needs to be chosen such that, $\lambda^{*}\leq\lambda$. On the other way
round, starting with an unspecified $\lambda$, one can learn about the
feasible margin of error by observing $\lambda^{*}$.

Theorem (1) shows that the discrepancy between the ’encoded’ and the ’target’
law can be made arbitrarily small around a constant with high probability.
Corollary (1), consequently establishes our idea of consistency in latent
space. Proof for the same can be found in the supplement. As such, for any
suitably chosen $t^{*}$, the constraint in problem (3) is satisfied. We now
investigate whether the decoder network is capable of regenerating a
distribution ’close’ to $\mu$, from $E_{\\#}\mu$. A probabilistic decoder, in
this context, is formally defined as a function
$D\mathrel{\mathop{\ordinarycolon}}\mathcal{Z}\longrightarrow\mathcal{X}$ such
that $D_{\\#}\rho\in\mathscr{P}(\mathcal{X})$.

The residual task at hand can be formally written as the minimization of

$d_{\mathscr{L}^{1}_{c}}((D\circ
E)_{\\#}\mu,\mu)=\sup_{l\in\mathscr{L}^{1}_{c}}\Big{\\{}\mathbb{E}_{x\sim(D\circ
E)_{\\#}\mu}\big{[}l(x)\big{]}-\mathbb{E}_{x\sim\mu}\big{[}l(x)\big{]}\Big{\\}}$

over $E\in\mathscr{F}(\mathcal{X},\mathscr{P}(\mathcal{Z}))$ which follows
assumption (4). Which, however under an observed empirical measure
$\hat{\mu}_{n}$ boils down to its sample counterpart, given by

$d_{\mathscr{L}^{1}_{c}}((D\circ
E)_{\\#}{\hat{\mu}_{n}},{\mu})=\sup_{l\in\mathscr{L}^{1}_{c}}\Big{\\{}\mathbb{E}_{x\sim(D\circ
E)_{\\#}{\hat{\mu}_{n}}}\big{[}l(x)\big{]}-\mathbb{E}_{x\sim\mu}\big{[}l(x)\big{]}\Big{\\}}.$
(10)

We remark that the role of the class of functions $\mathscr{L}^{1}_{c}$ while
minimizing (10) is to behave as ‘critics’. GANs, during their training,
gradually learn to be a better judge by casting this functional class through
a discriminator [5]. This freedom of choice in turn gives one more flexibility
to interpret its regenerative capabilities [13, 9, 14]. In the case of AEs
however, the choice depends solely on the preassigned discrepancy metric.
Hence, the theoretical justification of reconstruction for AEs needs
additional maneuvering. Our first step in doing so is an assumption on the
input distribution.

######  Assumption 5.

(i) $p_{\mu}\in\mathcal{H}^{\alpha}(\mathcal{X})$ with $\alpha>0$, where
$\mathcal{H}^{\alpha}(\mathcal{X})$ denotes the Hölder class based on
$\mathcal{X}$; such that, the $i^{\textrm{th}}$ order derivative
$p^{(i)}_{\mu}$ exists $(i\leq\lfloor{\alpha}\rfloor)$ and is bounded on
$\bar{\mathcal{X}}$. Also,
$D^{\lfloor{\alpha}\rfloor}_{p_{\mu}}=\sup_{x,y}\frac{\mathinner{\\!\left\lvert
p^{(\lfloor{\alpha}\rfloor)}_{\mu}(x)-p^{(\lfloor{\alpha}\rfloor)}_{\mu}(y)\right\rvert}}{{\mathinner{\\!\left\lVert
x-y\right\rVert}_{2}}^{\alpha-\lfloor{\alpha}\rfloor}}<\infty$, for $x\neq
y\in\textrm{Int}(\mathcal{X})$.

######  Remark.

Assumption (5) enables one to assign the Hölder norm, defined as

$\mathinner{\\!\left\lVert
p_{\mu}\right\rVert}_{\mathcal{H}^{\alpha}}=\max_{i\leq\lfloor{\alpha}\rfloor}\mathinner{\\!\left\lVert
p^{(i)}_{\mu}\right\rVert}_{\infty}+D^{\lfloor{\alpha}\rfloor}_{p_{\mu}}.$

Moreover, $\mathinner{\\!\left\lVert
p_{\mu}\right\rVert}_{\mathcal{H}^{\alpha}}$ turns out to be bounded.

Smoothness assumptions on input data distribution, in the form of Hölder or
Sobolev densities are quite familiar in the theory of density estimation for
generative models [13, 14, 21]. Observe that, earlier results still hold under
this additional assumption. The smoothness of both the input and latent
densities (2(ii)) together, ensures the existence of certain regenerative
maps, which are crucial to the forthcoming discussion. Lemma (3) formalizes
the same.

######  Lemma 3 ([33]).

Under assumptions [1, 2, 5], there exists a map $T\in\mathcal{H}^{\alpha+1}$
from $\mathcal{Z}$ to $\mathcal{X}$ such that, $T_{\\#}{\rho}=\mu$.

In our discussion, similar to the encoder transformation, we do not impose
specific structural restrictions on the decoder network. However, the
mathematical assumptions that are made, are inspired and supported by real
architectures.

######  Assumption 6.

The quasi-isometric embedding
$D\mathrel{\mathop{\ordinarycolon}}(\mathcal{Z},\;\mathinner{\\!\left\lVert\;\right\rVert}_{TV})\longrightarrow(\mathcal{X},c)$
induced by the decoder network is $\epsilon$-close to $T$ in uniform norm,
where $T$ is as defined in lemma (3). Also, $(D\circ E)_{\\#}\mu$ shares the
same support with $\mu$.

Classes of functions, learned by generator networks in GANs, are often taken
to be smooth [13, 21] to achieve minimax convergence rate. Our assumption of
quasi-isometric embedding is gentler in principle. We mention that an
alternative weaker assumption of Lipschitz continuity would have sufficed in
our analysis. Assumption (6) on the other hand, takes one step forward to
comment on the broader geometry of the two spaces under consideration.
Moreover, precise specification of parameters of a ReLU network can always
result in a map, which is capable of approximating the optimal Monge solution
[34, 35], which in our case turns out to be smooth. Note that, the metric on
$\mathcal{Z}$ can be equivalently taken as
$\>\mathinner{\\!\left\lVert\;\right\rVert}_{1}$.

The following lemma provides an oracle inequality by fragmenting the empirical
loss as in (10), into disjoint parts.

######  Lemma 4.

Given an encoder transformation $E^{*}$,

$d_{\mathscr{L}^{1}_{c}}((D\circ
E^{*})_{\\#}{\hat{\mu}_{n}},{\mu})\leq\mathcal{E}_{1}+\mathcal{E}_{2}+2\mathcal{E}_{3},$

where $\mathcal{E}_{1}=d_{\mathscr{L}^{1}_{c}}((D\circ
E^{*})_{\\#}{\hat{\mu}_{n}},D_{\\#}{\rho})$ is the ’Encoder Approximation
Error’;
$\mathcal{E}_{2}=d_{\mathscr{L}^{1}_{c}}(D_{\\#}{\rho},T_{\\#}{\rho})$ stands
for the ’Decoder Approximation Error’ and
$\mathcal{E}_{3}=d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},\mu)$, the ’Statistical
Estimation Error’.

We remark that successful regeneration by the f-WAE can be ensured by showing:
these individual errors are arbitrarily small or they approach zero in any
probabilistic sense. To demonstrate the same in the case of $\mathcal{E}_{3}$,
we introduce some concepts from [36, 18].

######  Definition 7 (1-Upper Wasserstein Dimension).

For $\gamma\in\mathscr{P}(\mathcal{X})$, the $(\epsilon,\tau)$-covering number
is given by

$\mathcal{N}_{\epsilon}(\gamma,\tau)=\inf_{S\subseteq\mathcal{X}}\\{\mathcal{N}_{\epsilon}(S)\mathrel{\mathop{\ordinarycolon}}\gamma(S)\geq
1-\tau\\}.$

Consequently, we define the $(\epsilon,\tau)$-dimension as
$\delta_{\epsilon}(\gamma,\tau)=\frac{\mathcal{N}_{\epsilon}(\gamma,\tau)}{-\log(\epsilon)}$.
Under this setup, the Upper Wasserstein Dimension for $p=1$ is

$\delta^{*}_{1}(\gamma)=\inf\\{s\in(2,\infty)\mathrel{\mathop{\ordinarycolon}}\limsup_{\epsilon\rightarrow
0}\delta_{\epsilon}(\gamma,\epsilon^{\frac{s}{s-2}})\leq s\\}.$

######  Lemma 5 ([18]).

Let $diam_{c}(Supp(\mu))=B$. Then, for $n\geq 0$ and $s>\delta^{*}_{1}(\mu)$,

$\mathbb{P}\Big{(}d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},\mu)\leq\mathcal{O}(n^{-\frac{1}{s}})+t\Big{)}\geq
1-\exp\Big{\\{}-\frac{2nt^{2}}{B^{2}}\Big{\\}}.$

Now, we propose the main theorem which provides a guarantee regarding
regeneration.

######  Theorem 2.

Given a margin of error $\lambda^{*}$ in latent space, let $\hat{\mu}_{n}$
denote an empirical input measure, consistent up to $\lambda^{*}$, under
encoder map $E^{*}$. Also, let $diam_{c}(Supp(\mu))=B$. Then, there exists a
constant $\zeta^{*}\geq 0$ and $\delta\in(0,1)$ such that

$d_{\mathscr{L}^{1}_{c}}((D\circ
E^{*})_{\\#}{\hat{\mu}_{n}},{\mu})-\zeta^{*}\leq\mathcal{O}(n^{-\frac{1}{s}})+\mathcal{O}(n^{-\frac{1}{2}})$

with probability at least $1-\delta$, where $s>\delta^{*}_{1}(\mu)$.

###### Proof of Theorem 2.

Observe that, the error committed by the encoder

$\displaystyle\mathcal{E}_{1}=$
$\displaystyle\;d_{\mathscr{L}^{1}_{c}}((D\circ
E^{*})_{\\#}{\hat{\mu}_{n}},D_{\\#}{\rho})=\inf_{\upsilon\in\Upsilon(E^{*}_{\\#}\hat{\mu}_{n},\rho)}\int
c(D(x),D(y))d\upsilon(x,y)$ (11) $\displaystyle\leq$
$\displaystyle\;A\inf_{\upsilon\in\Upsilon(E^{*}_{\\#}\hat{\mu}_{n},\rho)}\int\mathinner{\\!\left\lVert
x-y\right\rVert}_{TV}d\upsilon(x,y)$ $\displaystyle\leq$
$\displaystyle\;\lambda^{*}AB+\mathcal{O}(n^{-\frac{1}{2}}),$ (12)

where (12) holds with probability $\geq 1-\delta$ (using Theorem (1)).
$\Upsilon$ in (11) denotes the associated coupling and $A\geq 1$ is the
constant related to the embedding $D$. Say, $\zeta^{*}=\lambda^{*}AB$.

Similarly,

$\displaystyle\mathcal{E}_{2}=\;d_{\mathscr{L}^{1}_{c}}(D_{\\#}{\rho},T_{\\#}{\rho})=$
$\displaystyle\sup_{l\in\mathscr{L}^{1}_{c}}\Big{\\{}\mathbb{E}_{x\sim\rho}\big{[}l(D(x))\big{]}-\mathbb{E}_{x\sim\rho}\big{[}l(T(x))\big{]}\Big{\\}}$
$\displaystyle\leq$
$\displaystyle\;\mathbb{E}_{x\sim\rho}\big{[}\mathinner{\\!\left\lVert
D-T\right\rVert}_{\infty}\big{]}\leq\epsilon^{*},$ (13)

which is a consequence of the fact that, $\mathinner{\\!\left\lVert
D-T\right\rVert}_{\infty}\leq\epsilon$ (Assumption (6)). Here, $\epsilon^{*}$
is an arbitrarily small quantity corresponding to $\epsilon$.

Also, lemma (5) suggests that for $s>\delta^{*}_{1}(\mu)$,

$\mathcal{E}_{3}=\;d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},\mu)\leq\mathcal{O}(n^{-\frac{1}{s}})+\frac{1}{\sqrt{n}}B\sqrt{\frac{1}{2}\ln\big{(}{\frac{1}{\delta}}\big{)}}$
(14)

with probability at least $1-\delta$.

As such, (12), (13) and (14) together prove the theorem. ∎

######  Remark.

Let us weigh up on a special case, which carries notable significance.
Suppose, one obtains $\lambda_{n}$ as an upper bound to (8), corresponding to
$\mathcal{L}^{*}_{n},\;n\in\mathbb{N}^{+}$, such that $\lambda_{n}=o(1)$. We
do not prove the existence of such a sequence, which might be taken up as a
future work. However, under the assumption of existence, corollary (1) implies
that,

$\sup_{\mathcal{A}\in\mathcal{F}}\mathinner{\\!\left\lVert
E_{\\#}{\hat{\mu}_{n}}(\mathcal{A})-\rho(\mathcal{A})\right\rVert}\longrightarrow
0,$

where $\mathcal{F}$ is the Borel $\sigma$-algebra on $\mathcal{Z}$. As such,
$E_{\\#}\hat{\mu}_{n}$ converges strongly to $\rho$. This theoretically
ensures the achievement of a target latent law.

Similarly, such an $\\{\lambda_{n}\\}$ will have a remarkable effect on the
regeneration process. In that case, Theorem (2) will imply,

$d_{\mathscr{L}^{1}_{c}}((D\circ
E^{*})_{\\#}{\hat{\mu}_{n}},{\mu})\longrightarrow 0,$

i.e. $(D\circ E^{*})_{\\#}{\hat{\mu}_{n}}$ converges weakly in
$\mathscr{P}(\mathcal{X})$ to $\mu$ [26]. This result serves as a
reconstruction guarantee.

Now, let us look back at the original WAE objective in (1). Denote by

$d^{*}_{c}(P_{X},(E,D))=\int_{\mathcal{X}}\mathbb{E}_{z\sim
E(x)}[c(x,D(z))]dP_{X}(x)$

the reconstruction loss. In general, this acts as an upper bound to the f-WAE
counterpart [7]. However, under additional restrictions on D, they become
equivalent [7]. In such a case, if $\Omega$ in (1) is taken to be $D_{f}$, the
two reconstructions also follow the same trait. In our study, the measure of
discrepancy of distributions in latent space was throughout taken to be TV. JS
divergence, being upper bounded by TV, is obliged to follow the results
established exactly. As such, the only task remaining is the transferral of
regeneration guarantees to WAEs [6].

######  Corollary 2.

There exists a specific margin of error $\kappa\geq 0$ in the latent space
such that, Theorem (2) holds exactly for $d^{*}_{c}(\hat{\mu}_{n},(E^{*},D))$,
where $D$ is also invertible.

###### Proof of Corollary (2).

Husain et al. [7] had suggested the existence of a $\kappa\geq 0$, such that
for all margin or error $\lambda>\kappa$, (1) and (2) are exactly equal. The
proof however, demands the decoder transform to be invertible. In such a case,
for an encoder $E^{*}$ and $\Omega=D_{f}$ imply that

$d^{*}_{c}(\hat{\mu}_{n},(E^{*},D))=\int_{\mathcal{X}}\mathbb{E}_{z\sim
E^{*}(x)}[c(x,D(z))]d\hat{\mu}_{n}(x)\leq d_{\mathscr{L}^{1}_{c}}((D\circ
E^{*})_{\\#}{\hat{\mu}_{n}},{\mu})+d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},{\mu}).$

Hence, using lemma (2) and Theorem (2) we say that

$d^{*}_{c}(\hat{\mu}_{n},(E^{*},D))-\zeta^{*}\leq\mathcal{O}(n^{-\frac{1}{s}})+\mathcal{O}(n^{-\frac{1}{2}})$

holds with probability at least $1-\delta$, for $s>\delta^{*}_{1}(\mu)$. ∎

We emphasize the fact that the argument of weak convergence, however, as given
in (Remark), does not apply directly to this case. The Wasserstein distance
metrizes $\mathscr{P}(\mathcal{X})$, i.e. weak convergence holds if and only
if $d_{\mathscr{L}^{1}_{c}}\longrightarrow 0$. On the other hand, $d^{*}_{c}$
does not satisfy the axioms of a distance. As such, WD produces stronger
inferences, even though under carefully taken assumptions they tend to be
equal.

##  5 Conclusion

Our analysis, besides serving as the first of its kind theoretical promises
regarding the simultaneous tasks a WAE has to perform, also points toward
untraveled avenues. An immediate extension might look into broader classes of
discrepancy measures in latent space. The latent space and hence the
distribution that characterizes it might also be in focus. An even elaborate
characterization can deliver it further justice. Our study includes a
commentary on the geometry preserving nature of deep generative networks from
a fairly new perspective. Being a novel representation, it creates new
opportunities for inventive scrutiny. We also restrict our analysis to a non-
parametric regime, which may encourage similar endeavours under a parametrized
setup. Testing the regeneration capabilities of WAE for even general classes
of distributions might be interesting too.

##  6 Future Work

Another WAE architecture that appears in [6], uses Maximum Mean Discrepancy
(MMD) instead of JS divergence. To the best of our knowledge, there is no
evidence of theoretical superiority that MMD enjoys. However, uniform
convergence bounds on empirical distributions under MMD, as established by
[37] in a different context, produces similar convergence rates. A comparative
statistical analysis of the two architectures might be fruitful from a
practitioner’s viewpoint.

The concept of ‘disentanglement’ in AE context remains somewhat unclear to
this day. While it is not properly defined, to the best of our understanding,
it can arguably be described as the process of achieving a factorial
representation; one with ’expressive’ and perhaps independent coordinates,
which characterize the features. A somewhat gentle representation of the same
might be a distribution with an axis-aligned covariance structure (diagonal
dispersion matrix). Although our work allows for the latent distribution class
to be $d$-dimensional axis-aligned Gaussians, a parametric approach might help
in studying the relationship between regularization and disentanglement.

The non-parametric approach adopted in this work, does not take into
consideration specific model architectures of the networks in use. An
immediate investigation may look into the effect of network parameters such
as, depth, width, activation functions etc. on regeneration and consistency in
the latent space. This, in turn, may improve the theoretical results based on
training plans as well.

##  Appendix A Appendix

###### Proof of lemma (1).

Here, $\mathscr{P}(\mathcal{C})$ denotes the set of probability measures
defined on the common support $\mathcal{C}$. This is a slight abuse of the
notation, since $\mathcal{C}$ is not the underlying space, but a subset of the
$\sigma$-algebra defined on it. Consequently,

$\mathcal{Y}(\mathscr{P}(\mathcal{C}))=\big{\\{}\omega\in\mathcal{C}\mathrel{\mathop{\ordinarycolon}}f_{1}(\omega)\geq
f_{2}(\omega);\>f_{1},f_{2}\in\mathscr{P}(\mathcal{C})\big{\\}}.$

Let, $f,g\in\mathscr{P}(\mathcal{C})$. Observe that,

$\sup_{\omega\in\mathcal{C}}\mathinner{\\!\left\lvert
f(\omega)-g(\omega)\right\rvert}=\>\mathinner{\\!\left\lVert
f-g\right\rVert}_{TV}\geq\>\mathinner{\\!\left\lVert
f-g\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))},$

due to the definition of TV.

Define,
$A=\\{\omega\in\mathcal{C}\mathrel{\mathop{\ordinarycolon}}f(\omega)\geq
g(\omega)\\}\in\mathcal{Y}(\mathscr{P}(\mathcal{C}))$. Now,

$\mathinner{\\!\left\lVert
f-g\right\rVert}_{TV}=\>\frac{1}{2}\mathinner{\\!\left\lVert
f-g\right\rVert}_{1}=\>\mathinner{\\!\left\lvert
f(A)-g(A)\right\rvert}\leq\>\mathinner{\\!\left\lVert
f-g\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))}.$

∎

###### Proof of lemma (2).

Since we only deal with measures supported on $\mathcal{C}$, our proof
revolves around $\mathscr{P}(\mathcal{C})$. A similar argument will hold for
all the measures, based on the $\sigma$-algebra corresponding to
$\mathcal{Z}$.

Let, $\gamma\in\mathscr{P}(\mathcal{C})$. Also, let $\\{X_{i}\\}_{i=1}^{n}$
denote an i.i.d. sample from $\gamma$. Define,
$\hat{\gamma}_{n}(S)=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}}(S)$, for
$S\in\mathcal{C}$.

Using Dudley’s chaining argument coupled with symmetrization, it can be shown
that (Corollary 7.18 [38]) there exists an universal constant $L$ such that,

$\mathbb{E}\Big{[}\sup_{S\in\mathcal{Y}(\mathscr{P}(\mathcal{C}))}\mathinner{\\!\left\lvert\hat{\gamma}_{n}(S)-\gamma(S)\right\rvert}\Big{]}\leq
L\sqrt{\frac{\textrm{VC-dim}[\mathcal{Y}(\mathscr{P}(\mathcal{C}))]}{n}}.$

This constant $L$ depends on the diameter of $\mathcal{C}$ with respect to the
$\>\mathinner{\\!\left\lVert\;\right\rVert}_{2}$ norm. Now, by McDiarmid’s
inequality

$\mathbb{P}\Big{(}\sup_{S\in\mathcal{Y}(\mathscr{P}(\mathcal{C}))}\mathinner{\\!\left\lvert\hat{\gamma}_{n}(S)-\gamma(S)\right\rvert}-\mathbb{E}\big{[}\sup_{S\in\mathcal{Y}(\mathscr{P}(\mathcal{C}))}\mathinner{\\!\left\lvert\hat{\gamma}_{n}(S)-\gamma(S)\right\rvert}\big{]}\geq\eta\Big{)}\leq\exp{(-cn\eta^{2})},$

where $c$ is a positive constant. As such,

$\displaystyle\mathbb{P}\Big{(}\mathinner{\\!\left\lVert\hat{\gamma}_{n}-\gamma\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))}\geq
L\sqrt{\frac{v}{n}}+\eta\Big{)}\leq\exp{(-cn\eta^{2})}$
$\displaystyle\Longleftrightarrow\;$
$\displaystyle\mathbb{P}\Big{(}\mathinner{\\!\left\lVert\hat{\gamma}_{n}-\gamma\right\rVert}_{\mathcal{Y}(\mathscr{P}(\mathcal{C}))}\leq
L\sqrt{\frac{v}{n}}+\frac{1}{\sqrt{n}}\sqrt{\frac{1}{c}\ln{\big{(}\frac{1}{\delta}\big{)}}}\Big{)}\geq
1-\delta,$

where $v=\textrm{VC-dim}[\mathcal{Y}(\mathscr{P}(\mathcal{C}))]$ and
$\delta\in(0,1)$. Judicious choices of $k_{1}$ and $k_{2}$ proves the lemma. ∎

###### Proof of lemma (4).

Since, Wasserstein distance is a metric on $\mathscr{P}(\mathcal{X})$, using
triangle inequality we get

$\displaystyle d_{\mathscr{L}^{1}_{c}}((D\circ
E^{*})_{\\#}{\hat{\mu}_{n}},{\mu})\leq$
$\displaystyle\>d_{\mathscr{L}^{1}_{c}}((D\circ
E^{*})_{\\#}{\hat{\mu}_{n}},\hat{\mu}_{n})+d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},{\mu})$
$\displaystyle\leq$ $\displaystyle\>d_{\mathscr{L}^{1}_{c}}((D\circ
E^{*})_{\\#}{\hat{\mu}_{n}},D_{\\#}{\rho})+d_{\mathscr{L}^{1}_{c}}(D_{\\#}{\rho},\hat{\mu}_{n})+\mathcal{E}_{3}$
$\displaystyle\leq$
$\displaystyle\>d_{\mathscr{L}^{1}_{c}}(D_{\\#}{\rho},T_{\\#}{\rho})+d_{\mathscr{L}^{1}_{c}}(T_{\\#}{\rho},\hat{\mu}_{n})+\mathcal{E}_{1}+\mathcal{E}_{3}$
$\displaystyle=$
$\displaystyle\>\mathcal{E}_{1}+\mathcal{E}_{2}+2\mathcal{E}_{3}.$

Here, $T$ is as suggested in lemma (3). ∎

###### Proof of lemma (5).

Theorem 1 of [18] ensures that, for $s>\delta^{*}_{1}(\mu)$

$\mathbb{E}\big{[}d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},{\mu})\big{]}=\mathcal{O}(n^{-\frac{1}{s}}).$

Denote, $W(\omega)=d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},{\mu})$, where
$\omega\in\mathcal{X}^{n}$. Now, for
$x_{1},x_{2},...,x_{n},x^{{}^{\prime}}_{n}\in\mathcal{X}$

$\mathinner{\\!\left\lvert
W(x_{1},x_{2},...,x_{n})-W(x_{1},x_{2},...,x^{{}^{\prime}}_{n})\right\rvert}\leq\frac{1}{n}c(x_{n},x^{{}^{\prime}}_{n})\leq\frac{B}{n}.$

As such, $d_{\mathscr{L}^{1}_{c}}(\;)$ satisfies the bounded difference
inequality. Thus, using the McDiarmid’s inequality we get

$\mathbb{P}\Big{(}d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},{\mu})-\mathbb{E}\big{[}d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},{\mu})\big{]}\geq
t\Big{)}\leq\exp\Big{\\{}-\frac{2nt^{2}}{B^{2}}\Big{\\}},$

$t>0$ i.e.,
$\big{\\{}d_{\mathscr{L}^{1}_{c}}(\hat{\mu}_{n},{\mu})\leq\mathcal{O}(n^{-\frac{1}{s}})+t\big{\\}}$
holds with probability at least $1-\exp\big{(}-\frac{2nt^{2}}{B^{2}}\big{)}$.
∎

###### Proof of Corollary (1).

Observe that,

$\displaystyle\mathbb{P}\Big{(}\mathinner{\\!\left\lVert
E_{\\#}{\hat{\mu}_{n}}-\rho\right\rVert}_{TV}-\lambda^{*}-c_{1}\sqrt{\frac{v}{n}}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle\;\mathbb{P}\Big{(}\mathinner{\\!\left\lVert
E_{\\#}{\hat{\mu}_{n}}-\widehat{(E_{\\#}\mu)}_{n}\right\rVert}_{TV}+\>\mathinner{\\!\left\lVert\widehat{(E_{\\#}\mu)}_{n}-\rho\right\rVert}_{TV}-\lambda^{*}-c_{1}\sqrt{\frac{v}{n}}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle\;\mathbb{P}\Big{(}\mathinner{\\!\left\lVert
E_{\\#}{\hat{\mu}_{n}}-\widehat{(E_{\\#}\mu)}_{n}\right\rVert}_{TV}\geq\frac{\epsilon}{2}\Big{)}+\;\mathbb{P}\Big{(}\mathinner{\\!\left\lVert\widehat{(E_{\\#}\mu)}_{n}-\rho\right\rVert}_{TV}-\lambda^{*}-c_{1}\sqrt{\frac{v}{n}}\geq\frac{\epsilon}{2}\Big{)}$
$\displaystyle\leq$
$\displaystyle\;k\exp\big{\\{}-\frac{n^{r}\epsilon^{2}}{4}\big{\\}}+c_{3}\exp\big{\\{}-\frac{nc^{{}^{\prime}}\epsilon^{2}}{4}\big{\\}},$
(15)

where $c^{{}^{\prime}}=\frac{1}{c_{2}^{2}}$ and $v=\textrm{VC-
dim}[\mathcal{Y}(\mathscr{P}(\mathcal{C}))]$, which is taken to be finite.
Theorem (1) and Assumption (4(ii)) together result in (15). Hence, for $r\geq
1$, $c^{*}=\min\\{\frac{1}{4},\frac{c^{{}^{\prime}}}{4}\\}$ and
$k^{*}=2\max\\{k,c_{3}\\}$,

$\mathbb{P}\Big{(}\mathinner{\\!\left\lVert
E_{\\#}{\hat{\mu}_{n}}-\rho\right\rVert}_{TV}-\lambda^{*}\geq
c_{1}\sqrt{\frac{v}{n}}+\epsilon\Big{)}\leq
k^{*}\exp\big{\\{}-nc^{*}\epsilon^{2}\big{\\}}.$

i.e., with probability at least $1-\delta$,

$\mathinner{\\!\left\lVert
E_{\\#}{\hat{\mu}_{n}}-\rho\right\rVert}_{TV}-\lambda^{*}\leq\mathcal{O}(n^{-\frac{1}{2}})+\frac{1}{\sqrt{n}}\sqrt{\frac{1}{c^{*}}\ln{\big{(}\frac{k^{*}}{\delta}\big{)}}}.$

∎

######  Remark (Regarding Proof of lemma (3)).

The objective at hand is to find a
$T\mathrel{\mathop{\ordinarycolon}}\mathcal{Z}\longrightarrow\mathcal{X}$ such
that,

$T\in\operatorname*{argmin}_{T\mathrel{\mathop{\ordinarycolon}}T_{\\#}\rho=\mu}\int
c(x,T(x))d\rho(x).$

Assumption (1) and (5) ensure that the density corresponding to $\mu$ is
smooth in the sense of Hölder and is based on a convex $\mathcal{X}$.
$p_{\rho}$ has also been taken to be smooth (2). When
$\mathcal{X},\mathcal{Z}\subseteq\mathbb{R}^{d}$, a quadratic cost $c$ implies
that such a solution $T$ exists (Brenier Potential) and moreover, satisfies
the Monge-Ampère equation (Eq. 12.4 in [26]). In this premise, the regularity
results on $T$, provided by Caffarelli et al.[33] exactly proves Lemma (3).

## References

  * [1] Diederik P. Kingma and Max Welling.  Auto-Encoding Variational Bayes.  In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
  * [2] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS’14, page 2672–2680, 2014.
  * [3] Alireza Makhzani, Jonathon Shlens, Navdeep Jaitly, Ian Goodfellow, and Brendan Frey.  Adversarial autoencoders, 2016.
  * [4] Lars Mescheder, Sebastian Nowozin, and Andreas Geiger.  Adversarial variational bayes: Unifying variational autoencoders and generative adversarial networks, 2018.
  * [5] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 214–223. PMLR, 2017.
  * [6] Ilya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf.  Wasserstein auto-encoders.  In International Conference on Learning Representations, 2018.
  * [7] Hisham Husain, Richard Nock, and Robert C Williamson.  A primal-dual link between gans and autoencoders.  In Advances in Neural Information Processing Systems, volume 32, 2019.
  * [8] Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang.  Generalization and equilibrium in generative adversarial nets (GANs).  In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 224–232. PMLR, 06–11 Aug 2017.
  * [9] Gérard Biau, Benoît Cadre, Maxime Sangnier, and Ugo Tanielian.  Some theoretical properties of GANS.  The Annals of Statistics, 48:1539 – 1566, 2020.
  * [10] Sebastian Nowozin, Botond Cseke, and Ryota Tomioka.  f-gan: Training generative neural samplers using variational divergence minimization.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
  * [11] Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabás Póczos.  Mmd gan: Towards deeper understanding of moment matching network, 2017\.
  * [12] Youssef Mroueh, Chun-Liang Li, Tom Sercu, Anant Raj, and Yu Cheng.  Sobolev gan, 2017.
  * [13] Tengyuan Liang.  How well generative adversarial networks learn distributions, 2020.
  * [14] Minshuo Chen, Wenjing Liao, Hongyuan Zha, and Tuo Zhao.  Statistical guarantees of generative adversarial networks for distribution estimation, 2020.
  * [15] Shuang Liu, Olivier Bousquet, and Kamalika Chaudhuri.  Approximation and convergence properties of generative adversarial learning, 2017.
  * [16] Gérard Biau, Maxime Sangnier, and Ugo Tanielian.  Some theoretical insights into wasserstein gans, 2020.
  * [17] Zhiting Hu, Zichao Yang, Ruslan Salakhutdinov, and Eric P. Xing.  On unifying deep generative models, 2018.
  * [18] Jonathan Weed and Francis Bach.  Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance, 2017.
  * [19] Jing Lei.  Convergence and concentration of empirical measures under wasserstein distance in unbounded functional spaces.  Bernoulli, 26(1), Feb 2020.
  * [20] Shashank Singh and Barnabás Póczos.  Minimax distribution estimation in wasserstein distance, 2019.
  * [21] Shashank Singh, Ananya Uppal, Boyue Li, Chun-Liang Li, Manzil Zaheer, and Barnabás Póczos.  Nonparametric density estimation with adversarial losses.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 10246–10257, 2018.
  * [22] Luis A. Perez Rey, Vlado Menkovski, and Jim Portegies.  Diffusion variational autoencoders.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 2704–2710. International Joint Conferences on Artificial Intelligence Organization, 7 2020\.
  * [23] Yannis G. Yatracos.  Rates of convergence of minimum distance estimators and kolmogorov’s entropy.  The Annals of Statistics, 13(2):768–774, 1985.
  * [24] L. Devroye and G. Lugosi.  Combinatorial methods in density estimation.  In Springer series in statistics, 2001.
  * [25] Alfred Müller.  Integral probability metrics and their generating classes of functions.  Advances in Applied Probability, 29(2):429–443, 1997.
  * [26] Villani Cédric.  Optimal transport : old and new.  Grundlehren der mathematischen Wissenschaften. Springer, 2009.
  * [27] Gabriel Peyré and Marco Cuturi.  Computational optimal transport, 2020.
  * [28] Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert R. G. Lanckriet.  On integral probability metrics, $\phi$-divergences and binary classification, 2009.
  * [29] Igal Sason and Sergio Verdu.  $f$ -divergence inequalities.  IEEE Transactions on Information Theory, 62(11):5973–6006, Nov 2016.
  * [30] Stephen Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge University Press, USA, 2004.
  * [31] Hassan Ashtiani and Abbas Mehrabian.  Some techniques in density estimation, 2018.
  * [32] Villani Cédric.  Topics in optimal transportation.  Graduate studies in mathematics. American mathematical society, C 2003\.
  * [33] L. Caffarelli.  The regularity of mappings with a convex potential.  Journal of the American Mathematical Society, 5:99–104, 1992.
  * [34] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao.  Efficient approximation of deep relu networks for functions on low dimensional manifolds.  In Advances in Neural Information Processing Systems, volume 32, 2019.
  * [35] Dmitry Yarotsky.  Error bounds for approximations with deep relu networks.  Neural Networks, 94:103–114, 2017.
  * [36] R. M. Dudley.  The Speed of Mean Glivenko-Cantelli Convergence.  The Annals of Mathematical Statistics, 40(1):40 – 50, 1969.
  * [37] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  Journal of Machine Learning Research, 13:723–773, 2012.
  * [38] Ramon Van Handel.  Probability in high dimensions.  Technical report, 2016.


# Deep learning classification of large-scale point clouds:
A case study on cuneiform tablets

###### Abstract

This paper introduces a novel network architecture for the classification of
large-scale point clouds. The network is used to classify metadata from
cuneiform tablets. As more than half a million tablets remain unprocessed,
this can help create an overview of the tablets. The network is tested on a
comparison dataset and obtains state-of-the-art performance. We also introduce
new metadata classification tasks on which the network shows promising
results. Finally, we introduce the novel Maximum Attention visualization,
demonstrating that the trained network focuses on the intended features. Code
available at https://github.com/fhagelskjaer/dlc-cuneiform

Index Terms—  Deep learning, Point clouds, Classification, Cuneiform

##  1 Introduction

††This project was funded in part by Innovation Fund Denmark through the
project MADE FAST, in part by the SDU I4.0-Lab.

The oldest recorded writing is cuneiform signs imprinted on clay tablets.
Cuneiform writing was used at least from the fourth millennia BCE until the
end of the first millennia BCE [1]. As a result of the durability of the clay,
vast quantities of tablets have been excavated during the years. However, the
number of assyriologists to process these tablets does not match the massive
amount of excavated tablets. This is emphasized by the fact that there are
currently more than half a million unprocessed tablets [2]. As these tablets
contain vast amounts of knowledge currently unavailable, it is very desirable
to process cuneiform tablets automatically. Methods have demonstrated that
deep learning is possible with cuneiform data, but these methods either
require manual preprocessing [3] or only use 2D scans [4]. However, as
cuneiform tablets are 3D objects, the text often wraps around the corners [1,
p. 14]. The processing, therefore, needs to be in 3D to include all
information [5]. As a result, datasets have been created of 3D scanned tablets
[2, 6, 7]. Deep learning, therefore, needs to be performed in 3D to process
the tablets thoroughly. The introduction of the PointNet architecture
demonstrated that deep learning could be performed on 3D models by conversion
to point clouds [8]. Since then, a number of architectures for deep learning
of point clouds have been introduced [9]. While successful, these networks
generally handle smaller point clouds [10]. DGCNN handles point clouds of up
to 4096 points [11] and PointNet++ [12] go to 8192 points. However, to include
the fine-grained details of the tablets, large-scale point clouds are needed.
In our method, we process point clouds of 32,768 points.

Fig. 1: Left: Tablet ”HS 2275” [6]. Right: Our Maximum Attention visualization
shows the positive attention of the network. The network is trained to
classify tablets with signs on the left side, and most of the attention is
around this sign.

A successful network for processing very large point clouds is introduced by
Bogacz et al. [5]. Using the Heidelberg Cuneiform Benchmark Dataset
(HeiCuBeDa) [6] a dataset for classification of tablet time period is
introduced. The network created by combining SplineNet [13] and PointNet++
[12], and outperforms a PointNet++ network.

In this paper, we introduce a novel architecture for classifying large-scale
point clouds, which outperforms Bogacz et al. [5]. The network is based on
DGCNN [11], but we introduce several modifications. The main contributions are
an AvgPool guided MaxPool layer suited for large-scale point clouds, and a
bottom-up neighbor computation in geometric space. We also introduce the
Maximum Attention visualization method, demonstrating that the network attend
to relevant features, as shown in Fig. 1. Compared with existing methods [14,
15] that show the class prediction of each point, our method only shows the
points contributing to the prediction.

Fig. 2: Model architecture: From the input point cloud, the SparseEdge finds
neighbors, computes features, and a local MaxPool reduces the output. This
process is repeated in the second layer, with neighbors found using the mean
neighbor distance in the first layer as the minimum distance. The global
AvgPool is then computed from the two local MaxPools. The output of the
AvgPool is concatenated and combined with the local MaxPools, and a global
MaxPool is computed. The AvgPool and MaxPool layers are concatenated, and the
fully connected layers compute the class prediction.

##  2 Method

The developed network is based on DGCNN [11]. However, the point clouds are
much larger than those generally processed by DGCNN. The large number of
points are necessary to include the details of the surface imprints. However,
a sub-sampling is required both due to memory constraints, the largest tablet
has 2,414,753 vertices, and to keep an equal amount of points in each point
cloud. This is opposed to Bogacz et al. [5] which keep a varying point cloud
size. The sub-sampling is set to 32,768 as it is the largest doubling of
PointNets original 1024 points, which also encompass the smallest tablet at
44,629 and fit within memory constraints. Four changes have been made to
adjust the network to the large number of points. The network was trained on a
Tesla V100-SXM2 with 16 GB memory. A standard DGCNN network with 32,768 points
is too large to fit onto the GPU. The network was therefore reduced to allow
training on the large point cloud. The batch size also had to be reduced to
one, to fit the network onto the GPU

The Edge feature is replaced with the SparseEdge feature [16]. Whereas the
Edge feature finds the twenty nearest neighbors, the SparseEdge feature finds
the sixty nearest neighbors and randomly selects twenty points. This gives a
broader range, without increasing memory requirements.

Additionally, as the point clouds are very large, the neighbor space for the
Edge feature has been changed. In the original DGCNN network, neighbors in the
first layer are found in geometric space, and for the second layer, neighbors
are found in feature space. However, as the point clouds are very dense, the
possibility of neighbors being repeated from the first layer to the second
layer increases. To avoid this, we compute the second layer neighbors in
geometric space but use a minimum distance for the second layer neighbors. The
minimum distance is found by calculating the mean distance to all neighbors in
the first layer. An extended range is ensured by excluding all points within
the minimum distance.

A MaxPool layer combined with huge point clouds makes back-propagation
difficult, as few points are used for training [5]. In Bogacz et al., the
MaxPool layer is replaced with an AvgPool to compensate for this. However,
this excludes the discriminating effect of the MaxPool, which can bring focus
to specific points. To obtain the strengths of both, we use the AvgPool to aid
the MaxPool computation. The AvgPool is computed from the combined SparseEdge
layers. It is then expanded and concatenated with the SparseEdge layers, and
from this, the MaxPool is computed. Finally, the AvgPool and MaxPool layers
are concatenated, and the fully connected layers compute the class
predictions. The complete network structure is shown in Fig. 2.

The large data size restricts the network to training with a batch size of
one. As a result, batch normalization cannot be used. To obtain the advantages
of normalization, we instead use group normalization [17]. Instead of
normalizing across batches, the normalization is performed across groups in
the channels. This approach has shown good performance when batch
normalization is not possible [17].

###  2.1 Compensating Class Imbalance

The class distribution of the dataset introduced in Bogacz et al. is heavily
imbalanced [5]. To address this, Bogacz et al. fix each class to 100 samples
[5], excluding much of the data.

However, several methods exist to compensate for uneven sample distributions
[18, 19]. The general procedure weighs the training loss to provide each class
equal attention. In this paper, we implement the Inverse Number of Samples
strategy [18]. This method computes the loss-weight of each sample as a
normalized reciprocal of the sample size.

###  2.2 Maximum Attention Visualization

While test data is used to verify the network’s generalization ability, it
does not show that the network attend to the intended features. To visualize
the network’s attention, a novel saliency method has been developed. Our
visualization focuses on the points contributing to the MaxPool, as only these
points contribute to the final classification. By separating the MaxPool
feature, the forward propagation of the fully connected layer can be used to
calculate the saliency. The resulting class contribution can be calculated by
increasing a value of the MaxPool feature, running a forward-pass, and measure
the resulting change in prediction value. Furthermore, the major contributors
for a class can be determined by setting a cutoff value in relation to the
change in prediction. Positive contributions are colored green, negative red,
and points with a contribution under the cutoff value are colored blue. We
name this visualization method Maximum Attention, as only the points which
contribute to the MaxPool are shown.

##  3 Experiments

Several tests are performed to demonstrate the performance of the developed
method. Firstly our method is compared with Bogacz et al. using the same
dataset [5]. Secondly, the weight distribution allows us to sample a larger
uneven dataset on which our method is trained. Additionally, two new
classification datasets have been made concerning tablet metadata. These tests
can help with classifying tablets when experts are not available. Only UR III
data is used for these experiments to simplify the task, as these are the most
numerous type.

All experiments are performed using the same architecture and the same hyper-
parameters. The hyper-parameters are similar to Bogacz et al. [5], i.e. 200
epochs, batch size one, and trained with the ADAM optimizer [20]. The only
difference is the learning rate which decays from $10^{-3}$ to $10^{-7}$.

###  3.1 Performance on the comparison dataset

A comparison is performed with the dataset introduced by Bogacz et al. The
training and test splits are obtained from the original authors. The dataset
consists of tablets from four different time periods. For each time period,
the sample size is 100, except for the Old Assyrian, where 37 are present.

While the original papers duplicate the Old Assyrian tablets to have 100, the
loss-weighing allows us to keep it at 37. The Inverse Number of Samples set
the Old Assyrian loss-weight to 1.9 and the others to 0.7. The final F1-score
on the test set is 0.88, which outperforms Bogacz et al. at 0.84. Bogacz et
al. also tested a Raster baseline and a reduced PointNet++ [12], that obtains
an F1-Score of 0.68 and 0.62 respectively, which our method outperforms. The
F1-scores of our method for each class is shown in Fig. 3, as Ours Identical
Data. It is seen that our method outperforms Bogacz et al., shown as Bogacz,
on all classes, especially the under-represented class of Old Assyrian, with a
difference of 0.53 to 0.80 in F1-score.

As the loss-weighting allows uneven sample sizes, the fixed sample size is
unnecessary. To take advantage of this, new training data is sampled using all
available tablets, excluding the test data. Additionally, tablets too large,
according to Bogacz et al., are also excluded [5]. The new dataset now
includes 631 tablets, with 312 from UR III. The very large unbalance set the
loss-weight of UR III to 0.3, where Old Assyrian is at 2.3. The resulting
F1-score is further improved to 0.92. The results for each class are shown in
Fig. 3 as Ours Increased Data. It is seen that the heavy unbalance towards UR
III does not lead to over-fitting and the F1-score for all classes increases.
Again, the smallest class, Old Assyrian, actually increases the most.

Fig. 3: F1-score for each class. Results are shown for Bogacz, ours with
identical training data, and increased training data.

###  3.2 Classifying seal presence

A different type of classification task is to determine if seal imprints are
present on the tablets. Seals are sometimes found impressed on tablets as a
signature [1, p. 27], either impressed on intentional blank spaces or directly
over the text.

The dataset is created by using transliterations from HeiCuBeDa [6] and
searching for the ”@seal” tag. Tablets with no transliteration are discarded.
This results in 136 tablets with seal impressions and 223 without, using ten
percent for testing. The test results are shown in Tab. 1. The performance
shows that the network can generalize to this task, but further improvements
can be obtained on this dataset.

| Predicted Label
---|---
| w/ seal | w/o seal
True Label | w/ seal | 10 | 2
w/o seal | 1 | 22
Table 1: Seal Presence Classification

###  3.3 Classifying left side sign presence

Another task we introduce is to classify if signs have been written on the
left side of the tablet. For some tablets, the writing is not only on the
front and back of the tablet but also on the left side [21]. This writing does
not follow the general writing direction but is rotated ninety degrees. The
task is made difficult by the fact that the general writing often overlaps
onto the left side [1, p. 14]. The network, therefore, needs to discriminate
the sign orientation. An additional challenge is that very few signs can be
present, as shown in Fig. 4. The dataset is created by using transliterations
from HeiCuBeDa [6] and searching for the ”@left” tag. The resulting training
set is heavily unbalanced as 48 tablets have left side signs, and 276 do not.
The performance on the test set is shown in Tab. 2. The network is able to
classify most tablets correctly but makes two errors.

Fig. 4: Top: Tablet ”HS 2275” shown from left/middle/right. Bottom: Maximum Attention overlaid according to Sec. 2.2. Best viewed digitally. | Predicted Label
---|---
| w/ text | w/o text
True Label | w/ text | 6 | 1
w/o text | 1 | 27
Table 2: Left Side Text Presence

To verify that the network focuses on the intended signs the Maximum
Activation visualization is used. The activation for two different tablets
with left side writing is shown in Fig. 4 and Fig. 5. It is shown that the
network successfully focuses on the actual signs.

###  3.4 Ablation Study

Several tests are performed to verify the effectiveness of the developed
network. All tests are performed on the dataset from Bogacz et al., where our
method obtained an average F1-score of 0.88.

The first test is to verify that the developed network outperforms a classic
DGCNN [11]. As a result of hardware limitations, the DGCNN only has two
convolutional layers as opposed to three, and the batch normalization is
removed. DGCNN obtains an average F1-score of 0.83, which is far outperformed
by our network. However, the reduced DGCNN outperforms the reduced PointNet++
at 0.62 indicating the importance of the local neighbor information.

An ablation study is performed to test the influence of each contribution. The
result of each ablation is shown in Tab. 3. In the first test, the standard
neighbor search from DGCNN is used as opposed to our minimum distance, shown
as MD. The second test replaces the SparseEdge feature with the classic Edge
feature from the DGCNN, shown as SE.

A test is also performed without using the MaxPool layer. The AvgPool output
is simply used directly by the fully connected layer. This reduced network is
also tested by replacing the AvgPool layer with an MaxPool layer. The two test
are shown as Avg and Max, respectively. Finally, the network is tested without
group normalization, shown as GN. It is seen that all parts contribute to the
performance. The highest contribution comes from using a MaxPool layer, while
the AvgPool in combination also improves performance. The SparseEdge also
improves the performance significantly.

Fig. 5: Top: Tablet ”HS 2269” shown from left/middle/right. Bottom: Maximum Attention overlaid according to Sec. 2.2. Best viewed digitally. Omitted | None | MD | SE | Max | Avg | GN
---|---|---|---|---|---|---
F1-score | 0.88 | 0.87 | 0.85 | 0.82 | 0.86 | 0.87
Table 3: Resulting F1-scores of ablation study.

##  4 Conclusion and future work

In this work, we presented a novel network architecture for the classification
of large-scale point clouds. The developed network is tested on a comparison
dataset where it achieves state-of-the-art performance. We also introduce two
new classification tasks that demonstrate the network’s abilities. Finally,
the Maximum Attention visualization method is introduced, which confirms that
the network targets the intended features. The networks greatest limitation is
the memory constraints, restricting the network size. The part consuming the
largest amount of memory is the adjacency matrix which is used to compute
neighbors, as the size is $N^{2}$, with $N=32,768$ points. With access to a
GPU with more memory, the performance of a full-size network could be
computed. Another interesting aspect is the development of networks able to
compute the neighbor information without requiring the large adjacency matrix
The generalizability of the network could also be tested by introducing other
tablet databases [2, 7].

## References

  * [1] Christopher Bromhead Fleming Walker,  Cuneiform, vol. 3,  Univ of California Press, 1987.
  * [2] Jonathan D Cohen, Donald D Duncan, Dean Snyder, Jerrold Cooper, Subodh Kumar, Daniel V Hahn, Yuan Chen, Budirijanto Purnomo, and John Graettinger,  “iclay: Digitizing cuneiform.,”  in VAST, 2004, pp. 135–143.
  * [3] Marcos Zampieri, Shervin Malmasi, Yves Scherrer, Tanja Samardžić, Francis Tyers, Miikka Silfverberg, Natalia Klyueva, Tung-Le Pan, Chu-Ren Huang, Radu Tudor Ionescu, et al.,  “A report on the third vardial evaluation campaign,”  Association for Computational Linguistics, 2019.
  * [4] Shai Gordin, Gai Gutherz, Ariel Elazary, Avital Romach, Enrique Jiménez, Jonathan Berant, and Yoram Cohen,  “Reading akkadian cuneiform using natural language processing,”  PloS one, vol. 15, no. 10, pp. e0240511, 2020.
  * [5] Bartosz Bogacz and Hubert Mara,  “Period classification of 3d cuneiform tablets with geometric neural networks,”  in 2020 17th International Conference on Frontiers in Handwriting Recognition (ICFHR). IEEE, 2020, pp. 246–251.
  * [6] Hubert Mara and Bartosz Bogacz,  “Breaking the code on broken tablets: The learning challenge for annotated cuneiform script in normalized 2d and 3d datasets,”  in 2019 International Conference on Document Analysis and Recognition (ICDAR). IEEE, 2019, pp. 148–153.
  * [7] Sean E. Anderson and Marc Levoy,  “Unwrapping and visualizing cuneiform tablets,”  IEEE Computer Graphics and Applications, vol. 22, no. 6, pp. 82–88, 2002.
  * [8] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas,  “Pointnet: Deep learning on point sets for 3d classification and segmentation,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 652–660.
  * [9] Yulan Guo, Hanyun Wang, Qingyong Hu, Hao Liu, Li Liu, and Mohammed Bennamoun,  “Deep learning for 3d point clouds: A survey,”  IEEE transactions on pattern analysis and machine intelligence, 2020\.
  * [10] Saifullahi Aminu Bello, Shangshu Yu, Cheng Wang, Jibril Muhmmad Adam, and Jonathan Li,  “Deep learning on 3d point clouds,”  Remote Sensing, vol. 12, no. 11, pp. 1729, 2020.
  * [11] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon,  “Dynamic graph cnn for learning on point clouds,”  ACM Transactions on Graphics, 2019.
  * [12] Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas,  “Pointnet++: Deep hierarchical feature learning on point sets in a metric space,”  in Advances in neural information processing systems, 2017, pp. 5099–5108.
  * [13] Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller,  “Splinecnn: Fast geometric deep learning with continuous b-spline kernels,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 869–877.
  * [14] Binbin Zhang, Shikun Huang, Wen Shen, and Zhihua Wei,  “Explaining the pointnet: What has been learned inside the pointnet?,”  in CVPR Workshops, 2019, pp. 71–74.
  * [15] Shikun Huang, Binbin Zhang, Wen Shen, and Zhihua Wei,  “A claim approach to understanding the pointnet,”  in Proceedings of the 2019 2nd International Conference on Algorithms, Computing and Artificial Intelligence, 2019, pp. 97–103.
  * [16] Frederik Hagelskjær and Anders Glent Buch,  “Bridging the reality gap for pose estimation networks using sensor-based domain randomization,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 935–944.
  * [17] Yuxin Wu and Kaiming He,  “Group normalization,”  in Proceedings of the European conference on computer vision (ECCV), 2018, pp. 3–19.
  * [18] Yu-Xiong Wang, Deva Ramanan, and Martial Hebert,  “Learning to model the tail,”  in Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017, pp. 7032–7042.
  * [19] Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang,  “Learning deep representation for imbalanced classification,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 5375–5384.
  * [20] Diederik P Kingma and Jimmy Ba,  “Adam: A method for stochastic optimization,”  arXiv preprint arXiv:1412.6980, 2014.
  * [21] Christina Tsouparopoulou,  “Reflections on paratextual markers and graphic devices in ur iii administrative documents,”  Textual Cultures, vol. 8, no. 2, pp. 1–14, 2013.