Rethinking Test-time Likelihood: The Likelihood Path Principle and Its Application to OOD Detection

I have the concern of whether the assumptions (essential separation concepts) are too strong, so that they can easily imply the theoretical guarantee. Also, I am not sure whether these "separations" are reasonable in realistic dataset.

We thank you for pointing this confusion out. We would like to invite you to Main Responses 7 and 8, and further clarify below.

[Essential separation is no stronger than prior literature]

The assumptions of essential separation and distance are no stronger than any other prior works, theoretical or empirical. To our best knowledge, Essential separation and distance strictly include “near” OOD and “far” OOD settings considered in most if not all prior literature [1, 2, 3]. If they were too strong, prior informal and rigorous attempts would all become too strong.

We remark that prior arts consider either “far OOD” (total separation) or “near OOD” (not much separation). Essential separation is separation with a specified level of probability, which incorporates both. We invite you to explore the generality of our definitions via examples from B.2 to B.5.

[Our definitions work for any any metric including realistic datasets, e.g. SVHN v.s. CIFAR10]

They are also developed for any abstract metric spaces, in theory including human-like perceptual distances (proxied by perceptual distance in [4]). Take SVHN vs. CIFAR10 as an example, they are clearly separable (no one confuses digits with cars), as a result they are by definition essentially separable.

[Our proof mainly uses VAEs’ structure, not the essential separation]

As for whether these general assumptions can imply theoretical guarantees, we invite you to check our proof in the Appendix. First, our proof mostly uses VAEs’ unique structure, not the essential separation themselves. Second, since our definitions strictly include prior ones, prior assumptions are stronger. If the proof for VAEs simply follows from the definitions, prior works would have proved similar results. To our best knowledge, ours is the first provable work in the unsupervised OOD detection setting.

The writing is unclear in the sense that some notation seems not to be defined, such as $p_{\theta}, \mu_z$ This makes me sometimes a little bit confusing.

We thank you for improving our exposition. We assume familiarity to the VAEs literature where we recall Equation 1. $p_{\theta}$ is defined there. We also assumed familiarity with the minimal sufficient statistics of VAEs on page 4, where we defined the sufficient statistics $T$ including $\mu_z$. We will make these dependencies more explicit.

[1] Zhen Fang, Yixuan Li, Jie Lu, Jiahua Dong, Bo Han, and Feng Liu. Is out-of-distribution detection learnable? Advances in Neural Information Processing Systems, 35:37199–37213, 2022.

[2] Hendrycks, Dan, and Kevin Gimpel. "A baseline for detecting misclassified and out-of-distribution examples in neural networks." arXiv preprint arXiv:1610.02136 (2016).

[3] Fort, Stanislav, Jie Ren, and Balaji Lakshminarayanan. "Exploring the limits of out-of-distribution detection." Advances in Neural Information Processing Systems 34 (2021): 7068-7081.

[4] Gatys, Leon A., Alexander S. Ecker, and Matthias Bethge. "Image style transfer using convolutional neural networks." Proceedings of the IEEE conference on computer vision and pattern recognition. 2016.

The utilization of |$\lvert \mu_{z}(x_{\text{OOD}}) - r_0 \rvert$| to approximate the distance between test and ID samples is questioned for its lack of a principled basis. If ID samples have a wide spread in in the latent space, the absence of a singular reference point makes the approximation meaningless.

Thank you for pointing this our and improving our rigor. We invite you to Main Response 8 to see our now fully rigorous justification. In particular, the aforementioned approximations, as in Equations 13 and 14, enjoy similar provable guarantees (Proposition B 16 and Corollary B 17) as Theorem 3.8. The gap between Equation 10 (main theorem) and Equations 13 +14 (experimental version) depends on empirically verifiable concentration phenomenon (discussed in Section 3.2, illustrated on Figure 2. In light of these observations, we also strengthen this concentration via regularization (Section 3.2)).

For the DC-VAEs we used, even without regularization, we empirically observe that the latent code concentrates. You are correct that when IID samples have a wide spread, our experiments without regularization showed minor performance degradation. But the unregularized model still delivers strong performances.

Theoretically, this is related to our essential definitions. Many false statements in fact are true with high probability. The widespread latent code is an example: while the latent code norm can spread a wide range, most of them are concentrated near a narrow range. In sum, widespread latent codes might weaken an absolute logical statement to a high probability one. But it does not make it meaningless. These are experimentally verified and rigorously proved (Proposition B 16 and Corollary B 17).

