Single Layer Predictive Normalized Maximum Likelihood for Out-of-Distribution Detection
Year: 2022

Abstract:
Detecting out-of-distribution (OOD) samples is vital for developing machine learning based models for critical safety systems. Common approaches for OOD detection assume access to some OOD samples during training which may not be available in a real-life scenario. Instead, we utilize the predictive normalized maximum likelihood (pNML) learner, in which no assumptions are made on the tested input. We derive an explicit expression of the pNML and its generalization error, denoted as the regret, for a single layer neural network (NN). We show that this learner generalizes well when (i) the test vector resides in a subspace spanned by the eigenvectors associated with the large eigenvalues of the empirical correlation matrix of the training data, or (ii) the test sample is far from the decision boundary. Furthermore, we describe how to efficiently apply the derived pNML regret to any pretrained deep NN, by employing the explicit pNML for the last layer, followed by the softmax function. Applying the derived regret to deep NN requires neither additional tunable parameters nor extra data. We extensively evaluate our approach on 74 OOD detection benchmarks using DenseNet-100, ResNet-34, and WideResNet40 models trained with CIFAR-100, CIFAR-10, SVHN, and ImageNet-30 showing a significant improvement of up to 15.6% over recent leading methods.

heading: 1 Introduction
text: An important concern that limits the adoption of deep neural networks (DNN) in critical safety systems is how to assess our confidence in their predictions, i.e, quantifying their generalization capability (Kaufman et al., 2019; Willers et al., 2020). Take, for instance, a machine learning model for medical diagnosis (Bibas et al., 2021). It may produce (wrong) diagnoses in the presence of test inputs that are different from the training set rather than flagging them for human intervention (Singh et al., 2021). Detecting such unexpected inputs had been formulated as the out-of-distribution (OOD) detection task (Hendrycks and Gimpel, 2017), as flagging test inputs that lie outside the training classes, i.e., are not in-distribution (IND).
Previous learning methods that designed to offer such generalization measures, include VCdimension (Zhong et al., 2017; Vapnik and Chervonenkis, 2015) and norm based bounds (Neyshabur et al., 2018; Bartlett et al., 2017). As a whole, these methods characterized the generalization ability based on the properties of the parameters. However, they do not consider the test sample that is presented to the model (Jiang et al., 2020), which makes them useless for OOD detection. Other approaches build heuristics over the empirical risk minimization (ERM) learner, by post-processing
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
the model output (Sastry and Oore, 2020) or modifying the training process (Papadopoulos et al., 2021; Vyas et al., 2018). Regardless of the approach, these methods choose the learner that minimizes the loss over the training set. This may lead to a large generalization error because the ERM estimate may be wrong on unexpected inputs; especially with large models such as DNN (Belkin et al., 2019).
To produce a useful generalization measure, we exploit the individual setting framework (Merhav and Feder, 1998). In the individual setting, there is no assumption about how the training and the test data are generated, nor about their probabilistic relationship. Moreover, the relationship between the labels and data can be deterministic and may therefore be determined by an adversary. The generalization error in this setting is often referred to as the regret (Merhav and Feder, 1998). This regret is defined by the log-loss difference between a learner and the genie: a learner that knows the specific test label, yet is constrained to use an explanation from a set of possible models. The individual setting is the most general framework and so the result holds for a wide range of scenarios. Specifically, the result holds to OOD detection where the distribution of the OOD inputs is unknown.
The pNML learner (Fogel and Feder, 2018) was proposed as the min-max solution of the regret, where the minimum is over the learner choice and the maximum is for any possible test label value. Intuitively, the pNML assigns a probability for a potential outcome as follows: Add the test sample to the training set with an arbitrary label, find the ERM solution of this new set, and take the probability it gives to the assumed label. Follow this procedure for every label and normalize to get a valid probability assignment. The pNML was developed before for linear regression (Bibas et al., 2019b) and was evaluated empirically for DNN (Fu and Levine, 2021; Bibas et al., 2019a).
We derive an analytical solution of the pNML learner and its generalization error (the regret) for a single layer NN. We analyze the derived regret and show it obtains low values when the test input either (i) lies in a subspace spanned by the eigenvectors associated with the large eigenvalues of the training data empirical correlation matrix or (ii) is located far from the decision boundary. Crucially, although our analysis focuses on a single layer NN, our results are applicable to the last layer of DNNs without changing the network architecture or the training process: We treat the pretrained DNN as a feature extractor with the last layer as a single layer NN classifier. We can therefore show the usage of the pNML regret as a confidence score for the OOD detection task.
To summarize, we make the following contributions.
1. Analytical derivation of the pNML regret. We derive an analytical expression of the pNML regret, which is associated with the generalization error, for a single layer NN.
2. Analyzing the pNML regret. We explore the pNML regret characteristics as a function of the test sample data, training data, and the corresponding ERM prediction. We provide a visualization on low dimensional data and demonstrate the situations in which the pNML regret is low and the prediction can be trusted.
3. DNN adaptation. We propose an adaptation of the derived pNML regret to any pretrained DNN that uses the softmax function with neither additional parameters nor extra data.
Applying our pNML regret to a pretrained DNN does not require additional data, it is efficient and can be easily implemented. The derived regret is theoretically justified for OOD detection since it is the individual setting solution for which we do not require any knowledge on the test input distribution. Our evaluation includes 74 IND-OOD detection benchmarks using DenseNet-BC-100, ResNet-34, and WideResNet-40 trained with CIFAR-100, CIFAR-10, SVHN, and ImageNet-30. Our approach outperforms leading methods in nearly all 74 OOD detection benchmarks up to a remarkable +15.2%

heading: 2 Related work
text: OOD detection. Many recent work use additional OOD set in training (Malinin and Gales, 2018; Hendrycks et al., 2019a; Nandy et al., 2020; Mohseni et al., 2020). A well-known method for OOD detection, named ODIN (Liang et al., 2018), manipulates the input image based on the gradient of the loss function. This input manipulation increases the margin between the maximum probability of images with known classes and images with unknown objects. However, the manipulation strength is defined by OOD data, which might be unavailable or different from the OOD samples in inference.
Different approaches propose to manipulate the loss function in the training phase. Lee et al. (2018) proposed to use the Mahalanobis distance between the test input representations and the class conditional distribution in the intermediate layers to train a logistic regression classifier to determine if the input sample is OOD. The Energy method (Liu et al., 2020) adds a cost function to the training phase to shape the energy surface explicitly for OOD detection. Papadopoulos et al. (2021) suggested the outlier exposure with confidence control (OECC) method in which a regularization term is added to the loss function such that the model produces a uniform distribution for OOD samples.
All mentioned methods require manipulating the DNN architecture or adding additional data. The Baseline method (Hendrycks and Gimpel, 2017) is one of the earliest approaches designed to identify whether a test input is IND and does not require changing the pretrained model. This method uses the maximum probability of the DNN output as the OOD score. The Gram method (Sastry and Oore, 2020) detects OODs based on feature representations obtained in intermediate layers. Given a test sample, the Gram matrices of the test sample features are compared with those of the training samples known to belong to the estimated class of the test sample. However, this method requires IND validation set and does not have a theoretical motivation.
Other work suggested using Bayesian techniques to estimate the prediction confidence (Gal and Ghahramani, 2016; Lakshminarayanan et al., 2017; van Amersfoort et al., 2020). However, the Bayesian techniques add extensive compute overhead to the prediction.
The pNML learner. The pNML learner is the min-max solution of the supervised batch learning in the individual setting (Fogel and Feder, 2018). For sequential prediction it is termed the conditional normalized maximum likelihood (Rissanen and Roos, 2007; Roos and Rissanen, 2008).
Several methods deal with obtaining the pNML learner for different hypothesis sets. Bibas et al. (2019b) and Bibas and Feder (2021) showed the pNML solution for linear regression. Rosas et al. (2020) proposed an NML based decision strategy for supervised classification problems and showed it attains heuristic PAC learning. Fu and Levine (2021) used the pNML for model optimization based on learning a density function by discretizing the space and fitting a distinct model for each value.
For the DNN hypothesis set, Bibas et al. (2019a) estimated the pNML distribution with DNN by fine-tuning the last layers of the network for every test input and label combination. This approach is computationally expensive since training is needed for every test input. Zhou and Levine (2020) suggested a way to accelerate the pNML computation in DNN by using approximate Bayesian inference techniques to produce a tractable approximation to the pNML. Pesso et al. (2021) used the pNML with adversarial target attack as a defense mechanism against adversarial perturbation.

