Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes using a Bayesian hypothesis test for out-of-distribution detection with deep generative models.  The null hypothesis is that the newly observed data is in-sample and the alternative is that the new data is out-of-sample.  The test statistic is a likelihood ratio between the max likelihood model and the model fit to the given test input.  As this statistic is impractical to compute, the paper uses a perturbation of the MLE to find the parameters for the single sample test point.  The paper shows (Prop 1) that this test is the locally most powerful Bayesian test if the training set is sufficiently large.  Yet as the test requires computation of the inverse Hessian matrix, a low-rank approximation is necessary in practice.  Experiments are reported on benchmark image data sets (FashionMNIST, CIFAR, SVHN, CelebA, etc).  The proposed method performs well in terms of AUROC when compared to likelihood ratios and input complexity.  An ablation study of the rank of the Hessian approximation is also performs and shows the method is relatively insensitive to the rank.
main_review: ### Positives

**(Mostly) well-motivated approach to detecting distribution shift**:  This paper adapts the well-founded techniques of Bayesian hypothesis testing to deep generative models.  As detecting distribution shift with DGMs, ideally, requires fast, per-point evaluation, this method seems to provide just that.  Although, see my question / critique regarding identifiability below.

**Tuning computational overhead**:  As Figure 2 demonstrates, the method seems to work well—or even a bit better—when using a low-rank approximation to the Hessian matrix.  This allows the user to tune the method's computational overhead to fit the application.  This is important as detecting distribution shift often must be done in real time.  

### Critiques / Questions

**Local approximation and its validity for overparameterized models**:  While the motivating Bayesian hypothesis testing framework is undoubtedly motivated for well-identified models, it seems like identifiability could be an issue for deep generative models.  In neural networks, we know that there are often directions in parameter space around local minima that can leave the resulting model unchanged [[Maddox et al.; 2020]](https://arxiv.org/abs/2003.02139).  Thus, are parameterization issues such as this a worry when applying this test to deep generative models?  How do we know the local perturbation method won't detect these directions, thinking there is indeed distribution shift, while the model is actually invariant?  

**Why is the AUROC best at around 30 eigenvalues?:**  I was surprised to see that the test's performance doesn't improve monotonically with the rank of the approximation.  Do you have any idea why this is?  You mention that the Hessian is sparse, explaining the good performance at low rank, but I don't think this would explain why performance degrades a bit as rank increases.  Could this possibly be due to the "spurious" directions in parameter space I mention above?

**Remainder term in Proposition 1**:  Prop 1, how is the remainder term resolved?  Equation 12 is stated as an approximation, and I see how the 1/n term implies a good approximation when the data set is large.  But how do we know that the remainder term also can go to zero?  It seems like the paper is concerned about the convergence of the first and second order terms without discussing when they dominate the remainder?

**Discussion of score matching and [Sharma et al. (UAI 2021)](https://arxiv.org/abs/2102.12567)**: The paper is light in its discussion of previous work on OOD detection for deep generative models, and there is no Related Work section.  I think previous work on score matching and the Fisher information approach of Sharma et al. [UAI 2021] should be discussed as I see these as related methods, using perturbations of the log density function to test for OOD-ness.
limitations_and_societal_impact: Yes, as detecting distribution shift can improve the safety of AI systems, this method should have positive societal impact.  There are some limitations not mentioned in the paper (e.g. the issue of identifiability), which I mention above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new Bayesian hypothesis test for out-of-distribution detection (OOD) based on a trained generative model. The problem is formulated as a hypothesis testing on the parameter of the model where the null hypothesis $H_0$ posits that the model parameter is $\theta_0$ and the alterternative $H_1$ states that the parameter is $\theta_1$. The test statistic is the ratio of the posterior probabilities of the two (Bayes factor. See (5)). This way to formulate the problem is common and $\theta_0$ is commonly set to the maximum likelihood estimate (MLE) on the training data (in-distribution samples).

The main contribution of this paper is in setting $\theta_1$. The paper proposes to set it by MLE but on data constructed by combining the training data and the test point to test (i.e., so one more point added to the training data. See (7)). The paper shows that doing this leads to a test that satisfies a new notion called “locally most powerful Bayesian test” (LMPBT) given in Def 3.1. Since fully estimating the MLE on the augmented training data for each point to test is expensive, the paper further proposes a way to scale up, based on the use of the upweighting method from [9], and Hessian approximation (see (8) and Sec 4.1). The resulting MLE solution on the augmented data can be written as an additive perturbation (involving a low-rank Hessian) of the MLE estimate from the original training data. In this way, the MLE on the training data can be estimated only once, and reused for each OOD test point. In experiments, the new Bayesian test is shown to outperform competing approaches on standard benchmark datasets such as CIFAR10, CIFAR100, SVHN, MNIST, and Fashion MNIST.

main_review: 
*Clarity*:

The paper is fairly well written. The problem setting and background are briefly given just enough to understand the contribution, which is good. Preciseness in mathematical statements can be improved. For instance, the use of $\approx$ in the proof of Prop 1 makes it unclear about the effect of the omission of the remainder term in the Taylor expansion. It is also unclear what “sufficiently small $\delta$” means in Def 3.1 (i.e., how small is small). Other than these, the main ideas presented and the details of the proposed method are easy to follow.

*Originality*:

The use of Bayes factor for OOD is natural and has been considered before. The main contributions are 
1. Setting $\theta_1$ by MLE on the augmented training data (training data + the test point);
2. The use of upweighting ((9)) to avoid a full MLE computation for each point, as well as its further low-rank Hessian approximation (Sec 4.1) to scale up;
3. The result in Prop 4.1 stating that setting $\theta_1$ in this way results in a locally most powerful test.

The upweighting method is known from [9], and the low rank Hessian approximation is a commonly used operation especially in the optimization literature among others. In that sense, I see that the originality mainly comes from the idea in 1) and the result in 3). Overall I find that the paper has nicely put together these results and makes a practical approach.

