Bag-of-Embeddings for Text Classification

1 Introduction

Text classification is important for a wide range of web applications, such as web search [Chekuri et al., 1997], opinion mining [Vo and Zhang, 2015], and event detection [Kumaran and Allan, 2004]. Dominant approaches in the literature treat text classification as a standard classification problem, using supervised or semi-supervised machine learning methods. A key research topic is the design of effective feature representations.

Words are central to text classification. Bag-of-words models [Harris, 1954], such as Naive Bayes [Mccallum and Nigam, 1998] can give highly competitive baselines compared with much more sophisticated models with complex feature representations. The main intuition behind is that there is typically a salient set of words that signal each document class. For example, in news the words "coach", "sport", "basketball" occur relatively frequently in sports, and the words "chipset", "compiler" and "Linux" are relatively unique for information technology.

⇤Corresponding author: Xingyuan Chen (1045258214@qq.com)

More sources of information have been explored for text classification, including parts of speech [Lewis, 1995], syntax structures [Post and Bergsma, 2013; Tetsuji et al., 2010] and semantic compositionality [Moilanen and Pulman, 2007]. However, such features have demonstrated limited gains over bag-of-words features [Wang and Manning, 2012]. One useful feature beyond bag-of-words is bag-of-ngrams. Wang and Manning [2012] show that bigram features are particularly useful for sentiment classification. Bigrams offer a certain degree of compositionality while being relatively less sparse compared with larger n-gram features. For example, the bigram "abnormal return" strongly indicates finance, although both "abnormal" and "return" can be common across difference classes. Similar examples include "world cup" and "large bank", where bi-grams indicate text classes, but the words do not.

One intuitive reason behind the strength of bigrams is that they resolve the ambiguity of polysemous words. In the above examples the words "return", "cup", and "bank" have different meanings under different document classes, and the correct identification of their word sense under a ngram context is useful for identifying the document class. For example, when the word "bank" exists under a context with words such as "card" and "busy", it strongly indicates the "finance" sense. This fact suggests a simple extension to bag-of-word features by incorporating context and word sense information. We propose a natural extension to the skip-gram word embedding model [Mikolov et al., 2013] to this end.

Word embeddings are low-dimensional, dense vector representation of words, first proposed in neural language models [Bengio et al., 2003]. Traditionally, embeddings are trained during the training of a neural language model as a part of the model parameters. Mikolov et al. [2013] define specific objective functions for efficient training of word embeddings, by simplifying the original training objective of a neural language model. The skip-gram model trains word embeddings by maximizing the probabilities of words given their context windows. Two sets of embeddings are defined for the same word as a target word and a context word, respectively. The probability of a target word is estimated by the cosine similarities between the target embedding and the content embeddings of its context words. This offers a way to estimate word probability via the embedding probability that readily integrates context information.

To further integrate word sense information, we make a simple extension by training multi-prototype target word embeddings, with one distinct vector trained for a word under each class. The context vectors of words remain the same across different classes. Here by associating word senses with document classes, we make the assumption that each word exhibits one sense in each document class, and the sense of a word differs across different classes. This assumption is highly coarse-grained and does not correspond to the definition of word senses in linguistics. However, it empirically works effectively, and we find that the definition of sense here can capture subtle differences between word meanings across different document classes.

Under the above assumptions, the probability of a class given a document can be calculated from the probabilities of the embeddings of each word under this class. Since the probability of each word embeddings is calculated separately, we call this model a bag-of-embeddings model. Training requires text corpora with class labels, some of them are obtained from naturally labeled [Go et al., 2009] and some are hand-labeled [Lewis, 1995]. The bag-of-embeddings model is conceptually simple, with the only parameters being word embeddings. We show that maximum-likelihood training for document classification is consistent with the skip-gram objective for training multi-prototype word embeddings.

Experiments on two standard document classification benchmark data show that our model achieve higher accuracies and macro-F1 scores compared than state-ofthe-art models. Our method achieves the best reported accuracies for both the balanced and the imbalanced datasets. The source code of this paper is released at https://github.com/hiccxy/Bag-of-embedding-fortext-classification.

2 RelatedWork

Text classification has traditionally been solved as a standard classification task, using supervised learning approaches such as Naive Bayes [Mccallum and Nigam, 1998], logistic regression [Nigam et al., 1999], and support vector machines [Joachims, 1998]. Word features, and in particular bag-ofwords features, have been used for classification. There have been research efforts to incorporate more complex features into text classification models. Lewis [1995] uses parts-ofspeech and phrase information for text categorization; Tetsuji et al. [2010] use dependency tree features for sentiment classification; Post and Bergsma [2013] integrate syntax into text classification models by explicit features and implicit kernels; Moilanen and Pulman [2007] model semantic compositionality for sentiment classification. Wang and Manning [2012] show that bag-of-words and bigram features can give competitive accuracies compared with such more complex features.

