Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Distribution Shift & Robustness

When the test world differs from the training world.

Every guarantee in this topic assumed that test data come from the training distribution. Deployment breaks that assumption: a diagnostic model moves to a hospital with different patients, an epidemic changes disease prevalence, spammers change tactics. This lesson classifies the ways a distribution can shift, derives what can be corrected (importance weighting for covariate shift, prior correction and estimation for label shift), proves the bound of Ben-David et al. that frames domain adaptation, and surveys what robustness benchmarks show.

What you’ll learn

  • Define covariate, label and concept shift by which factor of the joint distribution changes, and judge which assumption fits a problem.
  • Derive importance weighting, its variance and effective sample size, and estimate density ratios with a domain classifier.
  • Correct calibrated probabilities for a new prevalence, and estimate that prevalence from unlabeled data.
  • Prove the Ben-David et al. (2010) domain-adaptation bound and explain what it does and does not justify.

A taxonomy of shift

A source distribution PS(x,y)P_S(\mathbf x,y) produced the training data; a target PT(x,y)P_T(\mathbf x,y) will produce the inputs the model meets. With no assumption linking them, the source says nothing about the target. Each standard kind of distribution shift keeps one factor of the joint distribution fixed:

ShiftChangesStays fixedTypical setting
Covariate shiftp(x)p(\mathbf x)p(y∣x)p(y\mid\mathbf x)new sites or sensors; selection of who gets labeled
Label (prior) shiftp(y)p(y)p(x∣y)p(\mathbf x\mid y)an epidemic changes prevalence; fraud rates vary by season
Concept shiftp(y∣x)p(y\mid\mathbf x)possibly p(x)p(\mathbf x)adversaries adapt; definitions or policies change
Subpopulation shiftgroup proportionseach group's distributiona minority group is common at deployment

Causal direction suggests which assumption is plausible (Schölkopf et al., 2012). When x\mathbf x causes yy, the mechanism p(y∣x)p(y\mid\mathbf x) tends to be stable, so covariate shift is natural. When yy causes x\mathbf x, as a disease causes symptoms, p(x∣y)p(\mathbf x\mid y) tends to be stable, so label shift is natural. The two are generally incompatible: if p(y)p(y) changes while p(x∣y)p(\mathbf x\mid y) stays put, Bayes' rule changes p(y∣x)p(y\mid\mathbf x) wherever the classes overlap.

Covariate shift: importance weighting

DerivationReweighting the risk, and what it costs
  1. RT(h)=ET[ℓ(h(X),Y)]=ES[w(X) ℓ(h(X),Y)]R_T(h)=\E_T\big[\ell(h(X),Y)\big]=\E_S\big[w(X)\,\ell(h(X),Y)\big]

    Assume pT(y∣x)=pS(y∣x)p_T(y\mid\mathbf x)=p_S(y\mid\mathbf x) and that pS>0p_S>0 wherever pT>0p_T>0. With the importance weight w(x)=pT(x)/pS(x)w(\mathbf x)=p_T(\mathbf x)/p_S(\mathbf x), a change of measure turns target risk into a source expectation:

  2. ES[w(X)2]=∫pT(x)2pS(x) dx=1+χ2(PT ∥ PS)\E_S\big[w(X)^2\big]=\int\frac{p_T(\mathbf x)^2}{p_S(\mathbf x)}\,d\mathbf x=1+\chi^2\big(P_T\,\|\,P_S\big)

    So the weighted average 1n∑iw(xi)ℓi\frac1n\sum_iw(\mathbf x_i)\ell_i over source data is unbiased for RT(h)R_T(h). For a loss bounded by ℓmax⁡\ell_{\max} its variance is at most ℓmax⁡2 ES[w2]/n\ell_{\max}^2\,\E_S[w^2]/n, and the second moment is a divergence:

  3. pS=N(0,1), pT=N(δ,1):ES[w2]=eδ2,neff≈n e−δ2p_S=\mathcal N(0,1),\ p_T=\mathcal N(\delta,1):\quad\E_S[w^2]=e^{\delta^2},\qquad n_{\text{eff}}\approx n\,e^{-\delta^2}

    Hence the effective sample size neff≈n/ES[w2]n_{\text{eff}}\approx n/\E_S[w^2], estimated in practice by Kish's (∑iwi)2/∑iwi2(\sum_iw_i)^2/\sum_iw_i^2. For a mean shift of δ\delta standard deviations in one Gaussian feature, the cost is exponential in δ2\delta^2:

Predict before you look

A shift moves one Gaussian input feature's mean by 2 standard deviations. Out of 10,000 labeled source examples, what effective sample size remains after importance weighting?

Show the answer

180

10,000×e−4≈18310{,}000\times e^{-4}\approx183. A one-standard-deviation shift keeps about 37%, two keep under 2%. Cortes, Mansour and Mohri (2010) prove learning bounds for importance weighting in terms of exactly this second moment, and show that guarantees fail when it is unbounded.

To estimate ww without estimating two densities, pool the source examples (label SS) with unlabeled target inputs (label TT) and train a probabilistic domain classifier. Bayes' rule converts its odds into the density ratio: w(x)=nSnT⋅Pr⁡(T∣x)Pr⁡(S∣x)w(\mathbf x)=\frac{n_S}{n_T}\cdot\frac{\Pr(T\mid\mathbf x)}{\Pr(S\mid\mathbf x)}. Kernel mean matching (Huang et al., 2007) and KLIEP (Sugiyama et al., 2008) estimate ww directly. Clipping the weights, or flattening them to wλw^\lambda with 0≤λ≤10\le\lambda\le1, trades bias for variance.

Label shift: estimating and correcting the prior

DerivationPrior correction and black-box estimation
  1. pT(y∣x)=w(y) pS(y∣x)∑y′w(y′) pS(y′∣x)p_T(y\mid\mathbf x)=\frac{w(y)\,p_S(y\mid\mathbf x)}{\sum_{y'}w(y')\,p_S(y'\mid\mathbf x)}

    Under label shift, p(x∣y)p(\mathbf x\mid y) is shared. Bayes' rule in each domain gives the target posterior from the source posterior and the prior ratio w(y)=πT(y)/πS(y)w(y)=\pi_T(y)/\pi_S(y):

  2. μT(i)=∑jP(y^=i∣y=j) πT(j)=∑jCij w(j)⟹w^=C^−1μ^T\mu_T(i)=\sum_jP(\hat y=i\mid y=j)\,\pi_T(j)=\sum_jC_{ij}\,w(j)\quad\Longrightarrow\quad\hat{\mathbf w}=\hat C^{-1}\hat{\boldsymbol\mu}_T

    So a calibrated source model is corrected by reweighting and renormalizing its outputs, a shift of the logit bias by log⁡w(y)\log w(y). To estimate πT\pi_T, note that p(y^∣y)p(\hat y\mid y) is also shared. With the source joint confusion matrix Cij=PS(y^=i,y=j)C_{ij}=P_S(\hat y=i,y=j) and the target's predicted-label frequencies μT(i)=PT(y^=i)\mu_T(i)=P_T(\hat y=i) (Lipton, Wang & Smola, 2018):

  3. π^T=q^−FPRTPR−FPR\hat\pi_T=\frac{\hat q-\mathrm{FPR}}{\mathrm{TPR}-\mathrm{FPR}}

    This needs an invertible confusion matrix, not a calibrated model. In the binary case it is Forman's (2008) "adjusted count": a target flag rate q=πT TPR+(1−πT) FPRq=\pi_T\,\mathrm{TPR}+(1-\pi_T)\,\mathrm{FPR} inverts to

Predict before you look

On source data a classifier has TPR 0.575 and FPR 0.095. It flags 12% of a large unlabeled target batch. Estimate the target prevalence, in percent.

Show the answer

5.2 %

(0.12−0.095)/(0.575−0.095)=0.025/0.48≈5.2%(0.12-0.095)/(0.575-0.095)=0.025/0.48\approx5.2\%. Taking the flag rate at face value, 12%, more than doubles the answer, because at low prevalence most flags are false positives.

The alternative is maximum likelihood by EM (Saerens, Latinne & Decaestecker, 2002): alternate between correcting the posteriors with the current prior estimate and resetting the prior to their mean. With well-calibrated models it is hard to beat (Alexandari, Kundaje & Shrikumar, 2020).

Bounds, invariance and robustness in practice

DerivationProof
  1. εT(h)≤εT(h∗)+εT(h,h∗)\varepsilon_T(h)\le\varepsilon_T(h^*)+\varepsilon_T(h,h^*)

    Let h∗h^* attain λ\lambda. Disagreement obeys the triangle inequality, since 1[h≠f]≤1[h≠g]+1[g≠f]\mathbf 1[h\neq f]\le\mathbf 1[h\neq g]+\mathbf 1[g\neq f]:

  2. εT(h,h∗)≤εS(h,h∗)+∣εT(h,h∗)−εS(h,h∗)∣≤εS(h,h∗)+12dHΔH(DS,DT)\varepsilon_T(h,h^*)\le\varepsilon_S(h,h^*)+\big|\varepsilon_T(h,h^*)-\varepsilon_S(h,h^*)\big|\le\varepsilon_S(h,h^*)+\tfrac12d_{\mathcal H\Delta\mathcal H}(D_S,D_T)

    Move the disagreement to the source. Because h,h∗∈Hh,h^*\in\mathcal H, the change is controlled by the divergence:

  3. εS(h,h∗)≤εS(h)+εS(h∗) ⟹ εT(h)≤εS(h)+12dHΔH+εS(h∗)+εT(h∗)⏟λ\varepsilon_S(h,h^*)\le\varepsilon_S(h)+\varepsilon_S(h^*)\ \Longrightarrow\ \varepsilon_T(h)\le\varepsilon_S(h)+\tfrac12d_{\mathcal H\Delta\mathcal H}+\underbrace{\varepsilon_S(h^*)+\varepsilon_T(h^*)}_{\lambda}

    Apply the triangle inequality on the source and collect terms:

The bound says that adaptation works when the source error is small, the domains look alike to the class's disagreement tests, and one hypothesis does well on both. It motivated domain-adversarial training (Ganin et al., 2016), which learns features on which a domain classifier fails. But λ\lambda cannot be estimated without target labels, and making feature distributions match can raise it: Zhao et al. (2019) proved that when label distributions differ, invariant representations force a lower bound on the joint error.

Empirically, ImageNet-C (Hendrycks & Dietterich, 2019) measures robustness to synthetic corruptions and WILDS (Koh et al., 2021) to real shifts across hospitals, locations and time. Across many models and natural shifts, out-of-distribution accuracy is close to a linear function of in-distribution accuracy after a probit transform, "accuracy on the line" (Miller et al., 2021); gains above that line, effective robustness (Taori et al., 2020), are rare, and the clearest came from training on much more diverse data, as in CLIP (Radford et al., 2021). On domain-generalization benchmarks, carefully tuned empirical risk minimization matched specialized algorithms (Gulrajani & Lopez-Paz, 2021). For subpopulation shift, group distributionally robust optimization minimizes the worst group's loss (Sagawa et al., 2020).

Key takeaways

  • Covariate shift fixes p(y∣x)p(y\mid\mathbf x), label shift fixes p(x∣y)p(\mathbf x\mid y), concept shift changes p(y∣x)p(y\mid\mathbf x); causal direction suggests which assumption fits, and only concept shift is invisible without target labels.
  • Importance weighting w=pT/pSw=p_T/p_S makes source risk unbiased for the target, but its variance scales with 1+χ2(PT ∥ PS)1+\chi^2(P_T\,\|\,P_S): a 2-SD Gaussian mean shift leaves about e−4≈2%e^{-4}\approx2\% of the sample.
  • Domain classifiers estimate density ratios; weighting matters most for misspecified models and cannot fix missing support.
  • Under label shift, rescale calibrated posteriors by πT/πS\pi_T/\pi_S, and estimate πT\pi_T from unlabeled data by inverting the confusion matrix (BBSE, adjusted count) or by EM.
  • Ben-David et al.: εT≤εS+12dHΔH+λ\varepsilon_T\le\varepsilon_S+\tfrac12d_{\mathcal H\Delta\mathcal H}+\lambda. The unobservable λ\lambda limits invariant-representation methods, and in practice out-of-distribution accuracy tracks in-distribution accuracy ("accuracy on the line").

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A diagnostic model maps symptoms to diseases. During an epidemic one disease becomes three times as common, but each disease's symptom profile is unchanged. What kind of shift is this, and what correction fits?

  1. Covariate shift; reweight training examples by pT(x)/pS(x)p_T(\mathbf x)/p_S(\mathbf x)
  2. Concept shift; nothing can be done without new labels
  3. Label shift; rescale calibrated posteriors by πT(y)/πS(y)\pi_T(y)/\pi_S(y), estimating πT\pi_T from unlabeled data if needed
  4. No shift, since the symptom profiles are unchanged
Show the answer

C. Label shift; rescale calibrated posteriors by πT(y)/πS(y)\pi_T(y)/\pi_S(y), estimating πT\pi_T from unlabeled data if needed

p(x∣y)p(\mathbf x\mid y) is fixed and p(y)p(y) changed: label shift, the natural case for an anticausal problem. Reweight and renormalize the posteriors, with πT\pi_T from BBSE or EM.

Question 2

Importance weighting gives an unbiased estimate of target risk. Why can it still fail badly?

  1. Its variance grows with ES[w2]=1+χ2(PT ∥ PS)\E_S[w^2]=1+\chi^2(P_T\,\|\,P_S), which can be enormous or infinite, leaving a tiny effective sample size
  2. It is biased whenever the model is misspecified
  3. It only works for classification losses
  4. It requires labels from the target domain
Show the answer

A. Its variance grows with ES[w2]=1+χ2(PT ∥ PS)\E_S[w^2]=1+\chi^2(P_T\,\|\,P_S), which can be enormous or infinite, leaving a tiny effective sample size

Unbiasedness says nothing about variance. A few examples with huge weights dominate the estimate; for a 2-standard-deviation Gaussian shift, neff≈n e−4n_{\text{eff}}\approx n\,e^{-4}. Without source support where the target has mass, the weights are infinite.

Question 3

Which term of the bound εT(h)≤εS(h)+12dHΔH+λ\varepsilon_T(h)\le\varepsilon_S(h)+\tfrac12d_{\mathcal H\Delta\mathcal H}+\lambda cannot be estimated without labeled target data?

  1. εS(h)\varepsilon_S(h)
  2. dHΔHd_{\mathcal H\Delta\mathcal H}
  3. Every term needs target labels
  4. λ\lambda, the best joint error over both domains
Show the answer

D. λ\lambda, the best joint error over both domains

εS(h)\varepsilon_S(h) uses source labels, and the divergence only asks whether classifiers disagree, which needs inputs alone. λ\lambda involves εT(h∗)\varepsilon_T(h^*), which needs target labels, and aligning representations can silently increase it.

Question 4

You have plenty of unlabeled data from the target domain. Which change could it never reveal?

  1. A change in the distribution of inputs
  2. A change in p(y∣x)p(y\mid\mathbf x) with p(x)p(\mathbf x) unchanged
  3. A change in class prevalence under label shift
  4. A new cluster of inputs absent from the source
Show the answer

B. A change in p(y∣x)p(y\mid\mathbf x) with p(x)p(\mathbf x) unchanged

Unlabeled data reveal pT(x)p_T(\mathbf x) only. If the inputs look identical while their labels change, every unlabeled test passes; labeled target data are the only way to see it.

Further reading

  • S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira & J. W. Vaughan, "A theory of learning from different domains," Machine Learning 79, 151–175 (2010).
  • H. Shimodaira, "Improving predictive inference under covariate shift by weighting the log-likelihood function," Journal of Statistical Planning and Inference 90, 227–244 (2000).
  • Z. C. Lipton, Y.-X. Wang & A. Smola, "Detecting and correcting for label shift with black box predictors," ICML (2018).
  • J. Quiñonero-Candela, M. Sugiyama, A. Schwaighofer & N. D. Lawrence (eds.), Dataset Shift in Machine Learning (MIT Press, 2009).
  • P. W. Koh et al., "WILDS: A benchmark of in-the-wild distribution shifts," ICML (2021).