Instance Selection and Instance Weighting for Cross-Domain Sentiment Classification via PU Learning

1 Introduction

In the field of natural language processing (NLP), methods for domain adaptation can be classified into two main categorizations: 1) labeling adaptation, which aims to learn a new feature representation or a new labeling function for the target domain; 2) instance adaptation, which learns the importance of labeled data in the source domain based on instance weighting.

Instance adaptation is particularly important for sentiment classification, since we can easily obtain a large collection of labeled data in the vast amount of Internet reviews. But maybe only some of them are beneficial for training a desired target-domain sentiment classifier. Therefore, it is important for us to identify the samples that are the most relevant to the target domain. Under this circumstance, instance adaptation is very necessary for training an effective classifier.

To our knowledge, however, most of the existing domain adaptation studies in sentiment classification are based on labeling adaptation, while the work of instance adaptation are very scarce. Indeed, there are some instance adaptation algorithms proposed by the machine learning community. But most of them are hard to be applied directly to NLP applications with discrete distributions and high dimensional feature space (such as sentiment classification).

In this work, we propose a novel approach, based on instance selection and instance weighting via PU learning, in the context that the labeled training data are domain-mixed 1 and large-size. PU learning is a collection of semi-supervised techniques for training a binary classifier on the positive set and the unlabeled set only. PU learning is used, in our approach, to learn a binary in-target-domain selector, which assigns an in-target-domain probability to each sample in the training set. Based on the in-target-domain probabilities, two models are proposed: 1) Instance Selection (PUIS), where the instances with higher in-target-domain probability are selected as training data; 2) Instance Weighting (PUIW), where we first calibrate the in-target-domain probability to an appropriate degree, and then use the calibrated probabilities as sampling weights for training an instance-weighted na·ve Bayes model, based on the principle of maximum weighted likelihood estimation.

Let us use an artificial example to illustrate our approach. In Figure 1, the red dots denote the target-domain unlabeled data, which are drawn from an unknown distribution. The blue crosses denote the training data, which are drawn from some other distributions. Here, "domain-mixed" means the red dots and blue crosses are partially overlapped, and "large-size" means the number of the blue training data is large. In domain adaptation, our aim is to estimate the distribution of the red-dot target domain, based on the blue-cross training data.

1 We refer to "domain-mixed" by assuming that the training data may contain some target-domain or target-domain-relevant samples, but we do no know where they are in the mixed training data.

Our method can be interpreted as follows: First, we use PU learning (where is the set of red dots, and is the set of blue crosses) to learn an in-target-domain selector and assign an in-target-domain probability (the value is denoted by the size of the cross) to each blue cross. The blue cross that is closer to the target domain will have a larger size. Second, the in-target-domain probabilities are calibrated to control the rate of size-increase of the blue crosses as the distance becomes small. Finally, the calibrated probabilities are used as sampling weights for training an instance-weighted model, based on the principle of maximum weighted likelihood estimation. Instances that have a larger size will influence the model more than those with a smaller one. In this manner, the gravity-center of the blue crosses will move toward the red dots, and the distribution of the training data will become more approximate to the target-domain distribution.

The approach is evaluated by a range of experiments. The experimental results prove the necessity and effectiveness of the approach, especially when the size of training data is large. Compared to PUIS, PUIW is more effective and stable. The results also indicate that our approach has a good property: the larger the Kullback-Leibler divergence (KLD) between the training and test data, the more effective our approach will be.

2 Related Work

2.1 Domain Adaptation

A survey of domain adaptation and transfer learning can be found in [Pan and Yang, 2010]. There are two main kinds of methods for domain adaptation 2 [Jiang and Zhai, 2007]: labeling adaptation and instance adaptation. We review them respectively.

1) Labeling adaptation. Daume III [2007] proposed an easy domain adaptation (EDA) method by duplicating the feature space of both the source and target data. The structural correspondence learning (SCL) model proposed by Blitzer et al. [2007] was the representative work of labeling adaptation. Pan proposed two domain adaptation approaches via transfer component analysis (TCA) [Pan et al., 2009] and spectral feature alignment (SFA) [Pan et al., 2010], respectively. [Xia and Zong, 2011] and [Samdani and Yih, 2011] at the same time proposed feature re-weighting based on ensemble learning, but the feature subsets are divided in different ways. Glorot et al. [2011] proposed a deep learning approach to address domain adaptation for large-scale sentiment classification. Duan et al. [2012] proposed a method based on augmented feature representations for heterogeneous domain adaptation.

2 There are still some other types of domain adaptation methods, such as parameter-based methods and semi-supervised-based methods. Due to space limitation, they are not reviewed.

