Linking Heterogeneous Input Features with Pivots for Domain Adaptation

1 Introduction

With the rise of social media (e.g., blogs, social networks, etc.), more and more user generated sentiment data have been shared on the web. They exist in the form of user reviews on shopping or opinion sites, in posts of blogs or customer feedbacks. This has created a surge of research in sentiment classification (or sentiment analysis), which aims to automatically determine the sentiment polarity (e.g., positive or negative) of user generated sentiment data (e.g., reviews, blogs).

Machine learning algorithms have been proved promising and widely used for sentiment classification [Pang et al., 2002; Pang and Lee, 2008; Liu, 2012; Zhou et al., 2014b; 2015]. Applications to many different domains have been presented, ranging from movie reviews [Pang et al., 2002] and congressional floor debates [Thomas et al., 2006] to product recommendations [Snyder and Barzilay, 2007; Blitzer et al., 2007].

These user generated sentiment data can span so many different domains that it is difficult to manually label training data for all of them. In real applications, users may use different vocabularies (or domain-specific words) to express sentiment in different domains. For example, in the Electronic domain the words "durable" and "light" are used to express positive sentiment, whereas "expensive" and "short battery" often indicate negative sentiment. On the other hand, in the Book domain the words "exciting" and "thriller" are used to express positive sentiment, whereas the words "boring" and "lengthy" usually express negative sentiment. In all these examples, the source domain and the target domain have different input feature spaces - we refer to this problem setting as Heterogeneous Input Features (HIF). As a result, a classifier trained on one domain might not perform well on a different domain because it fails to learn the sentiment of domain-specific words. Thus domain adaptation is highly desirable to reduce the gap between domains and manually labeling cost.

Domain adaptation also poses new challenges from the algorithm perspective since multiple domains seem to be totally uncorrected with each other if their examples are in different input features. Here our key observation is that in many real applications, there might exist some correspondence among certain input dimensions of different domains. In the example of domain adaptation for sentiment classification, some domain-specific words are linked via the same sentiment polarity. The correspondence across different input features provides an important connection among multiple domains. In this paper, such correspondence is represented by pivots, which consists of tuples of input dimensions from multiple domains bearing the same correspondence.

Inspired by the above observation, we propose a novel learning framework, called Linking Heterogeneous Input Features via Pivots via Joint Non-negative Matrix Factorization (PJNMF). PJNMF assumes that there exists a set of domain-specific features for each of the domain, and there also exists a set of pivot features for the source and target domains. In PJNMF, documents in each domain are represented as a term-document matrix. The term-document matrix is then approximated as the product of two matrices: one matrix represents the domain-specific features as well as the pivot features, the second matrix denotes the document representation based on the latent features. An objective function is defined to learn the mappings from the heterogeneous input features to a common space and the prediction model in this space. In this framework, to make full use of the pivot information, we enforce the input dimensions mapped to the same pivot be projected to the common space in a similar way. To demonstrate the effectiveness of the proposed approach, we conduct experiments on a benchmark composed of reviews of 4 types of Amazon products. Experimental results show that the proposed approach significantly outperforms several baselines, and achieves an accuracy which is competitive with best known method for sentiment classification adaptation.

The remainder of this paper is organized as follows. Section 2 introduces the related work. Section 3 describes our proposed linking heterogeneous input features via pivots for domain adaptation. Section 4 presents the experimental results. In section 5, we conclude with ideas for future research.

2 RelatedWork

Sentiment classification has gained widely interest in natural language processing (NLP) community, we point the readers to recent books [Pang and Lee, 2008; Liu, 2012] for an in-depth survey of literature on sentiment analysis. In this section, we briefly describe the related work of domain adaptation for sentiment classification.

In real applications, user generated sentiment data can span so many different domains that it is difficult to manually label training data for all of them. A classifier trained on one domain might not perform well on a different domain because it fails to learn the sentiment of unseen words. To address this problem, domain adaptation for sentiment classification has been widely studied in the literature. Blitzer et al. [2007] proposed a structural correspondence learning (SCL) algorithm to train a cross-domain sentiment classifier. SCL is motivated by a multi-task learning algorithm, alternating structural optimization (ASO), proposed by Ando and Zhang [2005]. Given labeled data from a source domain and unlabeled data from both source and target domains, SCL attempts to model the relationship between "pivot features" and "non-pivot features". Pan et al. [2010] proposed a spectral feature alignment (SFA) algorithm to align the domain-specific words from the source and target domains into meaningful clusters, with the help of domain-independent words as a bridge. In the way, the cluster can be used to reduce the gap between domainspecific words of two domains. In SCL and SFA. there is no constrain on the domain-specific words to prevent them from capturing the information from the pivot features. Neither is there a constrain that stops leakage of domain-specific words into the pivot features. In this paper, our PJNMF uses a regularization term on the pivots and domain-specific words, ensuring that the pivots capture only correspondence aspects and the domain-specific words capture only individual aspects. Besides, the formulation and optimization of PJNMF in this paper are different from that in [Blitzer et al., 2007; Pan et al., 2010].

