Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies out-of-distribution detection with single-layer neural networks. There are theoretical and experimental results - for theoretical contributions the authors derive the analytical form of the NML regret, and for experimental contributions the authors run their method on top of a pre-trained neural network, where they achieve superior performance in out-of-distribution data collection for the CIFAR and SVHN datasets. 
main_review: The paper is overall well written and well-motivated and the contributions are clear. 

I have some concerns with the magnitude and significance of the contributions in the paper, but of course these are my own opinions and I would like to hear the authors opinions. The "single-layer" neural network discussed in the paper is really just a softmax linear classifier/multi-class logistic regression. In terms of writing, to avoid potential confusion for readers I believe it should just be referred to by a more standard name, such as logistic regression. The application for DNNs also only applies to training the final layer, which reduces the problem to logistic regression since the static network is just a fixed feature transform, in contrast to actually training the entire network. This aspect seems slightly swept under the rug, and maybe deserves more insight into the tradeoffs in the two potential approaches. The theory presented in the paper also seem more suited to be labeled corollaries rather than substantial theoretical contributions - they involve plugging the results derived in one paper (Zhuang et. al 2020) into the definitions for logistic regression and the NML distribution. 

The experimental results seem solid, although I am not familiar with prior work in OOD detection, the metrics used, and what numbers constitute a strong result. Therefore, I will not make a strong claim in this area.

Even though the theoretical results do not hold in this case, have the authors compared fine-tuning the last layer of the neural network with NML, versus training the all layers of the network? This would also be an interesting ablation study because the full neural network would have higher regret due to the more expressive model class, and it would be interesting to see how this plays together with OOD detection. Is a more expressive class better or worse for this task?
limitations_and_societal_impact: Yes, the authors discussed several limitations and potential negative societal impacts in the conclusion.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper generalizes the *predictive normalized maximum likelihood (pNML)* learner to single-layer neural network (linear regression with softmax) and show its application to detect out of distribution test samples for neural networks. The pNML learner can output a regret value (defined with respect to the learner that knows the actual test label) for each testing sample and this regret value is used for classifying the testing samples as out-of-distribution. The proposed method achieves strong empirical performance on image recognition tasks and can be further combined with existing OOD methods. 

I find the proposed method to be novel and empirically strong. Therefore, I am leaning toward accepting. I think the authors have done a good job setting up the intuition and explaining the pNML learner. However, I wish the authors had done more analysis for the proposed method when combined with neural network.
main_review: Pros

- the proposed method is novel
- the proposed method is empirically strong
- the submission is well-written and clear
- the proposed method doesn't not introduce high computational overhead unlike methods that require retraining
- the proposed method does not require additional data

Cons/Questions

- Can the authors clarify how pNML is used together with other OOD detection methods in Table 1 and Table 2?
- Fundamentally the success of this method relies on the quality of the feature extractor. After all, a feature extractor that maps any input into the same output is hopeless for OOD detection. I think the authors should acknowledge this fact in their discussion in section 4.2
- I wonder if there are more analyses the authors can do to support their empirical evaluation. For example, qualitatively, how is this proposed method different from existing measures such as the Baseline method?
limitations_and_societal_impact: I do not see any immediate negative societal impact from this work
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper analytically derived the pNML regret for the single layer neural network, and apply it to any pre-trained NN by treating the layers as feature extractor and the last layer as a single layer NN for classification. Experimental results show that it can significantly improve the OOD detection performances of pre-trained classifiers.
main_review: The paper is well written, with a good balance between theoretical analysis and experimental evaluation. Although the analysis is a simplified version as it only considers single layer case, but it is good that the same method can be applied to any classifiers by looking at the last layer. The empirical results arecomprehensive and impressive, as it shows significant improvements over different models and datasets.

My only concern is that, it would be nicer to include experiments on larger dataset instead of only focuses on 32 resolution images. Recently, some paper on OOD detection include results on both small and large images (such as ImageNet-30 dataset, a subset of ImageNet), and this would make the results more convincing. 

In general, I think the paper is theoretically sound and the results are convicing, therefore I vote for accept.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper propose using Predictive Normalized Maximum Likelihood (pNML) as the score for deep OOD prediction. The pMNL score is derived by computing the worst-case regret with respect to a oracle under MSE loss and with the model class constrained to a single-layer NN. Authors tested the effectiveness of pNML score for OOD detection by building it on top of various other works (Baseline, ODIN, Gram, OECC), showing consistent improvement over the baseline approaches.
main_review: **Originality & Significance**:
Decent. The author derived a closed-form expression for pNML regret and empirically illustrated consistent improvement over recent approaches. The proposal appears to be simple and effective, and should be of interest to the NeurIPS community.

**Quality**: The derivation appears to be technically sound. The experiment setup used is standard among the OOD community. 

