PaperlayerView exact revision on arXiv

Source-linked AI summary

Sample Selection Bias Correction Theory

Corinna Cortes, Mehryar Mohri, Michael Riley, Afshin Rostamizadeh

arXiv:0805.2775v1cs.LG

TL;DR

Sample selection bias correction reweights biased training errors to better match an unbiased distribution, but finite-sample weight estimates may be inaccurate. The paper develops a distributional-stability analysis of this effect for cluster-based estimation and KMM, with experiments on several data sets. It concludes that the framework and proof techniques can also support analyses of other importance-weighting settings.

  • Problem

    Training and test distributions can differ, while correction relies on weights estimated from finite samples whose effect on hypothesis accuracy lacks a general analysis.

  • Method

    The paper uses distributional stability to analyze estimation-error bounds for cluster-based reweighting and kernel mean matching.

  • Results

    The analysis covers kernel-based regularization algorithms and reports experiments showing that clustering-based reweighting with more reliable counts can be effective, while KMM results are consistent with prior reports.

  • Takeaways & Limitations

    The distributional-stability techniques can be applied to other importance-weighting algorithms and contexts such as learning with uncertain labels.

  • Takeaways & Limitations

    The clustering analysis assumes roughly uniform cluster sizes and equal sampling probabilities within each cluster, while the kernel analysis assumes a bounded universal kernel with positive smallest eigenvalue.

Abstract

from arXiv · show

This paper presents a theoretical analysis of sample selection bias correction. The sample bias correction technique commonly used in machine learning consists of reweighting the cost of an error on each training point of a biased sample to more closely reflect the unbiased distribution. This relies on weights derived by various estimation techniques based on finite samples. We analyze the effect of an error in that estimation on the accuracy of the hypothesis returned by the learning algorithm for two estimation techniques: a cluster-based estimation technique and kernel mean matching. We also report the results of sample bias correction experiments with several data sets using these techniques. Our analysis is based on the novel concept of distributional stability which generalizes the existing concept of point-based stability. Much of our work and proof techniques can be used to analyze other importance weighting techniques and their effect on accuracy when using a distributionally stable algorithm.

1 Introduction

Sample selection bias arises when training and test data follow different distributions, a common situation across several applied fields. The paper analyzes how errors in estimated correction weights affect learned hypotheses using distributional stability and two estimation techniques.

  • Training and test samples often differ because data collection or labeling constraints bias the available training sample.The problem appears in areas including astronomy, econometrics, and species habitat modeling.
  • Sample selection bias can sometimes be corrected using large amounts of unlabeled data drawn from the test distribution.
  • Common correction methods reweight training errors so their costs more closely reflect the test distribution.
  • Finite-sample errors in estimated sampling probabilities can affect the accuracy of the returned hypothesis, a problem not previously analyzed generally.
  • Distributional stability generalizes point-based stability and establishes stability results for broad families of kernel-based regularization algorithms.The paper gives stability coefficients for both l1 and l2 distances, including algorithms such as SVR and kernel ridge regression.
  • The paper derives bounds for cluster-based estimation and KMM, compares them, and evaluates both techniques on several public data sets.The analysis is intended to extend to other importance-weighting techniques used with distributionally stable algorithms.

2 Sample Selection Bias Correction

Sample selection bias correction reweights biased labeled training data to approximate the true test distribution, often using unlabeled data. The section formalizes this correction and motivates analyzing how imperfect weight estimates affect hypothesis accuracy.

  • The true distribution D generates test points, while the learner receives labeled points from a biased distribution D′ represented by sampling variable s.The support of D′ is included in the support of D.
  • A weighted sample assigns each training point a non-negative weight that emphasizes or de-emphasizes its error cost for weight-sensitive algorithms.
  • With perfect reweighting, weights based on the sampling probability can recover the true distribution from the biased one.
  • For weight-sensitive algorithms, correction is needed only for the biased training sample, and sampling probabilities need be estimated only at its points.Under exact reweighting, the expected weighted empirical error matches learning from the true distribution, so usual generalization bounds apply.
  • When sampling is label-independent, unlabeled data can estimate the needed probabilities; for discrete points, frequencies in biased and full data provide a simple estimator.
  • Because estimated weights are generally imperfect, the next analysis studies how estimation error changes the returned hypothesis's error rate.

3 Distributional Stability

Distributional stability extends point-based stability by relating changes in a sample’s weight distribution to changes in prediction cost. The paper establishes this property for broad families of kernel-based regularization algorithms, including SVR and kernel ridge regression.

  • 3 Distributional Stability: Distributional stability generalizes point-based stability from changing one sample point to changing the sample’s weight distribution.The framework measures changes between weighted samples using a divergence such as relative entropy, Hellinger distance, or an l_p distance.
  • 3 Distributional Stability: An algorithm is distributionally β-stable when small divergence between weighted samples produces small changes in error cost at every point.The definition bounds the cost difference by β times the divergence d(W, W′).
  • 3.1 Distributional Stability of Kernel-Based Regularization Algorithms: Kernel-based regularization algorithms, including SVR, kernel ridge regression, and margin-loss SVMs, are shown to be distributionally stable.The result assumes bounded kernel values and, for the cost function, σ-admissibility; related regularization algorithms can be handled similarly.
  • 3.1 Distributional Stability of Kernel-Based Regularization Algorithms: The stability analysis derives bounds for both l1 and l2 distances between weighted-sample distributions.The proofs use convex regularization, reproducing-kernel properties, Cauchy–Schwarz, and Rayleigh-quotient bounds.
  • 3.1 Distributional Stability of Kernel-Based Regularization Algorithms: Uniform point-based stability is a special case of distributional stability for kernel-based regularized algorithms under the l1 distance.The uniform sample assigns weight 1/m to each point, while removing one point assigns zero weight to it and 1/(m − 1) to the others.

