A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> Abstract This paper presents a general technique for the treatment of samples drawn without replacement from finite universes when unequal selection probabilities are used. Two sampling schemes are discussed in connection with the problem of determining optimum selection probabilities according to the information available in a supplementary variable. Admittedly, these two schemes have limited application. They should prove useful, however, for the first stage of sampling with multi-stage designs, since both permit unbiased estimation of the sampling variance without resorting to additional assumptions. * Journal Paper No. J2139 of the Iowa Agricultural Experiment Station, Ames, Iowa, Project 1005. Presented to the Institute of Mathematical Statistics, March 17, 1951. <s> BIB001 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> In this paper, I present a simple characterization of the sample selection bias problem that is also applicable to the conceptually distinct econometric problems that arise from truncated samples and from models with limited dependent variables. The problem of sample selection bias is fit within the conventional specification error framework of Griliches and Theil. A simple estimator is discussed that enables analysts to utilize ordinary regression methods to estimate models free of selection bias. The techniques discussed here are applied to re-estimate and test a model of female labor supply developed by the author. (1974). This paper is in three parts. In the first section, selection bias is presented within the specification error framework. In this section, general distributional assumptions are maintained. In section two, specific results are presented for the case of normal regression disturbances. Simple estimators are proposed and discussed. In the third section, empirical results are presented. <s> BIB002 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> This article addresses the issue of specification of econometric selectivity models and suggests approaches for the correction of selectivity bias. Our approaches provide ways to specify selectivity models without the assumption of multinormal distribution. Some flexible function forms for the correction of selectivity bias in the regression equation are derived. All the models considered can be estimated by simple consistent two stage methods. Our approaches provide simple procedures for the testing of selectivity bias without imposing restrictive distributional assumptions and also tests for the normality assumption. <s> BIB003 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> This paper revisits the problem of optimal learning and decision-making when different misclassification errors incur different penalties. We characterize precisely but intuitively when a cost matrix is reasonable, and we show how to avoid the mistake of defining a cost matrix that is economically incoherent. For the two-class case, we prove a theorem that shows how to change the proportion of negative examples in a training set in order to make optimal cost-sensitive classification decisions using a classifier learned by a standard non-costsensitive learning method. However, we then argue that changing the balance of negative and positive training examples has little effect on the classifiers produced by standard Bayesian and decision tree learning methods. Accordingly, the recommended way of applying one of these methods in a domain with differing misclassification costs is to learn a classifier from the training set as given, and then to compute optimal decisions explicitly using the probability estimates given by the classifier. 1 Making decisions based on a cost matrix Given a specification of costs for correct and incorrect predictions, an example should be predicted to have the class that leads to the lowest expected cost, where the expectation is computed using the conditional probability of each class given the example. Mathematically, let the entry in a cost matrix be the cost of predicting class when the true class is . If then the prediction is correct, while if the prediction is incorrect. The optimal prediction for an example is the class that minimizes ! (1) Costs are not necessarily monetary. A cost can also be a waste of time, or the severity of an illness, for example. For each , is a sum over the alternative possibilities for the true class of . In this framework, the role of a learning algorithm is to produce a classifier that for any example can estimate the probability " # of each class being the true class of . For an example , making the prediction means acting as if is the true class of . The essence of cost-sensitive decision-making is that it can be optimal to act as if one class is true even when some other class is more probable. For example, it can be rational not to approve a large credit card transaction even if the transaction is most likely legitimate. 1.1 Cost matrix properties A cost matrix always has the following structure when there are only two classes: actual negative actual positive predict negative $% $& ' )(!*+* $% -,. /(!*10 predict positive 2,& $& ' )(302* 2,& -,. /(30+0 Recent papers have followed the convention that cost matrix rows correspond to alternative predicted classes, while columns correspond to actual classes, i.e. row/column = / = predicted/actual. In our notation, the cost of a false positive is (302* while the cost of a false negative is (!*!0 . Conceptually, the cost of labeling an example incorrectly should always be greater than the cost of labeling it correctly. Mathematically, it should always be the case that ( 0 *54 ( *+* and ( *!064 ( 0 0 . We call these conditions the “reasonableness” conditions. Suppose that the first reasonableness condition is violated, so (!*+*879(302* but still (!*!0 4 (30+0 . In this case the optimal policy is to label all examples positive. Similarly, if (:0 * 4 (!*+* but (30 0;7 in a cost matrix if for all , = ?7 > @ A . In this case the cost of predicting > is no greater than the cost of predicting = , regardless of what the true class is. So it is optimal never to predict = . As a special case, the optimal prediction is always > if row > is dominated by all other rows in a cost matrix. The two reasonableness conditions for a two-class cost matrix imply that neither row in the matrix dominates the other. Given a cost matrix, the decisions that are optimal are unchanged if each entry in the matrix is multiplied by a positive constant. This scaling corresponds to changing the unit of account for costs. Similarly, the decisions that are optimal are unchanged B if a constant is added to each entry in the matrix. This shifting corresponds to changing the baseline away from which costs are measured. By scaling and shifting entries, any two-class cost matrix that satisfies the reasonableness conditions can be transformed into a simpler matrix that always leads to the same decisions: <s> BIB004 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> Resampling methods are commonly used for dealing with the class-imbalance problem. Their advantage over other methods is that they are external and thus, easily transportable. Although such approaches can be very simple to implement, tuning them most effectively is not an easy task. In particular, it is unclear whether oversampling is more effective than undersampling and which oversampling or undersampling rate should be used. This paper presents an experimental study of these questions and concludes that combining different expressions of the resampling approach is an effective solution to the tuning problem. The proposed combination scheme is evaluated on imbalanced subsets of the Reuters-21578 text collection and is shown to be quite effective for these problems. <s> BIB005 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> Classifier learning methods commonly assume that the training data consist of randomly drawn examples from the same distribution as the test examples about which the learned model is expected to make predictions. In many practical situations, however, this assumption is violated, in a problem known in econometrics as sample selection bias. In this paper, we formalize the sample selection bias problem in machine learning terms and study analytically and experimentally how a number of well-known classifier learning methods are affected by it. We also present a bias correction method that is particularly useful for classifier evaluation under sample selection bias. <s> BIB006 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> On-line learning in domains where the target concept depends on some hidden context poses serious problems. A changing context can induce changes in the target concepts, producing what is known as concept drift. We describe a family of learning algorithms that flexibly react to concept drift and can take advantage of situations where contexts reappear. The general approach underlying all these algorithms consists of (1) keeping only a window of currently trusted examples and hypotheses; (2) storing concept descriptions and re-using them when a previous context re-appears; and (3) controlling both of these functions by a heuristic that constantly monitors the system's behavior. The paper reports on experiments that test the systems' performance under various conditions such as different levels of noise and different extent and rate of concept drift. <s> BIB007 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> An approach to the construction of classifiers from imbalanced datasets is described. A dataset is imbalanced if the classification categories are not approximately equally represented. Often real-world data sets are predominately composed of"normal"examples with only a small percentage of"abnormal"or"interesting"examples. It is also the case that the cost of misclassifying an abnormal (interesting) example as a normal example is often much higher than the cost of the reverse error. Under-sampling of the majority (normal) class has been proposed as a good means of increasing the sensitivity of a classifier to the minority class. This paper shows that a combination of our method of over-sampling the minority (abnormal) class and under-sampling the majority (normal) class can achieve better classifier performance (in ROC space) than only under-sampling the majority class. This paper also shows that a combination of our method of over-sampling the minority class and under-sampling the majority class can achieve better classifier performance (in ROC space) than varying the loss ratios in Ripper or class priors in Naive Bayes. Our method of over-sampling the minority class involves creating synthetic minority class examples. Experiments are performed using C4.5, Ripper and a Naive Bayes classifier. The method is evaluated using the area under the Receiver Operating Characteristic curve (AUC) and the ROC convex hull strategy. <s> BIB008 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> The field of dataset shift has received a growing amount of interest in the last few years. The fact that most real-world applications have to cope with some form of shift makes its study highly relevant. The literature on the topic is mostly scattered, and different authors use different names to refer to the same concepts, or use the same name for different concepts. With this work, we attempt to present a unifying framework through the review and comparison of some of the most important works in the literature. <s> BIB009 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> Let X denote the feature and Y the target. We consider domain adaptation under three possible scenarios: (1) the marginal PY changes, while the conditional PX/Y stays the same (target shift), (2) the marginal PY is fixed, while the conditional PX/Y changes with certain constraints (conditional shift), and (3) the marginal PY changes, and the conditional PX/Y changes with constraints (generalized target shift). Using background knowledge, causal interpretations allow us to determine the correct situation for a problem at hand. We exploit importance reweighting or sample transformation to find the learning machine that works well on test data, and propose to estimate the weights or transformations by reweighting or transforming training data to reproduce the covariate distribution on the test domain. Thanks to kernel embedding of conditional as well as marginal distributions, the proposed approaches avoid distribution estimation, and are applicable for high-dimensional problems. Numerical evaluations on synthetic and real-world data sets demonstrate the effectiveness of the proposed framework. <s> BIB010 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> We present a series of new theoretical, algorithmic, and empirical results for domain adaptation and sample bias correction in regression. We prove that the discrepancy is a distance for the squared loss when the hypothesis set is the reproducing kernel Hilbert space induced by a universal kernel such as the Gaussian kernel. We give new pointwise loss guarantees based on the discrepancy of the empirical source and target distributions for the general class of kernel-based regularization algorithms. These bounds have a simpler form than previous results and hold for a broader class of convex loss functions not necessarily differentiable, including L"q losses and the hinge loss. We also give finer bounds based on the discrepancy and a weighted feature discrepancy parameter. We extend the discrepancy minimization adaptation algorithm to the more significant case where kernels are used and show that the problem can be cast as an SDP similar to the one in the feature space. We also show that techniques from smooth optimization can be used to derive an efficient algorithm for solving such SDPs even for very high-dimensional feature spaces and large samples. We have implemented this algorithm and report the results of experiments both with artificial and real-world data sets demonstrating its benefits both for general scenario of adaptation and the more specific scenario of sample bias correction. Our results show that it can scale to large data sets of tens of thousands or more points and demonstrate its performance improvement benefits. <s> BIB011 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> When estimating population descriptive statistics, weighting is called for if needed to make the analysis sample representative of the target population. With regard to research directed instead at estimating causal effects, we discuss three distinct weighting motives: (1) to achieve precise estimates by correcting for heteroskedasticity; (2) to achieve consistent estimates by correcting for endogenous sampling; and (3) to identify average partial effects in the presence of unmodeled heterogeneity of effects. In each case, we find that the motive sometimes does not apply in situations where practitioners often assume it does. <s> BIB012 </s> A review of single-source unsupervised domain adaptation <s> SAMPLE-BASED APPROACHES <s> In various applications, such as law enforcement and medical screening, one class outnumbers the other, which is called class imbalance. The inspection to recognize targets from the minority class is usually driven by experience and expert knowledge. In that way, targets can be found way above the base rate to make the inspection process feasible. In order to make the search for targets more efficient, the inspected samples can serve as training set for a learning method. In this study, we show how the introduced selection bias can be remedied in several ways using unlabeled data. With a synthetic dataset and a real-world law enforcement dataset, we show that adding unlabeled data to the non-targets strongly improves ranking performance. Importantly, completely leaving out the labeled non-targets and using only the unlabeled data as non-targets gives the best results. <s> BIB013
We are ultimately interested in minimizing the target risk, but want to do this by making use of the source domain. One way to relate the source distribution to the target risk R T , at least superficially, is to consider: In order to deal with Equation 3, we need to determine the ratio p T (x, y)/p S (x, y). Estimating that ratio would require labeled data from both domains. As discussed, however, in the domain adaptation techniques we cover here, no labeled target data is available. Another approach is to make certain simplifying assumptions, such that estimation actually becomes possible without labeled target data. Joint distributions can be decomposed in two ways: p(x | y)p(y) and p(y | x)p(x). In the former case, if p(x | y) remains constant but p(y) changes, then prior shift is said to occur BIB009 . This situation is related to cost-sensitive learning BIB004 ,  and the problem of imbalanced classes BIB005 , BIB013 . Corrections usually consist of over-or under-sampling classes BIB008 ,  . In the latter case, if p(y | x) changes but p(x) remains constant, then the problem is known as concept shift BIB009 , BIB010 . This can occur in the context of online learning, where the posteriors might change slowly over time BIB007 . Prior and concept shift are outside of the scope of this review, as they require observations of target labels to perform adaptation If p(y | x) remains the same, but p(x) changes then it is a covariate shift problem. The knowledge that the posteriors remain equivalent can be exploited by factorizing the decomposing the joint distributions and canceling the posteriors in the ratio. With this cancellation, a risk function R W is formed that contains a weighting by the ratio of data marginals: Note that no observations of target labels are necessary here. Weights can be estimated purely on unlabeled data in both domains. Of course, in practice, the underlying probability distributions are unknown. Therefore, an important question to ask is: when are the posterior distributions equal? The covariate shift assumption is known to hold in cases of sample selection bias, a well-studied problem in statistics BIB002 , BIB003 , BIB001 . In the sample selection bias setting, one differentiates between the true underlying data-generating distribution and a sampling distribution. This sampling distribution defines the probability of each instance to be observed or, in other words, to be selected for the training set  , BIB006 . If the sampling distribution is not uniform, then the resulting sample will be biased with respect to the underlying distribution. The challenge is to correct for the non-uniform selection probabilities and generalize to an unbiased sample BIB012 . Since the underlying data-generating distribution remains constant, the underlying posteriors are known to be equivalent between the biased and unbiased samples BIB011 . Note that there is a subtle difference between sample selection bias and domain adaptation: the goal in the former is to generalize to the whole population and the goal in the latter is to generalize to a specific other biased sample.