The reliance on VAEs' regularization of the posterior on towards a Gaussian (typically zero mean) implies the technique may not be generalizable to other generative models with distinct latent variable regularization.

You are correct that the regularization is VAEs specific, but we would like to invite you to visit Main Response 4 for why our VAEs model specific techniques are useful in the present unsupervised OOD detection we consider. The no free lunch principle, stating no single algorithm works the best in all cases, also discussed in Footnote 3, suggests dependence on VAEs can also be a strength, making our dependence on VAEs a double-edged sword. Whether it is a weakness or not highly depends on the applications of interest.

When a few current SOTA sits below AUC 0.7, we are willing to trade off generality for empirical performances. Looking at Table 1, we believe taking advantage of VAEs’ structural uniqueness is exactly why our empirical performances match or exceed SOTA benchmarks which are based on arguably more sophisticated models (Glow, DDPM, etc.). This implicitly shows our method is more sophisticated, since our model is much smaller. The sophistication probably comes from our model specific choice. For the present application (IID v.s. OOD), while the benefits of richer latent structures remain unclear (geometrically, we only need to carve the latent or visible spaces into IID v.s. OOD, it is less clear richer latent structure surely helps), our methods’ performances are demonstrated.

Moreover, as discussed previously, our performances only degraded a little without such concentration regularizations. This is because the unregularized VAEs already exhibit concentration phenomenon when VAEs have high latent dimensions, which motivates us to further strengthen it.

Complexity of implementation. While not explicitly mentioned, the introduction of new theoretical concepts might imply a more complex implementation and understanding, potentially limiting accessibility for practitioners. The author has not provided any valid implementations for reviewing.

We did not provide implementations because there is dependency on private repos. We have attached a self-contained jupyter notebook that illustrates the pipeline on synthetic datasets. We would like to emphasize that although it takes some math to derive our algorithm, its implementation is simple, similar to DoSE [1] as we mentioned in the paper.

Dependence on VAEs. The method's effectiveness may be highly dependent on the performance and tuning of the underlying VAEs, which can be sensitive to hyperparameters and data quality.

We would like to invite you to visit Main Response 4 for our choice of VAEs based algorithm, per no free lunch principle. We believe model specific OOD detection is advantageous when a few SOTA sits below AUC 0.7. The no free lunch principle is also discussed in Footnote 3, which suggests dependence on VAEs can also be a strength, making our dependence on VAEs a double-edged sword. Whether it is a weakness or not highly depends on the applications of interest.

On one hand, you are right that this dependence makes our detection algorithm less general. On the other hand, we believe taking advantage of VAEs’ structural uniqueness is exactly why our empirical performances match or exceed SOTA benchmarks which are based on arguably more sophisticated models (Glow, DDPM, etc.). This implicitly shows our method is more sophisticated, since our model is much smaller.

We note that however that the proposed LPath principle is general and orthogonal to improving VAEs. This showcases the opportunity to conduct research and improve upon the aforementioned directions independently.

Last but not the least, under practical constraints, it can be difficult to further improve the quality of many generative models (e.g. their robustness to hyperparameters, etc. See Introduction, the works of Behrmann et al., 2021; Dai et al.) in practice. When we cannot further improve the underlying model, our method can still yield significant improvement on the OOD detection performance (we performed targetted experiments to empirically verify it in Table 3, Section D.1, in Appendix). We believe this is our method’s added value and it is orthogonal to model improvements, and it is one of the main motivations behind this work.

[1] Morningstar, Warren, et al. "Density of states estimation for out of distribution detection." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

The intuition behind the theorem and the illustration in Figure 1 can be further improved. As the main figure of the paper which is introducing the idea, Figure 1 is not easy to follow. You need to read the paper all the way to the end of page 7 so you can understand the 4 cases and their connection to the idea presented in the paper.

We thank you for pointing this out. We will work on a revised figure with modified caption to better illustrate the LPath principle.

As the authors have mentioned, Equation 10 is non-trivial to compute and an approximation is provided. The effect of the error of this approximation on the performance of the algorithm can be further studied in synthetic cases.

We believe you are referring to the gap between Equation 10 and Equations 13+14. We have now provided a more detailed justification with rigorous proofs. Equation 13 and 14 now come with similar guarantees (Proposition B 16 and Corollary B 17). The gap between Equation 10 and Equations 13+14 depends on empirically verifiable concentration phenomenon (discussed in Section 3.2, illustrated on Figure 2). In light of these observations, we also strengthen this concentration via regularization (Section 3.2).

Setting the decision criteria in the proposed algorithm is non-trivial and can be further studied in the paper.

