Bi-Weighting Domain Adaptation for Cross-Language Text Classification

1 Introduction

Over the past few decades, a considerable number of studies have been made in data mining and machine learning. However, many machine learning methods work well only under the case where the training and test data are drawn from the same feature space and the same distribution. A few attempts have been made for leaning under different distributions. When the distribution changes, it could be costly in terms of time and human efforts to re-collect the needed training data and rebuild the models. As a result, transfer learning has been proposed to address this problem.

Recently, transfer learning was found to be useful in many real-world applications. One important application is web mining, where the goal is to classify a given web document into several predefined categories. If the training documents and the test documents are in the same distribution, we can use the traditional machine learning methods to solve it. However, in the real world, this assumption cannot always be satisfied. In reality, there are plenty of such resources in English since it has the largest population in the Internet world, which is not true in many other languages. From the statistics in ODP 1 , it has sorted English web pages up to 1,429,760. However the number of web pages in other languages are much smaller (e.g. 13,293 classified Chinese web pages and 189,323 sorted Japanese web pages). It is well known that, classification requires a large number of labeled training data. Generally, the more labeled training data we get, the better the classification accuracy is. Fortunately, there exist many Web pages in English with class labels. Thus we should consider how to make use of the information got from the Web pages in English to classify the Web pages in other languages. This problem is called cross-language text classification, which we address in this paper. In order to utilize Web pages in English to classify Web pages in other languages, we can use a translation tool to translate the target data sets into English language. In this way, a classifier trained on English Web pages can be applied. Unfortunately, this directly application of this method may lead to some serious problems due to the following reasons:

∗Corresponding author

• First, due to the difference in language and culture, there exists a word drift. This means that a word which frequently appears in English Web pages may hardly appear in other languages Web pages. In machine learning we call this different distribution in feature between training data and test data. This problem needs to be overcome in our study.
• Second, due to the errors introduced in the translation process, there may be different kinds of errors in the translated text. This noise problem produced in translation procedure should also be addressed effectively for the purpose of improving the accuracy of classification.
• Due to the word drift, some features functional for classification on source domain may be useless for classifying data in target domain. Thus, we have to make the distributions of source domain and target domain as sim-

1 According to the statistics reported from ODP on August 1, 2010

ilar as possible to let the features selected from source domain also work for the target domain.

To solve the above problems, we develop a novel algorithm for cross-language text classification. We introduce the weights of features and training instances for domain adaptation. An objective function on these two type weights is built to take the distance between source domain and target domain and the inner distance in domain into consideration. We try to optimize the objective function through Bi-Weighting. The detail of our algorithm will be described later.

The rest of our paper is organized as follows. In section 2, we discuss the related work. In section 3, we give the mathematical formulation of the problem we focus on in the paper. Section 4 describes our proposed algorithm in details, including feature weighting and instance weighting. The experimental results are presented and analyzed in section 5. Finally, we conclude this paper with future works in section 6.

2 RELATEDWORK

2.1 Cross-Language Text Classification

Many attempts have been made on addressing cross-language classification problems. [Bel et al., 2003] study EnglishSpanish cross-language classification problem. [Rigutini et al., 2005] proposes an EM-based learning method to address English-Italian cross-language classification and acquires good empirical results. It applies feature selection before each iteration. [Ling et al., 2008] proposes an approach based on information bottleneck theory [Tishby et al., 2000]. The method allows all the information to be put through a "bottleneck". Then, the approach maintains most of the common information and disregards the irrelevant information.

2.2 Transfer Learning