2) Instance adaptation. In the field of machine learning, this problem is also termed "covariate shift" or "instance selection bias" [Zadrozny, 2004], where the key problem is "density ratio estimation (DRE)". Shimodaira [2000] used kernel density estimation, Dudik et al. [2005] used maximum entropy density estimation, and Huang et al.[2007] used kernel mean matching, to estimate the density ratio. The KLIEP algorithm proposed by Sugiyama et al. [2007] was one of the representative work, where the density ratio was estimated by minimizing the K-L divergence between the true and approximated distributions based on a linear model. Bickel et al. [2010] proposed an algorithm based on joint discriminative learning for modeling the covariate shift.

To our knowledge, most of the existing domain adaptation methods in NLP are based on labeling adaptation, while the work of instance adaptation that are particularly designed for NLP applications are very scarce. Recently, Axelrod et al. [2011] proposed a method based on a language model, to select parallel training data for machine translation.

In this work, we develop an instance adaptation method for cross-domain sentiment classification, based on in-target-domain selection via PU learning. The process of in-target-domain selection is similar to the work by Bickel et al. [2010], where the sampling weights are trained by a joint discriminative learning. Different from that, the sampling weights in our approach are provided by PU learning, rather than a complex joint-training. It leads to computational efficiency and can be easily applied to NLP even when the training size is large.

2.2 PU Learning

Liu et al. [2002] summarized several PU learning algorithms and performed a comprehensive evaluation. PU learning has the potential for many NLP applications, especially for the tasks related to distribution similarity. For example, Li et al. [2007] use the PU learning framework to identify unexpected instances in the test set which are different in distribution to the training set. Li et al. [2010] used PU learning for the problem of entity set expansion, where PU learning was compared with traditional distributional similarity and showed significant superiority.

The usage of PU learning in this work is similar to [Li et al., 2007], but in a reverse direction. They use PU learning to identify unexpected test instances, while we use it to identify the most useful training instances. To our knowledge, it is the first time that PU learning is used for instance selection and instance weighting in domain adaptation.

3 The Proposed Approach

3.1 PU Learning for In-target-domain Selection

PU learning is stated as follows [Liu et al. 2002]: Given a set of positive samples of a particular class, and a set of unlabeled samples that contains hidden positive and negative samples, a classifier is built using and for classifying the data in binary decisions.

In our approach, PU learning is employed to build a binary in-target-domain selector. The class labels are positive (in-target-domain) and negative (not-in-target-domain). 3 The target-domain test set is referred to as the positive set , and the domain-mixed training set is referred to as the unlabeled set . Our aim is to learn a binary classifier based on and , and identify the most positive (i.e., target-domain-likely) samples from the domain-mixed training set (i.e., set). There are several PU learning algorithms. In this work, the S-EM algorithm proposed in [Liu et al., 2003] is used to learn the in-target-domain selector. The algorithm is presented in Figure 2.

Algorithm S-EM( , , , ) ; % Step 1 = Sample( , %); Assign each instance in the class label ; Assign each instance in the class label ; Build a NB classifier using and ; Classify each using ; for each if ; ; Assign each instance in the class label ; % Step-2 Assign each instance in the class label ; Learn an EM classifier iteratively on , and ; for each % Final prediction Predict using ; if Output as a positive (in-target-domain) sample; else Output as a negative (not-in-target-domain) sample;

S-EM contains two main steps. In Step 1, a small set of samples is randomly sampled from the positive set . The positive samples in are called "spies". The dataset of and are labeled as positive and negative, respectively. A naive Bayes (NB) classifier is then applied to predict each instance and identify a reliable negative sample set based on a threshold . In Step 2, given the positive set , the reliable negative set and the remaining unlabeled set , an Expectation Maximization (EM) algorithm is used for semi-supervised learning, to build a in-target-domain selector that iteratively predict the samples in . Finally, the positive-labeled subset is identified as the in-target-domain part. Each training sample will receive an in-target-domain probability .

3 The positive and negative labels in PU learning should be distinguished from the sentiment positive and negative labels. In PU learning, positive means in-target-domain; negative means not-in-target-domain.

Based on the in-target-domain probabilities, we propose two models for domain adaptation:

1. Instance Selection (PUIS). The instances with higher in-target-domain probability are selected as training data;
2. Instance Weighting (PUIW). In PUIW, we assume that the target-domain test data are generated by the following In-target-domain Selection process: a target-domain instance is drawn by first sampling from the distribution of the training set , and then a in-target-domain indicator variable decides whether is moved into the target domain ( ) or not ( ). On this basis, the target-domain distribution could be estimated as:

where the in-target-domain probabilities will be used as weights for instance weighting.