We also note that our PJNMF is related to transfer common knowledge across domains via matrix factorization in [Li et al., 2009]. However, Li et al. [2009] explored the matrix factorization and knowledge transfer by optimizing the two objective functions separately, e.g., maximizing the empirical likelihood on the source and target domains, respectively. Actually, these two objective functions are complementary to each other and optimizing them simultaneously can make the solution smoother and further improve the accuracy on the target domain. Recently, Zhou et al. [2014a] also explored PJNMF for community question retrieval. On the contrary, this paper focuses on domain adaptation for sentiment classification, giving rise to the different task description and model formulation.

Finally, other studies also address domain adaptation for sentiment classification from different perspectives. He et al. [2011] employed a joint sentiment-topic model for crossdomain sentiment classification; Bollegala et al. [2011] used a sentiment sensitive thesaurus to perform cross-domain sentiment classification; Glorot et al. [2011] and Chen et al. [2012] employed a deep learning approach to perform domain adaptation for large-scale sentiment classification; Li et al. [2013] proposed an active learning algorithm for cross-domain sentiment classification. In contrast, our paper conducts domain adaptation for sentiment classification from a new perspective via pivots transfer under a constraint framework.

3 Linking Heterogeneous Input Features with Pivots

In this section, we propose the learning scheme for domain adaptation with pivots, followed by the optimization algorithm and convergence analysis.

3.1 Learning Scheme

Given two domains Xs and Xt, where Xs and Xt are referred to a source domain and a target domain, respectively. Suppose we have a set of labeled sentiment documents as well as some unlabeled documents in a source domain Xs with size ns, containing terms from a vocabulary V with size m. The documents in source domain Xs can be represented as a term-document matrix Xs = {x(s) 1 , · · · , x(s) ns } ∈ Rm×ns , where each element denotes the weight of the corresponding term, for example tf-idf used in this paper. The labels on sentiment documents can be described using a ns × 2 matrix Ys where Ys(i, 1) = 1 if the i-th document expresses positive sentiment, and Ys(i, 2) = 1 for negative sentiment [Li et al., 2009].

Similarly, suppose we have a set of unlabeled sentiment documents in a target domain Xt with size nt, containing terms from a vocabulary V with size m. The documents in target domain Xt can also be represented as a term-document matrix Xt = {x(t) 1 , · · · , x(t) nt } ∈ Rm×nt , where each element denotes a tf-idf weight of the corresponding term. The task of cross-domain sentiment classification is to learn a robust classifier to predict the polarity of unseen sentiment documents from Xt. Note that we only consider one source domain and one target domain in this paper. However, our proposed algorithm is a general framework and can be easily adapted to multi-domain problems.

Without loss of generality, let ¯Ud = [U0,Ud] ∈ Rm×(k0+kd) be the term-topic matrix corresponding to domain d, where k0 is the number of pivot topics, kd is the number of domain-specific topics corresponding to domain d, and d ∈ {s, t}. Term-topic matrix U0 can be represented as U0 = [u(0) 1 , · · · , u(0) k0 ] ∈ Rm×k0 , in which each column corresponds to a pivot topic. While the term-topic matrix Ud can be represented as Ud = [u(d) 1 , · · · , u(d) k ] ∈ Rm×kd . The total number of topics in domain d is k0 + kd. Let VT d = [v(d) 1 , · · · , v(d) nd ] ∈ Rnd×(k0+kd) be the documenttopic matrix corresponding to domain d, in which each column denotes the document representation in the topic space. We also denote VT d = [HTd ,LTd ], where Hd ∈ Rk0×nd and Ld ∈ Rkd×nd correspond to the coefficients of shared topics U0 and domain-specific topics Ud, respectively.

Given a sentiment document collection Xs in a source domain with unlabeled and labeled data, the document representation based on non-negative matrix factorization (NMF) [Lee and Seung, 2001] can be formulated as follows:

where ‖ · ‖2F is the Frobenius norm.

