Sample Selection Bias Correction Theory

By Corinna Cortes, Mehryar Mohri, Michael D. Riley, Afshin Rostamizadeh. 2008

365 citations recorded by the source corpus.

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 stabilitywhich 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.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Recommendations as Treatments: Debiasing Learning and Evaluation (2016, methodology): “ing theory related to weighting approaches in (Cortes et al., 2008; 2010).”
Ad click prediction: a view from the trenches (2013, neutral): “Since we control the sampling distribution, we do not have to estimate the weights ω as in general sample selection [7].”
Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models (2009, methodology): “techniques similar to those used by Bousquet and Elisseeff [2], or other authors, e.g., [ 6 ], in the analysis of stability.”
Adaptive Risk Minimization: A Meta-Learning Approach for Tackling Group Shift (2020, background): “such as importance weighting the training data [61, 32, 12], representation learning [22, 3], and adversarial training [19, 67, 44].”
Relative deviation learning bounds and generalization with unbounded loss functions (2013, background): “It has applications in areas such as sample bias correction and adaptation [16, 43].”
Recovering Causal Effects from Selection Bias (2015, background): “The selection bias problem has been studied in a wide range of scenarios, for instance, in several tasks in AI (Cooper 1995; Elkan 2001; Zadrozny 2004; Cortes et al. 2008), statistics (Whittemore 1978; Little and Rubin 1986; Jewell 1991; Kuroki and Cai 2006) as well as in the empirical sciences (e.”
Federated Multi-Task Learning under a Mixture of Distributions (2021, neutral): “These weights aim to construct an unbiased estimate of the true risk over each underlying distribution D̃m using only points sampled from the client mixtures, similarly to importance sampling strategies used to learn from data with sample selection bias [61, 11, 10, 64].”
Stability and Hypothesis Transfer Learning (2013, background): “Previous work has addressed in detail the theory of DA and proposed algorithms that critically depend on optimal weighting parameters given by the theoretical analysis (Ben-David et al., 2010a;b; Mansour et al., 2009b; Cortes et al., 2008).”
Domain Generalization by Marginal Transfer Learning (2017, background): “For example, several works adopt the covariate shift assumption, which requires the source and target domains to have the same posterior, allowing the marginals to differ arbitrarily (Zadrozny, 2004; Huang et al., 2007; Cortes et al., 2008; Sugiyama et al., 2008; Bickel et al., 2009; Kanamori et al.”
Learning Bounds for Importance Weighting (2010, methodology): “There is also a large body of literature dealing with differe nt t chniques for sample bias correction [11, 29, 16, 8, 25, 6] or domain adaptation [3, 7, 19, 10, 17] in the recent machine learning and natural language processing literature.”
Domain Adaptation with Coupled Subspaces (2011, background): “Either the source and target distributions share support [18, 20, 10], or they have low divergence for a specific hypothesis class [6, 28].”
An introduction to domain adaptation and transfer learning (2018, background): “But this tends to have a negative effect on the variance of the importance weights [46,44,45].”
Maximum Mean Discrepancy for Class Ratio Estimation: Convergence Bounds and Kernel Selection (2014, methodology): “The analysis of MMD for the covariance shift problem is very different (Yu & Szepesvari, 2012; Gretton et al., 2009; Cortes et al., 2008) from ours because their objectives and assumptions are different.”
Robust Learning under Uncertain Test Distributions: Relating Covariate Shift to Model Misspecification (2014, result): “Figure 3(c) compares the test losses of RCSA with the regular unweighed learning algorithm, the clusteringbased reweighing algorithm (Cortes et al., 2008), KLIEP (Sugiyama et al.”
Configurable 3D Scene Synthesis and 2D Image Rendering with Per-pixel Ground Truth Using Stochastic Grammars (2017, methodology): “…domain adaptation techniques can be divided into four categories: (i) covariate shift with shared support (Heck-man 1977; Gretton et al. 2009; Cortes et al. 2008; Bickel et al. 2009),(ii)learningsharedrepresentations(Blitzeretal.2006; Ben-David et al. 2007; Mansour et al. 2009), (iii)…”
Domain adaptation and sample bias correction theory and algorithm for regression (2014, methodology): “A common choice consists of selecting the weight of a point x of the training sample as an estimate of the ratio ω(x) = P (x)/Q(x) where P is the target (unbiased) distribution and Q the observed source distribution, since this choice preserves the expected loss [32, 10].”
GMC: Graph-Based Multi-View Clustering (2020, background): “First, sample selection bias [13] leads to view diversity.”
Adaptation Based on Generalized Discrepancy (2019, methodology): “In particular, we compare our bounds with those of Cortes et al. (2008) for the KMM algorithm.”