Distributed word representations [Bengio et al., 2003; Collobert et al., 2011; Mikolov et al., 2013] have been typically used as additional features in discrete models for semisupervised learning, or as inputs to neural network models. For text classification, word embeddings have mostly been used as inputs to neural models such as recursive tensor networks [Socher et al., 2011], dynamic pooling network

[Kalchbrenner et al., 2014] and deep convolutional neural network [Santos and Gatti, 2014]. There has also been work on directly learning distributed vector representations of paragraphs and sentences [Le and Mikolov, 2014], which has been shown as useful as the above mentioned neural network models for text classification. Such neural network result in vector representation of text data. Along this line, Tang et al. [2014] is the closet in spirit to our work. They learn text embeddings specifically for end tasks, such as classification. We also learn word embeddings specifically for text classification. However, rather than learning one vector for each word, which Tang et al. [2014] do, we learn multi-prototype embeddings, with certain words having multiple vector forms according to the text class. In addition, we have a very simple document model, with the only parameters being word vectors. The simplicity demonstrates the effectiveness of incorporating text class information into distributed word representation.

Our work is also related to prior work on multi-prototype word embeddings [Reisinger and Mooney, 2010; Huang et al., 2012; Tian et al., 2014]. Previous methods define word prototypes according to word senses from ontologies, or induce word senses automatically. They share a more linguistic focus on word similarities. In contrast, our objective is to improve text classification performance, and hence we train multi-prototype embeddings based on text classes.

3 Method

3.1 The Skip-gramModel

Our bag-of-embeddings model extends the skip-gram model [Mikolov et al., 2013], which is a simplification of neural language models for efficient training of word embeddings. The skip-gram model works by maximizing the probabilities of words being predicted by their context words.

In particular, two sets of embeddings are defined for each word w, when w is used as the output target word and as the input context word, respectively. We use ~v(w) and ~u(w) to denote target (output) embedding vector and context (input) embedding vector of w, respectively.

Given a target word w and a context w0 of w, the probability of ~v(w) given ~u(w0 ) is defined based on the cosine similarity between ~v(w) and ~u(w0 ), as follows,

where V is the vocabulary.

The model can be regarded as a crude approximation of a language model estimating the probability of a sentence s = w1w2▷▷▷w♣s♣ by

where t(wi↪ s) is the context of wi in s, which typical includes T words before wi and T words after wi. P(~v(wi)♣t(wi↪ s)) is estimated by predicting ~v(wi) using each word w0 in t(wi↪ s).

This approximation does not give a highly accurate language model, but can be used to train word embeddings efficiently. The resulting embeddings can be used as input to train more sophisticated neural language model or to solve other NLP tasks [Mikolov et al., 2013].

Training is achieved by maximizing the likelihood of raw text using stochastic gradient descent, which is equivalent to maximizing logP(~v(wi)♣~u(w0 )) for all wi and w0 in a corpus. Because gradients to the probability in Equation (1) requires summary over the vocabulary, the skip-gram model uses a rough approximation to the noise contrastive estimation (NCE) method (Gutmann and Hyvarinen, 2010), which instead maximizes

Here σ is the sigmoid activation function, Pn(w) is a distribution for negative samples, which is typically the unigram distribution raised to the 3◁4th power (Mikolov et al., 2013), and l is the number of negative samples, set to a small number below 20. Equation 2 approximates the log probability P(~v(wi)~u(w0 )) by contrastive estimation between seen words and negative samples from a noise distribution, where l ! 1, the gradient closely approximates the gradient of P (~v(wi)~u(w0 )).

3.2 The Bag-of-embeddings Model for Text Classification

The goal of text categorization is the classification of a given document d 2 D into a fixed number of predefined categories C, where D is the set of documents. Although according to [Joachims, 1998], each document d can be in multiple, exactly one, or no category at all, in this paper we simplify to find the most likely class c 2 C for d. We find c by using

We estimate the class probability P(c♣d) by estimating the probability of d's vector form under c, denoted as ~v(d↪ c). Denoting the words in d as w1↪w2↪ ▷▷▷↪w♣d♣, where wi 2 V , ~v(d↪ c) consists of the class-specific target embedding sequence of w1↪ w2↪ ▷▷▷↪ w♣d♣.

Further by assuming that the class-specific target embeddings are conditionally independent i.e. bag-of-embeddings, it follows that

Now following the skip-grammodel, assume that the probability of ~v(wi↪ c) depends only on the context window t(wi↪ d) = wi-T ↪wi-T+1↪ ▷▷▷↪wi-1↪wi+1↪ ▷▷▷↪wi+T (i.e. 2T is the context window size), we have

