Instance Weighting with Applications to Cross-domain Text Classification via Trading off Sample Selection Bias and Variance

1 Introduction

Instance weighting (also called importance sampling), a generalization of statistical bias correction techniques, can potentially correct the sample selection bias in the labeled training data. It is therefore considered as an important type of domain adaptation method, that improves the adaptive performance by re-weighting the source-domain training samples to approximate the target-domain distribution.

In the field of machine learning, instance weighting has been studied extensively under the concept of sample selection bias or covariate shift. It has been proven that the sample selection bias can be canceled by using the density ratio to re-weight the training samples [Shimodaira, 2000; Zadrozny, 2004]. Therefore, density ratio estimation (DRE) becomes the key problem in correcting sample selection bias. A series of methods were proposed in the literature to solve the DRE problem [Shimodaira, 2000; Huang et al., 2006; Sugiyama et al., 2008; Tsuboi et al., 2009; Kanamori et al., 2009]. The core idea is to learn the instance weights by minimizing the gap between the re-weighted source-domain distribution and the target-domain true distribution.

Instance weighting for domain adaptation has been widely discussed in the field of NLP. Most of the methods first learn the weight for each training instance based on sample bias correction, and then train an instance-weighted classifier for cross-domain classification. Although these methods were effective to estimate the density ratio, most of them do not perform well when applied to NLP domain adaptation tasks. There were even some negative reports in the literature toward using instance weighting for domain adaptation in NLP. For example, [Plank et al., 2014] presented a negative result on instance weighting for cross-domain POS tagging. They stated that "the publication bias toward reporting positive results makes it hard to say whether researchers have tried." Due to the difficulty in using instance weighting, instance selection by setting the weight of all selected instances to 1 and 0 otherwise, is used instead in real practice for instance-based domain adaptation [Jiang and Zhai, 2007; Axelrod et al., 2011; Xia et al., 2013].

Till now, the causes to the failure and inefficiency of instance weighting for domain adaptation still remained unclear in the literature, and we have not seen studies that explicitly discussed this problem before.

In this work, we find that sample selection bias is actually not the only way the training data affect the domain adaptation performance. In addition to that, there is another important factor which we call "sample selection variance". However, most of the previous instance weighting approaches only aimed at correcting the sample selection bias, while ignored the influence of sample selection variance in domain adaptation. We find that as a result of correcting selection bias, the traditional instance weighting algorithms tend to make a small number of samples have much higher weights than the rest, which increases the risk of having a high sample selection variance, and it will accordingly cause poor domain adaptation performance.

In machine learning, the bias-variance tradeoff is the problem of simultaneously minimizing two sources of error that prevent supervised learning algorithms from generalizing beyond their training set. This tradeoff applies to all forms of supervised learning, including instance weighting for domain adaptation.

Based on the aforementioned findings, we propose a new instance weighting framework, by taking both sample selection bias and sample selection variance into consideration for domain adaptation. We evaluate our approach on two NLP domain adaptation tasks including cross-domain sentiment classification and personalized spam filtering. We compare our approach with the state-of-the-art instance weighting algorithms. The experimental results clearly confirm our conjecture on the inefficiency of previous instance weighting methods and strongly prove our approach's effectiveness and stability for domain adaptation.

The main contributions of this paper are as follows.

• To our knowledge, it is the first work that explicitly discusses the shortcomings of only correcting sample selection bias, and introduces the concept of sample selection variance as well as the bias-variance dilemma in the settings of instance weighting for domain adaptation;
• This work provides three ways of limiting the sample selection variance, and proposes a new framework that trades off sample selection bias and variance in instance weighting. It makes instance weighting more practical for domain adaptation tasks in NLP;
• In comparison with the previous instance weighting methods, the proposed approach has significant advantages in domain adaptive performance, optimization efficiency and parameter stability.

2 RelatedWork

Domain adaptation methods include feature-based adaptation and instance-based adaptation, etc [Jiang, 2008; Pan and Yang, 2010]. In this work, we focus on instance-based adaptation, which performs domain adaptation by instance weighting on the source-domain labeled training data.

