A review of single-source unsupervised domain adaptation <s> Algorithmic robustness <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> BIB001 </s> A review of single-source unsupervised domain adaptation <s> Algorithmic robustness <s> We consider regularized support vector machines (SVMs) and show that they are precisely equivalent to a new robust optimization formulation. We show that this equivalence of robust optimization and regularization has implications for both algorithms, and analysis. In terms of algorithms, the equivalence suggests more general SVM-like algorithms for classification that explicitly build in protection to noise, and at the same time control overfitting. On the analysis front, the equivalence of robustness and regularization, provides a robust optimization interpretation for the success of regularized SVMs. We use the this new robustness interpretation of SVMs to give a new proof of consistency of (kernelized) SVMs, thus establishing robustness as the reason regularized SVMs generalize well. <s> BIB002 </s> A review of single-source unsupervised domain adaptation <s> Algorithmic robustness <s> We derive generalization bounds for learning algorithms based on their robustness: the property that if a testing sample is"similar"to a training sample, then the testing error is close to the training error. This provides a novel approach, different from the complexity or stability arguments, to study generalization of learning algorithms. We further show that a weak notion of robustness is both sufficient and necessary for generalizability, which implies that robustness is a fundamental property for learning algorithms to work. <s> BIB003 </s> A review of single-source unsupervised domain adaptation <s> Algorithmic robustness <s> We derive a generalization bound for domain adaptation by using the properties of robust algorithms. Our new bound depends on ?-shift, a measure of prior knowledge regarding the similarity of source and target domain distributions. Based on the generalization bound, we design SVM variants for binary classification and regression domain adaptation algorithms. <s> BIB004 </s> A review of single-source unsupervised domain adaptation <s> Algorithmic robustness <s> Domain adaptation (DA) is a new learning framework dealing with learning problems where the target test data are drawn from a distribution different from the one that has generated the learning source data. In this article, we introduce self-labeling domain adaptation boosting (SLDAB), a new DA algorithm that falls both within the theory of DA and the theory of Boosting, allowing us to derive strong theoretical properties. SLDAB stands in the unsupervised DA setting where labeled data are only available in the source domain. To deal with this more complex situation, the strategy of SLDAB consists in jointly minimizing the empirical error on the source domain while limiting the violations of a natural notion of pseudo-margin over the target domain instances. Another contribution of this paper is the definition of a new divergence measure aiming at penalizing models that induce a large discrepancy between the two domains, reducing the production of degenerate models. We provide several theoretical results that justify this strategy. The practical efficiency of our model is assessed on two widely used datasets. <s> BIB005 </s> A review of single-source unsupervised domain adaptation <s> Algorithmic robustness <s> Unsupervised Domain Adaptation (DA) is used to automatize the task of labeling data: an unlabeled dataset (target) is annotated using a labeled dataset (source) from a related domain. We cast domain adaptation as the problem of finding stable labels for target examples. A new definition of label stability is proposed, motivated by a generalization error bound for large margin linear classifiers: a target labeling is stable when, with high probability, a classifier trained on a random subsample of the target with that labeling yields the same labeling. We find stable labelings using a random walk on a directed graph with transition probabilities based on labeling stability. The majority vote of those labelings visited by the walk yields a stable label for each target example. The resulting domain adaptation algorithm is strikingly easy to implement and apply: It does not rely on data transformations, which are in general computational prohibitive in the presence of many input features, and does not need to access the source data, which is advantageous when data sharing is restricted. By acting on the original feature space, our method is able to take full advantage of deep features from external pre-trained neural networks, as demonstrated by the results of our experiments. <s> BIB006
Some methods are inherently more resistant to certain changes in distributions: maximum-margin based classifiers ignore samples away from the margin, and consequently, any shifts therein BIB001 . This is an example of algorithmic robustness: an algorithm is deemed robust if it can partition a labeled feature space into disjoint sets (or regions) such that the variation of the classifier's loss is bounded BIB002 , BIB003 . This implies that when a training sample is removed from or added to a region, the change in loss is small. Robustness naturally extends to the case of data set shift: when going from the source domain to the target domain, source samples are removed from regions and target samples are added. How many source samples of each class are likely to disappear and how many target samples of each class are likely to appear, depends on the posterior probabilities of each domain. A classifier that is robust to such changes, can be trained on the source domain and would generalize well to the target domain. In fact, a generalization error bound can be derived using the notion of algorithmic robustness BIB004 . Changes over posterior probabilities in regions of feature space can be described by λ-shift. It is said that the target posterior is λ-shifted from the source if the following holds for all x ∈ X r ⊂ X and for all k ∈ {1, . . . , K}: where X r ∈ X refers to the r-th region of the sample space X . Note that for λ = 0, the posteriors are exactly equal, and for λ = 1, the posteriors can be arbitrarily different. In essence, this measure is a generalization of the assumption of equal posterior distributions that was used in importance-weighting methods for covariate shift. λ-shift is a less strict assumption and, hence, algorithms based on λshift are more widely applicable than importance-weighting methods. Using the notion of λ-shift and a robust algorithm, the following holds with probability 1 − δ, for δ > 0 (Theorem 2, BIB004 ): where ξ is the upper bound on the loss function, |X r | refers to the number of regions andp T (X r ) consists of the empirical probability of a target sample falling in region X r . Xr ℓ λ (h(x), y) dx dy corresponds to the maximal loss the classifier h incurs with respect to the source samples in the region X r , taking into account the λ-shift in posterior probability in that region. The terms on the right-hand side are based on the difference between the empirical source error and the true source error of a robust algorithm, as a function of the number of regions and the maximal difference in loss between two samples in a region. Algorithmic robustness pairs well with support vector machines (SVM), because their loss is constrained within the margin and they assign no loss to correctly classified samples outside the margin BIB002 , BIB003 . Incorporating λshift produces λ-shift SVM Adaptation (λ-SVMA) BIB004 . We will only discuss its most pessimistic variant here, which corresponds to putting no restrictions on the difference between posterior distributions (i.e. λ is set to 1). Pessimistic λ-SVMA's dual optimization problem formulation is identical to a standard SVM, except for the addition of an additional constraint: the sum of weights belonging to source samples x i falling in region X r has to be less than or equal to the trade-off parameter γ times the empirical target probability of region X r ; xi∈Xr a i ≤ γp T (X r ). This could be interpreted as that the weights are not allowed to concentrate on regions of feature space where there are few target samples. This approach has been extended to ridge and lasso regression BIB004 , and to the case of boosting BIB005 . It also resembles another robust SVM approach that aims to find support vectors for the target domain that produce stable labelings BIB006 . .