Year: 2019

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.

text: 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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 PRELIMINARIES
text: The setting we are concerned with is the following. Consider a continuous random variable x ∈ X with probability density function p(x). Let xn := (x1, x2, ..., xn) denote the collection of n random variables x. Let hp 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:
T (n) := {
xn ∈ Xn : | − 1 n
log p(xn)− hp| < } . (1)
In words, this is the set of sequences of samples whose average negative-log-probability is close to the differential entropy. This set has high probability under p(x), implying that most sequences of data points sampled from p(x) are contained in this set (Cover & Thomas, 2012).

heading: 2.1 HYPOTHESIS TESTING
text: We are interested in determining the plausibility that some collection of samples x̃n ∈ Xn 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, H0 := x̃n ∼ p(x) • The alternative-hypothesis, H1 := x̃n ∼ p̂(x),
where here p̂(x) is any distribution such that DKL(p‖p̂) ≥ d. If we define An ⊂ Xn to be the acceptance region for the null-hypothesis, or the set of all sequences xn such that H0 is deemed more probable, then we can define the probabilities of error as the following:
αn = p n(Acn), βn = max p̃:D(p‖p̃)≥d p̃n(An). (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 x̃n ∈ T (n) . In other words, a collection of points are determined to be anomalous with respect to p(x) iff x̃n 6∈ 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 H0, the test for typicality will fail to detect anomalous data at a rate no greater than the bound given.

heading: 2.2 DENSITY LEARNING AS OPTIMIZATION
text: 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, x̄2, ...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 θ DKL(p(x)‖q(x;θ)). (3)
The KL divergence is defined by DKL(p(x)‖q(x; θ)) := Ep[log p(x)q(x;θ) ]. By expanding terms and eliminating constants, it is clear that an equivalent optimization problem is
max θ Ep[log q(x;θ)] ≈ max θ
1
N N∑ i=1 log q(x̄i;θ). (4)
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 x̄i’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.

heading: 2.3 MODERN DENSITY PARAMETERIZATIONS
text: 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 :
q(x;θ) = r(z;θ) ∣∣∣dm(x;θ)
dx ∣∣∣ . (5) 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.

heading: 3 CASE STUDY ON SYNTHETIC DATA
text: 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.
Let M denote the number of mixture components in the base distribution. Then we define the base distribution as the following:
p(x) := M∑ m=1 πmpm(x;µm,Σm), (6)
where pm(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 := R100, 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 qk(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
learned densities attempt to represent the M = 20 modes of the base distribution using only about 12 of their 20 modes.
Recalling that the base distribution p(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.
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.

heading: 4 TYPICAL SETS OF ENSEMBLES OF LEARNED DENSITIES
text: 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 qk(x), k ∈ {1, ...,K}. For a given > 0 and positive integer n, this set is defined as the following:
T (n) ({q1(x), ..., qK(x)}) := {
xn ∈ Xn : max k∈{1,...,K}
| − log qk(xn)− hk| < } . (7)
Here, hk refers to the differential entropy of the k-th density in the ensemble, qk(x).
The method we propose is the following:
1. Train an ensemble of parameterized densities, {q1(x;θ1, ..., qK(x;θK)}, using random initializations and using the maximum likelihood objective (4).
2. When discerning between H0 and H1 (Section 2.1), we choose H0 iff x̃n ∈ T (n) ({q1(x;θ1), ..., qK(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 hp, and any collection of distributions qk(x), k ∈ {1, ...,K}, all having DKL(p‖qk) = dk < ∞. Let Tp := T (n) (p) denote the typical set of p, and similarly Tqk := T (n) (qk) the typical set of qk for each k ∈ {1, ...,K}.
For n sufficiently large, if the following hold, • 14 log (
1−2 K−1 K +
) > n
• dk < 1n log ( 1−2 e −4n − K−1 K ) + 3
then V ol ( Tp ⋂ k Tqk ) > 0.
Theorem 3. For continuous random variable x ∈ X , consider two distributions, qa(x) and qb(x). Denote ha and hb, the differential entropy of these distributions, respectively. Similarly, let Ta := T (n) (qa) and Tb := T (n) (qb) represent the typical sets of qa and qb. If for some 0 < r ≤ 1, and n sufficiently large,
DKL(qa‖qb) > hb − ha − 3 + 1 n log ( 1 r(1− )e−2n − 2 ) ,
then, V ol ( Ta ∩ Tb ) V ol ( Ta ) < 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.

heading: 5 RELATED WORK
text: 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 Chen et al. (2017), Ho et al. (2019), Grathwohl et al. (2018), De Cao et al. (2019), van den Oord et al. (2017), and Razavi et al. (2019), to list a few. There are also other objectives that are considered when learning densities, such as training a density in a adversarial manner as in Grover et al. (2018) and Danihelka et al. (2017). Alternatively, Li & Malik (2018) define implicit maximum likelihood estimation, which can be thought of as approximately minimizing the reverse KL-divergence.

heading: 6 CONCLUSION
text: 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.

heading: A APPENDIX
text: A.1 PROOF OF THEOREMS
To prove Theorem 1, we make use of the following lemma.
Lemma 1. Consider a continuous random variable x ∈ X , and two distributions qa(x) and qb(x). Denote the differential entropy of qa(x) and qb(x) as ha and hb, respectively. Let DKL(qa‖qb) = d. Denote the typical sets of these distributions as Ta := T (n) (qa(x)) and Tb := T (n) (qb(x)). Finally, let Tab := T (n) (DKL(qa‖qb) represent the relative entropy typical set (Cover & Thomas (2012), Section 11.8). Then, for n sufficiently large,
qa(Tb) < e −n(d+ha−hb−3 ) + 3 .
Proof of Lemma 1. We prove this lemma through contradiction. Assume
qa(Tb) > e −n(d+ha−hb−3 ) + 3 .
Then by Theorem 8.2.2 in Cover & Thomas (2012) and the union bound, we have
qa(Ta ∩ Tb) > e−n(d+ha−hb−3 ) + 2 ,
and, qa(Ta ∩ Tab) > 1− 2 . This implies that
e−n(d+ha−hb−3 ) < qa(Ta ∩ Tb ∩ Tab) < e−n(ha− )V ol(Ta ∩ Tb ∩ Tab),
implying e−n(d−hb−2 ) < V ol(Ta ∩ Tb ∩ Tab).
We also have that
qb(Tab) > qb(Ta ∩ Tb ∩ Tab) > V ol(Ta ∩ Tb ∩ Tab) · min x∈Ta∩Tb∩Tab qb(x)
> e−n(d−hb−2 )e−n(hb+ )
= e−n(d− )
However, we also have that qb(Tab) < e−n(d− ) by Lemma 11.8.1 in Cover & Thomas (2012). This implies that
e−n(d− ) < e−n(d− ),
which forms a contradiction. Therefore, our original assumption must be false, and therefore
qa(Tb) < e −n(d+ha−hb−3 ) + 3 .
Proof of Theorem 1. The proof relies on the preceding lemma. Letting Tb in Lemma 1 correspond to our acceptance region for H0, T (n) (p(x)), then Lemma 1 states that for any distribution p̃, the probability
p̃(T (n) (p(x))) < e −n(DKL(p̃‖p)+hp̃−hp−3 ) + 3 .
Therefore, by optimizing over all distributions p̃(x) such that DKL(p‖p̃) < d, the result follows immediately.
To prove Theorem 2, we make use of the following lemmas.
Lemma 2. For n sufficiently large,
qk(Tp) > (1− 2 )e−n(dk+ )
Proof of Lemma 2. See Cover & Thomas (2012), Lemma 11.8.1.
Lemma 3. For n sufficiently large, V ol ( Tp ∩ Tqk ) ≥ (1− 2 )en(h(p)−3 ) − en(h(p)+dk−2 ).
Proof of Lemma 3. For n sufficiently large, qk(Tqk) > 1− , as shown in Cover & Thomas (2012), Theorem 8.2.2. By the union bound and Lemma 2,
qk(T c qk ∪ T cp) < + 1− (1− 2 )e−n(dk+ )
(1− 2 )e−n(d+ ) − < qk(Tqk ∩ Tp) ≤ ∫
x∈Tqk∩Tp p(xn)e−n(dk− )dxn
≤ ∫
x∈Tqk∩Tp e−n(h(p)− )e−n(dk− )dxn
= e−n(h(p)+dk−2 )V ol ( Tqk ∩ Tp ) (1− 2 )en(h(p)−3 ) − en(h(p)+dk−2 ) < V ol ( Tqk ∩ Tp )
Lemma 4. For sets Si ⊂ X , i ∈ {0, ...,K}, if
V ol(Si ∩ S0) V ol(S0) > K − 1 K , ∀i ∈ {1, ...,K},
Then V ol( ⋂K i=0 Si) > 0.
Proof of Lemma 4. Immediate consequence of union bound. Proof of Theorem 2. For n sufficiently large, V ol ( T (p) ) < en(h(p)+ ) (Cover & Thomas (2012), Theorem 8.2.2). If for all k ∈ {1, ...,K},
V ol(T (qk) ∩ T (p)) V ol(Tp) > K − 1 K ,
then by Lemma 4, the result holds. For k ∈ {1, ...,K},
V ol(T (qk) ∩ T (p)) V ol(T (p)) > (1− 2 )en(h(p)−3 ) − en(h(p)+dk−2 ) en(h(p)+ )
= (1− 2 )e−4n − en(dk−3 ).
Therefore if K − 1 K < (1− 2 )e−4n − en(dk−3 ),
or equivalently
dk < 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.
Proof of Theorem 3. Similar to Lemma 1, we prove this by contradiction. We make use of bounds that hold for n sufficiently large, which we assume from here on to avoid repeatedly stating so. Let Tab := T (n) (DKL(qa‖qb)) represent the relative entropy typical set (Cover & Thomas (2012), Section 11.8).
Assume that, in fact, V ol ( Ta ∩ Tb ) V ol ( Ta ) > r.
Therefore, by Theorem 8.2.2 in Cover & Thomas (2012), V ol ( Ta ∩ Tb ) > rV ol ( Ta )
> r(1− )en(ha− ).
However, by the definition of Ta,
V ol ( Ta ∩ Tb ) <
qa(Ta ∩ Tb) minxn∈Ta∩Tb qa(x n)
< qa(Ta ∩ Tb) e−n(ha+ ) .
This then implies that qa(Ta ∩ Tb) > r(1− )e−2n .
Now, using the union bound and Theorem 11.8.2 in Cover & Thomas (2012), we have that
qa(Ta ∩ Tab) > 1− 2 .
Therefore, again by the union bound,
r(1− )e−2n − 2 < qa(Ta ∩ Tb ∩ Tab)
= ∫ xn∈Ta∩Tb∩Tab qa(x n)dxn
< e−n(ha− )V ol(Ta ∩ Tb ∩ Tab) =⇒ V (Ta ∩ Tb ∩ Tab) > (r(1− )e−2n − 2 )en(ha− ).
Finally, we have that
qb(Tab) ≥ qb(Ta ∩ Tb ∩ Tab) ≥ V ol(Ta ∩ Tb ∩ Tab) · min xn∈Ta∩Tb∩Tab qb(x n)
= V ol(Ta ∩ Tb ∩ Tab)e−n(hb+ )
> (r(1− )e−2n − 2 )e−n(hb−ha+2 ).
From Theorem 11.8.2 referenced above, we also have that qb(Tab) < e−n(DKL(qa‖qb)− ), which implies the following.
(r(1− )e−2n − 2 )e−n(hb−ha+2 ) < e−n(DKL(qa‖qb)+ ) log ( r(1− )e−2n − 2 ) − n(hb − ha + 2 ) < −n ( DKL(qa‖qb)− ) .
Rearranging, this gives rise to the condition:
DKL(qa‖qb) > hb − ha − 3 + 1 n log ( 1 r(1− )e−2n − 2 ) .
If this condition does not hold, then there is a contradiction, and our original assumption that V ol ( Ta ∩ Tb ) V ol ( Ta ) < r
must be false.
A.2 EXPRESSING THE MULTI-TYPICAL SET AS THE TYPICAL SET OF SOME DISTRIBUTION
Recall the definition of the multi-typical set for a given ensemble of probability distributions: T (n) ({q1(x), ..., qK(x)}) := {
xn ∈ Xn : max k∈{1,...,K}
| − log qk(xn)− hk| < } . (8)
An interesting question to ask is if there exist a probability distribution which has typical set corresponding to the multi-typical set defined here. Here we show that we can approximately recover an un-normalized version of such a distribution.
Define q̃k(x) := ehkqk(x). Then we have T (n) ({q1(x), ..., qK(x)}) = {
xn ∈ Xn : max k∈{1,...,K}
| log q̃k(xn)| < } . (9)
.
Defining m̃(x) := q̃k(x), k = argmini | log q̃i(x)|, we have T (n) ({q1(x), ..., qK(x)}) = { xn ∈ Xn : | log m̃(xn)| < } . (10)
. Now, define Z = ∫
x∈X m̃(x)dx, and m(x) = m̃(x)/Z such that m(x) is a valid probability distribution. Then if Em[− logm(x)] = log(Z), then the distribution m(x) has typical set identical to the set T (n) ({q1(x), ..., qK(x)}). The property that Em[− logm(x)] = log(Z) will not hold exactly in practice, but often times it is approximately true. The reason this is true is because over the space X , each of the functions log q̃k(x) have zero mean. Pointwise, the function m̃(x) takes as its value the q̃k whose log value is farthest from the origin. If the q̃k are chosen such that on average, equal mass is kept on either side of the origin (in log-space), then the property will hold.
The result of such a procedure is a approximation of the density which has typical set identical to the multi-typical set. Since in practice computing the normalization constant Z is intractable, we can learn another divergence, using m̃(x) as a target instead of p(x). The reason we might wish to do this, is by having an explicit form of m̃(x), we can learn a density by optimizing other divergences than the forward KL-divergence, such as the reverse KL-divergence. Note that if we optimize
DKL(q(x)‖m̃(x)) = DKL(q(x)‖Zm(x)) (11) = DKL(q(x)‖m(x))− logZ. (12)
Therefore, knowledge of the normalization constant is not needed in this context, since the constant term doesn’t affect the optimization procedure. Similar results can be shown for other divergences.
A.3 VISUALIZATIONS OF SAMPLES FROM THE MIXTURE OF GAUSSIANS EXPERIMENT

Review summaries:
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.             

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.