Supervised classification tasks like Sentiment Analysis or text classification need labelled training data. These labels can be difficult to obtain, especially for complicated and ambiguous data like texts. Instead of labelling new data, domain adaptation tries to reuse already labelled data from related tasks as training data. We propose a greedy selection strategy to identify a small subset of data samples that are most suited for domain adaptation. Using these samples the adaptation is done on a subspace in a kernel defined feature space. To make this kernel approach applicable for large scale data sets, we use random Fourier features to approximate kernels by expectations.
The usual assumption for most of the Data Mining and Machine Learning tasks is that the training data used to learn a model has the same distribution as the test data on that the model is applied. On the other hand, there are many situation where this is not true. Imagine as Data Mining task Sentiment Analysis on product reviews from Amazon. In case of a new product or product type, producers might be interested in how their products catches on. Sentiment Analysis now tries to label the reviews of the corresponding products as being positive or negative. To assign such labels, classification models are trained on some labelled reviews and than applied on the unlabelled reviews. For new product types it is reasonable to assume that we have no labelled training data at hand. Labelling the new reviews can be quite expensive. Especially identifying the sentiment in texts can be hard - even for experts. Ambiguous words or sarcasm for instance make this task difficult. Instead of starting to label the new reviews, another possibility is to reuse already labelled reviews from different products. There might be for instance already labelled reviews about books and now we get new reviews about DVDs. The idea is to leverage the reviews about books to train a classifier that is applied on reviews about DVDs. To accomplish this, we need to find a way to safely transfer the information from one domain to another.
We solve this problem by domain adaptation with the following assumptions: We have two data sets with (possible large) difference in distribution. We have data from a source domain S that is distributed via ps together with label information y distributed via ps(yjx). On the other hand, we also have data from a target domain T that is distributed via pt with no label information. The domain adaptation task now is to use the source domain together with its label information to find a classifier that labels the target domain best.
We expect that many data sets share similarities on latent subspaces. On product reviews for instance, a book might be described as tedious while a toaster might be described as malfunctioning. Both words have negative meaning and very likely appear together with other negative words like bad, poor or poorly. In a latent subspace in the space spanned by the words, we expect that these words span together a whole dimension. When we map texts of reviews from books and electronic articles onto such a subspace the words tedious and malfunctioning can be replaced by their common meaning. This will make the texts from the different domains more similar. Further, only terms alone might not be able to find such subspaces. For instance, bi-grams like little helpful or hardly improving can also span a latent subspace that is helpful for domain adaptation. Generally, n-grams should also be considered.
In order to integrate information of multiple combinations of words, kernels like polynomial kernels can be used. Kernel methods can also integrate structural information and even information from probabilistic models. Consequently, we find low dimensional representations of the data from a source and a target domain in a Reproducing Kernel Hilbert Space. These representations shall keep enough structure from the data that a classifier trained on the source domain still performs well. On the other hand, the low dimensional representation shall make the two data sets more similar. This justifies a safe application of a classifier trained on the source domain, to the target domain.
To find the subspace for the domain adaptation we propose a greedy selection
strategy that finds the most useful data samples in the source domain for the domain
adaptation. By this, we reduce the data size and concentrate on those samples that are
potentially best suited to transfer knowledge. This idea is based on the assumption that not all
source samples might by equally important for adaptability. This has been investigated
for instance by in [
We distinguish two main directions in domain adaptation. On the hand, many of the existing approaches try to find weights for the samples that account for an mismatch in distribution of a target and a source domain. This is especially useful under the so call covariate shift assume. Here, we assume that the distribution of the labels given a sample is the same for both target and source domain. Via the weights, a sample selection bias shall be corrected. This means, we assume that the source domain is sampled from the target distribution applied a certain weighting mechanism. Many previous approaches learn such weights such that the weighted source distributions is most similar to the target distribution.
For instance [
In contrast to these approaches, several other works try to extract a subspace or feature representations in the data space that covers invariant parts across the target and the source distribution. Within such a subspace or feature representations, transferring knowledge between the source and target domain is expected to be more effective than in the whole ambient space.
In [
In this section, we introduce the background on kernel methods, subspaces in Hilbert Spaces and distances of distributions. The presented information are crucial for our proposed strategy in the next sections.
Kernel methods accomplish to apply linear methods on non-linear representations of data. Any kernel method uses a map X ! (X) from a compact input space X, for instance <n, into a so called Reproducing Kernel Hilbert Space (RKHS). In this space, linear methods are applied to the mapped elements like Linear Regressions or Support Vector Machines. The RKHS is a space of functions f (y) = (x)(y) 8x 2 X that allows point evaluations by an inner product, hence f (y) = (x)(y) = h (x); (y)i.
(x) is a function and (x)(y) means the function value at y.
Subspace Methods A subspace in an RKHS H is a closed subset H0 H. We identify
this subspace by a projection P that maps all elements of H into H0. In this work, we
concentrate only on subspaces that are spanned by the given data points in the RKHS.
This means each element in the subspace can be written as linear combination of all
data points in the RKHS, hence v = Px2H i (xi) for all v 2 H0. This is important
since we only need to consider kernel evaluations and not infinite dimensional elements
of the RKHS. Kernel PCA for instance can be used to find an appropriated projection
matrix onto such a subspace. See [
As proposed by [
M M D(H; S; T )2 = k(xi; xj ) (1) 1 X S 2 j j xi;xj2S 1
X jSjjT j xi2S;xj2T k(xi; xj ) + 1
X jT j2 xi;xj2T k(xi; xj ):
To avoid large computational and storage complexity of kernel methods,
approximations of the kernel can be used. Random features for instance approximate the feature
maps in Hilbert spaces by low dimensional random projections. The expectation of
the inner products of these random features evaluate to corresponding kernel values.
Any shift-invariant kernel (as for example the Gaussian kernel) can be represented as
expectation of random features cos(!x + b) for an appropriate distribution p(!) and
b uniformly drawn from [0; 2 ], see [
The deviation of the inner product of the random features of dimension k to the true kernel value is bounded by a tail bound using Hoeffding’s inequality. Since z! 2 [ p2; p2], we have z!(xi)0z!(xj ) 2 [ 2; 2]. This and E![z!(xi)0z!(xj )] = k(xi; xj ) justifies the following bound:
P (jz!(xi)0z!(xj ) k(xi; xj )j ) 2e k 2=8
In a domain adaptation task, we try to use information about a data set S for a classification task on data from set T . For instance, in online reviews about products we might have reviews and information about the sentiment of the reviews about lots of electronic products. Now, the people also start reviewing books. A company might for instance broaden their offers. Now, the new reviews of books shall also be classified by their sentiment. Instead of starting from scratch and labelling all book reviews, we want to leverage the information from all the reviews about electronics that have already been classified by their sentiment. Using this information, a classifier can be learned on a transformed representation of the electronic reviews and be applied to transformed book reviews.
We assume that both data sets lie in the same Hilbert space H by using the same kernel and that their distributions have the same support. Further, we have for each element a probability distribution over a label l that is the same for both data sets. This is the so called Covariate Shift assumption. This means, given an element from H the probability of label l depends not on the set the elements is in, but only on the element.
To transfer knowledge, we project all data onto a low dimensional subspace that captures the structure of the source data and the target data. This is important since otherwise we might not be able to train a good classifier or even project all data points onto a single point. In this case the distributions are the same but we can not train a good classifier.
The simplest way to find a projection onto a subspaces that captures most of the structure is using kernel PCA. We have two data sets that should not loose too much of its structure after projection. The structure of the source domain must be kept to train a good classifier, but the target domain is the actual data we are interested in. Further, we expect that not all information from the source is useful. The idea is now to keep the structure of the target data completely, but for the source data only those parts such that the source and target distributions are close on the subspace that covers only this structure.
Having found a suitable subspace for domain adaptation we project all data orthogonally onto this space. An orthogonal projection onto a low dimensional subspace retracts all data points and makes the distributions of the two data sets more similar. This is true since kP t P sk kP k k t sk and kP k = 1 for an orthogonal projection P and the mean functional t of the target distribution and s of the source distribution.
Further, the expected distance between classification models on source and target domain decreases. Since we concentrated on linear classifiers in an RKHS, we write any classifier from the source, respectively the target domain as: hs(:) = P i h (xis); :i and ht(:) = P j h (xtj ); :i. Hence, we identify the classifier by weight vectors ws = P i (xis) respectively wt = P j (xtj ). After projecting all elements onto the subspace via P , the corresponding weight vectors are wsP = P i P (xis) respectively wtP = P j P (xtj ) The distance of any of these classifiers can be bounded in the following way: jwsP (x) wtP (x)jpt(x)dx (2) = = =
Z Z Z Z kP k j j X
Z X i P X j i
i (xit) (xis) (xis)
X
X j P
X j
(xtj )jpt(x)dx (xtj )jpt(x)dx j
(xtj )jpt(x)dx jws(x)
wt(x)jpt(x)dx
Here, we use the fact that the norm of the orthogonal projection is 1, hence kP k = 1.
The bound shows that the expected distance of the linear classifiers in the subspace is
less than in the original Hilbert space. The inequality cannot become an equality since
we project always on lower dimensional subspace. This shows that these projections
decrease the expected error on the target domain of any classifier trained on source
domain with a different distribution, see (CF-[
To find the most promising data points from the source domain for the domain adaptation, we propose a greedy strategy to efficiently select them. The sampled data points shall be close to the target domain to prevent too much influence of the source domain. On the other hand, the samples must keep enough structure of the source domain such that a good classifier can be trained on the source domain data. The proposed strategy is based on the distance of the the source domain distribution to the target domain distribution. The picture in Figure 1 illustrates our idea on electronic (red) and DVD (blue) reviews. We assume the reviews of electronics as target domain and the reviews about DVDs as source domain. The reviews seem to be more similar on one direct than on the other. The idea now is to prefer points from the source domain that are more prominent in this direction for the domain adaptation.
Distribution Based Sampling We propose a sampling strategy that is based on the data
distribution. In the Hilbert space we iteratively select mapped samples from the source
domain that are most similar to the target distribution. For pt the expectation functional
for the target domain in an RKHS, the difference k pt n1 Px2S0 S (x)k2H estimates
the difference of the target distribution and a subset of samples from the source
distribution. Similar approaches are proposed by [
xt+1 = argmaxx2S fx1; ;xtghwt; (x)i wt+1 = wt + Ept [ (x)] (xt+1) (3)
For deciding when to stop the sampling, we monitor maxx2S fx1; ;xtghwt; (x)i. As soon as we have only data points from the source data set left that make the distance in distribution no longer decreasing, we stop. By this, we sample only those points such that the empirical distributions of samples and the target data are minimal. The picture on the right of Figure 1 shows an example of the course of the MMD of the samples from the source domain (electronic reviews) and the target domain (DVD reviews). We sample as long as the MMD decreases to find all points that make the distribution similar. This bewares us to sample points that make the two distribution dissimilar. Analysis of Distribution Based Sampling For pt = n1t Pxi2T strategy minimizes: (xi), our sampling E = k pt 1 X T xj2S0 (xj )k2H :
E = h pt ; pt i 2 X T xj2S0
1 h pt ; (xj )i + T 2
X xi;xj2S0 h (xi); (xj )i: Since h pt ; pt i is constant, minimizing E is the same as maximizing 2 X T xj2S0 h pt ; (xj )i Multiplying the last expression by T results in the greedy sampling as defined above when we set w0 = pt . This means the strategy matches the empirical distribution of the target samples with the empirical distribution of the subset of the samples from the source distribution.
Random Feature Sampling Our proposed sampling strategy can still result in a large number of points from the source distribution. We further propose to combine the selection strategy and the domain adaptation on a subspace by random features of dimension k. This enables us to perform the domain adaptation task in the linear space spanned by the random Fourier bases of the random features as defined above.
We define M M D! similar as M M D in Equation 2 except that the kernel evaluations are replaces by the inner products of the random features. Since M M D! 2 [ 8; 8], we can apply Hoeffding’s inequality to bound the difference to the true M M D by:
P (jM M D!2
Due to linearity of the expectation we have: E!M M D!2 = M M D2 and from the definition of the random features we have: k(xi; xj ) = E![z!(xi)0z!(xj )]. All together results in the bound.
Further, we need to estimate how much the components for the random features
deviate from the true components the source samples in the RKHS. For this it suffices
to investigate the expected difference of the true kernel matrix K for n data points and
the matrix of the inner products of the random features K!. An appropriate bound is
proposed by [
E[kK!
Kk] r 2n2 log n k + r 2n log n k :
We test our proposed method to find projections onto subspaces for domain adaptation on three standard benchmark data sets that have been used in previous domain adaptation experiments.
As first data set, we use the Amazon reviews [
The second data set is the Reuters-21578 [
The third data set is the 20 Newsgroup data set1. We use the four top-categories
(comp,rec,sci and talk) in the same configuration and splits as in [
For the subspace for domain adaptation, we simply extract the first 100 principle components from the kernel matrix K for all samples from the sampled source domain data and the target domain. This means, for each xi; xj 2 fT [ S0g we have K = (k(xi; xj ))i;j . We project all data samples (all source and training data) onto the subspace spanned by the extracted components and train a classifier on the source domain in this subspace. Next, we apply this classifier on the target domain in the
Method org vs. places places people comp comp comp rec vs. rec vs. sci vs. places vs. org vs. vs. vs. rec vs. sci vs. talk sci talk talk people places KMM 60.1 56.8 58.5 56.2 96.9 84.4 98.5 91.2 98.5 95.4 TCA 85.4 80.5 76.5 76.5 94.5 87.8 96.2 90.2 94.1 88.9 GFK 72.9 66.1 68.7 66.4 84.1 74.7 91.9 72.5 86.6 79.02 Sampling 90 82 83.5 79.2 99.1 92 99.2 98.3 99 96.2 Sampling+RF 84.7 82.9 85.5 77.3 98 88.4 98.7 91.7 98 93.7 Table 1. Accuracies on the Reuters and 20 news groups data sets. We compare our proposed greedy sampling methods (without and with random features) and projection with Kernel Mean Matching (KMM) and Transfer Component Analysis (TCA), Gradient Flow Kernel (GFK).
Method fD [ B [ Kg !E fE [ B [ Kg !D fE [ D [ Kg !B fE [ D [ Bg !K
KMM 81.0 75.2 72.5 83.9
TCA 81.4 77.8 74.7 84.9
GFK 68.7 66.3 62.2 70.7
Sampling 82.4 79.15 77.25 85.25
Sample+RF 81.3 79.7 77.65 84.85
Table 2. Accuracies on Amazon reviews using one product as target domains and all the other
domains as source domain. We compare our proposed greedy sampling methods (without and with
random features) and projection with Kernel Mean Matching (KMM) and Transfer Component
Analysis (TCA), Gradient Flow Kernel (GFK) and the Landmark method (LM) with projection
for domain adaptation.
subspace. We compare the sampling strategies without and with random features
(Sampling, Sampling+RF) with Transfer Component Analyses (TCA) [
The method by [
The results of the first experiment are shown in Tables 1 and 2. The projections onto the components result in the best performances for all the domains. The subspace obviously covers the important invariant parts of the data very well. Using random features to approximate the kernel values results in the second best accuracies compared to the other methods.
We now explore how many source domain points have been chosen from which domain.
Figure 2 shows histograms of the selected data points from the source domain for the different methods. The sampling strategy without and with random features and the GFK method uses a similar amount of samples from the source domains. The histograms show that for each target domain the methods have always one domain in the mixture of source domain where most of the samples are drawn from. For sampling there is always on clear domain from which the method samples most from.
To investigate this further we calculate the Maximum Mean Discrepancy as defined in Equation 2 to estimate the difference of the distributions of the target and source domains. Table 3 shows the MMD values using reviews from the domains. For the electronics reviews (E), the reviews about kitchens (K) are closest in distributions. Comparing this result with the accuracies from above, on the target domain with reviews about electronics, source domain kitchen performs best for domain adaptation. Similar results can be seen for the other domains. Comparing the MMD of the domains with the sampled points from the last experiments, we see that the sampling method chooses the source domain points that results in low MMD best.
MMD
E D B K
Finally, we investigate the influence of the random features on the quality of the domain adaptation. We perform several runs using different feature sizes.
The plots in Figure 3 show a fast convergence already after some thousand random features. Experiments with random features of dimension less than one thousand has let to poor performance. This might be due to the slower convergence of the kernel matrix to the matrix of the inner products of the random features in the norm. In the future we will investigate this further.
We proposed a selection strategy on samples from a source domain that are best suited for domain adaptation to a target domain with a different data distribution. The samples are selected to keep the structure of the target domain points while adding some structure from the source domain points. Projecting onto the subspace of the selected samples and the target samples results in a subspace that is well suited for domain adaptation from the source to the target domain. To apply this approach also on large scale data sets, we use random features to approximate kernel values. On benchmark data sets, we showed that our methods perform well on domain adaptation tasks. In the future we want to investigate domain adaptation across different feature spaces. In this context, we want to look at the connections to MKL and domain adaptation using multiple sources.