Test for non-negligible adverse shifts

Suppose we fit a predictive model on a training set and predict on a test set. Dataset shift, also known as data or population drift, occurs when training and test distributions are not alike [Kelly et al., 1999, Quionero-Candela et al., 2009]. This is essentially a sample mismatch problem. Some regions of the data space are either too sparse or absent during training and gain importance at test time. We want methods that alert users to the presence of unexpected inputs in the test set [Rabanser et al., 2019]. To do so, a measure of divergence between training and test set is required. Can we not use the many modern off-the-shelf multivariate tests of equal distributions for this?

One reason for moving beyond tests of equal distributions is that they are often too strict. They require high fidelity between training and test set everywhere in the input domain. However, not all changes in distribution are a cause for concern – some changes are benign. Practitioners distrust these tests because of false alarms. Polyzotis et al. [2019] comment:

statistical tests for detecting changes in the data distribution […] are too sensitive and also uninformative for the typical scale of data in machine learning pipelines, which led us to seek alternative methods to quantify changes between data distributions.

Even when the difference is small or negligible, tests of equal distributions reject the null hypothesis of no difference. Monitoring model performance and data quality is a critical part of deploying safe and mature models in production [Paleyes et al., 2020, Zhang et al., 2020]. An alarm should only be raised if a shift warrants intervention. Retraining models when distribution changes are benign is both costly and ineffective [Vovk et al., 2021]. To tackle these challenges, we propose D-SOS instead.

In comparing the test set to the training set, D-SOS pays more attention to the regions — typically, the outlying regions — where we are most vulnerable. To confront false alarms, it uses a robust test statistic, the weighted area under the receiver operating characteristic curve (WAUC). The weights in the WAUC discount the safe regions of the distribution. As best we know, this is the first time that the WAUC is being used as a test statistic in this context. The goal of D-SOS is to detect non-negligible adverse shifts. This is reminiscent of noninferiority tests [Wellek, 2010], widely used in healthcare to determine if a new treatment is in fact not inferior to an older one. Colloquially, D-SOS holds that the new sample is not substantively worse than the old sample, and not that the two are equal.

D-SOS moves beyond tests of equal distributions and lets users specify which notions of outlyingness to probe. The choice of the score function plays a central role in formalizing what we mean by worse. These scores can come from out-of-distribution (outlier) detection, two-sample classification, uncertainty quantification, residual diagnostics, density estimation, dimension reduction, and more. While some of these scores are underused and underappreciated in two-sample statistical tests, they can be more telling than the density-based scores.

In this paper, we make the following contribution. We derive D-SOS, a novel and robust two-sample test for no adverse shift, from tests of goodness-of-fit. The main takeaway is that given a generic method to assign an outlier score to a data point, D-SOS turns these scores into a two-sample test for no adverse shift. It converts arbitrary outlier scores into interpretable probabilities, namely $p-$values. The field is replete with tests of equal distribution and goodness-of-fit. We have comparatively fewer options for tests of no adverse shift. We have created an accompanying R package dsos for our method. In addition, all code and data used in this paper are publicly available.

For illustration, we apply D-SOS to the canonical iris dataset [Anderson, 1935]. The task is to classify the species of Iris flowers based on $d=4$ covariates (features) and $n=50$ observations for each species. We show how D-SOS helps diagnose false alarms. We highlight that (1) changes in distribution do not necessarily hurt predictive performance, and (2) points in the densest regions of the distribution can be the most difficult – unsafe – to predict.

We consider four tests of no adverse shift. Each test uses a different score. For two-sample classification, this score is the probability of belonging to the test set. For density-based out-of-distribution (OOD) detection, the score comes from isolation forest; this score is inversely related to the local density. For residual diagnostics, it is the out-of-sample (out-of-bag) prediction error from random forests. Finally, for confidence-based OOD detection, it is the standard error of the mean prediction from random forests, a proxy for prediction (resampling) uncertainty similar to [Schulam and Saria, 2019]. Only the first notion of outlyingness – two-sample classification – pertains to modern tests of equal distributions; the others capture other meaningful notions of adverse shifts. For all these scores, higher is worse: higher scores indicate that the observation is diverging from the desired outcome or that it does not conform to the training set.

