Transductive Learning with String Kernels for Cross-Domain Text Classification

Abstract: For many text classification tasks, there is a major problem posed by the lack of labeled data in a target domain. Although classifiers for a target domain can be trained on labeled text data from a related source domain, the accuracy of such classifiers is usually lower in the cross-domain setting. Recently, string kernels have obtained state-of-the-art results in various text classification tasks such as native language identification or automatic essay scoring. Moreover, classifiers based on string kernels have been found to be robust to the distribution gap between different domains. In this paper, we formally describe an algorithm composed of two simple yet effective transductive learning approaches to further improve the results of string kernels in cross-domain settings. By adapting string kernels to the test set without using the ground-truth test labels, we report significantly better accuracy rates in cross-domain English polarity classification.

Domain shift is a fundamental problem in machine learning, that has attracted a lot of attention in the natural language processing and vision communities BIBREF0 , BIBREF1 , BIBREF2 , BIBREF3 , BIBREF4 , BIBREF5 , BIBREF6 , BIBREF7 , BIBREF8 , BIBREF9 , BIBREF10 . To understand and address this problem, generated by the lack of labeled data in a target domain, researchers have studied the behavior of machine learning methods in cross-domain settings BIBREF2 , BIBREF11 , BIBREF10 and came up with various domain adaptation techniques BIBREF12 , BIBREF5 , BIBREF6 , BIBREF9 . In cross-domain classification, a classifier is trained on data from a source domain and tested on data from a (different) target domain. The accuracy of machine learning methods is usually lower in the cross-domain setting, due to the distribution gap between different domains. However, researchers proposed several domain adaptation techniques by using the unlabeled test data to obtain better performance BIBREF13 , BIBREF14 , BIBREF15 , BIBREF16 , BIBREF7 . Interestingly, some recent works BIBREF10 , BIBREF17 indicate that string kernels can yield robust results in the cross-domain setting without any domain adaptation. In fact, methods based on string kernels have demonstrated impressive results in various text classification tasks ranging from native language identification BIBREF18 , BIBREF19 , BIBREF20 , BIBREF21 and authorship identification BIBREF22 to dialect identification BIBREF23 , BIBREF17 , BIBREF24 , sentiment analysis BIBREF10 , BIBREF25 and automatic essay scoring BIBREF26 . As long as a labeled training set is available, string kernels can reach state-of-the-art results in various languages including English BIBREF19 , BIBREF10 , BIBREF26 , Arabic BIBREF27 , BIBREF20 , BIBREF17 , BIBREF24 , Chinese BIBREF25 and Norwegian BIBREF20 . Different from all these recent approaches, we use unlabeled data from the test set in a transductive setting in order to significantly increase the performance of string kernels. In our recent work BIBREF28 , we proposed two transductive learning approaches combined into a unified framework that improves the results of string kernels in two different tasks. In this paper, we provide a formal and detailed description of our transductive algorithm and present results in cross-domain English polarity classification.
The paper is organized as follows. Related work on cross-domain text classification and string kernels is presented in Section SECREF2 . Section SECREF3 presents our approach to obtain domain adapted string kernels. The transductive transfer learning method is described in Section SECREF4 . The polarity classification experiments are presented in Section SECREF5 . Finally, we draw conclusions and discuss future work in Section SECREF6 .
Transfer learning (or domain adaptation) aims at building effective classifiers for a target domain when the only available labeled training data belongs to a different (source) domain. Domain adaptation techniques can be roughly divided into graph-based methods BIBREF1 , BIBREF29 , BIBREF9 , BIBREF30 , probabilistic models BIBREF3 , BIBREF4 , knowledge-based models BIBREF14 , BIBREF31 , BIBREF11 and joint optimization frameworks BIBREF12 . The transfer learning methods from the literature show promising results in a variety of real-world applications, such as image classification BIBREF12 , text classification BIBREF13 , BIBREF16 , BIBREF3 , polarity classification BIBREF1 , BIBREF29 , BIBREF4 , BIBREF6 , BIBREF30 and others BIBREF32 .
General transfer learning approaches. Long et al. BIBREF12 proposed a novel transfer learning framework to model distribution adaptation and label propagation in a unified way, based on the structural risk minimization principle and the regularization theory. Shu et al. BIBREF5 proposed a method that bridges the distribution gap between the source domain and the target domain through affinity learning, by exploiting the existence of a subset of data points in the target domain that are distributed similarly to the data points in the source domain. In BIBREF7 , deep learning is employed to jointly optimize the representation, the cross-domain transformation and the target label inference in an end-to-end fashion. More recently, Sun et al. BIBREF8 proposed an unsupervised domain adaptation method that minimizes the domain shift by aligning the second-order statistics of source and target distributions, without requiring any target labels. Chang et al. BIBREF9 proposed a framework based on using a parallel corpus to calibrate domain-specific kernels into a unified kernel for leveraging graph-based label propagation between domains.
Cross-domain text classification. Joachims BIBREF13 introduced the Transductive Support Vector Machines (TSVM) framework for text classification, which takes into account a particular test set and tries to minimize the error rate for those particular test samples. Ifrim et al. BIBREF14 presented a transductive learning approach for text classification based on combining latent variable models for decomposing the topic-word space into topic-concept and concept-word spaces, and explicit knowledge models with named concepts for populating latent variables. Guo et al. BIBREF16 proposed a transductive subspace representation learning method to address domain adaptation for cross-lingual text classification. Zhuang et al. BIBREF3 presented a probabilistic model, by which both the shared and distinct concepts in different domains can be learned by the Expectation-Maximization process which optimizes the data likelihood. In BIBREF33 , an algorithm to adapt a classification model by iteratively learning domain-specific features from the unlabeled test data is described.
Cross-domain polarity classification. In recent years, cross-domain sentiment (polarity) classification has gained popularity due to the advances in domain adaptation on one side, and to the abundance of documents from various domains available on the Web, expressing positive or negative opinion, on the other side. Some of the general domain adaptation frameworks have been applied to polarity classification BIBREF3 , BIBREF33 , BIBREF9 , but there are some approaches that have been specifically designed for the cross-domain sentiment classification task BIBREF0 , BIBREF34 , BIBREF1 , BIBREF29 , BIBREF11 , BIBREF4 , BIBREF6 , BIBREF10 , BIBREF30 . To the best of our knowledge, Blitzer et al. BIBREF0 were the first to report results on cross-domain classification proposing the structural correspondence learning (SCL) method, and its variant based on mutual information (SCL-MI). Pan et al. BIBREF1 proposed a spectral feature alignment (SFA) algorithm to align domain-specific words from different domains into unified clusters, using domain-independent words as a bridge. Bollegala et al. BIBREF31 used a cross-domain lexicon creation to generate a sentiment-sensitive thesaurus (SST) that groups different words expressing the same sentiment, using unigram and bigram features as BIBREF0 , BIBREF1 . Luo et al. BIBREF4 proposed a cross-domain sentiment classification framework based on a probabilistic model of the author's emotion state when writing. An Expectation-Maximization algorithm is then employed to solve the maximum likelihood problem and to obtain a latent emotion distribution of the author. Franco-Salvador et al. BIBREF11 combined various recent and knowledge-based approaches using a meta-learning scheme (KE-Meta). They performed cross-domain polarity classification without employing any domain adaptation technique. More recently, Fernández et al. BIBREF6 introduced the Distributional Correspondence Indexing (DCI) method for domain adaptation in sentiment classification. The approach builds term representations in a vector space common to both domains where each dimension reflects its distributional correspondence to a highly predictive term that behaves similarly across domains. A graph-based approach for sentiment classification that models the relatedness of different domains based on shared users and keywords is proposed in BIBREF30 .
In recent years, methods based on string kernels have demonstrated remarkable performance in various text classification tasks BIBREF35 , BIBREF36 , BIBREF22 , BIBREF19 , BIBREF10 , BIBREF17 , BIBREF26 . String kernels represent a way of using information at the character level by measuring the similarity of strings through character n-grams. Lodhi et al. BIBREF35 used string kernels for document categorization, obtaining very good results. String kernels were also successfully used in authorship identification BIBREF22 . More recently, various combinations of string kernels reached state-of-the-art accuracy rates in native language identification BIBREF19 and Arabic dialect identification BIBREF17 . Interestingly, string kernels have been used in cross-domain settings without any domain adaptation, obtaining impressive results. For instance, Ionescu et al. BIBREF19 have employed string kernels in a cross-corpus (and implicitly cross-domain) native language identification experiment, improving the state-of-the-art accuracy by a remarkable INLINEFORM0 . Giménez-Pérez et al. BIBREF10 have used string kernels for single-source and multi-source polarity classification. Remarkably, they obtain state-of-the-art performance without using knowledge from the target domain, which indicates that string kernels provide robust results in the cross-domain setting without any domain adaptation. Ionescu et al. BIBREF17 obtained the best performance in the Arabic Dialect Identification Shared Task of the 2017 VarDial Evaluation Campaign BIBREF37 , with an improvement of INLINEFORM1 over the second-best method. It is important to note that the training and the test speech samples prepared for the shared task were recorded in different setups BIBREF37 , or in other words, the training and the test sets are drawn from different distributions. Different from all these recent approaches BIBREF19 , BIBREF10 , BIBREF17 , we use unlabeled data from the target domain to significantly increase the performance of string kernels in cross-domain text classification, particularly in English polarity classification.
String kernels. Kernel functions BIBREF38 capture the intuitive notion of similarity between objects in a specific domain. For example, in text mining, string kernels can be used to measure the pairwise similarity between text samples, simply based on character n-grams. Various string kernel functions have been proposed to date BIBREF35 , BIBREF38 , BIBREF19 . Perhaps one of the most recently introduced string kernels is the histogram intersection string kernel BIBREF19 . For two strings over an alphabet INLINEFORM0 , INLINEFORM1 , the intersection string kernel is formally defined as follows: DISPLAYFORM0 
where INLINEFORM0 is the number of occurrences of n-gram INLINEFORM1 as a substring in INLINEFORM2 , and INLINEFORM3 is the length of INLINEFORM4 . The spectrum string kernel or the presence bits string kernel can be defined in a similar fashion BIBREF19 .
Transductive string kernels. We present a simple and straightforward approach to produce a transductive similarity measure suitable for strings. We take the following steps to derive transductive string kernels. For a given kernel (similarity) function INLINEFORM0 , we first build the full kernel matrix INLINEFORM1 , by including the pairwise similarities of samples from both the train and the test sets. For a training set INLINEFORM2 of INLINEFORM3 samples and a test set INLINEFORM4 of INLINEFORM5 samples, such that INLINEFORM6 , each component in the full kernel matrix is defined as follows: DISPLAYFORM0 
where INLINEFORM0 and INLINEFORM1 are samples from the set INLINEFORM2 , for all INLINEFORM3 . We then normalize the kernel matrix by dividing each component by the square root of the product of the two corresponding diagonal components: DISPLAYFORM0 
We transform the normalized kernel matrix into a radial basis function (RBF) kernel matrix as follows: DISPLAYFORM0 
Each row in the RBF kernel matrix INLINEFORM0 is now interpreted as a feature vector. In other words, each sample INLINEFORM1 is represented by a feature vector that contains the similarity between the respective sample INLINEFORM2 and all the samples in INLINEFORM3 . Since INLINEFORM4 includes the test samples as well, the feature vector is inherently adapted to the test set. Indeed, it is easy to see that the features will be different if we choose to apply the string kernel approach on a set of test samples INLINEFORM5 , such that INLINEFORM6 . It is important to note that through the features, the subsequent classifier will have some information about the test samples at training time. More specifically, the feature vector conveys information about how similar is every test sample to every training sample. We next consider the linear kernel, which is given by the scalar product between the new feature vectors. To obtain the final linear kernel matrix, we simply need to compute the product between the RBF kernel matrix and its transpose: DISPLAYFORM0 
In this way, the samples from the test set, which are included in INLINEFORM0 , are used to obtain new (transductive) string kernels that are adapted to the test set at hand.
[!tpb] Transductive Kernel Algorithm
Input:
 INLINEFORM0 – the training set of INLINEFORM1 training samples and associated class labels;
 INLINEFORM0 – the set of INLINEFORM1 test samples;
 INLINEFORM0 – a kernel function;
 INLINEFORM0 – the number of test samples to be added in the second round of training;
 INLINEFORM0 – a binary kernel classifier.
