Domain Adaptation with Ensemble of Feature Groups

1 Introduction

Discriminative learning models work effectively when the training and testing examples are drawn from the same distribution. However, in several real-world applications, it is often highly desirable to train a classifier from one source domain, and apply it to a similar but different target domain, where the annotated data is unavailable or expensive to create. One example of this scenario is to learn a text categorizer from a large collection of labeled newswire articles, but use it to process regular Web documents. In this domain adaptation setting, the goal is to leverage the data available in the source domain to improve the accuracy of the model when testing on target domain examples.

As observed by previous studies, unfortunately, na¨ıvely applying classifiers to a different domain often leads to considerable performance degradation [Daum´e III, 2007; Jiang and Zhai, 2007]. Consequently, a number of approaches have been proposed recently to address the problem of domain adaptation. Some methods focus on re-weighting training instances from different domains [Jiang and Zhai, 2007; Bickel

∗This research was conducted during author's internship at Microsoft Research.

Wen-tau Yih

Microsoft Research Redmond, WA, USA scottyih@microsoft.com

et al., 2009], while others modify the feature space to capture domain-specific and domain-invariant aspects [Blitzer et al., 2006; Daum´e III, 2007; Finkel and Manning, 2009; Jiang and Zhai, 2006]. Despite the fact that these methods adapt seemingly very different strategies, the shared rationale behind is to bring the empirical source distribution closer to the target domain, and thus increase the accuracy of the classifier when evaluated on the target domain data.

In this paper, we present a novel ensemble-based approach for domain adaptation, based on feature re-weighting. Our method builds on the observation that when moving from the source domain to the target domain, different features may have different levels of distributional change. For instance, in email spam detection, the distribution of content-based features changes heavily over time as it is very easy for spammers to revise the subject and body of a spam message. In contrast, the distribution of features based on user-preference or sender-IP does not change as much. This phenomenon can be easily observed empirically, which we demonstrate in Sec. 4.2. Intuitively, a classifier trained on distributionally stable features is likely to behave more consistently than a classifier based on an unstable feature group. Therefore, in addition to the expressiveness of its feature space in predicting the label, the importance of each classifier should also depend on the distributional stability of its features. Given a set of feature groups that capture this notion, where the grouping can be decided by domain knowledge or statistics derived from unlabeled data, we first train individual classifiers separately using only the corresponding group of features. The final model is a weighted ensemble of individual classifiers, where the weights are tuned based on the performance of the ensemble on a small amount of labeled target data. Compared to the existing approaches, our method is unique in that it considers the cross-domain behavior of different feature groups directly in terms of their classification accuracy. Afterwards, instead of creating an instance distribution close to the target domain, it adjusts the influence of features on the final classifier by tuning their weights.

Our approach is supported both by a solid theoretical analysis and a strong empirical validation. We present a generalization bound for the style of ensembles mentioned above based on the dH-distance framework proposed by Ben-David et al. [2007]. We show that ensembles provide an additional degree of freedom in the form of tunable weights of individual classifiers which can be leveraged to adapt to the target domain. Empirically, when applied to the problems of sentiment analysis and spam detection, our approach outperforms several state-of-the-art methods, as well as the strong baseline that is trained simply on combined source and target data.

The rest of the paper is organized as follows. We first formalize the problem setting in Sec. 2. Then we show our algorithm along with the theoretical analysis in Sec. 3, followed by the experimental results in Sec. 4. Closely related work is surveyed in Sec. 5 and Sec. 6 concludes the paper with some discussion and future work.

2 Problem Setting

Let X = {0, 1}p be the feature space from which a pdimensional feature X = {X1, . . . ,Xp} is sampled and let Y = {-1, 1} be the output space. Suppose DS(x, y) and DT (x, y) are two distributions over X × Y - the former is called the source distribution and the latter, the target distribution. Let LS and LT be labeled examples sampled from DS and DT , respectively. In the setting of domain adaption, usually |LS| ≫ |LT |. Moreover, we assume that some unlabeled data from the target domain, UT ∼ DT (x), is available.