[Pan and Yang, 2009] summarize the relationship between traditional machine learning and transfer learning and give us the categorization under three sub-settings, inductive transfer learning, transductive transfer learning and unsupervised transfer learning. Instance transfer tries to re-weight the source domain data or reduce the effect of the "bad" ones encouraging the "good" source data to contribute more for the classification. Based on this definition, [Dai et al., 2007] proposed a booting algorithm, TrAdaBoost, which is an extension of the AdaBoost algorithm. TrAdaBoost assumes that the source and target domain data share the same set of features and labels, but the distributions of the data in the two domains are different. In addition, [Jiang and Zhai, 2007] propose a heuristic method to remove "misleading" training examples from the source data. Feature transfer focuses on finding "good" feature space to reduce the gap among domains and minimize classification or regression model error [Pan et al., 2009; Chen et al., 2009]. Supervised feature learning is similar to methods used in multi-task learning. [Argyriou et al., 2006] propose a sparse feature learning method for multi-task learning. In a follow-up work [Argyriou et al., 2008] propose a spectral regularization framework on matrices for multi-task structure learning. [Raina et al., 2007] propose applying sparse coding [Lee et al., 2006],which is an unsupervised feature construction method in order to learn higher level features for transfer learning. Recently, manifold learning has been an alternative method for transfer learning. [Wang and Mahadevan, 2008] propose a Procrustes analysis based approach to manifold alignment without correspondences, which can be used to transfer the knowledge across domains via the aligned manifolds.

3 Problem Statement

In this section, we describe the problem we focus on in this paper and introduce some notations and definitions used in this paper.

A domain D includes two components: a feature space X and a joint probability distribution P (⃗x), where ⃗x ∈ X. Given a specific domain D = {X, P (·)}, a task T associated with domain D consists of two parts: a label space Y and an objective predictive function f(·) (represented by T = {Y, f(·)}), which can be learned from a training sample with data pairs {⃗xi, yi}, where ⃗xi ∈ X and yi = f(⃗xi) ∈ Y.

Consider the case where there are one source domain DS with its corresponding task TS and one target domain DT with its corresponding task TT . Here DS = {⃗xS1 , . . . , ⃗xSnS }, where ⃗xSi ∈ XS is an instance, XS is the feature space in the source domain, and nS is the number of instances in the source domain; the task in the source domain TS = {YS, fS(·)}, where YS is the label space in the source domain and fS is the corresponding predictive function; DT = {⃗xT1 , . . . , ⃗xTnT }, where ⃗xTi ∈ XT is an instance, XT is the feature space in the target domain, and nT is the number of instances in the target domain; and the task in the target domain TT = {YT , fT (·)}, where YT is the label space in the target domain and fT is the corresponding predictive function. In addition, we set ⃗x = {x1 , · · · , xnf }, where xi stands for the value of the i-th feature Ai in instance ⃗x and nf is the number of features.

In this paper, we address the cross-domain text classification problems, which imply that DS ̸= DT and YS = YT . We aim at searching for a predictive function fP (·) approaching the target predictive function fT (·) ∈ TT as much as possible with aid of the knowledge in DS and TS.

4 Our Approach

In this section, we present a novel domain adaptation approach to tackle the cross-domain classification problems by means of both feature and instance selection. The general assumption in domain adaptation is that marginal densities, P(⃗xS) and P(⃗xT ), are very different. It is the key reason leading to low classification performance because a classifier having good performance in DS may lead to poor results on DT . Here, we try to measure the distance of DS and DT and make it as small as possible. On the other hand, a feature has major difference of probability distribution among different classes is more likely to help us classify the test data. Thus, we also take the difference of a feature's distribution among class labels into consideration. The main idea here is to select featurs which have distinguished utility for classification from DS and make distributions of DS and DT as similar as possible. In this way, we can assume that features useful for classifying instances in DS could also be functional for classification on DT . This can be achieved by feature and instance weighting. WF ∈ Rnf and WI ∈ RnS are the weights of features and training instances respectively and used to get the weighted DS and DT to realize the previous goals. For ∀i, j,WFi and WIj range from 0 to 1. From the above discussion, we can define the objective function as follows:

where DB, DI ∈ Rnf are column vectors. DB is used to estimate the distance between DS and DT (the smaller, the better). Besides, we let DI to estimate the difference of Ai among different classes, which can be also considered as the inner distance of a domain. 1F ∈ Rnf and 1I ∈ RnS are column vectors with all ones. ‖1F -WF ‖2 and ‖1I -WI‖2 are to control the change of two domains. λWF and λWI are trade-off factors. Here, we use KL divergence[Kullback and Leibler, 1951] to calculate the distance of features. Thus Eq.(1) can be written as:

where p(Ai) and q(Ai) are probability distributions of feature Ai in DS and DT respectively. pj(Ai) and pk(Ai) reprsent the distributions of Ai on class j and k in DS respectively. DI only consider the inner distance of DS due to the absence of class labels in DT . DKL(p(x)‖q(x)) is the KL-divergence defined as follows:

Note that KL-divergence is always non-negative due to the Gibbls' inequality[Cover and Thomas, 1991]. In addition, p(Ai), pj(Ai) and pk(Ai) are the distributions of Ai consisting of the weighted training instances. Each Ai has the internals Vi = {vi1, · · · , vil}. Eq.(2) can be rewritten as:

where DSmi is the ith feature of instance ⃗xSm ∈ DS. Accordingly, DTri is the ith feature of instance ⃗xTr ∈ DT . Our objective is to acquire WF and WI making J(WF ,WI) as small as possible.

Now, we introduce how to iteratively update WF and WI . In the first step, we fix WI and update WF to optimize J (WF , WI ) by computing the derivate of J (WF , WI ) with parameter WF :

GivenWI and solving

we can get the new value of WFi . Next, we update WI when WF is fixed. We calculate the derivate of J(WF ,WI) with parameter WI :

where vu equals to DSmi . It is apparent that p(vu), pj(vu), pk(vu) are the first-order function on WIm 's reciprocal. Let

and we obtain the new value of WIm . We can use feature weighting and instance weighting iteratively until convergence or for the specific times. We summarize the above process in Algorithm 1 .

Algorithm 1 BI-Weighting (BIW) Domain Adaptation for Cross-Domain Text Classification

• INPUT DS: source domain; DT : target domain; λWF : smooth factor for feature weight; λWI : smooth factor for source domain instance weight; CB: base classifier trainer (e.g. SVM).

OUTPUT the predictive function fP .

• 1: Initialize WF andWI;
• 2: repeat
• 3: FixingWI, update WF in light of Eqs. (5 & 6);
• 4: FixingWF , update WI in light of Eqs. (7 & 8);
• 5: until convergence (or achieving iterNum times)
• 6: Revise XS to X R S withWF andWI;
• 7: Build a classifier fP with X R S and CB;
• 8: RETURN fP

5 Experiments

In this section, we empirically evaluate the effectiveness and efficiency of the algorithm proposed in Section 4.

5.1 Experimental Setting

Our evaluation uses the Web pages crawled from the Open Directory Project(ODP) 2 during May 2010, including categories of Arts, Computers, Games, Health, Home, News, Recreation, Reference, Science and Shopping. Each Web page in ODP was classified by human experts. We preprocess the raw data as follows. First, all the Chinese Web pages are translated into English by Google Translator 3 . Then, we transform all the letters to lowercase, and stem the words using the Porter's stemmer [Porter, 1980]. Afterwards, stop words are removed.

In order to evaluate our algorithm, we set up six crosslanguage classification tasks. Five of them are binary classification tasks, and the other one is for three-class classification. We randomly resample 50000 instances from English Web pages as the training set due to the computational issue.

In the following experiments, we choose two traditional classifiers: Naive Bayes and Support Vector Machines (SVM) [Chang and Lin, 2001], and four transfer learning approaches: Transductive SVM (TSVM) [Joachims, 1999], Information Bottleneck (IB) [Ling et al., 2008], Transfer Component Analysis (TCA) [Pan et al., 2009] and domain adaptation with Extracting Discriminative Concepts (EDC) [Chen et al., 2009] for the purpose of comparisons. λWF and λWI are set to 0.05.

