# A unified framework for dataset shift diagnostics

Felipe Maia Polo
Department of Statistics
University of Michigan
United States of America
&Rafael Izbicki
Department of Statistics
Federal University of São Carlos
Brazil
&Evanildo Gomes Lacerda Jr
Trustly
Brazil
Juan Pablo Ibieta-Jimenez
Experian LatAm DataLab
Brazil
&Renato Vicente
Department of Applied Mathematics
Institute of Mathematics and Statistics
University of São Paulo
Brazil

###### Abstract

Supervised learning techniques typically assume training data originates from
the target population. Yet, in reality, _dataset shift_ frequently arises,
which, if not adequately taken into account, may decrease the performance of
their predictors. In this work, we propose a novel and flexible framework
called DetectShift111Our implementation for DetectShift can be found in
https://github.com/felipemaiapolo/detectshift. that quantifies and tests for
multiple dataset shifts, encompassing shifts in the distributions of
$(\mathbf{X},Y)$, $\mathbf{X}$, $Y$, $\mathbf{X}|Y$, and $Y|\mathbf{X}$.
DetectShift equips practitioners with insights into data shifts, facilitating
the adaptation or retraining of predictors using both source and target data.
This proves extremely valuable when labeled samples in the target domain are
limited. The framework utilizes test statistics with the same nature to
quantify the magnitude of the various shifts, making results more
interpretable. It is versatile, suitable for regression and classification
tasks, and accommodates diverse data forms—tabular, text, or image.
Experimental results demonstrate the effectiveness of DetectShift in detecting
dataset shifts even in higher dimensions222Corresponding author: Felipe Maia
Polo<EMAIL_ADDRESS>
_K_ eywords Dataset shift detection $\cdot$ Hypothesis testing $\cdot$
Transfer learning

##  1 Introduction

In machine learning applications, it is conventionally assumed that training
data originates from the distribution of interest. We say a dataset shift has
happened when that assumption does not hold. Formally, we have dataset shift
when the joint distribution of features ($\mathbf{X}$) and labels ($Y$)
associated with the training sample, also known as the source distribution,
$P^{(1)}_{\mathbf{X},Y}$, and the distribution of interest, also known as the
target distribution, $P^{(2)}_{\mathbf{X},Y}$, are different. Real-world
applications, spanning fields like finance [41], health [9], technology [23],
and physics [10], often grapple with the challenges posed by dataset shifts.
Unfortunately, dataset shift may substantially decrease the predictive power
of machine learning models if it is not adequately addressed [42].

When labeled data from the target distribution is scarce, addressing dataset
shifts typically necessitates assumptions about the relationship between the
source and target distributions. Different assumptions are translated into
different types of shift [29], and every kind of shift demands specific
adaptation methods [36, 42, 28]. For instance, if $P^{(1)}_{\mathbf{X}}\neq
P^{(2)}_{\mathbf{X}}$ but $P^{(1)}_{Y|\mathbf{X}}=P^{(2)}_{Y|\mathbf{X}}$,
dataset shift adaptation can be performed by using importance weighting on the
training data [42, 15, 27]. Similarly, if $P^{(1)}_{Y}\neq P^{(2)}_{Y}$ but
$P^{(1)}_{\mathbf{X}|Y}=P^{(2)}_{\mathbf{X}|Y}$, dataset shift adaptation can
be performed by importance weighting [24] or re-calibrating posterior
probabilities via Bayes’ theorem [36, 45]. Therefore, to successfully adapt
prediction algorithms in a dataset shift setting, practitioners need to know
not only _if_ dataset shift occurs but also _which type_ of shift happens for
the data at hand.

This study introduces DetectShift, a novel unified framework capable of
accurately quantifying and testing for diverse types of dataset shifts. This
framework provides valuable insights to practitioners on optimally handling
changes in the data, particularly in scenarios where labeled samples from the
target domain are scarce. By using our framework, practitioners can detect
specific types of shifts. Consequently, they can use that information to use
both source and target data to retrain or adapt their predictors, which is
especially appealing in situations where naive model retraining using only
data points from $P^{(2)}_{\mathbf{X},Y}$ is not feasible333See [36, 24, 42,
28] for some examples on how to retrain or adapt predictors using not only
target samples. . In Section 4, we show in practice one example of how the
insights provided by DetectShift can help practitioners in a prediction task
in which target-labeled samples are not used to retrain the classifier.

The remainder of this paper is organized as follows. Firstly, in Section 2, we
provide an overview of recent works relevant to our research, highlighting our
contributions to the existing literature. Moving on to Section 3, we present
our framework called DetectShift, explaining its conceptual basis and
rationale. To demonstrate the effectiveness of our approach across various
scenarios, we apply DetectShift to both artificial and real data in Section 4.
Finally, in the concluding sections, we thoroughly discuss our findings,
contributions, limitations, and potential avenues for further exploration.

###  1.1 Contributions

The main contributions of DetectShift are that:

  * •

It facilitates quantification and formal testing of shifts in the
distributions of $(\mathbf{X},Y)$, $\mathbf{X}$, $Y$, $\mathbf{X}|Y$, and
$Y|\mathbf{X}$. Identifying different types of shifts helps practitioners gain
insights about changes in their data. Those insights allow them to leverage
source and target data to retrain or adapt their predictors3, which is
especially beneficial when target labels are scarce.

  * •

It utilizes test statistics with the same nature to quantify each type of
dataset shift, enabling practitioners to compare the magnitude of different
shifts and gain meaningful insights. Furthermore, empirical evidence
demonstrates that these test statistics result in powerful shift detectors
even in higher dimensions.

  * •

It can be applied to regression and classification tasks. Additionally, it can
be employed in conjunction with virtually any type of data, including tabular,
text, and image data.

##  2 Related work

Dataset shift detection methods can have different objectives. For instance,
specific approaches monitor the test error of a predictor over time,
triggering an alarm when there is a significant degradation in its performance
[11, 50, 31]. Other approaches are specifically designed to provide a deeper
understanding of how data distribution has changed by detecting specific types
of shifts, e.g., changes in the distribution of features. Our research aligns
closely with the latter category, which we will delve into next.

Source and target distributions can be different in many ways. For instance,
if $P^{(1)}_{Y}\neq P^{(2)}_{Y}$ but
$P^{(1)}_{\mathbf{X}|Y}=P^{(2)}_{\mathbf{X}|Y}$, then the dataset shift can be
characterized as label shift. If labels from the target domain are
unavailable, label shift detection and quantification are not straightforward
but can be accomplished under some conditions [24, 45]. The method proposed by
Lipton et al. [24], for example, exploits arbitrary black box classifiers and
their confusion matrices to estimate $P^{(2)}_{Y}$. In a different direction,
various methods are available when we are interested in detecting or
understanding changes in the marginal distribution of possibly high-
dimensional features $\mathbf{X}$. Detecting shifts in $P_{\mathbf{X}}$ can be
solved using two-sample tests [34, 25], and some extensions are possible. For
example, Jang et al. [16] proposes an online approach in which data is seen
sequentially, and Wijaya et al. [48] proposes extracting concept-based
features from images (e.g., rotation, shape) and then testing for shifts of
those concepts. Moreover, Ginsberg et al. [12] proposes a method for harmful
covariate shift detection while Luo et al. [26] proposes a martingale-based
approach in which false alarms are controlled over time. For objectives
centered on detecting shifts in conditional distributions like
$P_{Y|\mathbf{X}}$, several methods emerge. For instance, Schrouff et al. [37]
proposes using a conditional independence test to detect shifts in conditional
distributions in the context of algorithmic fairness. In contrast, Vovk [46]
proposes a martingale-based approach to detect online changes in
$P_{\mathbf{X}|Y}$ considering classification problems.

While identifying specific types of shifts is essential, it is typically
insufficient for making informed decisions. Ideally, practitioners should
access a unified framework that evaluates multiple dataset shifts, guiding
them on optimal next steps. That framework would also allow the practitioner
to compare the strength of the several shift types, permitting a more
interpretable analysis. Webb et al. [47] proposes a framework with those
characteristics. The authors use the total variation (TV) distance between two
probability distributions to measure shifts in $P_{Y}$, $P_{\mathbf{X}}$,
$P_{Y|\mathbf{X}}$, and $P_{\mathbf{X}|Y}$, to provide the practitioner with
valuable insights. Their approach is limited, however. Estimating the TV
distance between two probability distributions is challenging when variables
are not discrete or their dimensionality is high (see Figure 3 in our
experiments section). Moreover, Webb et al. [47] does not suggest using formal
hypothesis testing. Thus, false alarm control is not guaranteed. Building upon
Webb et al. [47], our work augments their framework, offering adaptability to
high-dimensional/continuous data and integrating rigorous hypothesis testing.

##  3 Methodology

We observe two datasets, $\mathcal{D}^{(1)}$ and $\mathcal{D}^{(2)}$, where

$\mathcal{D}^{(i)}=\left\\{\left(\mathbf{X}^{(i)}_{1},Y^{(i)}_{1}\right),\ldots,\left(\mathbf{X}^{(i)}_{n^{(i)}},Y^{(i)}_{n^{(i)}}\right)\right\\},$

for $i=1,2$. We assume that all observations from the same dataset are i.i.d.
and that the datasets are independent of each other. We denote by
$P^{(i)}_{\mathbf{X},Y}$ the distribution associated with an observation from
the $i$-th dataset, where $i=1$ stands for source and $i=2$ for the target. We
aim to quantify and test which types of dataset shifts occur from source to
target domain. The null hypotheses we want to test are

  * •

[Total Dataset Shift]
$H_{0,\text{D}}:P^{(1)}_{\mathbf{X},Y}=P^{(2)}_{\mathbf{X},Y}~{}~{}$

  * •

[Feature Shift]
$H_{0,\text{F}}:P^{(1)}_{\mathbf{X}}=P^{(2)}_{\mathbf{X}}~{}~{}$

  * •

[Response Shift] $H_{0,\text{R}}:P^{(1)}_{Y}=P^{(2)}_{Y}~{}~{}$

  * •

[Conditional Shift - Type 1]
$H_{0,\text{C1}}:P^{(1)}_{\mathbf{X}|Y}=P^{(2)}_{\mathbf{X}|Y}~{}~{}$
($P^{(2)}_{Y}$\- almost surely)

  * •

[Conditional Shift - Type 2]
$H_{0,\text{C2}}:P^{(1)}_{Y|\mathbf{X}}=P^{(2)}_{Y|\mathbf{X}}~{}~{}$
($P^{(2)}_{\mathbf{X}}$\- almost surely)

Section 3.1 describes how to obtain statistics that can quantify the amount of
each type of dataset shift and Section 3.2 shows how to use the statistics to
test each type of shift’s occurrence formally.

###  3.1 Test statistics

Our statistics are based on the Kullback-Leibler (KL) divergence [20, 32], a
well-known measure to describe discrepancies between probability measures.
Formally, the KL divergence between two probability distributions $P$ and $Q$
is defined as

$\textup{KL}(P||Q):=\int\log\left(\frac{dP}{dQ}\right)dP,$

where $\frac{dP}{dQ}$ is the Radon–Nikodym (R-N) derivative of $P$ with
respect to $Q$. If both $P$ and $Q$ are (Lebesgue) continuous distributions,
the R-N derivative is simply a density ratio $p/q$. For the R-N derivative to
be well defined, we need $P$ to be absolutely continuous with respect to $Q$
[32], meaning that the support of $P$ is a subset of the support of $Q$. From
now on, we assume that $P^{(2)}_{\mathbf{X},Y}$ is absolutely continuous with
respect to $P^{(1)}_{\mathbf{X},Y}$. Then, we use the following quantities to
measure each of the shifts described at the beginning of Section 3:

  * •

[Total Dataset Shift]
$\textup{KL}_{\mathbf{X},Y}:=\textup{KL}(P^{(2)}_{\mathbf{X},Y}||P^{(1)}_{\mathbf{X},Y})$

  * •

[Feature Shift]
$\textup{KL}_{\mathbf{X}}:=\textup{KL}(P^{(2)}_{\mathbf{X}}||P^{(1)}_{\mathbf{X}})$

  * •

[Response Shift] $\textup{KL}_{Y}:=\textup{KL}(P^{(2)}_{Y}||P^{(1)}_{Y})$

  * •

[Conditional Shift - Type 1]
$\textup{KL}_{\mathbf{X}|Y}:=\mathbb{E}_{P^{(2)}_{Y}}\left[\textup{KL}(P^{(2)}_{\mathbf{X}|Y}||P^{(1)}_{\mathbf{X}|Y})\right]$

  * •

[Conditional Shift - Type 2]
$\textup{KL}_{Y|\mathbf{X}}:=\mathbb{E}_{P^{(2)}_{\mathbf{X}}}\left[\textup{KL}(P^{(2)}_{Y|\mathbf{X}}||P^{(1)}_{Y|\mathbf{X}})\right]$

The following proposition states that we can rewrite the null hypotheses we
want to test in terms of the quantities above.

######  Proposition 1.

The hypotheses $H_{0,\text{D}}$, $H_{0,\text{F}}$, $H_{0,\text{R}}$,
$H_{0,\text{C1}}$, and $H_{0,\text{C2}}$ can be rewritten equivalently as
follows

$H_{0,\text{D}}:\textup{KL}_{\mathbf{X},Y}=0,~{}~{}~{}~{}H_{0,\text{F}}:\textup{KL}_{\mathbf{X}}=0,~{}~{}~{}~{}H_{0,\text{R}}:\textup{KL}_{Y}=0$
$H_{0,\text{C1}}:\textup{KL}_{\mathbf{X}|Y}=0,~{}~{}~{}~{}~{}H_{0,\text{C2}}:\textup{KL}_{Y|\mathbf{X}}=0$

The proof follows from the elementary KL divergence properties [32], e.g.,
$\textup{KL}(P||Q)=0$ if and only if $P=Q$. For the conditional shifts, see
that $\textup{KL}(P^{(2)}_{Y|\mathbf{X}}||P^{(1)}_{Y|\mathbf{X}})$ and
$\textup{KL}(P^{(2)}_{\mathbf{X}|Y}||P^{(1)}_{\mathbf{X}|Y})$ are non-negative
random variables, consequently, their expected values are zero if and only if
they are zero almost surely (with probability one).

To quantify and test the different types of shift, we use estimators of the
parameters $\textup{KL}_{\mathbf{X},Y}$, $\textup{KL}_{\mathbf{X}}$,
$\textup{KL}_{Y}$, $\textup{KL}_{\mathbf{X}|Y}$, and
$\textup{KL}_{Y|\mathbf{X}}$ as test statistics. That is a reasonable choice
because (i) our null hypotheses can be equivalently written in terms of such
estimable parameters, and (ii) the magnitude of the statistics is directly
related to the shift intensities. These suggest that tests based on these
statistics will be powerful in detecting shifts. Moreover, all parameters are
integrals computed using the target distribution. Thus, they give more weight
to regions of the feature/label space to which most target data points belong,
letting us focus on regions that matter.

To estimate $\textup{KL}_{\mathbf{X},Y}$, $\textup{KL}_{\mathbf{X}}$, and
$\textup{KL}_{Y}$, we first use444When $Y$ is discrete, $\textup{KL}_{Y}$ can
also be estimated by using a plug-in estimator described in the appendix.
training data and the probabilistic classification method for density ratio
estimation [44, 7], also known as odds-trick, to estimate the Radon–Nikodym
derivative between the two probability distributions. Then, we use test data
to estimate the divergences. More precisely, we first create the augmented
dataset

$\displaystyle\mathcal{D}=\left\\{\left(\mathbf{X}_{1},Y_{1},Z_{1}\right),\ldots,\left(\mathbf{X}_{n},Y_{n},Z_{n}\right)\right\\},$

where each $(\mathbf{X}_{k},Y_{k})$ corresponds to a different observation
taken from $\mathcal{D}^{(1)}\cup\mathcal{D}^{(2)}$ and $Z_{k}\in\\{1,2\\}$
indicates from which dataset $(\mathbf{X}_{k},Y_{k})$ comes from. We then
randomly split $\mathcal{D}$ into two sets: $\mathcal{D}^{tr}$ (training set)
and $\mathcal{D}^{te}$ (test set). We use $\mathcal{D}^{tr}$ to train a
probabilistic classifier that predicts $Z$. The features used to predict $Z$
are (i) $(\mathbf{X},Y)$ to estimate the amount of total dataset shift
($\textup{KL}_{\mathbf{X},Y}$), (ii) $\mathbf{X}$ to estimate the amount of
feature shift ($\textup{KL}_{\mathbf{X}}$), and (iii) $Y$ to estimate the
amount of response shift ($\textup{KL}_{Y}$). The estimated Radon–Nikodym
derivative in the case of total dataset shift (the other ones are analogous)
is given by

$\widehat{\frac{dP_{\mathbf{X},Y}^{(2)}}{dP_{\mathbf{X},Y}^{(1)}}}(\mathbf{x},y):=\frac{n_{tr}^{(1)}}{n_{tr}^{(2)}}\frac{\widehat{\mathbb{P}}(Z=2|\mathbf{X}=\mathbf{x},Y=y)}{\widehat{\mathbb{P}}(Z=1|\mathbf{X}=\mathbf{x},Y=y)},$

where $\widehat{\mathbb{P}}$ denotes the trained probabilistic classifier and
$n_{tr}^{(i)}$ is the number of samples from population $i$ in
$\mathcal{D}^{tr}$. If target-labeled samples are scarce, training the
classifier $\widehat{\mathbb{P}}$ from scratch can be challenging when
$\mathbf{X}$ is high-dimensional. However, if target unlabeled samples are
abundant, one possible solution is first training a classifier only depending
on $\mathbf{X}$ and then using
$h(\mathbf{x})=\widehat{\mathbb{P}}(Z=2|\mathbf{X}=\mathbf{x})$ to reduce the
dimensions of $\mathbf{X}$ before training the classifier dependent on both
$\mathbf{X}$ and $Y$. This solution does not affect the reliability of our
method since false alarm control is not affected.

Finally, we use empirical averages555The same approach is used to estimate
divergences by Sønderby et al. [40] in the context of generative models, for
example. over the test dataset $\mathcal{D}^{te}$ to estimate the KL
divergence (again in the case of total dataset shift; the other ones are
analogous):

$\widehat{\textup{KL}}_{\mathbf{X},Y}:=\frac{1}{|\mathcal{D}^{te}_{2}|}\sum_{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}^{te}_{2}}\log\left(\widehat{\frac{dP_{\mathbf{X},Y}^{(2)}}{dP_{\mathbf{X},Y}^{(1)}}}(\mathbf{X}_{k},Y_{k})\right),$

where
$\mathcal{D}^{te}_{2}:=\\{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}^{te}:Z_{k}=2\\}$
denotes the test samples from the second population.

This approach however cannot be used to estimate $\textup{KL}_{\mathbf{X}|Y}$
or $\textup{KL}_{Y|\mathbf{X}}$. Instead, we rely on the KL divergence
decomposition, given in the following proposition extracted from Polyanskiy
and Wu [32] (Theorem 2.13). To keep this text as self-contained as possible,
we include a proof in the appendix.

######  Proposition 2.

Let $\textup{KL}_{Y}$, $\textup{KL}_{X}$, $\textup{KL}_{Y|X}$,
$\textup{KL}_{X|Y}$, $\textup{KL}_{X,Y}$ be defined as they were in Section
3.1. Then

$\displaystyle\textup{KL}_{\mathbf{X},Y}$
$\displaystyle=\textup{KL}_{Y|\mathbf{X}}+\textup{KL}_{\mathbf{X}}$
$\displaystyle=\textup{KL}_{\mathbf{X}|Y}+\textup{KL}_{Y}$

This result shows that the KL divergences of the conditional distributions can
be estimated via
$\widehat{\textup{KL}}_{\mathbf{X}|Y}:=\widehat{\textup{KL}}_{\mathbf{X},Y}-\widehat{\textup{KL}}_{Y}~{}~{}\text{
and
}~{}~{}\widehat{\textup{KL}}_{Y|\mathbf{X}}:=\widehat{\textup{KL}}_{\mathbf{X},Y}-\widehat{\textup{KL}}_{\mathbf{X}}.$

###  3.2 Hypothesis Testing

Once we have statistics that can quantify the magnitude of different types of
dataset shifts, we can use them to formally test the hypotheses described in
Section 3.1. In this section, $Y$ can be discrete or continuous, except when
obtaining the $p$-values for the hypothesis
$P^{(1)}_{\mathbf{X}|Y}=P^{(2)}_{\mathbf{X}|Y}$, in which we assume it is
discrete. This is needed since Algorithm 1, in the appendix, relies on this
assumption. If $Y$ is continuous or has few repeated values, the conditional
shift of type 1 can be tested by discretizing/binning the label for computing
the statistic and applying the algorithm666Binning is not needed when training
the classifiers though. – we give more details and references at the end of
this section.

Consider the datasets $\mathcal{D}^{te}$ and $\mathcal{D}^{te}_{2}$ as defined
in Section 3.1, and let $T(\mathcal{D}^{te}_{2})$ be a test statistic of
interest computed using $\mathcal{D}^{te}_{2}$. Namely,
$T(\mathcal{D}^{te}_{2})$ can represent any of the following random
quantities, depending on which type of shift we are testing for:
$\widehat{\textup{KL}}_{Y}$, $\widehat{\textup{KL}}_{X}$,
$\widehat{\textup{KL}}_{Y|X}$, $\widehat{\textup{KL}}_{X|Y}$,
$\widehat{\textup{KL}}_{X,Y}$. We test each of the hypotheses of interest by
computing a $p$-value of the form

$\displaystyle
p(\mathcal{D}^{te})=\frac{1+\sum_{j=1}^{B}\mathbb{I}\left[T(\mathcal{D}^{te}_{2})\leq
T\left(\widetilde{\mathcal{D}}^{{te}^{(j)}}_{2}\right)\right]}{B+1},$ (1)

where each $\widetilde{\mathcal{D}}^{{te}^{(j)}}_{2}$ is a modified version of
$\mathcal{D}^{te}_{2}$, which can depend on the whole test set
$\mathcal{D}^{te}$. The modification that is done depends on the hypothesis we
are testing:

  * •

To test the hypotheses related to unconditional distributions
($H_{0,\text{D}},H_{0,\text{F}}$ and $H_{0,\text{R}}$),
$\widetilde{\mathcal{D}}^{{te}^{(j)}}_{2}$ is obtained randomly permuting
$Z_{k}$’s on $\mathcal{D}^{te}$ and then selecting the samples with $Z_{k}=2$
to form the modified version of $\mathcal{D}^{te}_{2}$. In this case, $p$ is
the $p$-value associated with a permutation test, a method commonly used to
perform two-sample tests [22].

  * •

To test $H_{0,\text{C1}}$, $\widetilde{\mathcal{D}}^{{te}^{(j)}}_{2}$ is
obtained randomly permuting the values of $Z_{k}$’s _within each level of $Y$_
on $\mathcal{D}^{te}$ and then selecting the samples with $Z_{k}=2$ to form
the modified version of $\mathcal{D}^{te}_{2}$. Thus, we require $Y$ to be
discrete to apply this test. In this case, $p$ is the $p$-value associated
with a _conditional independence_ local permutation test [17].

  * •

To test $H_{0,\text{C2}}$, we first estimate the conditional distribution of
$Y|\mathbf{X}$ using the whole training set $\mathcal{D}^{tr}$ of labeled
samples. Let $Q_{Y|\mathbf{X}}$ denote such an estimate, which can be obtained
using any probabilistic classifier, such as logistic regression, neural
networks, CatBoost classifier [33], or conditional density estimators [14] and
GANs [3] if $Y$ is continuous. We then obtain
$\widetilde{\mathcal{D}}^{{te}^{(j)}}_{2}$ by replacing each $Y_{k}$ in
$\mathcal{D}^{te}_{2}$ by a random draw from
$Q_{Y|\mathbf{X}=\mathbf{X}_{k}}$. This test is known as the conditional
randomization test (CRT) [5, 4].

Figure 1: DetectShift in a nutshell. First, data are sampled from source and
target distributions, mixed together, and split into a training and a test
set. Then, using the training set, the Radon–Nikodym (R-N) models are trained,
and all the test statistics are computed using the test set. Finally,
$p$-values to conduct the tests are obtained through simulation procedures.

Algorithm 1, in the appendix, details the steps to obtain the $p$-values for
each case. For all the cases, we assume the procedure involving the training
of probabilistic classifiers, described in Section 3.1, has already been
executed. That is, we have a test statistic $T$ for every test we want to
perform. Also, for the case we are testing for conditional shift type 2, we
assume the estimated conditional distribution $Q_{Y|\mathbf{X}}$ has been
computed. We fix a significance level $\alpha\in(0,1)$, and after calculating
the $p$-value $p$ for a specific null hypothesis of interest, reject that
hypothesis if $p\leq\alpha$. Figure 1 summarizes how our framework,
DetectShift, works.

The following proposition shows that such tests are valid (that is, they
control Type I error rate). In other words, false alarms are controlled. The
only exception is the test for $H_{0,\text{C2}}$, which approximately controls
Type I error probabilities as long as $Q_{Y|\mathbf{X}}$ is a good
approximation of $P^{(2)}_{Y|\mathbf{X}}$. For the following result, we
consider that $T$ and $Q_{Y|\mathbf{X}}$ are given and fixed, as both are
obtained from the training set. Also, we make sure that
$(T(\mathcal{D}^{te}_{2}),T(\widetilde{\mathcal{D}}^{{te}^{(1)}}_{2}),\cdots,T(\widetilde{\mathcal{D}}^{{te}^{(B)}}_{2}))$
has no repeated values by adding small centered Gaussian noises777This step is
performed to break ties among data modifications, making it easy to show
Type-I error is controlled. to $T(\mathcal{D}^{te}_{2})$ and
$T(\widetilde{\mathcal{D}}^{{te}^{(j)}}_{2})$, for every $j$.

######  Proposition 3.

Let $p(\mathcal{D}^{te})$ be a $p$-value obtained from Algorithm 1 (appendix)
with fixed $T$ and $Q_{Y|\mathbf{X}}$. Then, for every $\alpha\in(0,1)$,

  * •

Under $H_{0,\text{D}},H_{0,\text{F}}$,$H_{0,\text{R}}$, and $H_{0,\text{C1}}$
(if $Y$ is discrete),

$\mathbb{P}(p(\mathcal{D}^{te})\leq\alpha)\leq\alpha$

  * •

Under $H_{0,\text{C2}}$

$\mathbb{P}(p(\mathcal{D}^{te})\leq\alpha)\leq\alpha+\mathbb{E}_{\bar{P}^{(2)}_{\mathbf{X}}}\left[d_{\text{TV}}(\bar{Q}_{Y|\mathbf{X}},\bar{P}_{Y|\mathbf{X}})\right],$

where $d_{\text{TV}}$ is the total variation distance,
$\bar{P}^{(2)}_{\mathbf{X}}:=\prod_{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}_{2}^{te}}P^{(2)}_{\mathbf{X}_{k}}$,
$\bar{Q}_{Y|\mathbf{X}}:=\prod_{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}_{2}^{te}}Q_{Y|\mathbf{X}=\mathbf{X}_{k}}$,
and
$\bar{P}_{Y|\mathbf{X}}=\prod_{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}_{2}^{te}}P^{(2)}_{Y|\mathbf{X}=\mathbf{X}_{k}}$.

Here, $\prod$ denotes products of probability distributions. Proposition 3
borrows well-studied results from the Statistics literature. The results for
$H_{0,\text{D}}$, $H_{0,\text{F}}$, and $H_{0,\text{R}}$ are directly obtained
by the fact that we use a permutation test [22], while the result for
$H_{0,\text{C1}}$ is obtained because of properties of local permutation [17]
and the result for $H_{0,\text{C2}}$ is obtained by adapting the results of
Berrett et al. [4] (Theorem 4) to our context. Suppose $Y$ is continuous or
has few repeated values. In that case, if we discretize/bin it to test the
conditional shift of type 1, our approach leads to an approximate test for
$H_{0,\text{C1}}$ in the sense it approximately controls the Type I error. See
Kim et al. [17] (Theorems 2 and 3) for more details. To make this work self-
contained, we include a proof for Proposition 3 in the appendix.

##  4 Experiments

This section presents numerical experiments with both artificial and real
data. In all the experiments in which $Y$ is discrete, we use the plug-in
estimator (appendix) to estimate $\textup{KL}_{Y}$.

###  4.1 Artificial Data Experiments

####  4.1.1 Detecting different types of shifts in isolation

Figure 2: Power surfaces. In these experiments, $\delta$ controls response
shift, $\gamma$ controls conditional shift 1, $\lambda$ controls feature
shift, and $\theta$ controls conditional shift 2. While the tests can control
Type I errors, their power gets close to 1 when the shifts are bigger.
Moreover, our procedure can detect the types of shifts in isolation.
Therefore, the novel unified framework can reliably detect different types of
dataset shifts.

In the first experiment, we set

$P^{(1)}_{Y}=\textup{Ber}(1/2),~{}~{}P^{(2)}_{Y}=\textup{Ber}(1/2+\delta)$

and

$P^{(1)}_{X|Y}=\mathcal{N}(Y\cdot
1_{d},\textup{I}_{d}),~{}~{}P^{(2)}_{X|Y}=\mathcal{N}\left((Y+\gamma)\cdot
1_{d},\textup{I}_{d}\right),$

where $\textup{Ber}(p)$ denotes the Bernoulli distribution with mean $p$,
$1_{d}$ denotes a vector of ones of size $d=3$, $\textup{I}_{d}$ the identity
matrix of dimension $d=3$, and $\mathcal{N}(\mu,\Sigma)$ denotes the normal
distribution with mean vector $\mu$ and covariance matrix $\Sigma$. This way,
$\delta$ controls the amount of response shift, while $\gamma$ controls the
amount of conditional shift of type 1. Indeed, it is possible to show that
$\textup{KL}_{Y}$ positively depends only on $|\delta|$ while
$\textup{KL}_{X|Y}$ positively depends only on $|\gamma|$. In the second
experiment, we set

$P^{(1)}_{X}=\mathcal{N}(0,1),~{}~{}P^{(2)}_{X}=\mathcal{N}(\lambda,1)$

and

$P^{(1)}_{Y|X}=\mathcal{N}(X,1),~{}~{}P^{(2)}_{Y|X}=\mathcal{N}(X+\theta,1),$

where $\mathcal{N}(\mu,\sigma^{2})$ denotes the normal distribution with mean
$\mu$ and variance $\sigma^{2}$. In this way, $\lambda$ controls the amount of
feature shift, while $\theta$ controls the amount of conditional shift of type
2. Indeed, it is possible to show that $\textup{KL}_{X}$ positively depends
only on $|\lambda|$ while $\textup{KL}_{Y|X}$ positively depends only on
$|\theta|$.

We vary $(\delta,\gamma)$ and $(\lambda,\theta)$ in a grid of points for
experiments 1 and 2, respectively. For each point in the grid, we perform 100
Monte Carlo simulations to estimate the tests’ powers, that is, the
probabilities of rejecting the null hypotheses. For each pair
$(\delta,\gamma)$ or $(\lambda,\theta)$ and Monte Carlo simulation, we: (i)
draw training and test sets, from both joint distributions, with size 2500
each; (ii) train a logistic regression888We use Scikit-Learn’s [30] default
configuration with no hyperparameter tuning. model as a probabilistic
classifier to estimate the Radon-Nikodym derivatives using the training sets;
(iii) use the test set from the target population to estimate
$\textup{KL}_{X,Y},$ $\textup{KL}_{X|Y}$ or $\textup{KL}_{Y|X}$, and
$\textup{KL}_{Y}$ or $\textup{KL}_{\mathbf{X}}$; (iv) and use the test set to
calculate the $p$-values using999For the conditional randomization test, we
train a linear regression model with Gaussian errors to estimate the
conditional distribution of $Y$ given $X$ using the full training set.
Algorithm 1 in the appendix setting $B=100$; (v) reject the null hypothesis if
the $p$-value is smaller than the level of significance $\alpha=5\%$.

Figure 2 shows the power estimates for each test as a function of
$(\delta,\gamma)$ or $(\lambda,\theta)$. Our procedure to test the presence of
different types of dataset shift is well-behaved: the power is close to the
nominal level $\alpha=5\%$ when $(\delta,\gamma)$ or $(\lambda,\theta)$ is
close to the origin, i.e., when no shift happens and grows to 1 when
$||(\delta,\gamma)||$ or $||(\lambda,\theta)||$ gets larger. Moreover, our
procedure could also detect types of shifts in isolation: the power of our
tests increases for conditional shift (types 1 and 2) and response/feature
shift detection when increasing $|\gamma|$ or $|\lambda|$ and $|\delta|$ or
$|\gamma|$ separately. As expected, the tests are not affected by the shifts
that are not being tested at that moment.

In these experiments, we showed that the novel unified framework could
reliably detect different dataset shifts in isolation.

####  4.1.2 Comparisons with existing approaches

Now, we compare our framework with existing methods for detecting shifts. We
do this by comparing the power of the different hypotheses tests fixing
$\alpha=5\%$. For this experiment, we use the same data-generating process
used in the first two experiments and set the sample sizes of training and
test sets to 500. Moreover, we use 200 Monte Carlo simulations to estimate
power and set $B=100$ for Algorithm 1. When our objective is to detect
response and feature shifts, we vary $\delta$ and $\lambda$ but fix
$\gamma=\theta=0$; when we aim to see both types of conditional shifts, we
vary $\gamma$ and $\theta$ but set $\delta=\lambda=0$.

The main alternative approach we compare our method with is the total
variation (TV) approach proposed by Webb et al. [47], quantifying different
types of dataset shift. To apply their method, we discretized the data and
used our Algorithm 1 (appendix) to obtain $p$-values. When testing for
response shift, we also include comparisons with a Z-test to compare two
proportions [22], a $\chi^{2}$ test [34], and a classification-based two-
sample test [25]. When testing for feature shift, we also include comparisons
with a Kolmogorov-Smirnov (KS) test [18, 39], an MMD-based test [13, Corollary
16], and a classification-based two-sample test [25]. For the classification-
based two-sample tests, we use Lopez-Paz and Oquab [25]’s formulation to
obtain the $p$-values. Finally, when we test for conditional shifts 1 and 2,
we include two instances of the local permutation test101010Permuting data
within each level of $Y$. (LPT) [17] and the conditional randomization test
(CRT) [4, 5, 3] using statistics based on the classification approach [25].
More details can be found in the appendix.

Figure 3: Comparing our framework with existing approaches plotting their
power curves when $\alpha=5\%$. Our method had power curves similar to the
alternative approaches when testing for response and feature shifts. However,
our method achieved significantly higher power when testing both conditional
shifts. In summary, (i) our approach has the advantage of being unified, i.e.,
a single framework is used to test all hypotheses using test statistics with
the same nature, and (ii) when compared to specialized tests, the novel
unified framework does not lose in power when detecting marginal shifts while
it wins when detecting conditional shifts.

Figure 3 shows that our method had similar power curves to the alternative
approaches when testing for response and feature shift. However, when testing
for both types of conditional shift, our method achieved a significantly
higher power when compared with the alternative approaches.

Next, we investigate the role of the dimensionality of the feature space in
the performance of the three methods used to test for feature shift, and that
can be easily extended to multidimensional cases. More specifically, our goal
in the example is to detect feature shifts using the settings from the second
experiment of this section when $\lambda=.24$. We concatenate to $X$ a
standard Gaussian random vector (independent of the original $X$), ending up
with an updated version of $X$ with size $d$. Then, we compare the various
tests in terms of their power to test $H_{0,F}$ when $\alpha=5\%$. We use 200
Monte Carlo simulations to estimate power and set $B=100$ for Algorithm 1
(appendix). Because the divergence between the distributions remains the same
when adding this noise, this experiment allows us to isolate the
dimensionality.

Figure 4: Role of the feature space’s dimensionality in the tests’ power. The
performance of our method and the classification approach when $d=400$ is
equivalent to the performance of the TV approach when $d=4$. Our method scales
well to high-dimensional data and consistently outperforms other approaches.

Figure 4 indicates that the performance of our method and the classification
approach does not suffer as much from increasing $d$ compared to the TV
approach. We compare the TV approach with $d\in\\{1,2,3,4\\}$ with our
approach $d\in\\{1,2,3,4,10,\linebreak 20,30,40,100,200,300,400\\}$. We stop
at $d=4$ for the TV approach because the quantity of bins increases
geometrically with the number of dimensions, and if $d\geq 5$, we would expect
to find less than two data points per bin. Interestingly, the performance of
the TV approach when $d=4$ is equivalent to the performance of the other
methods when $d=400$. Moreover, our method consistently outperforms the other
two approaches.

In summary, (i) our approach has the advantage of being unified, i.e., a
single framework is used to test all hypotheses using test statistics with the
same nature while maintaining good power; (ii) our method scales well to high-
dimensional data and consistently outperforms other approaches.

###  4.2 Real Data Experiments

####  4.2.1 Insights from credit data

In this experiment, we use our method to extract insights into how probability
distributions can differ in a financial application. The dataset used in this
experiment is a credit scoring dataset and was kindly provided by the Latin
American Experian DataLab, based in Brazil. It contains financial data of one
million Brazilians collected every month going from August/2019 to May/2020.

The features in this dataset are related to past financial data, e.g., amount
of loans and credit card bills not paid on time, and the _label variable_
informs whether a consumer will _delay a debt payment_ for 30 days in the
_next three months_ , i.e., we have a binary classification problem. In this
experiment, we kept 20k random data points each month, with $20\%$ of them
going to the test set. Also, we kept the top 5 most essential features of the
credit risk prediction model. These specific features are related to payment
punctuality for credit card bills, the number of active consumer contracts,
and the monetary values involved. We used CatBoost [33] both to estimate the
Radon-Nykodim derivative and the conditional distribution of $Y|\mathbf{X}$.

Figure 5: Detecting different types of dataset shift using credit data from
the Latin American Experian DataLab, based in Brazil. The vertical dashed line
marks the beginning of the COVID-19 crisis in Brazil. We highlight the
decoupling between the total shift and covariate or conditional shift type 1
after February/2020. This behavior is due to a bigger shift in the marginal
and conditional distribution of $Y$ and is possibly associated with the
economic consequences of the pandemic. Because all tests use test statistics
with the same nature, we can easily compare the magnitude of the different
types of shifts. The testing procedure becomes interpretable.

The results in Figure 5 indicate increasing covariate, conditional shift type
1, and total dataset shift from the beginning. This is expected because the
features contain information about how people use their credit (e.g., loan
amount, credit card use). The way people use their credit is a function of
changes in the economy that can occur rapidly, such as fluctuating
inflation/interest/exchange rates, extra expenses due to holidays, etc. From
February 2020 onward, i.e., labels relative to months post-March 2020, it is
possible to notice a decoupling between shift curves in the coming months
after the first official COVID-19 case detected in Brazil and the beginning of
the economic crisis. The decoupling means that a more significant share of the
total shift is due to a shift in the marginal and conditional distribution of
$Y$. We speculate that this decoupling is due to measures taken by banks and
credit bureaus to help consumers during the pandemic. Some measures include
but are not limited to, longer payment intervals and lower interest rates.

To conclude, because all test statistics have the same nature, we can easily
compare the magnitude of the different types of shifts. The testing procedure
becomes interpretable.

####  4.2.2 Using dataset shift diagnostics to improve predictions

In this experiment, we evaluate our method as a guide for dataset shift
adaptation using the MNIST and USPS datasets [21, 49]. Both datasets contain
images, i.e., pixel intensities, and labels for the same ten digits (i.e. 0 to
9). Our interest is (i) to use our framework to quantify and formally test the
presence of all types of dataset shift using the MNIST distribution as the
source and a mixture between MNIST and USPS (with increasing proportions of
USPS participation) as target distributions and then (ii) adapt our predictors
using the insights given by our diagnostics to achieve better out-of-sample
performance. We aim to show how detecting specific types of shift help
practitioners correct their models. In this experiment, we use $256$ features
(pixel intensities of $16\times 16$ images) and partition the data in 12
smaller disjoint datasets of size 3.1k in a way that the proportion of USPS
samples increases linearly from $0\%$ to $50\%$. We split each dataset with
$10\%$ of the samples to test and use CatBoost [33] to estimate R-N
derivatives and conditional distribution. We use the first dataset, with only
MNIST samples, as our baseline and compare it to the mixed datasets.

Figure 6: Detecting different types of dataset shift using MNIST and USPS data
and then adapting a predictor. We define the MNIST distribution (USPS
$(\%)=0$) as the source distribution and the mixed distributions (USPS
$(\%)>0$) as multiple target distributions. Response and conditional shifts of
type 2 (shift in $P_{Y|\mathbf{X}}$) are not evident, while others are. The
second plot indicates that adapting for feature shift should be enough (as
$P_{Y|\mathbf{X}}$ seems static). In the third plot, we compare the
performance of two logistic regression models trained using pure MNIST samples
with one adapted for feature shift. The adapted model gives better
predictions. Thus, by properly leveraging the insights given by our framework,
one can improve the predictive power of the supervised learning model.

The plots in Figure 6 indicate that the total dataset shift (shift in
$P_{\mathbf{X},Y}$), conditional shift 1 (shift in $P_{\mathbf{X}|Y}$), and
feature shift (shift in $P_{\mathbf{X}}$) are promptly detected while response
shift (shift in $P_{Y}$) and conditional shift 2 (shift in $P_{Y|\mathbf{X}}$)
are not. That observation is consistent with the fact that (i) the
distribution of $Y$ is similar in both MNIST and USPS populations which also
implies that (ii) two similar pixel configurations should induce similar
posterior distributions of labels regardless of the origin distribution.
Finally, the plots indicate that adapting for feature shifts should be enough
to achieve better predictions on the target domain. Indeed, that is the case
here – in the third plot, we compare the performance of two logistic
regression models8. Both are trained using pure MNIST samples, but one is
correct for feature shift using importance weighting [43]. The weights are
obtained via the classifier used to estimate $\text{KL}_{\mathbf{X}}$, with no
need to fit an extra model for the weights.

In this experiment, we show that, by properly leveraging the insights given by
our framework, one can improve the predictive power of the supervised learning
model.

####  4.2.3 Detecting shifts with deep models

We use our framework to detect shifts in image and text datasets using deep
learning models as classifiers to estimate the Radon-Nikodym derivative and
the conditional distribution of $Y|\mathbf{X}$. We use large pre-trained
models as feature extractors, freezing all the layers except the output one,
given by a logistic regression model. The pre-trained models are VGG-16 [38]
for images and XLM-ROBERTa [6] for texts. We use the Tiny ImageNet [8, 1] and
CIFAR-10 [19] as image111111Tiny ImageNet contains $64\times 64$ images from
200 classes while CIFAR-10 contains $32\times 32$ images from 10 classes.
datasets and “Amazon Fine Food Reviews,” available on Kaggle, as our text
dataset. Then, the first two datasets we use are composed of RGB images from
$K=10$ different classes121212We group, in increasing order, the classes from
Tiny ImageNet in 10 meta-classes.. In contrast, the third dataset is composed
of product reviews in the form of short texts and a rating, varying from 0 to
4, given by consumers, thus having $K=5$ classes131313Regarding the Amazon
dataset, we subsampled the data to guarantee all the classes have roughly the
same number of examples.. The sample sizes are 30k data points with $10\%$
going to test.

We derive the source and target datasets from the original datasets as
follows. First, we fix $\delta\in(0,.5)$ and then create a list LIST of $K$
numbers (one for each class) where the first element of the list is $\delta$,
the last is $1-\delta$, and the intermediate ones are given by linear
interpolation of $\delta$ and $1-\delta$. Then, for each
$k\in\\{0,...,K-1\\}$, we randomly select LIST[$k$] of the samples of class
$k$ to be in the source dataset, while the rest goes to the target dataset. In
this way, we explicitly introduce label shift (shift in $P_{Y}$ but not in
$P_{\mathbf{X}|Y}$), which is expected to induce feature shift and conditional
shift type 2 as well. After we have data from both populations (source and
target), we detect the shifts as usual. We repeated the same procedure for all
$\delta\in\\{.5,.45,.4,.35,.3\\}$ and for five different random seeds.

Figure 7: Detecting different types of dataset shift using complex high-
dimensional data. For many values of $\delta$, we could detect all types of
shift except conditional shift 1, which is expected because we introduced
response shift in isolation ($\delta\neq.5$ is equivalent to label shift). The
benchmark approaches cannot detect a conditional shift of type 2, which can be
explained by lower power. Then, our framework can accurately detect the
correct shifts even in complex datasets and using deep models.

The results are shown in Figure 7, where the lines represent averages across
repetitions and error bars give the standard deviations. We were able to
detect141414Except when $\delta$ is close to $.5$ (small or no shift). all
types of shift except conditional shift 1 using our approach. This result was
expected because, given the class, the distribution of the features must not
be affected by how we introduced the shift. We also run results considering
the classification-based two-sample test proposed by [25] to test shifts
related to joint/marginal distributions and CRT 1 and LPT 1, explained in
detail in the appendix, to test for conditional shifts. For the benchmarks, we
cannot detect a conditional shift of type 2. A lower power of the benchmarks
compared to our method can explain that fact (see artificial data
experiments). Furthermore, we cannot compare shift magnitudes using benchmark
approaches since their statistics do not have the same nature. We report KL
estimates of DetectShift in the appendix. We also left in the appendix an
extra (and similar) experiment in which our framework obtained similar
p-values compared to the benchmarks.

In summary, we show that our framework can accurately detect the correct
shifts even in complex datasets and using deep models.

##  5 Discussion

The proposed DetectShift framework quantifies and formally tests different
dataset shifts, including response, feature, and conditional shifts. Our
approach sheds light not only on _if_ a prediction model should be
retrained/adapted but also on _how_ , enabling the practitioners to tackle
shifts in their data objectively and efficiently. Our method is versatile and
applicable across various data types and supervised tasks. Unlike our
framework, existing dataset shift detection methods are only designed to
detect specific types of shift or cannot formally test their presence,
sometimes even requiring both labels and features to be discrete or low-
dimensional.

Our experiments have provided compelling evidence of the effectiveness of our
framework. Through artificial data experiments, we have demonstrated the
versatility of DetectShift in isolating different types of dataset shifts and
leveraging supervised learning to construct powerful tests. Furthermore, our
framework has shown remarkable performance in higher dimensions, surpassing
possible benchmarks. In real data experiments, we have illustrated how
DetectShift can extract valuable insights from data, assisting practitioners
in adapting their models to changing distributions. Moreover, our approach
seamlessly integrates with deep learning models, making it applicable to real-
world scenarios. These findings highlight the significant contributions of our
framework, showcasing its efficacy in detecting dataset shifts and
underscoring its potential for practical applications in various domains.

##  6 Final remarks and possible extensions

In conclusion, we reflect on key facets and potential limitations inherent to
our framework.

Why and how to obtain better Radon-Nikodym derivatives estimates? While Type I
error control is not affected by Radon-Nikodym derivatives estimation (as the
theoretical results show), the power of the tests is. This happens because the
classifiers’ performance in predicting probabilities directly influences how
well we approximate the KL divergence and, consequently, can detect shifts in
the data. Thus, we can use the cross-entropy (CE) loss on a validation set to
pick the best classifier.

Modular framework and alternative statistics choices. Our hypothesis tests are
agnostic to the choice test statistics; therefore, our framework is modular.
We consider the KL statistics desirable, among other things, because we have
the additivity property (Proposition 2), making the analyses more
interpretable. A natural alternative to the KL statistics, when we do not want
to favor one of the distributions, is the symmetrized KL, for example.

Dealing with streaming data. While the primary design of our framework does
not cater to streaming data, it possesses the flexibility for adaptation in
such settings. One way of doing this is to group the data into batches (e.g.,
every hour, day, month) and then apply the proposed approach to compare two or
more data batches. Multiple testing methods [35] can be used along with our
framework if the practitioner desires.

Labeled data in the target domain. Even though there are many situations in
which at least some labeled data are available for the target domain, there
are cases in which that is not true. We recognize this scenario as a
limitation, warranting further exploration in subsequent research.

##  7 Acknowledgments

We sincerely thank the “Information Sciences” editor and anonymous reviewers
for their invaluable contributions to this paper. We are grateful for their
time and dedication in carefully evaluating our manuscript and providing
valuable suggestions for improvement.

We are thankful for the credit dataset provided by the Latin American Experian
Datalab, the Serasa Experian DataLab. We want to thank the developers of
Grammarly and ChatGPT, which were helpful tools when polishing our text.

FMP is grateful for the financial support of CNPq (32857/2019-7) and
Fundunesp/Advanced Institute for Artificial Intelligence (AI2) (3061/2019-CCP)
during his master’s degree at the University of São Paulo (USP). Part of this
work was written when FMP was at USP.

RI is grateful for the financial support of CNPq (309607/2020-5 and
422705/2021-7) and FAPESP (2019/11321-9).

##  8 Code and data

Our package for dataset shift detection can be found in
https://github.com/felipemaiapolo/detectshift

The source code and data used in this paper can be found in
https://github.com/felipemaiapolo/dataset_shift_diagnostics.

## References

  * Abai and Rajmalwar [2019] Zoheb Abai and Nishad Rajmalwar.  Densenet models for tiny imagenet classification.  _arXiv preprint arXiv:1904.10429_ , 2019.
  * Annamoradnejad et al. [2022] Issa Annamoradnejad, Jafar Habibi, and Mohammadamin Fazli.  Multi-view approach to suggest moderation actions in community question answering sites.  _Information Sciences_ , 600:144–154, 2022.  ISSN 0020-0255.  doi: https://doi.org/10.1016/j.ins.2022.03.085.  URL https://www.sciencedirect.com/science/article/pii/S0020025522003127.
  * Bellot and van der Schaar [2019] Alexis Bellot and Mihaela van der Schaar.  Conditional independence testing using generative adversarial networks.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Berrett et al. [2020] Thomas B Berrett, Yi Wang, Rina Foygel Barber, and Richard J Samworth.  The conditional permutation test for independence while controlling for confounders.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 82(1):175–197, 2020.
  * Candès et al. [2018] Emmanuel Candès, Yingying Fan, Lucas Janson, and Jinchi Lv.  Panning for gold:‘model-x’knockoffs for high dimensional controlled variable selection.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 80(3):551–577, 2018.
  * Conneau et al. [2020] Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov.  Unsupervised cross-lingual representation learning at scale.  In _ACL_ , 2020.
  * Dalmasso et al. [2021] Niccolo Dalmasso, David Zhao, Rafael Izbicki, and Ann B Lee.  Likelihood-free frequentist inference: Bridging classical statistics and machine learning in simulation and uncertainty quantification.  _arXiv preprint arXiv:2107.03920_ , 2021.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * Finlayson et al. [2021] Samuel G Finlayson, Adarsh Subbaswamy, Karandeep Singh, John Bowers, Annabel Kupke, Jonathan Zittrain, Isaac S Kohane, and Suchi Saria.  The clinician and dataset shift in artificial intelligence.  _The New England journal of medicine_ , 385(3):283, 2021.
  * Freeman et al. [2017] Peter E Freeman, Rafael Izbicki, and Ann B Lee.  A unified framework for constructing, tuning and assessing photometric redshift density estimates in a selection bias setting.  _Monthly Notices of the Royal Astronomical Society_ , 468(4):4556–4565, 2017.
  * Gama et al. [2004] Joao Gama, Pedro Medas, Gladys Castillo, and Pedro Rodrigues.  Learning with drift detection.  In _Brazilian symposium on artificial intelligence_ , pages 286–295. Springer, 2004.
  * Ginsberg et al. [2023] Tom Ginsberg, Zhongyuan Liang, and Rahul G Krishnan.  A learning based hypothesis test for harmful covariate shift.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=rdfgqiwz7lZ.
  * Gretton et al. [2012] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  _The Journal of Machine Learning Research_ , 13(1):723–773, 2012.
  * Izbicki and Lee [2017] Rafael Izbicki and Ann B Lee.  Converting high-dimensional regression to high-dimensional conditional density estimation.  _Electronic Journal of Statistics_ , 11(2):2800–2831, 2017.
  * Izbicki et al. [2017] Rafael Izbicki, Ann B Lee, and Peter E Freeman.  Photo-$z$ estimation: An example of nonparametric conditional density estimation under selection bias.  _The Annals of Applied Statistics_ , 11(2):698–724, 2017.
  * Jang et al. [2022] Sooyong Jang, Sangdon Park, Insup Lee, and Osbert Bastani.  Sequential covariate shift detection using classifier two-sample tests.  In _International Conference on Machine Learning_ , pages 9845–9880. PMLR, 2022.
  * Kim et al. [2021] Ilmun Kim, Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman.  Local permutation tests for conditional independence.  _arXiv preprint arXiv:2112.11666_ , 2021.
  * Kolmogorov [1933] A N Kolmogorov.  Sulla determinazione empirica di una legge di distribuzione.  _Giorn. Ist. Ital. Attuar._ , 4:83–91, 1933.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Kullback and Leibler [1951] Solomon Kullback and Richard A Leibler.  On information and sufficiency.  _The annals of mathematical statistics_ , 22(1):79–86, 1951.
  * LeCun et al. [1998] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Lehmann et al. [2005] Erich Leo Lehmann, Joseph P Romano, and George Casella.  _Testing statistical hypotheses_ , volume 3.  Springer, 2005.
  * Li et al. [2010] Yan Li, Hiroyuki Kambara, Yasuharu Koike, and Masashi Sugiyama.  Application of covariate shift adaptation techniques in brain–computer interfaces.  _IEEE Transactions on Biomedical Engineering_ , 57(6):1318–1324, 2010.
  * Lipton et al. [2018] Zachary Lipton, Yu-Xiang Wang, and Alexander Smola.  Detecting and correcting for label shift with black box predictors.  In _International conference on machine learning_ , pages 3122–3130. PMLR, 2018.
  * Lopez-Paz and Oquab [2016] David Lopez-Paz and Maxime Oquab.  Revisiting classifier two-sample tests.  _arXiv preprint arXiv:1610.06545_ , 2016.
  * Luo et al. [2022] Rachel Luo, Rohan Sinha, Ali Hindy, Shengjia Zhao, Silvio Savarese, Edward Schmerling, and Marco Pavone.  Online distribution shift detection via recency prediction.  _arXiv preprint arXiv:2211.09916_ , 2022.
  * Maia Polo and Vicente [2022] Felipe Maia Polo and Renato Vicente.  Effective sample size, dimensionality, and generalization in covariate shift adaptation.  _Neural Computing and Applications_ , pages 1–13, 2022.
  * Maity et al. [2021] Subha Maity, Diptavo Dutta, Jonathan Terhorst, Yuekai Sun, and Moulinath Banerjee.  A linear adjustment based approach to posterior drift in transfer learning.  _arXiv preprint arXiv:2111.10841_ , 2021.
  * Moreno-Torres et al. [2012] Jose G Moreno-Torres, Troy Raeder, Rocío Alaiz-Rodríguez, Nitesh V Chawla, and Francisco Herrera.  A unifying view on dataset shift in classification.  _Pattern recognition_ , 45(1):521–530, 2012.
  * Pedregosa et al. [2011] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830, 2011.
  * Podkopaev and Ramdas [2021] Aleksandr Podkopaev and Aaditya Ramdas.  Tracking the risk of a deployed model and detecting harmful distribution shifts.  _arXiv preprint arXiv:2110.06177_ , 2021.
  * Polyanskiy and Wu [2022] Yury Polyanskiy and Yihong Wu.  Information theory: From coding to learning, 2022.
  * Prokhorenkova et al. [2017] Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin.  Catboost: unbiased boosting with categorical features.  _arXiv preprint arXiv:1706.09516_ , 2017.
  * Rabanser et al. [2019] Stephan Rabanser, Stephan Günnemann, and Zachary Lipton.  Failing loudly: An empirical study of methods for detecting dataset shift.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Rice et al. [2008] Treva K Rice, Nicholas J Schork, and DC Rao.  Methods for handling multiple testing.  _Advances in genetics_ , 60:293–308, 2008.
  * Saerens et al. [2002] Marco Saerens, Patrice Latinne, and Christine Decaestecker.  Adjusting the outputs of a classifier to new a priori probabilities: a simple procedure.  _Neural computation_ , 14(1):21–41, 2002.
  * Schrouff et al. [2022] Jessica Schrouff, Natalie Harris, Sanmi Koyejo, Ibrahim M Alabdulmohsin, Eva Schnider, Krista Opsahl-Ong, Alexander Brown, Subhrajit Roy, Diana Mincu, Christina Chen, et al.  Diagnosing failures of fairness transfer across distribution shift in real-world medical settings.  _Advances in Neural Information Processing Systems_ , 35:19304–19318, 2022.
  * Simonyan and Zisserman [2014] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Smirnov [1939] Nikolai V Smirnov.  Estimate of deviation between empirical distribution functions in two independent samples.  _Bulletin Moscow University_ , 2(2):3–16, 1939\.
  * Sønderby et al. [2016] Casper Kaae Sønderby, Jose Caballero, Lucas Theis, Wenzhe Shi, and Ferenc Huszár.  Amortised map inference for image super-resolution.  _arXiv preprint arXiv:1610.04490_ , 2016.
  * Speakman et al. [2018] Skyler Speakman, Srihari Sridharan, and Isaac Markus.  Three population covariate shift for mobile phone-based credit scoring.  In _Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies_ , pages 1–7, 2018.
  * Sugiyama and Kawanabe [2012] Masashi Sugiyama and Motoaki Kawanabe.  _Machine learning in non-stationary environments: Introduction to covariate shift adaptation_.  MIT press, 2012.
  * Sugiyama et al. [2007] Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert Müller.  Covariate shift adaptation by importance weighted cross validation.  _Journal of Machine Learning Research_ , 8(5), 2007.
  * Sugiyama et al. [2012] Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori.  _Density ratio estimation in machine learning_.  Cambridge University Press, 2012.
  * Vaz et al. [2019] Afonso Fernandes Vaz, Rafael Izbicki, and Rafael Bassi Stern.  Quantification under prior probability shift: The ratio estimator and its extensions.  _The Journal of Machine Learning Research_ , 20(1):2921–2953, 2019.
  * Vovk [2020] Vladimir Vovk.  Testing for concept shift online.  _arXiv preprint arXiv:2012.14246_ , 2020.
  * Webb et al. [2018] Geoffrey I Webb, Loong Kuan Lee, Bart Goethals, and François Petitjean.  Analyzing concept drift and shift from sample data.  _Data Mining and Knowledge Discovery_ , 32(5):1179–1199, 2018.
  * Wijaya et al. [2021] Maleakhi A Wijaya, Dmitry Kazhdan, Botty Dimanov, and Mateja Jamnik.  Failing conceptually: Concept-based explanations of dataset shift.  _arXiv preprint arXiv:2104.08952_ , 2021.
  * Xu and Klabjan [2021] Yiming Xu and Diego Klabjan.  Concept drift and covariate shift detection ensemble with lagged labels.  In _2021 IEEE International Conference on Big Data (Big Data)_ , pages 1504–1513. IEEE, 2021.
  * Yu et al. [2019] Shujian Yu, Zubin Abraham, Heng Wang, Mohak Shah, Yantao Wei, and José C Príncipe.  Concept drift detection and adaptation with hierarchical hypothesis testing.  _Journal of the Franklin Institute_ , 356(5):3187–3215, 2019.

##  Appendix A Methodology

###  A.1 Alternative estimator for $\textup{KL}_{Y}$ when $Y$ is discrete

Assume $\mathcal{Y}$ is the range of $Y$ in the target domain, where
$\mathcal{Y}$ is finite. Define $p_{y}^{(i)}=P_{Y}^{(i)}(\\{y\\})$, for
$i=1,2$. Then, we can write
$\textup{KL}_{Y}=\sum_{y\in\mathcal{Y}}p_{y}^{(2)}\log\frac{p_{y}^{(2)}}{p_{y}^{(1)}}$.
Having observed two datasets (in practice, we use the test datasets),
$\mathcal{D}^{(1)}$ and $\mathcal{D}^{(2)}$, we define $\hat{p}_{y}^{(i)}$ to
be the relative frequency of the label $y$ in dataset $i$. Then, a plug-in
estimator for $\textup{KL}_{Y}$ is given by
$\widehat{\textup{KL}}_{Y}=\sum_{y\in\mathcal{Y}}\hat{p}_{y}^{(2)}\log\frac{\hat{p}_{y}^{(2)}}{\hat{p}_{y}^{(1)}}$.
This estimator is consistent.

###  A.2 Algorithm to obtain $p$-values

Input: (i) Hypothesis to be tested and respective test statistic $T$, (ii)
Test set $\mathcal{D}^{te}$, (iii) number of iterations $B\in\mathbb{N}$, (iv)
conditional distribution $Q_{Y|\mathbf{X}}$ (in case of testing for
conditional shift type 2), (v) Gaussian noise variance $\nu$;

1

Output: p-value $p=p(\mathcal{D}^{te})$;

2

3Initialize $C=0$ and obtain
$\mathcal{D}^{te}_{2}=\\{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}^{te}:Z_{k}=2\\}$;

4Get $T_{0}=T(\mathcal{D}^{te}_{2})+N(0,\nu)$;

5for  _$j$ in $\\{1,...,B\\}$_ do

6 if  _Testing for response shift, feature shift, or dataset shift_ then

7 Draw a random permutation $\pi=(\pi_{1}~{}...~{}\pi_{|\mathcal{D}^{te}|})$
of natural numbers from $1$ to $|\mathcal{D}^{te}|$

8 Set
$\widetilde{\mathcal{D}^{te}_{2}}^{(j)}=\\{(\mathbf{X}_{k},Y_{k},Z_{\pi_{k}}):(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}^{te}\text{
and }Z_{\pi_{k}}=2\\}$

9

10 else if  _Testing for conditional shift (type 1)_ then

11 Let $\mathcal{Y}$ be a finite set which $Y$ takes values

12 for  _$y$ in $\mathcal{Y}$_ do

13 Get
$\mathcal{D}^{(y)}=\\{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}^{te}:Y_{k}=y\\}$

14 Draw a random permutation
$\pi^{(y)}=(\pi^{(y)}_{1}~{}...~{}\pi^{(y)}_{|\mathcal{D}^{(y)}|})$ of natural
numbers from $1$ to $|\mathcal{D}^{(y)}|$

15

16 Set
$\widetilde{\mathcal{D}^{te}_{2}}^{(j)}=\bigcup_{y\in\mathcal{Y}}\\{(\mathbf{X}_{k},Y_{k},Z_{\pi^{(y)}_{k}}):(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}^{(y)}\text{
and }Z_{\pi^{(y)}_{k}}=2\\}$

17 else if  _Testing for conditional shift (type 2)_ then

18 Sample $\widetilde{Y}_{k}|\mathbf{X}_{k}\sim
Q_{Y|\mathbf{X}=\mathbf{X}_{k}}$, for each $\mathbf{X}_{k}$ from elements of
$\mathcal{D}_{2}^{te}$

19 Set
$\widetilde{\mathcal{D}^{te}_{2}}^{(j)}=\\{(\mathbf{X}_{k},\widetilde{Y}_{k},Z_{k}):(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}_{2}^{te}\\}$

20

21 Get $T_{j}=T(\widetilde{\mathcal{D}^{te}_{2}}^{(j)})+N(0,\nu)$;

22 Update $C=C+\mathbb{I}\left[T_{0}\leq T_{j}\right]$;

23

24$p=\frac{C+1}{B+1}$

return $p$.

Algorithm 1 DetectShift: obtaining p-values

In practice, $\nu>0$ can be a very small number, e.g., $10^{-10}$.

###  A.3 Proofs

The results presented in this section are not original; however, we decided to
include proofs to make this work self-contained.

Proposition 2. Let $\textup{KL}_{Y}$, $\textup{KL}_{X}$, $\textup{KL}_{Y|X}$,
$\textup{KL}_{X|Y}$, $\textup{KL}_{X,Y}$ be defined as they were in Section
3.1. Then

$\displaystyle\textup{KL}_{\mathbf{X},Y}$
$\displaystyle=\textup{KL}_{Y|\mathbf{X}}+\textup{KL}_{\mathbf{X}}$
$\displaystyle=\textup{KL}_{\mathbf{X}|Y}+\textup{KL}_{Y}$

###### Proof.

In this proof, we assume the distributions are absolutely continuous with
respect to the Lebesgue measure. For a more general proof, see Polyanskiy and
Wu [32] (Theorem 2.13).

We start showing
$\textup{KL}_{\mathbf{X},Y}=\textup{KL}_{Y|\mathbf{X}}+\textup{KL}_{\mathbf{X}}$.
Let $p^{(1)}_{\mathbf{X},Y}$ and $p^{(2)}_{\mathbf{X},Y}$ be the joint
densities of $P^{(1)}_{\mathbf{X},Y}$ and $P^{(2)}_{\mathbf{X},Y}$ with
respect to the Lebesgue measure. Then

$\displaystyle\textup{KL}_{\mathbf{X},Y}$ $\displaystyle=\int
p^{(2)}_{\mathbf{X},Y}(\mathbf{x},y)\log\frac{p^{(2)}_{\mathbf{X},Y}(\mathbf{x},y)}{p^{(1)}_{\mathbf{X},Y}(\mathbf{x},y)}d(\mathbf{x},y)$
$\displaystyle=\int
p^{(2)}_{Y|\mathbf{X}}(y|\mathbf{x})p^{(2)}_{\mathbf{X}}(\mathbf{x})\log\frac{p^{(2)}_{Y|\mathbf{X}}(y|\mathbf{x})p^{(2)}_{\mathbf{X}}(\mathbf{x})}{p^{(1)}_{Y|\mathbf{X}}(y|\mathbf{x})p^{(1)}_{\mathbf{X}}(\mathbf{x})}d(\mathbf{x},y)$
$\displaystyle=\int p^{(2)}_{\mathbf{X}}(\mathbf{x})\int
p^{(2)}_{Y|\mathbf{X}}(y|\mathbf{x})\log\frac{p^{(2)}_{Y|\mathbf{X}}(y|\mathbf{x})}{p^{(1)}_{Y|\mathbf{X}}(y|\mathbf{x})}dyd\mathbf{x}+\int
p^{(2)}_{\mathbf{X}}(\mathbf{x})\log\frac{p^{(2)}_{\mathbf{X}}(\mathbf{x})}{p^{(1)}_{\mathbf{X}}(\mathbf{x})}d\mathbf{x}$
$\displaystyle=\textup{KL}_{Y|\mathbf{X}}+\textup{KL}_{\mathbf{X}}$

We can show that
$\textup{KL}_{\mathbf{X},Y}=\textup{KL}_{\mathbf{X}|Y}+\textup{KL}_{Y}$
analogously. ∎

Proposition 3. Let $p(\mathcal{D}^{te})$ be a $p$-value obtained from
Algorithm 1 (appendix) with fixed $T$ and $Q_{Y|\mathbf{X}}$. Then, for every
$\alpha\in(0,1)$,

  * •

Under $H_{0,\text{D}},H_{0,\text{F}}$,$H_{0,\text{R}}$, and $H_{0,\text{C1}}$
(if $Y$ is discrete),

$\mathbb{P}(p(\mathcal{D}^{te})\leq\alpha)\leq\alpha$

  * •

Under $H_{0,\text{C2}}$

$\mathbb{P}(p(\mathcal{D}^{te})\leq\alpha)\leq\alpha+\mathbb{E}_{\bar{P}^{(2)}_{\mathbf{X}}}\left[d_{\text{TV}}(\bar{Q}_{Y|\mathbf{X}},\bar{P}_{Y|\mathbf{X}})\right],$

where $d_{\text{TV}}$ is the total variation distance,
$\bar{P}^{(2)}_{\mathbf{X}}:=\prod_{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}_{2}^{te}}P^{(2)}_{\mathbf{X}_{k}}$,
$\bar{Q}_{Y|\mathbf{X}}:=\prod_{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}_{2}^{te}}Q_{Y|\mathbf{X}=\mathbf{X}_{k}}$,
and
$\bar{P}_{Y|\mathbf{X}}=\prod_{(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}_{2}^{te}}P^{(2)}_{Y|\mathbf{X}=\mathbf{X}_{k}}$.

###### Proof.

We start deriving the result for $H_{0,\text{F}}$ using the theory behind
permutation tests for two-sample/independence tests (see Lehmann et al. [22,
Chapter 15] for more details). The results for $H_{0,\text{D}}$ and
$H_{0,\text{R}}$ obtained analogously. Define
$\widetilde{\mathcal{D}}^{{te}^{(0)}}_{2}:=\mathcal{D}^{{te}}_{2}$ and
$T_{j}:=T\left(\widetilde{\mathcal{D}}^{{te}^{(j)}}_{2}\right)+N_{j}$, for all
$j$, where $N_{j}$’s are i.i.d. $N(0,\nu)$. For the rest of the proof,
$T_{j}$’s will always be noisy versions of the respective
$T\left(\widetilde{\mathcal{D}}^{{te}^{(j)}}_{2}\right)$’s.

Recall that

$\displaystyle p(\mathcal{D}^{te})$
$\displaystyle=\frac{\sum_{j=0}^{B}\mathbb{I}\left[T_{0}\leq
T_{j}\right]}{B+1}$

See that $(B+1)p(\mathcal{D}^{te})$ gives the rank of $T_{0}$ among all
$T_{j}$’s, that is, if $(B+1)p(\mathcal{D}^{te})=k$ it means that there are
$k$ values of $j$ such that $T_{0}\leq T_{j}$. If
$P^{(1)}_{\mathbf{X}}=P^{(2)}_{\mathbf{X}}$ and the permutations are drawn
uniformly from the set of all permutations of
$\\{1,\cdots,|\mathcal{D}^{te}|\\}$, then $T_{0},\cdots,T_{B}$ are
exchangeable. Because we add $N_{j}$’s in $T_{j}$’s, we can guarantee that all
$T_{j}$’s are different with probability 1. Consequently,
$U_{B+1}:=(B+1)p(\mathcal{D}^{te})$ is uniformly distributed in
$\\{1,\cdots,B+1\\}$. Then,

$\displaystyle\mathbb{P}\left(p(\mathcal{D}^{te})\leq\alpha\right)$
$\displaystyle=\mathbb{P}\left((B+1)p(\mathcal{D}^{te})\leq(B+1)\alpha\right)$
$\displaystyle=\mathbb{P}\left(U_{B+1}\leq(B+1)\alpha\right)$
$\displaystyle=\mathbb{P}\left(U_{B+1}\leq\left\lfloor(B+1)\alpha\right\rfloor\right)$
$\displaystyle=\frac{\left\lfloor(B+1)\alpha\right\rfloor}{B+1}$
$\displaystyle\leq\frac{(B+1)\alpha}{B+1}$ $\displaystyle=\alpha$

where $\left\lfloor\cdot\right\rfloor$ is the floor function.

The result for $H_{0,\text{C1}}$ is obtained similarly. Assume that
$P^{(1)}_{\mathbf{X}|Y=y}=P^{(2)}_{\mathbf{X}|Y=y}$ for every
$y\in\textup{supp}(P^{(2)}_{Y})$. We can ignore values of $y$ not in
$\textup{supp}(P^{(2)}_{Y})$ because $p(\mathcal{D}^{te})$ does not depend on
them. Given that we permute samples within each level of $Y$, we have that
$T_{0},\cdots,T_{B}$ are exchangeable, implying that (by our derivations
above)

$\displaystyle\mathbb{P}\left(p(\mathcal{D}^{te})\leq\alpha\right)\leq\alpha.$

The result for $H_{0,\text{C2}}$ is based on Theorem 4 of Berrett et al. [4].
For each $j\in\\{1,\cdots,B\\}$, denote
$\widetilde{\mathcal{D}^{te}_{2}}^{(j)}=\\{(\mathbf{X}_{k},\widetilde{Y}_{k},Z_{k}):(\mathbf{X}_{k},Y_{k},Z_{k})\in\mathcal{D}_{2}^{te}\\}$
where $\widetilde{Y}_{k}|\mathbf{X}_{k}\sim Q_{Y|\mathbf{X}=\mathbf{X}_{k}}$,
for each $\mathbf{X}_{k}$ from elements of $\mathcal{D}_{2}^{te}$. Define
$\widetilde{\mathcal{D}^{te}_{2}}^{(0)}:=\mathcal{D}^{te}_{2}$ and let
$\widetilde{\mathcal{D}^{te}_{2}}^{(B+1)}$ be one extra dataset built in the
same way as all others $\widetilde{\mathcal{D}^{te}_{2}}^{(j)}$ considering
$j\in\\{1,\cdots,B\\}$. See that all datasets
$\widetilde{\mathcal{D}^{te}_{2}}^{(j)}$ considering $j\in\\{0,\cdots,B+1\\}$
share the same values for the covariates; let $\mathbb{X}$ denote a random
matrix containing such values for all samples. Because the p-values only
depend on the data coming from151515If that was not true, the following
inequality would hold if we condition not only on $\mathbb{X}$ but also on a
matrix composed of $Z$’s (as done in Berrett et al. [4]).
$\mathcal{D}_{2}^{te}$ (and not on the full test set $\mathcal{D}^{te}$), we
have that

$\displaystyle\mathbb{P}\left(p(\mathcal{D}^{te})\leq\alpha|\mathbb{X}\right)\leq\mathbb{P}\left(\tilde{p}(\mathcal{D}^{te})\leq\alpha|\mathbb{X}\right)+d_{\text{TV}}(\bar{Q}_{Y|\mathbf{X}},\bar{P}_{Y|\mathbf{X}})$

where $\tilde{p}(\mathcal{D}^{te})$ is the p-value calculated using
$\widetilde{\mathcal{D}^{te}_{2}}^{(B+1)}$ instead of
$\widetilde{\mathcal{D}^{te}_{2}}^{(0)}$. This step is justified by the
definition of the total variation distance and by a conditional independence
argument [4] (given $\mathbb{X}$, all data replications are conditionally
independent).

By construction, $T_{1},\cdots,T_{B+1}$ are exchangeable given $\mathbb{X}$,
we have that
$\mathbb{P}\left(\tilde{p}(\mathcal{D}^{te})\leq\alpha|\mathbb{X}\right)\leq\alpha$.
Then, taking expectations on both sides of the inequality above, we get

$\displaystyle\mathbb{P}\left(p(\mathcal{D}^{te})\leq\alpha\right)\leq\alpha+\mathbb{E}_{\bar{P}^{(2)}_{\mathbf{X}}}\left[d_{\text{TV}}(\bar{Q}_{Y|\mathbf{X}},\bar{P}_{Y|\mathbf{X}})\right]$

∎

Realize that the last result is true even if $H_{0,\text{C2}}$ does not hold.
However, if $H_{0,\text{C2}}$ is not true, we do not expect
$\mathbb{E}_{\bar{P}^{(2)}_{\mathbf{X}}}\left[d_{\text{TV}}(\bar{Q}_{Y|\mathbf{X}},\bar{P}_{Y|\mathbf{X}})\right]$
to be small.

##  Appendix B Experiments

###  B.1 Comparisons with existing approaches (more details)

Some details about the experiments were omitted from the main text: (i) how we
choose $Q_{Y|\mathbf{X}}$ when testing for conditional shift 2; (ii) how the
local permutation tests (LPT) and conditional randomization tests (CRT)
alternatives work and what statistic they use.

####  B.1.1 How do we choose $Q_{Y|\mathbf{X}}$ in this set of experiments?

Given that our main objective in this experiment is comparing the power of
different tests that use the same approximated distribution
$Q_{Y|\mathbf{X}}$, we choose to fix $Q_{Y|X}=P^{(0)}_{Y|X}=\mathcal{N}(X,1)$,
where $P^{(0)}_{Y|X}$ is the conditional distribution of $Y|X$ under
$H_{0,\text{C2}}$.

####  B.1.2 How do the LPT and CRT alternative tests work, and what statistics
do they use?

We start explaining the two CRT alternative tests, which work in the same way
but have different test statistics.

  1. 1.

We split our dataset $\mathcal{D}=\\{(X_{i},Y_{i},Z_{i}\\}_{i=1}^{n}$ in a
training set $\mathcal{D}^{tr}=\\{(X_{i},Y_{i},Z_{i}\\}_{i=1}^{n^{tr}}$ and a
test set $\mathcal{D}^{te}=\mathcal{D}-\mathcal{D}^{tr}$;

  2. 2.

We build an artificial training set
$\widetilde{\mathcal{D}^{tr}}=\\{(X_{i},\tilde{Y}_{i},Z_{i})\\}_{i=1}^{n^{tr}}$,
where $\\{\tilde{Y}_{i}\\}$ are sampled from $Q_{Y|\mathbf{X}}$;

  3. 3.

We train a probabilistic classifier $\hat{h}$ to distinguish samples from
$\mathcal{D}^{tr}$ and $\widetilde{\mathcal{D}^{tr}}$, where the original set
receives label 1 and the artificial data receives label 0;

  4. 4.

For $B\in\mathbb{N}$, we test each of the hypotheses of interest by computing
a $p$-value of the form

$\displaystyle
p(\mathcal{D}^{te})=\frac{1+\sum_{j=1}^{B}\mathbb{I}\left[T(\mathcal{D}^{te})\leq
T\left(\widetilde{\mathcal{D}^{te}}^{(j)}\right)\right]}{B+1},$

where $T$ is a test statistic depending on $\hat{h}$ and each
$\widetilde{\mathcal{D}^{te}}^{(j)}$ is obtained sampling different labels
from $Q_{Y|\mathbf{X}}$. When

$T(\mathcal{D}^{te})=\frac{1}{|\mathcal{D}^{te}|}\sum_{(X,Y,Z)\in\mathcal{D}^{te}}\mathbb{I}[\hat{h}(X,Y,Z)>1/2]$

we have CRT 1. When

$T(\mathcal{D}^{te})=\frac{1}{|\mathcal{D}^{te}|}\sum_{(X,Y,Z)\in\mathcal{D}^{te}}\hat{h}(X,Y,Z)$

we have CRT 2.

The LPT alternative tests work in the same way. The only difference is that
the "artificial" variables $\\{\tilde{X_{i}}\\}$ are obtained via local
permutation within $Y$ levels.

$\hat{h}$ represents a CatBoost classifier in this experiment. When $\hat{h}$
is a logistic regressor (like in the KL tests), at least one test is too
conservative.

###  B.2 Digits experiment

MNIST samples tend to have more white pixels than USPS (Figure 8); thus, the
distributions of $\mathbf{X}$ are different in both datasets.

|
---|---
Figure 8: Image samples from MNIST and USPS

###  B.3 A regression experiment

We present a regression experiment using data from 2017, 2018, 2019, and 2020
of ENEM161616Data extracted from https://www.gov.br/inep/pt-br/acesso-a-
informacao/dados-abertos/microdados/enem, the “Brazilian SAT.” In each of the
years, $Y$ is given by the students’ math score in a logarithmic scale while
$\mathbf{X}$ is composed of six of their personal and socioeconomic features:
gender, race, school type (private or public), mother’s education, family
income and the presence of a computer at home. We randomly subsample the data
in each one of the years to 30k data points with $10\%$ of them going to the
test portion and then use the CatBoost algorithm to estimate the Radon-Nikodym
derivative and the conditional distribution of $Y|\mathbf{X}$. When estimating
the distribution of $Y|\mathbf{X}$, we first fit a regressor to predict $Y$
given $\mathbf{X}$, and then, using a holdout set, we fit a Gaussian model on
the residuals. When testing for a shift in the $\mathbf{X}|Y$ distribution, we
discretize $Y$ in 10 bins, evenly splitting the data. Even though we use the
binned version of $Y$ to get the $p$-value, we report
$\hat{\text{KL}}_{\mathbf{X}|Y}$ in the first panel of Figure 9. In this
experiment, we do a similar analysis compared to the credit one, comparing the
probability distributions of 2018, 2019, and 2020 with the one in 2017. From
Figure 9, it is possible to see that we detected all kinds of shifts after
2017. This result indicates that a model trained in 2017 might not generalize
well to other years, and practitioners may consider retraining their models
from scratch using more recent data.

Figure 9: Detecting different types of dataset shift in a regression
experiment. Using data from ENEM, the “Brazilian SAT,” we do a similar
analysis compared to the credit one, comparing the probability distributions
of 2018, 2019, and 2020 with the one in 2017. In this experiment, $Y$ is given
by the student’s math score on the logarithmic scale, while $\mathbf{X}$
comprises students’ personal and socioeconomic features. It is possible to see
that we detected all kinds of shifts in every moment after 2017. This result
indicates that a model trained in 2017 might not generalize well to other
years, and practitioners may consider retraining their models.

###  B.4 Detecting shifts with deep models

####  B.4.1 Extra plot

Figure 10: Detecting different types of dataset shift using complex high-
dimensional data. For many values of $\delta$, we could detect all types of
shift except conditional shift 1, which is expected because we introduced
response shift in isolation ($\delta\neq.5$ is equivalent to label shift).

####  B.4.2 Extra results

We include one extra experiment using the “60k Stack Overflow Questions with
Quality Rating" dataset171717https://www.kaggle.com/datasets/imoore/60k-stack-
overflow-questions-with-quality-rate [2]. This dataset has three classes of
rating from Stack Overflow questions. We repeat the same procedure to obtain
results for the other deep-learning experiments.

Ours
---
Benchmark
Figure 11: Detecting different types of dataset shift using Stack Overflow
text data. For many values of $\delta$, we could detect all types of shift
except concept shift 1, which is expected because we introduced label shift in
isolation ($\delta\neq.5$ is equivalent to label shift).

###  B.5 Experiments running time

All the experiments were run in a MacBook Air (M1, 2020) 16GB, except for the
credit analysis experiment in an 80 CPUs Intel Xeon Gold 6148 cluster. We
consider one iteration as all the steps needed to compute all the $p$-values
used for a specific experiment. In the artificial data experiments, on
average, each iteration performed by our framework took less than $1s$, while
in real data experiments, each iteration took less than $200s$.