In a target domain, we transfer the pivot topics U0 from the source domain Xs to the target domain Xt as a bridge. Specially, given a set of unlabeled sentiment document collection Xt in a target domain, the sentiment classification problem based on non-negative matrix factorization can be formulated as follows:

Once obtaining the representation of documents from the two domains, a natural avenue is to integrating the two objective functions seamlessly into one unified framework. However, this direct solution has a crucial drawback in segregating the pivot and individual feature spaces: there is no constraint on the individual feature spaces to prevent them from capturing basis vectors from the pivot spaces. Neither is there a constraint that stops leakage of individual basis vectors into the pivot space. Of those two issues, the first is important when we are interested in the individual aspects of the two domains. While the second issue is more important when looking from the point of view of transfer learning. This is because when the pivot matrix U0 captures some topics or basis vectors corresponding to the individual aspect of one domain and used later for modeling the other domain, this leakage degrades performance.

To circumvent the above problems, we propose to add a regularization on the pivot and domain-specific feature spaces which can avoid both of the above problems. It not only ensures that Us and Ut capture only the individual basis vectors but also that U0 captures only the common basis vectors. With this regularization, our optimization cost function is to minimize the following form

where λs ≜ ‖Xs‖-2 F , λt ≜ ‖Xt‖-2 F , andR(U0,Us,Ut) is a regularization term used to penalize the "similarity" between feature spaces spanned by matrices U0, Us and Ut.

When seeking feature spaces which do not capture the similar basis vectors and be complementary to each other, one way to formulate them is by considering them as mutually orthogonal. Note for example that if the feature spaces spanned by matrices U0, Us, are mutually orthogonal, we have UT0 Us = 0. To impose this constraint, we choose to minimize the sum-of-squares of entries of the matrix UT0 Us, i.e., ‖UT0 Us‖2F which uniformly optimizes each entry of UT0 Us. With this choice, the regularization term of equation (3) is given by

where α, β and γ are the regularization parameters.

3.2 Optimization Algorithm

Note that the optimization problem in equation (3) is not convex in variables {U0,Us,Ut,Vs,Vt} together. However, when considering one variable at a time, the cost function turns out to be convex. For example, given {Us,Ut,Vs,Vt}, the cost function is a convex function w.r.t. U0. Therefore, although we cannot expect to get a global minimum of the above problem, we shall develop an algorithm which is not only simple and efficient but its convergence can also be guaranteed.

The equation (3) is a constrained optimization problem due to the nonnegative constraints on the factorization matrices, and can be solved using the Lagrange multiplier method. Let Au0 (i, j) be the Lagrangian multiplier for constraints U0(i, j) ≥ 0 and Au0 = [Au0 (i, j)], let Tr[·] denote the trace of a matrix. Similarly if Aus , Aut , Avs , Avt are the Lagrangian multiplier matrices for nonnegative constraints of matrices Us, Ut, Vs and Vt, then the above cost function in an unconstrained form (denoted by L) can be written as below

where D(U0,Us,Ut,Vs,Vt) is defined as

Optimize U0 given {Us,Ut,Vs,Vt}

The first derivative of the cost function L with respect to matrix U0 is given by

where X(r) s ≜ [U(r) 0 ,U(r) s ]H(r) s and X(r) t ≜ [U(r) 0 ,U(r) t ]H(r) t . Using Karush-Kuhn-Tucker (KKT) conditions Au0 (i, j)U0(i, j) = 0 with the expression of the gradient ∇L, for any stationary point, we get the following

which leads to the following update equation

where [·] [·] is element-wise division.

Optimize Us given {U0,Ut,Vs,Vt}

The first derivative of the cost function L with respect to matrix Us is given by

Similar as above, using KKT conditions Aus (i, j)Us(i, j) = 0 with the expression of the gradient ∇L, for any stationary point, we get the following update equation

Similarly, optimizing for Ut given {U0,Us,Vs,Vt}, we get the following update equation

Update equations for matrices Vs, Vt andWs, are similar to standard NMF and are given by

We note that multiplicative update rules given by equations (7)∼(10) are obtained by extending the updates of standard NMF [Lee and Seung, 2001]. There are alternative ways of optimizing the objective function L such as alternating least squares and the active set method [Kim and Park, 2008] or the projected gradients approach [Lin, 2007], which often have better convergence behavior. Nonetheless, the multiplicative updates derived in this paper have reasonably fast convergence behavior as shown empirically in the experiments. Besides, we also note that a good initialization of matrices U0, Us, Ut, Vs and Vt may lead to quicker convergence of the proposed algorithm. Several methods have been proposed for NMF to address this issue [Langville et al., 2006; Boutsidis and Gallopoulos, 2008]. However, it is difficult to use them for initializing matrix U0 and the corresponding coefficient matrix Vs and Vt. Other matrices such as Us and Ut also depend on U0 given the data. Therefore, we initialize these matrices by random nonnegative values.