We use the skip-gram model to estimate this multiprototype embedding probability. In particular, denoting the context embedding of a word w as ~u(w), P(~v(wi↪ c)♣t(wi↪ d)) is estimated by

From the above equation, it can be seen that the bag-ofembeddings model is similar to the skip-gram model in the definition of target and context embeddings. However, it is different in that the target embeddings are class-dependent, and each word can have different target embeddings in different classes. On the other hand, each word has a unique context embedding across classes.

Figure 1 gives an illustration of this difference. Now given P(~v(wi↪ c)♣t(wi↪ d)), the document probability

Correspondingly,

The last equation corresponds to the estimation of the log probability, which is more efficient than the estimation of the conditional probability.

The parameters u(w) and v(w↪ ci) in Equation 3, which is used for predicting, are trained in a supervised way described in the following subsection.

3.3 Training

Given a set of labeled documents D = ¶(d1↪ c1)↪ (d2↪ c2)↪ ▷▷▷↪ (dN↪ cN)♦, the bag-of-embeddings model is trained by maximizing its likelihood function By using stochastic gradient descent, maximizing P(D) consists of iteratively maximizing each P(~v(wi↪ ck)♣~u(w0 )). This is consistent in form to the objective of the skip-gram model, which maximizes the probability of each word given each context word. The only difference is that the target word vector depends on the label class in the bag-ofembedding model. We follow the skip-gram model and train P(~v(wi↪ ck)♣~u(w0 )) using a simplification of NCE by negative sampling, where the objective is

Consistent with the skip-gram model, σ is the sigmoid function, and Pn(w) is a noise distribution of words. Note, however, that in this equation, the context word w0 is sampled instead of the target word, because it is relatively more difficult to find a distribution of negative examples that includes the class label. Pn(w) being unigram distribution to the 3◁4th power, and all parameters setting are the same as Mikolov et al. [2013] except the iteration number 1 . This is because our corpus is much smaller than theirs. For the parameters, we set l = 5, the iteration number to 5, the size of context window to 10 and the dimensions of word vector to 100.

3.4 Correlation with Skip-gram and Bag-of-words

The bag-of-embeddings model is closely related to the skipgram model and bag-of-words model. Compared with the bag-of-words model for document classification, the bag-ofembeddings model also makes the Naive Bayes assumption, by treating the target embedding vector of each word in the document as being independent of each other. On the other hand, it is different from the bag-of-words model in that the model integrates context information. Rather than predicting the text class using unigram alone, it relies on the distributional similarity between each target word embedding and the context embeddings of words in a context window. With respect to feature space, the bag-of-embeddings model is a much richer model with hundreds of dense parameters to represent each word. Our experiments show that it outperforms a bag-of-words model significantly.

The parameters of the bag-of-embeddings model are target and context embedding vectors. This is closely related to the skip-gram model. The main difference in terms of embeddings is that the bag-of-embeddings model integrates document class information, training multiple-prototype embeddings for each word. The training methods of the skipgram model and the bag-of-embeddings are shown in Figure 2(a) and 2(b), respectively. Compared with the skip-gram model, the target embeddings of the bag-of-embeddings contain class labels. On the other hand, the context embeddings remain single-prototype, which serves to connect the embeddings space for target word between different classes. One additional difference between the bag-of-embeddings model and the skip-gram model is that the former is designed for document classification, but the latter is specifically designed to train embeddings.

1 Empirically, the sampling method gives highly competitive accuracy when the iteration number is greater than 10 and the performance is very stable.

In our experiments we find that the classification accuracies can be improved by 0.2% to 0.5% by adding w itself into the targets in Figure 2(b), and therefore take this variation in choose the context window t(wi↪ d).

4 Experiments

We evaluate our models on two multi-class text classification datasets, one is imbalanced and the other is nearly balanced. The experimental setup is as follows.

4.1 Experiment Setup

Data Sets We choose the twenty newsgroup (20NG) 2 test [Lang, 1995] for multi-class classification. We use the "bydate" data, which consists of 11,314 training instances and 7,532 test instances, which are partitioned (nearly) evenly across the classes. For training, the largest class has 600 instances and the smallest class has 377 instances.

For imbalanced classification, Lewis [1995] introduced the Reuters-21578 corpus 3 . We choose this benchmark dataset as follow Debole and Sebastiani [2005] and perform the R8 evaluation requires that each class should have at least one training and one test example and only the most frequent eight categories (i.e. R8) are evaluated. R8 consists of 5,485 documents for training and 2,189 for testing. For training, the largest class has 2,840 instances and the smallest class has 41

2 http://qwone.com/˜jason/20Newsgroups/

3 http://www.daviddlewis.com/resources/testcollections/ reuters21578/

