Domain Adaptation with Topical Correspondence Learning

1 Introduction

The conventional discriminative learning implicitly assumes that training and test data follow the same distribution. This assumption, however, seldom holds in reality. In contrary, it is usually expensive to obtain an adequate amount of training data that follow the same distribution of the test data. On the other hand, there often exists a sufficient amount of labeled data from related, albeit different, domains. The objective of domain adaptation or transfer learning is to exploit such labeled data in a source domain to accurately predict the labels of test data in a target domain where little or no label information is available.

Several domain adaptation methods have been developed recently for applications in diverse areas, such as text document classification [Dai et al., 2007a], computer visions [Saenko et al., 2010] and computational biology [Liu et al., 2008]. In text document classification, whose primary objective is to predict the classes of given documents, training and test documents may be from different domains. For example, in the 20Newsgroups data that have been widely used in text document classification, the task rec vs sci is to classify recreation and science related articles. Words like "cars" and "engine" as well as "doctor" and "disease" are among the most discriminative words when the documents are drawn from the automobile and medical domains. However, in the sports and space domains, which are subcategories of rec and sci, respectively, the most discriminative words become "game" and "team" as well as "moon" and "earth". If a discriminative model is trained using documents from one domain, the model typically performs poorly in other domains. This is primarily because domain-specific vocabularies are used to describe distinct concepts in different domains (i.e., subcategories here), e.g., concepts related to recreation versus that related to science. More critically, some of the most discriminative words in one domain may be missing entirely in other domains, resulting in incomparable feature spaces between training and test data.

Topical models [Xue et al., 2008; Jin et al., 2011] and Nonnegative Matrix Factorization (NMF) based methods [Lee et al., 1999; Zhuang et al., 2011; Long et al., 2012a; 2012b] have been proposed to alleviate the problem of divergent feature spaces by learning a joint representation that integrates features in the source and target domains. In text document classification, for example, it is natural to consider a document as a linear combination of semantic topics. Ideally, the class of a given document can be uniquely determined by a composition of the topics described, presumably semantically independent of the domains considered. If we can project a document from the word space to a semantics space, where each axis corresponds to a particular topic, documents from different domains can be unified in a common representation. A major challenge here is to find a projection that is not only coherent in multiple domains but also able to preserve the discriminative power after the projection.

In this paper, we proposed Topical Correspondence Learning (TCL), a novel domain adaptation method. The central element of TCL is an optimization problem, formulated as a joint Non-negative Matrix Tri-Factorization (NMTF), with the objective of simultaneously learning a topical representation and conditional probabilities of document classes. The key idea of TCL stems from the observation that a semantic topic is typically comprised of two types of words, i.e., common and domain-specific words. Even though many domainspecific words appear only in one domain, which seems to be useless for cross-domain classification, they are invaluable for discriminating classes within the domain. Common words can then serve to bridge the gap between domain-specific words for transferring knowledge across domains. TCL models the domain dependency of words in each topic by decomposing words into common and domain-specific parts in such a way that domain-specific words are explicitly associated with common words in the same topic. Comparing with the existing NMF based methods, TCL promotes the correspondence between topics in different domains and thus draws the distributions of the source and target domains closer while preserving the discriminative power in the new topical representation. TCL incorporates the label information into the optimization framework in a semi-supervised manner by directly modeling the posterior probability of labels so that no additional classifier is needed to make predictions. The TCL optimization problem is solved with an efficient iterative updating algorithm with theoretical convergence guarantees. We empirically evaluated the performance of TCL on three well-adopted benchmark datasets. Our approach outperforms several state-of-the-art methods for cross-domain document classification. Our results show that the learned topics by TCL are semantically meaningful and are useful for understanding the commonalty and difference among different domains.

In the following, we first discuss the basic notations and problem settings in Section 2. We then describe the new method along with a theoretical analysis in Section 3. Experiment results are presented in Section 4, and related works are reviewed in Section 5. We conclude in Section 6.

