A review of single-source unsupervised domain adaptation <s> Importance Weighting <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> Importance Weighting <s> From the Publisher: ::: How does it differ from first edition? Includes new material on: * support vector machines (SVM's), * fat shattering dimensions * applications to neural network learning, * learning with dependent samples generated by beta-mixing process, * connections between system identification and learning theory * probabilistic solution of "intractable" problems in robust control and matrix theory using randomised algorithms. In addition, solutions to some open problems posed in the first edition are included, and new open problems are added. The author is a respected authority in the field of control and systems theory. This new edition, with substantial new material, takes account of important new developments in the theory of learning. It also deals extensively with the theory of learning control systems, which has now reached a level of maturity comparable to that of learning of neural networks. The book is written in a manner that would suit self-study and contains comprehensive references. The chapters are also written to be as autonomous as possible and contain updated open problems to enhance further research and self-study. <s> BIB002 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> Abstract A class of predictive densities is derived by weighting the observed samples in maximizing the log-likelihood function. This approach is effective in cases such as sample surveys or design of experiments, where the observed covariate follows a different distribution than that in the whole population. Under misspecification of the parametric model, the optimal choice of the weight function is asymptotically shown to be the ratio of the density function of the covariate in the population to that in the observations. This is the pseudo-maximum likelihood estimation of sample surveys. The optimality is defined by the expected Kullback–Leibler loss, and the optimal weight is obtained by considering the importance sampling identity. Under correct specification of the model, however, the ordinary maximum likelihood estimate (i.e. the uniform weight) is shown to be optimal asymptotically. For moderate sample size, the situation is in between the two extreme cases, and the weight function is selected by minimizing a variant of the information criterion derived as an estimate of the expected loss. The method is also applied to a weighted version of the Bayesian predictive density. Numerical examples as well as Monte-Carlo simulations are shown for polynomial regression. A connection with the robust parametric estimation is discussed. <s> BIB003 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> A common assumption in supervised learning is that the training and test input points follow the same probability distribution. However, this assumption is not fulfilled, e.g., in interpolation, extrapolation, or active learning scenarios. The violation of this assumption-- known as the covariate shift--causes a heavy bias in standard generalization error estimation schemes such as cross-validation and thus they result in poor model selection. In this paper, we therefore propose an alternative estimator of the generalization error. Under covariate shift, the proposed generalization error estimator is unbiased if the learning target function is included in the model at hand and it is asymptotically unbiased in general. Experimental results show that model selection with the proposed generalization error estimator is compared favorably to crossvalidation in extrapolation. <s> BIB004 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> MOTIVATION ::: Many problems in data integration in bioinformatics can be posed as one common question: Are two sets of observations generated by the same distribution? We propose a kernel-based statistical test for this problem, based on the fact that two distributions are different if and only if there exists at least one function having different expectation on the two distributions. Consequently we use the maximum discrepancy between function means as the basis of a test statistic. The Maximum Mean Discrepancy (MMD) can take advantage of the kernel trick, which allows us to apply it not only to vectors, but strings, sequences, graphs, and other common structured data types arising in molecular biology. ::: ::: ::: RESULTS ::: We study the practical feasibility of an MMD-based test on three central data integration tasks: Testing cross-platform comparability of microarray data, cancer diagnosis, and data-content based schema matching for two different protein function classification schemas. In all of these experiments, including high-dimensional ones, MMD is very accurate in finding samples that were generated from the same distribution, and outperforms its best competitors. ::: ::: ::: CONCLUSIONS ::: We have defined a novel statistical test of whether two samples are from the same distribution, compatible with both multivariate and structured data, that is fast, easy to implement, and works well, as confirmed by our experiments. ::: ::: ::: AVAILABILITY ::: http://www.dbs.ifi.lmu.de/~borgward/MMD. <s> BIB005 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> We consider the scenario where training and test data are drawn from different distributions, commonly referred to as sample selection bias. Most algorithms for this setting try to first recover sampling distributions and then make appropriate corrections based on the distribution estimate. We present a nonparametric method which directly produces resampling weights without distribution estimation. Our method works by matching distributions between training and testing sets in feature space. Experimental results demonstrate that our method works well in practice. <s> BIB006 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> A common assumption in supervised learning is that the input points in the training set follow the same probability distribution as the input points that will be given in the future test phase. However, this assumption is not satisfied, for example, when the outside of the training region is extrapolated. The situation where the training input points and test input points follow different distributions while the conditional distribution of output values given input points is unchanged is called the covariate shift. Under the covariate shift, standard model selection techniques such as cross validation do not work as desired since its unbiasedness is no longer maintained. In this paper, we propose a new method called importance weighted cross validation (IWCV), for which we prove its unbiasedness even under the covariate shift. The IWCV procedure is the only one that can be applied for unbiased classification under covariate shift, whereas alternatives to IWCV exist for regression. The usefulness of our proposed method is illustrated by simulations, and furthermore demonstrated in the brain-computer interface, where strong non-stationarity effects can be seen between training and test sessions. <s> BIB007 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> We address classification problems for which the training instances are governed by a distribution that is allowed to differ arbitrarily from the test distribution---problems also referred to as classification under covariate shift. We derive a solution that is purely discriminative: neither training nor test distribution are modeled explicitly. We formulate the general problem of learning under covariate shift as an integrated optimization problem. We derive a kernel logistic regression classifier for differing training and test distributions. <s> BIB008 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> 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. <s> BIB009 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> A situation where training and test samples follow different input distributions is called covariate shift. Under covariate shift, standard learning methods such as maximum likelihood estimation are no longer consistent—weighted variants according to the ratio of test and training input densities are consistent. Therefore, accurately estimating the density ratio, called the importance, is one of the key issues in covariate shift adaptation. A naive approach to this task is to first estimate training and test input densities separately and then estimate the importance by taking the ratio of the estimated densities. However, this naive approach tends to perform poorly since density estimation is a hard task particularly in high dimensional cases. In this paper, we propose a direct importance estimation method that does not involve density estimation. Our method is equipped with a natural cross validation procedure and hence tuning parameters such as the kernel width can be objectively optimized. Simulations illustrate the usefulness of our approach. <s> BIB010 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> An independent vehicle wheel suspension arrangement which includes a pair of control arms disposed in a superimposed relationship. The control arms are articulated to a wheel carrier and are selectively in a mutually parallel or non-parallel position. A wheel suspension unit is supported on the wheel carrier with a steering knuckle of the wheel being also articulated to the wheel carrier along the steering axis of the steerable wheels. The control arms are articulated to the wheel carrier by means of ball and socket joints and the wheel carrier is supported against a twisting about a substantially perpendicular axis of rotation determined by the ball and socket joints, with respect to the vehicle body, by an additional moment supporting arm. The moment supporting arm is likewise connected to the wheel carrier and the vehicle body by ball and socket joints. <s> BIB011 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> We propose a framework for analyzing and comparing distributions, allowing us to design statistical tests to determine if two samples are drawn from different distributions. Our test statistic is the largest difference in expectations over functions in the unit ball of a reproducing kernel Hilbert space (RKHS). We present two tests based on large deviation bounds for the test statistic, while a third is based on the asymptotic distribution of this statistic. The test statistic can be computed in quadratic time, although efficient linear time approximations are available. Several classical metrics on distributions are recovered when the function space used to compute the difference in expectations is allowed to be more general (eg. a Banach space). We apply our two-sample tests to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where they perform strongly. Excellent performance is also obtained when comparing distributions over graphs, for which these are the first such tests. <s> BIB012 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> This chapter contains sections titled: Introduction, Sample Reweighting, Distribution Matching, Risk Estimates, The Connection to Single Class Support Vector Machines, Experiments, Conclusion, Appendix: Proofs <s> BIB013 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> We address the problem of estimating the ratio of two probability density functions, which is often referred to as the importance. The importance values can be used for various succeeding tasks such as covariate shift adaptation or outlier detection. In this paper, we propose a new importance estimation method that has a closed-form solution; the leave-one-out cross-validation score can also be computed analytically. Therefore, the proposed method is computationally highly efficient and simple to implement. We also elucidate theoretical properties of the proposed method such as the convergence rate and approximation error bounds. Numerical experiments show that the proposed method is comparable to the best existing method in accuracy, while it is computationally more efficient than competing approaches. <s> BIB014 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> A major assumption in many machine learning and data mining algorithms is that the training and future data must be in the same feature space and have the same distribution. However, in many real-world applications, this assumption may not hold. For example, we sometimes have a classification task in one domain of interest, but we only have sufficient training data in another domain of interest, where the latter data may be in a different feature space or follow a different data distribution. In such cases, knowledge transfer, if done successfully, would greatly improve the performance of learning by avoiding much expensive data-labeling efforts. In recent years, transfer learning has emerged as a new learning framework to address this problem. This survey focuses on categorizing and reviewing the current progress on transfer learning for classification, regression, and clustering problems. In this survey, we discuss the relationship between transfer learning and other related machine learning techniques such as domain adaptation, multitask learning and sample selection bias, as well as covariate shift. We also explore some potential future issues in transfer learning research. <s> BIB015 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> This paper presents an analysis of importance weighting for learning from finite samples and gives a series of theoretical and algorithmic results. We point out simple cases where importance weighting can fail, which suggests the need for an analysis of the properties of this technique. We then give both upper and lower bounds for generalization with bounded importance weights and, more significantly, give learning guarantees for the more common case of unbounded importance weights under the weak assumption that the second moment is bounded, a condition related to the Renyi divergence of the traning and test distributions. These results are based on a series of novel and general bounds we derive for unbounded loss functions, which are of independent interest. We use these bounds to guide the definition of an alternative reweighting algorithm and report the results of experiments demonstrating its benefits. Finally, we analyze the properties of normalized importance weights which are also commonly used. <s> BIB016 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> In real supervised learning scenarios, it is not uncommon that the training and test sample follow different probability distributions, thus rendering the necessity to correct the sampling bias. Focusing on a particular covariate shift problem, we derive high probability confidence bounds for the kernel mean matching (KMM) estimator, whose convergence rate turns out to depend on some regularity measure of the regression function and also on some capacity measure of the kernel. By comparing KMM with the natural plug-in estimator, we establish the superiority of the former hence provide concrete evidence/understanding to the effectiveness of KMM under covariate shift. <s> BIB017 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> Machine learning is an interdisciplinary field of science and engineering that studies mathematical theories and practical applications of systems that learn. This book introduces theories, methods, and applications of density ratio estimation, which is a newly emerging paradigm in the machine learning community. Various machine learning problems such as non-stationarity adaptation, outlier detection, dimensionality reduction, independent component analysis, clustering, classification, and conditional density estimation can be systematically solved via the estimation of probability density ratios. The authors offer a comprehensive introduction of various density ratio estimators including methods via density estimation, moment matching, probabilistic classification, density fitting, and density ratio fitting as well as describing how these can be applied to machine learning. The book also provides mathematical theories for density ratio estimation including parametric and non-parametric convergence analysis and numerical stability analysis to complete the first and definitive treatment of the entire framework of density ratio estimation in machine learning. <s> BIB018 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> Importance weighting is widely applicable in machine learning in general and in techniques dealing with data co-variate shift problems in particular. A novel, direct approach to determine such importance weighting is presented. It relies on a nearest neighbor classification scheme and is relatively straightforward to implement. Comparative experiments on various classification tasks demonstrate the effectiveness of our so-called nearest neighbor weighting (NNeW) scheme. Considering its performance, our procedure can act as a simple and effective baseline method for importance weighting. <s> BIB019 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <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> BIB020 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> In this paper, we tackle the problem of unsupervised domain adaptation for classification. In the unsupervised scenario where no labeled samples from the target domain are provided, a popular approach consists in transforming the data such that the source and target distributions become similar. To compare the two distributions, existing approaches make use of the Maximum Mean Discrepancy (MMD). However, this does not exploit the fact that probability distributions lie on a Riemannian manifold. Here, we propose to make better use of the structure of this manifold and rely on the distance on the manifold to compare the source and target distributions. In this framework, we introduce a sample selection method and a subspace-based method for unsupervised domain adaptation, and show that both these manifold-based techniques outperform the corresponding approaches based on the MMD. Furthermore, we show that our subspace-based approach yields state-of-the-art results on a standard object recognition benchmark. <s> BIB021 </s> A review of single-source unsupervised domain adaptation <s> Importance Weighting <s> Abstract In astronomical applications of machine learning, the distribution of objects used for building a model is often different from the distribution of the objects the model is later applied to. This is known as sample selection bias, which is a major challenge for statistical inference as one can no longer assume that the labeled training data are representative. To address this issue, one can re-weight the labeled training patterns to match the distribution of unlabeled data that are available already in the training phase. There are many examples in practice where this strategy yielded good results, but estimating the weights reliably from a finite sample is challenging. We consider an efficient nearest neighbor density ratio estimator that can exploit large samples to increase the accuracy of the weight estimates. To solve the problem of choosing the right neighborhood size, we propose to use cross-validation on a model selection criterion that is unbiased under covariate shift. The resulting algorithm is our method of choice for density ratio estimation when the feature space dimensionality is small and sample sizes are large. The approach is simple and, because of the model selection, robust. We empirically find that it is on a par with established kernel-based methods on relatively small regression benchmark datasets. However, when applied to large-scale photometric redshift estimation, our approach outperforms the state-of-the-art. <s> BIB022
The ratio of the data marginal distributions is often referred to as an importance weight, denoted as w(x) = p T (x)/p S (x). It signifies how important each source sample is under the target domain, relative to the source domain. The weights influence a classification model by increasing the loss for certain samples and decreasing the loss for others. Figure 3 shows a scatterplot of the example setting from Section 2.2. The importance of the source samples is shown through the size of their markers. Training on these importance weighted samples produces a different classifier, shown as the dashed black line. This classifier is said to have adapted to the data from the hospital in Long Beach. BIB015 is interesting, but does not tell us anything about the finite sample size case. The difference between the empirical importance-weighted source error and the true target error can be bounded. The bound shows how the difference depends on the complexity of the classifier, the sample size and the divergence between the domains. With probability 1 − δ for δ > 0, the difference between the true target error e T and the empirical weighted source errorê W for a classifier h is (Theorem 3, BIB016 ): where D 2R (p T p S ) is the Rényi divergence from Equation 2 BIB016 , and c is the so-called pseudo-dimension of the hypothesis space BIB002 . For a fixed choice of hypothesis space (e.g. linear classifiers), as the divergence between the domains increases, the sample size needs to increase at a certain rate, in order to maintain the same probability of being approximately correct. Furthermore, it turns out that an importance-weighted classifier will only converge if the expected squared weight is finite, . If the domains are too dissimilar, then this will not be the case and importance-weighting will not be a feasible approach. However, it should be said that, asymptotically, weighting is only effective for a mis-specified classification model, e.g. a linear classifier for a non-linear classification problem BIB001 , BIB003 , BIB020 . With a correctly specified model, as the sample size goes to infinity, the unweighted estimator will find the optimal classifier as well BIB001 . In fact, with a correctly specified model, the weighted estimator will converge to the optimal classifier for any fixed set of non-negative weights that sums to 1 BIB001 . But how to find appropriate importance weights? Indirect weight estimators first estimate the marginal data distribution of each domain separately and subsequently compute the ratio. Estimating each data distribution can be done parametrically, i.e. using a probability distribution with a fixed set of parameters, or non-parametrically, i.e. using a distribution with a variable set of parameters. With parametric weight estimators, one obtains a functional form of the resulting ratio of distributions. For example, one could assume Gaussian distributions for each domain BIB003 . Then the weight function consists of: Such weight functions can be analyzed and often show interesting properties. For example, members of the exponential family can drastically increase the variance of the importance weights BIB016 , BIB009 . High weight variance means that it is probable that a few samples will receive large weights. Consequently, at training time, the classifier will focus on those few samples designated as important, and ignore the others. The result is often a pathological classifier that will not generalize well. The non-parametric alternative is to use kernel density estimators  , BIB017 , BIB021 : where κ is a kernel function and σ denotes its bandwidth. The density of a source sample x i depends on the distance to each kernel's center. Bandwidths are considered hyperparameters and can be tuned to produce smoother densities. Kernel density estimators have the advantage that they can become multi-modal: when samples are clustered in two regions, the overlayed kernel functions naturally form a mode on the cluster centers. Instead of estimating the data distribution in each domain and taking their ratio, weights can be estimated directly BIB010 , BIB018 . This is most often done through an optimization procedure that minimizes the discrepancy between the weighted source and the target distribution, with respect to the importance weights BIB011 . Different methods use different discrepancy measures. Two constraints are added to the optimization procedure. Firstly, all importance weights should be non-negative. Secondly, the weighted source distribution should be a valid probability distribution: The above approximate equality can be enforced by constraining the absolute deviation of the weight average from 1 to be less than some small ǫ. With these two constraints, the optimization problem becomes: where D refers to the discrepancy measure. Weights obtained through optimization w i are values specific to the i-th source sample. An direct optimization procedure for weights is limited in that it does not produce a weight function w(·), which means interpolations between source samples are not possible. The most popular measure of domain dissimilarity is the Maximum Mean Discrepancy (MMD) BIB005 , BIB012 . It stems from a hypothesis test to determine if two sets of samples originate from the same distribution  . The original formulation is based on the distance between the expected values of two distributions under the continuous function that pulls them maximally apart BIB005 . But it can be approximated using universal kernels BIB012 . Minimizing the empirical MMD with respect to the importance weights, is called Kernel Mean Matching (KMM) BIB006 , BIB013 : Note that constant terms are not relevant to the optimization procedure. Depending on how the weights are further constrained, algorithmic computational complexities and convergence criteria can be derived as well BIB017 , BIB013 . Another popular direct importance-weight estimator is the Kullback-Leibler Importance Estimation Procedure (KLIEP) BIB004 , BIB007 . As its name suggests, it uses the Kullback-Leibler Divergence, a measure of distribution discrepancy that is well known in information theory  . The KLdivergence between the true target distribution and the importance-weighted source distribution is the following: Note that this formulation requires weighting target samples. New weights would have to be estimated for each new target sample. To avoid this, a functional model is proposed. It consists of the inner product of parameters α and basis functions φ, i.e. w(x) = φ(x)α  . The objective now simplifies to m −1 m j log φ(z j )α, where α is not dependent on an individual sample. So, KLIEP can be applied to new target samples without additional weight estimation. A third discrepancy is the L 2 -norm between the weights and the ratio of data distributions BIB014 ,  . The squared difference can be expanded and terms not involving the weights can be dropped. Using a functional model of the weights, w(x) = φ(x)α, and approximating expectations with sample averages, the empirical discrepancy becomes: where φ(x i ) ⊤ φ(x i ′ ) denotes the outer product of applying the basis functions to a single source sample BIB014 . This method is called the Least-Squares Importance Fitting procedure. Note that although this form resembles Kernel Mean Matching, it estimates α's, which can have a different dimensionality than the w i 's. KMM can be very impractical in large data sets, because one needs to solve a quadratic program with n variables, one for each w i . Suppose the dimensionality of φ is d, and d < n. Then, there are d α's, and d variables for the quadratic program. As such, this approach can be computationally cheaper than KMM. There are also a few direct weight estimators that do not employ optimization. Nearest-Neighbour Weighting is based on tessellating the feature space into Voronoi cells BIB019 . Each cell is a polygon of variable size marking an area of equal probability. The cells approximate a probability distribution function in the same way as a multi-dimensional histogram  . To obtain weights, one forms the Voronoi cell V i of each source sample x i with the part of feature space that lies closest to x i BIB019 . The ratio of target over source is then approximated by counting the number of target samples z j that lie within each Voronoi cell: where | · | denotes cardinality. Counting the number of target samples lying within a source sample's Voronoi cell is equivalent to counting the number of target samples that are nearest neighbours of that source sample BIB022 , BIB019 . This estimator does not require hyperparameter optimization, but Laplace smoothing, which adds a 1 to each cell, can additionally be performed BIB019 . Lastly, it is also possible to avoid the two-step procedure, and optimize the weights simultaneously with optimizing the classifier BIB008 ,  .