4 Effect of Estimation Error for Kernel-Based Regularization Algorithms

This section bounds how errors in cluster-based frequency estimates and KMM weights affect hypotheses produced by kernel-based regularization algorithms. The analysis connects weight-distribution error to generalization-error differences through distributional stability, with convergence depending on sampling frequencies and kernel properties.

  • 4 Effect of Estimation Error for Kernel-Based Regularization Algorithms: The section analyzes cluster-based frequency estimation and kernel mean matching as two ways to estimate sample-bias correction weights.The goal is to quantify their effect on the generalization error of the returned hypothesis.
  • 4.1 Cluster-Based Estimation: Cluster-based estimation uses empirical sampling frequencies after partitioning the input space into histogram buckets or clusters.Partitioning avoids relying on repeated exact feature vectors, which are often unique or infrequent for real-valued data.
  • 4.1 Cluster-Based Estimation: The cluster-based error bound depends essentially on how quickly the least frequent training example becomes frequent in the unlabeled sample.For large n, the least-frequency count n0 approximates p0n; the number of distinct sample points contributes only a small logarithmic term.
  • 4.1 Cluster-Based Estimation: Under λmax(K) ≤ m, including Gaussian-kernel settings, the l2-based cluster-bound convergence is at least as fast.The comparison concerns convergence of the error-rate difference between optimal reweighting and frequency-estimated reweighting.
  • 4.2 Kernel Mean Matching: KMM matches average feature-vector values between biased training data and unlabeled unbiased data, relying on injectivity for universal kernels.For universal kernels, the expected feature vector uniquely determines the probability distribution.
  • 4.2 Kernel Mean Matching: With high probability, the l2 distance between normalized KMM weights and perfect weights is bounded under a strictly positive definite universal kernel.The KMM optimization constrains the feature-mean mismatch and weight range, with ǫ assumed no larger than 1/2.
  • 4.2 Kernel Mean Matching: The bounds compare cluster-based and KMM convergence, with the more favorable technique depending on the parameter values.The cluster-based bound is more favorable for some values, while KMM converges faster for others.

5 Experimental Results

The experiments compare cluster-based reweighting with KMM for sample bias correction, using decision-tree leaves to estimate sampling probabilities and applying the resulting weights to training data. The results indicate that clustering can make reweighting effective, while KMM outcomes are consistent with prior reports.

  • Experimental setup: The experiments compare cluster-based reweighting and KMM empirically on several regression data sets.Table 1 reports normalized mean-squared error for unweighted, ideal, clustered, and kernel-mean-matched reweightings.
  • Reweighting methods: The experiments estimate sampling probabilities with clusters but apply the resulting weights to the full training set rather than training only on cluster representatives.The associated bounds remain similar when cluster sizes are roughly uniform and sampling probability is constant within each cluster.
  • Theoretical comparison: Uniform cluster sizes yield |CM|k = m, producing a bound similar to Proposition 5.This connects the clustered analysis to the earlier distribution-distance bound.
  • Clustering method: Decision-tree leaves define clusters whose points are assumed to have similar sampling probabilities.The tree greedily selects coordinate cuts using node impurity measures such as MSE for regression.
  • Reweighting methods: The clustered method assigns each training point weight |Ci ∩U|/|Ci ∩S|, using regression-tree leaves with a minimum count of 4.Larger cluster sizes showed similar but declining performance.
  • Implementation caveat: KMM used a Gaussian kernel with σ = d/2, B = 1000, and ϵ = 0, but no principled cross-validation method was known for it.KMM cannot produce weights for a held-out set.
  • Results: Reweighting with more reliable clustered counts can be effective, and the results confirm the theoretical dependence on n0.KMM results were consistent with those reported by the technique's authors.

6 Conclusion

The conclusion presents a general analysis of sample selection bias correction and bounds the effect of estimation error on returned hypotheses. It emphasizes that the stability concepts and proof techniques may extend to other importance-weighting and uncertain-label settings.

  • 6 Conclusion: The paper gives bounds on how estimation error affects the accuracy of hypotheses returned under sample selection bias correction.This is framed as a general analysis rather than a technique-specific result.
  • 6 Conclusion: Distributional-stability techniques may also analyze other importance-weighting algorithms and learning with uncertain labels.The conclusion says the techniques apply similarly in those settings.
  • 6 Conclusion: The analysis of a discriminative covariate-shift method could benefit from this study.This is presented as a possible extension.

A Proof of Theorem 3

The proof establishes that the kernel mean embedding is injective by approximating continuous functions with functions induced by a universal kernel. Equality of embeddings therefore implies equality of the underlying distributions.

  • A Proof of Theorem 3: For two distributions p and q, equal kernel mean embeddings imply equal expectations for every continuous function.The proof uses universality to approximate any continuous f uniformly by a function induced by K.
  • A Proof of Theorem 3: A function induced by K is represented as an inner product ⟨w, Φ(x)⟩ in the feature space.The proof expands this representation using a countable orthonormal basis.
  • A Proof of Theorem 3: Continuity of the universal kernel and compactness of X provide a uniform bound on the feature map norm.This supports the treatment of the partial sums in the feature-space expansion.
  • A Proof of Theorem 3: The expectation difference for the approximating function is expressed through the inner product of w with the mean embedding.The same equality is established for q, allowing the approximation error to vanish as ϵ approaches zero.
  • A Proof of Theorem 3: Because the equality holds for every ϵ > 0, expectations agree for all continuous functions and p = q.This completes the injectivity argument for µ.
Loading 0805.2775v1…