For the subsequent tests, we split iris into 2/3 training and 1/3 test set. The train-test pairs correspond to two partitioning strategies: (1) random sampling and (2) in-distribution (most dense) examples in the test set. How do these sample splits fare with respect to the aforementioned tests? Let $s$ and $p$ denote $s-$value and $p-$value. The results are reported on the $s=-\,\log_{2}(p)$ scale because it is intuitive and lends itself to comparison. We return to the advantages of using $s-$value for comparison later. An $s-$value of $k$ can be interpreted as seeing $k$ independent coin flips with the same outcome – all heads or all tails – if the null is that of a fair coin [Greenland, 2019]. This conveys how incompatible the data is with the null.

In Figure 1, the case with (1) random sampling exemplifies the type of false alarms we want to avoid. Two-sample classification, standing in for tests of equal distributions, is incompatible with the null of no adverse shift (a $s-$value of around 8). But this shift does not carry over to the other tests. Residual diagnostics, density-based and confidence-based OOD detection are all fairly compatible with the view that the test set is not worse. Had we been entirely reliant on two-sample classification, we may not have realized that this shift is essentially benign. Tests of equal distributions alone give a narrow perspective on dataset shift.

Returning to Figure 1, density-based OOD detection does not flag the (2) in-distribution test set as expected. We might be tempted to conclude that the in-distribution observations are safe, and yet, the tests based on residual diagnostics and confidence-based OOD detection are fairly incompatible with this view. Some of the densest points are concentrated in a region where the classifier does not discriminate well: the species ‘versicolor’ and ‘virginica’ overlap. That is, the densest observations are not necessarily safe. Density-based OOD detection glosses over this: the trouble may well come from inliers that are difficult to predict. We get a more holistic perspective of dataset shift because of these complementary notions of outlyingness.

The theoretical framework builds on Zhang [2002]. Take an i.i.d. training set $X^{tr}=\{x_{i}^{tr}\}_{i=1}^{n^{tr}}$ and a test set $X^{te}=\{x_{i}^{te}\}_{i=1}^{n^{te}}$. Each dataset $X^{o}$ with origin $o\in\{tr(ain),te(st)\}$ lies in $d$-dimensional domain $\mathcal{X}\subseteq\mathbf{R}^{d}$ with sample sizes $n^{o}$, cumulative distribution function (CDF) $F^{o}_{X}$ and probability density function (PDF) $f^{o}_{X}$. Let $\phi:\mathcal{X}\rightarrow\mathcal{S}\subseteq\mathbf{R}$ be a score function and define the threshold score $s\in\mathcal{S}$. The proportion above the threshold $s$ in dataset $o$ is in effect the contamination rate $C^{o}(s)=\Pr\left(\phi(x_{i}^{o})\geq s\right)$. The contamination rate is the complementary CDF of the scores, $F^{o}(s)=1-C^{o}(s)$. As before, $F^{o}$ and $f^{o}$ now denote the CDF and PDF of the scores.

Consider the null hypothesis $\mathcal{H}_{0}:F^{te}_{X}=F^{tr}_{X}$ of equal distribution against the alternative $\mathcal{H}_{1}:F^{te}_{X}\neq F^{tr}_{X}$. In tandem, consider the null of equal contamination $\mathcal{H}_{0}^{s}:C^{te}(s)=C^{tr}(s)$ against the alternative $\mathcal{H}_{1}^{s}:C^{te}(s)\neq C^{tr}(s)$ at a given threshold score $s$. To evaluate goodness-of-fit, Zhang [2002] shows that testing $\mathcal{H}_{0}$ is equivalent to testing $\mathcal{H}_{0}^{s}$ for $\forall s\in\mathcal{S}$. If $z(s)$ is the relevant test statistic for equal contamination, a global test statistic $Z$ for goodness-of-fit can be constructed from $z(s)$, its local counterpart. One such $Z$ is

where $w(s)$ are threshold-dependent weights. For concision, we sometimes suppress the dependence on the threshold score $s$ and denote weights, contamination statistics and rates as $w$, $z$ and $C^{o}$ respectively. D-SOS differs from the $Z$ statistic in Equation (1) in three ways: the score function $\phi$, the weights $w$ and the contamination statistic $z$. We address each in turn.