In the following sections, we introduce PUIW in detail. We first calibrate the in-target-domain probability to an appropriate degree (Section 3.2), and then use the calibrated probabilities as sampling weights for training an instance-weighted na·ve Bayes model (Section 3.4), according to the principle of maximum weighted likelihood estimation (Section 3.3).

3.2 In-target-domain Probability Calibration

In the S-EM algorithm, each training sample is assigned with an in-target-domain probability . However, S-EM tends to generate a probability either arbitrarily close to 0 or arbitrarily close to 1, due to the naive Bayes assumption. It is important to obtain well-calibrated in-target-domain probabilities for an accurate instance weighting.

It is known that the posterior probability output can also be written in the form of a sigmoid function of the log-odds output , where is the log-odds. We calibrate the in-target-domain probability by multiplying a calibration parameter ( ) to the log-odds:

where is used to prevent the in-target-domain probabilities from being too arbitrary and make them more smooth.

Replacing the in-target-domain probability in Equation (1) with the calibrated one, we obtain the approximated target-domain distribution:

Note that Equation (1) is a special case of Equation (3) when .

3.3 PUIW for Domain Adaptation

In this section, we use the maximum likelihood estimation (MLE) principle to derive the PUIW framework for domain adaptation.

Assume that and are the feature space and label space respectively, and is the joint probability of and . In cross-domain classification, our aim is to find the best parameter that maximizes the (expected) likelihood of the data drawn from the target domain:

We use (Equation 3) as an estimation to the real target-domain distribution, and assume . Then, the MLE problem could be written as:

Since the target-domain labeled data are not available, we maximize the (empirical) likelihood of the source-domain training data instead. It turns out to be a weighted version of maximum likelihood estimation (MWLE):

where is the sampling weight (calibrated in-target-domain probability) of the training instance , and is the size of training data.

3.4 Instance-weighted Na·ve Bayes Model

Note that PUIW is a framework that could be integrated with different classification algorithms. In this work, we employ the naive Bayes algorithm, and propose an instance-weighted na·ve Bayes (WNB) model. 4

Parameters of traditional NB are estimated by the MLE principle, which turns out to be the ratio of empirical counts. In the context of WNB, the parameters should be estimated by the MWLE principle (Equation 4), which results in a weighted version of the ratio of empirical counts:

4 Here, NB is used for sentiment classification. It should be distinguished from the usage of NB in PU learning (S-EM).

where is the identification function, is short for the calibrated in-target-domain probability, is the count of word appears in document , and is the size of vocabulary. It is reasonable that the counts of features in target-domain-relevant samples will contribute more to the model than those irrelevant samples.

4 Experimental Study

4.1 Experimental Settings and Datasets

In order to evaluate our approach extensively, we conduct the experiments under two different settings: 1) Experiments with a normal-size training set; 2) Experiments with a large-size training set. The results are reported in Section 4.2 and 4.3, respectively.

In Setting 1, the Movie review dataset 5 is used as the source domain data, and each domain of the Multi-domain sentiment datasets 6 (Book, DVD, Electronics, and Kitchen) is used as the target domain. We artificially construct a domain-mixed training data by randomly choosing 200 labeled data from the target domain, and mixing them with 2000 source-domain labeled data. The remaining data in the target domain are used as test set. Unigrams and Bigrams with term frequency no less than 4 are used as features. We repeat the experiments for 10 times, and report the average results.

In Setting 2, we extract one large domain (Video) from the unprocessed part of the Multi-domain sentiment datasets. Reviews of 1 or 2 stars are marked as negative, and reviews of 4 or 5 stars are marked as positive. It finally contains 10,000 class-balanced training samples. Reviews from each of the other 12 domains are used as the target-domain test data. Unigrams with term frequency on less than 5 are used as features. The experiments are also repeated for 10 times and the average results are reported.

4.2 Experiments with A Normal-size Training Set

We first report the results using a normal-size training set. In Figure 3, we draw the accuracy curve of three different methods: 1) For PUIS, the bottom x-axis (which denotes the number of selected samples) is used. All training samples are sorted in a descending order according to the in-target-domain probabilities, and we report the system performance trained with an increasing number of selected samples; 2) For Random Selection (denoted by "Random"), we report the performance of the same number of randomly selected samples; 3) For PUIW, the top x-axis (which denotes the value of calibration parameter ) is used. In Table 1, we explicitly compare the best results obtained by different methods, where "All" denotes the results using all training samples. The K-L divergence (KLD) between the training and test data is also reported for each task. The results of PUIW are in terms of that obtained by WNB, and the results of PUIS are in terms of that obtained by NB trained with selected samples.

5 http://www.cs.cornell.edu/people/pabo/movie-review-data/

6 http://www.cs.jhu.edu/~mdredze/datasets/sentiment/