heading: 3 Notation and preliminaries
text: In the supervised machine learning scenario, a training set consisting of N pairs of examples is given
DN = {(xn, yn)}Nn=1, xn ∈ X , yn ∈ Y, (1) where xn is the n-th data instance and yn is its corresponding label. The goal of a learner is to predict the unknown test label y given a new test data x by assigning probability distribution q(·|x) to the unknown label. The performance is evaluated using the log-loss function
`(q;x, y) = − log q(y|x). (2)
For the problem to be well-posed, we must make further assumptions on the class of possible models or hypothesis set that is used to find the relation between x and y. Denote Θ as a general index set, this class is a set of conditional probability distributions
PΘ = {pθ(y|x), θ ∈ Θ}. (3) The ERM is the learner from the hypothesis set that attains the minimal log-loss on the training set.
The individual setting. An additional assumption required to solve the problem is related to how the data and the labels are generated. In this work we consider the individual setting (Merhav and Feder, 1998; Fogel and Feder, 2018; Bibas et al., 2019b,a), where the data and labels, both in the training and test, are specific individual quantities: We do not assume any probabilistic relationship between them, the labels may even be assigned in an adversarial manner.
The genie. In the individual setting the goal is to compete with a reference learner, a genie, that has to following properties: (i) knows the test label value, (ii) is restricted to use a model from the given hypotheses set PΘ, and (iii) does not know which of the samples is the test. This reference learner then chooses a model that attains the minimum loss over the training set and the test sample
θ̂(DN ;x, y) = arg min θ∈Θ
[ ` (pθ;x, y) +
N∑ n=1 ` (pθ;xn, yn)
] . (4)
The regret is the log-loss difference between a learner q and this genie: R(q;DN ;x, y) = − log q(y|x)− [ − log pθ̂(DN ;x,y)(y|x) ] . (5)
Theorem 1 (Fogel and Feder (2018)). The universal learner, denoted as the pNML, minimizes the regret for the worst case test label
Γ = R∗(DN , x) = min q max y∈Y R(q;DN ;x, y). (6)
The pNML probability assignment and regret are
qpNML(y|x) = pθ̂(DN ;x,y)(y|x)∑
y′∈Y pθ̂(DN ;x,y′)(y ′|x) , Γ = log ∑ y′∈Y pθ̂(DN ;x,y′)(y ′|x). (7)
Proof. The regret is equal for all choices of y. If we consider a different probability assignment, it should assign a smaller probability for at least one of the outcomes. If the true label is one of those outcomes it will lead to a higher regret. For more information see Fogel and Feder (2018).
The pNML regret is associated with the model complexity (Zhang, 2012). This complexity measure formalizes the intuition that a model that fits almost every data pattern very well would be much more complex than a model that provides a relatively good fit to a small set of data. Thus, the pNML incorporates a trade-off between goodness of fit and model complexity as measured by the regret.
Online update of a neural network. Let XN and YN be the data and label matrices of N training points respectively
XN = [x1 x2 . . . xN ] > ∈ RN×M , YN = [y1 y2 . . . yN ] > ∈ RN×C , (8)
such that the number of input features and model outputs are M and C respectively. Denote X+N as the Moore–Penrose inverse of the data matrix
X+N =
{ (X>NXN ) −1X>N Rank(X > NXN ) = M
X>N (XNX > N ) −1 otherwise,
(9)
f(·) and f−1(·) as the activation and inverse activation functions, and θ ∈ RM×C as the learnable parameters. The ERM, that minimizes the training set mean squared error (MSE), is
θ̂N = X + Nf −1(YN ) = arg min θ ||YN − f(XNθ)||22. (10)
Recently, Zhuang et al. (2020) suggested a recursive formulation of the DNN weights. Using their scheme only one training sample is processed at a time: Denote the projection of a sample x onto the orthogonal subspace of the training set correlation matrix as
x⊥ = ( I −X+NXN ) x, (11)
the update rule when receiving a new training sample with data x with label y is
θ̂(DN ;x, y) = θ̂N + g ( f−1(y)− x>θ̂N ) , g ,
{ 1
‖x⊥‖2 x⊥ x⊥ 6= 0 1 1+x>X+NX +> N x X+NX +> N x, x⊥ = 0 . (12)
In their paper, Zhuang et al. (2020) applied this formulation for a DNN, layer by layer.

heading: 4 The pNML for a single layer NN
text: Intuitively, the pNML as stated in (7) can be described as follows: To assign a probability for a potential outcome, (i) add it to the training set with an arbitrary label, (ii) find the best-suited model, and (iii) take the probability it gives to the assumed label. Follow this procedure for every label and normalize to get a valid probability assignment. Use the log normalization factor as the confidence measure. This method can be extended to any general learning procedure that generates a prediction based on a training set. One such method is a single layer NN.
A single layer NN maps an input x ∈ RM×1 using the softmax function to a probability vector which represents the probability assignment to one of C classes
pθ(i|x) = f(x>θ)i = eθ > i x∑C
j=1 e θ>j x
, i ∈ {1, . . . , C}. (13)
To align with the recursive formulation of (12), the label y is a one-hot vector with C elements and is represented by a row vector in the standard base {ei}Ci=1 (the i-th element is 1 and all others are 0). c stands for the true test label such that ec is the one-hot vector of the true label. Also, the learnable parameters {θi}Ci=1 are the columns of the parameter matrix of (10). We would like that the probability assignment of the true label to be 1. We define the following MSE minimization objective
min θ∈Θ N∑ n=1 ( 1− ynf ( θ>xn ))2 . (14)
Minimizing this MSE objective is equivalent to constrain the genie to the following Gaussian family
PΘ = { pθ(y|x) =
1√ 2πσ2 exp
{ − 1 2σ2 ( ec ( y − f(x>θ) ))2} , θ ∈ RM×C } (15)
and minimizing the log loss with respect to it. More details are in appendix A. The inverse of the activation function is
z , f−1 (pθ (i|x)) = ln pθ (i|x) + ln C∑ j=1 eθ > j x. (16)
To compute the genie, we assume that the label of the test sample is known and add it to the training set. We fit the model by optimizing the learnable parameters to minimize the loss of this new set. Lemma 1. Given test data x with label y = ec, the genie prediction of the true label is
pθ̂(DN ;x,y=ec)(c|x) = pc
pc + p x>g c (1− pc)
, (17)
where pc is the probability assignment of the ERM model of the label c, and g is as defined in (12).
Proof. Using (12), the probability assignment of the genie can be written as follows.
pθ̂(DN ;x,y=ec)(c|x) = eθ̂(DN ;x,y=ec) >x∑C j=1 j 6=c eθ > j x + eθ̂(DN ;x,y=ec)>x = ex >[θc+g(z−θ>c x)]∑C j=1 e θ>j x − eθ>c x + ex>[θc+g(z−θ>c x)] .
(18) The genie knows the true test label ec. The inverse activation function can be written as z = lnS where S , ∑C j=1 e θ>j x. The simplified numerator is
eθ > c xex >g(z−θ>c x) = eθ > c x [ Se−θ > c x ]x>g = Sp−x >g
c pc. (19)
Substituting to (18) and divide the numerator and denominator by S provides the result.
The true test label is not available to a legit learner. Therefore, in the pNML process, every possible label is taken into account. The pNML regret is the logarithm of the sum of models’ prediction, each one trained with a different test label value.
Theorem 2. Denote pi as the ERM prediction of label i, the pNML regret of a single layer NN is
Γ = log C∑ i=1
pi
pi + p x>g i (1− pi)
. (20)
Proof. The normalization factor is the sum of the probabilities assignment of models that were trained with a specific value of the test sample K = ∑C i=1 pθ̂(DN ;x,y=ei)(i|x). Using Theorem 1, the log normalization factor is the pNML regret. With lemma 1, we get the explicit expression.
The pNML probability assignment of label i ∈ {1, . . . , C} is the probability assignment of a model that was trained with that label divided by the normalization factor qpNML(i|x) = 1K pθ̂(DN ;x,y)(y|x).
Let um and hm be the m-th eigenvector and eigenvalue of the training set data matrix XN such that for x⊥ = 0, the quantity x>g is
x>g = x>X+NX +> N x
1 + x>X+NX +> N x
=
1 N ∑M m=1 1 h2m ( x>um )2 1 + 1N ∑M i=1 1 h2m (x>um) 2 . (21)
We make the following remarks.
1. If the test sample x lies in the subspace spanned by the eigenvectors with large eigenvalues, x>g is small and the corresponding regret is low limx>g−→0 Γ = log ∑C i=1 pi = 0. In this
case, the pNML prediction is similar to the genie and can be trusted.
2. Test input that resides is in the subspace that corresponds to the small eigenvalues produces x>g = 1 and a large regret is obtained limx>g−→1 Γ = log ∑C i=1
1 2−p2i . The prediction for this test sample cannot be trusted. In section 5 we show that in this situation the test sample can be classified as an OOD sample.
3. As the training set size (N ) increases x>g becomes smaller and the regret decreases.
4. 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.

heading: 4.1 The pNML regret characteristics using a low-dimensional dataset
text: We demonstrate the characteristics of the derived regret and show in what situations the prediction of the test sample can be trusted. To visualize the pNML regret on a low-dimensional dataset, we use the Iris flower data set (Fisher, 1936). We utilize two classes and two features and name them c1, c2, and feature 1, feature 2 respectively.
Figure 1a shows the ERM probability assignment of class c2 for a single layer NN that was fitted to the training data, which are marked in red. At the top left and bottom right, the model predicts with high probability that a sample from these areas belongs to class c1 and c2 respectively.
Figure 1b presents the analytical pNML regret. At the upper left and lower right, the regret is low: Although there are no training samples there, these regions are far from the decision boundary, adding one sample would not alter the probability assignment significantly, thus the pNML prediction is close to the genie. At the top right and bottom left, there are no training points therefore the regret is relatively high and the confidence in the prediction is low. In section 5, we show that these test samples, which are associated with high regret, can be classified as OOD samples.
In addition, we visualize the regret for overlapping classes. In figure 1c, the ERM probability assignment for inseparable class split is shown. The ERM probability is lower than 0.7 for all test feature values. Figure 1d presents the corresponding pNML regret. The pNML regret is small in the training data surroundings (including the mixed label area). The regret is large in areas where the training data is absent, as in the figure edges.

heading: 4.2 Deep neural network adaptation
text: In previous sections, we derived the pNML for a single layer NN. We next show that our derivations can, in fact, be applied to any pretrained NN, without requiring additional parameters or extra data.
First extract the embeddings of the training set: Denote φ(·) as the embedding creation (feature extraction) using a pretrained ERM model, propagate the training samples through the DNN up to the last layer and compute the inverse of the data matrix φ(XN )+φ(XN )+>. Then, given a specific test example x, extract its embedding φ(x) and its ERM probability assignment {pi}Ci=1. Finally calculate the regret as described in Theorem 1 using the training set and test embedding vectors.
We empirically found that norms of OOD embeddings are lower than those of IND samples. The regret depends on the norm of the test sample: For 0 < a < b, the regret of ax is lower than the regret of bx. Hence, we normalize all embeddings (training, IND, and OOD) to have L2 norms equal to 1.0.
Samples with a high regret value are considered samples with a large distance from the genie, the learner that knows the true label, and therefore the prediction cannot be trusted. Our proposed method utilizes this regret value to determine whether a test data item represents a known or an unknown.

heading: 5 Application to out-of-distribution detection
text: We rigorously test the effectiveness of the pNML regret for OOD detection1. The motivation for using the individual setting and the pNML as its solution for OOD detection is that in the individual setting there is no assumption on the way the data is generated. The absence of assumption means that the result holds for a wide range of scenarios (PAC, stochastic, and even adversary) and specifically to OOD detection, where the OOD samples are drawn from an unknown distribution.
1Code is available in https://github.com/kobybibas/pnml_ood_detection

heading: 5.1 Experimental setup
text: We follow the standard experimental setup (Liu et al., 2020; Sastry and Oore, 2020; Lee et al., 2018). All the assets we used are open-sourced with either Apache-2.0 License or AttributionNonCommercial 4.0 International licenses. We ran all experiments on NVIDIA K80 GPU.
IND sets. For datasets that represent known classes, we use CIFAR-100, CIFAR-10 (Krizhevsky et al., 2014) and SVHN (Netzer et al., 2011). These sets contain RGB images with 32x32 pixels. In addition, to evaluate higher resolution images, we use ImageNet-30 set (Hendrycks et al., 2019b).
OOD sets. The OOD sets are represented by TinyImageNet (Liang et al., 2018), LSUN (Yu et al., 2015), iSUN (Xu et al., 2015), Uniform noise images, and Gaussian noise images. We use two variants of TinyImageNet and LSUN sets: a 32x32 image crop that is represented by “(C)” and a resizing of the images to 32x32 pixels that termed by “(R)”. We also used CIFAR-100, CIFAR-10, and SVHN as OOD for models that were not trained with them.
Evaluation methodology. We benchmark our approach by adopting the following metrics (Sastry and Oore, 2020; Lee et al., 2018): (i) AUROC: The area under the receiver operating characteristic curve of a threshold-based detector. A perfect detector corresponds to an AUROC score of 100%. (ii) TNR at 95% TPR: The probability that an OOD sample is correctly identified (classified as negative) when the true positive rate equals 95%. (iii) Detection accuracy: Measures the maximum possible classification accuracy over all possible thresholds.

heading: 5.2 Results
text: We build upon the existing leading methods: Baseline (Hendrycks and Gimpel, 2017), ODIN (Liang et al., 2018), Gram (Sastry and Oore, 2020), OECC (Papadopoulos et al., 2021), and Energy (Liu et al., 2020). We use the following pretrained models: ResNet-34 (He et al., 2016), DenseNet-BC-
100 (Huang et al., 2017) and WideResNet-40 (Zagoruyko and Komodakis, 2016). Training was performed using CIFAR-100, CIFAR-10 and SVHN, each training set used separately to provide a complete picture of our proposed method’s capabilities. Notice that ODIN, OECC, and Energy methods use OOD sets during training and the Gram method requires IND validation samples.
Table 1 and Table 2 show the AUROC of different OOD sets for DenseNet and ResNet models respectively. Our approach improves all the compared methods in nearly all combinations of INDOOD sets. The largest AUROC gain over the current state-of-the-art is of CIFAR-100 as IND and LSUN (C) as OOD: For the DenseNet model, we improve Gram and OECC method by 3.1% and 2.2% respectively. For the ResNet model, we improve this combination by 2.4% and 2.1% respectively. The additional metrics (TNR at 95% FPR and detection accuracy) are shown in appendix E.
The Baseline method uses a pretrained ERM model with no extra data. Combining the pNML regret with the standard ERM model as shown in the Baseline+pNML column surpasses Baseline by up to 69.4% and 41.5% for DensNet and ResNet, respectively. Also, Baseline+pNML is comparable to the more sophisticated methods: Although it lacks tunable parameters and does not use extra data, Baseline+pNML outperforms ODIN in most DenseNet IND-OOD set combinations.
Table 3 shows the results of the Energy method and our method when combined with the pretrained Energy model (Energy+pNML) with WideResNet-40 model on CIFAR-100 and CIFAR-10 as IND sets. Evidently, our method improves the AUROC of the OOD detection task in 14 out of 16 INDOOD combinations. The most significant improvement is in CIFAR-100 as IND and ImageNet (R) and iSUN as the OOD sets. In these sets, we improve the AUROC by 15.6% and 15.2% respectively. For TNR at TPR 95%, the pNML regret enhances the CIFAR-100 and Gaussian combination by 90.4% and achieves a perfect separation of IND-OOD samples.
For high resolution images, we use Resnet-18 and ResNet-101 models trained on ImageNet. We utilize the ImageNet-30 training set for computing φ(XN )+φ(XN )+>. All images were resized to 254× 254 pixels. We compare the result to the Baseline method in Table 4. The table shows that the pNML outperforms Baseline by up to 9.8% and 8.23% for ResNet-18 and ResNet-101 respectively.

heading: 6 Conclusions
text: We derived the analytical expression of the pNML regret for a single layer NN. We showed that the model generalizes well when the test data resides in either a subspace spanned by the eigenvectors associated with the large eigenvalues of the training data correlation matrix or far from the decision boundary. We showed how to apply the pNML for any pretrained DNN that uses the softmax layer with neither additional parameters nor extra data. We demonstrated the effectiveness of our pNML regret–based approach on 74 IND-OOD detection benchmarks. Compared with the recent state of the art methods, our approach elevates absolute AUROC values by up to 15.6%
For future work, in our regret derivation we constrained the genie hypothesis set to the Gaussian family and a single layer NN. We would like to extend the derivation to larger hypothesis sets and more layers, believing it would improve performance. Furthermore, the pNML regret can be used for additional tasks such as active learning, probability calibration, and adversarial attack detection.
Societal impacts. The negative social impact of this work depends on the application. For instance, in a surveillance camera scenario, a person from a minority group can be flagged as OOD if the minority group was not included in the training set. We recommend that when OOD is flagged a human will intervene rather than an algorithmic response since the nature of the OOD is unknown.

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

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.

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.