D-SOS scores instances from least to most abnormal according to a specified notion of outlyingness. To be concrete, for density estimation, the negative log density is a natural score for outlyingness [Kandanaarachchi and Hyndman, 2021]. This property of the score function $\phi$ can be expressed as

for $x_{i},x_{j}\in\mathcal{X}$ and $\epsilon$, a (sufficiently small) approximation error. Accordingly, instances in high-density regions of the training set $X^{tr}$ (nominal points or inliers) score low; those in low-density regions (outliers) score high. Here, the score function $\phi$ can be thought of as a density-preserving projection. More generally, higher scores, e.g. wider prediction intervals and larger residuals, indicate worse outcomes; the higher the score, the more unusual the observation. The structure in $\phi$ is the catalyst for adjusting the weights $w$ and the statistic $z$.

D-SOS updates the weights $w$ to be congruent with the score function $\phi$. When projecting to the outlier subspace, high scores imply unusual points, whereas both tails are viewed as extremes in the Zhang framework. Univariate tests such as the Anderson-Darling and the Cramér-von Mises tests fit the framework in Equation (1): they make different choices for $\phi$, $z$ and $w$. These classical tests place more weight at the tails to reflect the severity of tail exceedances relative to deviations in the center of the distribution. D-SOS corrects for outliers being projected to the upper (right) tail of scores via the score function. The D-SOS weights $w$ are specified as

The weights in Equation (3) shift most of the mass from low to high-threshold regions. As a result, D-SOS is highly tolerant of negligible shifts associated with low scores, and conversely, it is attentive to the shifts associated with high scores. Low (high) thresholds map to high (low) contamination rates and low (high) values of the CDF, $F^{tr}_{X}$. At the lowest threshold, every point in the training set is an outlier; at the highest threshold, none is. Within this spectrum, high thresholds better reflect the assumption that the training set does not contain too many outliers¹¹1We do not assume that the training set only consists of inliers. It may be contaminated, but hopefully not too badly compromised i.e. it is clean enough to be the reference distribution.. Thus, we put more weights on high, rather than low, thresholds. Zhang [2002] posits other functional forms, but the quadratic relationship between weights and contaminations as in Equation (3) gives rise to one of the most powerful variants of the test and so, we follow suit.

D-SOS constructs a test statistic based on the score ranks, not on the levels. The weighted area under the receiver operating characteristic curve (WAUC) is a robust statistic that is invariant to changes in levels so long as the underlying ranking is unaffected. The WAUC, denoted $T$, can be written as

See Equation (1) in Hand [2009] for details. $T$ in Equation (4) is formally the D-SOS test statistic for adverse shift. The (W)AUC is also threshold-invariant, meaning that it averages (discriminative) performance over thresholds of varying importance. The upside is we do not have to commit to a single threshold. The downside is, if not careful, the (W)AUC summarizes performances over irrelevant regions e.g. low-threshold regions. As a generalization of the AUC, the WAUC puts non-uniform weights on thresholds [Li and Fine, 2010]. D-SOS seizes on this to give more weight to the outlying regions of the data²²2Weng and Poon [2008] also advocates for the WAUC as a performance metric for imbalanced datasets because it can capture disparate misclassification costs.. These data-driven (adaptive) weights conform to the training (reference) distribution, relieving us of the burden of introducing additional hyperparameters.

The null of no adverse shift $\mathcal{H}_{0}^{ds}$ is that most instances in the test set are not worse than those in the training set. The alternative $\mathcal{H}_{1}^{ds}$ is that the test set contains more outliers than expected, if the training set is the reference distribution. D-SOS specifies its null as $\mathcal{H}_{0}^{ds}:T_{0}\leq T\mid\mathcal{H}_{0}$ against the alternative $\mathcal{H}_{1}^{ds}:T_{0}>T\mid\mathcal{H}_{0}$. $T_{0}$ is the observed WAUC and $T\mid\mathcal{H}_{0}$, the WAUC under the null of exchangeable samples. When the test set is cleaner than the training set, tests of goodness-of-fit and of equal distributions both reject the null of no difference, whereas D-SOS by design does not reject its null of no adverse shift. These shifts do not trigger the alarm as they otherwise would had D-SOS been a two-tailed test.

We make a few remarks to further distinguish D-SOS from other two-sample statistical tests. Firstly D-SOS does not need to specify the equivalence margin, the minimum meaningful difference needed to sound the alarm [Wellek, 2010]. This margin is often a prerequisite of noninferiority tests and similar approaches³³3For example, Podkopaev and Ramdas [2022] sets in advance what drop in accuracy, say 5%, constitutes a non-negligible adverse shift.. Choosing this margin or minimum effect size is often a non-trivial task, requiring substantive domain knowledge [Betensky, 2019]. D-SOS sidesteps margin elicitation from experts and relies solely on the training set being an adequate reference distribution. Secondly, tests of equal distributions ignore that the training set precedes the test set, and not vice versa. D-SOS, like tests of goodness-of-fit, improve on the former because they use the training set as the reference distribution. Lastly, D-SOS deviates from tests of goodness-of-fit. It emphasizes robustness to fight false alarms, it narrows its scope to detecting adverse shifts, not any distribution shift, and it accomodates any outlier score⁴⁴4The score in Zhang [2002] is inspired from the likelihood ratio..

Outlier scores. Density ratios and class probabilities often serve as scores in comparing distributions [Menon and Ong, 2016] These scores, however, do not directly account for the predictive performance. Prediction intervals and residuals, on the other hand, do. Intuitively, they both reflect poor predictive performance in some regions of the feature space. Confidence-based OOD detection leans on this insight and tracks uncertain predictions e.g. Snoek et al. [2019], Berger et al. [2021]. This is in contrast to density-based OOD detection e.g. Morningstar et al. [2021]. The classical approach, which also accounts for the predictive performance, is based on residual diagnostics and underpin misspecification tests. Janková et al. [2020] is a recent example of this approach with a machine learning twist. Other methods such as trust scores can also flag unreliable predictions [Jiang et al., 2018]. Because all these scores represent distinct notions of outlyingness, the contrasts are often insightful. In this respect, D-SOS is in some sense a unifying framework. Bring your own outlier scores and D-SOS would morph into the equivalent two-sample test for no adverse shift.

Dimension reduction. In practice, the reconstruction errors from dimension reduction can separate inliers from outliers. Recently, Rabanser et al. [2019] uses dimension reduction, as a preprocessing step, to detect distributional shifts. Some methods gainfully rely on the supervised predictions for their low-rank representation [Cieslak and Chawla, 2009, Lipton et al., 2018]. This last approach, to add a cautionary note, entangles the supervised model, subject to its own sources of errors such as misspecification and overfitting, with dataset shift [Wen et al., 2014]. But it also points to the effectiveness of projecting to a lower and more informative subspace to circumvent the curse of dimensionality. Indeed, the classifier two-sample test uses univariate scores to detect changes in multivariate distributions [Cai et al., 2020]. Inspired by this approach, D-SOS uses outlier scores as a device for dimension reduction.

Statistical tests. The area under the receiver operating characteristic curve (AUC) has a long tradition of being used as a robust test statistic in two-sample comparison. Demidenko [2016] proposes an AUC-like test statistic as an alternative to the classical tests at scale because the latter “do not make sense with big data: everything becomes statistically significant” while the former attenuates the strong bias toward large sample size. D-SOS is firmly rooted in the tradition of two-sample comparison. Inference is at the sample level. At the instance level, we may want to check if a given test point is an outlier to the training set. Bates et al. [2021] for example tests for individual outliers via conformal $p-$values. Turning pointwise outlier score into an interpretable (standardized) measure such as a probability is a common and useful desideratum [Kriegel et al., 2009, 2011]. Podkopaev and Ramdas [2022], on the other hand, casts the problem of detecting harmful shifts in a sequential setting and controls for the false alarm rate due to continuous monitoring. In sequential settings, statistical process control e.g. [Qiu, 2020] is often used for a similar purpose.