2 Notation and Setting

We use bold capital letters, e.g., X and Y, for matrices and bold lowercase letters, e.g., x and y, for vectors. We denote (X)i: the i-th row of matrix X, (X):j the j-th column of X, and (X)ij the entry at the i-th row and j-th column of X.

Let {Dd | d ∈ [1,D]} be a family of D domains. Following the paradigm of transductive transfer learning, we assume that documents are from two types of domains, source S where documents are labeled, and target T where documents are unlabeled. For each domain Dd, we sample an m×nd matrix of data Xd = {x1, ..., xnd }, where x(d) i is a feature vector in the shared feature space with m words. We assume that the raw feature representation only involves positive numbers, e.g. bag-of-words or term frequency-inverse document frequency (tf-idf) [Salton and Buckley, 1988]. Suppose that there are c classes. Each source domain Dd ∈ S is associated with a nd × c label matrix Yd = {y1, ..., ynd }, where if document x(d) i is in class j ∈ [1, c] then y(d) ij = 1, or y(d) ij = 0, otherwise. Our goal is to learn a classifier h ∈ H given the labeled set {(Xd,Yd) | Dd ∈ S} to accurately predict the labels of an unlabeled sets {Xd | Dd ∈ T }.

3 The TCLMethod

We begin with a brief review of Non-negative Matrix TriFactorization (NMTF) [Ding et al., 2006] and its extension to domain adaptation [Li et al., 2010]. We then present our TCL method, which preserves the modeling power of NMTF and exploits the correspondence of topics to support crossdomain knowledge transfer.

3.1 Non-negative Matrix Tri-Factorization

Given a non-negative m × n word-document matrix X, NMTF is to approximate X by the product of three nonnegative matrices: X ≈ WHVT , where W is an m × k word-topic matrix, each column of W defines a latent topic, and (W)ij describes the contribution of the i-th word to the j-th topic; V is an n × c document-class matrix representing soft membership of documents in c classes; and H is a k×c matrix indicating the association between the document classes and latent topics. The non-negativity constraint on all factors stems from the intuition that the contribution of topics should be additive rather than subtractive. This property leads to interpretability and sparse solutions to the problem [Lee et al., 1999]. Specifically, NMTF solves the following optimization problem through a set of iterative update,

where ‖.‖F is the Frobenius norm and 1u is a u × 1 column vector with all entries equal to 1. The equality constraints on W and V avoid ambiguity of the factorization and, furthermore, provide W and V with a probability interpretation, i.e., (W)ij becomes the posterior probability of the i-th word belonging to the j-th topic and (V)ij becomes the posterior probability of the i-th document being in class j.

In order to apply NMTF to a corpus of documents {Xd} from multiple domains {Dd}, the minimization problem in (1) can be extended to,

whereWd is the word-topic matrix, or the topical model, and Vd the document-class matrix in the d-th domain. From the perspective of classification, Wd can be viewed as the coordinates of a k-dimensional projection space of topics, and HVT d together can be considered as a new representation of the documents in the projected space defined by Wd. Here the common factor, H, accommodates the notion that the association between topics and document classes is domain independent. H serves as a topic-level bridge among domains by implicitly associating topics from different domains using the same coefficients. As a result, the label of a given document, x(d) i , in domain d can be determined by:

3.2 Topical Correspondence Learning