In the field of machine learning, instance weighting is normally known as sample selection bias or covariate shift. This concept was first introduced in the field of econometrics by [Heckman, 1979], and brought into the field of machine learning by [Zadrozny, 2004]. It has been proven that the sample selection bias can be canceled by using the density ratio to re-weight the likelihood terms [Shimodaira, 2000; Zadrozny, 2004]. Hence, the key problem becomes density ratio estimation (DRE). A range of density estimation methods have been proposed to solve the DER problem. For example, kernel density estimation, maximum entropy density estimation and kernel mean matching, were used in [Shimodaira, 2000], [Dud´ık et al., 2005] and [Huang et al., 2006], respectively.

[Sugiyama et al., 2008] proposed a K-L importance estimation procedure (KLIEP) to directly estimate the density ratio under a linear assumption. The instance weights were learned by minimizing the K-L divergence between the reweighted source distribution and the target distribution, based on a projection descent algorithm. The least square importance fitting (LSIF) and unconstrained LSIF (uLSIF) were further proposed by [Kanamori et al., 2009]. [Tsuboi et al.,

2009] extended KLIEP by employing a log-linear model instead of the linear model, and made KLIEP feasible in largescale test data set. [Xia et al., 2014] proposed a logistic approximation instance adaptation model that performed instance adaptation more effectively than KLIEP. [Wen et al., 2015] used the Frank-Wolfe algorithm to solve the projected gradient optimization in KMM and KLIEP. Since FrankWolfe is projection-free, its time complexity is in general smaller than KMM and KILEP.

In addition to the general approaches in machine learning, existing work has also proposed methods specifically designed for NLP tasks. For example, [Jiang and Zhai, 2007] first used instance weighting to select a subset of the source data for domain adaptation. [Axelrod et al., 2011] proposed a pseudo in-domain data selection method to select sourcedomain training samples based on language model for machine translation. [Xia et al., 2013] proposed an instance selection and instance weighting approach via PU learning for domain adaptation in sentiment classification.

In comparison with the generally positive results in machine learning, the reports of instance weighting on NLP domain adaptation tasks tend to be negative. For example, it seems that the instance selection technique performed better and more stably than instance weighting [Jiang and Zhai, 2007; Xia et al., 2013]. [Plank et al., 2014] presented a negative results of using instance weighting for domain adaptation in POS tagging.

The aforementioned methods in both machine learning and NLP only aimed at correcting sample selection bias. However, sample selection bias is not the only way the training data are biased. They ignored the influence of sample selection variance when applying instance weighting to domain adaptation. By contrast, our approach takes both factors into consideration in instance weighting.

3 Preliminaries

3.1 InstanceWeight Estimation by Correcting Sample Selection Bias

Given the source-domain distribution ps(x) and the targetdomain distribution pt(x), it has been proven that the sample selection bias can be corrected by using density ratio (DRE) w(x) = pt(x) ps(x) as the weights for instance weighting [Shimodaira, 2000; Zadrozny, 2004]. A range of density estimation methods have been proposed to solve the DRE problem.

For example, the KMMmethod [Huang et al., 2006] tries to match the mean elements in a kernel feature space Φ by solving

where H denotes the reproducing kernel Hilbert space (RKHS). Ns and Nt are the number of samples in the sourcedomain training set and the target-domain test set, respectively.

The KLIEP algorithm [Sugiyama et al., 2008] assumes the density ratio is a linear model

and determine the parameters by minimizing the KullbackLeibler divergence between the target-domain true distribution pt(x) and the re-weighted source-domain distribution qs(x) = w(x)ps(x):

which finally results in an equality-constrained optimization.

We adopt the In-target-domain Logistic Approximation (ILA) algorithm [Xia et al., 2014] as the basis of this work. In ILA, the density ratio was defined as a normalized logistic function:

where α is a normalization factor. Due to the constraint qs(x) sum up to one, α can be represented by a function of β:

and the equality-constrained K-L minimization in Equation (3) can be converted to a unconstrained optimization:

3.2 Instance-weighted Classification for Domain Adaptation

Once the instance weight w(x) have been estimated, the next step is then to build an instance weighted classifier for domain adaptation.

Let θ denote the parameters of the classification model. The goal is then to find the best parameter θ∗ that maximizes the likelihood of the data drawn from the target domain

Since there is not labeled data in the target domain, we maximize the likelihood of the data drawn from the source domain

by assuming that pt(x) = w(x)ps(x) and pt(y|x) = ps(y|x). This results an instance-weighted classification.

In short, the process of instance weighting for domain adaptation is a pipeline of two steps:

• Step 1 (density ratio estimation, DRE): Using density ratio estimation methods to learn the instance weights;
• Step 2 (instance-weighted classification, IWC): Based on the instance weights to learn an instance-weighted classifier.

4 Our Approach

4.1 Why Only Correcting Sample Selection Bias is not Enough?

In machine learning, there are three types of prediction error: bias, variance, and irreducible noise. According to biasvariance decomposition [Geman et al., 1992], the expected error on an unseen example x can be decomposed as follows

The bias is an error from erroneous assumptions in the learning algorithm; the variance is an error from sensitivity to small fluctuations in the training set. Ideally, one wants to choose a model that both accurately capture the regularities in its training data, but also generalizes well to unseen data. Unfortunately, it is typically impossible to do both simultaneously. High-variance learning methods may be able to represent their training set well but are at risk of overfitting to noisy or unrepresentative training data. In contrast, algorithms with high bias typically produce simpler models that don't tend to overfit but may underfit their training data, failing to capture important regularities.

The bias-variance tradeoff applies to all supervised learning, including both steps summarized in Section 3.2. To trade off the bias and variances in Step 2, people normally added a L2 penalty to the objective function in Equation (8). And in Step 1, the sample selection bias can be corrected by using density ratio as the instance weight. However, the variance in Step 1 was normally ignored in previous instance weighting approaches. We name the bias and variance in Step 1 as Sample Selection Bias and Sample Selection Variance, respectively.

Given a training instance x, the instance weight w(x) = pt(x) ps(x) has roughly three situations:

• If pt(x) is much higher than ps(x), w(x) will be very large;
• If pt(x) is much lower than ps(x), w(x) will be very small;
• If the difference of pt(x) and ps(x) is not big, w(x) will be moderate.

In NLP, the multinomial distribution is widely used to model text. The probability of a document p(x) is normally calculated in terms of the product of each term's probability: p(x) = ∏|x| i=1 p(ti), and is apt to be arbitrarily close to 1 or 0. As a result, the density ratio might be very large (e.g., pt(x) = 0.999, ps(x) = 0.002, w(x) = 0.999 0.002 = 499.5), or very small (e.g., pt(x) = 0.002, ps(x) = 0.999, w(x) = 0.002 0.999 = 0.002). That is to say, although the sample selection bias can be corrected by using density ratio as the instance weight, the value of the instance weights may vary widely.

Hence, the Bias-Variance Dilemma in Instance Weighting for Domain Adaptation can be summarized as follows:

• To reduce the sample selection bias in Step 1, the density ratio needs to be used as the instance weight which may vary widely and accordingly cause poor classification performance in Step 2 due to high variance;
• To reduce the sample selection variance in Step 1, the more uniform instance weights are, the better. This will increase the sample selection bias and finally result in a domain non-adapted classifier in Step 2.

Most of the previous instance weighting approaches only sought correcting the sample selection bias while ignore reducing the sample selection variance. We infer that it is the most important reason of their failure in instance-based domain adaptation.

Figure 1 reports a failed result of only correcting sample selection bias on the "movie→book" cross-domain sentiment classification task (see Section 5.1 in detail). As can be seen, directly reducing sample selection bias causes a rapid growth of the instance weight variance. It consequently weakens the generalization ability in instance weighted classification, and finally leads to poor domain adaptation performance. Therefore, a reasonable instance weighting algorithm should trade off sample selection bias and variance.