Domain-Adapted Kernel Matrix Computation Steps:
 INLINEFORM0 INLINEFORM1 ; INLINEFORM2 ; INLINEFORM3 ; INLINEFORM4 
 INLINEFORM0 INLINEFORM1 INLINEFORM2 
 INLINEFORM0 INLINEFORM1 INLINEFORM2 
 INLINEFORM0 
 INLINEFORM0 
Transductive Kernel Classifier Steps:
 INLINEFORM0 
 INLINEFORM0 
 INLINEFORM0 
 INLINEFORM0 INLINEFORM1 
 INLINEFORM0 
 INLINEFORM0 
 INLINEFORM0 INLINEFORM1 the dual weights of INLINEFORM2 trained on INLINEFORM3 with the labels INLINEFORM4 
 INLINEFORM0 
 INLINEFORM0 ; INLINEFORM1 
 INLINEFORM0 INLINEFORM1 
 INLINEFORM0 
 INLINEFORM0 INLINEFORM1 sort INLINEFORM2 in descending order and return the sorted indexes
 INLINEFORM0 
 INLINEFORM0 
 INLINEFORM0 
 INLINEFORM0 
 INLINEFORM0 
Output:
 INLINEFORM0 – the set of predicted labels for the test samples in INLINEFORM1 . 
