PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified View of Label Shift Estimation

Saurabh Garg, Yifan Wu, Sivaraman Balakrishnan, Zachary C. Lipton

arXiv:2003.07554v3cs.LGstat.ML

TL;DR

Label shift estimation must recover changed label proportions when class-conditional features remain fixed, but existing methods differ in calibration and optimization. This paper unifies BBSE and MLLS, characterizes MLLS theoretically, and finds that calibration—not the matching objective—accounts for MLLS’s empirical advantage.

  • Problem

    The paper addresses how to estimate target label distributions under label shift when p(y) changes but p(x|y) remains fixed.

  • Method

    The paper provides a unified calibration-based framework for BBSE and MLLS, proves MLLS consistency conditions, and decomposes its finite-sample error.

  • Results

    MLLS achieves 2–10× lower Mean Squared estimation Error (MSE) depending on shift magnitude, with its advantage attributed to more granular calibration rather than its objective.

  • Takeaways & Limitations

    BBSE corresponds to a particular calibration choice, while calibration granularity is the supported explanation for MLLS’s empirical advantage.

  • Takeaways & Limitations

    The analysis assumes label shift and focuses on estimating target label distributions rather than broadly changing machine-learning practice.

Abstract

from arXiv · show

Under label shift, the label distribution p(y) might change but the class-conditional distributions p(x|y) do not. There are two dominant approaches for estimating the label marginal. BBSE, a moment-matching approach based on confusion matrices, is provably consistent and provides interpretable error bounds. However, a maximum likelihood estimation approach, which we call MLLS, dominates empirically. In this paper, we present a unified view of the two methods and the first theoretical characterization of MLLS. Our contributions include (i) consistency conditions for MLLS, which include calibration of the classifier and a confusion matrix invertibility condition that BBSE also requires; (ii) a unified framework, casting BBSE as roughly equivalent to MLLS for a particular choice of calibration method; and (iii) a decomposition of MLLS's finite-sample error into terms reflecting miscalibration and estimation error. Our analysis attributes BBSE's statistical inefficiency to a loss of information due to coarse calibration. Experiments on synthetic data, MNIST, and CIFAR10 support our findings.

1 Introduction

The paper studies label shift, where class-conditional features remain fixed while label proportions change, and develops a unified theoretical and empirical account of BBSE and MLLS. It characterizes MLLS consistency, relates the methods through calibration, and finds lower MLLS estimation error in experiments.

  • Problem setting: Label shift changes p(y) while preserving p(x|y), motivating estimation of target label proportions from unlabeled target data.The setting is relevant to domain adaptation, but assumptions about the type of shift are needed to make the problem identifiable.
  • Existing approaches: BBSE uses moment matching and confusion matrices, whereas MLLS uses maximum likelihood with classifier outputs to estimate the shift.BBSE has known consistency and finite-sample guarantees under an invertible confusion matrix; MLLS had been observed to perform better empirically with calibration.
  • Contributions: The paper proves MLLS consistency under canonical calibration and an invertible confusion matrix, the latter also required by BBSE.It additionally shows that calibration can sometimes be necessary for consistency.
  • Contributions: The paper unifies BBSE and MLLS by treating BBSE as corresponding to a particular calibration choice, and attributes MLLS’s advantage to finer calibration rather than its objective.This conclusion is supported by experiments comparing methods under matched calibration choices.
  • Empirical validation: MLLS achieves 2–10× lower Mean Squared estimation Error (MSE) depending on shift magnitude across synthetic data, MNIST, and CIFAR-10.The experiments relate MLLS’s MSE to calibration granularity.

2 Problem Setup

The problem setup assumes label shift and focuses on estimating target-to-source label importance weights. These estimates support target prediction correction, while calibration is treated as a central property of the black-box predictor.

  • Assumptions: The setup assumes ps(x|y) = pt(x|y) and non-zero source support for every label.The paper focuses on multiclass classification under the label shift assumption.
  • Goal: The paper focuses on quantification: estimating w(y) = pt(y)/ps(y) for every label y.Detection and correction are identified as related domain adaptation goals but are not the paper’s primary focus.
  • Use of estimates: Estimated importance weights can update classifiers through importance-weighted ERM or analytic correction.Within the ERM framework, better weight estimates tighten a generalization bound that depends on weight-estimation error.
  • Calibration: Canonical calibration requires Ps(y = j|f(x)) = f_j(x) for every input x and label j.The expected squared canonical calibration error measures the distance between f and the conditional label distribution given f(x).
  • Calibration: The experiments use post-hoc calibration, including Bias-Corrected Temperature Scaling, which extends temperature scaling with per-class bias terms.The paper distinguishes calibration during training from calibration of a trained classifier on held-out data.

3 Prior Work