The primary objective of an NMF-based method for transductive learning is to learn a topic model, Wd, to define the coordinates of a new representation in which the distributions of source and target documents are drawn closer than before the projection. Even though the topics, (Wd1 ):i and (Wd2 ):i, with the same column index i across two domains, Dd1 and Dd2 , are implicitly associated through (H)i:, there is no guarantee that the coordinates of the new representation are closely related because a set of topics are learned independently in each domain . A possible remedy is to use a common word-topic matrix ˜W across all domains such that Xd ≈ ˜WHVT d . Although it guarantees that all domains share the same topic coordinates, this will seriously undermine the modeling power of NMF because it disregards the difference between vocabularies in different domains and thus results in an incoherent new representation. To overcome this problem, some recent works [Long et al., 2012a; Gupta et al., 2011] partition the word-topic matrix ˜W into two parts [U,Wd], where U is an m × k1 matrix representing the k1 common topics shared by all domains and Wd is an m × k2 matrix representing the k2 domain-specific topics unique to the d-th domain. The objective of the extended NMTF [Long et al., 2012a] can be formulated as,

Among all k = k1 + k2 topics in each domain, at least k1 coordinates are exactly aligned. The remaining k2 topics are used to properly model the domain-specific words to avoid negative transfer [Gupta et al., 2011].

A key observation here is that a domain-specific word is unlikely to be included in a common topic in U, because if this happened, any document associated with the topic in the other domains would have to include that domain-specific word, thus increasing the reconstruction error as a result. In other words, topics defined inWd tend to contain all domainspecific words. In fact, even though the distributions of different domains are closer in the subspace defined by U, the distributions become more distant under Wd because the corresponding coordinates are almost always orthogonal to one another. Due to the lack of association between cross-domain topics in Wd, domain-specific words will not be particularly useful for a cross-domain discriminative learner. As discussed in Section 1, domain-specific words, however, still contain valuable knowledge because many of them may be among the most discriminative features.

Domain-specific words can be exploited. The key idea, which forms the cornerstone of this research is to build a correspondence between cross-domain topics in Wd by associating domain-specific words with common words that are shared by all domains. From a document generative perspective, we assume that when we choose a word from a certain topic to generate a document, either a common word or a domain-specific word is selected. For each topic, the objective is to learn a decomposition of a common vocabulary (U):i and d domain-specific vocabularies (Wd):i. Specifically, we construct a one-to-one correspondence between cross-domain topics, Wd, and the shared topics H, arriving at minimizing the following objective function,

Here the factor of association between topics and document classes is a vertical duplication of k × c matrix H. U and Wd, which are word-topic matrices of the same size, m× k, are comprised of common and domain-specific words respectively. The hyperparameter α ∈ [0, 1] determines the probability of choosing a common or domain-specific word. By enforcing the same H on U and Wd, we in fact force the reconstruction of documents in a way that, whenever a common topic (U)i: is chosen, a proportional amount, 1-α α , of (Wd):i has also been chosen in the d-th domain as well. Accordingly we explicitly associate topics, (Wd):i, of different domains through the common topic, (U):i, by the same coefficients (H)i:. Due to this feature, we name our method Topical Correspondence Learning. Figure 1 sketches the intuition behind the proposed method.

3.3 The Algorithm

The TCL optimization problem in Eq. (4) is not jointly convex in all variables. Therefore, it is unrealistic to find global minima. Therefore we derive an iterative algorithm to search for local optima by alternatively updating one variable and fixing the others in one step of the search. Denote Pd = (αU+ (1 - α)Wd). The optimization problem in Eq. (4) can be solved using the following update rules,

Then we normalize the columns of U and Wd, and the rows of Vd to l1-norm to satisfy the equality constrains.

A proper initialization may lead to a fast convergence. Similar to [Long et al., 2012a; 2012b], we initialize the labels of documents in source domains as true labels, i.e. {Vd = Yd} if Dd ∈ S. Following the multiplicative updates in Eq. (5) to (8), if (Vd)ij is initialized to 0, it will remain to be 0. Thus the values of Vd in the source domain are automatically kept unchanged throughout the execution of the algorithm. We also initialize the labels of data in the target domain by Logistic Regression trained on the data in the source domain.

3.4 Theoretical Analysis

The correctness of the algorithm directly follows the derivation of the updating rules as stated in the following theorem:

Theorem 1. If the iteration of update rules in Eqs. (5) to (8) converge, it converges to a local optimal solution.

Proof. Let ΛU , ΛWd and ΛVd be the Lagrange multiplier matrices of the equality constraints on U, Wd, and Vd, respectively. Using the KKT conditions from the theory of constrained optimization [Boyd and Vandenberghe, 2004], for any stationary point we have the following equations,

Consider the updating rule for Wd first. If the iteration on Eq. (6) converges, the converged solutionW∗ d satisfies

Although it is difficult to explicitly compute the Lagrange multiplier ΛWd , after normalization of Wd, the two terms 1m1Tk ΛWd and 1m1TmWdΛWd are in fact equal. They can be safely ignored when considering the convergence. A similar technique can be applied to prove the convergence of U and Vd. Therefore, this gives rise to the updating rules that satisfies the KKT conditions.

We have the following theorem regarding the convergence of the iterative updating rules.

Theorem 2. The objective function O in (4) is non-increasing under the updating rules in Eqs. (5) to (8). O is invariant under these updates if and only if U, Wd, H and Vd become stationary.

Theorem 2 grantees the iterative algorithm to converge to local optima. Due to space limitation, we omit the proof but give a sketch here. To prove Theorem 2, we use the auxiliary function approach used in Expectation-Maximization [Dempster et al., 1977] and NMF [Lee et al., 1999]. The basic idea is to find an auxiliary function C(x, x′ ) that is an upper bound of the objective function O(x) and the equality of these two functions holds at x = x′ . Then we can show that each update in the form of x(t+1) ← x(t) from Eqs. (5) to (8) is equivalent to the minimization of x(t+1) = argminx C(x, x(t) ), which ensures that O is non-increasing.

4 Results

4.1 Datasets Tested

We evaluated the TCL algorithm together with the existing domain adaption algorithms on three benchmark datasets: SRAA 1 , 20-Newsgroups 2 , and Reuters-21578 3 . We restricted our evaluation to binary classification for clarity and convenience, while TCL can be readily extended to multi-class classification tasks.

SRAA dataset contains 73, 218 UserNet articles from four discussion groups: simulated auto racing (sim-auto), simulated aviation (sim-aviation), real autos (real-auto) and real aviation (real-aviation). To create the binary classification task of sim vs real, we constructed the source domain of auto to contain the sim-auto and real-auto articles and the target domain of aviation to contain the sim-aviation and realaviation articles. Likewise, we constructed the task auto vs aviation by splitting sim and real as source and target domains respectively. In each group we sampled around 3, 000 documents, each of which contained at least 20 words, to balance the number of documents across domains. We removed stop words and words appeared in less than 10 documents, resulting in a cohort of 13, 472 documents with 5, 982 features. 20-Newsgroups is a large collection of documents evenly distributed in 20 distinct newsgroups. Each document belongs to one of four top categories and one of the many subcategories. We created one binary classification task for every pair of top categories. From each top category, we selected two subcategories to form the source domain and two others as the target domain so that the classification task in source and target domains were related but their distributions were different. We followed the same procedure for selecting subcategories as in [Long et al., 2012b]. We removed stop words and words occurred in less than 15 documents, resulting in a cohort of 18, 774 documents with 13, 781 features.

1 http:// people.cs.umass.edu/ mccallum/data.html

2 http:// people.csail.mit.edu/jrennie/20Newsgroups/

3 http: //www.daviddlewis.com/resources/testcollections/

Reuters-21578 has been one of the most used test categorization collection. It contains five top categories and many subcategories. Similar to 20-Newsgroups, we used the top categories to construct binary classification tasks, and grouped subcategories into source and target domains. We used the preprocessed data 4 as described in [Pan et al., 2011].

Table 1 lists all the cross-domain tasks that were considered in our evaluation.

4.2 Performance Evaluation and Comparison