*Quality*:

There is some impreciseness in the statement of Prop 4.1, and Def 3.1 however. More in the questions below. Up to these impreciseness, the proposed Bayesian approach appears to be technically sound.


*Significance*:

The proposed test gives strong empirical results, outperforming competing methods. Empirically, the approach is deemed significant, and may open up a new direction for OOD. There are some unclear points regarding experiments, as discussed below. Theoretical significance is lacking however. Besides showing that the approach is a locally most powerful Bayesian test (LMPBT), there is no further elaboration on the implications of this statement.  The definition of the LMPBT also appears to be proposed by the present work for the first time, tailored to fit the proposed approach (combining [6] and [12]).

## Questions
1. In the definition of LMPBT in Def 3.1, how small is small for $\delta$?
2. What are the implications of Proposition 1? That is, the test is a LMPBT. What can be said more about this? Is it the only test that satisfies this definition?
3. In (9), the Hessian-gradient product term carries a factor of 1/n where n is the sample size. What happens asymptotically (i.e., when n goes to infinity)? Does it mean $\tilde{\theta}_t$ (MLE on the augmented data) would be the same as $\hat{\theta}_t$ (MLE on the training data)? What happens to the decision of the test in that case?
4. In Fig 2b, why does the AUC curve fluctuate as $r$ the number of eigenvectors in approximating the Hessian increases? Naturally one would expect the approximation to get better as $r$ increases.
5. In Fig 3, what does “tested on CIFAR-100 test data and SVHN” mean? Are they combined into one test set? I’m trying to see why the likelihood ratio LLR shows completely different behaviors in  Fig 3a and Fig 3b.

—-

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: **Summary**
This paper presents a novel OOD detection method for deep generative models. The key idea is to formulate OOD detection as a Bayesian hypothesis test, where the OOD score is the log of likelihood ratio under the original network parameters $\theta_0$ and new parameters $\theta_1$ when adding the test sample $\mathbf{x}_t$. The overall testing framework is similar to previous works on likelihood ratio (Ren et al. 2019) and likelihood regret (Xiao et al. 2020). The novelty lies in the estimation of $\theta_1$ under the alternative hypothesis. Specifically, the authors estimate new network parameters using the second-order Hessian information. The authors also propose strategies to reduce the computational cost. Evaluations on both CIFAR-10 and CIFAR-100 demonstrate superior performance. 
main_review: **Strengths**:
- Authors extensively evaluate the proposed method under two generative models (VAE and Glow) and various datasets.
- The performance improvement over the prior state-of-the-art, name likelihood regret, is significant. 
- The test is mathematically grounded. 
- The authors spent efforts addressing two key challenges related to the computational issues in Section 4: (1) low-rank approximation of the hessian and (2) inverse of Hessian. The experimental results in L268-L274 also presented convincing evidence. 
- The writing is mostly clear but can be improved.

**Weaknesses**:

- Likelihood Regret [r1] seems to share the same spirit in terms of estimating the new network parameters when the test sample x_t is added to the training set.  [r1] finetunes the model with the test sample for a few iterations, which seems to be the upper bound of the authors' algorithm., i.e, the proposed method is the approximation of the fine-tuned parameters. An explanation and discussion about why the authors' method surpasses  [r1] are needed. 
- According to the authors' code, they need a preprocessing step to compute the top-k Hessian eigenvectors and eigenvalues of the original model using power iteration across the whole training set. The computation budget would be very high given this pre-processing approach. More discussion on this would be appreciated. 
- The computational overhead could be significantly higher when employing the proposed method on the high-resolution datasets and large models due to the computation of Hessian. While the reviewer understands it's a general concern shared by second-order methods, it'd be informative to test the limits of the approach. 

Minor: 
Typo in the caption of Table 6 in Appendix, it should be the results under CIFAR-100, not CIFAR-10.

