Testing For Typicality with Respect to an Ensemble of Learned Distributions
Authors: Forrest Laine
Claire Tomlin
Venue:  (2020)
Keywords: anomaly detection
density estimation
generative models

Abstract: Good 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, but those results require
knowing a model of the base distribution. The ability to correctly reject anomalous
data 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 goodness-of-fit problem do not ac-
count 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.

Under review as a conference paper at ICLR 2020
TESTING TYPICALITY WITH RESPECT TO AN ENSEMBLE OF LEARNED DISTRIBUTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Good methods of performing anomaly detection on righ--imensionll data sets are needed, since algorithms which are trained data are only expected to perform well on data that is similar to the training data. There are theoretical results on the ability detect if a population of data likely to come from a known base dis- tribution, which is known as the goodness-of-ff problem, but those results require knowing model of the base distribution. The ability to correctly reject anomalous data hinges on the accuracy of the model of the base distribution. For high dimen- sional data, learning an accurate- eccurate-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 goodness-of-fe problem do not ac- count for the fact that model of the base distribution is learned. To address that gap, we offer a theoretically motivated approach to account for the density learn- ing procedure. In particular, considering data to be anomalous if the data is anomalous with respect to any member of the ensemble. We provide 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 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.
propose training ensemble of density models,
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 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 out-of-distributio data, we unable to detect when the models are presented with out-of- -iitt-idiitiitttionn data. This poses a conundrum, since we wish deploy our high-performing models, yet often we can't since they can potentially have unpredictable behavior at unpredictable instances.
variety of
Since training a model that robust all possible distributional shifts the model might encounter is potentially impossible, more modest approach might be to come up with ways for detecting -ftt--iiiitiiitiionn data. These detections could then act an indication that the model might be incorrect. This ability predict incorrectness can go a long way in making systems more reliable.
The problem of detecting duitt--distribution data has long history, and is formally known as the goodness-of-ff of-fit problem. Statisticians have proved bounds on the probability of detecting popula- tions 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, plicit form of the probability density function (or probability mass function) deseribing the base distribution is needed. For most real-world data sets, this density is not known, and must be esti-

---