Let Δ : ℜ × ℜ → {0, 1} be the standard zero-one loss function: Δ(z1, z2) is zero if z1z2 ≥ 0, one otherwise. The idea behind domain adaptation is to leverage LS and UT , in addition to LT , to learn a hypothesis ht : X → Y with low expected error on target, defined by ΔDT (ht) = E(x,y)∼DT [Δ(ht(x), y)]. Of course, LS can help only if DS and DT are not "too different".

Although the feature space defined here is binary (i.e., X ⊆ {0, 1}p ), our analysis and technique, by no means, are restricted to discrete feature spaces. In the text applications considered in this paper, such a setting is very common; for example, the occurrences of unigrams or bigrams in the text are encoded as binary features. Also, the number of features, p, is typically much larger than the number of training examples.

Last, we assume that we have a decomposition of feature vector X into r + 1 (possibly overlapping) feature vectors or groups: X1 ,X2 , . . . ,Xr ⊂ X with X0 = X; that is, Xi is a subset of features contained in X. Essentially, our approach considers ensembles of classifiers where each classifier is trained on one particular feature group. The nature and purpose of these groupings would become clear in section 3.

3 Feature Ensembles for Domain Adaptation

In this section, we propose FEAD, a Feature Ensembles approach for Domain Adaptation, which learns a classifier for the target domain in the form of an ensemble of feature group classifiers. The design of FEAD is motivated by a VC-style generalization bound analysis for ensemble classifiers in the context of domain adaptation. Compared to existing domain adaption methods, FEAD provides an additional degree of freedom to adjust the trade-off between the generalization error and domain distribution change of individual classifiers trained on the corresponding feature groups. Although the selection of the underlying learning algorithm is not restricted, Algorithm 1 Algorithm for Feature Ensembles for Domain Adaptation (FEAD)

• 1: Given: Data: LS and LT ; feature groups: X0, . . . ,Xr; hypotheses spaces: H0, . . . ,Hr; convex loss function: Δc
• 2: for i = 0 to r do
• 3: learn: hiS ← arg minh∈Hi ΔcLS (h)
• 4: end for
• 5: α ← argminα′≥0 ∑(x,y)∈LT Δ(∑i α′ihiS (x), y)
• 6: return wt = ∑ri=0 αihiS

we give an interesting insight into FEAD via a concrete instantiation of our ensemble approach when using logistic regression.

3.1 Algorithm

Before introducing our algorithm, we first give some notations that are useful throughout the whole section. Let Δc : ℜ × ℜ → ℜ+ be a convex loss function upper bounding Δ. For a set of labeled examples L, ΔcL(f) = 1 |L| ∑(x,y)∈L Δc (f(x), y) denotes the empirical loss of the hypothesis f on L. Also, let ΔD(f, g) = E(x,y)∼D[Δ(f(x), g(x))] be the expected zero-one loss between hypotheses f and g on a distribution D. Let H be the hypothesis space being considered. For example, H can be the space of all linear classifiers.

For a feature group Xi ⊆ X: let DiS (x, y) = DS(Xi=xi ,y) Zi be the marginal source distribution over (Xi , y) where Zi is chosen to making DiS a valid distribution; let Hi be the space of hypotheses defined over Xi (clearly H0 = H and for several popular, including linear, hypothesis spaces, Hi ⊆ H); and let hSi = argminh∈Hi ΔcLS (h) be a classifier in Hi minimizing the loss on LS with ΔcLS (hSi ) = ϵSi .

We express the final classifier as an ensemble of classifiers given by h(α) = ∑ri=0 αihSi , where α = (α0, . . . , αr) ≥ 0. α is learned by minimizing the empirical target error. The whole learning procedure is delineated in Algorithm 1. On line 5, we can use grid search to find a good α, given the small search space. Empirically, we found that applying a linear classification technique like logistic regression is more efficient and performs well, which is used in our experiments.

Note that α ≥ 0 (Line 5) is not a restrictive assumption as in the event some hSi is rendered ineffectual on the target domain due to drastic distribution change of Xi , αi can be simply set to zero - it is highly unlikely for classification decisions to be reversed for any feature group. Since Δ is invariant to positive re-scaling, we assume that ∑i αi = 1.

3.2 Theoretical Analysis

In order to present generalization results for feature groupsbased ensembles, we use a classifier-induced distance for distributions called the dH-distance - related to the generalized Kolmogorov-Smirnov distance [Devroye et al., 1996] - introduced for domain adaptation by Ben-David et al. [2007]. 1