4.2 Trading off Sample Selection Bias and Variance

Although Section 3.1 can correct the sample selection bias, it tends to increase the sample selection variance, and finally reduce the generalization performance. A simple way to limit the sample selection variance is to protect the instance weight from varying too much.

To this end, we develop the following three kinds of penalty functions, as an extension to the MSD cost function, to reduce sample selection bias.

(1) Limiting the Maximum Instance Weight (MIW)

where wmax(x) and xmax respectively denote the maximum weight and the corresponding instance. δ(·) denotes the sigmoid function.

(2) Limiting the Variance of Instance Weights (VIW)

where w(xi) denotes the weight of xi, and ¯w = 1 Ns ∑j w(xj) represents the average weight of all training instances.

(3) Limiting the Top-ranked Instance Weights (TIW)

where p denotes the percentage of top-ranked instance weights we want to limit, and [·] denotes the integer part.

We further have the following proposition that MIW and VIW are special cases of TIW.

Proposition 1. TIW equals to MIW when p = 1 Ns , and equals to VIW when p = 1.

Proof:

Firstly, by setting p = 1 Ns in Equation (12), we get Equation (10) directly.

Secondly, according to Equations (4) and (5), we have

and we can therefore re-write the VIW penalty as follows:

which is equal to JTIW when p = 1.

Finally, we add the penalty term to the MSD cost function in Equation (6) for a joint optimization:

where λ is a tradeoff parameter. Since the cost function is unconstrained, we can use either gradient descent or L-BFGS for optimization. In each iteration, the indices of the optimal top-ranked instance weights were computed according to the results at iteration (t - 1). After that, we update the parameters at iteration (t). It is reasonable since we just need to penalize the (previously) top-weighted instances.

5 Experiments

5.1 Experimental Settings and Datasets

We evaluate our approach on the following two tasks.

• Cross-domain sentiment classification. The Movie review dataset 1 is used as the source domain, and each domain of Multi-domain sentiment dataset 2 (Book, DVD, Electronics, and Kitchen) serves as the target domain. "A→B" denotes the task where A is the source domain and B is the target domain.
• Cross-domain personalized spam filtering. The dataset comes from the ECML/PKDD 2006 discovery challenge 3 . The goal is to adapt a spam filter trained on a common pool of 4000 labeled emails to three individual users' personal inboxes (u00, u01, u02), each containing 2500 emails.

In this work, we used the instance-weighted na¨ıve Bayes model for cross-domain text classification. Unigrams are used as features in instance weight learning. Both unigrams and bigrams with term frequency no less than 4 are used as features for instance weighted classification. The results are reported in terms of the average of 10 random repeats.

5.2 The Performance of InstanceWeighting for Domain Adaptation

In this paper we focus on instance weighting for domain adaptation and have not compared our approach with the feature-based domain adaptation algorithms such as SCL [Blitzer et al., 2007] and TCA [Pan et al., 2011]. We implement the following eight instance weighting systems for comparison.

