Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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; \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.

"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"
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper proposes to use ensembles of estimated probability distributions in hypothesis testing for anomaly detection.
While the problem of density estimation with its application to anomaly detection is relevant, I have a number of concerns listed below:

- Overall, this paper is not clearly written and it is difficult to follow.
    Discussion is not straightforward at many points.
    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?
    There are also many grammatical mistakes, which also deteriorates the quality of the paper.
- Technical quality is not high.
    * Equations (3) and (4) are wrong. The distribution p should be not the ground truth but the empirical distribution.
    * In experiments, only a simple Gaussian mixture model has been examined. A variety of distributions should be examined.
    * How strong are the assumptions in Theorem 2 in practical situations?
- There is no experimental evaluation for the proposed method. Hence the effectiveness of the proposed method is not clear.

Minor comments:
- P.2, L.3 in Section 2: ", The" -> ", the"
- P.7, L.-6: "q_1(x; \theta_1," -> "q_1(x; \theta_1),"
- P.8, L.1 in Theorem 2: "x \in X, Consider" -> "x \in X, consider"

review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: 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.             

____

Pros:  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].   

____

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

Besides 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.      

____

Final 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.

review_title: Official Blind Review #1

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