On the effectiveness of feature set augmentation using clusters of word embeddings

Abstract: Word clusters have been empirically shown to offer important performance improvements on various tasks. Despite their importance, their incorporation in the standard pipeline of feature engineering relies more on a trial-and-error procedure where one evaluates several hyper-parameters, like the number of clusters to be used. In order to better understand the role of such features we systematically evaluate their effect on four tasks, those of named entity segmentation and classification as well as, those of five-point sentiment classification and quantification. Our results strongly suggest that cluster membership features improve the performance.

Many research attempts have proposed novel features that improve the performance of learning algorithms in particular tasks. Such features are often motivated by domain knowledge or manual labor. Although useful and often state-of-the-art, adapting such solutions on NLP systems across tasks can be tricky and time-consuming BIBREF0 . Therefore, simple yet general and powerful methods that perform well across several datasets are valuable BIBREF1 .
An approach that has become extremely popular lately in NLP tasks, is to train word embeddings in an unsupervised way. These embeddings are dense vectors that project words or short text spans like phrases in a vector space where dimensions are supposed to capture text properties. Such embeddings can then be used either as features with off-the-shelf algorithms like Support Vector Machines, or to initialize deep learning systems BIBREF2 . However, as shown in BIBREF3 linear architectures perform better in high-dimensional discrete spaces compared to continuous ones. The latter is probably the main reason of the high performance of the vector space model BIBREF4 in tasks like text classification with linear models like SVMs. Using linear algorithms, while taking advantage of the expressiveness of text embeddings is the focus of this work.
In this paper, we explore a hybrid approach, that uses text embeddings as a proxy to create features. Motivated by the argument that text embeddings manage to encode the semantics of text, we explore how clustering text embeddings can impact the performance of different NLP tasks. Although such an approach has been used in different studies during feature engineering, the selection of word vectors and the number of clusters remain a trial-end-error procedure. In this work we present an empirical evaluation across diverse tasks to verify whether and when such features are useful.
Word clusters have been used as features in various tasks like Part-of-Speech tagging and NER. Owoputi et al. Owoputi13 use Brown clusters BIBREF5 in a POS tagger showing that this type of features carry rich lexical knowledge as they can substitute lexical resources like gazetteers. Kiritchenko et al. KiritchenkoZM14 discusses their use on sentiment classification while Hee et al. HeeLH16 incorporate them in the task of irony detection in Twitter. Ritter et al. Ritter2011 inject also word clusters in a NER tagger. While these works show that word clusters are beneficial no clear guidelines can be concluded of how and when to use them.
In this work, we empirically demonstrate that using different types of embeddings on three NLP tasks with twitter data we manage to achieve better or near to the state-of-the art performance on three NLP tasks: (i) Named Entity Recognition (NER) segmentation, (ii) NER classification, (iii) fine-grained sentiment analysis and (iv) fine-grained sentiment quantification. For each of the three tasks, we achieve higher performance than without using features which indicates the effectiveness of the cluster membership features. Importantly, our evaluation compared to previous work BIBREF6 who focus on old and well studied datasets uses recent and challenging datasets composed by tweets. The obtained results across all the tasks permits us to reveal important aspects of the use of word clusters and therefore provide guidelines. Although our obtained scores are state-of-the-art, our analysis reveals that the performance in such tasks is far from perfect and, hence, identifies that there is still much space for improvement and future work.
Word embeddings associate words with dense, low-dimensional vectors. Recently, several models have been proposed in order to obtain these embeddings. Among others, the skipgram (skipgram) model with negative sampling BIBREF7 , the continuous bag-of-words (cbow) model BIBREF7 and Glove (glove) BIBREF8 have been shown to be effective. Training those models requires no annotated data and can be done using big amounts of text. Such a model can be seen as a function INLINEFORM0 that projects a word INLINEFORM1 in a INLINEFORM2 -dimensional space: INLINEFORM3 , where INLINEFORM4 is predefined. Here, we focus on applications using data from Twitter, which pose several difficulties due to being particularly short, using creative vocabulary, abbreviations and slang.
For all the tasks in our experimental study, we use 36 millions English tweets collected between August and September 2017. A pre-processing step has been applied to replace URLs with a placeholder and to pad punctuation. The final vocabulary size was around 1.6 millions words. Additionally to the in-domain corpus we collected, we use GloVe vectors trained on Wikipedia articles in order to investigate the impact of out-of-domain word-vectors.
We cluster the embeddings with INLINEFORM0 -Means. The k-means clusters are initialized using “k-means++” as proposed in BIBREF9 , while the algorithm is run for 300 iterations. We try different values for INLINEFORM1 . For each INLINEFORM2 , we repeat the clustering experiment with different seed initialization for 10 times and we select the clustering result that minimizes the cluster inertia.
We evaluate the proposed approach for augmenting the feature space in four tasks: (i) NER segmentation, (ii) NER classification, (iii) fine-grained sentiment classification and (iv) fine-grained sentiment quantification. The next sections present the evaluation settings we used. For each of the tasks, we use the designated training sets to train the learning algorithms, and we report the scores of the evaluation measures used in the respective test parts.
NER concerns the classification of textual segments in a predefined set of categories, like persons, organization and locations. We use the data of the last competition in NER for Twitter which released as a part of the 2nd Workshop on Noisy User-generated Text BIBREF10 . More specifically, the organizers provided annotated tweets with 10 named-entity types (person, movie, sportsteam, product etc.) and the task comprised two sub-tasks: 1) the detection of entity bounds and 2) the classification of an entity into one of the 10 types. The evaluation measure for both sub-tasks is the F INLINEFORM0 measure.
The following is an example of a tweet which contains two named entities. Note that named entities may span several words in the text:
 INLINEFORM0 tonite ... 90 's music .. oldskool night wiith INLINEFORM1 