Prior work estimates label shift with black-box predictors using either confusion-matrix moment matching or maximum likelihood. BBSE and RLLS rely on confusion-matrix-based estimation, while MLLS substitutes predictor outputs into a likelihood objective.

  • BBSE and RLLS: BBSE estimates shift ratios by applying a black-box predictor to source and target data and inverting an estimated confusion matrix.The confusion matrix may be hard, based on arg-max predictions, or soft, based on randomized predictions from predictor outputs.
  • BBSE and RLLS: RLLS extends the confusion-matrix approach with a regularization term penalizing deviation of w from 1.It solves a constrained optimization problem for the shift ratios.
  • MLLS: MLLS estimates shift ratios by performing maximum likelihood while substituting predictor outputs for the unknown probabilities ps(y|x).Although introduced as an EM procedure, its likelihood objective is concave, allowing multiple optimization algorithms.
  • MLLS: Prior empirical work found that naive MLLS can underperform BBSE, while calibrated MLLS can achieve low error and outperform BBSE and RLLS.The paper uses this contrast to motivate its analysis of calibration and objective choice.

4 A Unified View of Label Shift Estimation with Black Box Predictors

The paper unifies BBSE and MLLS as distribution-matching methods distinguished by their calibrated representation and matching objective. It establishes MLLS consistency conditions, connects BBSE to a calibrated MLLS special case, and relates estimation error to miscalibration and finite sampling.

  • Unified distribution matching: Identifiability requires the class-conditional distributions {p(z|y)} to be linearly independent; with discrete Z, this becomes confusion-matrix invertibility.Without this condition, distinct weight vectors can satisfy the same matching equations.
  • The confusion matrix approach: Confusion-matrix methods use Z = Y, with soft predictions sampling from bf(x) and hard predictions taking arg max bf(x).The resulting source joint distribution and target marginal can be estimated from labeled source and unlabeled target data.
  • Maximum likelihood label shift estimation: With a calibrated predictor, MLLS is equivalent to distribution matching in the predictor-output space, and its population estimate is consistent under the required identifiability condition.The finite-sample estimator converges almost surely when the conditions of the population theorem hold.
  • MLLS with confusion matrix: BBSE and MLLS share the same calibration and identifiability requirements, but differ in distribution matching: BBSE solves linear equations whereas MLLS minimizes a likelihood-related objective.Using confusion-matrix calibration inside MLLS yields a BBSE analog that is a special case of MLLS.
  • Unified distribution matching: A label-shift estimator chooses a latent representation p(z|x) and then matches source and target distributions in that space.This framework separates representation design from the distribution-matching procedure.

5 Theoretical Analysis of MLLS

MLLS estimation error arises from finite target samples and predictor miscalibration, while its consistency and efficiency depend on calibration and Hessian invertibility. Coarse confusion-matrix calibration discards information, explaining BBSE-like inefficiency.

  • Theoretical bounds separate target-sample error from error caused by using a miscalibrated predictor.
  • MLLS estimation error decomposes into finite-sample error, which decays as m^-1/2, and predictor calibration error.
  • MLLS and BBSE have analogous rate dependencies, but MLLS uses the minimum Hessian eigenvalue whereas BBSE uses the confusion-matrix eigenvalue.
  • MLLS error depends inversely on the minimum Hessian eigenvalue, so coarse calibration increases error by reducing this quantity and discarding information.
  • The target-side Hessian invertibility condition can be stronger than the source-side condition, and the gap is left for future work.

6 Experiments

Experiments on synthetic data, MNIST, and CIFAR-10 compare MLLS with BBSE, RLLS, and confusion-matrix-calibrated MLLS across shift magnitudes and target sample sizes. MLLS performs best, while finer calibration reduces error and improves Hessian conditioning.

  • MLLS with BCTS-calibrated classifiers uniformly dominates BBSE, RLLS, and MLLS-CM in MSE across shifts and target sizes.
  • MLLS’s advantage grows under extreme shifts and remains significant as target data increases.
  • MLLS-CM is roughly equivalent to BBSE, linking MLLS’s advantage to prediction granularity rather than the distribution-matching loss.
  • Increasing calibration bins decreases MSE and increases the minimum Hessian eigenvalue.
  • Confusion-matrix calibration performs poorly; with true predictors, more bins strictly improve MSE, though fixed source data can make many bins overfit.

7 Conclusion

The paper unifies label-shift estimators by treating them as calibration and optimization choices. It attributes MLLS’s advantage over BBSE to more granular calibration and identifies calibration guidance as future work.

  • The framework relates methods using off-the-shelf predictors for label-shift estimation.
  • BBSE corresponds to a particular calibration method within the common framework.
  • MLLS with BCTS outperforms BBSE because of calibration choice rather than the distribution-matching optimization objective.
  • Future work will operationalize these insights into guidance for calibration schemes.

Broader Impact

The paper studies the consistency and efficiency of label-shift estimators as a foundational theoretical problem. The authors do not identify a significant societal concern from this work.

  • The work addresses statistical consistency and efficiency for estimating target-domain label distributions.
  • The authors believe the work does not present a significant societal concern.