• No-Adapt (the standard machine learning method without adaptation);
• KMM (kernel mean matching) [Huang et al., 2006];
• KLIEP (Kullback-Leibler importance estimation procedure) [Sugiyama et al., 2008];
• uLSIF (unconstrained least-squares importance fitting) [Kanamori et al., 2009];
• DALR (domain adaptive logistic regression) [Jiang and Zhai, 2007];
• PUIS (instance selection via PU learning [Xia et al., 2013];
• PUIW (instance weighting via PU learning) [Xia et al., 2013];
• FW (Frank-Wolf algorithm for correcting covariate shift) [Wen et al., 2015].

In our approach, the tradeoff parameter λ is set to be 0.01. The percentage parameter p is set as 5% in TIW. We use the L-BFGS algorithm to optimize the parameters, and set the maximum iterations steps as 20. The paired t-test is used for the significance testing.

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

2 https://www.cs.jhu.edu/ mdredze/datasets/sentiment/

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

In Table 1, we report the domain adaptation performance of nine systems on two tasks. It can be seen that most of the instance weighting approaches outperform No-Adapt. But it is somehow surprising that KMM almost fails in domain adaptation. uLSIF performs significantly better than KLIEP, but the performance is not stable across different datasets. PUIW has a similar performance to uLSIF. Their performance is better than PUIS and DALR in sentiment classification but worse in personalized spam filtering. FW, as a modification to KLIEP, performs slightly better than the latter. Our approach obtains generally the best performance across different settings. The improvements are stable and significant according to the paired t-test.

5.3 The Effect of Trading off Sample Selection Bias and Variance

In Figure 1, it is already shown that when we only correct sample selection bias, the decrease of the cost function does not necessarily increase the cross-domain classification performance. For comparison, in Figure 2 we display the results of trading off sample selection bias and variance. It can be seen that, due to the penalty term that limits the sample selection variance, the instance weight variance and maximum instance weight have been controlled. Consequently, the domain adaptation accuracy increases gradually as the cost function decreases.

In Table 2, we further compare the performances of using different ways to limit the sample selection variance. The results are obtained with L-BFGS, except for Early Stopping which is based on gradient descent. First, it can be seen that only correcting the sample selection bias without considering the variance fails in domain adaptation. It confirms again that limiting sample selection bias is of great necessity. Second, early stopping may be a choice to prevent the sample selection variance from being too large. But it is infeasible in L-BFGS due to the fast convergence speed. The difficulty in determining "when to stop" also makes Early Stopping less efficient in practice. Finally, the three ways to limit sample selection variance (MIW, VIW, TIW) perform significantly better than either ignoring the variance or using Early Stopping to correct it.

5.4 Tuning the Percentage Parameter p in TIW

It has been proven in Section 4.2 that MIW and VIW are special cases of TIW. In Figure 3, we display the domain adaptation accuracy curve by tuning p in TIW on the M→K task. TIW equals to VIW when p = 1, and MIW when p = 1 Ns . We can find the performance is quite stable. TIW can obtain the best performance when p is at [1%, 10%]. In this work, p is set as 5%.

5.5 Tuning the Tradeoff Parameter λ

We further discuss the sensitivity of the tradeoff parameter λ in Equation (14). Figure 4 presents the corresponding results via tuning λ on cross-domain sentiment classification tasks. When λ = 0, it becomes the MSD cost only; when λ = 1, it only has the sample selection variance regularizer. Both cases are not effective. It again proves the necessity to correct sample selection bias and variance together. The best performance can be obtained when λ is located at [0.005, 0.02]. It suggests that the MSD and TIW have distinct strength, and an appropriate combination of them is reasonable for domain adaptation.

6 Conclusions

Instance weighting is one kind of domain adaptation method due to its capacity of correcting the bias in the labeled training data. However, in practice the instance weighting methods often fail to achieve good domain adaptation performance in many NLP tasks. In this work, we conduct in-depth discussion on such failure and point out there are two kinds of important factors (i.e., sample selection bias and sample selection variance) in domain adaptation, and only correcting sample selection bias is not enough. On this basis, we propose a new instance weighting framework that jointly limits the sample selection bias and sample selection variance. We evaluate our approach on two NLP domain adaptation tasks and compare it with eight strong instance weighting systems. The experimental results confirm our conjecture and prove our approach's effectiveness and stability in instance weighting methods for domain adaptation.

Although this work can make instance weighting more stable for domain adaptation, a major limitation is that it should be based on condition that supports of features spaces between domains are similar. Instance-based domain adaptation only takes charge of the marginal distribution's transfer ps(x) → pt(x), but is unable to model the discriminative function's transfer ps(y|x) → pt(y|x). Another limitation is that the framework of instance-based domain adaptation is a pipeline of two steps where instance weight learning and cross-domain classification are separated. Therefore, a instance/feature joint end-to-end domain adaptation learning framework under neural networks might be a promising direction for future work.

Acknowledgments

The work was supported by the Natural Science Foundation of China (No. 61672288), and the Natural Science Foundation of Jiangsu Province for Excellent Young Scholars (No. BK20160085).