1 We slightly modify the notation to suit our analysis.

Definition 1 (dH-distance [Ben-David et al., 2007]). Let H be a set of hypotheses, mapping X to ℜ. The dH-distance between two distributions Q1 and Q2 over X is defined as

Intuitively, dH(Q1, Q2) bounds how closely we can predict the loss between two hypotheses on Q2 if we know their loss on Q1. We first present two propositions regarding dH.

Proposition 1 (Convexity). For any distributions D,D1, and D2 with Dλ = λD1 + (1 - λ)D2, λ ≥ 0, we have

Proof.

Proposition 2 (Triangle inequality). For any distributions D1, D2 and D′ we have

Proof. Similar to the proof of proposition 1.

We now have the following bound, which is similar to Theorem 3 in [Ben-David et al., 2010].

Theorem 1. For all h = ∑i αihSi with αi ≥ 0 ∀i and ∑i αi = 1, the following bound holds with probability at least 1 - δ for δ > 0 and for all β ∈ [0, 1]

where DiS (x, y) = DS(Xi=xi ,y) Zi is the normalized marginal source distribution over (Xi , y), ϵ∗ = argminh′∈H(ΔDT (h′ ) + ΔDS (h′ )) and ϵ(pH, β, δ) = 2√ β2 η + (1-β)2 1-η √ 2pH log(2(m+1))+2 log( 8 δ ) m where m = |LS| + |LT |, η = |LT | m , and pH is the VC Dimension of H.

Proof. UsingD′ = ∑i αiDiS in Proposition 2 and then using Proposition 1 yields

Substituting the above in the second step of the proof of Theorem 3 in [Ben-David et al., 2010], along with the fact that Δ ≤ Δc and the convexity of Δc yields the result.

Theorem 1 gives a bound on the expected error (ΔDT (h)) on target in terms of empirical source errors (ϵSi ) of individual feature group classifiers, empirical error (ΔLT (h)) of the ensemble on target, and the dH-distance of each feature group distribution with the source (dH(DS,DiS )) and the target (dH(DiS ,DT )). In addition, it also provides several interesting theoretical insights, which we discuss below.

By using the triangle inequality for dH-distance (Proposition 2), we have not loosened the bound in Theorem 1 in the sense that by setting α0 = 1, we can recover the bound for a single classifier based on X and trained on LS. Furthermore, the above bound provides free parameter α = (α0, . . . , αr), in addition to β, which can be tuned to obtain a lower target error. While most domain adaptation algorithms (e.g., [BenDavid et al., 2010]) operate by tuning β, which controls the weight of the error on LT vs. the error on LS through instance weighting, FEAD focuses on minimizing the target error by tuning α instead. Simultaneously, terms in Eq. (1) can be kept bounded by considering feature groups that allow a low error on source domain data and have a low dH-distance from DS and DT (i.e. they generalize well across domains).

This analysis naturally motivates an approach that is even simpler than FEAD - picking a single "best" feature group classifier (BFG) for the target domain, where the notion of "best" can be decided by the user. Although the ensemble approach is clearly more expressive than the BFG approach, as the former's output space is a superset of the latter, it is valid to ask whether the additional expressiveness indeed earns FEAD a lower error than BFG. In general, there is no reason to expect that the expected target error or its upper bound given by Theorem 1 is minimized when only one of the classifiers is picked (in this case the result will be the same as the BFG approach.)

We give a simple artificial example which elucidates this point. Consider the following setting: We have two features (x1, x2) ∈ ℜ2 and a label y ∈ {-1, 1}, which we wish to predict. The features are conditionally independent given the label i.e. P(x1, x2|y) = P(x1|y)P(x2|y). Moreover, we are given the following description of the distribution: (1) P(y = 1) = P(y = 0) = 12 ; (2) DS(x1|y) = DS(x2|y) = N(y, 1); (3) DT (x1|y) = N(y, 1); 4) DT (x2|y) = N(y, 2), where DS and DT describe distributions on source and target, respectively, and N (μ, σ2 ) represents a Gaussian distribution with mean μ and variance σ2 .

It is easy to see that the asymptotically optimal classifiers for source domain are given by x1 and x1 + x2 when considering feature groups x1 and (x1, x2), respectively; similarly, the bayes optimal classifier for the target domain and the feature group (x1, x2) is given by x1 + 12 x2.