To create a baseline for our comparison, we trained a linear Support Vector Machines (SVM) and a Logistic Regression (LR) 5 method on the labeled data in the source domain and tested these two models on the target domain data. We also built a semi-supervised NMTF model using data from both source and target domains. In addition to these three baseline models, we included in our comparison several state-of-the-art domain adaptation methods, including an unsupervised marginalized Stacked Denoising Autoencoder (mSDA) [Chen et al., 2012] and two NMTF based methods, Graph co-regularized Collective Matrix Factorization (GCMF) [Long et al., 2012b] and Dual Transfer Learning (DTL) [Long et al., 2012a].

For SVM and LR, we cross-validated the C parameter on the training data. For NMTF, we implemented the formulation in Eq. (2). The labels in the source domain were included by initializing Vd as Yd and we set the number of topics, k, to 20 because it has a similar effect of the k parameter as in the other NMF-based methods. In mSDA, we stacked 5 layers of features and cross-validated the noise ratio on the training data. We then applied LR to the new representation to evaluate mSDA. For GCMF and DTL, we followed the same parameter selection criteria as in the original papers. Finally, for TCL, we set the number of topics, k, to 10 and the maximal number of iterations for updating to 100 for all tasks, and cross-validated α on training data. For all NMF-based methods, we repeated the experiment 10 times and report the mean and standard deviation of classification accuracy.

4 http://www.cse.ust.hk/TL/dataset/Reuters.zip

5 http://www.csie.ntu.edu.tw/ cjlin/liblinear/

4.3 Experiment Results

Performance Evaluation

Table 2 lists the classification accuracies of the methods compared across all domain adaption tasks considered. The new method TCL clearly outperformed the other competing methods in 10 of the 11 tasks. SVM and LR performed poorly on most of these tasks because they were unable to handle the distribution discrepancy between source and target data. As an unsupervised method, mSDA outperformed LR and SVM in most of the cases, indicating that the newly learned feature space can indeed help discriminative learners for cross-domain classification. The semi-supervised NMTF worked surprisingly well and even outperformed mSDA in many cases. Two factors may contribute to the good performance of NMTF. Firstly, the incorporation of labeled data makes the learned latent topics to preserve more discriminative power than unsupervised methods do. Secondly, the classification tasks in our experiment are closely related to the semantic topics, which align well with the assumption for NMTF based methods. As direct extensions to NMTF, both GCMF and DTL achieved better performance than NMTF overall and GCMF performed better than DTL. Finally, except on the task comp vs rec, where TCL had a comparable performance with other NMTF based methods, TCL was significantly better than the other methods. On comp vs rec task, it is likely the case that domain-dependent topics provided enough discriminative power, while additional knowledge from other domains may not be so useful.

Our implementation of TCL in MATLAB TM is very efficient. It took only ∼ 30 seconds on the largest task on a 2.30 GHz quad-core AMD Opteron TM 2376 processor.

Bridge for Knowledge Transfer - Common words

TCL outputs not only the posterior probability of class labels with Vd, but also the posterior probabilities of common and domain-specific words in a given topic, included in U and Wd, respectively. By sorting the columns of U and Wd, we can identify the most representative common and domain-specific words in a topic. Table 3 shows an example, listing the representative words from two selected groups of topics in the rec vs sci task. Here group 1 contains topics with the same column index of U andWd that are related to the class label rec, and topics in group 2 are the ones related to sci. We can observe the potential associations of sourceand target-specific words through the bridge for knowledge transfer: common words. For instance, in topic 1, it is likely that the words of car and team are associated with the common word top, and in topic 2 the words space and security are associated with such words as research and system. This information of correspondence can be useful for knowledge discovery by improving the understanding of the commonalty and difference of different domains.

Effect of Parameters