Our model for solving the task is a learning to search approach. More specifically we follow BIBREF11 which has been ranked 2nd among 10 participants in the aforementioned competition BIBREF10 . The model uses handcrafted features like n-grams, part-of-speech tags, capitalization and membership in gazetteers. The algorithm used belongs to the family of learning to search for structured prediction tasks BIBREF12 . These methods decompose the problem in a search space with states, actions and policies and then learn a hypothesis controlling a policy over the state-action space. The BIO encoding is used for attributing the corresponding labels to the tokens where B-type is used for the first token of the entity, I-type for inside tokens in case of multi-term entities and O for non entity tokens.
Tables TABREF6 and TABREF7 present the results for the different number of clusters across the three vector models used to induce the clusters. For all the experiments we keep the same parametrization for the learning algorithm and we present the performance of each run on the official test set.
Regarding the segmentation task we notice that adding word clusters as features improve the performance of the best model up to 1.1 F-score points while it boosts performance in the majority of cases. In only one case, for glove INLINEFORM0 vectors, there is a drop across all number of clusters used.
As for the number of clusters, the best results are generally obtained between 250 and 1000 classes for all word vector models. These dimensions seem to be sufficient for the three-class sub-task that we deal with. The different models of word vectors perform similarly and thus one cannot privilege a certain type of word vectors. Interestingly, the clusters learned on the Wikipedia GloVe vectors offer competitive performance with respect to the in-domain word vectors used for the other cases showing that one can rely to out-of-domain data for constructing such representations.
Concerning the classification task (Table TABREF7 ) we generally observe a drop in the performance of the tagger as we deal with 10 classes. This essentially corresponds to a multi-class problem with 21 classes: one for the non-entity type and two classes for each entity type. In this setting we notice that the best results are obtained in most cases for higher number of classes (1000 or 2000) possibly due to a better discriminatory power in higher dimensions. Note also, that in some cases the addition of word cluster features does not necessarily improve the performance. Contrary, it may degrade it as it is evident in the case of glove INLINEFORM0 word clusters. Like in the case of segmentation we do not observe a word vector model that clearly outperforms the rest. Finally, we note the same competitive performance of the Wikipedia word clusters and notably for the glove INLINEFORM1 clusters which obtain the best F1-score.
The task of fine grained sentiment classification consists in predicting the sentiment of an input text according to a five point scale (sentiment INLINEFORM0 {VeryNegative, Negative, Neutral, Positive, VeryPositive}). We use the setting of task 4 of SemEval2016 “Sentiment Analysis in Twitter” and the dataset released by the organizers for subtask 4 BIBREF13 .
In total, the training (resp. test) data consist of 9,070 (resp. 20,632) tweets.
The evaluation measure selected in BIBREF13 for the task in the macro-averaged Mean Absolute Error (MAE INLINEFORM0 ). It is a measure of error, hence lower values are better. The measure's goal is to take into account the order of the classes when penalizing the decision of a classifier. For instance, misclassifying a very negative example as very positive is a bigger mistake than classifying it as negative or neutral. Penalizing a classifier according to how far the predictions are from the true class is captured by MAE INLINEFORM1 BIBREF14 . Also, the advantage of using the macro- version instead of the standard version of the measure is the robustness against the class imbalance in the data.
Learning algorithm To demonstrate the efficiency of cluster membership features we rely on the system of BIBREF15 which was ranked 1st among 11 participants and uses a Logistic Regression as a learning algorithm. We follow the same feature extraction steps which consist of extracting n-gram and character n-gram features, part-of-speech counts as well as sentiment scores using standard sentiment lexicons such as the Bing Liu's BIBREF16 and the MPQA lexicons BIBREF17 . For the full description, we refer the interested reader to BIBREF15 .
To evaluate the performance of the proposed feature augmentation technique, we present in Table TABREF10 the macro-averaged Mean Absolute Error scores for different settings on the official test set of BIBREF13 . First, notice that the best score in the test data is achieved using cluster membership features, where the word embeddings are trained using the skipgram model. The achieved score improves the state-of-the art on the dataset, which to the best of our knowledge was by BIBREF15 . Also, note that the score on the test data improves for each type of embeddings used, which means that augmenting the feature space using cluster membership features helps the sentiment classification task.
Note, also, that using the clusters produced by the out-of-domain embeddings trained on wikipedia that were released as part of BIBREF8 performs surprisingly well. One might have expected their addition to hurt the performance. However, their value probably stems from the sheer amount of data used for their training as well as the relatively simple type of words (like awesome, terrible) which are discriminative for this task. Lastly, note that in each of the settings, the best results are achieved when the number of clusters is within INLINEFORM0 as in the NER tasks. Comparing the performance across the different embeddings, one cannot claim that a particular embedding performs better. It is evident though that augmenting the feature space with feature derived using the proposed method, preferably with in-domain data, helps the classification performance and reduces MAE INLINEFORM1 .
From the results of Table TABREF10 it is clear that the addition of the cluster membership features improves the sentiment classification performance. To better understand though why these clusters help, we manually examined a sample of the words associated with the clusters. To improve the eligibility of those results we first removed the hashtags and we filter the results using an English vocabulary. In Table TABREF11 we present sample words from two of the most characteristic clusters with respect to the task of sentiment classification. Notice how words with positive and negative meanings are put in the respective clusters.
Quantification is the problem of estimating the prevalence of a class in a dataset. While classification concerns assigning a category to a single instance, like labeling a tweet with the sentiment it conveys, the goal of quantification is, given a set of instances, to estimate the relative frequency of single class. Therefore, sentiment quantification tries to answer questions like “Given a set of tweets about the new iPhone, what is the fraction of VeryPositive ones?”. In the rest, we show the effect of the features derived from the word embeddings clusters in the fine-grained classification problem, which was also part of the SemEval-2016 “Sentiment Analysis in Twitter” task BIBREF13 .
Learning Algorithm To perform the quantification task, we rely on a classify and count approach, which was shown effective in a related binary quantification problem BIBREF15 . The idea is that given a set of instances on a particular subject, one first classifies the instances and then aggregates the counts. To this end, we use the same feature representation steps and data with the ones used for fine grained classification (Section 3.2). Note that the data of the task are associated with subjects (described in full detail at BIBREF13 ), and, hence, quantification is performed for the tweets of a subject. For each of the five categories, the output of the approach is a 5-dimensional vector with the estimated prevalence of the categories.
The evaluation measure for the problem is the Earth Movers Distance (EMD) BIBREF18 . EMD is a measure of error, hence lower values are better. It assumes ordered categories, which in our problem is naturally defined. Further assuming that the distance of consecutive categories (e.g., Positive and VeryPositive) is 1, the measure is calculated by: INLINEFORM0 
where INLINEFORM0 is number of categories (five in our case) and INLINEFORM1 and INLINEFORM2 are the true and predicted prevalence respectively BIBREF19 .
Results Table TABREF13 presents the results of augmenting the feature set with the proposed features. We use Logistic Regression as a base classifier for the classify and count approach. Notice the positive impact of the features in the performance in the task. Adding the features derived from clustering the embeddings consistently improves the performance. Interestingly, the best performance ( INLINEFORM0 ) is achieved using the out-of-domain vectors, as in the NER classification task. Also, notice how the approach improves over the state-of-the-art performance in the challenge ( INLINEFORM1 ) BIBREF13 , held by the method of BIBREF20 . The improvement over the method of BIBREF20 however, does not necessarily mean that classify and count performs better in the task. It implies that the feature set we used is richer, that in turn highlights the value of robust feature extraction mechanisms which is the subject of this paper.
We have shown empirically the effectiveness of incorporating cluster membership features in the feature extraction pipeline of Named-Entity recognition, sentiment classification and quantification tasks. Our results strongly suggest that incorporating cluster membership features benefit the performance in the tasks. The fact that the performance improvements are consistent in the four tasks we investigated, further highlights their usefulness, both for practitioners and researchers.
Although our study does not identify a clear winner with respect to the type of word vectors (skipgram, cbow, or GloVe), our findings suggest that one should first try skip-gram embeddings of low dimensionality ( INLINEFORM0 ) and high number of clusters (e.g., INLINEFORM1 ) as the results obtained using these settings are consistently competitive. Our results also suggest that using out-of-domain data, like Wikipedia articles in this case, to construct the word embeddings is a good practice, as the results we obtained with these vectors are also competitive. The positive of out-of-domain embeddings and their combination with in-domain ones remains to be further studied.

Figure and table captions:
Table 1: Scores on F1-measure for named entities segmentation for the different word embeddings across different number of clusters. For each embedding type, we show its dimension and window size. For instance, glove40,w5 is 40-dimensional glove embeddings with window size 5.
Table 2: Results in terms of F1-score for named entities classification for the different word clusters across different number of clusters.
Table 3: MAEM scores (lower is better) for sentiment classification across different types of word embeddings and number of clusters.
Table 4: Sample from two clusters that were found useful for the sentiment classification. Words with positive or negative meaning are grouped together.
Table 5: Earth Movers Distance for fine-grained sentiment quantification across different types of word embeddings and number of clusters. The score in brackets denotes the best performance achieved in the challenge.

Questions about this paper:
Which hyperparameters were varied in the experiments on the four tasks?
How were the cluster extracted? 

Answers:
number of clusters, seed value in clustering, selection of word vectors, window size and dimension of embedding
Word clusters are extracted using k-means on word embeddings