If we consider two feature groups: (x1, x2) and x1, the BFG approach would, asymptotically, dictate picking the best of x1 +x2 and x1 for the target domain; clearly, both of these classifiers give higher error on the target domain than the optimal classifier: x1 + 12 x2. However, the WPoE approach would be able to produce the optimal classifier x1 + 12 x2 as x1 + 12 x2 = 12 (x1 + x2) + 12 (x1). This example illustrates how additional expressiveness of feature group ensembles can help outperform the BFG approach.

Overall, our theoretical analysis shows that FEAD is a flexible algorithm that directly tackles domain change - it allows for minimizing error on LT while keeping the error on LS bounded. Although the focus of this paper is not on techniques for deciding the "best" feature groups, we demonstrate in Sec. 4 that by adapting simple heuristics to determine the feature grouping, based on statistical measures or domain knowledge, FEAD can yield strong empirical results in a number of real-world domain adaption tasks.

3.3 FEAD as Product of Experts

When considering a specific setting where H is the space of all linear classifiers and Δc is the log-loss given by Δc (h(x), y) = log(1 + exp(-yh(x))), our analysis in this section provides an interesting probabilistic perspective of FEAD. Let wiS be a weight vector learned for feature group Xi via logistic regression. Given a feature vector x, the probability of output y, as per wiS , is given by

which implies that the odds ratio of y = 1 and y = -1 for this instance is given by

FEAD expresses the final linear classifier for the target domain, wt, as ∑i αiwis , which is equivalent to expressing the odds for any instance as a weighted product of odds given by individual classifiers. In this sense, our approach is similar to the Product-of-Experts framework proposed by Hinton [1999], wherein classifiers based on feature groups can be thought of as experts.

4 Experiments

We evaluate our approach empirically on two domain adaption tasks - sentiment analysis and email spam detection - and compare with other state-of-the-art approaches.

4.1 Sentiment Classification

Sentiment analysis is the task of classifying textual reviews into positive or negative based on the expressed "sentiment" [Pang et al., 2002; Blitzer et al., 2007]. Reviews for different categories of products tend to be different in terms of vocabulary and writing style. Consequently, a sentiment classifier trained on one domain (e.g., books) suffers from considerable performance degradation when applied to another domain (e.g., electronics), thus necessitating a need for domain adaption methods.

In this set of experiments, we use the benchmark dataset released by Blitzer et al. [2007], which consists of reviews of four different product categories: books, DVDs, electronics, and kitchen appliances, collected from Amazon.com. Along with the IMDB movie reviews released by Pang et al. [2002], we generate all 20 possible source-target pairs for the empirical evaluation. For all the methods we tested, we follow the same data split and experimental procedure. Each domain contains 2000 instances and is randomly split into a training/testing set of 1600/400 examples. Furthermore, we randomly select 160 instances from the training set of each domain to serve as a validation set. For each source-target adaptation setting, we use the training set of source as LS (labeled source training data), the validation set of target as LT (labeled target training data), and the remaining training examples of target as UT (unlabeled target data.) Features extracted from each review are the unigrams and bigrams occurring at least twice in LS ∪ LT ∪ UT , encoded as binary features. We perform 30 such random splits for each setting and report the averaged accuracy when evaluating the model on the target testing data.

We compare four approaches - logistic regression (LR), multiview transfer learning (Multi-T), easy adapt (EA) and our feature ensemble approach (FEAD). As the baseline approach, LR is a model trained over all the features. We first find the best Gaussian smoothing prior by training the model on the source training set (LS) and testing it on the validation set (LT .) The final model is learned on the entire labeled data (LS ∪ LT ) using the selected prior. Proposed recently by Blitzer et al. [2009], Mutlti-T is an enhanced version of structural correspondence learning (SCL) [Blitzer et al., 2007], which has been tested previously on the sentiment dataset 2 . We conduct the experiments using the exact setting as reported in their paper. Another state-of-the-art method, EA [Daum´e III, 2007] projects the source and target examples to a new expanded feature space first, and then trains the classifier on the new labeled examples in a way similar to the baseline LR approach. Finally, FEAD uses two groups of features. The first one is the trivial group that contains all the features - call this feature group total. For the second feature group, we aim to have features that lead to low dHdistance and empirical error. We adapt a heuristic similar to the one used in [Blitzer et al., 2007] based on mutual information. For each feature appearing in LS, we first compute its mutual information compared with the label. For a feature to be included in this group, its mutual information needs to be higher than at least half of the features in LS and it needs to occur at least once in the target data (LT ∪ UT ). We call this feature group common. Notice that this by no means provides the best feature grouping for our approach. Instead, we demonstrate that even with simple groups of features selected following the principle suggested by our theoretical analysis, a significant improvement can be observed empirically.