We are unsure what criteria Reviewer 6idB refers to. We believe this is related to the hyperparameters needed for the OOD decision rule, in the Question section. If we are wrong, we would like to ask for more elaborations. Note that we also discussed training and inference hyperparameters/configurations in Appendix C.3. Our neural feature extraction stage (Section 4) is quite standard, except that we tune latent dimensions (Appendix B 4.2, C.3). Our second stage statistical algorithm requires no hyperparameter.

The fact that the method outperforms other VAE baselines but doesn’t perform as well as more sophisticated baselines makes the practical usage of the method in safety critical domains less feasible.

We would like to emphasize that while we do not perform better in all cases, we surpass or match all others except SVHN (IID) vs CIFAR 10/VFlip/HFlip (OOD). Among these mostly widely used benchmarks, our method is at least as good as all others overall.

As for practical application in safety critical domains, we invite you to Main Response 2 for our advantage. In safety critical domains, theoretical guarantees are arguably more important in OOD detection, because in deployment, there is no way to control the streaming data. Offline validations such as the ones every paper performs are not guarantees to translate to the real world.

In contrast, as a provable method, even if we are not the best in the deployment environment, we can theoretically identify the factors that caused the degradation. The co-Lipschitz degrees (K, k) are the most difficult to estimate in practice, which is a separate topic itself. We now developed Lemma B.12 that suggests a way of estimating those, related to the adversarial robustness certification literature.

For the above reasons, we believe our method is more interpretable and reliable than other SOTA methods. We would like to hear from reviewer 6idB whether this discussion has addressed the aforementioned concern.

How does the approximation error of Equation 12 affect the performance?

Approximation occurs in Equation 13 and 14, where justification heuristically is provided in Footnote 10 and fully rigorously in Proposition B 16 and Corollary B 17 in the new version. They also come with provable guarantees.

The motivation behind the paired VAE idea in section 4 is unclear. The idea has been introduced in few lines and the reasoning behind it is deferred to the appendix. Can you either expand the motivation in the main text or move these few lines to the appendix?

We thank you for improving our exposition. We propose adding the following to Section 4. The idea behind VAEs pairing is that Equation 10 in Theorem 3.8 prefers smaller K, while Equation 11 prefers bigger K. These two conditions cannot be satisfied by a single VAE, but can be achieved with a paired VAEs. More details and discussion are given in the Appendix B 4.2 and B 4.3.

We appreciate your additional thoughts on the change. Any further suggestions would be welcomed.

8. [Our main theorem holds for any metric space; our approximation is now fully justified]

Theorem 3.8 in fact generalizes to all metric spaces ($L^{\infty}$ in adversarial robustness, perceptual distance in vision [6], etc.). We chose the L2 norm because of the Gaussian decoder and its accessibility. Our exposition aimed to limit the introduction of new math and hence the L2 choice. We believe our approximations of Equation 10 by Equations 13 and 14, are sufficiently intuitive, but thanks to the reviewing process, we have now made them fully rigorous with similar guarantees depending on an empirically verifiable gap. The new statements and proofs are added for all above (Theorem 3.8, Proposition B 16 and Corollary B 17).

[1] Kingma, Durk P., et al. "Semi-supervised learning with deep generative models." Advances in neural information processing systems 27 (2014).

[2] Feng, Hao-Zhe, et al. "Shot-vae: semi-supervised deep generative models with label-aware elbo approximations." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 8. 2021.

[3] Guo, Chuan, et al. "On calibration of modern neural networks." International conference on machine learning. PMLR, 2017.

[4] Minderer, Matthias, et al. "Revisiting the calibration of modern neural networks." Advances in Neural Information Processing Systems 34 (2021): 15682-15694.

[5] Zhen Fang, Yixuan Li, Jie Lu, Jiahua Dong, Bo Han, and Feng Liu. Is out-of-distribution detection learnable? Advances in Neural Information Processing Systems, 35:37199–37213, 2022.

[6] Gatys, Leon A., Alexander S. Ecker, and Matthias Bethge. "Image style transfer using convolutional neural networks." Proceedings of the IEEE conference on computer vision and pattern recognition. 2016.

[7] Hendrycks, Dan, and Kevin Gimpel. "A baseline for detecting misclassified and out-of-distribution examples in neural networks." arXiv preprint arXiv:1610.02136 (2016).

[8] Fort, Stanislav, Jie Ren, and Balaji Lakshminarayanan. "Exploring the limits of out-of-distribution detection." Advances in Neural Information Processing Systems 34 (2021): 7068-7081.