With the optimization results of {U0,Ut}, a linear classifier is trained on the transformed labeled data of the source domain. Support Vector Machines (SVM) being known to perform well on sentiment classification [Pang et al., 2002], we use a linear SVM with squared hinge loss. This classifier is eventually tested on the target domain.

3.3 Convergence Analysis

Without loss of generality, we only show the convergence of multiplicative update given by equation (8). We first introduce the definition of the auxiliary function as follows.

Definition 1. F(X,X′ ) is an auxiliary function for L(X) if L(X) ≤ F(X, X′ ) and equality holds if and only if L(X) = F(X, X).

Lemma 1. [Lee and Seung, 2001] If F is an auxiliary function for L, L is non-increasing under the update

Lemma 2. Let L(U(r) s ) denote the sum of all terms in L that contain U(r) s , the following function is an auxiliary function for L(U(r) s )

Following the similar convergence analysis as shown above, we can prove the updating rules for the rest variables.

Theorem 1. The objective function L(U0,Us,Ut,Vs,Vt) is non-increasing under the alternating multiplicative update rules of equations (7)∼(10).

Proof. Since we are minimizing L(Us) using the auxiliary function F(Us,U(r) s ). Therefore, evaluating ∇F(Us, U(r) s ) = 0 and utilizing the results of Lemma 1 and Lemma 2, we get the following update equation

Noting that ∇L(U(r) s )

and substituting S(U(r) s ) from Lemma 2, we get the desired update of equation (8).

3.4 AlgorithmComplexity

In this section, we analyze the computational complexity of the learning algorithm described in equations (7)∼(10). Besides expressing the complexity of the algorithm using big O notation, we also count the number of arithmetic operations to provide more details about the run time. Computational complexity of learning matrix U0 is O(m× n × k0) per iteration where n = max(ns, nt). Similarly, for each iteration, learning matrices Us andUt takes O(m×ns×ks) and O(m× nt × kt), respectively. Learning matrices Vs and Vt takes O(m × ns × (k0 + ks)) and O(m × nt × (k0 + kt)) operations per iteration. Therefore, overall complexity of the algorithm, dominated by computation of matrices Vs and Vt, is O(m × n × k) where k = max(k0 + ks, k0 + kt). This is also the order of complexity of NMF algorithm [Lee and Seung, 2001] for each iteration. Note that, for implementation efficiency, when computing matrices such as ¯Us ¯UTs Vs, we should compute ¯Us ¯UTs first and then multiply it to matrix Vs. Similarly, when computing UsUTs U0, we should compute UTs U0 first and pre-multiply by Us. The main idea is to group the matrix multiplications by their inner-products first rather than their outer products.

4 Experiments

4.1 Data Set

Domain adaptation for sentiment classification has been widely studied in the NLP community. A large majority experiments are performed on the benchmark made of reviews of Amazon products gathered by Blitzer et al. [2007]. This data set contains 4 different domains: Book (B), DVDs (D), Electronics (E) and Kitchen (K). For simplicity and comparability, we follow the convention of [Blitzer et al., 2007; Pan et al., 2010; Glorot et al., 2011] and only consider the binary classification problem whether a review is positive (higher than 3 stars) or negative (3 stars or lower). There are 1000 positive and 1000 negative reviews for each domain, as well as approximately 4,000 unlabeled reviews (varying slightly between domains). The positive and negative reviews are also exactly balanced. Following the literature [Pan et al., 2010], we can construct 12 cross-domain sentiment classification tasks: DB, EB, KB, KE, DE, BE, BD, KD, ED, BK, DK, EK, where the word before corresponds with the source domain and the word after corresponds with the target domain. To be fair to other algorithms that we compare to, we use the raw bag-of-words unigram/bigram features as their input and pre-process with tf-idf. Table 2 presents the statistics of the data set.

4.2 ComparedMethods

