Title: TESTING TYPICALITY WITH RESPECT TO AN ENSEMBLE OF LEARNED DISTRIBUTIONS Anonymous

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 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 esti-mated. 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-ofthe-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 x ∈ X with probability density function p(x). Let x n := (x 1 , x 2 , ..., x n ) denote the collection of n random variables x. Let h p denote the differential entropy of p(x). For > 0 and positive integer n, The typical set with respect to p(x) is defined as the following:

EQUATION

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(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 xn ∈ X n were sampled i.i.d. according to p(x). In hypothesis testing terminology, we are interested in determining which of two hypotheses are more probable:

• The null-hypothesis,

H 0 := xn ∼ p(x)

• The alternative-hypothesis,

H 1 := xn ∼ p(x),

where here p(x) is any distribution such that D KL (p p) ≥ d. If we define A n ⊂ X n to be the acceptance region for the null-hypothesis, or the set of all sequences x n such that H 0 is deemed more probable, then we can define the probabilities of error as the following:

α n = p n (A c n ), β n = max p:D(p p)≥d pn (A n ).

(2)

Typically we desire tests that minimize β n for a fixed α 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 xn ∈ T (n) . In other words, a collection of points are determined to be anomalous with respect to p(x) iff xn ∈ T (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(x). In order to validate this approach, we first prove that for a fixed α n , the typical set test achieves an error rate β n that is at worst, given by: Theorem 1. Let the region of acceptance for the typicality test be defined by the set T

(n) (p(x)). For n sufficiently large, then α n < , and

β n < max p:D(p p)≥d e -n(DKL( p p)+hp-hp-3 ) + 3 Proof of Theorem 1. See Section A.1.

This theorem states that for a fixed rate of correctly accepting 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(x) is needed. For many practical applications, we are only ever presented with a data set of N samples from p(x), which we denote X = (x 1 , x2 , ...x N ). However, an estimate of the ground-truth density can be learned. We denote a parameterized distribution by q(x; θ), which can be learned by minimizing the following objective:

min θ D KL (p(x) q(x; θ)).

(3)

The KL divergence is defined by D KL (p(x) q(x; θ)) := E p [log p(x) q(x;θ) ]. By expanding terms and eliminating constants, it is clear that an equivalent optimization problem is

EQUATION

The optimal θ 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 maximum-likelihood 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-divergence is equal to zero if and only if p(x) = q(x; θ) ∀x ∈ X , this objective is well-motivated if we wish that q(x; θ) ≈ p(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(x; θ) 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 θ * such that q(x; θ * ) = p(x).

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. This can lead to locally optimal learned densities which have high probability density in regions of 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(x), but in-distribution with respect to the sub-optimally learned q(x; θ).

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(x) and q(x; θ) in the standard KL-divergence, has an alternate effect; q(x; θ) is directly penalized for assigning high density to 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 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(x; θ) : X → Z is a continuously differentiable bijection, and r(z; θ) is a probability density function corresponding to random variable z ∈ Z, then together m and r implicitly define a probability density function over random variable x ∈ X :

EQUATION

So long as the determinant in ( 5) is easy to evaluate, the probability density q(x; θ) can be evaluated and the parameters θ 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. Let M denote the number of mixture components in the base distribution. Then we define the base distribution as the following:

EQUATION

where p m (x; µ m , Σ m ) is the probability density function associated with a Gaussian distribution with mean µ m 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 we consider the parameters µ m and Σ m to be chosen such that the µ m are sampled from a uniform distribution over a hyper-ball with radius r = 3.0, and the matrices Σ 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 π 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(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. We attempt to learn p(x) by optimizing (4), for a q(x; θ) parameterized exactly as p(x). In other words, the parameters θ are the set {π 1 , µ 1 , Σ 1 , π 2 , µ 2 , Σ 2 , ..., π M , µ M , Σ M }, where the π m > 0 are constrained to sum to 1, and the Σ m are constrained to be positive definite and diagonal.

We perform five experiments, each time randomly initializing the parameters θ exactly as was done for p(x). We use the indices k ∈ {1, ..., K = 5} to index the 5 experiments ran, and refer the the k-th learned density as q k (x; θ 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 Recalling that the base distribution p(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). 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.

Table 1 : 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 set n = 1. Note that each of the learned densities include most 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.

Sampling Distribution p(x) q 1 (x; θ 1 ) q 2 (x; θ 2 ) q 3 (x; θ 3 ) q 4 (x; θ 4 ) q 5 (x; θ 5 ) T 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.

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 (x), k ∈ {1, ..., K}.

For a given > 0 and positive integer n, this set is defined as the following:

EQUATION

Here, h k refers to the differential entropy of the k-th density in the ensemble, q k (x).

The method we propose is the following:

1. Train an ensemble of parameterized densities, {q 1 (x; θ 1 , ..., q K (x; θ K )}, using random initializations and using the maximum likelihood objective (4). 2. When discerning between H 0 and H 1 (Section 2.1), we choose H 0 iff xn ∈ T (n) ({q 1 (x; θ 1 ), ..., q K (x; θ 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 KLdivergence 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 x ∈ X , Consider some distribution p(x) with differential entropy h p , and any collection of distributions

q k (x), k ∈ {1, ..., K}, all hav- ing D KL (p q k ) = d k < ∞. Let T p := T (n) (p)

denote the typical set of p, and similarly

T q k := T (n) (q k ) the typical set of q k for each k ∈ {1, ..., K}.

For n sufficiently large, if the following hold,

• 1 4 log 1-2 K-1 K + > n • d k < 1 n log 1-2 e -4n -K-1 K + 3 then V ol T p k T q k > 0.

Theorem 3. For continuous random variable x ∈ X , consider two distributions, q a (x) and q b (x). Denote h a and h b , the differential entropy of these distributions, respectively. Similarly, let T a := T (n) (q a ) and T b := T (n) (q b ) represent the typical sets of q a and q b . If for some 0 < r ≤ 1, and n sufficiently large,

D KL (q a q b ) > h b -h a -3 + 1 n log 1 r(1 -)e -2n -2 , then, V ol T a ∩ T b V ol T a < 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 (n) (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 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

(n) (p(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 (n) (p(x)). Here we use the word conservative, since the conditions only are sufficient for the multi-typical set to act as an underapproximation of T (n) (p(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 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 pointwise 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 outof-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 

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 multitypicality test proposed here, and further evaluating the empirical performance of our proposed test on different domains.

Lemma 3. For n sufficiently large, V ol T p ∩ T q k ≥ (1 -2 )e n(h(p)-3 ) -e n(h(p)+d k -2 ) .

Proof of Lemma 3. For n sufficiently large, q k (T q k ) > 1 -, as shown in Cover & Thomas (2012), Theorem 8.2.2. By the union bound and Lemma 2, q k (T c q k ∪ T c p ) < + 1 -(1 -2 )e -n(d k + ) (1 -2 )e -n(d+ ) -< q k (T q k ∩ T p )

≤ x∈Tq k ∩Tp p(x n )e -n(d k -) dx n ≤ x∈Tq k ∩Tp

e -n(h(p)-) e -n(d k -) dx n = e -n(h(p)+d k -2 ) V ol T q k ∩ T p (1 -2 )e n(h(p)-3 ) -e n(h(p)+d k -2 ) < V ol T q k ∩ T p Lemma 4. For sets S i ⊂ X , i ∈ {0, ..., K}, if V ol(S i ∩ S 0 )

V ol(S 0 ) > K -1 K , ∀i ∈ {1, ..., K},

Then V ol( K i=0 S i ) > 0.

Proof of Lemma 4. Immediate consequence of union bound.

Proof of Theorem 2. For n sufficiently large, V ol T (p) < e n(h(p)+ ) (Cover & Thomas (2012), Theorem 8.2.2). If for all k ∈ {1, ..., K}, V ol(T (q k ) ∩ T (p))

V ol(T p) > K -1 K , then by Lemma 4, the result holds. For k ∈ {1, ..., K}, V ol(T (q k ) ∩ T (p))

V ol(T (p)) > (1 -2 )e n(h(p)-3 ) -e n(h(p)+d k -2 ) e n(h(p)+ )

= (1 -2 )e -4n -e n(d k -3 ) .

Therefore if K -1 K < (1 -2 )e -4n -e n(d k -3 ) , or equivalently

d k < 1 n log 1 -2 e -4n - K -1 K + 3 ,

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 4 log 1 -2 K-1 K + > n.

These conditions are the two conditions in Theorem 2. 

:

CASE STUDY ON SYNTHETIC DATATo 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.

Figures and Tables:

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

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

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.

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.

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.

Peer review (iclr2020):
Summary: I 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. Pros: The 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. The 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. The idea of using the intersection of the typical sets of an ensemble of models is interesting and clever, and backed by strong theoretical results. Cons: Even 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. Theorems 2 and 3 provide a solid foundation for the proposed idea, but it*s not clear how they can be used in practice. Specifically: - 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? - 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? - 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? The 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. Decision: I 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. Inaccuracies or subjective statements that I encourage the authors to fix/moderate: *we are still bad at reliably predicting when those models will fail* *we are unable to detect when the models are presented with out-of-distribution data* These 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. *detecting out-of-distribution data [...] is formally known as the goodness-of-fit problem* I*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. (Second bullet-point of section 1) *distributions having low KL divergence must have non-zero intersection* To be more precise, the typical sets must have non-zero intersection, not the distributions. *determining which of two hypotheses are more probable* *H0 is deemed more probable* Classical 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. *which accepts the null-hypothesis* *f correctly accepting H0* Hypothesis 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. *the KL-divergence is equal to zero if and only if p(x) = q(x; ?) ?x ? X* The 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. *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* The 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. *this requires direct knowledge of p(x) to evaluate the objective* However 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. *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.* I 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; 	heta). 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. *Variational Auto-encoders [...] map a lower-dimensional, latent random variable* There 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. *Because the image of any non-surjective function necessarily has measure zero* This 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. *autoregressive models, such as PixelCNN* Autoregressive 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. *all of these models rely on optimizing the forward KL-divergence in order to learn their parameters* Not 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. *advancements in the expressivity of the models are unlikely to fix the undesired effects* This 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. Figure 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. *we see that the learning procedure converged* We 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*. I 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. In eq. (7), shouldn*t each log q_k be divided by 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* There is no empirical evidence presented in the paper in support of this statement. *least probable density* *least typical density* I 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. *This measure only corresponds to measuring typicality if the bijection is volume preserving* I*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. Minor errors, typos, and suggestions for improvement: The 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. Missing full stop in first bullet-point of section 1. It would be good to provide more details of the experiment in section 3. Specifically: - What training algorithm was used to maximize the likelihood? SGD or EM? - How many training datapoints were used? *to index the 5 experiments ran* --> run *refer the k-th learned density* --> refer to interestig --> interesting Missing closing bracket in point 1 of section 4. Capital C in *Consider* in theorem 2. *if every model in a density of learned distributions* --> an ensemble of learned distributions *where as the method we propose* --> whereas *can be found in in*, double *in*