Domain Adaptation via Transfer Component Analysis

1 Introduction

Domain adaptation aims at adapting a classifier or regression model trained in a source domain for use in a target domain, where the source and target domains may be different but related. This is particularly crucial when labeled data are in short supply in the target domain. For example, in indoor WiFi localization, it is very expensive to calibrate a localization model in a large-scale environment. However, the WiFi signal strength may be a function of time, device or space, depending on dynamic factors. To reduce the re-calibration effort, we might want to adapt a localization model trained in one time period (the source domain) for a new time period (the target domain), or to adapt the localization model trained on one mobile device (the source domain) for a new mobile device (the target domain). However, the distributions of WiFi data collected over time or across devices may be very different, hence domain adaptation is needed [Yang et al., 2008]. Another example is sentiment classification. To reduce the effort of annotating reviews for various products, we might want to adapt a learning system trained on some types of products (the source domain) for a new type of product (the target domain). However, terms used in the reviews of different types of products may be very different. As a result, distributions of the data over different types of products may be different and thus domain adaptation is again needed [Blitzer et al., 2007].

A major computational problem in domain adaptation is how to reduce the difference between the distributions of source and target domain data. Intuitively, discovering a good feature representation across domains is crucial. A good feature representation should be able to reduce the difference in distributions between domains as much as possible, while at the same time preserving important (geometric or statistical) properties of the original data.

Recently, several approaches have been proposed to learn a common feature representation for domain adaptation [Daum´e III, 2007; Blitzer et al., 2006]. Daum´e III [2007] proposed a simple heuristic nonlinear mapping function to map the data from both source and target domains to a highdimensional feature space, where standard machine learning methods are used to train classifiers. Blitzer et al. [2006] proposed the so-called structural correspondence learning (SCL) algorithm to induce correspondences among features from the different domains. This method depends on the heuristic selections of pivot features that appear frequently in both domains. Although it is experimentally shown that SCL can reduce the difference between domains based on the A-distance measure [Ben-David et al., 2007], the heuristic criterion of pivot feature selection may be sensitive to different applications. Pan et al. [2008] proposed a new dimensionality reduction method, Maximum Mean Discrepancy Embedding (MMDE), for domain adaptation. The motivation of MMDE is similar to our proposed work. It also aims at learning a shared latent space underlying the domains where distance between distributions can be reduced. However, MMDE suffers from two major limitations: (1) MMDE is transductive, and does not generalize to out-of-sample patterns; (2) MMDE learns the latent space by solving a semi-definite program (SDP), which is a very expensive optimization problem.

In this paper, we propose a new feature extraction approach, called transfer component analysis (TCA), for domain adaptation. It tries to learn a set of common transfer components underlying both domains such that the difference in distributions of data in the different domains, when projected onto this subspace, can be dramatically reduced. Then, standard machine learning methods can be used in this subspace to train classifiers or regression models across domains. More specifically, if two domains are related to each other, there may exist several common components (or latent variables) underlying them. Some of these components may cause the data distributions between domains to be different, while others may not. Some of these components may capture the intrinsic structure underlying the original data, while others may not. Our goal is to discover those components that do not cause distribution change across the domains and capture the structure of the original data well. We will show in this paper that, compared to MMDE, TCA is much more efficient and can handle the out-of-sample extension problem.

The rest of the paper is organized as follows. Section 2 first describes the problem statement and preliminaries of domain adaptation. Our proposed method is presented in Section 3. We then review some related works in Section 4. In Section 5, we conduct a series of experiments on indoor WiFi localization and text classification. The last section gives some conclusive discussions.

In the sequel, A ≻ 0 (resp. A ⪰ 0) means that the matrix A is symmetric and positive definite (pd) (resp. positive semidefinite (psd)). Moreover, the transpose of vector / matrix (in both the input and feature spaces) is denoted by the superscript ⊤, A† is the pseudo-inverse of the matrix A, and tr(A) denotes the trace of A.

2 Preliminaries of Domain Adaptation

In this paper, we focus on the setting where the target domain has no labeled training data, but has plenty of unlabeled data. We also assume that some labeled data DS are available in a source domain, while only unlabeled data DT are available in the target domain. We denote the source domain data as DS = {(xS1 , yS1 ), . . . , (xSn1 , ySn1 )}, where xSi ∈ X is the input and ySi ∈ Y is the corresponding output. Similarly, we denote the target domain data as DT = {xT1 , . . . , xTn2 }, where the input xTi is also in X. Let P(XS) and Q(XT ) (or P and Q for short) be the marginal distributions of XS and XT , respectively. In general, P and Q can be different. Our task is then to predict the labels yTi 's corresponding to the inputs xTi 's in the target domain. The key assumption in a typical domain adaptation setting is that P ̸= Q, but P(YS|XS) = P(YT |XT ) .

2.1 MaximumMean Discrepancy

Many criteria, such as the Kullback-Leibler (KL) divergence, can be used to estimate the distance between distributions.

However, many of these criteria are parametric, since an intermediate density estimate is usually required. To avoid such a non-trivial task, a non-parametric distance estimate between distributions is more desirable. Recently, Borgwardt et al. [2006] proposed the Maximum Mean Discrepancy (MMD) as a relevant criterion for comparing distributions based on the Reproducing Kernel Hilbert Space (RKHS). Let X = {x1, . . . , xn1 } and Y = {y1, . . . , yn2 } be random variable sets with distributions P and Q. The empirical estimate of the distance between P and Q, as defined by MMD, is

where H is a universal RKHS [Steinwart, 2001], and φ : X → H.

Therefore, the distance between distributions of two samples can be well-estimated by the distance between the means of the two samples mapped into a RKHS.

3 Transfer Component Analysis

Based on the inputs {xSi } and outputs {ySi } from the source domain, and the inputs {xTi } from the target domain, our task is to predict the unknown outputs {yTi } in the target domain. The general assumption in domain adaptation is that the marginal densities, P(XS) and Q(XT ), are very different. In this section, we attempt to find a common latent representation for both XS and XT that preserves the data configuration of the two domains after transformation. Let the desired nonlinear transformation be φ : X → H. Let X ′S = {x′Si } = {φ(xSi )}, X ′T = {x′Ti } = {φ(xTi )} and X ′ = X ′S ∪X ′T be the transformed input sets from the source, target and combined domains, respectively. Then, we desire that P ′ (X ′S ) = Q′ (X ′T ).

Assuming that φ is the feature map induced by a universal kernel. As shown in Section 2.1, the distance between two distributions P and Q can be empirically measured by the (squared) distance between the empirical means of the two domains:

Therefore, a desired nonlinear mapping φ can be found by minimizing this quantity. However, φ is usually highly nonlinear and a direct optimization of (2) can get stuck in poor local minima. We thus need to find a new approach, based on the following assumption.

The key assumption in the proposed domain adaptation setting is that P ̸= Q, but P(YS|φ(XS)) = P(YT |φ(XT )) under a transformation mapping φ on the input.

In Section 3.1, we first revisit Maximum Mean Discrepancy Embedding (MMDE) which proposed to learn the kernel matrix K corresponding to the nonlinear mapping φ by solving a SDP optimization problem. In Section 3.2, we then propose a factorization of the kernel matrix for MMDE. An efficient eigendecomposition algorithm for kernel learning and computational issues are discussed in Sections 3.3 and 3.4.

3.1 Kernel Learning for Domain Adaptation

Instead of finding the nonlinear transformation φ explicitly, Pan et al. [2008] proposed to transform this problem as a kernel learning problem. By virtue of the kernel trick, (i.e., k(xi, xj ) = φ(xi)′φ(xj )), the distance between the empirical means of the two domains in (2) can be written as:

where

is a (n1 +n2) × (n1 +n2) kernel matrix, KS,S, KT,T and KS,T respectively are the kernel matrices defined by k on the data in the source domain, target domain, and cross domains; and L = [Lij ] ⪰ 0 with Lij = 1 n21 if xi, xj ∈ XS; Lij = 1 n22 if xi, xj ∈ XT ; otherwise, - 1 n1n2 .

In the transductive setting, learning the kernel k(·, ·) can be solved by learning the kernel matrix K instead. In [Pan et al., 2008], the resultant kernel matrix learning problem is formulated as a semi-definite program (SDP). Principal Component Analysis (PCA) is then applied on the learned kernel matrix to find a low-dimensional latent space across domains. This is referred to as Maximum Mean Discrepancy Embedding (MMDE).

3.2 Parametric Kernel Map for Unseen Patterns

There are several limitations of MMDE. First, it is transductive and cannot generalize on unseen patterns. Second, the criterion (3) requires K to be positive semi-definite and the resultant kernel learning problem has to be solved by expensive SDP solvers. Finally, in order to construct lowdimensional representations of X ′S and X ′T , the obtained K has to be further post-processed by PCA. This may potentially discard useful information in K.

In this paper, we propose an efficient method to find a nonlinear mapping φ based on kernel feature extraction. It avoids the use of SDP and thus its high computational burden. Moreover, the learned kernel k can be generalized to out-of-sample patterns directly. Besides, instead of using a two-step approach as in MMDE, we propose a unified kernel learning method which utilizes an explicit low-rank representation.

First, recall that the kernel matrix K in (4) can be decomposed as K = (KK-1/2 )(K-1/2K), which is often known as the empirical kernel map [Sch¨olkopf et al., 1998]. Consider the use of a (n1 + n2) × m matrix ˜ W to transform the corresponding feature vectors to a m-dimensional space. In general, m ≪ n1 + n2. The resultant kernel matrix 1 is then

where W = K-1/2˜ W ∈ R(n1+n2)×m. In particular, the corresponding kernel evaluation of k between any two patterns xi and xj is given by

1 As is common practice, one can ensure that the kernel matrix K is positive definite by adding a small ϵ > 0 to its diagonal [Pan et al., 2008].

where kx = [k(x1, x), . . . , k(xn1+n2 , x)]⊤ ∈ Rn1+n2 . Hence, the kernel ˜k in (6) facilitates a readily parametric form for out-of-sample kernel evaluations.

Moreover, using the definition of ˜K in (5), the distance between the empirical means of the two domains can be rewritten as:

3.3 Transfer Components Extraction

In minimizing criterion (7), a regularization term tr(W ⊤W) is usually needed to control the complexity of W. As will be shown later in this section, this regularization term can avoid the rank deficiency of the denominator in the generalized eigendecomposition. The kernel learning problem for domain adaptation then reduces to:

where μ is a trade-off parameter, I ∈ Rm×m is the identity matrix, H = In1+n2 - 1 n1+n2 11⊤ is the centering matrix, where 1 ∈ Rn1+n2 is the column vector with all ones, and In1+n2 ∈ R(n1+n2)×(n1+n2) is the identity matrix. Moreover, note that the constraint W ⊤KHKW = I is added in (8) to avoid the trivial solution (W = 0), such that the transformed patterns do not collapse to one point, which can inflate the learned kernel k such that the embedding of data x′i is preserved as in kernel PCA.

Though the optimization problem (8) involves a nonconvex norm constraint W ⊤KHKW = I, it can still be solved efficiently by the following trace optimization problem:

Proposition 1 The optimization problem (8) can be reformulated as

or

Proof. The Lagrangian of (8) is

where Z is a symmetric matrix. Setting the derivative of (11) w.r.t. W to zero, we have

Multiplying both sides on the left by W T , and then on substituting it into (11), we obtain (9). Since the matrix I + μKLK is non-singular benefited from the regularization term tr(W ⊤W), we obtain an equivalent trace maximization problem (10). □

Similar to kernel Fisher discriminant (KFD), the solution of W in (10) is the eigenvectors corresponding to the m leading eigenvalues of (I + μKLK)-1KHK, where at most n1 + n2 - 1 eigenvectors can be extracted. In the sequel, the proposed method is referred to as Transfer Component Analysis (TCA).

3.4 Computational Issues

The kernel learning algorithm in [Pan et al., 2008] relies on SDPs. As there are O((n1 +n2)2 ) variables in ˜K, the overall training complexity is O((n1 + n2)6.5 ) [Nesterov and Nemirovskii, 1994]. This becomes computationally prohibitive even for small-sized problems. Note that criterion (3) in this kernel learning problem is similar to the recently proposed supervised dimensionality reduction method colored MVU [Song et al., 2008], in which low-rank approximation is used to reduce the number of constraints and variables in the SDP. However, gradient descent is required to refine the embedding space and thus the solution can get stuck in a local minimum. On the other hand, our proposed kernel learning method requires only a simple and efficient eigendecomposition. This takes only O(m(n1 +n2)2 ) time when m non-zero eigenvectors are to be extracted [Sorensen, 1996].

4 RelatedWorks

Domain adaptation, which can be considered as a special setting of transfer learning [Pan and Yang, 2008], has been widely studied in natural language processing (NLP) [Ando and Zhang, 2005; Blitzer et al., 2006; Daum´e III, 2007]. Ando and Zhang [2005] and Blitzer [2006] proposed structural correspondence learning (SCL) algorithms to learn the common feature representation across domains based on some heuristic selection of pivot features. Daum´e III [2007] designed a heuristic kernel to augment features for solving some specific domain adaptation problems in NLP. Besides, domain adaptation has also been investigated in other application areas such as sentiment classification [Blitzer et al., 2007]. Theoretical analysis of domain adaptation has also been studied in [Ben-David et al., 2007].

The problem of sample selection bias (also referred to as co-variate shift) is also related to domain adaption. In sample selection bias, the basic assumption is that the sampling processes between the training data Xtrn and test data Xtst may be different. As a result, P(Xtrn) ̸= P(Xtst), but P(Ytrn|Xtrn) = P(Ytst|Xtst). Instance re-weighting is a major technique for correcting sample selection bias [Huang et al., 2007; Sugiyama et al., 2008]. Recently, a state-ofart method, called kernel mean matching (KMM), is proposed [Huang et al., 2007]. It re-weights instances in a RKHS based on the MMD theory, which is different from our proposed method. Sugiyama et al. [2008] proposed another re-weighting algorithm, Kullback-Leibler Importance Estimation Procedure (KLIEP), which is integrated with crossvalidation to performmodel selection automatically. Xing et al. [2007] proposed to correct the labels predicted by a shiftunaware classifier towards a target distribution based on the mixture distribution of the training and test data. Matching distributions by re-weighting instances is also used successfully in Multi-task Learning [Bickel et al., 2008]. However, unlike instance re-weighting, the proposed TCA method can cope with noisy features (as in image data and WiFi data) by effectively denoising and finding a latent space for matching distributions across different domains simultaneously. Thus, TCA can be treated as an integration of unsupervised feature extraction and distribution matching in a latent space.

5 Experiments

In this section, we apply the proposed domain adaptation algorithm TCA on two real-world problems: indoor WiFi localization and text classification.

5.1 Cross-domainWiFi Localization

For cross-domain WiFi localization, we use a dataset published in the 2007 IEEE ICDM Contest [Yang et al., 2008]. This dataset contains some labeled WiFi data collected in time period A (the source domain) and a large amount of unlabeled WiFi data collected in time period B (the target domain). Here, a label means the corresponding location where the WiFi data are received. WiFi data collected from different time periods are considered as different domains. The task is to predict the labels of the WiFi data collected in time period B. More specifically, all the WiFi data are collected in an indoor building around 145.5 × 37.5 m2 , 621 labeled data are collected in time period A and 3128 unlabeled data are collected in time period B.

We conduct a series of experiments to compare TCA with some baselines, including other feature extraction methods such as KPCA, sample selection bias (or co-variate shift) methods, KMM and KLIEP and a domain adaptation method, SCL. For each experiment, all labeled data in the source domain and some unlabeled data in the target domain are used for training. Evaluation is then performed on the remaining unlabeled data (out-of-sample) in the target domain. This is repeated 10 times and the average performance is used to measure the generalization abilities of the methods. In addition, to compare the performance between TCA and MMDE, we conduct some experiments in the transductive setting [Nigam et al., 2000]. The evaluation criterion is the Average Error Distance (AED) on the test data, and the lower the better. For determining parameters for each method, we randomly select a very small subset of the target domain data to tune parameters. The values of parameters are fixed for all the experiments.

Figure 1(a) compares the performance of Regularized Least Square Regression (RLSR) model on different feature representations learned by TCA, KPCA and SCL, and different re-weighted instances learned by KMM and KLIEP. Here, we use μ = 0.1 for TCA and the Laplacian kernel. As can be seen, the performance can be improved with the new feature representations of TCA and KPCA. TCA can achieve much higher performance because it aims at finding the leading components that minimize the difference between domains. Then, from the space spanned by these components, the model trained in one domain can be used to perform accurate prediction in the other domain.

Figure 1(b) shows the results under a varying number of unlabeled data in the target main. As can be seen, with only a few unlabeled data in the target domain, TCA can still find a good feature representation to bridge between domains.

Since MMDE cannot generalize to out-of-sample patterns, in order to compare TCA with MMDE, we conduct another series of experiments in a transductive setting, which means that the trained models are only evaluated on the unlabeled data that are used for learning the latent space. In Figure 1(c), we apply MMDE and TCA on 621 labeled data from the

(a) Varying # features of domain adaptation

methods. (# unlabeled data is 300).

(b) Varying # unlabeled data (# dimensions of

TCA and KPCA is 10).

(c) Comparison of MMDE and TCA in the

transductive setting (# unlabeled data is 300).

Figure 1: Comparison of Average Error Distance (in m).

source domain and 300 unlabeled data from the target domain to learn new representations, respectively, and then train RLSR on them. More comparison results in terms of ACE with varying number of training data are shown in Table 1. The experimental results show that TCA is slightly higher (worse) than MMDE in terms of AED. This is due to the nonparametric kernel matrix learned by MMDE, which can fit the observed unlabeled data better. However, as mentioned in Section 3.4, the cost of MMDE is expensive due to the computationally intensive SDP. The comparison results between TCA and MMDE in terms of computational time on the WiFi dataset are shown in Table 2.

5.2 Cross-domain Text Classification

In this section, we perform cross-domain binary classification experiments on a preprocessed dataset of Reuters-21578. These data are categorized to a hierarchical structure. Data from different sub-categories under the same parent category are considered to be from different but related domains. The task is to predict the labels of the parent category. By following this strategy, three datasets orgs vs people, orgs vs places and people vs places are constructed. We randomly select 50% labeled data from the source domain, and 35% unlabeled data from the target domain. Evaluation is based on the (out-of-sample) testing of the remaining 65% unlabeled data in the target domain. This is repeated 10 times and the average results reported.

Similar to the experimental setting on WiFi localization, we conduct a series of experiments to compare TCA with KPCA, KMM, KLIEP and SCL. Here, the support vector machine (SVM) is used as the classifier. The evaluation criterion is the classification accuracy (the higher the better). We experiment with both the RBF kernel and linear kernel for feature extraction or re-weighting used by KPCA, TCA and KMM. The kernel used in the SVM for final prediction is a linear kernel, and the parameter μ in TCA is set to 0.1.

As can be seen from Table 3, different from experiments on the WiFi data, sample selection bias methods, such as KMM and KLIEP perform better than KPCA and PCA on the text data. However, with the feature presentations learned by TCA, SVM performs the best for cross-domain classification. This is because TCA not only discovers latent topics behind the text data, but also matches distributions across domains in the latent space spanned by the latent topics. Moreover, the performance of TCA using the RBF kernel is more stable.

6 Conclusion and Future Work

Learning feature representations is of primarily an important task for domain adaptation. In this paper, we propose a new feature extraction method, called Transfer Component Analysis (TCA), to learn a set of transfer components which reduce the distance across domains in a RKHS. Compared to the previously proposed MMDE for the same task, TCA is much more efficient and can be generalized to out-of-sample patterns. Experiments on two real-world datasets verify the effectiveness of the proposed method. In the future, we are planning to take side information into account when learning the transfer components across domains, which may be better for the final classification or regression tasks.

7 Acknowledgement

Sinno Jialin Pan and Qiang Yang thank the support fromMicrosoft Research MRA07/08.EG01 and Hong Kong CERG Project 621307. Ivor W. Tsang thanks the support from SingaporeMOEAcRF Tier-1 Research Grant (RG15/08). James T. Kwok thanks the support from CERG project 614508.