instances. The pre-processing is conducted by turning all letters to lowercase, removing all the words which occurs less than five times and replacing all punctuation with space.

Evaluation Metrics We use the standard accuracy (AC), which is defined as the number of correctly predicted documents out of all test documents. Precision, recall and F1 score are also used. The macro-average F1- score (MF1) takes into account the skewed class label distributions by weighting each class uniformly.

Baseline Models We compare our models with several strong baseline models, including Support Vector Machines, and two state-of-the-art text representation models.

• ÷ SVM: We take a bag-of-words baseline using SVM, which outperforms the Naive Bayes model. Follows Wang et al. [2013], we use LIBSVM 4 with a linear kernel and optimize the parameter C 2 1e -4↪ ▷▷▷↪ 1e +4 by ten-fold cross-validation. Bag-of-words features are used to represent the documents. It is denoted as "BoWSVM" in Table 1.
• ÷ TWE: Liu et al. [2015] employ latent topic models to assign topics to each word in the whole corpus, and learn topical word embeddings based on both words and their topics (i.e. each word has different embeddings under different topics). Three models are proposed, and the best one TWE-1, regards each topic as a pseudo word and learns topic embeddings and word embeddings separately. The model outperforms the paragraph vector model of Le and Mikolov [2014].
• ÷ GoW: Rousseau et al. [2015] propose three graph-ofwords approaches to capture the distance dependency between words. A linear SVM is used as classifier and their best model served as our baseline. It is denoted as "GoW-SVM" in Table 1.

4.2 Results

Table 1 summaries the performances of our model and the baseline models, where "BoE" denotes our proposed bag-ofembedding model. Our model outperforms the state-of-theart models TWE and GoW on the balanced and the imbalanced data sets, respectively. For both data sets, the bag-ofembeddings model gives the best results that we are aware of the in the literature.

Tables 2 and 3 show detailed comparisons between our bag-of-embeddings model and the bag-of-words SVM on the balanced and imbalanced data sets, respectively, where the higher precision or recall is shown in bold. Our model gives higher precision for most of the classes, and higher recall for nearly all the classes. This demonstrates the effectiveness of the bag-of-embeddings model in leveraging context information. The higher recall also shows the advantage of dense features in reducing feature sparsity as compared with discrete bag-of-word features.

4 https://www.csie.ntu.edu.tw/˜cjlin/libsvm/

4.3 Analysis

To better understand the mechanism of disambiguation by the bag-of-embeddings model, we analyze the interactions between target and context vectors, and the correlation between target embedding vectors under different classes. Figure 3 (a) and (b) shows the probabilities of the words "win" and "runs" as calculated using different context word embeddings, respectively. We choose the most popular context words from different classes by following Lacoste-Julien et al. [2008].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 19 20

The X-axis represents the target embeddings in the 20 classes in Table 2, in the same order.

It can be seen from the Figure 3 that the same words have highly different probabilities across different classes, reflected by the inner product of their class-sensitive target embedding and a context word embedding. In addition, context words have a large influence on the distributions. For example, the word "win" has a large probability under the computer graphics class when the context word is "image", yet large probabilities in the two sports classes when the context word are "baseball" and "hockey", respectively. This demonstrates how word and context information interact in the bagof-embeddings model. In contrast, a bag-of-word model relies on words themselves rather than word-context relations for disambiguating document classes.

Within each class, the training of target embedding vectors is essentially the same as the skip-grammodel, and therefore the embeddings trained for the classification model should exhibit a certain degree of distributed similarities. Table 4 confirms the intuition. For example, under various classes, the closest words to the word "win" include "windows", "dos" and "won", which are synonyms or morphological variations of the word, and "use", "chance" and "game", which are syntactics or semantically related words in a distributed context. In addition, the closest words of the same word differ when the class change, again showing the class sensitivity of the embeddings. For example, under class 3, namely comp.os.ms-windows.misc in Table 2, the word "win" is close to "windows", "dos" and "program". On the other hand, under class 10, rec.sports.baseball, "win" is close to "team", "pitching" and "game", demonstrating class-specific distributional similarity.

5 Conclusion and FutureWork

We built a text classifier by using a Naive Bayes model with bag-of-embeddings probabilities. Compared with bagof-word models, the bag-of-embeddings model exploits contextual information by deriving the probabilities of classsensitive embedding vectors from their inner product with context words. Our model is conceptually simple, with only parameters being embedding vectors, trained using a variation of the skip-gram method. Experiments on two standard datasets showed that our model outperforms state-of-the-art methods for both balanced and imbalanced data.

Future work includes two directions. First, we would consider leveraging unlabeled data for semi-supervised [Tang et al., 2015]. Second, we would exploit neural documents models, which contains richer parameters spaces by capturing word relations, for potentially better accuracies.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (61373056, 61272221 and 61272233).