Under review as a conference paper at ICLR 2020
mated. While there has been lot of analysis 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 dimen- sions using learned densities is hard, even when using modern, powerful density estimators. For example, the researchers in Nalisnick al. (2018) and Choi & Jang (0088) both claim that state-of- the-art learned densities are not suitable for anomaly detection since they assign higher probability some out-o--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- nigh-dimensional distributions. Therefore they propose performing an anomaly de- tection 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 of-fit 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 di- vergence must have non-zero intersection.
We these theorems to motivate our proposed method for conservative goodness-of of testing. Specifically, we propose training an ensemble of models, and show that by taking the intersection of their typical sets, ground truth distribution. We show that such an ensemble can exist and give sufficient conditions for its existence.
approximately recover the typical set of the
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 den- sities 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 x X with probability density function p(x). Let x" == (X1, X2...., xn) denote the collection of random variables x. Let hn denote the differential entropy of p(x). For e > and positive integer n, The typical set with respect to p(x) is defined as the following:
T.(m) = {x" Ex""xx"
1 1 1 logg(x") n
X"
hpl cc.
In words, this is the set of sequences of samples whose average negative-log probabiiot is close to the differential entropy. This set has high probability under p(x), implying that most sequences of data points sampled from p(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 X" E X were sampled i...d. according to p(x). In hypothesis testing terminology, we interested in determining which two hypotheses are more probable:
The mull-hypothesis,
Ho = 8" ~ p(x)
The allernative-hypottesii,,
Hi nd p(x),
2

---

Under review as a conference paper at ICLR 2020
where here p(x) is any distribution such that (KL(P))) 2 d. If define A. X to be the acceptance region for the null- aull-hypothesis, or the set of all sequences x" such that Hy is deemed more probable, then we can define the probabilities of eπror as the following:
On (A)),
Bn
max p" (An).
(:D(pll))d
Typically we desire tests that minimize 3, for a fixed an tests that minimize some linear combi- nation of the two.
The authors in Nalisnick et al. (2019) propose test procedure which accepts the null-hypothesis iff x" E T! In other words, collection of points are determined to be anomalous with respect to p(x) iff x" & r=")) In that work, they show that this test performs about well other tests such as the Student's 's t-test, the Kolmogorov-Smingg Kernelized Stein Discrepancy test. We note that in those comparisons, all tests performed with respect to a learned density as proxy for the ground-truth density.
test, the Maximum Mcan Discrepancy test, and the
In this work, we consider the same apicclity-bbssee 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(x). In order to validate this approach, we first prove that for a fixed ax the typical set test achieves an error rate 3n that worst, given by:
Theorem 1. Let the region of acceptance for the rypicality test be defined by the set T!(") T!") (p(x)). For n sufficiently large, then an < c, and
Bn
(P
+
p:D(pll)
Proof of Theorem
1 See Section
A.1
This theorem states that for fixed rate of correctly accepting Ho. 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 anoma- lous not, model of the probability density function p(x) is needed. For many practical ap- plications, we are only ever presented with a data set of N samples from p(x), which we denote X= (2, However, estimate of the ground-truth density can be learned. We denote parameterized distribution by (xx; 0), which can be learned by minimizing the following objective:
min DKL (p(x)ll((xx 0)).
(3)
The KI. divergence is defined by DKL (p(x) 0)) log p(x) eliminating constants, is clear that an equivalent optimization problem
q(x0) I- By expanding terms and
N
max Epllog q(x: 0[) so max
Σ 1=1
log g(x;; 0).
(4)
The optimal 0 in this problem is that which maximizes the log likelihood on the data set X. This is why this optimization is commonly referred to as waaxiimum-lkkeliboe estimation. Importantly, the dependence on the unknown true distribution p(x) was removed through the use of the law of large numbers. Since the KL--dvergence is equal to zero if and only if p(x) q(x: 0) Va: E X, this objective is well-motivated we wish that ((x; 0) As p(x). However, there are many other statisti- cal divergences between distributions that would also be suitable 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 distribu- tions xx: 0) 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 0² such that q(x; 0*) p(x).
3

---

Under review as a conference paper at ICLR 2020
For example, by looking the form of the KL-divergence, there is no direct penalty for q(:: 0) in assigning a high density to points far away from any of the x,'s. This can lead to locally optimal learned densities which have high probability density in regions of X' that p(r) does not. This can potentially lead to situations in which a collection of points can be anomalous with respect to p(x), but in-distribution with respect to the sub-optimally learned g(x; 0).
There exist other divergences which do not suffer this effect, but it is not obvious how to optimize with respect them. For example, the reverse KL-divergence, which switches the places of p(x) and (x; 0) in the standard KL-divergence, has an alternate effect; g(x; 0) is directly penalized for assigning high density anywhere that does not also have high density under p(x). Unfortunately, this requires direct knowledge of p(x) to evaluate the objective, as do all divergences other than the forward KI., to the best of our knowledge. This makes the forward Kl--diveeeence special in that 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 PARAMETERIZATION
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 dwwr--dimesiionl, latent random variable through probabilistie 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 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 bijective, continuously differentiable mapping, which we refer to change-of- varriable models. These models include autoregressive models, such as PixeICNN (Oord et al.) 2016 Sali- mans al. 2017), and invertible flow models, such NICE (Dinh et al. 2014), NVP (Dih et al.] 2016), and GL.OW (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 probability density function through change of variables. Specifically, if m 0) X + Z is continuously differentiable bijection, and r(z; 0) is probability den- sity function corresponding to random variable z E Z, then together m and r implicitly define a probability density function over random variable x E Xx:
<x: 0) r(2; 0) (
(5)
dx
So long the determinant in (5) is easy to evaluate, the probability density (xx; 9) can be evaluated and the parameters 9 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.
CASE STUDY ON SYNTHETIC DATA
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(x) is known. In particular, we consider the problem of learning the density of a high-dimensional mixture of Gaussians.
4

---

Under review as a conference paper at ICLR 2020
Figure 1: Random projections of samples from 100-dimensional Mixture of Gaussians Distribu- tion.
Let M denote the number of mixture components in the base distribution. Then we define the base distribution as the following:
p(x) E Pm (x: (mms Em),
where Pm (x: Mms Em) is the probability density function associated with Gaussian distribution with mean pm and covariance Σm. For this investigation, we define the space X' := R 100 so that effects dependent on the dimensionality of X are evident. Here consider the parameters Jm and Σm to be chosen such that the j4m are sampled from uniform distribution over a hyper-ball with radius r 3.0, and the matrices Em 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 Tm 1/M. In all experiments we choose the number of components to be M 20.
Some random projections of samples from one such p(x) can be seen in Figure Note that although each projection the probability mass of the different mixture components seem be overlapping, due to the dimensionality of the space, each mode is separated by relatively large distance. In the example shown Figure I the minimum distance between the means of each mixture component is 3.62. Furthermore, the max probability of any mode with respect any of the other mixture components is roughly le-20. This means that each the M modes in the mixture distribution are clearly distinct and separated by regions of near-zero probability.
Train arror
Test error
.log q(x)
20
0
Training Iterations
Figure 2:
Learning curve for the Mixture of Gaussian Experiment. Average (across experiments) are plotted along with their #1 standard deviation region.
train and test neg-log- neg-looo--iie liklliiillsoods
We attempt to learn p(x) by optimizing (4 for a ((x; 0) parameterized exactly as p(x). In other words, the parameters 0 are the set {m1 M1, E,, T2, μ2: Eg...., TM. MM, E,), where the 7m are constrained to sum to 1, and the Σ,, are constrained to be positive definite and diagonal.
We perform five experiments, each time randomly initializing the parameters O exactly as was done for p(x). We use the indices & {1, K 5) to index the 5 experiments ran, and refer the the k-th learned density as qu (x; 0z). The training curve for learning these densities can be seen in Figure which shows the average test and train errors across experiments, and random projections of the resulting samples overlaid on samples the base distribution can be seen in Figure 5 Exam- ining these figures, 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
that the learning procedure converged, yet the samples generated from
5

---

Under review as a conference paper at ICLR 2020
Relobive Probabilttcs tis
Components
Figure 3: Bar plots showing the relative weighting of the mixture components in the learned densities in the Mixture of Gaussians experiment. Here can be seen that each of the 5 learned densities use only approximately 12 out of the 20 modes to explain the data.
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 pxx) has distinctly separated modes, the fact that the base dis- tributions represent the data using fewer modes directly implies that the models necessarily assign high density to regions in 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).
COUFTE
Figure 4: Histograms of the negative log-likelihood of the ground truth distribution, evaluated on samples from the ground- -ruth distribution (top-left). and samples from each of the learned distribu- tions in the Mixture of Gaussians experiment. As it can be seen, only about a third of samples from each learned distribution have negative tog-likelihoon close to the ground-trui tnrththhhhhhhh sample average.
To validate this claim, we generate histograms of the ground truth negative log- likellkiiioods on sam- ples from the base distribution and each of the learned distributions, which can be seen in Figure We also list in Table [ the percentages of samples from each learned density that lie 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 40% of the samples from each learned distribution lie in the typical set the true distribution. In the context of anomaly detection, this means that if used test for typicality using one of these learned densities, about 60% of the region acceptance would include points that are not actually typical with respect to the base distribution.
only about

---

Under review as a conference paper at ICLR 2020
Table I: Percentages of samples lying in the Typical Set of each of the learned and ground-truth distributions. Here, we take to be such that approximately 95% of samples from a distribution lie in its own typical set, and we n of the ground-truth samples from p(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.
Note that each of the learned densities include most
Sampling Distribution
p(x)
(x; 0
42(x:
02)
(x(x; 0s)
(x 0₂)
Øa (x: 0g)
Th (p())
95.3
37.8
34.4
42.9
35.0
40.7
_0 (x;(x;))
93.3
93.4
35.1
41.2
34.3
38.9
Tea) (2)
93.2
69.6
95.0
80.6
68.9
73.0
T( (9a(x;
96.2
47.0
33.9
97.0
40.5
47.4
T
94.5
47.4
44.5
44.8
94.5
50.4
T: (x;(x;0;)
95.7
46.6
39.9
48.9
38.2
50.4
The mismatch in typical sets corroborates what 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 which they do results inadvertently explaining other regions of the data space as well.
The example presented here is admittedly simple one, yet demonstrates that coming up with more clever parameterizations will not necessarily result in better learning process. In this example, the learned densities are expressive enough to learn the true distribution, however get stuck 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, 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 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 distribu- tions. As can be seen in Table find that due 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 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 Section 2.1 what we call the multi-typical set, with respect to ensemble of distributions eu (x), k E {I,..., K
First we define
For a given > 0 and positive integer n, this set is defined as the following:
The)) (x (K (x))) = E Am
max - log q (x*) - hel < x kE(I...,.K)
(7)
Here, hg refers to the differential entropy of the k-th density in the ensemble, (x). The method propose is the following:
1. Train an ensemble parameterized densities, {91 (x; 0,, 9x (x; 0x)}, using random ini- tializations and using the maximum likelihood objective (4).
2. When discerning between Ho and Hi (Section 2.1 we choose Ho iff x"
T!()) ( -x 0x)))-
Before justifying this test theoretically, we first demonstrate its utility on the Mixture of Gaussians By using rejection sampling, we generate samples that lie in the multi-
example in Section 3

---

Under review as a conference paper at ICLR 2020
typical set with respect to the learned densities. Specifically, 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 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 these samples lie in the ground-truth typical set as samples from the ground-truth distribution itself demonstrates that this set works as good indicator of typicality with respect to the ground
distribution.
Therefore, by leveraging the use of an ensemble of learned densities, we have shown that the short- coming of any individual learned density model can be overcome, 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 guar- anteed 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 For continuous random variable x E X. Consider some distribution p(x) with differential entropy hpp and any collection of distributions (u(x), k E {l..... K}. all hav- ing DKL
DKL(p (pllgx) = dg < cc. Let Tp == Tp")()) (p) denote the typical set of p. and similarly
Ty. T (qx) the rypical set of qu for each & (1,...K))
For sufficiently large, the following hold,
I log
K-t
1-2c
>
d3 < 1 log
1-2e c
Ane
K -1 ck'
+ 3e
then
Vol minu Tan O.
Theorem 3. For continuous random variable x E X, consider two distributions, qa (x) and (x)... Denote ha and hys the differential entropy of these distributions, respectively. Similarly, let Tę T!!) (qu) and T T!(i) (gb)) represent the typical sets of qa and qu- for some O < r S and
sufficiently large,
1
1
DKI(qa hi -ha 3e + n
log (r(1 c)e- 20ee 2
then,
Vol nT) (ol(T.)
<T.
Proof of both Theorems is given in Section A.1 The result of Theorem is that we can be sure that if every model in 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 ( (p(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 Theorem is approximately the same for every pair of models the ensemble. If the conditions listed in both theorems hold, then the multi-typical set must lie almost entirely in (p(x)). The result of this is that the multi-typical set, if constructed according to the conditions
8

---

Under review as a conference paper at ICLR 2020
given, can be used as a conservative estimate of the typical set Th (p(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 (p(x))
The point of proving these theorems is to demonstrate that, in theory, an ensemble of learned models approximate the typical set of the ground truth distribution. The bounds given sufficient conditions, but in practice we find that 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 guide for choosing the values of and in practice.
RELATED WORK
There are many works interested in goodness-of-fit testing for modern high-dimensional data distri- butions. The works most similar to ours are Nalisnick al. (2019) and Choi & Jang (0018). 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
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 single learned distribution. Specifically, they leverage the Akaiee Information Criterion (Watanabe) (010)) to produce a score which averages the log probabilities across models 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 way, that method can be thought of as generating density that is the point- wise least probable density in the ensemble, where as the method we propose can be thought 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 baseline test that resembles 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. (017)) propose using the outputs of trained neural networks themselves to dis- cern when the networks are presented with out-of distriibibtt 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 Schleel 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 VAE to make data points more likely under a learned distri- bution before feeding them to a trained model. An issue with all of these methods mentioned is that they rely checking whether fow-dimensional, learned representations of the data or not. This has the downside that by construction, anomalous aspects of the data can be missed the low-dimensional representation is invariant to those aspects. Nevertheless, some of these meth- ods 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).
anomalous
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 nigh-dimensional large data sets. An overview of KDE methods can found in Chen (2017). Some more modern approaches to model- ing 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) 7). and Razavi et al. (2019), to list few. There are also other objectives that are considered when learning densities, such as training density in adversarial manner in Grover et al. (2018) and Danihelka jet al.] (2017). Alternatively, Li & Malik (2018) define implicit maximum likelihood estimation, which be thought of as approximately minimizing the reverse Kl--divergence.

---

Under review as a conference paper at ICLR 2020
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 test for anomalous data must be considered together with the procedure for learning density which is used by the test. Along these lines, we propose training 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 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.
ensemble of learned densities and jointly testing for typicality
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
Sivaraman Balakrishnan, Larry Wasserman, et al. Hypothesis testing for densities and high- dimensional multinomials: Sharp local minimax rates. The Annals of Statistics, 4794):1893-1927, 2019.
Andrew R Barron. Uniformly powerful goodness of fit tests. The Annals of Statistics, pp. 107-124, 1989.
Raghavendra Chalapathy and Sanjay Chawla. Deep learning for anomaly detection: A survey. arXiv preprint STGIvv19001034000 2019.
Xi Chen, Nikhil Mishra, Mostafa Rohaninejad, and Pieter Abbeel. Pixelsnail: An improved autore- gressive generative model. arXiv preprint 17Xiv:1712.09963, 2017.
Yen-Chi Chen. A tutorial on kernel density estimation and recent advances. Biostatistics Epi-
demiology, 1(1):161-187, 2017.
Hyunsun Choi and Eric Jang. Generative ensembles for robust anomaly detection. arXiv preprint arXiv:1810.01392, 2018.
Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 2012.
Ivo Danihelka, Balaji I Lakshminarayanan, Benigno Uria, Daan Wierstra, and Peter Dayan. Compari- son of maximum likelihood and gan-based training of real nvps. arXiv preprint arXiv: 055666, 2017.
Nicola De Cao, Ivan Titov, and Wilker Aziz. Block neural autoregressive flow. arXiv preprint NXXi:1904.04677 2019.
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components esti- mation. arXiv preprint arXiv:1410.8516 2014.
Laurent Dinh, Jascha Sohk-Dick,,,,,, and Samy Bengio. Density estimation using real nvp. arXiv preprint 1605 (ttp:/000000008333. 2016.
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.
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 Intel- ligence, 2018.
Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. arXiv preprint
2016.
Dan Hendrycks, Mantas Mazeika, and Thomas G Dietterich. Deep anomaly detection with outlier exposure, arXiv preprint arXiv: 18/2. 246666 2018.
10

---

Under review as a conference paper at ICLR 2020
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.00027, 2019.
Diederik Kingma and Max Welling. arXiv:1312.61 14, 2013.
Auto-encoding variational bayes.
arXiv preprint
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1xl convolutions, In Advances in Neural Information Processing Systems, pp. 10215-10224, 2018.
Ke Li and Jitendra Malik. Implicit maximum likelihood estimation.
arXiv preprint
arXiv: 1PXi:/880.000087 2018.
Shiyu Liang, Yixuan Li, and R Srikant. Enhancing the reliability of out-of-distribution image detec- tion in neural networks. arXiv preprint arXiv: 70000000022222 02690, 2017.
Alireza Makhzani, Jonathon Shlens, Navdeep Jaitly, Ian Goodfellow, and Brendan Frey. Adversarial autoencoders. arXiv preprint ar 2015.
Rowan McAllister, Gregory Kahn, Jeff Clune, and Sergey Levine. Robustness ouiti--disttibution inputs via task-aware generative uncertainty. In International Conference on Robotics and Au- tomation. IEEE, 2019.
Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Gorur, and Balaji Lakshminarayanan Do deep generative models know what they don't 't know? arXiv preprint arXiv:1810.09136, 2018.
Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, and Balaji Lakshminarayanan. Detecting out-of-distributioo inputs to deep generative models using a test for typicality. arXiv preprint 1rXivv/906.000 02994, 2019.
Aaron van den Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural networks. arXiv preprint ar arXiv: 1X010066 2016.
Ali Razavi, Aaron van den Oord, and Oriol Vinyals. Generating diverse high-fidelity images with 2019.
vq-vae-2. arXiv preprint
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. arXiv preprint arXiv:1401.4003 2014.
Oren Rippel and Ryan Prescott Adams. High-dimensions probability estimation with deep density models. arXiv preprint 102h::130..5125, 2013.
Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P Kingma. Pixelcnn++: Improving the pixelenn with discretized logistic mixture likelihood and other modifications. arXiv preprint arXiv: 1701.0077.. 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.
Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. arXiv preprint 1710. 10766, 2017.
Lucas Theis, Aäron van den Oord, and Matthias Bethge. note on the evaluation of generative 2015.
models. arXiv preprint
Aaron van den Oord, Oriol Vinyals, et al. Neural discrete representation learning. In Advances in Neural Information Processing Systems, pp. 6306-6315, 2017.
Sumio Watanabe. Asymptotic equivalence of bayes cross validation and widely applicable infor- mation criterion in singular learning theory. Journal of Machine Learning Research, 11(Dec): 3571-3594, 2010.
11

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 PROOF OF THEOREMS
To prove Theorem T we make use of the following lemma.
Lemma 1. Consider continuous random variable E X, and two distributions qa (x) and qo (x).
Denote the differential entropy of (x) and (x(x) as hag and has respectively. Let DKL (gall)))))))) = d.
Denote the typical sets of these distributions as To == T (x)) and T. := T (q) (x)). Finally,
let Tab :- Toa) (DKL (gall))))) represent the relative entropy typical set (Cover & Thomas 2012
Section 11.8). Then, for n sufficiently large,
qa (Tb) < -n(thh - + 3c.
Proof of Lemma 7
We prove this lemma through contradiction. Assume
la (T)) a(dth. Na-3)))))))))) + 3c.
Then by Theorem 8.2.2 in Cover & Thomas 2012 and the union bound, we have
Qa (Ta (T) n(d hh-3e) 2c,
and, 4a (To (aat) > 1 2e. This implics that
e m(d+hh -3)
9a (T (ToNaaa)
<6 Vol Taas,
implying
-ndd-hs-20 < <Vol TTnnaa
We also have that
(Tar)) gb (Ta nT, Tax) > Vol(Ta n Tb Tat)
min
(x(x)
> -dd-hs 26) m(hste)
=e -n(dee)
However, we also have that qo (Tas) < n((dde) by Lemma 11.8.1 in Cover & Thomas (002). This implies that
-n(d-e) n(dde)
which forms a contradiction. Therefore, our original assumption must be false, and therefore
qa < e n(d+hha -,, -n-3c) + 3c.
Proof of Theorem 7
The proof relies on the preceding lemma. Letting Th Lemma correspond to our acceptance region for Ho. (p()), then Lemma states that for any distribution ý. the probability
((T (p(x))) < e - (ilp) -6) 36) + 3e.
Therefore, by optimizing over all distributions p(x) such that DRI(pplE) < d, the result follows immediately.
To prove Theorem 2 we make use of the following lemmas.
Lemma 2. For n sufficiently large,
nu (Tp)) (1 2c)e 4c)
Proof of Lemma
See Cover & Thomas 2012), Lemma 11.8.1.
n
12

