Sample Selection Bias,Lei Tang Feb. 20th, 2007,Classical ML vs. Reality,Training data and Test data share the same distribution (In classical Machine Learning) But thats not always the case in reality. Survey data Species habitat modeling based on data of only one area Training and test data collected by different experiments Newswire articles with timestamps,Sample selection bias,Standard setting: data (x,y) are drawn independently from a distribution D If the selected samples is not a random samples of D, then the samples are biased. Usually, training data are biased, but we want to apply the classifier to unbiased samples.,Four cases of Bias(1),Let s denote whether or not a sample is selected. P(s=1|x,y) = P(s=1) (not biased) P(s=1|x,y) = P(s=1|x) (depending only on the feature vector) P(s=1|x,y) = P(s=1|y) (depending only on the class label) P(s=1|x,y) (depending on both x and y),Four cases of Bias(2),P(s=1|x, y)= P(s=1|y): learning from imbalanced data. Can alleviate the bias by changing the class prior. P(s=1|x,y) = P(s=1|x) imply P(y|x) remain unchanged. This is mostly studied. If the bias depends on both x and y, lack information to analyze.,An intuitive Example,P(s=1|x,y) = P(s=1|x) = s and y are independent. So P(y|x, s=1) = P(y|x). Does it really matter as P(y|x) remain unchanged?,Bias Analysis for Classifiers(1),Logistic Regression Any classifiers directly models P(y|x) wont be affected by bias Bayesian Classifier But for nave Bayesian classifier,Bias Analysis for Classifiers(2),Hard margin SVM: no bias effect. Soft margin SVM: has bias effect as the cost of misclassification might change. Decision Tree usually results in a different classifier if the bias is presented In sum, most classifiers are still sensitive to the sample bias. This is in asymptotic analysis assuming the samples are “enough”,Correcting Bias,Expected Risk: Suppose training set from Pr, test set from Pr So we minimize the empirical regularized risk:,Estimate the weights,The samples which are likely to appear in the test data will gain more weight. But how to estimate the weight of each sample? Brute force approach: Estimate the density of Pr(x) and Pr(x), respectively, Then calculate the sample weight. Not applicable as density estimation is more difficult than classification given limited number of samples. Existing works use simulation experiments in which both Pr(x) and Pr(x) are known (NOT REALISTIC),Distribution Matching,The expectation in feature space: We have Hence, the problem can be formulated as Solution is:,Empirical KMM optimization,where,Therefore, its equivalent to solve the QP problem:,Experiments,A Toy Regression Example,Simulation,Select some UCI datasets to inject some sample selection bias into training, then test on unbiased samples.,Bias on Labels,Unexplained,From theory, the importance sampling should be the best, why KMM performs better? Why kernel methods? Can we just do the matching using input features? Can we just perform a logistic regression to estimate beta by treating test data as positive class, and training data as negative. Then, beta is the odds.,Some Related Problems,Semi-supervised Learning (Is it equivalent?) Multi-task Learning: assume P(y|x) to be different. But sample selection bias(mostly) assume P(y|x) to be the same. MTL requires training data for each task. Is it possible to discriminate features which introduce the bias? Or find invariant dimensionalities?,Any Questions?,Happy Pig Year!,