# Testing for Typicality with Respect to an
Ensemble of Learned Distributions

Forrest Laine & Claire Tomlin
Department of Electrical Engineering and Computer Sciences
University of California, Berkeley
Berkeley, CA, 94720, USA
{forrest.laine<EMAIL_ADDRESS>
###### Abstract

Methods of performing anomaly detection on high-dimensional data sets are
needed, since algorithms which are trained on data are only expected to
perform well on data that is similar to the training data. There are
theoretical results on the ability to detect if a population of data is likely
to come from a known base distribution, which is known as the goodness-of-fit
problem. One-sample approaches to this problem offer significant computational
advantages for online testing, but require knowing a model of the base
distribution. The ability to correctly reject anomalous data in this setting
hinges on the accuracy of the model of the base distribution. For high
dimensional data, learning an accurate-enough model of the base distribution
such that anomaly detection works reliably is very challenging, as many
researchers have noted in recent years. Existing methods for the one-sample
goodness-of-fit problem do not account for the fact that a model of the base
distribution is learned. To address that gap, we offer a theoretically
motivated approach to account for the density learning procedure. In
particular, we propose training an ensemble of density models, considering
data to be anomalous if the data is anomalous with respect to any member of
the ensemble. We provide a theoretical justification for this approach,
proving first that a test on typicality is a valid approach to the goodness-
of-fit problem, and then proving that for a correctly constructed ensemble of
models, the intersection of typical sets of the models lies in the interior of
the typical set of the base distribution. We present our method in the context
of an example on synthetic data in which the effects we consider can easily be
seen.

##  1 Introduction

Machine learning models are inherently non-robust to distributional shift, and
at no fault of the model necessarily. There is no reason to expect that models
should perform well on data that is dissimilar to the data on which they were
trained. Interestingly, despite the fact that researchers and practitioners
have been able to train models that perform exceptionally well on a variety of
challenging tasks, we are still bad at reliably predicting when those models
will fail. This implies that not only will the models have undefined behavior
on out-of-distribution data, we are unable to detect when the models are
presented with out-of-distribution data. This poses a conundrum, since we wish
to deploy our high-performing models, yet often we can’t since they can
potentially have unpredictable behavior at unpredictable instances.

Since training a model that is robust to all possible distributional shifts
the model might encounter is potentially impossible, a more modest approach
might be to come up with ways for detecting out-of-distribution data. These
detections could then act as an indication that the model might be incorrect.
This ability to predict incorrectness can go a long way in making systems more
reliable.

The problem of detecting out-of-distribution data has a long history, and is
formally known as the goodness-of-fit problem. Statisticians have proved
bounds on the probability of detecting populations of out-of-distribution
data, such as in Barron (1989) and Balakrishnan et al. (2019). These type of
bounds show that certain tests can be performed which are capable of
discerning (with non-trivial probability) that populations of data sampled
from distributions at least some positive distance away from the base
distribution are anomalous. However, in order to perform the proposed tests,
an explicit form of the probability density function (or probability mass
function) describing the base distribution is needed. For most real-world data
sets, this density is not known, and must be estimated. While there has been a
lot of analysis on the ability to detect anomalous data, those analyses
typically do not account for the fact that the base density for which the
tests are designed is learned.

Empirically, however, many researchers have noted that detecting anomalous
data in high dimensions using learned densities is hard, even when using
modern, powerful density estimators. For example, the researchers in Nalisnick
et al. (2018) and Choi & Jang (2018) both claim that state-of-the-art learned
densities are not suitable for anomaly detection since they assign higher
probability to some out-of-distribution data than the data on which the models
were trained. The authors in Nalisnick et al. (2019) realized that such a
phenomenon is actually not cause for alarm, and is even expected with high-
dimensional distributions. Therefore they propose performing an anomaly
detection test based on the typicality of data under the learned density
instead of the likelihood of data under the learned density. However, in that
work, the authors noted such a test still performed poorly in some cases.

In this article, we investigate why goodness-of-fit tests are challenging when
using learned densities. In particular, we analyze how the typical set of
learned distributions relates to the typical set of the ground truth
distribution. In order to do this, we work with synthetic distributions in
which the probability density function is known exactly. The contributions we
make are summarized as the following:

  * •

We prove error rate bounds on the goodness-of-fit test based on testing for
typicality with respect to the base distribution

  * •

We prove theorems stating that the typical sets of any two distributions
having sufficiently high KL divergence must have low intersection, and that
distributions having low KL divergence must have non-zero intersection.

  * •

We use these theorems to motivate our proposed method for conservative
goodness-of-fit testing. Specifically, we propose training an ensemble of
models, and show that by taking the intersection of their typical sets, we can
approximately recover the typical set of the ground truth distribution. We
show that such an ensemble can exist and give sufficient conditions for its
existence.

  * •

We demonstrate on synthetic data sets that the typical set of standard learned
distributions and the ground-truth distribution often have low intersection,
even when the class of densities from which we approximate the ground truth
contains the ground-truth. We validate that our proposed method addresses this
issue.

##  2 Preliminaries

The setting we are concerned with is the following. Consider a continuous
random variable ${\textnormal{x}}\in\mathcal{X}$ with probability density
function $p({\textnormal{x}})$. Let
${\textnormal{x}}^{n}:=({\textnormal{x}}_{1},{\textnormal{x}}_{2},...,{\textnormal{x}}_{n})$
denote the collection of $n$ random variables x. Let $h_{p}$ denote the
differential entropy of $p({\textnormal{x}})$. For $\epsilon>0$ and positive
integer $n$, The typical set with respect to $p({\textnormal{x}})$ is defined
as the following:

$T_{\epsilon}^{(n)}:=\Big{\\{}{\textnormal{x}}^{n}\in\mathcal{X}^{n}:|-\frac{1}{n}\log
p({\textnormal{x}}^{n})-h_{p}|<\epsilon\Big{\\}}.$ (1)

In words, this is the set of sequences of samples whose average negative-log-
probability is close to the differential entropy. This set has high
probability under $p({\textnormal{x}})$, implying that most sequences of data
points sampled from $p({\textnormal{x}})$ are contained in this set (Cover &
Thomas, 2012).

###  2.1 Hypothesis Testing

We are interested in determining the plausibility that some collection of
samples $\tilde{{\textnormal{x}}}^{n}\in\mathcal{X}^{n}$ were sampled i.i.d.
according to $p({\textnormal{x}})$. In hypothesis testing terminology, we are
interested in determining which of two hypotheses are more probable:

  * •

The null-hypothesis,  $\mathcal{H}_{0}:=\tilde{{\textnormal{x}}}^{n}\sim
p({\textnormal{x}})$

  * •

The alternative-hypothesis,
$\mathcal{H}_{1}:=\tilde{{\textnormal{x}}}^{n}\sim\hat{p}({\textnormal{x}})$,

where here $\hat{p}({\textnormal{x}})$ is any distribution such that
$D_{\mathrm{KL}}(p\|\hat{p})\geq d$. If we define
$A_{n}\subset\mathcal{X}^{n}$ to be the acceptance region for the null-
hypothesis, or the set of all sequences ${\textnormal{x}}^{n}$ such that
$\mathcal{H}_{0}$ is deemed more probable, then we can define the
probabilities of error as the following:

$\displaystyle\alpha_{n}=p^{n}(A_{n}^{\mathsf{c}}),\quad\beta_{n}=\max_{\tilde{p}:D(p\|\tilde{p})\geq
d}\tilde{p}^{n}(A_{n}).$ (2)

Typically we desire tests that minimize $\beta_{n}$ for a fixed $\alpha_{n}$,
or tests that minimize some linear combination of the two.

The authors in Nalisnick et al. (2019) propose a test procedure which accepts
the null-hypothesis iff $\tilde{{\textnormal{x}}}^{n}\in T_{\epsilon}^{(n)}$.
In other words, a collection of points are determined to be anomalous with
respect to $p({\textnormal{x}})$ iff $\tilde{{\textnormal{x}}}^{n}\not\in
T_{\epsilon}^{(n)}$. In that work, they show that this test performs about as
well as other tests such as the Student’s t-test, the Kolmogorov-Smirnov test,
the Maximum Mean Discrepancy test, and the Kernelized Stein Discrepancy test.
We note that in those comparisons, all tests are performed with respect to a
learned density as a proxy for the ground-truth density.

In this work, we consider the same typicality-based test for accepting or
rejecting the null hypothesis. We focus on this test since it allows for
analysis into what happens when the proxy learned density for which the
typical set is constructed is different from the ground-truth distribution
$p({\textnormal{x}})$. In order to validate this approach, we first prove that
for a fixed $\alpha_{n}$, the typical set test achieves an error rate
$\beta_{n}$ that is at worst, given by:

######  Theorem 1.

Let the region of acceptance for the typicality test be defined by the set
$T_{\epsilon}^{(n)}(p({\textnormal{x}}))$. For $n$ sufficiently large, then
$\alpha_{n}<\epsilon$, and

$\beta_{n}<\max_{\tilde{p}:D(p\|\tilde{p})\geq
d}e^{-n(D_{\mathrm{KL}}(\tilde{p}\|p)+h_{\tilde{p}}-h_{p}-3\epsilon)}+3\epsilon$

###### Proof of Theorem 1.

See Section A.1. ∎

This theorem states that for a fixed rate of correctly accepting
$\mathcal{H}_{0}$, the test for typicality will fail to detect anomalous data
at a rate no greater than the bound given.

###  2.2 Density Learning as Optimization

In order to perform the test on typicality to determine whether a sequence of
data points are anomalous or not, a model of the probability density function
$p({\textnormal{x}})$ is needed. For many practical applications, we are only
ever presented with a data set of $N$ samples from $p({\textnormal{x}})$,
which we denote
$\bar{X}=(\bar{{\textnormal{x}}}_{1},\bar{{\textnormal{x}}}_{2},...\bar{{\textnormal{x}}}_{N})$.
However, an estimate of the ground-truth density can be learned. We denote a
parameterized distribution by $q({\textnormal{x}};{\bm{\theta}})$, which can
be learned by minimizing the following objective:

$\min_{{\bm{\theta}}}D_{\mathrm{KL}}(p({\textnormal{x}})\|q({\textnormal{x}};{\bm{\theta}})).$
(3)

The KL divergence is defined by
$D_{\mathrm{KL}}(p({\textnormal{x}})\|q({\textnormal{x}};\theta)):=\mathbb{E}_{p}[log\frac{p({\textnormal{x}})}{q({\textnormal{x}};\theta)}]$.
By expanding terms and eliminating constants, it is clear that an equivalent
optimization problem is

$\max_{{\bm{\theta}}}\mathbb{E}_{p}[log\
q({\textnormal{x}};{\bm{\theta}})]\approx\max_{{\bm{\theta}}}\frac{1}{N}\sum_{i=1}^{N}log\
q(\bar{{\textnormal{x}}}_{i};{\bm{\theta}}).$ (4)

The optimal ${\bm{\theta}}$ in this problem is that which maximizes the log
likelihood on the data set $\bar{X}$. This is why this optimization is
commonly referred to as maximum-likelihood estimation. Importantly, the
dependence on the unknown true distribution $p({\textnormal{x}})$ was removed
through the use of the law of large numbers. Since the KL-divergence is equal
to zero if and only if $p({\textnormal{x}})=q({\textnormal{x}};{\bm{\theta}})\
\forall x\in\mathcal{X}$, this objective is well-motivated if we wish that
$q({\textnormal{x}};{\bm{\theta}})\approx p({\textnormal{x}})$. However, there
are many other statistical divergences between distributions that would also
be suitable as objectives in the optimizations above. In fact, many of these
other divergences might be preferred, especially in the context of anomaly
detection. Among other reasons, this is because when the parameterized class
of distributions $q({\textnormal{x}};{\bm{\theta}})$ is highly expressive, the
optimizations are non-convex, and local optima may be found with sub-optimal
properties. This can be true even if there exist some ${\bm{\theta}}^{*}$ such
that $q({\textnormal{x}};{\bm{\theta}}^{*})=p({\textnormal{x}})$.

For example, by looking at the form of the KL-divergence, there is no direct
penalty for $q({\textnormal{x}};{\bm{\theta}})$ in assigning a high density to
points far away from any of the $\bar{{\textnormal{x}}}_{i}$’s. This can lead
to locally optimal learned densities which have high probability density in
regions of $\mathcal{X}$ that $p(x)$ does not. This can potentially lead to
situations in which a collection of points can be anomalous with respect to
$p({\textnormal{x}})$, but in-distribution with respect to the sub-optimally
learned $q({\textnormal{x}};{\bm{\theta}})$.

There exist other divergences which do not suffer this effect, but it is not
obvious how to optimize with respect to them. For example, the reverse KL-
divergence, which switches the places of $p({\textnormal{x}})$ and
$q({\textnormal{x}};{\bm{\theta}})$ in the standard KL-divergence, has an
alternate effect; $q({\textnormal{x}};{\bm{\theta}})$ is directly penalized
for assigning high density to anywhere that does not also have high density
under $p({\textnormal{x}})$. Unfortunately, this requires direct knowledge of
$p({\textnormal{x}})$ to evaluate the objective, as do all divergences other
than the forward KL, to the best of our knowledge. This makes the forward KL-
divergence special in that it is the only divergence which can directly be
optimized for.

These implications are important when considering how learning a density
affects the hypothesis testing problem.

###  2.3 Modern Density Parameterizations

There have been many advancements in the parameterization of density models in
recent years. Broadly speaking, there are two main classes of
parameterizations, being latent-variable models and invertible flow models.
Latent variable models, such as Variational Auto-encoders (Rezende et al.,
2014; Kingma & Welling, 2013), refer to models which map a lower-dimensional,
latent random variable through a probabilistic mapping into data space.
Because the image of any non-surjective function necessarily has measure zero,
these type of models cannot have deterministic mappings, or else the model
cannot constitute a valid probability distribution. The probabilistic mapping
corrects for this, and the ability to represent data in a lower-dimensional
latent space is a nice property of such models.

The other major class of parameterizations are those which map a probability
density function through a bijective, continuously differentiable mapping,
which we refer to as change-of-variable models. These models include
autoregressive models, such as PixelCNN (Oord et al., 2016; Salimans et al.,
2017), and invertible flow models, such as NICE (Dinh et al., 2014), RealNVP
(Dinh et al., 2016), and GLOW (Kingma & Dhariwal, 2018). Often autoregressive
models are considered as a separate class of model than invertible flow
models, but we lump them together as they are effectively different
implementations of the same concept. All change-of-variable models operate on
the ability to express a probability density function through a change of
variables. Specifically, if
$m({\textnormal{x}};{\bm{\theta}}):\mathcal{X}\to\mathcal{Z}$ is a
continuously differentiable bijection, and $r({\textnormal{z}};{\bm{\theta}})$
is a probability density function corresponding to random variable
${\textnormal{z}}\in\mathcal{Z}$, then together $m$ and $r$ implicitly define
a probability density function over random variable
${\textnormal{x}}\in\mathcal{X}$:

$q({\textnormal{x}};{\bm{\theta}})=r({\textnormal{z}};{\bm{\theta}})\begin{vmatrix}\frac{dm({\textnormal{x}};{\bm{\theta}})}{d{\textnormal{x}}}\end{vmatrix}.$
(5)

So long as the determinant in (5) is easy to evaluate, the probability density
$q({\textnormal{x}};{\bm{\theta}})$ can be evaluated and the parameters
${\bm{\theta}}$ can easily be optimized over. In both of these broad class of
parameterizations, there have been many clever implementations of these
concepts, creating highly expressive density models. In this work, our
considerations are tangential and complementary to the advancements in these
parameterizations. This is because regardless of the parameterization used,
all of these models rely on optimizing the forward KL-divergence in order to
learn their parameters. The effects we study in this paper occur even when the
parameterization includes the ground-truth density we wish to learn,
indicating that advancements in the expressivity of the models are unlikely to
fix the undesired effects.

##  3 Case Study on Synthetic Data

Figure 1: Random projections of samples from a 100-dimensional Mixture of
Gaussians Distribution.

To understand why hypothesis testing is so difficult when using learned
densities, we investigate this occurrence by learning synthetic probability
distributions for which the ground-truth $p({\textnormal{x}})$ is known. In
particular, we consider the problem of learning the density of a high-
dimensional mixture of Gaussians.

Let $M$ denote the number of mixture components in the base distribution. Then
we define the base distribution as the following:

$p({\textnormal{x}}):=\sum_{m=1}^{M}\pi_{m}p_{m}({\textnormal{x}};{\bm{\mu}}_{m},{\bm{\Sigma}}_{m}),$
(6)

where $p_{m}({\textnormal{x}};{\bm{\mu}}_{m},{\bm{\Sigma}}_{m})$ is the
probability density function associated with a Gaussian distribution with mean
${\bm{\mu}}_{m}$ and covariance ${\bm{\Sigma}}_{m}$. For this investigation,
we define the space $\mathcal{X}:=\mathbb{R}^{100}$, so that effects dependent
on the dimensionality of $\mathcal{X}$ are evident. Here we consider the
parameters ${\bm{\mu}}_{m}$ and ${\bm{\Sigma}}_{m}$ to be chosen such that the
${\bm{\mu}}_{m}$ are sampled from a uniform distribution over a hyper-ball
with radius $r=3.0$, and the matrices ${\bm{\Sigma}}_{m}$ are diagonal
matrices with the negative logarithm of the diagonal elements each sampled
from a uniform distribution between 1.0 and 3.0. We fix the $\pi_{m}=1/M$. In
all experiments we choose the number of components to be $M=20$.

Some random projections of samples from one such $p({\textnormal{x}})$ can be
seen in Figure 1. Note that although in each projection the probability mass
of the different mixture components seem to be overlapping, due to the
dimensionality of the space, each mode is separated by a relatively large
distance. In the example shown in Figure 1, the minimum distance between the
means of each mixture component is 3.62. Furthermore, the max probability of
any mode with respect to any of the other mixture components is roughly
$1e$-$20$. This means that each of the $M$ modes in the mixture distribution
are clearly distinct and separated by regions of near-zero probability.

Figure 2: Learning curve for the Mixture of Gaussian Experiment. Average
(across experiments) train and test neg-log-likelihoods are plotted along with
their $\pm 1$ standard deviation region.

We attempt to learn $p({\textnormal{x}})$ by optimizing (4), for a
$q({\textnormal{x}};{\bm{\theta}})$ parameterized _exactly_ as
$p({\textnormal{x}})$. In other words, the parameters ${\bm{\theta}}$ are the
set
$\\{\pi_{1},{\bm{\mu}}_{1},{\bm{\Sigma}}_{1},\pi_{2},{\bm{\mu}}_{2},{\bm{\Sigma}}_{2},...,\pi_{M},{\bm{\mu}}_{M},{\bm{\Sigma}}_{M}\\}$,
where the $\pi_{m}>0$ are constrained to sum to 1, and the ${\bm{\Sigma}}_{m}$
are constrained to be positive definite and diagonal.

Figure 3: Bar plots showing the relative weighting of the mixture components
in the learned densities in the Mixture of Gaussians experiment. Here it can
be seen that each of the 5 learned densities use only approximately 12 out of
the 20 modes to explain the data.

We perform five experiments, each time randomly initializing the parameters
${\bm{\theta}}$ exactly as was done for $p({\textnormal{x}})$. We use the
indices $k\in\\{1,...,K=5\\}$ to index the 5 experiments ran, and refer the
the $k$-th learned density as $q_{k}({\textnormal{x}};{\bm{\theta}}_{k})$. The
training curve for learning these densities can be seen in Figure 2, which
shows the average test and train errors across experiments, and random
projections of the resulting samples overlaid on samples of the base
distribution can be seen in Figure 5. Examining these figures, we see that the
learning procedure converged, yet the samples generated from the learned
distributions clearly differ from the ground-truth samples. By examining the
relative probabilities of each mixture component for the learned densities
(Figure 3), we see that all of the learned densities attempt to represent the
$M=20$ modes of the base distribution using only about 12 of their 20 modes.

Recalling that the base distribution $p({\textnormal{x}})$ has distinctly
separated modes, the fact that the base distributions represent the data using
fewer modes directly implies that the models necessarily assign high density
to regions in-between modes of the ground-truth distribution. This behavior is
very troublesome for the purposes of anomaly detection, since intuitively
these regions of high-density in-between modes of the true distribution
effectively include those regions in the typical set of the learned density.
This means that data-points lying in these regions, which should be considered
anomalous with respect to the true distribution, are not detectable by
hypothesis tests which test for typicality (or likelihood, for that matter).

Figure 4: Histograms of the negative log-likelihood of the ground truth
distribution, evaluated on samples from the ground-truth distribution (top-
left), and samples from each of the learned distributions in the Mixture of
Gaussians experiment. As it can be seen, only about a third of samples from
each learned distribution have negative log-likelihood close to the ground-
truth sample average.

To validate this claim, we generate histograms of the ground-truth negative
log-likelihoods on samples from the base distribution and each of the learned
distributions, which can be seen in Figure 4. We also list in Table 1 the
percentages of samples from each learned density that lie in the typical sets
of the ground-truth distribution and every other learned distribution. These
statistics give a sense of the intersection of the typical sets of the learned
and ground-truth densities. In particular, despite almost all of the ground-
truth samples lying in the typical set of each learned-distribution, only
about $40\%$ of the samples from each learned distribution lie in the typical
set of the true distribution. In the context of anomaly detection, this means
that if we used a test for typicality using one of these learned densities,
about $60\%$ of the region of acceptance would include points that are not
actually typical with respect to the base distribution.

The mismatch in typical sets corroborates what was stated in Section 2.2,
which was that the forward KL-divergence objective can lead to assigning
density to regions far from any data points. Here, the learned densities are
optimized to explain the data. The way in which they do results in
inadvertently explaining other regions of the data space as well.

Table 1: Percentages of samples lying in the Typical Set of each of the learned and ground-truth distributions. Here, we take $\epsilon$ to be such that approximately $95\%$ of samples from a distribution lie in its own typical set, and we set $n=1$. Note that each of the learned densities include most of the ground-truth samples from $p({\textnormal{x}})$ in their typical sets, but the typical set of the ground-truth distribution excludes most samples from the learned densities. Furthermore, most of the samples from the learned densities are excluded from the typical sets of other learned densities.  | Sampling Distribution
---|---
|  $p({\textnormal{x}})$ |  $q_{1}({\textnormal{x}};{\bm{\theta}}_{1})$ |  $q_{2}({\textnormal{x}};{\bm{\theta}}_{2})$ |  $q_{3}({\textnormal{x}};{\bm{\theta}}_{3})$ |  $q_{4}({\textnormal{x}};{\bm{\theta}}_{4})$ |  $q_{5}({\textnormal{x}};{\bm{\theta}}_{5})$
$T_{\epsilon}^{(n)}(p({\textnormal{x}}))$ |  95.3 |  37.8 |  34.4 |  42.9 |  35.0 |  40.7
$T_{\epsilon}^{(n)}(q_{1}({\textnormal{x}};{\bm{\theta}}_{1}))$ |  93.3 |  93.4 |  35.1 |  41.2 |  34.3 |  38.9
$T_{\epsilon}^{(n)}(q_{2}({\textnormal{x}};{\bm{\theta}}_{2}))$ |  93.2 |  69.6 |  95.0 |  80.6 |  68.9 |  73.0
$T_{\epsilon}^{(n)}(q_{3}({\textnormal{x}};{\bm{\theta}}_{3}))$ |  96.2 |  47.0 |  33.9 |  97.0 |  40.5 |  47.4
$T_{\epsilon}^{(n)}(q_{4}({\textnormal{x}};{\bm{\theta}}_{4}))$ |  94.5 |  47.4 |  44.5 |  44.8 |  94.5 |  50.4
$T_{\epsilon}^{(n)}(q_{5}({\textnormal{x}};{\bm{\theta}}_{5}))$ |  95.7 |  46.6 |  39.9 |  48.9 |  38.2 |  93.9

The example presented here is admittedly a simple one, yet it demonstrates
that coming up with more clever parameterizations will not necessarily result
in a better learning process. In this example, the learned densities are
expressive enough to learn the true distribution, however get stuck in poor
local minima due to bad initializations. This is the case in this situation,
even though we initialized the learned distributions according to the same
distribution over parameters that the true distribution was initialized from.
For real data sets, it is unlikely that the parameterized space of densities
we learn over can ever represent the density we are trying to estimate, and
even if it could, finding a proper initialization might be exceptionally
difficult. Therefore, the effects illustrated in this example are expected to
occur in more complicated (and interestig) domains, and should be accounted
for in those domains as well.

In order to address this issue of over-assignment of density, we turn to
ensembles of learned distributions. As can be seen in Table 1, we find that
due to the random initializations of each of the learned distributions, the
regions in which they over-assign density have low intersection. In the
following section, we demonstrate how this property can be leveraged to
account for the mismatch in typical sets between learned and target densities.

##  4 Typical Sets of Ensembles of Learned Densities

We propose an alternative test to discern the two hypotheses described in
Section 2.1. First we define what we call the multi-typical set, with respect
to an ensemble of distributions $q_{k}({\textnormal{x}})$,
$k\in\\{1,...,K\\}$. For a given $\epsilon>0$ and positive integer $n$, this
set is defined as the following:

$T_{\epsilon}^{(n)}(\\{q_{1}({\textnormal{x}}),...,q_{K}({\textnormal{x}})\\}):=\Big{\\{}{\textnormal{x}}^{n}\in\mathcal{X}^{n}:\max_{k\in\\{1,...,K\\}}|-\frac{1}{n}\log
q_{k}({\textnormal{x}}^{n})-h_{k}|<\epsilon\Big{\\}}.$ (7)

Here, $h_{k}$ refers to the differential entropy of the $k$-th density in the
ensemble, $q_{k}({\textnormal{x}})$.

The method we propose is the following:

  1. 1.

Train an ensemble of parameterized densities,
$\\{q_{1}({\textnormal{x}};{\bm{\theta}}_{1},...,q_{K}({\textnormal{x}};{\bm{\theta}}_{K})\\}$,
using random initializations and using the maximum likelihood objective (4).

  2. 2.

When discerning between $\mathcal{H}_{0}$ and $\mathcal{H}_{1}$ (Section 2.1),
we choose $\mathcal{H}_{0}$ iff $\tilde{{\textnormal{x}}}^{n}\in
T_{\epsilon}^{(n)}(\\{q_{1}({\textnormal{x}};{\bm{\theta}}_{1}),...,q_{K}({\textnormal{x}};{\bm{\theta}}_{K})\\}).$

Before justifying this test theoretically, we first demonstrate its utility on
the Mixture of Gaussians example in Section 3. By using rejection sampling, we
generate samples that lie in the multi-typical set with respect to the 5
learned densities. Specifically, we generate 1000 samples from each model, and
then reject any of the resulting 5000 samples that do not lie in the typical
set of every model in the ensemble. The result of this is that $39.9\%$ of the
total samples make it through the rejection process, and $94.8\%$ of the
remaining samples lie within the typical set of the ground-truth distribution.
Furthermore, $96.6\%$ of the ground-truth samples are considered typical with
respect to the multi-typical set (7). We emphasize that this sampling
procedure is a proxy for estimating the interior of the multi-typical set. The
fact that about as many of these samples lie in the ground-truth typical set
as samples from the ground-truth distribution itself demonstrates that this
set works as a good indicator of typicality with respect to the ground-truth
distribution.

Therefore, by leveraging the use of an ensemble of learned densities, we have
shown that the shortcoming of any individual learned density model can be
overcome, at least in this motivating example.

The high-level idea for why this method works is that by sufficiently
minimizing the forward KL-divergence between the ground-truth distribution and
each of the learned distributions, there is guaranteed to be some intersection
of the typical sets of each model in the ensemble, and at least part of that
intersection must lie in the typical set of the ground-truth typical set.
Furthermore, we prove that if each model in the ensemble is sufficiently
different, such that the KL-divergence between each model is large enough,
then the intersection between their typical sets must be small. This implies
that the intersection of typical sets from sufficiently different models
trained to have low KL-divergence with the ground-truth model must lie almost
entirely in the interior of the typical set of the ground-truth distribution.

To formalize this argument, we state and prove the following theorems:

######  Theorem 2.

For continuous random variable ${\textnormal{x}}\in\mathcal{X}$, Consider some
distribution $p({\textnormal{x}})$ with differential entropy $h_{p}$, and any
collection of distributions $q_{k}({\textnormal{x}})$, $k\in\\{1,...,K\\}$,
all having $D_{\mathrm{KL}}(p\|q_{k})=d_{k}<\infty.$ Let
$T_{p}:=T_{\epsilon}^{(n)}(p)$ denote the typical set of $p$, and similarly
$T_{q_{k}}:=T_{\epsilon}^{(n)}(q_{k})$ the typical set of $q_{k}$ for each
$k\in\\{1,...,K\\}$.

For $n$ sufficiently large, if the following hold,

  * •

$\frac{1}{4\epsilon}\log\big{(}\frac{1-2\epsilon}{\frac{K-1}{K}+\epsilon}\big{)}>n$

  * •

$d_{k}<\frac{1}{n}\log\Big{(}\frac{1-2\epsilon}{\epsilon}e^{-4n\epsilon}-\frac{K-1}{\epsilon
K}\Big{)}+3\epsilon$

then

$Vol\Big{(}T_{p}\bigcap_{k}T_{q_{k}}\Big{)}>0.$

######  Theorem 3.

For continuous random variable ${\textnormal{x}}\in\mathcal{X}$, consider two
distributions, $q_{a}({\textnormal{x}})$ and $q_{b}({\textnormal{x}})$. Denote
$h_{a}$ and $h_{b}$, the differential entropy of these distributions,
respectively. Similarly, let $T_{a}:=T_{\epsilon}^{(n)}(q_{a})$ and
$T_{b}:=T_{\epsilon}^{(n)}(q_{b})$ represent the typical sets of $q_{a}$ and
$q_{b}$. If for some $0<r\leq 1$, and $n$ sufficiently large,

$D_{\mathrm{KL}}(q_{a}\|q_{b})>h_{b}-h_{a}-3\epsilon+\frac{1}{n}\log\Big{(}\frac{1}{r(1-\epsilon)e^{-2n\epsilon}-2\epsilon}\Big{)},$

then,

$\frac{Vol\big{(}T_{a}\cap T_{b}\big{)}}{Vol\big{(}T_{a}\big{)}}<r.$

Proof of both Theorems is given in Section A.1. The result of Theorem 2 is
that we can be sure that if every model in a density of learned distributions
is successful in minimizing the KL-divergence with respect to the ground-truth
density, then at least part of the multi-typical set must lie in the interior
of the typical set $T_{\epsilon}^{(n)}(p({\textnormal{x}}))$. The result of
Theorem 3 is that sufficiently different models in an ensemble must not have
large intersection. The condition should hold for the $r$ such that the ratio
of volumes in Theorem 3 is approximately the same for every pair of models in
the ensemble. If the conditions listed in both theorems hold, then the multi-
typical set must lie almost entirely in
$T_{\epsilon}^{(n)}(p({\textnormal{x}}))$. The result of this is that the
multi-typical set, if constructed according to the conditions given, can be
used as a conservative estimate of the typical set
$T_{\epsilon}^{(n)}(p({\textnormal{x}}))$. Here we use the word conservative,
since the conditions only are sufficient for the multi-typical set to act as
an under-approximation of $T_{\epsilon}^{(n)}(p({\textnormal{x}}))$.

The point of proving these theorems is to demonstrate that, in theory, an
ensemble of learned models can approximate the typical set of the ground-truth
distribution. The bounds given are sufficient conditions, but in practice we
find that it is much easier to find an ensemble of models such that the multi-
typical set approximates the ground-truth typical set than the bounds require.
Therefore, these theorems should be taken as proof that such a procedure is
well motivated, and not necessarily a guide for choosing the values of
$\epsilon$ and $n$ in practice.

##  5 Related Work

There are many works interested in goodness-of-fit testing for modern high-
dimensional data distributions. The works most similar to ours are Nalisnick
et al. (2019) and Choi & Jang (2018). The authors in Nalisnick et al. (2019)
use a test for typicality, showing empirically that it can perform about as
well as other traditional goodness-of-fit tests.

The authors in Choi & Jang (2018) leverage an ensemble of learned density
models to obtain better tests for anomaly detection than the other tests using
a single learned distribution. Specifically, they leverage the Watanabe-Akaike
Information Criterion (Watanabe, 2010) to produce a score which averages the
log probabilities across models of the ensemble, and subtracts the variance.
Without considering the variance term, taking the average log probability is
equivalent to the geometric mean of the probability density functions in the
ensemble, which acts as a sort of soft-min over the ensemble. Hence, in a way,
that method can be thought of as generating a density that is the point-wise
least probable density in the ensemble, where as the method we propose can be
thought of as taking the point-wise least typical density in the ensemble. We
elaborate more on this in Section A.2.

We also point out that the authors in Choi & Jang (2018) propose a baseline
test that resembles a test on typicality. They measure the distance from
latent variables in a normalizing flow model from the origin, assuming that
the distribution defined over the latent space is an isotropic Gaussian. This
measure only corresponds to measuring typicality if the bijection is volume
preserving.

There are many other methods for performing anomaly detection which do not
rely on traditional hypothesis testing theory. For example, the works in
Hendrycks & Gimpel (2016); Hendrycks et al. (2018); Liang et al. (2017)
propose using the outputs of trained neural networks themselves to discern
when the networks are presented with out-of-distribution data. By examining
the soft-max probabilities at the penultimate layer of these networks, they
can distinguish between in- and out-of-distribution inputs with relatively
good success. The work in Schlegl et al. (2017) similarly uses the output of
the final layers in the Discriminator in a GAN to detect anomalous data-
points. The authors in McAllister et al. (2019) use a VAE to make data points
more likely under a learned distribution before feeding them to a trained
model. An issue with all of these methods mentioned is that they rely on
checking whether low-dimensional, learned representations of the data are
anomalous or not. This has the downside that by construction, anomalous
aspects of the data can be missed if the low-dimensional representation is
invariant to those aspects. Nevertheless, some of these methods have proven to
work well in certain domains. A survey of other methods for leveraging deep
learning for anomaly detection can be found in in Chalapathy & Chawla (2019).

As an important aspect of hypothesis testing, it is important to consider the
many methods, old and new, for learning probability densities. Kernel Density
Estimation (KDE) methods are a traditional way of estimating densities,
although they do not scale to high-dimensional large data sets. An overview of
KDE methods can be found in Chen (2017). Some more modern approaches to
modeling densities were defined in Section 2.3. In addition to the
parameterizations of densities discussed there, many extensions have been
developed with appealing properties, such as Chen et al. (2017), Ho et al.
(2019), Grathwohl et al. (2018), De Cao et al. (2019), van den Oord et al.
(2017), and Razavi et al. (2019), to list a few. There are also other
objectives that are considered when learning densities, such as training a
density in a adversarial manner as in Grover et al. (2018) and Danihelka et
al. (2017). Alternatively, Li & Malik (2018) define implicit maximum
likelihood estimation, which can be thought of as approximately minimizing the
reverse KL-divergence.

##  6 Conclusion

We have presented a case study investigating why learned density models can
perform poorly when used in goodness-of-fit tests. We argue that the
hypothesis test used to test for anomalous data must be considered together
with the procedure for learning a density which is used by the test. Along
these lines, we propose training an ensemble of learned densities and jointly
testing for typicality with respect to each of these densities. We proved that
the intersection of typical sets of such an ensemble can lie in the interior
of the typical set of the ground-truth data distribution if the ensemble is
constructed correctly. We demonstrated on a simple and realistic example that
in practice, this procedure outperforms using typicality tests on a single
learned density.

Investigations left for future work include extending error rate bounds to the
case of the multi-typicality test proposed here, and further evaluating the
empirical performance of our proposed test on different domains.

## References

  * Balakrishnan et al. (2019) Sivaraman Balakrishnan, Larry Wasserman, et al.  Hypothesis testing for densities and high-dimensional multinomials: Sharp local minimax rates.  _The Annals of Statistics_ , 47(4):1893–1927, 2019.
  * Barron (1989) Andrew R Barron.  Uniformly powerful goodness of fit tests.  _The Annals of Statistics_ , pp. 107–124, 1989.
  * Chalapathy & Chawla (2019) Raghavendra Chalapathy and Sanjay Chawla.  Deep learning for anomaly detection: A survey.  _arXiv preprint arXiv:1901.03407_ , 2019.
  * Chen et al. (2017) Xi Chen, Nikhil Mishra, Mostafa Rohaninejad, and Pieter Abbeel.  Pixelsnail: An improved autoregressive generative model.  _arXiv preprint arXiv:1712.09763_ , 2017.
  * Chen (2017) Yen-Chi Chen.  A tutorial on kernel density estimation and recent advances.  _Biostatistics & Epidemiology_, 1(1):161–187, 2017.
  * Choi & Jang (2018) Hyunsun Choi and Eric Jang.  Generative ensembles for robust anomaly detection.  _arXiv preprint arXiv:1810.01392_ , 2018.
  * Cover & Thomas (2012) Thomas M Cover and Joy A Thomas.  _Elements of information theory_.  John Wiley & Sons, 2012.
  * Danihelka et al. (2017) Ivo Danihelka, Balaji Lakshminarayanan, Benigno Uria, Daan Wierstra, and Peter Dayan.  Comparison of maximum likelihood and gan-based training of real nvps.  _arXiv preprint arXiv:1705.05263_ , 2017.
  * De Cao et al. (2019) Nicola De Cao, Ivan Titov, and Wilker Aziz.  Block neural autoregressive flow.  _arXiv preprint arXiv:1904.04676_ , 2019.
  * Dinh et al. (2014) Laurent Dinh, David Krueger, and Yoshua Bengio.  Nice: Non-linear independent components estimation.  _arXiv preprint arXiv:1410.8516_ , 2014.
  * Dinh et al. (2016) Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio.  Density estimation using real nvp.  _arXiv preprint arXiv:1605.08803_ , 2016.
  * Grathwohl et al. (2018) Will Grathwohl, Ricky TQ Chen, Jesse Betterncourt, Ilya Sutskever, and David Duvenaud.  Ffjord: Free-form continuous dynamics for scalable reversible generative models.  _arXiv preprint arXiv:1810.01367_ , 2018.
  * Grover et al. (2018) Aditya Grover, Manik Dhar, and Stefano Ermon.  Flow-gan: Combining maximum likelihood and adversarial learning in generative models.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018\.
  * Hendrycks & Gimpel (2016) Dan Hendrycks and Kevin Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  _arXiv preprint arXiv:1610.02136_ , 2016.
  * Hendrycks et al. (2018) Dan Hendrycks, Mantas Mazeika, and Thomas G Dietterich.  Deep anomaly detection with outlier exposure.  _arXiv preprint arXiv:1812.04606_ , 2018.
  * Ho et al. (2019) Jonathan Ho, Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel.  Flow++: Improving flow-based generative models with variational dequantization and architecture design.  _arXiv preprint arXiv:1902.00275_ , 2019.
  * Kingma & Welling (2013) Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Kingma & Dhariwal (2018) Durk P Kingma and Prafulla Dhariwal.  Glow: Generative flow with invertible 1x1 convolutions.  In _Advances in Neural Information Processing Systems_ , pp. 10215–10224, 2018.
  * Li & Malik (2018) Ke Li and Jitendra Malik.  Implicit maximum likelihood estimation.  _arXiv preprint arXiv:1809.09087_ , 2018.
  * Liang et al. (2017) Shiyu Liang, Yixuan Li, and R Srikant.  Enhancing the reliability of out-of-distribution image detection in neural networks.  _arXiv preprint arXiv:1706.02690_ , 2017.
  * Makhzani et al. (2015) Alireza Makhzani, Jonathon Shlens, Navdeep Jaitly, Ian Goodfellow, and Brendan Frey.  Adversarial autoencoders.  _arXiv preprint arXiv:1511.05644_ , 2015.
  * McAllister et al. (2019) Rowan McAllister, Gregory Kahn, Jeff Clune, and Sergey Levine.  Robustness to out-of-distribution inputs via task-aware generative uncertainty.  In _International Conference on Robotics and Automation_. IEEE, 2019\.
  * Nalisnick et al. (2018) Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Gorur, and Balaji Lakshminarayanan.  Do deep generative models know what they don’t know?  _arXiv preprint arXiv:1810.09136_ , 2018.
  * Nalisnick et al. (2019) Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, and Balaji Lakshminarayanan.  Detecting out-of-distribution inputs to deep generative models using a test for typicality.  _arXiv preprint arXiv:1906.02994_ , 2019.
  * Oord et al. (2016) Aaron van den Oord, Nal Kalchbrenner, and Koray Kavukcuoglu.  Pixel recurrent neural networks.  _arXiv preprint arXiv:1601.06759_ , 2016.
  * Razavi et al. (2019) Ali Razavi, Aaron van den Oord, and Oriol Vinyals.  Generating diverse high-fidelity images with vq-vae-2.  _arXiv preprint arXiv:1906.00446_ , 2019.
  * Rezende et al. (2014) Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra.  Stochastic backpropagation and approximate inference in deep generative models.  _arXiv preprint arXiv:1401.4082_ , 2014.
  * Rippel & Adams (2013) Oren Rippel and Ryan Prescott Adams.  High-dimensional probability estimation with deep density models.  _arXiv preprint arXiv:1302.5125_ , 2013.
  * Salimans et al. (2017) Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P Kingma.  Pixelcnn++: Improving the pixelcnn with discretized logistic mixture likelihood and other modifications.  _arXiv preprint arXiv:1701.05517_ , 2017.
  * Schlegl et al. (2017) Thomas Schlegl, Philipp Seeböck, Sebastian M Waldstein, Ursula Schmidt-Erfurth, and Georg Langs.  Unsupervised anomaly detection with generative adversarial networks to guide marker discovery.  In _International Conference on Information Processing in Medical Imaging_ , pp. 146–157. Springer, 2017.
  * Song et al. (2017) Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman.  Pixeldefend: Leveraging generative models to understand and defend against adversarial examples.  _arXiv preprint arXiv:1710.10766_ , 2017.
  * Theis et al. (2015) Lucas Theis, Aäron van den Oord, and Matthias Bethge.  A note on the evaluation of generative models.  _arXiv preprint arXiv:1511.01844_ , 2015.
  * van den Oord et al. (2017) Aaron van den Oord, Oriol Vinyals, et al.  Neural discrete representation learning.  In _Advances in Neural Information Processing Systems_ , pp. 6306–6315, 2017.
  * Watanabe (2010) Sumio Watanabe.  Asymptotic equivalence of bayes cross validation and widely applicable information criterion in singular learning theory.  _Journal of Machine Learning Research_ , 11(Dec):3571–3594, 2010.

##  Appendix A Appendix

###  A.1 Proof of Theorems

To prove Theorem 1, we make use of the following lemma.

######  Lemma 1.

Consider a continuous random variable ${\textnormal{x}}\in\mathcal{X}$, and
two distributions $q_{a}({\textnormal{x}})$ and $q_{b}({\textnormal{x}}).$
Denote the differential entropy of $q_{a}({\textnormal{x}})$ and
$q_{b}({\textnormal{x}})$ as $h_{a}$ and $h_{b}$, respectively. Let
$D_{\mathrm{KL}}(q_{a}\|q_{b})=d$. Denote the typical sets of these
distributions as $T_{a}:=T_{\epsilon}^{(n)}(q_{a}({\textnormal{x}}))$ and
$T_{b}:=T_{\epsilon}^{(n)}(q_{b}({\textnormal{x}}))$. Finally, let
$T_{ab}:=T_{\epsilon}^{(n)}(D_{\mathrm{KL}}(q_{a}\|q_{b})$ represent the
relative entropy typical set (Cover & Thomas (2012), Section 11.8). Then, for
$n$ sufficiently large,

$q_{a}(T_{b})<e^{-n(d+h_{a}-h_{b}-3\epsilon)}+3\epsilon.$

###### Proof of Lemma 1.

We prove this lemma through contradiction. Assume

$q_{a}(T_{b})>e^{-n(d+h_{a}-h_{b}-3\epsilon)}+3\epsilon.$

Then by Theorem 8.2.2 in Cover & Thomas (2012) and the union bound, we have

$q_{a}(T_{a}\cap T_{b})>e^{-n(d+h_{a}-h_{b}-3\epsilon)}+2\epsilon,$

and, $q_{a}(T_{a}\cap T_{ab})>1-2\epsilon$. This implies that

$\displaystyle e^{-n(d+h_{a}-h_{b}-3\epsilon)}$ $\displaystyle<q_{a}(T_{a}\cap
T_{b}\cap T_{ab})$ $\displaystyle<e^{-n(h_{a}-\epsilon)}Vol(T_{a}\cap
T_{b}\cap T_{ab}),$

implying

$e^{-n(d-h_{b}-2\epsilon)}<Vol(T_{a}\cap T_{b}\cap T_{ab}).$

We also have that

$\displaystyle q_{b}(T_{ab})>q_{b}(T_{a}\cap T_{b}\cap T_{ab})$
$\displaystyle>Vol(T_{a}\cap T_{b}\cap T_{ab})\cdot\min_{{\textnormal{x}}\in
T_{a}\cap T_{b}\cap T_{ab}}q_{b}(x)$
$\displaystyle>e^{-n(d-h_{b}-2\epsilon)}e^{-n(h_{b}+\epsilon)}$
$\displaystyle=e^{-n(d-\epsilon)}$

However, we also have that $q_{b}(T_{ab})<e^{-n(d-\epsilon)}$ by Lemma 11.8.1
in Cover & Thomas (2012). This implies that

$e^{-n(d-\epsilon)}<e^{-n(d-\epsilon)},$

which forms a contradiction. Therefore, our original assumption must be false,
and therefore

$q_{a}(T_{b})<e^{-n(d+h_{a}-h_{b}-3\epsilon)}+3\epsilon.$

∎

###### Proof of Theorem 1.

The proof relies on the preceding lemma. Letting $T_{b}$ in Lemma 1 correspond
to our acceptance region for $\mathcal{H}_{0}$,
$T_{\epsilon}^{(n)}(p({\textnormal{x}}))$, then Lemma 1 states that for any
distribution $\tilde{p}$, the probability

$\tilde{p}(T_{\epsilon}^{(n)}(p({\textnormal{x}})))<e^{-n(D_{\mathrm{KL}}(\tilde{p}\|p)+h_{\tilde{p}}-h_{p}-3\epsilon)}+3\epsilon.$

Therefore, by optimizing over all distributions $\tilde{p}({\textnormal{x}})$
such that $D_{\mathrm{KL}}(p\|\tilde{p})<d$, the result follows immediately. ∎

To prove Theorem 2, we make use of the following lemmas.

######  Lemma 2.

For $n$ sufficiently large,

$q_{k}(T_{p})>(1-2\epsilon)e^{-n(d_{k}+\epsilon)}$

###### Proof of Lemma 2.

See Cover & Thomas (2012), Lemma 11.8.1. ∎

######  Lemma 3.

For $n$ sufficiently large,

$Vol\Big{(}T_{p}\cap
T_{q_{k}}\Big{)}\geq(1-2\epsilon)e^{n(h(p)-3\epsilon)}-\epsilon
e^{n(h(p)+d_{k}-2\epsilon)}.$

###### Proof of Lemma 3.

For $n$ sufficiently large, $q_{k}(T_{q_{k}})>1-\epsilon$, as shown in Cover &
Thomas (2012), Theorem 8.2.2. By the union bound and Lemma 2,

$\displaystyle q_{k}(T_{q_{k}}^{\mathsf{c}}\ \cup\ T_{p}^{\mathsf{c}})$
$\displaystyle<\epsilon+1-(1-2\epsilon)e^{-n(d_{k}+\epsilon)}$
$\displaystyle(1-2\epsilon)e^{-n(d+\epsilon)}-\epsilon$
$\displaystyle<q_{k}(T_{q_{k}}\ \cap\ T_{p})$
$\displaystyle\leq\int_{{\textnormal{x}}\in T_{q_{k}}\cap
T_{p}}p({\textnormal{x}}^{n})e^{-n(d_{k}-\epsilon)}d{\textnormal{x}}^{n}$
$\displaystyle\leq\int_{{\textnormal{x}}\in T_{q_{k}}\cap
T_{p}}e^{-n(h(p)-\epsilon)}e^{-n(d_{k}-\epsilon)}d{\textnormal{x}}^{n}$
$\displaystyle=e^{-n(h(p)+d_{k}-2\epsilon)}Vol\big{(}T_{q_{k}}\cap
T_{p}\big{)}$ $\displaystyle(1-2\epsilon)e^{n(h(p)-3\epsilon)}-\epsilon
e^{n(h(p)+d_{k}-2\epsilon)}$ $\displaystyle<Vol\big{(}T_{q_{k}}\cap
T_{p}\big{)}$

∎

######  Lemma 4.

For sets $S_{i}\subset\mathcal{X},i\in\\{0,...,K\\}$, if

$\frac{Vol(S_{i}\cap S_{0})}{Vol(S_{0})}>\frac{K-1}{K},\ \ \forall
i\in\\{1,...,K\\},$

Then $Vol(\bigcap_{i=0}^{K}S_{i})>0$.

###### Proof of Lemma 4.

Immediate consequence of union bound. ∎

###### Proof of Theorem 2.

For $n$ sufficiently large, $Vol\big{(}T(p)\big{)}<e^{n(h(p)+\epsilon)}$
(Cover & Thomas (2012), Theorem 8.2.2). If for all $k\in\\{1,...,K\\}$,

$\frac{Vol(T(q_{k})\cap T(p))}{Vol(T{p})}>\frac{K-1}{K},$

then by Lemma 4, the result holds. For $k\in\\{1,...,K\\}$,

$\displaystyle\frac{Vol(T(q_{k})\cap T(p))}{Vol(T(p))}$
$\displaystyle>\frac{(1-2\epsilon)e^{n(h(p)-3\epsilon)}-\epsilon
e^{n(h(p)+d_{k}-2\epsilon)}}{e^{n(h(p)+\epsilon)}}$
$\displaystyle=(1-2\epsilon)e^{-4n\epsilon}-\epsilon e^{n(d_{k}-3\epsilon)}.$

Therefore if

$\frac{K-1}{K}<(1-2\epsilon)e^{-4n\epsilon}-\epsilon e^{n(d_{k}-3\epsilon)},$

or equivalently

$d_{k}<\frac{1}{n}\log\Big{(}\frac{1-2\epsilon}{\epsilon}e^{-4n\epsilon}-\frac{K-1}{\epsilon
K}\Big{)}+3\epsilon,$

then the result follows immediately. Note that the following condition is only
valid if the argument of the logarithm is positive, and only possible if the
entire right-hand side is positive. An sufficient condition for the RHS to be
positive is,

$\frac{1}{4\epsilon}\log\big{(}\frac{1-2\epsilon}{\frac{K-1}{K}+\epsilon}\big{)}>n.$

These conditions are the two conditions in Theorem 2. ∎

###### Proof of Theorem 3.

Similar to Lemma 1, we prove this by contradiction. We make use of bounds that
hold for $n$ sufficiently large, which we assume from here on to avoid
repeatedly stating so. Let
$T_{ab}:=T_{\epsilon}^{(n)}(D_{\mathrm{KL}}(q_{a}\|q_{b}))$ represent the
relative entropy typical set (Cover & Thomas (2012), Section 11.8).

Assume that, in fact,

$\frac{Vol\big{(}T_{a}\cap T_{b}\big{)}}{Vol\big{(}T_{a}\big{)}}>r.$

Therefore, by Theorem 8.2.2 in Cover & Thomas (2012),

$\displaystyle Vol\big{(}T_{a}\cap T_{b}\big{)}$
$\displaystyle>rVol\big{(}T_{a}\big{)}$
$\displaystyle>r(1-\epsilon)e^{n(h_{a}-\epsilon)}.$

However, by the definition of $T_{a}$,

$\displaystyle Vol\big{(}T_{a}\cap T_{b}\big{)}$
$\displaystyle<\frac{q_{a}(T_{a}\cap T_{b})}{\min_{x^{n}\in T_{a}\cap
T_{b}}q_{a}(x^{n})}$ $\displaystyle<\frac{q_{a}(T_{a}\cap
T_{b})}{e^{-n(h_{a}+\epsilon)}}.$

This then implies that

$q_{a}(T_{a}\cap T_{b})>r(1-\epsilon)e^{-2n\epsilon}.$

Now, using the union bound and Theorem 11.8.2 in Cover & Thomas (2012), we
have that

$q_{a}(T_{a}\cap T_{ab})>1-2\epsilon.$

Therefore, again by the union bound,

$\displaystyle r(1-\epsilon)e^{-2n\epsilon}-2\epsilon$
$\displaystyle<q_{a}(T_{a}\cap T_{b}\cap T_{ab})$
$\displaystyle=\int_{x^{n}\in T_{a}\cap T_{b}\cap T_{ab}}q_{a}(x^{n})dx^{n}$
$\displaystyle<e^{-n(h_{a}-\epsilon)}Vol(T_{a}\cap T_{b}\cap T_{ab})$
$\displaystyle\implies V(T_{a}\cap T_{b}\cap T_{ab})$
$\displaystyle>(r(1-\epsilon)e^{-2n\epsilon}-2\epsilon)e^{n(h_{a}-\epsilon)}.$

Finally, we have that

$\displaystyle q_{b}(T_{ab})\geq q_{b}(T_{a}\cap T_{b}\cap T_{ab})$
$\displaystyle\geq Vol(T_{a}\cap T_{b}\cap T_{ab})\cdot\min_{x^{n}\in
T_{a}\cap T_{b}\cap T_{ab}}q_{b}(x^{n})$ $\displaystyle=Vol(T_{a}\cap
T_{b}\cap T_{ab})e^{-n(h_{b}+\epsilon)}$
$\displaystyle>(r(1-\epsilon)e^{-2n\epsilon}-2\epsilon)e^{-n(h_{b}-h_{a}+2\epsilon)}.$

From Theorem 11.8.2 referenced above, we also have that
$q_{b}(T_{ab})<e^{-n(D_{\mathrm{KL}}(q_{a}\|q_{b})-\epsilon)}$, which implies
the following.

$\displaystyle(r(1-\epsilon)e^{-2n\epsilon}-2\epsilon)e^{-n(h_{b}-h_{a}+2\epsilon)}$
$\displaystyle<e^{-n(D_{\mathrm{KL}}(q_{a}\|q_{b})+\epsilon)}$
$\displaystyle\log\big{(}r(1-\epsilon)e^{-2n\epsilon}-2\epsilon\big{)}-n(h_{b}-h_{a}+2\epsilon)$
$\displaystyle<-n\big{(}D_{\mathrm{KL}}(q_{a}\|q_{b})-\epsilon\big{)}.$

Rearranging, this gives rise to the condition:

$D_{\mathrm{KL}}(q_{a}\|q_{b})>h_{b}-h_{a}-3\epsilon+\frac{1}{n}\log\Big{(}\frac{1}{r(1-\epsilon)e^{-2n\epsilon}-2\epsilon}\Big{)}.$

If this condition does not hold, then there is a contradiction, and our
original assumption that

$\frac{Vol\big{(}T_{a}\cap T_{b}\big{)}}{Vol\big{(}T_{a}\big{)}}<r$

must be false. ∎

###  A.2 Expressing the Multi-Typical Set as the Typical Set of some
Distribution

Recall the definition of the multi-typical set for a given ensemble of
probability distributions:

$T_{\epsilon}^{(n)}(\\{q_{1}({\textnormal{x}}),...,q_{K}({\textnormal{x}})\\}):=\Big{\\{}{\textnormal{x}}^{n}\in\mathcal{X}^{n}:\max_{k\in\\{1,...,K\\}}|-\log
q_{k}({\textnormal{x}}^{n})-h_{k}|<\epsilon\Big{\\}}.$ (8)

An interesting question to ask is if there exist a probability distribution
which has typical set corresponding to the multi-typical set defined here.
Here we show that we can approximately recover an un-normalized version of
such a distribution.

Define $\tilde{q}_{k}({\textnormal{x}}):=e^{h_{k}}q_{k}({\textnormal{x}})$.
Then we have

$T_{\epsilon}^{(n)}(\\{q_{1}({\textnormal{x}}),...,q_{K}({\textnormal{x}})\\})=\Big{\\{}{\textnormal{x}}^{n}\in\mathcal{X}^{n}:\max_{k\in\\{1,...,K\\}}|\log\tilde{q}_{k}({\textnormal{x}}^{n})|<\epsilon\Big{\\}}.$
(9)

.

Defining $\tilde{m}(x):=\tilde{q}_{k}(x),\
k=arg\min_{i}|\log\tilde{q}_{i}(x)|$, we have

$T_{\epsilon}^{(n)}(\\{q_{1}({\textnormal{x}}),...,q_{K}({\textnormal{x}})\\})=\Big{\\{}{\textnormal{x}}^{n}\in\mathcal{X}^{n}:|\log\tilde{m}({\textnormal{x}}^{n})|<\epsilon\Big{\\}}.$
(10)

.

Now, define
$Z=\int_{{\textnormal{x}}\in\mathcal{X}}\tilde{m}({\textnormal{x}})d{\textnormal{x}}$,
and $m({\textnormal{x}})=\tilde{m}({\textnormal{x}})/Z$ such that
$m({\textnormal{x}})$ is a valid probability distribution. Then if
$\mathbb{E}_{m}[-\log m(x)]=\log(Z)$, then the distribution $m(x)$ has typical
set identical to the set
$T_{\epsilon}^{(n)}(\\{q_{1}({\textnormal{x}}),...,q_{K}({\textnormal{x}})\\})$.
The property that $\mathbb{E}_{m}[-\log m({\textnormal{x}})]=\log(Z)$ will not
hold exactly in practice, but often times it is approximately true. The reason
this is true is because over the space $\mathcal{X}$, each of the functions
$\log\tilde{q}_{k}({\textnormal{x}})$ have zero mean. Pointwise, the function
$\tilde{m}(x)$ takes as its value the $\tilde{q}_{k}$ whose log value is
farthest from the origin. If the $\tilde{q}_{k}$ are chosen such that on
average, equal mass is kept on either side of the origin (in log-space), then
the property will hold.

The result of such a procedure is a approximation of the density which has
typical set identical to the multi-typical set. Since in practice computing
the normalization constant $Z$ is intractable, we can learn another
divergence, using $\tilde{m}({\textnormal{x}})$ as a target instead of
$p({\textnormal{x}})$. The reason we might wish to do this, is by having an
explicit form of $\tilde{m}({\textnormal{x}})$, we can learn a density by
optimizing other divergences than the forward KL-divergence, such as the
reverse KL-divergence. Note that if we optimize

$\displaystyle D_{\mathrm{KL}}(q(x)\|\tilde{m}(x))$
$\displaystyle=D_{\mathrm{KL}}(q(x)\|Zm(x))$ (11)
$\displaystyle=D_{\mathrm{KL}}(q(x)\|m(x))-\log Z.$ (12)

Therefore, knowledge of the normalization constant is not needed in this
context, since the constant term doesn’t affect the optimization procedure.
Similar results can be shown for other divergences.

###  A.3 Visualizations of Samples from the Mixture of Gaussians Experiment

Figure 5: Samples from learned densities which are parameterized as Mixture of
Gaussians. Random projections (columns) of samples from different learned
densities (rows), are overlaid on samples from the target Mixture of Gaussians
distribution. The bottom row displays the ground-truth samples unobstructed
for reference.