---

Under review as a conference paper at ICLR 2020
Lemma 3. For sufficiently large,
Vol Vol(T TTa) (1 36) te2 26)
Proof of Lemina 3 For sufficiently large, q (T oz
) > - e, shown in Cover & Thomas 2012
Theorem 8.2.2. By the union bound and Lemma
qk (T 4
U T <c+1-cll1- (1 -2c)e -n) ((d++e)
(1 2t)e 2c)e- n(d+e] < <q 0 TTp)
p(x*) )e -ndd=------ -c) dxn
NTp
e (n((((p)-o) nn(ds -n(ds -c) -x
XET MI ((((k())dd Vol 0Tp)
(1 - 2e)e ((( < Vol (Tp)
Lemma 4. For sets S, c Cii (o........ if
Vol(S, n So) Vol(So)
K 1
Vi {l,..., K}.
K
K Then Vo S.) > 0.
Proof of Lemma Immediate consequence of union bound.
Proof of Theorem 2 For sufficiently large, Vol(T())) < (((((p)+e)) Cover & Thomas 2012 Theorem 8.2.2). If for all & E [L....,K.
Vol(T(gn)
K K-1
Vol(Tp)
then by Lemma the result holds. For k E {I,..,,K}
Vol(T(qu) (1 26 (M))) -c)) (((((())td
Vol(T(p)
en(h(p)+e)
= =11- - 20)e 4nc - ec n(dx-33
Therefore if
K
<1
-2eee-
Ane c
n(dx -36)
K
or equivalently
2c
K
dx
log
Ane
+ 3e,
n
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.
1 1
2c
log
> n.
K-1 K
+
These conditions are the two conditions in Theorem
2
13

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 3 Similar Lemma prove this by contradiction. We make of bounds that hold for n sufficienlly large, which we assume from here on to avoid repeatedly stating so.
Let Tab := Te (DkI(gall9))) represent the relative entropy typical set (Cover & Thomas 2012).
Section 11.8). Assume that, in fact,
(T nTb))
>
(Ta
Therefore, by Theorem 8.2.2 in Cover & Thomas 2012),
> rVa)(TT)
> r(1 e)en(haa-)
However, by the definition of Ta.
9a (Ta 0 Tb)
Vol(TanT)
min Mhinn ETanT qa (x²))
9a (T nT))
tch
This then implies that
4a (To nT) r(1 c)e 2nc
Now, using the union bound and Theorem 11.8.2 Cover Thomas (2012). we have that
La (a (Tab) > 2E.
Therefore, again by the union bound,
r(1 c)e 2ne 2e < <a n TTTTB Tas)
La (a(x") )dr
ITTTTATTNTT <e Wool n To Tab))
((TnTTnTa) > (r(1 e)e- 2ne 2e 2e) (ma
Finally, we have that
(Tabt) 2 (Ta (Tab) 2 Vol(T, Tab)
x" M (6(x")
min
= =Vo((Ta nI n Table
m(hute)
(r(1 - c)e -)e--2ne 2ne
2c)e 2nho-niho
From Theorem 11.8.2 referenced above, we also have that (T(sas) < e=n(Dka(oallo))-g which implies the following.
(r(1 - t)e 2ne -2eee-n(ee n(1i +2c) < < (Dullletlee)))
log (r(1 22ee 2ne -2c) - -n(h, - ha + 26) < -n DKI (gallag))))))) - c).
Rearranging, this gives rise to the condition:
DKL (aa (996)))))) > hs - has 3e + log r(1 E)e 2
If this condition does not hold, then there is a contradiction, and our original assumption that
Vol nT))
<r
(T.
must be false.
14

---

Under review as a conference paper at ICLR 2020
A.2 EXPRESSING THE TYPICAL SET AS THE TYPICAL SET SOME DISTRIBUTION
Recall the definition of the multi-typical set for given ensemble of probability distributions:
Thes (17 (x), [x(())) = {x" E Am
- log (x((x))) - hgl < <).
MAX (E......KK)
(8)
interesting question to ask is if there exist probability distribution which has typical set corre- sponding to the multi-typical set defined here. Here we show that we can approximately recover an un-normalized version of such a distribution.
Define (x): c²"qu(xx. Then we have
(x. 9K = =xx² E xm:
log [x"g kE(1....K)
(9)
Defining m(x) = dx (x), arg min; log (x)). we have
T(") ((q) (x), (x())) {x" E x" [log <
(10)
Now, define 7 == Sxxx m()) and m(x) = mm(x) such that m(x) a valid probability distribu- tion. Then if 1mm.m-lloo log m(x) log(Z) then the distribution m(x) has typical set identical to the TT'" (1g) (x).... 9k (x))). The property that E log mn()] log(2) will not hold exactly in practice, but often times it is approximately true. The reason this is true is because over the space X, each of the functions log qR (x) have zero mean. Pointwise, the function m m(x) takes as its value the dh whose log value is farthest from the origin. If the ÿK are chosen such that on average, equal mass kept on either side of the origin (in log-space), then the property will hold.
The result of such procedure is approximation of the density which has typical set identical to the multi-typical set. Since practice computing the normalization constant intractable, we can learn another divergence, using ri(x) as target instead of p(x). The reason we might wish to do this, is by having an explicit form of mx)), we can learn a density by optimizing other divergences than the forward KL-divergence, such the reverse KL-divergence. Note that if we optimize
DKL DKL(a())]l DKL (KL(g Zm(x))
(11)
-KL (g(z) [[(()) log
(12)
Therefore, knowledge of the normalization constant is not needed in this context, since the constant term doesn't 't affect the optimization procedure. Similar results can be shown for other divergences.
A.3 VISUALIZATIONS OF SAMPLES FROM THE MIXTURE OF GAUSSIANS EXPERIMENT
15

---

Under review as a conference paper at ICLR 2020
Figure 5: Samples from learned densities which are parameterized 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.
16


Reviews:
[{"review_id": "rygtsAw7YB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to use ensembles of estimated probability distributions in hypothesis testing for anomaly detection.\nWhile the problem of density estimation with its application to anomaly detection is relevant, I have a number of concerns listed below:\n\n- Overall, this paper is not clearly written and it is difficult to follow.\n    Discussion is not straightforward at many points.\n    In particular, the objective of experiments on synthetic data in Section 3 is unclear. What is the proposal and how to evaluate it in the experiments?\n    There are also many grammatical mistakes, which also deteriorates the quality of the paper.\n- Technical quality is not high.\n    * Equations (3) and (4) are wrong. The distribution p should be not the ground truth but the empirical distribution.\n    * In experiments, only a simple Gaussian mixture model has been examined. A variety of distributions should be examined.\n    * How strong are the assumptions in Theorem 2 in practical situations?\n- There is no experimental evaluation for the proposed method. Hence the effectiveness of the proposed method is not clear.\n\nMinor comments:\n- P.2, L.3 in Section 2: \", The\" -> \", the\"\n- P.7, L.-6: \"q_1(x; \\theta_1,\" -> \"q_1(x; \\theta_1),\"\n- P.8, L.1 in Theorem 2: \"x \\in X, Consider\" -> \"x \\in X, consider\"\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkxifG02KH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nI machine learning, we often have training data representative of an underlying distribution, and we want to test whether additional data come from the same distribution as the training data (e.g. for outlier/anomaly detection, or model checking). One way to do this is to learn a model of the underlying distribution, and test whether the additional data fall within the typical set of the model. This paper points out that the typical set of the model may be very different from the typical set of the underlying distribution if the model is learned by maximum likelihood, in which case a test of typicality with respect to the model would be a poor test of typicality with respect to the underlying distribution. The paper shows theoretically that the intersection of the typical sets of an ensemble of models lies within the typical set of the underlying distribution, provided that (a) each model is a good enough approximation to the underlying distribution, and (b) the models are all sufficiently different from each other. Based on that, the paper argues that a better test of typicality would be to test whether the additional data fall within the intersection of the typical sets of the ensemble of models.\n\nPros:\n\nThe paper addresses an interesting problem in a sound and well motivated way. There is a lot of work on outlier/anomaly detection that uses the model's probability density to determine whether a dataset is out-of-distribution or not, which is known to not be a good proxy for typicality, because atypical data can have high probability density. In contrast, this paper uses a well-founded notion of typicality based on the information-theoretic definition of a typical set.\n\nThe toy example that is used to illustrate the problem is clear and illuminating, and motivates the paper well. In particular, the example clearly illustrates the issue of local minima when training models, and the mass-covering behaviour of maximum-likelihood training.\n\nThe idea of using the intersection of the typical sets of an ensemble of models is interesting and clever, and backed by strong theoretical results.\n\nCons:\n\nEven though I appreciate the paper's theoretical contribution, there are no empirical results other than the motivating example. In particular, the paper proposes an idea and theory to back it up, but it doesn't really propose a practical method, and as a result it doesn't test the theory in practice.\n\nTheorems 2 and 3 provide a solid foundation for the proposed idea, but it's not clear how they can be used in practice. Specifically:\n- How can we verify that in practice the KL between the models and the underlying distribution is small enough as required by theorem 2 when we can't usually evaluate it?\n- In practice, how should we construct an ensemble such that the individual models in the ensemble are different enough from each other as required by theorem 3?\n- Both theorem 2 and 3 are valid \"for large enough n\". However, in practice we may want to check e.g. individual datapoints for typicality (in which case n=1). Are the theorems relevant for small n?\n\nThe paper is generally well written, but some statements made are either inaccurate or subjective, and I worry that they might mislead readers. Later in my review I will point out exactly which statements I'm referring to. I strongly encourage the authors to fix or moderate these statements before the paper is published.\n\nDecision:\n\nI believe the paper to be an important contribution, but the work is clearly incomplete. For this reason, my recommendation is weak accept, with an encouragement to the authors to continue the good work.\n\nInaccuracies or subjective statements that I encourage the authors to fix/moderate:\n\n\"we are still bad at reliably predicting when those models will fail\"\n\"we are unable to detect when the models are presented with out-of-distribution data\"\nThese statements may come across as too strong. I suggest making the statements about our current methods, rather than about the ability of the research community, and be more specific in what ways the current methods are inadequate.\n\n\"detecting out-of-distribution data [...] is formally known as the goodness-of-fit problem\"\nI'm not sure that detecting our-of-distribution data and goodness-of-fit are synonymous. Goodness-of-fit testing can be used in situations other than outlier detection, e.g. for testing whether a proposed model is a good fit to a dataset.\n\n(Second bullet-point of section 1) \"distributions having low KL divergence must have non-zero intersection\"\nTo be more precise, the typical sets must have non-zero intersection, not the distributions.\n\n\"determining which of two hypotheses are more probable\"\n\"H0 is deemed more probable\"\nClassical hypothesis testing does not assign a probability to a hypothesis, which would be a Bayesian approach instead. Therefore, it's technically incorrect to talk about the probability of a hypothesis in this context.\n\n\"which accepts the null-hypothesis\"\n\"f correctly accepting H0\"\nHypothesis testing doesn't accept a hypothesis, it merely decides whether to reject the null hypothesis in favour of the alternative hypothesis. Therefore, it may \"fail to reject\" the null hypothesis, but it never accepts it.\n\n\"the KL-divergence is equal to zero if and only if p(x) = q(x; θ) ∀x ∈ X\"\nThe KL is equal to zero if and only if the distributions are equal, but the densities may still differ in at most a set of measure zero. Therefore, it's not a requirement that the densities match for all x for the KL to be zero.\n\n\"For example, by looking at the form of the KL-divergence, there is no direct penalty for q(x; θ) in assigning a high density to points far away from any of the ¯xi’s\"\nThe problem that this statement is talking about is the problem of overfitting, which is the problem of the model learning the specifics of the training data rather than the underlying distribution. However, the statement preceding the above is about the problem of local minima when optimizing then parameters of a model. These two problems are distinct and shouldn't be conflated, as they are here.\n\n\"this requires direct knowledge of p(x) to evaluate the objective\"\nHowever we can evaluate the objective up to an additive constant when p(x) is known up to a multiplicative constant, which is enough to optimize it.\n\n\"as do all divergences other than the forward KL, to the best of our knowledge\"\n\"This makes the forward KL-divergence special in that it is the only divergence which can directly be optimized for.\"\nI don't think this is true. For example, the Maximum Mean Discrepancy is a divergence, since it's non-negative and zero if and only if the two distributions are equal, but it only involves expectations under p(x) and can be directly optimized over the parameters of q(x; \\theta). Moreover, the second statement doesn't follow from the first: it's incorrect to conclude that the forward KL is the only one that can be directly optimized for, based only on one's state of knowledge.\n\n\"Variational Auto-encoders [...] map a lower-dimensional, latent random variable\"\nThere is no fundamental reason why the latent variable of a VAE has to be low-dimensional. We may do this often in practice, but a VAE with a high-dimensional latent variable may also be used.\n\n\"Because the image of any non-surjective function necessarily has measure zero\"\nThis is not true; the absolute-value function is not surjective but its image doesn't have measure zero in the set of real numbers. I understand what the statement is trying to say, but it's important that it's said accurately.\n\n\"autoregressive models, such as PixelCNN\"\nAutoregressive models can also be used to model discrete variables in which case they can't be thought of as flows. In fact, PixelCNN as first proposed is a model of discrete variables.\n\n\"all of these models rely on optimizing the forward KL-divergence in order to learn their parameters\"\nNot necessarily, flow-based models don't have to be optimized by minimizing the forward KL. For example, they can be trained adversarially in the same way as GANs, and in principle can be trained with other divergences or integral probability metrics. The model and the loss are (at least in principle) orthogonal choices.\n\n\"advancements in the expressivity of the models are unlikely to fix the undesired effects\"\nThis is a subjective assessment, and is not sufficiently backed by arguments where it first appears. I understand that the arguments are presented later in section 3, so I would at least suggest that a forward reference to the argumentation in section 3 is given here.\n\nFigure 5 gives the impression that the model samples have less variance than the ground-truth samples. Isn't that surprising given that the problem is that minimizing the forward KL leads to mass-covering behaviour? I suspect that the problem here is that there are more ground-truth samples than model samples, and the ground-truth samples saturate the scatter plot. If that's the case, I believe that figure 5 is very misleading.\n\n\"we see that the learning procedure converged\"\nWe know however that the learning procedure hasn't really converged, instead it is stuck at a saddle point (where the model is using a single mode to cover two modes of the underlying distribution). In other words, it appears to us that the learning procedure has converged, even though it hasn't, and possibly if we wait for long enough we will see rapid improvement when the procedure escapes the saddle point. Therefore, I would at least say \"we see that the learning procedure has appeared to converge\".\n\nI would expect the bottom-right entry of table 1 to be higher than 90% like the other diagonal elements, so I suspect that it might be a typo.\n\nIn eq. (7), shouldn't each log q_k be divided by n?\n\n\"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\"\nThere is no empirical evidence presented in the paper in support of this statement.\n\n\"least probable density\"\n\"least typical density\"\nI understand what the intended meaning of these terms is, but these terms make little sense mathematically nevertheless. I would suggest that the statement is rewritten in a more precise and direct way.\n\n\"This measure only corresponds to measuring typicality if the bijection is volume preserving\"\nI'm not sure that the distance from a Gaussian mean is a valid measure of typicality. In high dimensions, the region around the mean is very atypical.\n\nMinor errors, typos, and suggestions for improvement:\n\nThe phrase \"the authors in Smith et al. (2019) propose\" is a bit awkward. Better say \"Smith et al. (2019) propose\", as Smith et al are indeed the authors.\n\nMissing full stop in first bullet-point of section 1.\n\nIt would be good to provide more details of the experiment in section 3. Specifically:\n- What training algorithm was used to maximize the likelihood? SGD or EM?\n- How many training datapoints were used?\n\n\"to index the 5 experiments ran\" --> run\n\n\"refer the k-th learned density\" --> refer to\n\ninterestig --> interesting\n\nMissing closing bracket in point 1 of section 4.\n\nCapital C in \"Consider\" in theorem 2.\n\n\"if every model in a density of learned distributions\" --> an ensemble of learned distributions\n\n\"where as the method we propose\" --> whereas\n\n\"can be found in in\", double \"in\"", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1gQLJXzYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:  This paper analyzes and extends a recently proposed goodness-of-fit test based on typicality [Nalisnick et al., ArXiv 2019].  Firstly, the authors give bounds on the type-II error of this test, showing it can be characterized as a function of KLD[q || p_true] where p is the true data generating process and q is an alternative generative process.  The paper then shifts to the main contribution: an in-depth study of a Gaussian mixture simulation along with accompanying theoretical results.  The simulation shows that maximum likelihood estimation (MLE)---due to it optimizing KLD[p_true || p_model]---does not penalize the model for placing probability in places not occupied by p_true.  This means that while samples from p_true should fall within the model’s typical set, the model typical set may be broader than p_true’s.  Table 1 makes this clear by showing that only 30-40% of samples from the model fall within the typical set of p_true.  Yet >93% of samples from p_true fall within the models’ typical sets.  The paper then makes the observation that the models do not have high overlap in their typical sets, and thus p_true’s typical set could be well approximated by the intersection of the various models’ typical sets.  Applying this procedure to the Gaussian mixture simulation, the authors observe that ~95% of samples drawn from the intersection of the ensemble fall within p_true’s typical set.  Moreover, ~97% of samples from p_true are in the ensemble (intersection) typical set.  The paper closes by proving that the diversity of the ensemble controls the overlap in their typical sets, and hence increasing diversity should only improve the approximation of p_true’s typical set.             \n\n____\n\nPros:  This paper contributes some interesting ideas to a recent topic of interest in the community---namely, that deep generative models assign high likelihood to out-of-distribution (OOD) data [Nalisnick et al., ICLR 2019] and how should we address this problem if we are to use them for anomaly detection, model validation [Bishop, 1994], etc.  This paper makes some careful distinctions between the true data process, the model, and the alternative distribution, which I have not seen done often in this literature.  And while the mass-covering effect of MLE on the resulting model fit is well known, this paper is the first with which I am aware that translates that fact into a practical recommendation (i.e. their intersection method).  Furthermore, this connection to ensembling may provide important theoretical grounding to other ensemble-based methods for OOD detection [Choi et al., ArXiv 2019].   \n\n____\n\nCons:  The primary deficiency in the paper is experimental.  While the text does make some compelling arguments in the Gaussian mixture simulations, some validation on real data must be provided.  Ideally experiments on CIFAR-10 vs SVHN (OOD) and FashionMNIST vs MNIST (OOD) should be reported as these data set pairings have become the benchmark cases in this line of literature.  \n\nBesides the lack of experiments on real data, I find the paper’s material to be a bit disjointed and ununified.  For instance, Theorem 1 is never discussed again after it is presented in Section 2.1.  I thought for sure the presence of the KLD-term would be referenced again to relate the ensembling methodology back to the bound on the type-II error.  For another example, normalizing flows are discussed in Section 2.3 and the change-of-variables formula given in Equation 5.  However, normalizing flows are never mentioned again except in passing in the Related Work section.      \n\n____\n\nFinal Evaluation:  While I find the paper to contain interesting ideas, it is too unfinished for me to recommend acceptance at this time.  Experiments on real data must be included and the overall coherence of the draft improved.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new method for testing whether new data comes from the same distribution as training data without having an a-priori density model of the training data. This is done by looking at the intersection of typical sets of an ensemble of learned models. 

On the theoretical side, the paper was received positively by all reviewers. The theoretical results were deemed strong, and the ideas in the paper were considered novel. The problem setting was considered relevant, and seen as a good proposal to deal with the shortcoming of models on out of distribution data. 

However, the lack of empirical results on at least somewhat realistic datasets (e.g. MNIST) was commented on by all reviewers. The authors only present a toy experiment. The authors have explained their decision, but I agree with R1 that it would be appropriate in such situations to present the toy experiment next to a more realistic dataset. This also means that the effectiveness of the proposed method in real settings is as of yet unclear. Although the provided toy example was considered clear and illuminating, the clarity of the text could still be improved.

Although the reviewers had a spread in their final score, I think they would all agree that the direction this paper takes is very exciting, but that the current version of the paper is somewhat premature. Thus, unfortunately, I have to recommend rejection at this point. 


Decision: Reject