TCL has two key parameters: the number of latent topics, k, and the weight of domain-specific vocabularies, α. These two parameters are considered to be dataset dependent. In general, k should be large enough to capture the topics in the corpus. However, it should not be too large as it can easily overfit and compromise the ability to generalize to new topics. In the top panel of Figure 2, we vary the values of k from 10 to 200 and plot the average accuracy of TCL on the three datasets separately. We find that the performance of TCL is relatively stable on k in a wide range: k ∈ [10, 100]. Similarly, we plot the average accuracy of TCL on varying values of α ∈ [0, 1] in the bottom panel of Figure 2. In most cases, α = 0.1 achieves a good performance.

5 RelatedWorks and Discussions

The existing domain adaption or transfer learning methods under the transductive settings can be classified into two categories. The algorithms in the first category attempt to draw the distributions of source and target domains closer by assigning different weights to the training instances, i.e., instance re-weighting [Dai et al., 2007b; Mansour et al., 2009]. It has been shown that their performance can asymptotically approach the performance of the optimal in-domain classifier if their underlying assumptions are met.

The algorithms in the second category aim to learn a new shared feature representation in which the source and target distributions are closer than in the original representation. Among these algorithms, Structural Correspondence Learning (SCL) [Blitzer et al., 2006] and deep learning methods [Glorot et al., 2011; Chen et al., 2012] augment the original feature space with newly constructed features. The key idea is to establish correspondences between features cross domains and then add the correspondence information to the new feature representation. Other methods, such as Maximum Mean Discrepancy Embedding [Pan et al., 2008] and Transfer Component Analysis [Pan et al., 2011], project the original features onto a higher level of feature space by assuming the existence of a low dimensional space that is coherent across domains. A major disadvantage of these methods is that they are usually unsupervised; the new representation are not jointly optimized with the label information, which has no guarantee to extract predictive features.

Non-negative Matrix Tri-Factorization (NMTF) [Ding et al., 2006] has recently drawn an extensive attention in document analysis. The NMTF-based algorithms are particularly useful for domain adaptation due to their ability to simultaneously learn a shared latent feature space and incorporate label information to strengthen the discriminative power of new features. In particular, one of the inspiring works of Long et al. [2012a], i.e., Dual Transfer Learning (DTL), utilizes an NMTF model as in Eq. (3) so that the marginal and conditional distributions of the source and target domains can be drawn closer at the same time. Comparing to DTL, our new TCL method promotes the coherence of the marginal distribution by explicitly associating commonly shared and domainspecific topics. Closely related to manifold alignment [Wang and Mahadevan, 2011], Graph co-regularized Collective Matrix tri-Factorization (GCMF) [Long et al., 2012b] builds correspondence between cross-domain topics by regularizing the latent feature space to preserve the geometric structure of both words and documents in the original space. It is well suited for tasks where the labels are consistent with the nearest-neighbor graph. However, it still lacks correspondence information across multiple domains without an adequate affinity graph to capture correlations between crossdomain words. The new method TCL, on the other hand, embeds these correlations in the corresponding topics, which essentially drives the distributions of the source and target domains closer than GCMF does in the latent space.

6 Concluding Remarks

We developed a novel domain adaption method under the NMTF framework to simultaneously learn a latent topic representation in the semantic space and the posterior probability of the document labels. We explicitly associated topics across distinct domains by enforcing a one-to-one correspondence between the corresponding columns of the word-topic matrix. Conceptually, we split each topic into several parts:

one for common words and the others for domain-specific words. A key feature of TCL is its ability of utilizing common factors as a bridge to transfer knowledge cross domains. We empirically compared TCL with several baseline models and state-of-the-art methods on three benchmark datasets to demonstrate the efficacy of TCL for cross-domain document classification. As a future direction, we are particularly interested in extending TCL to many application areas, e.g. biology, where the discovery of factors that link and differentiate multiple domains is a primary concern.

Acknowledgment

This work was supported by the National Institutes of Health (R01GM100364) and the National Science Foundation (DBI0743797).