A review of single-source unsupervised domain adaptation <s> Assumptions, tests & no-free-lunch <s> Abstract Under general conditions given here, the least squares estimator for the parameters of a misspecified nonlinear model converge strongly to the parameters of a (weighted) least squares approximation to the true model. With additional conditions, the least squares estimator is asymptotically normal. A new, specification-robust estimator of the covariance matrix is obtained, which simplifies to the usual estimator when the model is correct up to an independent additive error. The properties of the approximation and the covariance estimator are exploited to yield new tests for model misspecification. These results are applied to two examples in economics. <s> BIB001 </s> A review of single-source unsupervised domain adaptation <s> Assumptions, tests & no-free-lunch <s> A simple regression test of the null hypothesis of no sample selection bias has been suggested by J. J. Heckman. Because of its computational simplicity, this test is widely used by applied researchers. This paper shows that Heckman's test is equivalent to the Lagrange multiplier test of the null hypothesis. This allows us to readily deduce that the simple regression test also has desirable large sample properties. <s> BIB002 </s> A review of single-source unsupervised domain adaptation <s> Assumptions, tests & no-free-lunch <s> This is the first of two papers that use off-training set (OTS) error to investigate the assumption-free relationship between learning algorithms. This first paper discusses the senses in which there are no a priori distinctions between learning algorithms. (The second paper discusses the senses in which there are such distinctions.) In this first paper it is shown, loosely speaking, that for any two algorithms A and B, there are “as many” targets (or priors over targets) for which A has lower expected OTS error than B as vice versa, for loss functions like zero-one loss. In particular, this is true if A is cross-validation and B is “anti-cross-validation” (choose the learning algorithm with largest cross-validation error). This paper ends with a discussion of the implications of these results for computational learning theory. It is shown that one cannot say: if empirical misclassification rate is low, the Vapnik-Chervonenkis dimension of your generalizer is small, and the training set is large, then with high probability your OTS error is small. Other implications for “membership queries” algorithms and “punting” algorithms are also discussed. <s> BIB003 </s> A review of single-source unsupervised domain adaptation <s> Assumptions, tests & no-free-lunch <s> Many learning situations involve learning the conditional distribution p(y|x) when the training instances are drawn from the training distribution ptr(x), even though it will later be used to predict for instances drawn from a different test distribution pte(x). Most current approaches focus on learning how to reweigh the training examples, to make them resemble the test distribution. However, reweighing does not always help, because (we show that) the test error also depends on the correctness of the underlying model class. This paper analyses this situation by viewing the problem of learning under changing distributions as a game between a learner and an adversary. We characterize when such reweighing is needed, and also provide an algorithm, robust covariate shift adjustment (RCSA), that provides relevant weights. Our empirical studies, on UCI datasets and a real-world cancer prognostic prediction dataset, show that our analysis applies, and that our RCSA works effectively. <s> BIB004 </s> A review of single-source unsupervised domain adaptation <s> Assumptions, tests & no-free-lunch <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> BIB005
The problem with assumptions on the relationship between domains (e.g. equal posteriors) is that they are impossible to verify without target labels. In order to estimate whether the posterior distributions in each domain are actually equal, one would need labeled data from each domain. For the same reason, it is not possible to verify that the error of the ideal joint hypothesis is small. The inability to check for the validity of these assumptions means that it is impossible to predict whether a method will work well on a given data set. For any adaptive classifier, it is possible to find a case where learning fails dramatically. Clearly, also in domain adaptation we, of course, have no free lunch BIB003 . Advising practitioners on classifier selection is therefore difficult. Ideally, there would be some hypothesis test that gives an impression of how likely an assumption is to be valid for a given problem setting. Such a test does exist for regression under sample selection bias BIB002 and for the necessity of importance-weighting BIB001 , BIB004 . We will discuss the latter briefly: a set of classifier parameters θ * is said to be a pointwise dominator of all other sets of parameters if it produces a lower or equal target risk for all x individually BIB004 . A dominant strategy is when a set of parameters produces a smaller or equal risk against all re-weightings of the data with an expected weight of 1 (see Equation 6 ). It can be shown that if θ * exists, it is also a dominant strategy (Theorem 3, BIB004 ). Furthermore, if there exists a dominant strategy, then the unweighted solution is also a dominant strategy (Theorem 4, BIB004 ). Hence, the unweighted solution for a correctly specified model should produce a small loss against all reweightings of the data with expected weight 1. Thus, testing for the necessity of importance-weighting can be done by comparing the adversarial losses of the set of classifier parameters obtained by training with importanceweights versus without importance-weights, where the adversarial loss consists of maximizing the loss of a given set of classifier parameters with respect to the weights. The larger the difference, the more the model is mis-specified and the larger the necessity for importance-weighting. The above test indicates wether it is a good idea to use an importance-weighted classifier for the problem under consideration. Another test is that, in some cases, an empirical discrepancy can indicate whether a method has the capacity to generalize well in the given problem BIB005 . Such results are important to making domain-adaptive classifiers practical.