We next present a simple yet effective approach for adapting a one-versus-all kernel classifier trained on a source domain to a different target domain. Our transductive kernel classifier (TKC) approach is composed of two learning iterations. Our entire framework is formally described in Algorithm SECREF3 .
Notations. We use the following notations in the algorithm. Sets, arrays and matrices are written in capital letters. All collection types are considered to be indexed starting from position 1. The elements of a set INLINEFORM0 are denoted by INLINEFORM1 , the elements of an array INLINEFORM2 are alternatively denoted by INLINEFORM3 or INLINEFORM4 , and the elements of a matrix INLINEFORM5 are denoted by INLINEFORM6 or INLINEFORM7 when convenient. The sequence INLINEFORM8 is denoted by INLINEFORM9 . We use sequences to index arrays or matrices as well. For example, for an array INLINEFORM10 and two integers INLINEFORM11 and INLINEFORM12 , INLINEFORM13 denotes the sub-array INLINEFORM14 . In a similar manner, INLINEFORM15 denotes a sub-matrix of the matrix INLINEFORM16 , while INLINEFORM17 returns the INLINEFORM18 -th row of M and INLINEFORM19 returns the INLINEFORM20 -th column of M. The zero matrix of INLINEFORM21 components is denoted by INLINEFORM22 , and the square zero matrix is denoted by INLINEFORM23 . The identity matrix is denoted by INLINEFORM24 .
Algorithm description. In steps 8-17, we compute the domain-adapted string kernel matrix, as described in the previous section. In the first learning iteration (when INLINEFORM0 ), we train several classifiers to distinguish each individual class from the rest, according to the one-versus-all (OVA) scheme. In step 27, the kernel classifier INLINEFORM1 is trained to distinguish a class from the others, assigning a dual weight to each training sample from the source domain. The returned column vector of dual weights is denoted by INLINEFORM2 and the bias value is denoted by INLINEFORM3 . The vector of weights INLINEFORM4 contains INLINEFORM5 values, such that the weight INLINEFORM6 corresponds to the training sample INLINEFORM7 . When the test kernel matrix INLINEFORM8 of INLINEFORM9 components is multiplied with the vector INLINEFORM10 in step 28, the result is a column vector of INLINEFORM11 positive or negative scores. Afterwards (step 34), the test samples are sorted in order to maximize the probability of correctly predicted labels. For each test sample INLINEFORM12 , we consider the score INLINEFORM13 (step 32) produced by the classifier for the chosen class INLINEFORM14 (step 31), which is selected according to the OVA scheme. The sorting is based on the hypothesis that if the classifier associates a higher score to a test sample, it means that the classifier is more confident about the predicted label for the respective test sample. Before the second learning iteration, a number of INLINEFORM15 test samples from the top of the sorted list are added to the training set (steps 35-39) for another round of training. As the classifier is more confident about the predicted labels INLINEFORM16 of the added test samples, the chance of including noisy examples (with wrong labels) is minimized. On the other hand, the classifier has the opportunity to learn some useful domain-specific patterns of the test domain. We believe that, at least in the cross-domain setting, the added test samples bring more useful information than noise. We would like to stress out that the ground-truth test labels are never used in our transductive algorithm. Although the test samples are required beforehand, their labels are not necessary. Hence, our approach is suitable in situations where unlabeled data from the target domain can be collected cheaply, and such situations appear very often in practice, considering the great amount of data available on the Web.
Data set. For the cross-domain polarity classification experiments, we use the second version of Multi-Domain Sentiment Dataset BIBREF0 . The data set contains Amazon product reviews of four different domains: Books (B), DVDs (D), Electronics (E) and Kitchen appliances (K). Reviews contain star ratings (from 1 to 5) which are converted into binary labels as follows: reviews rated with more than 3 stars are labeled as positive, and those with less than 3 stars as negative. In each domain, there are 1000 positive and 1000 negative reviews.
Baselines. We compare our approach with several methods BIBREF1 , BIBREF31 , BIBREF11 , BIBREF8 , BIBREF10 , BIBREF39 in two cross-domain settings. Using string kernels, Giménez-Pérez et al. BIBREF10 reported better performance than SST BIBREF31 and KE-Meta BIBREF11 in the multi-source domain setting. In addition, we compare our approach with SFA BIBREF1 , CORAL BIBREF8 and TR-TrAdaBoost BIBREF39 in the single-source setting.
Evaluation procedure and parameters. We follow the same evaluation methodology of Giménez-Pérez et al. BIBREF10 , to ensure a fair comparison. Furthermore, we use the same kernels, namely the presence bits string kernel ( INLINEFORM0 ) and the intersection string kernel ( INLINEFORM1 ), and the same range of character n-grams (5-8). To compute the string kernels, we used the open-source code provided by Ionescu et al. BIBREF19 , BIBREF40 . For the transductive kernel classifier, we select INLINEFORM2 unlabeled test samples to be included in the training set for the second round of training. We choose Kernel Ridge Regression BIBREF38 as classifier and set its regularization parameter to INLINEFORM3 in all our experiments. Although Giménez-Pérez et al. BIBREF10 used a different classifier, namely Kernel Discriminant Analysis, we observed that Kernel Ridge Regression produces similar results ( INLINEFORM4 ) when we employ the same string kernels. As Giménez-Pérez et al. BIBREF10 , we evaluate our approach in two cross-domain settings. In the multi-source setting, we train the models on all domains, except the one used for testing. In the single-source setting, we train the models on one of the four domains and we independently test the models on the remaining three domains.
Results in multi-source setting. The results for the multi-source cross-domain polarity classification setting are presented in Table TABREF8 . Both the transductive presence bits string kernel ( INLINEFORM0 ) and the transductive intersection kernel ( INLINEFORM1 ) obtain better results than their original counterparts. Moreover, according to the McNemar's test BIBREF41 , the results on the DVDs, the Electronics and the Kitchen target domains are significantly better than the best baseline string kernel, with a confidence level of INLINEFORM2 . When we employ the transductive kernel classifier (TKC), we obtain even better results. On all domains, the accuracy rates yielded by the transductive classifier are more than INLINEFORM3 better than the best baseline. For example, on the Books domain the accuracy of the transductive classifier based on the presence bits kernel ( INLINEFORM4 ) is INLINEFORM5 above the best baseline ( INLINEFORM6 ) represented by the intersection string kernel. Remarkably, the improvements brought by our transductive string kernel approach are statistically significant in all domains.
Results in single-source setting. The results for the single-source cross-domain polarity classification setting are presented in Table TABREF9 . We considered all possible combinations of source and target domains in this experiment, and we improve the results in each and every case. Without exception, the accuracy rates reached by the transductive string kernels are significantly better than the best baseline string kernel BIBREF10 , according to the McNemar's test performed at a confidence level of INLINEFORM0 . The highest improvements (above INLINEFORM1 ) are obtained when the source domain contains Books reviews and the target domain contains Kitchen reviews. As in the multi-source setting, we obtain much better results when the transductive classifier is employed for the learning task. In all cases, the accuracy rates of the transductive classifier are more than INLINEFORM2 better than the best baseline string kernel. Remarkably, in four cases (E INLINEFORM3 B, E INLINEFORM4 D, B INLINEFORM5 K and D INLINEFORM6 K) our improvements are greater than INLINEFORM7 . The improvements brought by our transductive classifier based on string kernels are statistically significant in each and every case. In comparison with SFA BIBREF1 , we obtain better results in all but one case (K INLINEFORM8 D). Remarkably, we surpass the other state-of-the-art approaches BIBREF8 , BIBREF39 in all cases.
In this paper, we presented two domain adaptation approaches that can be used together to improve the results of string kernels in cross-domain settings. We provided empirical evidence indicating that our framework can be successfully applied in cross-domain text classification, particularly in cross-domain English polarity classification. Indeed, the polarity classification experiments demonstrate that our framework achieves better accuracy rates than other state-of-the-art methods BIBREF1 , BIBREF31 , BIBREF11 , BIBREF8 , BIBREF10 , BIBREF39 . By using the same parameters across all the experiments, we showed that our transductive transfer learning framework can bring significant improvements without having to fine-tune the parameters for each individual setting. Although the framework described in this paper can be generally applied to any kernel method, we focused our work only on string kernel approaches used in text classification. In future work, we aim to combine the proposed transductive transfer learning framework with different kinds of kernels and classifiers, and employ it for other cross-domain tasks.

Figure and table captions:
Table 1. Multi-source cross-domain polarity classification accuracy rates (in %) of our transductive approaches versus a state-of-the-art baseline based on string kernels [13], as well as SST [3] and KE-Meta [12]. The best accuracy rates are highlighted in bold. The marker * indicates that the performance is significantly better than the best baseline string kernel according to a paired McNemar’s test performed at a significance level of 0.01.
Table 2. Single-source cross-domain polarity classification accuracy rates (in %) of our transductive approaches versus a state-of-the-art baseline based on string kernels [13], as well as SFA [32], CORAL [40] and TR-TrAdaBoost [15]. The best accuracy rates are highlighted in bold. The marker * indicates that the performance is significantly better than the best baseline string kernel according to a paired McNemar’s test performed at a significance level of 0.01.

Questions about this paper:
How long is the dataset?
What is a string kernel?

Answers:
8000
String kernel is a technique that uses character n-grams to measure the similarity of strings