With the help of the knowledge from the source domain, transfer learning aims at predicting labels for instances in the target domain with classification performance as close as possible to the traditional classification scenarios, training a classifier with instances in the target domain and applying it to the instances in the same domain. In particular, for the purpose of comparisons, we implement a "upper bound" algorithm by committing 5-fold cross-validations with NB, SVM and TSVM individually over the data in the target domain (the Chinese text), which are called NB-CN, SVM-CN and TSVM-CN respectively. Note that, these classifiers are virtual "enemies" against the transfer learning algorithms. If the gap between a specific transfer learning algorithm and the virtual "enemies" is narrow, the transfer learning algorithm is close to the "limit"; otherwise, there is still space to improve. Precision, recall and F1-measure are calculated in each experiment in this paper, which are widely used as evaluation metrics in text classification.

5.2 Impact of Iteration Times

Since our algorithm BIW is an iterative algorithm, an important factor of BIW is the number of iterations (iterNum) or the convergence speed. We run a few tests to observe the convergence speed. Figure 1 shows the impact of iteration times on BIW in one of these tests. F1-measure at zero point indicates the value of the algorithm without any feature and instance weighting process. BIW usually converges at the two or third iteration. In the following experiments, we set iterNum to be 3 to make sure that BIW is to converge.

2 http://www.dmoz.com/.

3 http://www.google.com/language tools.

5.3 Comparison with InstanceWeighting Only

Since a few instance weighting methods have been applied on transfer learning, in this subsection, we compare our algorithm BIW with the methods using only instance weighting(Uni-Weighting) to see whether it is necessary to integrate instance weighting and feature weighting. We will compare BIW with feature weighting (or extracting) only methods in the next subsection. Figure 2 shows the classification performance of NB, Uni-NB and BIW-NB on two cross-language classification tasks. From the figure, it is clear that Uni-NB outperforms NB but does worse than BIW-NB. The results show the benefit of combining feature weighting and instance weighting.

5.4 Comparison with Baselines

In this subsection, we conduct experiments on all the six datasets. Five of the tasks are binary class classification while the other one is a 3-class classification. We use naive Bayes, LibSVM and IB as base classifiers in our BIW algorithm, which are named BIW-NB, BIW-SVM and BIW-IB respectively. Table 2 shows the experiments results of the comparisons with different baseline methods as well as the "upper bound" methods. From these tables, we see that the BIW algorithms are consistently better than their base classifiers. Further more, the BIW algorithms in some tasks perform as good as or even outperform the "upper bound" methods.

We compare the BIW algorithm with TCA [Pan et al., 2009] and EDC [Chen et al., 2009] in smaller datasets ( randomly select around 1000 instances in each task with about 10000 features) for the computational issue including memory usage of EDC 4 . Table 1 shows the result of the comparison. Apparently, BIW outperforms TCA and EDC by 5.2% and 7.3% in the overall F1-measure.

4 EDC needs O(m2 ) of memory, where m is the number of features.

Value

0.90

0.88

0.86

0.84

0.82

0.80

0.78

0.76

0.74

0.72

0.70

0.68

0.66

0.64

0.62

0.60

NB

Uni-NB

BIW-NB

Precision Recall F1-measure Games vs News

6 Conclusion and FutureWorks

In this paper, we present a novel transfer learning approach to tackle the cross-domain text classification problems. We first align the feature spaces in both domains utilizing some online translation service, which makes the two feature spaces under the same coordinate. Then we propose an alternated method for domain adaptation. We empirically evaluate the effectiveness and efficiency of our approach. The experimental results show that our approach outperforms some baselines including supervised, semi-supervised and transfer learning algorithms.

In the future, we plan to study other potentially better algorithms for the transductive transfer learning problems. We will apply our approach to other domains. We also plan to extend our method to the regression scenario.

Acknowledgments

We thank the anonymous reviewers for helpful comments. This work was supported by National Natural Science Foundation of China (61003140, 61033010) and the Fundamental Research Funds for the Central Universities (09lgpy62).