In this section, we turn our attention to deriving valid $p-$values. Without loss of generality, let $\mathcal{D}=[X^{tr},X^{te}]$ be the pooled training and test set. The score function $\phi=\Phi(\mathcal{D},\lambda)$ is estimated from data $\mathcal{D}$ and hyperparameters $\lambda\in\Lambda$. This calibration procedure $\Phi:\mathcal{X}\times\Lambda\rightarrow\phi$ returns the requisite score function $\phi:\mathcal{X}\rightarrow\mathcal{S}\subseteq\mathbb{R}$. The asymptotic null distribution of the WAUC, however, is invalid when the same data is used both for calibration and scoring. We circumvent this issue with permutations, sample splitting, and/or out-of-bag predictions.

Permutations use the empirical, rather than the asymptotic, null distribution. The maximum number of permutations is set to $R=1000$. We refer to this variant as DSOS-PT. Unless stated otherwise, this is the default used in Section 6. For speed, DSOS-PT is implemented as a sequential Monte Carlo test, which terminates early when the resampling risk is unlikely to affect the final result materially [Gandy, 2009]. Even so, permutations can be computationally prohibitive.

A faster alternative, based on sample splitting, relies on the asymptotic null distribution. It incurs a cost in calibration accuracy in the first step because it holds out half the data for scoring in the second step. This tradeoff is common in two-sample tests, which requires calibration. We randomly split each dataset in half: $X^{tr}=X_{1}^{tr}\cup X_{2}^{tr}$ and $X^{te}=X_{1}^{te}\cup X_{2}^{te}$. The first halves are used for calibration, and the second for scoring. We describe this split-sample procedure in Algorithm 1, and refer to it as DSOS-SS in Section 6. Given the weights in Equation 3, the WAUC under the null $T\mid\mathcal{H}_{0}$ is asymptotically normally distributed as

with mean $=\frac{1}{12}$ and standard deviation $\sigma(n^{tr},n^{te})$, which depends on the sample sizes. Equation 5 follows trivially from results in Li and Fine [2010] with a little bit of tedious algebra – see Equation (9) therein for the variance.

A third option, an obvious extension to sample splitting, is to use cross-validation instead. In $k-$fold cross-validation, the number of folds $k$ mediates between calibration accuracy and inferential robustness. At the expense of refitting $k$ times, this approach uses most of the data for calibration and can leverage the asymptotic null distribution, provided that the scores are out-of-sample predictions. This strategy is also called cross-fitting in semiparametric inference. It combines the best of both worlds, namely calibration accuracy and inferential speed. We refer to this variant as DSOS-CV in Section 6. We show in simulations that this approach either matches or exceeds the performance of DSOS-PT and DSOS-SS.

We make the following pragmatic choices for ease of use; typically, the selected score functions perform well out-of-the-box with little to no costly hyperparameter tuning. For density-based OOD detection, we use isolation forest. To investigate other notions of outlyingness, we use random forests. As in Hediger et al. [2022], random forests allow us to use the out-of-sample variant of D-SOS (DSOS-CV) for free, so to speak. Out-of-bag predictions are viable surrogates for out-of-sample scores. This out-of-bag variant is, when feasible, often convenient as it improves on sample splitting, which sacrifices calibration accuracy for inferential robustness. Details about the experimental setup are in the supplementary material.

D-SOS is a wrapper to turn outlier scores into a statistical test. This framework, derived from tests of goodness-of-fit, detects non-negligible adverse shifts. It can confront the data with more pertinent hypotheses than tests of equal distribution. This works well when mapping to the relevant outlier subspace discriminates between safe and unsafe regions of the data distribution. Our method accommodates different notions of outlyingness. It lets users define, via a score function, what is meant by worse off. Besides the outlier scores explored in this paper, we stress that other sensible choices for the score functions $\phi$ and the weights $w$ abound. These can be adjusted to account for domain knowledge. Looking ahead, future research could investigate other weighting schemes. The functional form of the postulated weights could be worth tuning. Moreover, composite score function, which would combine several notions of outlyingness together, would enrich the types of hypotheses we can test. We imagine situations where we want to combine the strengths of confidence-based and density-based OOD detection into a single aggregate score for example.