A MLLS Algorithm

The algorithm calibrates a black-box classifier on labeled source validation data, then uses the calibrated predictor to estimate label-shift weights from unlabeled target data. The section situates this procedure among label-shift estimation methods and calibration choices.

  • Algorithm: MLLS takes labeled source validation samples and unlabeled target samples as input, together with a trained black-box model, calibration model class, and loss.
  • Algorithm: It first minimizes a calibration loss over the model class on validation data to obtain a calibrated predictor.The loss may be mean squared error or negative log-likelihood.
  • Algorithm: It then solves the MLLS optimization problem using the calibrated predictor and outputs the estimated importance-weight vector.
  • Calibration: BCTS extends temperature scaling with per-class bias terms and is used experimentally as a surrogate for canonical calibration.The BCTS class has |Y| + 1 learned parameters: one temperature and one bias for each class.
  • Context: Label-shift estimators include BBSE and RLLS, which use moment matching, and MLLS, which uses maximum likelihood with classifier outputs.MPE alternatives can require explicit class-conditional calculations or inversion of an n × n Gram matrix, making them infeasible for large data in the cited discussion.

C Marginal calibration is insufficient to achieve consistency

The section shows that marginal calibration is weaker than canonical calibration and does not guarantee consistent MLLS estimates. A constructed discrete example yields a population estimate different from the true importance weights.

  • Definitions: Marginal calibration is defined as a per-label calibration condition and is strictly less restrictive than canonical calibration.
  • Counterexample: The constructed classifier is marginally calibrated but not canonically calibrated, and its population MLLS objective produces inconsistent estimates.
  • Construction: The example uses a discrete feature space with six feature values and three labels, with a one-to-one mapping from features to predictions.The source feature marginal is uniform, giving source label probabilities of 1/3 for each class.
  • Construction: Under label shift, the target label prior is parameterized as [α, β, 1 − α − β], and the target feature probabilities are formed from the corresponding source posterior terms.
  • Counterexample: For α = 0.8 and β = 0.1, MLLS estimates [2.505893, 0.240644, 0.253463] instead of the true weights [2.4, 0.3, 0.3].

D Proofs from Section 4

The proofs establish MLLS identifiability and consistency under calibration and a linear-independence condition equivalent to soft confusion-matrix invertibility. They also show that calibrated MLLS shares its objective with a related formulation and converges almost surely under the stated conditions.

  • Identifiability: Linear independence of the class-conditional prediction distributions identifies the importance-weight vector uniquely.Without linear independence, a problem instance can admit distinct weight vectors satisfying the same target-mixture equations.
  • Objective equivalence: For a calibrated predictor, the MLLS objectives coincide when the auxiliary variable ranges over the probability simplex and its conditional distribution is concentrated at the predictor output.
  • Population consistency: Calibration and strict linear independence of {p(f(x)|y)} are sufficient for the true weight vector to be the unique maximizer of the population MLLS objective.
  • Population consistency: For calibrated predictors, strict linear independence of the class-conditional prediction distributions is equivalent to invertibility of the soft confusion matrix.
  • Finite-sample consistency: Under the conditions of the population theorem, the finite-sample MLLS estimator converges to the true weight vector almost surely.The proof proceeds through entropy bounds, Hellinger and total-variation convergence, and the confusion-matrix eigenvalue condition.
  • Finite-sample consistency: The proof accommodates weights bounded away from zero and separately handles cases where the true weights can approach zero using truncated function classes.
  • Example: A two-Gaussian threshold-classifier example shows that the population MLLS error is zero only for a specific non-degenerate classifier calibration.

E Proofs from Section 5

The proofs decompose MLLS error into calibration and sampling components. They derive bounds using curvature, concentration, and regularity assumptions, with calibration error controlling the population discrepancy and empirical estimation contributing an additional finite-sample term.

  • Estimation error: The empirical MLLS error analysis uses Taylor expansion of the empirical negative log-likelihood and concentration of gradient differences.
  • Estimation error: For predictors satisfying the lower-bound condition, the distance between population and empirical MLLS weights is controlled by curvature and sampling fluctuations.
  • Estimation error: The resulting high-probability bound combines the empirical concentration terms through a union bound.
  • Calibration error: The population estimation error from using an uncalibrated predictor is bounded by a condition-dependent factor times its discrepancy from a calibrated predictor.
  • Calibration error: The calibration-error bound follows from a Taylor expansion around the true weights and a Lipschitz bound on the gradient.
  • Calibration error: For post-hoc calibration with squared loss, regularity conditions on the calibration class yield a bound on calibration error that can be inserted into the MLLS error decomposition.The stated regularity conditions include injectivity, Lipschitz continuity, twice differentiability, a nonsingular Hessian, and consistency.
  • Conditioning: The analysis relates the conditioning factors to the minimum class probability and the minimum eigenvalue of the predictor-dependent matrix.
Loading 2003.07554v3…