Distribution Shift Detection for Deep Neural Networks
Authors: Guy Bar-Shalom
Yonatan Geifman
Ran El-Yaniv
Venue: Submitted to ICLR 2023 (2023)
Keywords: Selective classification
Window based shift detection

Abstract: To deploy and operate deep neural models in production, the quality of their predictions, which might be contaminated benignly or manipulated maliciously by input distributional deviations, must be monitored and assessed. Specifically, we study the case of monitoring the healthy operation of a deep neural network (DNN) receiving a stream of data, with the aim of detecting input distributional deviations over which the quality of the network's predictions is potentially damaged. Using selective prediction principles, we propose a distribution deviation detection method for DNNs. The proposed method is derived from a tight coverage generalization bound computed over a sample of instances drawn from the true underlying distribution. Based on this bound, our detector continuously monitors the operation of the network over a test window and fires off an alarm whenever a deviation is detected. This novel detection method consistently and significantly outperforms the state of the art with respect to the CIFAR-10 and ImageNet datasets, thus establishing a new performance bar for this task, while being substantially more efficient in time and space complexities.

Under review as a conference paper at ICLR 2023
WINDOW-BASED DISTRIBUTION SHIFT DETECTION FOR DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
To deploy and operate deep neural models in production, the quality of their pre- dictions, which might be contaminated benignly or manipulated maliciously by input distributional deviations, must be monitored and assessed. Specifically, we study the case of monitoring the healthy operation of a deep neural network (DNN) receiving stream of data, with the aim of detecting input distributional deviations over which the quality of the network's 's predictions is potentially damaged. Us- ing selective prediction principles, we propose distribution deviation detection method for DNNs. The proposed method is derived from tight coverage general- ization bound computed over sample of instances drawn from the true underlying distribution. Based on this bound, our detector continuously monitors the operation the network over a test window and fires off an alarm whenever a deviation is detected. This novel detection method consistently and significantly outperforms the state of the art with respect to the CIFAR-10 and ImageNet datasets, thus establishing new performance bar for this task, while being substantially more efficient time and space complexities.
INTRODUCTION
wide range of artificial intelligence applications and services rely on deep neural models because of their remarkable accuracy. When trained model is deployed in production, its operation should be monitored for abnormal behavior, and a flag should be raised if such detected. Corrective measures can be taken if the underlying cause of the abnormal behavior is identified. For example, simple distributional changes may only require retraining with fresh data, while more severe cases may require redesigning the model (e.g., when new classes emerge).
In this paper we focus on distribution shift detection the context of deep neural models and consider the following setting. Pretrained model is given, and we presume it was trained with data sampled from some distribution P. addition to the dataset used in training f. we are also given an additional sample of data from P. which is used to train a detector D (we refer to this as the detection detection-trainingg dataset). While ff is used in production to process a stream of emerging input data, we continually feed 1 with the most recent window Wt of l input elements. The detector also has access to the final layers of the model f and should be able to determine whether the data contained in W came from distribution different from P. Detection algorithms based on a window, such as we consider here, have rarely been considered in the context of deep neural networks. To the best of our knowledge window-based deep detection has only been considered by (Rabanser al. 2019). We emphasize that in this paper we are not considering the problem of identifying single- inngle-instance nnttoo-ddisrrbbution or outlier instances (Liang al.. 2018 Hendrycks Gimpel 2017; Hendrycks
let al. 2019; Golan & Yania 2018 Ren et al.] 2019 Nalisnick et al.] 2019 Nado et al.) 1 Fort et al. 2) but rather the information residing in a population of is instances. Single-instance methods trivially applicable to window. However, these methods
not designed to detect
population-bai bassattiioo---dddddded changes (see discussion in Section 2 We also note that this paper does not address the issue of characterizing the type of distribution shift, nor correcting it (by "redesigning" the model to make accurate predictions on the shifted distribution).
The detection of distribution shifts is fundamental topic in machine learning and statistics. and the standard method for tackling it is by performing a dimensionality reduction over both the detection- training (source) and test (target) samples, and then applying two-sample statistical test over these

---

Under review as a conference paper at ICLR 2023
reduced representations to detect deviation. This is further discussed in Section Distribution shift detection has been scarcely considered in the context of deep neural networks (DNNs). Deep models can benefit from the semantic representation created by the model itself, which provides meaningful dimensionality reduction that is readily available at the last layers of the model. Using the embedding layer (or softmax) along with statistical two-sample tests was recently proposed by (Lipoon et al., 2018) and (Rabanser et al. 2019)) who termed solutions of this structure black-box shift detection (BBSD). Using both the univariate Solmogorov-Smirno (KS) test and the maximum mean discrepancy (MMD) method, see details below. (Rabanser et al., 2019) achieve impressive detection results when using MNIST and CIFAR-10 as proxies for the distribution P. As we demonstrate here, the KS-BBSD method is also very effective over ImageNet when a stronger model used (EfficientNet vs ResNet-18). BBSD methods have the disadvantage of being computationally intensive due to the use of two-sample tests between the detection ceaeccioonntriningg set (which can, and are preferred to be the largest possible) and the window W (a complexity analysis is provided in table D
We propose different approach based on selective prediction (EI- Yaniv& & Wiener 2010 Geifiaan & El-Yaniv 2017), where a model quantifies its prediction uncertainty and abstains from predicting uncertain instances. First, we develop method for selective prediction with guaranteed coverage. This method identifies the best abstaining threshold and coverage bound for a given pretrained classifier f. such that the resulting empirical coverage will not violate the bound with high probability (when abstention is determined using the threshold). The guaranteed coverage method of independent interest, and it is analogous to selective prediction with guaranteed risk (Geiffman & El- Eal-Yaniv, |217) Because the empirical coverage of such a classifier is highly unlikely to violate the bound if the underlying distribution remains the same, systematic violation indicates a shift in distribution. To be more specific, given a detection- traininngt sample Sm. our coverage- based detection algorithm computes log, m tight generalization coverage bounds, which are then used to detect a distribution shift in window W of test data. Due to its aggressive reduction of Sm to O(log m) numbers, the proposed detection algorithm is extremely efficient its computation requirements, unlike the baseline algorithms mentioned above, which follow the framework depicted in Figure B in Appendix 7. For example, consider the JFT-3B dataset (Zhai et al. 2021). Previous methods that require the processing of this set for each incoming window are infeasible, while our method allows one to summarize it with only 32 scalars.
In comprehensive empirical study, we compared our coverage- based detection algorithm with the best-performing BBSD baselines, including the KS approach of (Rabanser et al. 2019)) All methods used the same underlying models (ResNet-18. ResNet-50 and EfficientNet) for fair comparison. We simulated source distributions using both the CIFAR-10 10 and ImageNet databases. Distribution shifts were produced using various methods, beginning with simple noise and ending with adversarial examples. Based on these experiments, we can claim that our coverage- based detection method is significantly more powerful than the baselines across a wide range of test window sizes.
To summarize, the contributions of this paper are: (1) A theoretically justified algorithm (Algorithm D that produces a coverage bound, which of independent interest, and allows for the creation of selective classifiers with guaranteed coverage. (2) A theoretically motivated "windowed" detection algorithm (Algorithm 2). which detects a distribution shift over a window, (3) comprehensive empirical study demonstrating significant improvements relative to existing baselines over a variety of datasets and architectures.
2 RELATED WORK
Distribution shift detection methods often comprise the following two steps: dimensionality reduction, and two-sample test between the detection detection-training sample and test samples. In most cases, these methods are "lazy" in the sense that for each test sample, they make a detection decision based on a computation over the entire detection-training sample. Their performance will be sub-optimal if only a subset of the train sample used. Figure 3 in Appendix 7.1 illustrates this general framework.
The use of dimensionality reduction is optional. It can often improve performance by focusing on a less noisy representation of the data. Dimensionality reduction techniques include no reduction, principal components analysis (Wold et al. 1987). sparse random projection (Bingham & Mannilal 2001), autoencoders (Rumelhart et al. 1985; Pu et al. 2016), domain classifiers, (Rabanser et al. 2019) and more. In this work we focus black box shift detection (BBSD) methods (Lipton ct al., 2018), that rely on deep neural representations of the data generated by a pretrained model. The representation extract from the model will typically utilize either the softmax outputs
2

---

Under review as a conference paper at ICLR 2023
(acronymed BBSD-S) the embeddings (acronymed BBSD-E). Due to the dimensionality of the final representation. multivariate or multiple univariate two-sample tests can be conducted.
By combining BBSD-S with a Kolmogorov- -omiinonooo (KS) statistical test (Massey Jr 1951) and using the Bonferroni correction (Bland & Aliman 1995), (Rabanser et al.) 2019) achieved state-of- state-of-the-art results in distribution shift detection in the context of image classification (MNIST and CIFAR-10). We acronym their method as KS-BBSD-S. The univariate KS test processes individual dimensions separately; its statistic is calculated by computing the largest difference Z of the cumulative density functions (CDFs) across all dimensions as follows: Z = supl Fp(z)= =)= (2)2)), where Fo and Fp
the empirical CDFs of the detection-training and test data (which sampled from P and Q, respectively; see Section 3). The Bonferroni correction rejects the null hypothesis when the minimal p-value among all tests is less than a. where a is the significance level of the test, and d is the number of dimensions. Although there have been several less conservative approaches to aggregation (Heard & Subbin-Delanchy 2018 Loughin 2004), they usually assume some dependencies among the tests.
The maximum mean discrepancy (MMD) method (Gretton et al. 2012) is kernel-basee multi- variate test that can be used to distinguish between probability distributions and Q. Formally, ( (F, P. P)))== I| - #qq 11 where μp and μo are the mean embeddings of P and Q in a reproducing kernel Hilbert space F. Given a kernel K., and samples, {01, Ø2, -. ~ pm and {a x2y .....
..)) x Q², an unbiased estimator for MM D can be found in (Gretton et al.
2012, Serfling 2009). (Sutherland et al.) (017)) and (Gretton et al., 2012) used the RBF kernel <'(x,=')) e zez
where 2a² is set to the median of the pairwise Euclidean distances between all samples. By performing a permutation test on the kernel matrix, the p-value is ob- tained. In our experiments (see Section 5 we thus use four baselines: KS-BBSD-S, KS-BBSD-E, MMD-BBSD-S, S, and MMD-BBSID-E.
As mentioned in the introduction, our work is complementary to the topic of single-instane out- of-distribution (OOD) detection (Liang et al. (0.8) Hendrycks & Gimpel| [2017] Hendryykk et al.)
2019
Golan & Yaniv 2018, Ren al. [2099] Nalisnick al. [219 [ado et al. [2021] Fort et al.
2021 Obviously, these methods can be applied in a trivial manner over a window, by applying the
detector to each instance in the given window. However, these methods typically do not consider the population statistics over the window. Interestingly, we demonstrate in Section 5. Figure 2 that near perfect performance can be achieved by (our) window-based detection when the window is sufficiently large. For instance, a detection AUROC score close to 100% can be obtained over a 1K window when considering various distributional changes such as adversarial attacks, Gaussian noise, and more. OOD detection methods rarely achieve such near-perfect AUROC score when considering such distributional changes.
Finally, we mention (Geifman & EI- Yaniv 2017) who developed risk generalization bound for selective classifiers (El- Yaniv & Wiener 2010). The bound presented in that paper is analogous to the coverage generalization bound present in Theorem 4.2) The risk bound in (Geifman & El- El-yaniv 2017) can also be used for shift-detection. To apply their risk bound to this task, however, labels, which are not available, are required. Our method (Section 4 detects distribution shifts without using any labels.
PROBLEM FORMULATION
We consider the problem of detecting distribution shifts in input streams provided to pretrained deep neural models. Let P & Px denote a probability distribution over an input space X, and assume that a model f has been trained on set of instances drawn from P. Samples drawn from P are referred as in-distribution (ID), or detection-truining data, Consider a setting where the model f is deployed and while being used in production its input distribution might change or even be attacked by an adversary. Our goal is to detect such events to allow for appropriate action, e.g., retraining the model with respect to the revised distribution.
Inspired by RRabanser et al. 2019), we formulate this problem as follows. We are given a pretrained model f (whose ID training data was sampled from P). Then having f and additional ID detection- training data S,, ~ pm (possibly unlabeled), we would like to train a detection model to be able to detect distribution shift; namely, discriminate between windows containing ID data, and alternative-
3

---

Under review as a conference paper at ICLR 2023
distribution (AD) data. Thus, given an unlabeled test sample window We Q², where Q is possibly different distribution, the objective is to determine whether P * Q. We also ask what is the smallest test sample size k required to determine that P # Q. Since typically the training set Sm can be quite large, we further ask whether is possible to devise an effective detection procedure whose time complexity is o(m).
PROPOSED METHOD - COVERAGE-BASER DETECTION
In this section we present novel technique for detecting distribution shift based on selective prediction principles (definitions follow). We develop tight generalization coverage bound, based on ID training set sampled i.i.d. from the source distribution. This bound should hold with high probability for ID data from the source distribution. For a given window of data at test time we calculate its empirical coverage, and compare it to the theoretical coverage bound, Since the bound should hold with high probability on ID data, a coverage violation indicates w.h.p. a distribution shift from the ID source.
4.1 SELECTION WITH GUARANTEED COVERAGE
We begin by introducing basic selective prediction terminology and definitions that are required to describe our method. Consider a standard multiclass classification problem, where X' is some feature space (e.g., raw image data) and y a finite label set, y = {1, 2, .... C), representing C classes. Let P(X, Y) be probability distribution over X' x V and define classifier as a function f: X' + V. We refer to as the source distribution. A selective classifier Yaniv & Wiener 2010) is pair (f. g). where f is a classifier and X' - {0, 1 is selection function (El-Yaniv ct al. 2010), which serves as a binary qualifier for f as follows,
f(xx) don't know, if g(z) 0.
if g(x) = 1;
(f.))a))
A general approach for constructing a selection function based given classifier f is work functitoo (Geifman et al., 2019), Ky X - R_, referred to as CF The CF Ky should quantify confidence in predicting the label of based on signals extracted from f (Geifman et al., (019). The most common and well-known CF for a classification model f (with softmax its last layer) is its softmax response (SR) value (Cordella et al., [1955] De Stefano et al. 2000, Hendryckks & Gimpel 2017). A related CF is the entropy of the softmax vector (more precisely one minus the entropy, as Ky should indicate confidence). denoted here as Soft-Entropy Gaa 2016). A given CF Ky can be straightforwardly used to define a selection function: go(x) & [ k2) [ 2 0). where 0 is user-defined constant. For any selection function, we define its coverage w.r.t. distribution P, and its empirical coverage w.r.t. sample Sş (21, xk). as c(0, P) Er|go (x)], and č(0, Sk) & E respectively.
in terms of a confidence-rate function
Given a bound the expected coverage for a given selection function, we use it to detect distribution shift via violations of the bound. We now develop such a bound and show how to use to detect distribution shifts. For classifier f, detection detection-training training sample S,, pmm confidence parameter > O, and a desired coverage c* > O, our goal is to use S., to find a 0 value (which implies selection function 99) that guarantees the desired coverage. This means that under coverage should occur with probability of at most 8,
Prs..
< <c]
(1)
that guarantees Equation T provides probabilistic lower bound, guaranteeing that coverage of ID unseen population (sampled from P) satisfies > c* with probability of at least 1 6. A symmetric upper bound is presented in Appendix 7.5
We now describe the selection with guaranteed coverage (SGC) algorithm. The algorithm receives as input a classifier f, CF ky, a confidence parameter 6, a target coverage c², and a detection-traiine set Sm- The algorithm performs binary search to find the optimal coverage lower bound with confidence 8, and outputs a coverage bound b* and the threshold é, defining the selection function. A pseudo code of the SGC algorithm appears in Algorithm Our analysis of the SGC algorithm makes
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Selection with guaranteed coverage (SGC)
Input: train set: Sm. confidence-rate function: Ky. confidence parameter 6, target coverage: c².
Sort m. according to y (322, 24 E Sm (and now assume w.l.o.g. that indices reflect this ordering).
Emin = 1, Emux m
for to k [log2 m do
2 = (aainn + Zmax /
(x)()=)
Calculate 6s (O,, 5m)
Solve for bf (m, m (O,, Sm); {) (see Lemma 4.1
by (m, m (0,, mm); 2 S then
Sman
11 else
13
end
14 end
15 Output: bound: bg (m, m Ex (0s, Sm), f), threshold: Ox-
use of Lemma 4. which gives tight numerical (generalization) bound on the expected coverage, based on a test over a sample. The proof Lemma 4.1 is nearly identical to Langford's proof of Theorem 3.3 in (Langford & Schapire 2005). p. 278, where instead of the empirical error used in (Langford & Schapire 2005), we use the empirical coverage, which is also Bernoulli random variable. To gain better understanding of Lemma 4.1 please see Appendix 7.8
Lemma 4.1. Let P be any distribution and consider selection function with a threshold O whose be given and let ö(0, Sm) be the empirical coverage w.r.t the set Sm, sampled i..dd from P. Let b* (m, m- 600, Sm), 6) be the solution of the following equation:
coverage is c(O, P). Let
m-
arg min
Σ 3=0
B (5)
m
(1 b)m- $
(2)
b
Then,
Prs.. Pc < b (m, -(0, Sm, 8)} < 6.
(3)
The following is uniform convergence theorem for the SGC procedure stating that all the calculated bounds are valid simultaneously with probability of at least - 8. More specifically, we apply Lemma 4.1 [log2 m. times (using binary search), and the returned value (the last one) depends on all the other values. Since these applications are dependent we must use the union bound.
Theorem 4.2. (SGC- Uniform convergence) Assume Sm sampled i.i.d. from P, and consider an application of Algorithm 1 For k logg m]) let bi (m, (0;,, Sm), k) and O, be the values Then,
obtained in the gh iteration of Algorithm 1
Prs.. {i:: c(O,, P) < (m, m (0,, {)} < 8.
Proof (sketch see full proof in the Appendix 7.2.7y. Define, Bo, 2 by (m, m (2,0, Sm,, ) }), Co 2 c(O,, P), then,
Prs. (3i Co: < Ba,}
Σ
d0' Pr (Cor Bor Prs... (0: 0'}
Jo
8
d0' Prsm 10:=0'
4.2 COVERAGE-BASEE DETECTION ALGORITHM
Our detection algorithm works by applying SGC [log, m times for various target coverage values (c*). Application of SGC, with ej. yields corresponding pair, (b), 0,), ) of bound and threshold,
5

---

Under review as a conference paper at ICLR 2023
respectively. All applications of SGC are over the same sample Sm pm, In our experiments the [log, m. target coverages are uniformly spread in the interval j0, 1] (excluding its end points 0 and 1). Recalling that is the size of the window sample, We Q", define,
Dogg ml
1
bj.
logg m
j=1
Dogg mc]
[logz m!
k Σ ==1
20 Wx) = [log2 m
h: 90, (xp)
logg m
j=1
j=1
[loga mJ
=
k <llog2 m
go, (zi).
If Q is identical to P (i.e., no distribution shift), we expect that the bound computed by SGC over Sn will hold over Wa as well; namely, (0, Wx) 2 bjj for every iteration j of SGC.
As js represents the average of k log, values, and in experiments, k: (log m] >> 30, well known rule of thumb (James et al. 2013). 67, states that já is nearly normally distributed. Therefore, we can apply I-tes
accept or reject the null hypothesis Ho f Z μ., where the alternative hypothesis is H1 fi < The null hypothesis is rejected if the p-value is less than the desired threshold (significance level) of the test a (user defined). Thus, when evaluating performance using any tradeoff- based metric (e.g., AUROC) we vary to obtain the tradeoff. A pseudo code of our coverage-buae detection algorithm appears Algorithm
Algorithm 2: Coverage-Based Detection
// Training
Input Training: 8, Ny,, fez )== for j to le = llog, m| do
end by, Bg SGC(Sm. 6, cj, Kt))
Llog ml b2 Ejer
m
Output Training: μu, {bb,, 0,,,0,), ( logg
Detection model
Input Detection:
1a, {(b,, 02 ) [10gg Kyy, a, while True do
10
Receive windows Wi (71 m2k]
for 1 to logg do (0, Wv) > 90, (2.)
12
end 13
14
A
Floga m]
Σ
_==1
[logg logg mi
Σim G0, (F:)
15
Obtain p-value from t-test, Hu A 2 n. Hi A
if Ponlue < then
17
Shift_detected Truc
18
Output Detection: Shi seiiftddetccted Praluc
end if
20
end while
We train only once using SGC (Algorithm) I on the eettection-tranning data Sn, for [log, m times, in order to construct the pairs {bj, 0, llog ml
Our detection model utilizes these pairs to monitor given model, receiving at each time instant test sample window of size & (user defined). Wi- {.1, T2, ). which checked see content is distributionally shifted from the underlying distribution reflected by the cenectioonttriiiing data Sm. A schematic diagram of our procedure window data, WE. appears in Figure
In comparison to the previous baselines, our proposed method is extremely more efficient, as shown
in table [ A derivation the complexity bounds can be found in Appendix 7..
In experiments apply SciPy's stats. ttest_ samp t-test implementation Virtanen al.
2020

---

Under review as a conference paper at ICLR 2023
Ky [ci))=t [oggam]
Figure 1: Our detection procedure comprising two stages, training and detecting. The detec- [ {6, 1 [lok, mj (computed at the training stage), i.e., only Ollog2 m) parameters relative to the training data size (m).
Training (SGC)
(Di)) (
tion stage requires parameters {6; [ m)] and
S
i=1
W
Detection Model
Shift
No-Shift
Detection Method
Space
Time
Coverage-Basee Detection (Ours)
O + logm) Om + k2 + mm)
O + log m) O (d(m² + k22 + mk))
MMD
KS
0 (d(m + k))
O (d(mlog m klog k))
Table 1: Complexity comparison. Orange bolds entries indicate the best detection complexity. m, k refers to the detection -triinnn size, and window size, respectively. refers to the number of dimensions after dimensionality reduction. A derivation of the complexity bounds can be found in Appendix 7.3
EMPIRICAL STUDY
In this section we evaluate the performance of our coverage-based detection algorithm, as well as the baselines defined in Section Three experiments are conducted. The first experiment, is carried out using synthetic data, and its purpose to provide some insight into the operation of our algorithm. Specifically, we use synthetic data in order to demonstrate that our proposed bound tightly holds, and when a distribution shift occurs, is violated as expected. Unfortunately, due to lack of space, this experiment is described in Appendix 7.4.1 The purpose of the other two experiments is to examine the performance of our detection a algorithm, with respect to the four baselines (KS-BBSD-S, KS-BBSD-E. MMD-BBSD-S, and
carried out on the CIFAR-10 (Krizhevsky et al. 2009) and the ImageNet (Deng et al., 2009) datasets, which are used detection-training (ID) data. As test data use number of datasets and corruptions of the detection-training data to represent a variety of distribution shifts (see details below).
see Section 2). These experiments
We now define the metrics we to evaluate detection performance. Following (Liang et al. 2018). we consider a soft binary classification setting (is P = Q or P + Q, see Section 3). where the answer determined based decision threshold. We thus use the Area Under an Operating Characteristic curve (AUROC) and the Area under the Precision rrecal curve (AUPR).
AUROC is threshold-indeeendeer the relationship between the true positive rate and the false positive rate. The AUROC can be interpreted as the probability that a positive labeled window will have higher detection score than negative one (Fawcett 2006). An AUROC score of 100% corresponds to perfect detector. AUPR metric. The precision- recall (PR) curve a function giving the
metric (Davis & Goadrich 2006). The ROC curve depicts
is also a threshold-independdee relation between the precision TP/(TP+FP) and the recall TP/(TP+FN) for all threshold values. Following (Liang et al., 2018), we separate this metric into AUPR-Tr and AUPR-Te, which measure the area under the PR curve at which positive test windows are containing ID pretection-tranning data (AUPR-TI Tr) and AD (test) data (AUPR-Te), respectively. It should be noted that AUPR-Te Te is almost saturated in most of our experiments (due data imbalance), however, decided to include the results of AUPR-Te nonetheless for completeness.
5.1 CIFAR-10 AND IMAGENET
We now present our primary empirical study using the CIFAR-10 (Krizhevsky et al., 2009) and ImageNet (Deng et al.) 2009) datasets. In both cases the customary validation/test sets (10,000 instances in CIFAR-IO 10 and 50,000 in ImageNet) are split randomly (and uniformly) 30 times into two groups to form 30 detection-training sets (S,,. see Section 3 and tests pairs, that are used to train the detection model and evaluate its performance, respectively. The size of the test set is 1000 in all cases. Thus, the sizes of prrection-trannnng sets and test sets (9000, 1000) for CIFAR-10 10 and (49,000, 1000) for ImageNet. Detection models are challenged by forming windows We. &. for various sizes of 0 < k < 1000, where in each case Wi comprises simulated distribution shifts that represent various
7

---

Under review as a conference paper at ICLR 2023
distributions Q. including the no-shift case (where Q P), check for false-alarme (see details below). To aggregate a metric score such as AUROC, over all window sizes to a single number, we define the metrics Agg-AUROC (sce (egure2Heff) Agg-AUPR-TI and Seg-AUPR-To, which used T 3 These metrics denote the area under the curve of the metric as a function of k. We also display the scores individually for each window size, details later.
Figure 2: ImageNet Experiments. AUROC as a function of the win- dow size k (left), and the mar- gin between our best model (Ours- Ent). and the best baseline, KS- BBSD-S (right). The margin is the difference between the AUROC scores of Ours-Ent and KS-BBSD- S. 5.Oe--r error-bars are shadowed. All figures show metric values with a one-o error-bar obtained via bootstrapping. Throughout all experiments, we use the coverage-based detection algorithm (Algorithm 2 with á = 0.001, and in the applications described below, we instantiate CF (Kz)) with both SR and Soft-Entropy. These two applications of our method are referred to as Ours-SR and Ours-Ent.
100
16
Ours Ert <5 BUSD 5
93
AUROC
86
Agg-AURDC
KS-9250-5
3 4
8
10
Window data 18/100)
Window data (8/100)
5.1.1 CIFAR-10 EXPERIMENTS
To evaluate performance, we used two pretrained ResNet-18 and ResNet-50 (He et al., 2016). Following (Rabanser
2019) we simulated the following shifts: Rotations: with angles
{10,40 40, 90 Gaussian noise: with STD a E
D5E 255 255 J. the CIFAR-100 dataset (Krizhevsky
40 60
80
al., 2009), the SVHN dataset (Netzer al.
2011), and Adversarial: fast gradient sign method
(Goodfellow et al. 2015), projected gradient descent (Madry et al.] 2018). Carlini Wagner (Carlini &
Wagner 2017), referred to as FGSM, PGD and CW, respectively. The aggregated results for these shifts are summarized in Table 2]
ResNet-18
ResNet-50
Method
Agg-AUROC
Agg-AUPR-Te/T-
Agg-AUROC
Agg-AUPR-Te/T
Ent
98.57
99.85 / 122.18
98.72
99.87 / 92.08
Ours
SR
98.56
99.85 / 92.11
98.7
99.87 / 91 .84
BBSD-S
97.27
99.73/ / 82.58
97.61
99.77 / 83.71
KS
BBSD-E
96.76
99.69 77.09
97.47
99.75 / 82.94
BBSD-S
84.3
98.38 27.75
83.13
98.19 / 26.98
MMD
BBSD-E
87.25
98.73 / 35.1
85.7
98.47 32.09
Table 2: CIFAR-10 Experiments. An underlined entry indicates the best baseline among the proposed baselines (KS-BBSD-S, KS-BBSD-F, MMD-BBSD-S, and MMD-BBSD-F, see Section 2 and bold orange indicates the best detection score for given model and metric.
Orange bold entries indicate the best evaluation score, while underlined entries indicate the best evaluation score vis-a-vis the baselines. It is evident that Ours-Ent dominates all methods w.r.t. all performance metrics, and when applied with both architectures. Interestingly, both our detection variants excel in the Agg-AUPR-TH metric, compared to the baselines. This reflects the fact that detection methods have significantly fewer false-alarms compared to the baselines; i.e., the baselines are more likely to misidentify ID windows as AD windows than we are. This is crucial when considering distribution shift detection, since most of the time the model is processing ID data. Among the baselines, KS-BBSD-S dominates the three other baselines, in line with the findings of (Rabanser et al., 2019), who also experimented over CIFAR-10 10. For individual results regarding each window size, see Appendix 7.22
5.1.2 IMAGENET EXPERIMENTS
For the ImageNet dataset, we simulated larger number of shifts than we did in the CIFAR-10 experiments (Section 5.1.1 Rotations: 0 E {10, 40, 90, 120, 150, 180), the ImageNet-O dataset
8

---

Under review as a conference paper at ICLR 2023
(Hendryeks et al. (021), , the ImageNet-A dataset (Hendrycks al. 2021). and the ImageNet-C dataset (Hendrycks & Dietterich 2019), which contains 75 common visual distortions with intensities ranging from to 5; for our experiments we use {1, 3, 3). We also consider adversarial attacks: fast gradient sign method (Goodfellow et al. 2015), projected gradient descen! (Madry et al. 2018). Carlini Wagner (Carlini& & Wagner| 2017), referred to as FGSM, PGD and CW, respectively. For each distribution shift type we considered three proportions of window contamination, where p denotes the proportion of shifted instances in the window. For example, if p = 3.- a third of the window is contaminated with instances sampled from the shifted distribution. while the remaining instances are sampled from P. In our experiments we used proportions p E {1. 2 3) Due to lack of space we present only the most successful baseline (we experimented with ali), namely, the KS-BBSD-S detection model, which was also the most successful baseline regarding the CIFAR- 10 experiment. For this ImageNet experiment, we used the strong EfficientNet-BO network TTn & Le 2019) as the underlying model for our methods and the baseline. We took model that was pretrained over ImageNet [Wightman 2019). In Table 3 we summarize the aggregate results for all these shifts.
3:
EfficientNet-B0
Method
p=1 Agg-AUPR-Ie/I
2/3
1/3
Agg-AUROC
AggAUROC Agg-AUPR-Ie/T Agg-AUROC Agg-AUPR-ToTT
Ent
99.15
99.93 / 94.21
98.23
99.84 09.84/87.21
87.21
93.50
99.45 79.45/61.76
61.76
Ours
SR
99.12
99.92/ 94.29
98.18
99.84/ 86.21
93.38
99.44 59.95
KS
BBSD.S
98.3
99.86 83.85
96.06
99.67 70.5T
89.16
99.02/ / 44.28
Table ImageNet Experiments. Orange bolds indicate the best detection score for given metric, and contamination percentage (p). KS-BBSD-S (Rabanser et al., 2019), is the Saanogorov-Smirooe (KS) statistical test (Massey Jr 1951). using a Black Box Shift Detection (BBSD) (Lipton et al. 2018) method, using Softmax (S); namely, KS-BBSD-S. According to (Rabanser et al. 2019), and based on our analysis in Table this is the best proposed baseline.
Bold orange entries indicate the highest evaluation scores. In line with the results of the CIFAR-10 -00 experiment (Section 1.1.I. Ours-Ent dominates both other methods (Ours-SR, KS- KS-BBBD-S) for all performance metrics, and for each contamination percentage (p) considered, with the exception of Agg-AUPR-Trr (p> = 1), where in this case Ours-SR dominates. A significant margin separates Ours- Ent from KS-BBSD-S, and this margin becomes even larger when the contamination (p) decreases (see Appendix 7.4.3). In Figure 2efft) one can see the resulting AUROC scores as a function of the window size k for p = 1. In Figure righht we also display the margin between Ours-Ent and the best baseline, CSS-BBSD- (the rest of the metrics, appear in the Appendix, Figure 3 For the vast majority of window sizes, Ours- Ent performs significantly better than the best baseline, KS- BS-BBBD--S Furthermore, see Appendix 774.3] Ours-Ent consistently outperforms KS-BBSD-S over all metries, across all percentages of affected data (p (1, 3: 5 H). and for all window sizes, where the biggest gap is over the AUPR-TI Tr metric, which accounts for lower false-alarms compared to the baselines. We conclude that in our setting. Soft- Soft-Entropy is the best CF. Appendix 7.6 provides detailed comparison.
2
6 CONCLUDING REMARKS
We presented a novel and powerful method for the detection of distribution shifts within given window of samples. This coverage-based detection algorithm is theoretically motivated and can be applied to any pretrained model. Due to its low computational complexity, our method, unlike typical baselines, is practicable. Our comprehensive empirical studies demonstrate that the proposed method works very well, and overall significantly outperforms the baselines on both the CIFAR-10 10 and ImageNet datasets, across a number of neural architectures and a variety of distribution shifts, including adversarial examples. In addition, our coverage bound is of independent interest and allows for the creation of selective classifiers with guaranteed coverage. Several directions for future research are left open. Although we only considered classification, our method can be extended to regression using an appropriate confidence-rate function such as the MC-dropout (Gal & Ghahramani (0166). Extensions to other tasks, such as object detection and segmentation, would be very interesting. It would also be interesting to examine other types of shift benchmarks such as (Koh et al. [02II. In our method, the information from the multiple coverage bounds was aggregated by averaging, but it is plausible that other statistics weighted averages could provide more effective detections. Finally, an interesting open question is whether one can benefit from using outrier/averssariall detection techniques combined with population- detection techniques (as discussed here).

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ella Bingham and Heikki Mannila. Random projection dimensionality reduction: applications to image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 245-250, 2001.
J Martin Bland and Douglas G Altman. Multiple significance tests: the bonferroni method. Bmj. 1995.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposiun on Security and Privacy, 2017.
Luigi Pietro Cordella, Claudio De Stefano, Francesco Tortorella, and Mario Vento. A method for improving classification reliability of multilayer perceptrons. IEEE Transactions on Neural Networks, 6(5): 140-1147, 1995.
Jesse Davis and Mark Goadrich. The relationship between precision-recall and ro curves. In ICML., 2006.
Claudio De Stefano, Carlo Sansone, and Mario Vento. To reject or not to reject: that is the question-an answer in case of neural classifiers. IEEE Transactions Systems, Man, and Cybernetics, Part C (Applications and Reviews), 30(1):84-94, 2000.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: large-scale hier- archical image database. In 2009 IEEE Conference Computer Vision and Pattern Recognition, 2009.
Ran Gl-vaniv and Yair Wiener. On the foundations of noise-free selective classification. jmlr, 2010.
Ran Yaniv et al. On the foundations of noise-free selective classification. JMLRR 2010.
Tom Fawcett. An introduction to roc analysis. Pattern recognition letters, 27(():861-874 2006.
Stanislav Fort, Jie Ren, and Balaji Lakshminarayanan. Exploring the limits of out-of-distribution
detection. Advances in Neural Information Processing Systems, 2021.
Yarin Gal. Uncertainty in deep learning. 2016.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In ICML, 2016.
Yonatan Geifman and Ran Elnia..v. Selective classification for deep neural networks. In NIPS, 2017.
Yonatan Geifman, Guy Uziel, and Ran El-Yaniv. Bias-reduced uncertainty estimation for deep neural classifiers. ICLR, 2019.
Izhak Golan and Ran El- Yaniv. Deep anomaly detection using geometric transformations. In NeurlPS, 2018.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel two-sample test. Journal of Machine Learning Research, 13:723-773, 2012.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
Nicholas A Heard and Patrick Rubin-Delanchy, Choosing between methods combining-values. Biometrika, 105(1):239-22) 246, 2018
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. In ICLR, 2019.
Dan Hendrycks and Kevin Gimpel. baseline for detecting misclassified and out-of-distribution examples in neural networks. In ICLR, 2017.
10

---

Under review as a conference paper at ICLR 2023
Dan Hendrycks, Mantas Mazeika, and Thomas Dietterich. Deep anomaly detection with outlier exposure. In ICLR, 2019.
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. CVPR, 2021.
Gareth James, Daniela Witten Trevor Hastie, and Robert Tibshirani. An introduction to statistical learning, volume 112. Springer, 2013.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsub- ramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M Beery, Jure Leskovec, An- shul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. Wilds: benchmark of in-the-wild distribution shifts. In Proceedings of the 38th International Conference on Machine Learning. PMLR, 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
John Langford and Robert Schapire. Tutorial on practical prediction theory for classification. Journal of machine learning research, 6(3), 2005.
Shiyu Liang, Yixuan Li, and R. Srikant. Enhancing the reliability of out-of-distribution image detection neural networks. In ICLR, 2018.
Zachary C. Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In ICML, 2018.
Thomas M Loughin. A systematic comparison of methods for combining p-values from independent tests. Computational statistics & data analysis, 47(3):467-445, 2004.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Frank J Massey Jr. The kolmogorov-smirnov test for goodness of fit. Journal of the American statistical Association, 1951.
Zachary Nado, Neil Band, Mark Collier, Josip Djolonga, Michael W. Dusenberry, Sebastian Far- quhar, Angelos Filos, Marton Havasi, Rodolphe Jenatton. Ghassen Jerfel, Jeremiah Liu, Zelda Mariet, Jeremy Nixon, Shreyas Padhy, Jie Ren, Tim G. J. Rudner, Yeming Wen, Florian Wen- zel, Kevin Murphy, Sculley, Balaji Lakshminarayanan, Jasper Snoek, Yarin Gal, and Dustin Tran. Uncertainty baselines: Benchmarks for uncertainty & robustness in deep learning. CoRR, abs/2106.04015. 2021. htts::::: //axxii.//axxv...//// org
04015
Eric Nalisnick, Akihiro Matsukawa, Yee Whye Tch, and Balaji Lakshminarayanan. Detecting out-of- distribution inputs to deep generative models using typicality. arXiv preprint arXiv: (0t.::/990000994 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop, 2011.
Yunchen Pu, Zhe Gan, Ricardo Henao, Xin Yuan, Chunyuan Li, Andrew Stevens, and Lawrence Carin. Variational autoencoder for deep learning of images, labels and captions. In NIPS, 2016.
Stephan Rabanser, Stephan Günnemann, and Zachary Chase Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. NeurlPS, 2019.
Jie Ren, Peter J Liu, Emily Fertig, Jasper Snoek, Ryan Poplin, Mark Depristo, Joshua Dillon, and Balaji Lakshninarayanan. Likelihood ratios for out-of-distributio detection. Advances Neural Information Processing Systems, 2019.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning internal representations by error propagation. Technical report, California Uniy San Diego La Jolla Inst for Cognitive Science, 1985.
11

---

Svante Wold, Kim Esbensen, and Paul Geladi. Principal component analysis. Chemometrics and Under review as a conference paper at ICLR 2023
Robert J Serfling, Approximation theorems of mathematical statistics, volume 162. John Wiley & Sons, 2009.
Dougal Sutherland, Hsiao- Yu Tung, Heiko Strathmann, Soumyajit De, Aaditya Ramdas, Alexan- der J. Smola, and Arthur Gretton. Generative models and model criticism via optimized maximum mean discrepancy. In ICLR (Poster), 2017.
Mingxing Tan and Quoe Le. Efficientner: Rethinking model scaling for convolutional neural networks. In ICML, 2019.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, ilhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 2020.
Ross Wightman. Pytorch image models. pytorch- iww---maaeeeaas
https://github: http://ttthuu...o//v// ghtman/
2019.
intelligent laboratory systems, 2(1-3):37-52 1987.
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers. arXiv preprint arXiv:2106.04550 2021.
7 APPENDIX
7.1
SHIFT-DETECTIE GENERAL FRAMEWORK
The general framework for shift-detection can be found in the following figure, Figure
X
Two-Sample Test(s)
Combined Test Statistic Shift Detection
Dimensionality Reduction
X target
Figure The procedure of detecting a dataset shift using dimensionality reduction and then two-sample statistical test. The dimensionality reduction is applied to both the detection-training (source) and test (target) data, prior to being analyzed using statistical hypothesis testing. This figure taken from (Rabanser al. 2019).
7.2
PROOFS
7.2.1
PROOF FOR THEOREM 4.2
Proof.
Define
8 ) Be, & (m, Sm):
Co. 2 P).
dntection-training Consider the 1th iteration of SGR detection training set Sm. and recall that, 8, K (x))) Iz E Sm, (see Algorithm II. Therefore, 0, is a random variable (between zero and one), since it is function of random variable (x S..). Let Prs... (0; 0') be the probability that 0: 0'.
12

---

Under review as a conference paper at ICLR 2023
Therefore,
Prsm (Co, < B
d0' Prs (Co, BB,, 10; 0'} Prs... 10: = 0'}
do' Prrr (Co BBo) Prs... {0; 3
Since Bg, is obtained using Lemma 4.1 (see Algorithm Db. and 0; A'
Pre.. (Co,
B Prss (Cor BBr <
we get,
Prsm. (Co: < BB.}
do' Prsm (Co < Brr) Prs.. {0= = 0'}
d0' 8 J/¹
Prrs.. (0, =0)
k
8
(fo
d0' Prs (0: = =03}
8
k
The following application of the union bound completes the proof,
Prs.. (3i: Co, Be, S Σ Prsm. (Co. Bo, }
Σ 8.
13

---

Under review as a conference paper at ICLR 2023
7.3 COMPLEXITY ANALYSIS
This section provides brief complexity analysis of our method as well as the baselines (see Section 2) All baselines lazy learners (analogous nearest neighbors) in the sense that they require the entire source (detection-training) set for each detection decision they make. Using only subset will result sub-optimal performance. MMD permutation test (Gretton et al. 2012) that also employs a kernel. The complexity of kernel methods is dominated by the number of instances and, therefore, the time and space complexities of MMD are (dd(m² + k-2 + mk)) and O(m² + k.2 mk). respectively, where in the case of DNNs, d is the dimension of the embedding or softmax layer used for computing the kernel. The KS test Massey Jr 1951) is univariate test, which is applied on each dimension separately and then aggregates the results via a Bonferroni correction. Its time and space complexities are (d((m log m + l log k)) and (d((m + k)). respectively.
Our coverage- based detection algorithm is trained (only once) at (m logm) time and (m)) space complexities. Then, each detection round incurs OOk+log m) for both its time and space complexities. In practice, dm3 > dm logm m > log m, which makes method significantly more efficient. For example, both baselines cannot process large "Google-scale" datasets, which our method can handle. A summary of these complexities appears in Table (Section 4.2)
14

---

Under review as a conference paper at ICLR 2023
7.4 DETAILED EXPERIMENTS RESULTS
7.4.1 SYNTHETIC DATA
To gain some insight into the operation of our coverage- based detection algorithm we consider the following synthetic setting. A simple binary linear classifier trained to discriminate between two 2D Gaussians, which are centered at (-5, O), (5, 0), respectively, whose covariance matrix is the identity. As the confidence-rate function (CF) took the well-known softmax response (SR). For the shifted distribution we consider two cases where the modified distribution is defined by increasing or decreasing the distance between the Gaussians' centers. When the two Gaussians move closer, the coverage lower bound is expected to be violated. On the other hand, when they are further apart, the lower bound will not be violated. Thus, for this case, we introduce a symmetric coverage upper bound. This upper bound appears in Appendix 7..3 Hence, when the modified Gaussians are further apart, we expect that the upper bound will be violated. Go A (-5,, 0). (5, 0)} are the centers of the Gaussians generating the detection-training data. G_ {(-6, 6, 0), (6. 0)} and G {(-4, 0), (4, 0)) represent two variations of Go. where G+ increases and G decreases the distance between the centers.
We created two detection models by applying the training component of Algorithm 2twice (to obtain the lower and upper bounds) with the following hyperparameters: 5 = 0.001 and detection-training set Sm consisting of 50, 000 samples generated from the Gaussians Go (25,000 from each).
The set of desired coverages {<t )==1 lloga m] is uniformly spread in the interval [o. 1] (excluding its end points 0 and 1); thus, we have llog2 50, 000J = 15 desired coverages. To challenge our method in this setting. we generated samples from G+, G_ (expecting a violation of the upper and lower bounds, respectively), and also Go (as a sanity check that the bounds hold tightly).
We define the test windows W ~ G_, W ~ G+, W ~ Go. each containing 25,000 samples from each of its two generating Gaussians (thus, k = 50, 000). For example, in the case of G_, generate 25,000 samples from each Gaussian centered at (-4, 0), and (4. 0), respectively.
In Figure 4 we show the relationship between the empirical coverages (16) W&)), llog, ml
the bounds (1bū ) [log2 ml), and the desired coverages (fc² [|0g for each test window, W j=1
{-, + 0}. Figures (4a) through (4d) show the results corresponding the 'no-shift' and 'shift' cases, respectively.
0.8
0.8
3.4
2..
g0.0
0.4
Empprios
02
Emp
02 0.4
65
6.5
0.6
0.
02
C2
5.4
05 02
Oetite coverage
Destnd coverage
Desred coverage
Deatte coverage
W.P. bound.
(a)
lower
(b) bound.
W&.
upper
(c)
W
upper
(d)
W
lower
bound.
bound.
Figure 4: The empirical coverages and bounds as function of the desired coverages, for each the cases discussed in the text.
In particular, Figures (4c) and (4d) indicate that the windows Wi and W; violate the upper and lower bounds, respectively. This behavior is expected, since the former (WC) should result in under- confident predictions, and the latter (WF). over-confident predictions. The resulting p-values in both cases were nearly O, which indicates a certain shift detection. The no-shift cases (W2) are shown in Figures 44),, (4b), from which it is evident that both bounds hold tightly (the p-value is nearly 1). Interestingly, when a shift occurs, see Figures 4c 4d the largest margin between the empirical coverage and the bound (in both the upper and lower cases) is obtained the interior of the coverage range (e.g., around 0.7 coverage in the lower bound case, 4d). In other words, this synthetic experiment indicates that the detection effectiveness of our method is at its best in mid-range coverages. Specifically, Figure shows the margin between the empirical coverages !log ((2)(0) W !loa ml,
), the bounds ((b))] [loga
[logam]] "I] and the desired coverages ((e))
logg m)), for each
15

---

Under review as a conference paper at ICLR 2023
data window We +3 The no-shift case (WF) results in tight bound and, therefore, very small margin (see Figures 5a and 5b). When shifts occur (W₂ W ) the gap between the bounds and the empirical coverages Is signifrcantly larger and is not uniform (see Figures 5c and [d]..
We can thus infer that different data shifts would result in varying gap sizes, depending the desired coverage being analyzed. In particular, the largest gap does not necessarily occur when c* 1, indicating that the detection power lies within lower coverages.
3.5325
0.200
3.4000
0.5
2.0000
-0.2
0.1
2.0023
Margh lowerbounds
-0.008
Margin
Murgh
3,2000
-0220
Hoper bounds
0.
Usper bounte
Jower Spart 2o0nds
6.4
Desied
bedime
(a) Margin of a tight lower bound.
(b) Margin of tight upper bound.
(c) Margin of vio-
(d) Margin of a vio- lated lower bound.
lated upper bound.
Figure 5: The margins between the bounds and the actual coverage.
16

---

Under review as a conference paper at ICLR 2023
7.4.2 CIFAR- 10 EXPERIMENTS
The score for each window Wa. of size well the margin between our best method (Ours-Ent) and the best baseline (KS-BBSD-S) considering the ResNet-18 and ResNet-50 architectures, can be found in Figures respectively.
100
100.0
100
91
96.2
82
AUROC
82
96.4
64
MMD-6SSD-E
KS BBSD.5
94.6
HND 8BSD-E
MMD-665D-E
KS BEED
92.8
K 6BED
10
2
9
Window data (K100)
data (8/2000)
data (62.0))
Ours-Ent
Curs-Ent KS 68SD
Ours Ent
8850
KS 8650
Margin
Margin
Margin
0
10
8
9
10
Window data (K/1 00)
Window data (k/100)
Window data (A/200)
(a) AUROC
(b) AURP-Te
(c) AUPR-Tr
Figure 6: CIFAR-10 Detection results using ResNet- 18. The metric scores as a function of window size (upper), and the margin between best method and the best baseline, (lower). The margin is the difference between the metrics (AUROC, AUPR-Te, AUPR-Tr) scores of Ours-Ent and KS-BBSD-S. One-a error-bars are shadowed.
100
100.0
100.0
82.4
AUROC
AUPR.TE
64.8
MMD BS5D
BESD
MND-BB5D-E
MHD-6BSD-E
$BSD
29.6
93.0
12.0
3
10
3
4
9 10
1
4
9
Window data (8/100)
Window data (A/100)
Window data (k/100)
OursEnt
Curs-Ert
32
OursEEt
5S-8850
35-85SD-5
KS-655..5
18
Margin
Margin
Margin
3 4 5
2 3
9
2 3
6 7
8
10
Window data (R/100)
Window data (k/100)
Window data (A/000)
(a) AUROC
AURP-Te
(c) AUPR-Tr
Figure 7: CIFAR-10 10 Detection results using ResNet-50. The metric scores as function of window size (upper), and the margin between our best and the best baseline, (lower). The margin is the difference between the metrics (AUROC, AUPR-Te, AUPR-Tr) scores of Ours-Ent and KS-BBSD-S. One-a baror-bars are shadowed.
17

---

Under review as a conference paper at ICLR 2023
7.4.3 IMAGENET EXPERIMENTS
Regarding the ImageNet experiment, the score for each window WR. of size k, as well the margin between our best method (Ours-Ent) and the best baseline (KS-BBSD-S), considering the EfficientNet-Bie architecture, is given in Figures respectively.
10 for p 1. p 2/3, and p 1/3.
100.0
93
99.2
02.4
86
Agg AUROC 88,
AUPR-Tc
98.4
AUPR-F
64.8
79-
97.6
472
72-
KS 0850
96.0
K3-585DD-5
29.6
KS-8850-5
65
Durs-Ent
96.0
Curs Ent
12.0
Ours-En
Window (R220))
Window (V110))
16
Gur-fint
Ours-fit KS-8550-5
Gur--ft
KS-885D-5
32
K3-8850-5
Nörgin
Mangin
Margi
18
-4
(k/100)
(t/100)
(6/100)
Figure 8: ImageNet Detection results using EfficientNet-BOO with p 1. The metric scores function of window size (upper), and the margin between our best and the best baseline, (lower). The margin is the difference between the metrics (AUROC, AUPR-Te, AUPR- -T) scores of Ours-Ent and KS-BBSD-S. One-a arror-bary are shadowed.
100.0-
100.0
100.0
89.6
98.8
81.6
79.2
AUPRTe
AUPRoT
63.2
68.8
44.8
58.4
KS 88- D-5
95.2
KSS KS-BRRD-5 Cursfnt
26.4
K5-885D-5
48.0
Our
94.0
Gum-Ent
(k/100)
(6/100)
(k/100)
24
Ours Ent
Ours Ent KS-8850-5
53
Ours Ent
KS-BB5D-5
KS-B8SD-5
Margin
Margin
13.
-6
(K/100)
(2/100)
Window data (8/100)
Figure 9: ImageNet Detection results using EfficientNet-BO with p 2/3. The metric scores as function of window size (upper), and the margin between our best and the best baseline, (lower).The margin is the difference between the metrics (AUROC, AUPR-Te, AUPR-T scores of Ours-Ent and KS-BBO KS-BBSD-S. One-a error- bars are shadowed.
18

---

Under review as a conference paper at ICLR 2023
88.8
96.4
01.2
77.6
AUPRITe
96.8
AUPR-TS
62.4
66.4
95.2
43.6
KS B
93.6
BESD-5
Ourn-Ert
Curs-frt
data (A/200)
(R/100)
(W/100)
Ours Ent
Ours Ent KS 8
Ours Ent KS S
24
KS 9B5D-5
Margin
14:
Margin
17
-1
6
10
0
7
10
2
7
Window data (c/100)
Window data (A/100)
Window data (R/100)
Figure 10: ImageNet Detection results using EfficientNet-BOO with p 1/3. The metric scores as function of window size (upper), and the margin between our best method and the best baseline, (lower). The margin is the difference between the metrics (AUROC, AUPR-TC Te, AUPR-Tr) scores of Ours-Ent and KS-BBSD-S. One-o error-bars are shadowed.
19

---

Under review as a conference paper at ICLR 2023
7.5 SYMMETRIC UPPER BOUND
Here we develop an upper coverage bound.
For classifier /, detection-trainingg sample Sm pm. confidence parameter 8 0, and desired coverage c* >> 0, our goal is to use 5m to find a value (which implies a selection function go), such that the coverage satisfies,
Prs,. (c(0,)) c*) <
(5)
This means that coverage should occur with probability of at most 6.
The pseudo code the algorithm that finds the optimal coverage upper bound (with confidence 8), appears in Algorithm
Algorithm 3: Selection with guaranteed coverage Upper bound
Input: train set: Sm. confidence-rate function: Ky, confidence parameter d, target coverage: c". Sort Sm according Ni (ata), E Sm (and now assume w.l.o.g. that indices reflect this ordering).
Zmin 1, 2max
for 1 to [log, m do
[=mmin + Zmuxx /2]
8, = (xz)
Calculate (0,,,, Sm)
Solve for by (m, m (0;,,, Sm); 2) [see Lemma 4.1)
if bi (m, m (Oi, Sm), f 2 then
2min
else 11
12
2max = end if
13
14 end for
15 Output: bound: (m,,, èv (Ok; Sm), 2). threshold: 0g.
Similarly to SGC (Algorithm]) D. Algorithm uses Lemma 7.1 The proof of Lemma 7.1 can be easily
deduced from the proof of Lemma 4.1
Lemma 7.1. Let P be any distribution and consider CF threshold 0 with coverage of c00, P). Let < 8 < 1 be given and let č(0, Sm)) be the empirical coverage w.r.t. the set Smo sampled iidd from P. Let 6* (m, m E(0, Sm), be the solution of the following equation:
m-0(9....))
(ml)
arg min
Σ 1=0
61(1 6)m- =
(6)
i
Then,
Prs... (c(0, P)
> b" (m, (0, <
(7)
7.6 COMPARISON BETWEEN OUR TWo PROPOSED METHODS
The following Figure (T] compares between our two proposed methods, Ours-Ent, Ours-SR, for contamination value of 2/3. Figure 11 left) shows the AUROC metric as a function of window size. Figure I1 right) shows the margin between the two methods.
20

---

Under review as a conference paper at ICLR 2023
100.0
Ours-Ent
93.8
Ou
3
AUROC
87.6
Margin
81.4
75.2
Ours-SR
-3
69.0
Ours-Ent
-5
0
4
5
6
7
8
9
10
0
1
2
5
6
8
9
10
Window data (k/100)
Window data (k/100)
Figure 11: Comparison between Ours-Ent, and Ours-SR. One-a error-bars are shadowed.
7.7 PERFORMANCE PER DISTRIBUTION SHIFT IMAGENET
The following graphs demonstrate representative results regarding the detection performance per distribution shift. Specifically, the first row of Figure 12 represents the AUROC metric where the contamination value is two thirds (p 2/3), for the following diverse shifts separately: ImageNet C-severity 1, Imagenet A, rotation of 40 degrees, rotation of 180 degrees and the best considered adversarial attack, CW. The second of Figure represents the margin between our best method (Our-Ent) and the best baseline (KS-BBSD-S).
07.4
4,00
56.2
06
Devos
5
9:23
1
01500
01501
Figure 12: ImageNet Partial detection results, for individual distribution shifts, One-a error-bars are shadowed.
7.8 BROADER EXPLANATION OF LEMMA
Lemma gives (the tightest possible) generalization numerical bound of a coverage, given test sample, Sm, and confidence parameter 8. Equation 2 solves for the inverse binomial, which stands for the probability, such that an event with most c(0, S,,) "successes" will equal 6. Since the inverse binomial is monotonic decreasing function of b. we look for the minimum probability. Lemma 4.1 states, that the solution of Equation 2 b*, is lower bound, which holds with probability 1 - 8, and therefore, the probability of violating this bound is 6. This is stated in Equation 3
21


Reviews:
[{"review_id": "glXY4si4hYV", "reviewer": "Reviewer_TC5F", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a method for identifying when a distirbutional shift from the training data has been received in a DNN. The method considers a window of recent instances as opposed to identifying single OOD instances.", "summary_of_the_review": "Overall, I think this is a solid work, which gives an adequate contribution. I would still like to see the concerns raised above be addressed.", "strength_and_weaknesses": "## Strengths\n\n- The method is well motivated and sound.\n- The method outperforms previous methods with impressive gains in computational complexity.\n\n## Weaknesses\n\n- Do the metrics outlined in section 2 such as MMD and KS-BBSD have the implcit assumption that the data is coming in from an unbiased sample of the Q distribution? For instance, would everything break down if the test time environment made predictions by streaming many instances of a single class at once? \n\n- I ask the question above, because the testing data being an unbiased sample from the data seems to be an implicit assumption of the method, and one which might not be realisitic for an entire range of models in practice, which may hinder its usefulness. I realize this is a consequence of the chosen problem setting, but I think at the very least, this should be stated as a limitation which (I think) applies to the selected baselines as well.\n\n- Page 4: \"more precisely one minus the entropy...\" Entropy of a softmax $h$ is in the range $[0, \\infty]$. So why would one want to look at $1 - h$? Does this mean to only look at the class prediction index as a single Bernoulli variable?\n\n- The ImageNet experiments in Table 3 aggregate over all corruptions of the different imagenet datasets. It would be nice to see breakdowns of the performances on individual datasets as well (maybe in the appendix) to see if any patterns emerge between the different types of datasets. \n\n- The intuition around equation 2 and 3 could be expanded, maybe in the appendix. The understanding of the whole paper rests on these two equations, and they were both hard to digest at first without great effort for me. I think it would be easier for most readers to grasp if equations 2-3 could be justified with a non-rigorous, but intuitive explanation. \n\n## Minor\n\n- Page 2: \"As shown here, the KS-BBSD...\" as shown where? This sentence is unclear.\n- is the sorting in algorithm 1 ascending or descending? Or does it not matter?\n- Section 4.2: $(b^*_j, \\theta_j)$ is said to be a threshold and a bound, respectively, but the algorithm has those terms reversed. Shouldn't it say \"bound and a threshold, resepctively?\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "e120zmGsgx", "reviewer": "Reviewer_Uqk1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper focuses on improving distribution shift detection given a pre-trained deep model. It proposes a coverage-based statistic and uses the statistic to detect distribution shifts. The statistics are proven to have a high-probability coverage of the in-distribution data. The detection step is through a two-sample t-test. Experiments on CIFAR and ImageNet show the proposed method outperforms existing baselines. ", "summary_of_the_review": "The paper proposes a novel distribution shift detection method for deep models. The authors seem to quickly combine two works (Langford & Schapire, 2005 and Geifman & El-Yaniv, 2017) for their proposed solution. The novelty of the work is not enough without further addressing this. ", "strength_and_weaknesses": "Strengths:\n- The paper does a good work of explaining its scope. \n- The experiments are of high quality. Experiments are comprehensive and evaluate a lot of datasets. \n\nWeaknesses:\n- My main concern is the novelty of the paper. The paper proposes a new method for distribution shift detection. However, based on the description of the authors, the proposed method seems like a quick combination of two works (Langford & Schapire, 2005 and Geifman & El-Yaniv, 2017) without much modification. Maybe state clearly which efforts you made to adapt the two referenced works to the current task.\n- I feel the main idea and the motivation of the proposed method can be better explained intuitively with plain language. So the method can get better clarity. For example, “... find better summary statistics of the ID data inspired by generalization coverage bound…” (just an example, please ignore my terminology if I’m wrong).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NjrKGrvU-O", "reviewer": "Reviewer_RPBQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a distribution shift detection method, with the information of k-window data instances. The paper proposes a coverage-based method with a guaranteed bound, based on this, a further detection algorithm is proposed for efficient processing with the advantages of algorithmic complexity in terms of both space and time. The evaluation results also demonstrate the potential of the proposed technique.", "summary_of_the_review": "Overall, I enjoyed reading this paper, the proposed techniques should be sound and feasible. The evaluation is relatively comprehensive on the case of CIFAR and ImageNet. In addition, the authors also provide a formal analysis of the bound analysis,  as well as the detection complexity analysis of the proposed algorithms.\n\nEven though, the paper still posts a few concerns that the authors could consider for further enhancement.\n\n- The proposed methods rely on quite a few hyper-parameters, I would recommend add more discussion on their insights, the heuristic to choose them, as well as evaluating the impact of such selection.\n\n- During the evaluation, the authors mostly compared with KS and MMD methods, and simply believed that the single-instance-based methods e.g., for OoD detection would not work, which is not fully convincing to me. I would highly recommend adding comparisons with some SOTA instance-based OoD/Uncertainty detection liked methods, under the window k, for comparative analysis. This could be critical from my perspective, especially if the instance-based-OoD detection already works quite well, which is also efficient in some cases, e.g., under what conditions.\n\n- Regarding the evaluation scenario, I understand authors might try hard to try simple scenarios to simulate distribution shift, but the evaluated scenarios are quite artificial, which might be quite far away from real-world cases. I would recommend authors (1) considering some real-world cases, (2) as well as evaluating on more diverse tasks.\n\nFor example, the following paper could be a good reference.\n\n**WILDS: A Benchmark of in-the-Wild Distribution Shifts**\n\n***Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, Percy Liang***\n *Proceedings of the 38th International Conference on Machine Learning*\n, PMLR 139:5637-5664, 2021.", "strength_and_weaknesses": "Strength:\n\n- Important problem\n- Group-based distribution shift detection is less investigated, the proposed techniques are Sound and feasible solution\n- Some formal guarantees of the bound are analyzed\n- Extensive evaluation to demonstrate the potential usefulness\n- Promising results\n\nWeakness:\n\n- Evaluation is only performed on image data for classification tasks.\n- The scenarios of the distribution shifts are mostly simulated, not real scenarios from the real world.\n- Unclear about the insights of “k” selection and its relation to the population size of training data or the original data distribution P.\n- Unclear how to extend to streaming data cases.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3w2WfAs9wu4", "reviewer": "Reviewer_Mwu4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new out-of-distribution detection method when sampled are provided within a given window.  The core algorithm aims to find optimal coverage lower bound and the detection threshold given confidence parameter, and target coverage. The authors provide theoretical analysis and empirical studies on small-scale and large-scale datasets.", "summary_of_the_review": "The paper is theoretically motivated, sample-efficient compared to the baselines, and empirically performs well. However, the empirical evaluation can be further expanded. ", "strength_and_weaknesses": "\nStrengths\n- The method considers the window-based settings, which is relatively less explored in the literature.\n- The method is theoretically motivated and performs quite well in practice. \n\nWeaknesses\n- Lack empirical comparison with single-instance OOD detection methods. The paper mentions that \"Single-instance methods are trivially applicable to a window\". However, no methods are compared. What are the practical implications of \"not considering population statistics over the window\"? I wonder if authors provide empirical comparisons with representative methods in the literature, such as MaxLogit score [1] derived from the logit space and KNN score [2] derived from the feature embeddings.\n- Unlike the majority of instance-based methods in the literature, the proposed method is limited to window-based inputs. e.g., it might be better to change the title to indicate the specific set up.\n\n\n[1] Hendrycks et al., Scaling Out-of-Distribution Detection for Real-World Settings, ICML 2022\n[2] Sun et al., Out-of-Distribution Detection with Deep Nearest Neighbors, ICML 2022", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject