Theoretic Analysis and Extremely Easy Algorithms for Domain Adaptive Feature Learning

1 Introduction

In traditional supervised learning, it is assumed that training data samples and test data samples are drawn from the same distribution when a learner (e.g., classifier) is trained. However, this may not be valid in domain adaptation problems. We often have plenty of labeled examples from one domain (source domain) for training a classifier and intend to apply the trained classifier to another different domain (target domain) with very few or even no labeled example. Domain adaptation has tight relationship with semisupervised learning [Liu et al., 2012] and has been studied before under different names, including covariate shift [Shimodaira, 2000] and sample selection bias [Heckman, 1979; Zadrozny, 2004].

The difficulty of domain adaptation comes from the gap between the source distribution and target distribution. Hence, the learning model trained in the source domain could not be directly used in the target domain. Many algorithms have been proposed to address domain adaptation problems. For example, a semi-supervised method, namely structural correspondence learning (SCL), was proposed in [Blitzer et al., 2006]. SCL defines pivot features which are common to both domains and tries to find the correlation between pivot and non-pivot features. It extracts the corresponding subspace and augments the original feature space with the subspace towards more effective classification. The method in [Blitzer et al., 2011] tries to find the correlations between original features and identify the subspaces in which a good predictor could be obtained by training a classifier merely on the samples from the source domain. The kernel mean matching (KMM) method was proposed in [Huang et al., 2007], which aims to minimize the distance between means of the training and test samples in a reproducing kernel Hilbert space (RKHS) by reweighting the samples from the source domain. In [Chen et al., 2011b], a co-training method called CODA for domain adaptation was proposed. In each iteration, CODA formulates an individual optimization problem which simultaneously learns a target predictor, a split of the feature space into views, and a subset of source and target features to be included in the predictor. It tries to progressively bridge the gap between the source and target domains by adding both the features and instances that the current predictor is most confident about. Nonnegative matrix factorization was employed to bridge the gap between domains by sharing feature clusters [Wang et al., 2011]. Glorot et al. [Glorot et al., 2011] proposed to learn robust feature representations with stacked denoising auto-encoders (SDA) for domain adaptation. Marginalized stacked denoising autoencoder (mSDA) [Chen et al., 2012], a variant of SDA with a slightly different network structure, was proposed to address the drawback of SDA being too slow in training. Chen et al. [Chen et al., 2012] noticed that the random feature corruption for SDA can be marginalized out, which is equivalent to training a learning model with an infinitely large number of corrupted input data conceptually. Moreover, the linear denoising auto-encoders used in SDA have a closed form, which help speed up the computation. Promising performance was achieved in cross-domain sentiment analysis tasks. In [Sun et al., 2015], correlation alignment (CORAL) exploits the difference between the covariance matrices as a measure of the gap between the source and target domains. A shallow linear feature algorithm was then proposed. Inspired by the theory of domain adaptation [Ben-david et al., 2006], domainadversarial neural networks (DANN) [Ajakan et al., 2014] and domain adaptation by back-propagation (DAB) [Ganin and Lempitsky, 2015] optimize an approximated domain distance and an empirical training error on the source domain to seek the hidden representations for both source and target domain samples. DANN and DAB can be treated as classifiers for tackling domain adaptation problems, and also be trained on top of other feature learning algorithms, e.g., mSDA.

∗Corresponding author. Email: cswhjiang@gmail.com

Besides the aforementioned methods, domain adaptation has also been studied theoretically. Most of them are built on distances measuring the dissimilarity between different distributions, and generalization bounds are derived based on the proposed distances. In [Ben-david et al., 2006], the A-distance was used to analyze representations for domain adaptation, and VC-dimension shaped generalization bounds were derived for domain adaptation. The analysis showed that a good feature learning algorithm should achieve a low training error on source domain and a small A-distance simultaneously. In [Blitzer et al., 2008], a uniformconvergence bound was provided and it was extended to domain adaptation with multiple source domains combined with weights. In [Mansour et al., 2009; Zhang et al., 2013], the A-distance was extended to a more general form and could be used to compare the distance for more general tasks such as regression. All the distances mentioned above were defined in a worst-case sense. In [Germain et al., 2013], a distance defined in an average sense by making use of PAC-Bayesian theory was suggested and an algorithm that simultaneously optimizes the error on the source domain, the hypothesis complexity, and the distance was proposed. In [Ben-David et al., 2010], the conditions for the success of domain adaptation were analyzed. It was shown that a small distance between source and target domains and the existence of a low error classifier on both domains in the hypothesis class are necessary for the success of domain adaptation.

In this paper, we provide theoretic analysis of several key issues pertaining to effective domain adaptive feature learning, showing that the difference (measured by Frobenius norm) between the second moments of source and target domain distributions should be small. Based on this analysis, we propose a simple yet effective feature learning algorithm used in conjunction with linear classifiers. To further improve the feature learning quality, we employ a deep learning approach inspired by stacked denoising auto-encoders in [Glorot et al., 2011; Chen et al., 2012], leading to a deep linear model (DLM). DLMs are easy to analyze and usually are the starting point for theoretical development of neural networks [Goodfellow et al., 2016]. Finally, we demonstrate the effectiveness of our proposed feature learning algorithms on the Amazon review and spam datasets.

2 Theoretic Analysis and NewAlgorithms

2.1 Notations and Background

Usually, a domain is considered as a pair consisting of a distribution D on X and a labeling function f : X ↦→ {0, 1}. In this paper, we consider two domains, a source domain

〈DS, fS〉 and a target domain 〈DT , fT 〉. The probability density functions for source distribution and target distribution are pS(x) and pT (x), respectively. There exist ns samples DS = {x1, · · · , xns } ∈ Rd with labels LS = {y1, · · · , yns } sampled from the source domain while nt samples DT = {xns+1, · · · , xn} ∈ Rd from the target domain are sampled without labels. They have the same number of features, which is denoted as d. The samples from source domain form the data matrix XS ∈ Rd×ns , and samples from target domain form XT ∈ Rd×nt . We use X ∈ Rd×n to denote the data matrix containing the samples from both domains.

A hypothesis is a function h : X ↦→ {0, 1}. The risk of a hypothesis h over domain 〈D, f〉 is denoted as ǫ(h, f) = E[|h(x) - f(x)|], which is the difference between the two functions. We use notations ǫS(h, fS) = ES [|h(x) - fS(x)|] and ǫT (h, fT ) = ET [|h(x) - fT (x)|] to denote the risk of h on source domain and target domain respectively. In this paper, we consider only linear classifiers. We denote the best linear classifier for source domain as h∗S with corresponding parameter vector w∗S , the best classifier for target domain as h∗T with parameter vector w∗T . For simplicity of expression, we define the difference of expectation of a function t(x) on source domain and target domain as ES-T [t(x)] =

ES [t(x)] - ET [t(x)] = ∫ t(x)(pS (x) - pT (x))dx. Our goal in this paper is to learn a new feature representation with samples from source domain and target domain such that we can train a classifier with the learned representations on source domain and apply it directly to target domain for achieving low ǫT (h, fT ) value.

2.2 Analysis of Feature Learning for Linear Classifiers

Assumption. We assume that ‖x‖ ≤ α for all samples and there exists a low-risk linear classifier h∗ with parameter w∗ for both domains. Its risk on source domain is λ1 = ǫS(h∗ , fS), and risk on target domain is λ2 = ǫT (h∗ , fT ) and λ = ǫS(h∗ , fS) + ǫT (h∗ , fT ), where λ is assumed to be small.

With triangle inequality, it was shown that for any classifier h, the following is satisfied [Blitzer et al., 2008]:

From this inequality, we can see that the performance of classifier h on target domain is determined by: 1) the risk of the best classifier h∗ on both domains; 2) the risk of h on source domain; 3) the difference of dissimilarity between h and h∗ on both domains. A good feature learning algorithm should decrease the sum of these three terms. In this paper, we focus on the third part and provide an analysis for effective linear feature learning algorithm for linear classifiers.

In the above inequality, |h(x) - h∗ (x)| measures the difference between h(x) and h∗ (x), which is a non-smooth 0-1 loss and is difficult to analyze. In this paper, we use a smooth approximation for the measure of dissimilarity between h and h∗ . We denote the smooth loss as lx,y(z) = lx,y(wT x), where w is the parameter for the linear classifier h(x) and y is the true label of sample x. lx,y(z) can be logistic loss or smooth approximation of hinge loss [Zhang and Oles, 2001]. We denote l′x,y (z) and l′′ x,y (z) as the first and second derivatives of lx,y(z) respectively. Thus, we have the following theorem, which is proved in the supplementary material.

Theorem 1. Let R = {x = (x1, · · · , xd)T : ai < xi < bi (i = 1, 2, · · · , d)} and R′ = {y = (xT , zT )T = (x1, · · · , xd, z1, · · · , zd)T : ai < xi < bi and ai < zi < bi (i = 1, 2, · · · , d)}. Assume that any sample in our problem satisfies x ∈ R, we have the following inequality:

where C, M and G are defined as

Diu(x) and Div(x) are partial derivatives, y∗ is the label of sample x predicted by w∗ as y∗ = sgn(xT w∗ ).

Our goal is to find new representations such that the approximation for the measure of dissimilarity between h and h∗ is small. Here, we minimize its upper bound instead. In the right hand side of inequality (1), w∗ is the unknown best possible classifier, hence constants like C, G and ∣∣ES-T [lx,y∗(xT w∗ )]∣∣ which are related to w∗ could not be optimized directly by feature learning algorithms. We assume that the learned features lie in the same region with the original feature, hence M could not be optimized. Therefore, in order to achieve good performance, we should minimize ‖ES-T [xxT ]‖2F . We will use ‖ES-T [xxT ]‖2F as a measure of domain distance and design a feature learning algorithm based on it.

2.3 Algorithm

Let us denote MS = 1 ns XSX T S , MT = 1 nt XT X T T and ∆M = MS -MT , and our goal is to learn a linear transformation P such that the learned data matrix P T X is suitable for domain adaptation. Based on the above analysis, one of the objectives is to minimize ‖P T ∆MP‖2F = tr(∆MPP T ∆MPP T ), which is difficult to optimize. Because positive-semidefinite matrices A and B satisfy 0 ≤

tr(AB) ≤ tr(A) tr(B), we have tr(∆MPP T ∆MPP T ) ≤ tr(∆MPP T ∆M) tr(PP T ). Therefore, the domain distance is bounded by tr(P T ∆M 2P) tr(PP T ). Hence, our goal can be expressed as finding a matrix P with not only small Frobenius norm but also small tr(P T ∆M 2P ). Moreover, the learned representation should also be similar to the original ones. Hence, we can simply use

as objective function 1 . In order to force each feature to contribute equally, the length of features should be incorporated by the second term. The final objective function of our method is expressed as follows

where Λ is a diagonal matrix with Λii = Xi·X T i· , and Xi· is the ith row of data matrix X. We term our method as Feature LeArning with second Moment Matching (FLAMM). We will prove that our method will decrease the distance between domains under some conditions. If γ2 = 0, this algorithm becomes regularized linear regression, which is called simple feature learning algorithm, referred as SFL 2 . SFL does not consider minimizing the distance between the second moments explicitly, but it still can improve the adaptation performance in many cases which can be seen from the experimental results section. With our theoretical analysis of domain adaptation, we will make an attempt to illustrate why this simple method works.

To further improve the performance, we adopt the strategy from deep learning methods and apply this algorithm to the learned feature repeatedly. Following the tradition of deep learning, we call the process of finding one linear transformation matrix and updating the data matrix as one layer. The whole algorithm is summarized in Algorithm 1. We can see that the output of our method has the same dimensionality as input. Moreover, the final output is just the linear transformation of the original data matrix, which makes it easier to analyze than the other auto-encoder based methods.

Algorithm 1 Feature learning with second moment matching (FLAMM).

Input: X, γ1, γ2, number of layers K.

for k = 1 to K do

Compute P by solving problem (2).

Update X by X = P T X.

end for

Output: X

In [Sun et al., 2015], a linear feature algorithm called correlation alignment (CORAL) was proposed. It uses the difference between the covariance matrices of source distribution and target distribution as a measure of the gap between source domain and target domain. CORAL just whitens source domain and then recolors it with covariance matrix of target domain. The authors did not provide theoretical analysis for the gap measure used and CORAL is also not a deep feature learning method. We will show that our method is better than CORAL.

1 To express clearly, we omit the bias term.

2 The linear transformation step of mSDA could be rewritten in a form similar to SFL approximately. Hence, each layer of mSDA could be seen as SFL plus a non-linear transformation step.

2.4 Analysis of OurMethod

In this subsection, we will provide an analysis of FLAMM. Since FLAMM is just a revision of SFL by adding a term, we will analyze SFL first. We will prove that the domain distance decreases for each layer of SFL under some conditions, which also explains why mSDA works since the layer of mSDA is similar to that of SFL. Based on that, we will provide an analysis of FLAMM. Here are some necessary lemmas.

Lemma 1 (Weyl's inequality [Horn and Johnson, 2012] Theorem 4.3.1). Let A,B ∈ Rn×n be symmetric matrices, and denote the eigenvalue of matrix A as λi(A), which is arranged in increasing order λ1(A) ≤ λ2(A) ≤ · · · ≤ λn(A). For k = 1, 2, · · · , n, we have λk(A)+λ1(B) ≤ λk(A+B) ≤ λk(A) + λn(B).

Lemma 2 ([Horn and Johnson, 1991] Theorem 3.3.16). Let A,B be n × n matrices, and denote the singular values of matrix A as σi(A), which is arranged in increasing order σ1(A) ≤ σ2(A) ≤ · · · ≤ σn(A). For k = 1, 2, · · · , n, we have σk(AB) ≤ σk(A)σn(B).

Lemma 3. P is computed by solving problem (2) with γ2 = 0, if γ1 ≥ λd(XXT )-λ1(XXT ) λ1(Λ) then I -PP T is positive definite matrix.

Proof: According to Lemma 1, we have λi(XX T + γ1Λ) ≥ γ1λi(Λ) + λ1(XX T ), therefore λi((XX T + γ1Λ)-1 ) ≤ 1 γ1λi(Λ)+λ1(XXT ) . By Lemma 2, we have:

λ1(Λ) , we will have λd (XXT ) γ1λi(Λ)+λ1(XXT ) < 1, which means σi(P) < 1. Hence, λi(PP T ) = σi(P)2 < 1. Therefore, I - PP T is positive definite matrix. □

Lemma 4. A, B, C are symmetric matrices and A ⪰ 0, B ⪯ C, then tr(AB) ≤ tr(AC).

Proof: If A is a rank-one matrix, we can express A as A = vvT . Then we have tr(AB) = tr(vvT B) = vT Bv ≤ vT Cv = tr(AC). If A is not a rank-one matrix, it can be expressed as A = ∑i λiuiuTi . Since A ⪰ 0, we denote vi = √λiui and write A = ∑i vivT i . Then we have Based on the above lemmas, we have the following theorem:

Theorem 2. If P is computed by solving problem (2) with γ2 = 0 and γ1 ≥ λd(XXT )-λ1(XXT ) λ1(Λ) , then the inequality ‖∆M‖2F ≥ ∥∥P T ∆MP ∥∥2F is satisfied. Proof: In this proof, we will use the following notations:

By Lemma 3, we know that if γ1 ≥ λd(XXT )-λ1(XXT ) λ1(Λ) we will obtain that I - PP T is a positive definite matrix, which means Λ - PnΛP T n is also a positive definite matrix. Hence, we have PnΛP T n ⪯ Λ. Therefore, we obtain:

□

From the above theorem, we can see that on a certain layer of SFL, if γ1 is big enough distance between the second moments will definitely get smaller compared to that of the input matrix. Hence, SFL will decrease the distance implicitly on one layer. This also explains why mSDA works for domain adaptation problems, since the layer of mSDA is very similar to that of SFL. Therefore, even if SFL and mSDA do not optimize the difference between the two second moment explicitly, they are capable of improving the domain adaptation performance. For FLAMM, with the third term in the objective function, it can decrease the domain distance explicitly. Hence, FLAMM could be seen as a trade-off between reconstruction error and domain distance. And we can achieve the same reconstruction error with smaller domain distance. That's the reason why FLAMM performs better than SFL, which can be seen in the following section. In practice, we do not need to compute the exact condition in theorem 2, we can just treat γ1 and γ2 as ordinary parameters and select them using the validation set. We will illustrate the changes of distance empirically in the experimental results section.

3 Experimental Results

3.1 Datasets

We evaluate and analyze the proposed methods on the Amazon review dataset 3 [Blitzer et al., 2007], and the ECML/PKDD 2006 spam dataset 4 [Bickel, 2008]. As in [Blitzer et al., 2007], a smaller subset of the Amazon review dataset which contains reviews of four types of products: Books, DVDs, Electronics, and Kitchen appliances, is used. In this dataset, each domain consists of 2000 labeled inputs and approximately 4000 unlabeled ones. We only consider binary classification problem, i.e. whether a review is positive (higher than 3 stars) or negative (3 stars or lower) as in [Glorot et al., 2011; Chen et al., 2012] and use 5000 most frequent terms as features.

3 http://www.cs.jhu.edu/˜mdredze/datasets/ sentiment/

4 http://www.ecmlpkdd2006.org/challenge.html

The second dataset is from the ECML/PKDD 2006 discovery challenge which is about personalized spam filtering and generalization across related learning tasks. It contains two tasks: task A and task B. We adopt the dataset of task A for our comparisons and analysis because it contains more samples. In this dataset, 4000 labeled training samples were collected from publicly available sources, with half of them being spam and the other half being non-spam. The testing samples were collected from 3 different user inboxes, say U0, U1 and U2, each of which consists of 2500 samples. Hence, the distributions of source domain and target domain are different since they are from different sources. In this dataset, there are three adaptation tasks in total. As in the Amazon review dataset, 5000 most frequent terms were chosen as features. Three samples were deleted as a result of not containing any of these 5000 terms. Hence, we have 7497 testing samples totally.

3.2 Comparison and Analysis

For domain adaptation tasks, traditional cross validation can not be used to select parameters since the source distribution and target distribution are different. In our experiments, we simply use a small validation set containing only 500 labeled samples selected randomly from target domain to select parameters for all feature learning algorithms 5 . Once we have the new learned features, we treat the cross domain classification task as traditional supervised learning problem and the validation set was not used to select parameters for classifiers.

5 The method we used was called STV in [Zhong et al., 2010]. And it works quite well in our setting. Transfer cross validation [Zhong et al., 2010] should provide similar results.

We report the results of two baseline representations. The first one is just the raw tf-idf representation and the second one is the PCA representation. For PCA, the subspace is obtained from both source domain samples and target domain samples. Besides these two baselines, we also compare our method with CORAL [Sun et al., 2015] and CODA [Chen et al., 2011a]. CORAL is an effective shallow feature learning method and has been shown outperform many well-known methods, e.g. GFK [Gong et al., 2012], SVMA [Duan et al., 2012] and SCL [Blitzer et al., 2006], mainly on image domain adaptation tasks. CODA is a state-of-the-art domain adaptation algorithm based on co-training. At last, we compare our method with deep learning methods. Since mSDA is better than SDA as shown in [Chen et al., 2012], we only provide comparisons with mSDA. We use binary representations for mSDA as in [Chen et al., 2012], and for the other methods, samples are represented with tf-idf and normalized to have unit length. For representations learned by all feature learning methods, we train a linear SVM on the source domain data and test it on the target domain. The performance metric is classification accuracy.

We denote our method with K layers as FLAMMK and similar notations are also used for SFL and mSDA. We set K as 2 for the Amazon review dataset and 5 for the spam dataset. To provide better understanding of our algorithm, we also provide results with only one layer. Parameters for representation learning process were selected based on the validation set. On the Amazon review dataset, both γ1 and γ2 were selected from [10, 20, · · · , 100]. On the spam dataset, they were selected from [10, 30, 50, · · · , 150]. For mSDA, the noise was selected from [0.5, 0.6, 0.7, 0.8, 0.9] on the Amazon dataset and [0.9, 0.91, · · · , 0.99] on the spam dataset. For PCA, the reduced dimensionality was selected from

[50, 100, 150, 200, 250, 300] for both datasets. For CODA 6 , we used the same parameters as in [Chen et al., 2011b], except that we set γ = 0.0001 on the spam dataset. The results of CODA depend on initializations, hence we run CODA 10 times and provide the average accuracies. The results are presented in Tables 1 and 2. We can see that our method achieved the best performance on the two datasets. Results of FLAMM are better than those of SFL, and results with multiple layers are usually better than results with only one layer. We can see that the proposed objective and multi-layer structure did help improve the adaptation performance.

The performances with different number of layers on the two datasets are also plotted in Figure 1. We can see that our method is better than SFL consistently on both datasets. On the Amazon dataset, our method become worse when K is larger than 4. The reason might be that the difference between the learned representations and the original representations is unnecessarily high.

We also present the distance between the second moments of source domain and target domain through layers with different γ1 and γ2 7 when K = 10 as shown in Figure 2. We can see that the distance decreases through layers for both FLAMM and SFL and the distance of FLAMM is smaller than that of SFL with the same γ1. This observation explained why SFL also improved the adaptation performance. For FLAMM, the parameters control how small domain distance we can get. Bigger γ1 and γ2 will lead to smaller distance between the two second moments. But at the same time, the learned representations will be more different from the original input 8 , which might not be suitable for classifiers. Hence, our method could be understood as a trade-off between domain distance and reconstruction error.

6 Source code: http://www.cse.wustl.edu/˜mchen/ code/coda.tar

7 In our implementation, γ2 is the product of a number and n, where n is the number of samples.

4 Conclusions

In this paper, theoretic analysis of the factors that affect the performance of feature learning for domain adaptation was provided. We found that the distance between the second moments of the source domain and target domain should be small, which is important for a linear classifier to generalize well on the target domain. Based on our analysis, an extremely easy yet effective feature learning algorithm was proposed. Furthermore, our algorithm was extended by leveraging multiple layers, leading to a deep linear model. Meanwhile, we also explained why the simple ridge regression based method which does not minimize the gap between source and target distributions can improve the adaptation performance. The experimental results on the Amazon review and spam datasets corroborated the advantages of our proposed feature learning approach.

Acknowledgments

This work was partially supported by the following grants: NSF-IIS 1302675, NSF-IIS 1344152, NSF-DBI 1356628 and RGC GRF Grant No. PolyU 152039/14E.

8 FLAMM tries to reconstruct the new input data matrix in each layer, which is the output data matrix from previous layer. Hence, the outputs of each layer will usually have larger and larger difference with the original samples through layers.