Table 1 shows the averaged accuracy of different methods for each source-target adaptation setting. As can be seen clearly, FEAD yields the best results for most of the settings. Among them, FEAD performs statistically significantly better than both EA and Multi-T in 8 cases, and better than all competing approaches in 4 cases. Even when FEAD does not achieve the highest accuracy, the difference compared with the best performing method is not statistically significant, except for pairs M-E and M-K. Table 2 shows the normalized (i.e. weights for total and common features groups sum to 1) values of the weight assigned to the common feature group. From the table, it can be infered that the common feature group plays a significant role in the final classifier. Notice that the baseline (LR), when provided with some amount of labeled target data, is notoriously hard to defeat [Daum´e III, 2007; Chang et al., 2010]; our experiments corroborate this. Overall, the experiments on the sentiment analysis empirically show that FEAD is a simple yet powerful algorithm for domain adaptation.

2 We use the software package provided by the authors. Personal communication confirms that the results of Multi-T and SCL-MI are comparable.

4.2 Email SpamDetection

Spam detection is a problem of classifying email messages to either spam or good. Compared with the typical binary classification setting, the main challenge of spam detection comes from its adversarial nature. As spammers often quickly react to a newly deployed filter by modifying the spam messages [Lowd and Meek, 2005b; 2005a], the sample distribution from the testing period often dramatically changes. As argued previously by Jiang and Zhai [2007], such phenomenon can be treated as a domain adaptation scenario due to the temporal difference between the source and target domains, and thus is a good application for our approach.

We use real-world email spam data in the experiment. The dataset contains real email messages received by users of Hotmail. The sampling process randomly picks emails sent to the volunteer users and asks them to label the messages as either spam or good. Among the total 915,000 labeled messages, we treat the 765,000 messages received from July-01-2005 to Nov-30-2005 as the source training set (LS). The target set consists of 150,000 messages received from Dec-01-2005 and Dec-15-2005, where we keep the first 30,000 examples for training and tuning (LT ) and the rest for testing. Note that we are making a distinction between source and target data by cutting off a continuous timeline at an arbitrarily picked point. We assume that this distinction is a good enough approximation to the 'source-target' setting of domain adaptation.

Although spam detection is primarily treated as a textclassification problem, several non-textual types of features have been proven useful in previous work, such as the sender information [Leiba et al., 2005] or the distribution of email received by specific users [Chang et al., 2008]. These features not only capture very distinctive information, but also behave differently in the domain adaptation setting. For example, while it is easy for spammers to change email content, switching to a new server farm to send spam is relatively difficult. As a result, each specific type of features has nonidentical distribution change and leads to classifiers with different changes in expected errors.

In order to show how different feature groups undergo different changes in their discriminative power, we compare the performance of two classifiers: one trained only on features from email-content (content features) and the other trained only on features based on sender information (sender features.) For each set of features, we used two different settings: random and time-shifted. The random setting is the control group that tests the scenario when the training and testing data come from the same distribution. In this setting, we train the classifiers on randomly chosen 765,000 instances, tune on randomly chosen 50,000, and test on the remaining 100,000. In contrast, the time-shifted setting simulates the domain adaptation scenario, where we train the classifiers on first (chronologically) 765,000 instances, tune on the next 50,000, and test on the final 100,000. Fig. 1 shows the comparisons of the content and sender based classifiers in these two settings, using the ROC analysis. A large performance drop in the time-shifted setting compared to the random setting can be explained by a drastic distribution or domain change. The performance degradation is more significant for content-features compared to sender-features, which empirically shows they undergo different distribution change.