It should be noticed that we have not compared our model with traditional labeling adaptation approaches (such as SCL) due to different task settings. The focus of this paper is instance adaptation for sentiment classification. Our method do not rely on any additional target domain data, while the labeling adaptation methods need either a small amount of labeled data or a large amount of unlabeled data in the target domain for help.

We observe the results in the following aspects:

1. Random Selection. In all tasks, with the increase of training samples, the performance of Random Selection is gradually improved. This agrees with our general knowledge that more training data will improve the machine learning performance.
2. PUIS. Using the same number of training data, PUIS is significantly better than Random Selection. It indicates that PU learning is effective at selecting the most useful training samples. The accuracy increase is significant, especially in high-KLD tasks. For example, in Movie → {Electronics and Kitchen}, the improvements are 2.90 and 3.38 percentages, respectively. When the KLD is relatively low, however, the effect of PUIS are limited. The average increase is 1.58 percentages.
3. PUIW. Compared to PUIS, the effect of PUIW is more significant and robust. Across four tasks, the improvements are 1.79, 1.96, 5.25 and 6.78 (in average 3.94) percentages, respectively. It is reasonable since the calibrated in-target-domain probabilities used as sampling weight are more appropriate than the usage of 0/1 weight in instance selection.

4.3 Experiments with A Large-size Training Set

In this section, we report the experimental results using a large-size training set, which contains 10,000 labeled Video reviews. The reviews from each of the other 12 domains are used as test data respectively. In Figure 4, we draw the accuracy curve of Random Selection, PUIS and PUIW. Due to the space limitation, we only present four of them. In Table 2, we report the best results obtained by different methods as well as the KLD across all 12 tasks.

We observe the results the same way as in Section 4.2. But this time we lay the emphasis on the results that are special for large-size training data

1. The effect of adding more training samples. It can be observed in Random Selection that, when the size of training samples is relatively small (<2000), the accuracy increases significantly as the training size increases. But when the size becomes larger (>3000), the improvement by adding more training data is very slight. It indicates that when the size of training data is already large, adding more training samples will not cause significant improvements.
2. The necessity of PUIS/PUIW. Compared to the results in Section 4.2, the effects of PUIS and PUIW in this case are more significant. The average of increase of PUIS and PUIW are 3.32 and 4.48 percentages, respectively. It is worth noting that in many tasks, only about 10% of selected training samples could result in better performance than that trained with all samples. It indicates that instance adaptation is very necessary when the size of training data is large.
3. The stability of PUIW. In addition to its remarkable performance, it also can be observed that the accuracy curve of PUIW is unimodal and quite stable. While it is not easy to determine the best number of selected instances in PUIS, most of the best accuracy in PUIW are obtained when locates at the area around 0.1. It suggests another advantage of PUIW: the stability in model selection.

4.3 Further Discussion

We finally investigate the relation between K-L divergence (KLD) and the accuracy improvements of our approach. It is known that KLD measures the difference of two distributions. In our tasks, KLD represents the distributional change from the training set to test set. Hence, when KLD is small, the space of improvements in domain adaptation is limited; when KLD increases, the space of improvements also becomes larger.

In Figure 5, we draw the relation of KLD and the accuracy increase gained by PUIW. It can be observed that, KLD and accuracy increase are in a linear relation generally, except for few aberrant points. It indicates that our approach has a good property: the larger the KLD of the training and test data is, the more effective our approach will be.

5 Conclusions

In this paper, we propose a novel approach for cross-domain sentiment classification, based on instance selection and instance weighting via PU learning. PU learning is first used to learn an in-target-domain selector, and assign an in-target-domain probability to each sample in the training set. Based on the in-target-domain probabilities, two models namely PUIS and PUIW, are developed. The experimental results prove the necessity and effectiveness of the approach, especially when the size of training data is large. The results also indicate another good property of our approach: the larger the K-L divergence between the training and test data is, the more effective our approach will be.

Shortcomings of this work contain two aspects: 1) Explicit model selection, such as the determination of the number of selected samples and the value of the calibration parameter , are not involved; 2) It lacks the consideration for labeling adaptation (we simply assume in Section 3.3) in instance adaptation. Both of them are very important issues, and we will perform some related investigation in our future work.

Acknowledgments

The research work is supported by the Jiangsu Provincial Natural Science Foundation of China under Grant No. BK2012396, the Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20123219120025, the Open Project Program of the National Laboratory of Pattern Recognition (NLPR). The work is also partially supported by the Hi-Tech Research and Development Program (863 Program) of China under Grant No. 2012AA011102 and 2012AA011101, and the National Science Fund for Distinguished Young Scholars under Grant No. 61125305.