As baseline, we train a linear SVM on the raw bag-of-words representation of the labeled source and test it on target. In the original paper regarding the benchmark data set, Blitzer et al. [2007] adapt Structural Correspondence Learning (SCL) for sentiment analysis. Li and Zong [2008] propose the Multilabel Consensus Training (MCT) approach which combines several base classifiers trained with SCL. Pan et al. [2010] first use a Spectral Feature Alignment (SFA) algorithm to align words from different source and target domains to help bridge the gap between them. Glorot et al. [2011] first employ stacked Denoising Auto-encoders (SDA) to extract meaningful representation for domain adaptation. Chen et al. [2011] propose a state-of-the-art domain adaptation algorithm called CODA, which is based on sample and feature selection, applied to tf-idf features. For SCL, SDA and CODA, we use implementations provided by the authors. For SFA and MCT, we re-implement them based on the original papers. The above methods serve as comparisons in our empirical evaluation. All hyper-parameters are set by 5-fold cross validation on the source training set 1 .

Table 1 shows the accuracy of classification results for all methods and for all source-target domain pairs. We can check that all compared methods achieve the similar performance with the results reported in the original papers. From Table 1, we can see that our proposed approach outperforms all other six comparison methods in general. The baseline performs poorly on all the 12 tasks, while the other five domain adaptation methods, SCL, MCT, SFA, SDA and CODA, consistently outperform the baseline method across all the 12 tasks, which demonstrates that the transferred knowledge from the source domain to the target domain is useful for sentiment classification. Nevertheless, the improvements achieved by these five methods over the baseline are much smaller than the proposed approach. Surprisingly, we note that the deep learning based method (SDA) does not achieve the satisfactory results with ours, the reason may be that unsupervised feature learning typically only model the syntactic context of words but ignore the sentiment of text. This is problematic for sentiment analysis as they usually map words with similar context but opposite sentiment polarity, such as good and bad, to neighboring word vectors [Tang et al., 2014]. We also conduct significance tests for our proposed approach and SDA using a McNemar paired test for labeling disagreements [Gillick and Cox, 1989]. In general, the average result on the 12 source-target domain pairs indicates that the difference between our proposed approach PJNMF and SDA is mildly significant with p < 0.08.

1 We keep the default value of some of the parameters in SCL and SFA, e.g., the number of stop-words removed and stemming parameters - as they were already tuned for this benchmark set by the authors.

4.3 Convergence Behavior

In subsection 3.3, we have shown that the multiplicative updates given by equations (7)∼(10) are convergent. Here, we empirically show the convergence behavior of PJNMF. Figure 1 shows the convergence curve of PJNMF on the training data set. From the figure, y-axis is the value of objective function and x-axis denotes the iteration number. We can see that the multiplicative updates for PJNMF converge very fast, usually within 200 iterations.

4.4 Further Analysis

In this subsection, we would like to see how similarity the two domains are from each other. Ben-David et al. [2007] showed the A-distance as a measure of how different between the two domains. They hypothesized that it should be difficult to discriminate between the source and target domains in order to have a good transfer between them. In practice, computing the exact A-distance is impossible and one has to compute a proxy. Similar to [Glorot et al., 2011], the proxy for the A-distance is then defined as 2(1 - 2ϵ), where ϵ is the generalization error of a linear SVM classifier trained on the binary classification problem to distinguish inputs between the two domains. Figure 2 presents the results for each pair of domains. Surprisingly, the distance is increased with the help of pivot features. We explain this effect through the fact that PJNMF can ensure that the pivots capture only correspondence aspects and the domain-specific words capture only individual aspects.

Figure 2: Proxy A-distance between domains of the Amazon benchmark for the 6 different paris.

5 Conclusion

This paper proposes a joint non-negative matrix factorization framework by linking heterogeneous input features with pivots for domain adaptation, where different domains have heterogeneous input spaces. This is achieved by learning the domain-specific information from different domains into unified topics, with the help of pivots across all domains. An objective function is defined to learn the mappings from the heterogeneous input features to a common space, and then construcct a single prediction model in this space. To demonstrate the effectiveness of the proposed approach, we conduct experiments on a benchmark composed of reviews of 4 types of Amazon products. Experimental results show that our proposed approach significantly outperforms the baseline method, and achieves an accuracy which is competitive with the state-of-the-art methods for sentiment classification adaptation. There are some ways in which this research could be continued. First, since each word has its sentiment polarity (e.g., positive, negative), a natural avenue for future research is to encode the domain-independent lexical prior knowledge into our framework. Second, we will try to investigate the scalability of the proposed approach on a larger industrialstrength data set of 22 domains [Glorot et al., 2011].

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 61303180 and No. 61272332), the Beijing Natural Science Foundation (No. 4144087), and the Major Project of National Social Science Found (No. 12&2D223), and the Fundamental Research Funds for the Central Universities (No. CCNU15ZD003). We thank the anonymous reviewers for their insightful comments.