In the experiments, we leverage this background knowledge to form the feature grouping used by FEAD. In addition to content and sender features, we have two other feature groups: user features and a trivial feature group that contains all the features. The content features are words in the subject and body of the email that occur at least three time in the source set. The sender features include the first 16 bits, the first 24 bits, and the entire IP address of the sender. Finally, the user features are simply the recipient ids.

We compare the performance of FEAD with two other approaches, logistic regression (LR) and easy adapt (EA) 3 . LR and EA do not take advantage of the background knowledge of feature grouping and are trained on all (i.e. content, sender, and user) features put together. The experimental settings are the same as described in the experiments on sentiment analysis (Sec. 4.1). To compare performance, we report the ROC curves and the normalized AUC values in a low false-positive rate (FPR) region, as the cost of losing good email is much higher than receiving spam. Normalized AUC for FPR ≤ δ is defined as 1δ AUC(δ) where AUC(δ) is the area under the curve for FPR between 0 and δ. As can be observed from Fig. 2, FEAD performs better than LR and EA consistently in this region, and has a much higher normalized AUC score. In comparison, although EA indeed performs better than the baseline LR, the improvement gain is relatively small and its ROC curve in fact crosses that of LR. This empirical result suggests that FEAD can effectively leverage the domain knowledge of the feature grouping, which is valuable in improving the model performance for domain adaptation.

3 We attempted to include multiview transfer learning (Multi-T). Unfortunately, it does not seem to scale well to a large amount of training data, and failed to produce the final model due to memory issues, even after increasing the heap size to 20GB.

5 RelatedWork

The problem of domain adaptation has been studied extensively from both the theoretical perspective and algorithmic sides. To understand formally the characteristics of the problem, Ben-David et al. [2007; 2010] proposed the dH-distance framework, which was later extended to a wider variety of loss functions by Mansour et al. [2009]. Although the idea of feature grouping was never discussed previously, their work provides a solid foundation for the theoretical analysis of our ensemble approach.

A variety of algorithm-centric domain adaption methods have also been proposed. For example, EasyAdapt [Daum´e III, 2007] uses feature-replication to implicitly capture the domain-invariant and domain-specific aspects of features. Blitzer et al. [2006] proposed Structural Correspondence Learning (SCL), which projects features to a latent space such that these latent features exhibit roughly the same distribution across source and target domains. Alternatively, Finkel and Manning [2009] and Jiang and Zhai [2006] propose approaches based on imposing priors over individual features, where the priors can be decided directly based on the generalizability of the features. FEAD is related to these works as it massages the weights of different features in terms of their contribution to the final prediction function. However, unlike these approaches, the feature weights in FEAD are tweaked after creating the classifiers.

The use of feature grouping in FEAD is analogous to adaptation from multiple sources [Mansour et al., 2008; Ben-David et al., 2010], where feature groups can be thought of as different sources created artificially. However, adaptation from multiple sources typically assumes that the instances from different sources are independent, which is clearly not the case in our setting. Finally, we share the idea of using ensemble-like learning for domain adaptation with Dai et al. [2007], who use boosting for the same purpose. However, our approach considers ensembles over different feature groups, whereas they create ensembles by re-weighting instances.

6 Conclusion

In this paper, we introduced a technique that leverages the expressiveness of ensembles to adapt to distribution change between domains. Building on this notion, we presented a simple and easy-to-implement method based on re-weighting classifiers learned on different feature groups. Our approach provides the flexibility to re-adjust the influence of different feature groups on the target domain classifier based on their cross-domain distributional stability. This design is motivated by our theoretical analysis, and its empirical effectiveness is demonstrated through experiments on the benchmark sentiment analysis task and spam detection, where our approach outperforms several state-of-the-art methods.

Although in this work we showed that by using simple statistical measures or domain knowledge to generate the feature grouping, our approach can lead to significant improvement, it is nevertheless interesting to find automatically the best feature grouping for the task. We leave that as future work.

Acknowledgment We would like to thank John Blitzer for providing the Multiview-T software, Michael Gamon for preparing sentiment analysis data, Sumit Basu and Chris Meek for their comments and the anonymous reviewers for their useful suggestions. The work was partly supported by Army Research Laboratory (ARL) under agreement W911NF-09-2-0053 and by an ONR award on "Guiding Learning and Decision Making in the Presence of Multiple Forms of Information."