[r1] Z. Xiao, Q. Yan, and Y. Amit. Likelihood regret: An out-of-distribution detection score for variational auto-encoder. arXiv preprint arXiv:2003.02977, 2020.
limitations_and_societal_impact: The author does not include on in the main paper but this doesn't affect my scoring.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new method for out-of-distribution (OOD) detection using deep generative models. In particular, the paper leverages a Bayesian hypothesis testing framework, and is based the so-called „locally most powerful Bayesian test“, which enjoys certain theoretical guarantees (namely that it maximizes the probability of correct OOD detection) under some conditions. It is described how the intractable test can be efficiently implemented in practice (when used in conjunction with deep generative models), leveraging low-rank approximations of the involved Hessian matrix. Empirical evaluations demonstrate that the proposed approach compares favorably to alternative methods in a variety of settings, for both VAE and Glow models.
main_review: **Post Rebuttal**

The author response convincingly addressed the main concerns I had raised -- I therefore increase my score from 6 (weak acceptance) to 7 (acceptance).

---

This manuscript proposes a new method to tackle the important OOD detection problem. It is therefore relevant to the NeurIPS community and has potentially high impact. The method is theoretically motivated by Bayesian hypothesis testing, is intuitively sensible and easy-to-understand. The experiments clearly demonstrate that the proposed approach performs strongly compared to other recently-developed OOD detection methods for deep generative models. However, the computational complexity of the method is not entirely transparent. The required Hessian approximation seems fairly expensive, which is only insufficiently analyzed. (See comments below for more details.) Adding such an analysis to the paper would significantly strengthen it. All in all, I am tending towards recommending acceptance of the paper — I am happy to strengthen my recommendation if the authors can convincingly address the raised issues.


Detailed comments:
- I like the idea of explicitly formulating the OOD detection as a Bayesian hypothesis test, which to my knowledge has not been done in prior work.
- The proposed approach is conceptually simple, intuitively sensible and appears to be theoretically grounded and sound. The paper also provides some useful theoretical analysis of the properties of the Bayesian test used for OOD detection.
- It is described how the (originally intractable) method can be implemented in practice by doing a low-rank approximation of the required full-network Hessian (which is implemented using power iteration) and using Hessian-vector products that avoid computation and storage of the full Hessian. While this approach seems reasonable, it is not clear how the computational complexity compares to that of other OOD detection methods; using power iteration to obtain the top eigenvectors/-values is expected to still be comparably expensive, so a more thorough and transparent analysis of the computational cost would improve the paper significantly (see also below for a the comment on the short analysis provided in the experiments).
- They describe how their Bayesian testing framework generalizes previous likelihood-ratio based OOD detection methods, which is insightful.
- The empirical evaluation convincingly demonstrates the effectiveness of the proposed approach in a variety of settings, as compared to strong baselines such as LR, LLR and IC, for different types of deep generative models (in particular VAEs and Glow).
- They study how the rank of the low-rank approximation of the Hessian (i.e. the number of eigenvalues considered) affects the OOD detection performance, showing that even for deep neural network models, a small number of eigenvalues (i.e. 20-30) achieves the best performance. However, Fig 2 (right) is not entirely conclusive in that the performance seems to degrade for a larger number of estimated eigenvalues (i.e. a low-rank approximation with a higher rank). Clearly, in theory, performance should become better with more accurate Hessian estimation, so it would be great to know why this is not the case in practice, and I would appreciate the author’s comments on this. Is this simply result of numerical instabilities when using power iteration to estimate the top eigenvalues? If so, why is this not an issue in practice, and how would we choose the optimal number of eigenvalues in practice?
- They also analyze the computational cost of the proposed method, which seems comparable to LR. It would be great to also report the computational cost of LLR and IC, which are likely much cheaper as they only require likelihood computations. Otherwise it is somewhat difficult to assess the compute-performance trade-off of the proposed approach, which is necessary to fairly compare different methods. This is the main issue that I see with the described method.
limitations_and_societal_impact: The paper describes its limitations only to some degree. As pointed out above, the computational complexity of the approach is not assessed sufficiently. Without an analysis of the compute-performance trade-off (of both this method and competing baselines), it is difficult to assess the significance of the method. Potential negative societal impact is addressed sufficiently.
review_title: null

Meta-review: The paper proposes a new method for OOD detection using deep generative models based on Bayesian hypothesis testing, that they refer to as the locally most powerful Bayesian test (LMPBT). Overall, the reviewers found the paper well-motivated and the experiments support the key claims.  During the discussion phase, reviewers ossS and 6JoX increased their score and recommended acceptance. Reviewers msUZ and Huvy leaned towards acceptance but raised some concerns in the initial review; after reading the author rebuttal, I think that the authors satisfactorily address most of these concerns. 

I recommend acceptance and encourage the authors to incorporate the reviewer feedback in the final version.

Additional comment:
While the paper shows that they outperform some existing methods such as IC, LR, LLR, I believe there are stronger published results (e.g. 
 DoSE https://arxiv.org/abs/2006.09273) that should probably be mentioned. 
Decision: Accept (Poster)