**Clarity** 
The paper is well structured and clearly written. However, the description of experiment setup can be improved. Specifically, please provide sufficient detail about how pNML is built on top of each methods (e.g., ODIN+pNML, Gram+pNML, etc). Specifically, it is not clear to me how the score for Gram+pNML is generated, since this method does not seems to modify the base architecture. If author is building on Gram method by simply computing pNML score by using the last layer of the architecture used by Gram, should the result be same as Baseline+pNML?


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper derives an explicit expression of the predictive normalized maximum likelihood (pNML) learner a single layer neural network probability assignment and regret (Eq. 7). This derived pNML regret expression is applied for the OOD detection task from pre-trained NN models. The authors also connect their pNML framework for single layer NN with soft-max activations and demonstrate that it can be applied for DNN models to obtain consistent improvements for the OOD detection performance.


----------------------
After rebuttal:- Overall, I am satisfied with the paper. I am increasing my final score to 7 for the paper.

Few additional comments:- 
"... more closely related to the domain of adversarial attacks": 
I am not sure about this comment. Typically adversarial examples deal with minor perturbations. However in this case, I was talking about "any input sample that is far away from the training distributions". I think that should be part of out-of-distribution. 

"synthetic dataset":- Please label Feature 1 and Feature 2 values in the plot.



main_review: Overall, the paper is well-written and the idea of pNML is nicely motivated. I have a few questions and suggestions as follows:

1. Related works:- 

[Line 81] Lee et al. (2018) work with pre-trained models. They do not require to retrain their model. Also, there are a number of models that explicitly retrain their OOD detection models using additional OOD training datasets (e.g. [1-4]).
In contrast, frameworks such as ODIN, Mahalanobis, etc. do not retrain the model. Instead, they fine-tune/compute some hyper-parameters during inference.
Also, some other Bayesian-NN models do not use any additional data [5-7]. Please clearly mention these related works and the differences in Section 2.


2. compute the inverse of the data matrix (Line 216):-

It seems that you need to compute the inverse of the data matrix to obtain the regret score (Eq. 20 and 21). Does it lead to a bottleneck for scalability when the training size becomes very large? Please comment.


3. "If the test sample is far from the decision boundary, the ERM assigns to one of the labels probability 1. In this case, the regret is 0 no matter in which subspace the test vector lies." (Line 195-196)

Typically, any input sample that is far away from the training distributions is expected to produce high uncertainty scores and should be detected as OOD. Such data points can be also far away from the decision boundary. For example, see Figure 1 in [7]. However, this seems to be contradicting the idea of OOD. Please comment.

(Continued from the previous question) The analysis shown in Figure 1 is useful to understand the behavior of the proposed framework.
However, according to your claim, as we move top-left or bottom-right, we should never get an OOD data point with high regret. This does not seem to be right. 

So, can you please expand the rectangular space and show the values of the regret as we move far away from the original training data points? 
Also, can you please also consider an overlapping synthetic dataset and demonstrate the regret scores? (e.g., as in [3] Figure 5).

 
[1] Deep Anomaly Detection with Outlier Exposure, ICLR 2019

[2] Predictive Uncertainty Estimation via Prior Networks, NeurIPS 2018

[3] Towards Maximizing the Representation Gap between In-Domain & Out-of-Distribution Examples, NeurIPS 2020

[4] Self-Supervised Learning for Generalizable Out-of-Distribution Detection, AAAI 2020

[5] Simple and scalable predictive uncertainty estimation using deep ensembles, NeurIPS 2017

[6] Dropout as a bayesian approximation: Representing model uncertainty in deep learning, ICML 2016

[7] Uncertainty Estimation Using a Single Deep Deterministic Neural Network, ICML 2020

limitations_and_societal_impact: I did not find any direct limitations and potential negative societal impact of this work.
review_title: null

Meta-review: The paper proposes to use predictive normalized maximum likelihood (pNML) for detecting out-of-distribution inputs.

Overall, the reviewers found it be a well-written paper. The idea of pNML for OOD detection is novel and the empirical results show consistent improvements over baseline. The authors did a good job of addressing major reviewer concerns. During the discussion phase, the consensus decision learned towards acceptance. I recommend acceptance and encourage the authors to address the remaining comments in the camera ready version.

Other suggestions to improve the final version:
- I'd encourage the authors to evaluate the technique on harder OOD pairs (e.g. https://arxiv.org/abs/2007.05566 define near-OOD pairs such as CIFAR-100 vs CIFAR-10) as it would be interesting to see how the method performs on more difficult benchmarks.
- Section 4: The idea of weighting Eigen directions with large Eigen values seems related to variants of Mahalanobis distance such as marginal Mahalanobis distance https://arxiv.org/abs/2003.00402 and Relative Mahalanobis distance https://arxiv.org/abs/2106.09022 It would be interesting to add a discussion and potentially compare pNML to these methods. 
Decision: Accept (Poster)