Learning Concept Embeddings for Efficient Bag-of-Concepts Densification

Abstract: Explicit concept space models have proven efficacy for text representation in many natural language and text mining applications. The idea is to embed textual structures into a semantic space of concepts which captures the main topics of these structures. That so called bag-of-concepts representation suffers from data sparsity causing low similarity scores between similar texts due to low concept overlap. In this paper we propose two neural embedding models in order to learn continuous concept vectors. Once learned, we propose an efficient vector aggregation method to generate fully dense bag-of-concepts representations. Empirical results on a benchmark dataset for measuring entity semantic relatedness show superior performance over other concept embedding models. In addition, by utilizing our efficient aggregation method, we demonstrate the effectiveness of the densified vector representation over the typical sparse representations for dataless classification where we can achieve at least same or better accuracy with much less dimensions.

Vector-based semantic mapping models are used to represent textual structures (words, phrases, and documents) as high-dimensional meaning vectors. Typically, these models utilize textual corpora and/or Knowledge Bases (KBs) to acquire world knowledge, which is then used to generate a vector representation for the given text in the semantic space. The goal is thus to accurately place semantically similar structures close to each other in that semantic space. On the other hand, dissimilar structures should be far apart.
Explicit concept space models are motivated by the idea that high level cognitive tasks such learning and reasoning are supported by the knowledge we acquire from concepts BIBREF0 . Therefore, such models utilize concept vectors (a.k.a bag-of-concepts (BOC)) as the underlying semantic representation of a given text through a process called conceptualization, which is mapping the text into relevant concepts capturing its main topics. The concept space typically include concepts obtained from KBs such as Wikipedia, Probase BIBREF1 , and others. Once the concept vectors are generated, similarity between two concept vectors can be computed using a suitable similarity/distance measure such as cosine.
The BOC representation has proven efficacy for semantic analysis of textual data especially short texts where contextual information is missing or insufficient. For example, measuring semantic similarity/relatedness BIBREF2 , BIBREF3 , BIBREF4 , dataless classification BIBREF5 , BIBREF6 , BIBREF7 , BIBREF8 , short text clustering BIBREF0 , search and relevancy ranking BIBREF9 , event detection and coreference resolution BIBREF10 .
Similar to the traditional bag-of-words representation, the BOC vector is a high dimensional sparse vector whose dimensionality is the same as the number of concepts in the employed KB (typically millions). Consequently, it suffers from data sparsity causing low similarity scores between similar texts due to low concept overlap. Formally, given a text snippet INLINEFORM0 of INLINEFORM1 terms where INLINEFORM2 , and a concept space INLINEFORM3 of size INLINEFORM4 . The BOC vector INLINEFORM5 = INLINEFORM6 of INLINEFORM7 is a vector of weights of each concept where each INLINEFORM8 of concept INLINEFORM9 is calculated as in equation 1: DISPLAYFORM0 
Here INLINEFORM0 is a scoring function which indicates the degree of association between term INLINEFORM1 and concept INLINEFORM2 . For example, gabrilovich2007computing proposed Explicit Semantic Analysis (ESA) which uses Wikipedia articles as concepts and the TF-IDF score of the terms in these article as the association score. Another scoring function might be the co-occurrence count or Pearson correlation score between INLINEFORM3 and INLINEFORM4 . As we can notice, only very small subset of the concept space would have non-zero scores with the given terms. Moreover, the BOC vector is generated from the INLINEFORM5 concepts which have relatively high association scores with the input terms (typically few hundreds). Thus each text snippet is mapped to a very sparse vector of millions of dimensions having only few hundreds non-zero values BIBREF10 .
Typically, the cosine similarity measure is used compute the similarity between a pair of BOC vectors INLINEFORM0 and INLINEFORM1 . Because the concept vectors are very sparse, we can rewrite each vector as a vector of tuples INLINEFORM2 . Suppose that INLINEFORM3 and INLINEFORM4 , where INLINEFORM5 and INLINEFORM6 are the corresponding weights of concepts INLINEFORM7 and INLINEFORM8 respectively. And INLINEFORM9 , INLINEFORM10 are the indices of these concepts in the concept space INLINEFORM11 such that INLINEFORM12 . Then, the relatedness score can be written as in equation 2: DISPLAYFORM0 
where INLINEFORM0 is the indicator function which returns 1 if INLINEFORM1 and 0 otherwise. Having such sparse representation and using exact match similarity scoring measure, we can expect that two very similar text snippets might have zero similarity score if they map to different but very related set of concepts BIBREF7 .
Neural embedding models have been proposed to overcome the BOC sparsity problem. The basic idea is to learn fixed size continuous vectors for each concept. These vectors can then be used to compute concept-concept similarity and thus overcome the concept mismatch problem.
In this paper we propose two neural embedding models in order to learn continuous concept vectors based on the skip-gram model BIBREF11 . Our first model is the Concept Raw Context model (CRC) which utilizes concept mentions in a large scale KB to jointly learn embeddings of both words and concepts. Our second model is the Concept-Concept Context model (3C) which learns the embeddings of concepts from their conceptual contexts (i.e., contexts containing surrounding concepts only). After learning the concept vectors, we propose an efficient concept vector aggregation method to generate fully dense BOC representations. Our efficient aggregation method allows measuring the similarity between pairs of BOC vectors in linear time. This is more efficient than prior methods which require quadratic time or at least log-linear time if optimized (see equation 2).
We evaluate our embedding models on two tasks:
The contributions of this paper are threefold: First, we propose two low cost concept embedding models which requires few hours rather than days to train. Second, we propose simple and efficient vector aggregation method to obtain fully densified BOC vectors in linear time. Third, we demonstrate through experiments that we can obtain same or better accuracy using the densified BOC representation with much less dimensions (few in most cases), reducing the computational cost of generating the BOC vector significantly.
Concept/Entity Embeddings: neural embedding models have been proposed to learn distributed representations of concepts/entities. songunsupervised proposed using the popular Word2Vec model BIBREF12 to obtain the embeddings of each concept by averaging the vectors of the concept's individual words. For example, the embeddings of Microsoft Office would be obtained by averaging the embeddings of Microsoft and Office obtained from the Word2Vec model. Clearly, this method disregards the fact that the semantics of multi-word concepts is different from the semantics of their individual words. More robust concept embeddings can be learned from the concept's corresponding article and/or from the structure of the employed KB (e.g., its link graph). Such concept embedding models were proposed by hu2015entity,li2016joint,yamada2016joint who all utilize the skip-gram model BIBREF11 , but differ in how they define the context of the target concept.
li2016joint extended the embedding model proposed by hu2015entity by jointly learning concept and category embeddings from contexts defined by all other concepts in the target concept's article as well as its category hierarchy in Wikipedia. This method has the advantage of learning embeddings of both concepts and categories simultaneously. However, defining the concept contexts as pairs of the target concept and all other concepts appearing in its corresponding article might introduce noisy contexts, especially for long articles. For example, the Wikipedia article for United States contains links to Kindergarten, First grade, and Secondary school under the Education section.
yamada2016joint proposed a method based on the skip-gram model to jointly learn embeddings of words and concepts using contexts generated from surrounding words of the target concept or word. The authors also proposed incorporating the KB link graph by generating contexts from all concepts with outgoing link to the target concept to better model concept-concept relatedness.
Unlike li2016joint and hu2015entity who learn concept embeddings only, our CRC model (described in Section 3), maps both words and concepts into the same semantic space. Therefore we can easily measure word-word, word-concept, and concept-concept semantic similarities. In addition, compared to yamada2016joint model, we utilize contexts generated from both surrounding words and concepts. Therefore, we can better capture local contextual information of each target word/concept. Moreover, our proposed models are computationally less costly than hu2015entity and yamada2016joint models as they require few hours rather than days to train on similar computing resources.
BOC Densification: distributed concept vectors have been used by BOC densification mechanisms to overcome the BOC sparsity problem. songunsupervised proposed three different mechanisms for aligning the concepts at different indices given a sparse BOC pair ( INLINEFORM0 ) in order to increase their similarity score.
The many-to-many mechanism works by averaging all pairwise similarities. The many-to-one mechanism works by aligning each concept in INLINEFORM0 with the most similar concept in INLINEFORM1 (i.e., its best match). Clearly, the complexity of these two mechanisms is quadratic. The third mechanism is the one-to-one. It utilizes the Hungarian method in order to find an optimal alignment on a one-to-one basis BIBREF13 . This mechanism performed the best on dataless classification and was also utilized by li2016joint. However, the Hungarian method is a combinatorial optimization algorithm whose complexity is polynomial. Our proposed densification mechanism is more efficient than these three mechanisms as its complexity is linear with respect to the number of non-zero elements in the BOC vector. Additionally, it is simpler as it does not require tuning a cut off threshold for the minimum similarity between two aligned concepts as in prior work.
A main objective of learning concept embeddings is to overcome the inherent problem of data sparsity associated with the BOC representation. Here we try to learn continuous concept vectors by building upon the skip-gram embedding model BIBREF11 . In the conventional skip-gram model, a set of contexts are generated by sliding a context window of predefined size over sentences of a given text corpus. Vector representation of a target word is learned with the objective to maximize the ability of predicting surrounding words of that target word.
Formally, given a training corpus of INLINEFORM0 words INLINEFORM1 . The skip-gram model aims to maximize the average log probability: DISPLAYFORM0 
where INLINEFORM0 is the context window size, INLINEFORM1 is the target word, and INLINEFORM2 is a surrounding context word. The softmax function is used to estimate the probability INLINEFORM3 as follows: DISPLAYFORM0 
where INLINEFORM0 and INLINEFORM1 are the input and output vectors respectively and INLINEFORM2 is the vocabulary size. mikolov2013distributed proposed hierarchical softmax and negative sampling as efficient alternatives to approximate the softmax function which becomes computationally intractable when INLINEFORM3 becomes huge.
Our approach genuinely learns distributed concept representations by generating concept contexts from mentions of those concepts in large encyclopedic KBs such as Wikipedia. Utilizing such annotated KBs eliminates the need to manually annotate concept mentions and thus comes at no cost.
In this model, we jointly learn the embeddings of both words and concepts. First, all concept mentions are identified in the given corpus. Second, contexts are generated for both words and concepts from both other surrounding words and other surrounding concepts as well. After generating all the contexts, we use the skip-gram model to jointly learn words and concepts embeddings. Formally, given a training corpus of INLINEFORM0 words INLINEFORM1 . We iterate over the corpus identifying words and concept mentions and thus generating a sequence of INLINEFORM2 tokens INLINEFORM3 where INLINEFORM4 (as multi-word concepts will be counted as one token). Afterwards we train the a skip-gram model aiming to maximize: DISPLAYFORM0 
where as in the conventional skip-gram model, INLINEFORM0 is the context window size. In this model, INLINEFORM1 is the target token which would be either a word or a concept mention, and INLINEFORM2 is a surrounding context word or concept mention.
This model is different from yamada2016joint anchor context model in three aspects: 1) while generating target concept contexts, we utilize not only surrounding words but other surrounding concepts as well, 2) our model aims to maximize INLINEFORM0 where INLINEFORM1 could be a word or a concept, while yamada2016joint model maximizes INLINEFORM2 where INLINEFORM3 is the target concept/entity (see yamada2016joint Eq. 6), and 3) in case INLINEFORM4 is a concept, our model captures all the contexts in which it appeared, while yamada2016joint model generates for each entity one context of INLINEFORM5 previous and INLINEFORM6 next words. We hypothesize that considering both concepts and individual words in the optimization function would generate more robust embeddings.
Inspired by the distributional hypothesis BIBREF14 , we, in this model, hypothesize that "similar concepts tend to appear in similar conceptual contexts". In order to test this hypothesis, we learn concept embeddings by training a skip-gram model on contexts generated solely from concept mentions. As in the CRC model, we start by identifying all concept mentions in the given corpus. Then, contexts are generated from only surrounding concepts. Formally, given a training corpus of INLINEFORM0 words INLINEFORM1 . We iterate over the corpus identifying concept mentions and thus generating a sequence of INLINEFORM2 concept tokens INLINEFORM3 where INLINEFORM4 . Afterwards we train the skip-gram model aiming to maximize: DISPLAYFORM0 
where INLINEFORM0 is the context window size, INLINEFORM1 is the target concept, and INLINEFORM2 is a surrounding concept mention within INLINEFORM3 mentions.
This model is different from li2016joint and hu2015entity as they define the context of a target concept by all the other concepts which appear in the concept's corresponding article. Clearly, some of these concepts might be irrelevant especially for very long articles which cite hundreds of other concepts. Our 3C model, alternatively, learns concept semantics from surrounding concepts and not only from those that are cited in its article. We also extend the context window beyond pairs of concepts allowing more influence to other nearby concepts.
The main advantage of the 3C model over the CRC model is its computational efficiency where the model vocabulary is limited to the corpus concepts (Wikipedia in our case). One the other hand, the CRC model is advantageous because it jointly learns the embeddings of words and concepts and is therefore expected to generate higher quality vectors. In other words, the CRC model can capture more contextual signals such as actions, times, and relationships at the expense of training computational cost.
We utilize a recent Wikipedia dump of August 2016, which has about 7 million articles. We extract articles plain text discarding images and tables. We also discard References and External links sections (if any). We pruned both articles not under the main namespace and pruned all redirect pages as well. Eventually, our corpus contained about 5 million articles in total.
We preprocess each article replacing all its references to other Wikipedia articles with the their corresponding page IDs. In case any of the references is a title of a redirect page, we use the page ID of the original page to ensure that all concept mentions are normalized.
Following mikolov2013distributed, we utilize negative sampling to approximate the softmax function by replacing every INLINEFORM0 term in the softmax function (equation 4) with: DISPLAYFORM0 
where INLINEFORM0 is the number of negative samples drawn for each word and INLINEFORM1 is the sigmoid function ( INLINEFORM2 ). In the case of the CRC model INLINEFORM3 and INLINEFORM4 would be replaced with INLINEFORM5 and INLINEFORM6 respectively. And in the case of the 3C model INLINEFORM7 and INLINEFORM8 would be replaced with INLINEFORM9 and INLINEFORM10 respectively.
For both the CRC & 3C models with use a context window of size 9 and a vector of 500 dimensions. We train the skip-gram model for 10 iterations using 12 cores machine with 64GB of RAM. The CRC model took INLINEFORM0 15 hours to train for a total of INLINEFORM1 12.7 million tokens. The 3C model took INLINEFORM2 1.5 hours to train for a total of INLINEFORM3 4.5 million concepts.
As we mentioned in the related work section, the current mechanisms for BOC densification are inefficient as their complexity is least quadratic with respect to the number of non-zero elements in the BOC vector. Here, we propose simple and efficient vector aggregation method to obtain fully densified BOC vectors in linear time. Our mechanism works by performing a weighted average of the embedding vectors of all concepts in the given BOC. This operation scales linearly with the number of non-zero dimensions in the BOC vector. In addition, it produces a fully dense vector representing the semantics of the original concepts and considering their weights. Formally, given a sparse BOC vector INLINEFORM0 where INLINEFORM1 is weight of concept INLINEFORM2 . We can obtain the dense representation of INLINEFORM3 as in equation 8: DISPLAYFORM0 
where INLINEFORM0 is the embedding vector of concept INLINEFORM1 . Once we have this dense BOC vector, we can apply the cosine measure to compute the similarity between a pair of dense BOC vectors.
As we can notice, this weighted average is done once and for all for a given BOC vector. Other mechanisms that rely on concept alignment BIBREF7 , require realignment every time a given BOC vector is compared to another BOC vector. Our approach improves the efficiency especially in the context of dataless classification with large number of classes. Using our densification mechanism, we apply the weighted average for each class vector and for each instance once.
Interestingly, our densification mechanism allows us to densify the sparse BOC vector using only the top few dimensions. As we will show in the experiments section, we can get (near-)best results using these few dimensions compared to densifying with all the dimensions in the original sparse vector. This property reduces the cost of obtaining a BOC vector with a few hundred dimensions in the first place.
We evaluate the "goodness" of our concept embeddings on measuring entity semantic relatedness as an intrinsic evaluation. Entity relatedness has been recently used to model entity coherence in many named entity disambiguation systems.
We use a benchmark dataset created by ceccarelli2013learning from the CoNLL 2003 data. As in previous studies BIBREF16 , BIBREF15 , we model measuring entity relatedness as a ranking problem. We use the test split of the dataset to create 3,314 queries. Each query has a query entity and INLINEFORM0 91 response entities labeled as related or unrelated. The quality is measured by the ability of the system to rank related entities on top of unrelated ones.
We compare our models with two prior methods:
yamada2016joint who used the skip-gram model to learn embeddings of words and entities jointly. The authors also utilized Wikipedia link graph to better model entity-entity relatedness.
witten2008effective who proposed Wikipedia Link-based Measure (WLM) as a simple mechanism for modeling the semantic relatedness between Wikipedia concepts. The authors utilized Wikipedia link structure under the assumption that related concepts would have similar incoming links.
We report Mean Average Precision (MAP) and Normalized Discounted Cumulative Gain (nDCG) scores as commonly used measures for evaluating the ranking quality. Table 1 shows the performance of our CRC and 3C models compared to previous models. As we can see, the 3C model performs poorly on this task compared to prior models. On the other hand, our CRC model outperforms all the other methods by 2-4% in terms of nDCG and by 3% percent in terms of MAP.
chang2008importance proposed dataless classification as a learning protocol to perform text categorization without the need for labeled data to train a classifier. Given only label names and few descriptive keywords of each label, classification is performed on the fly by mapping each label into a BOC representation using ESA. Likewise, each data instance is mapped into the same BOC semantic space and assigned to the most similar label using a proper similarity measure such as cosine. Formally, given a set of INLINEFORM0 labels INLINEFORM1 , a text document INLINEFORM2 , a BOC mapping model INLINEFORM3 , and a similarity function INLINEFORM4 , then INLINEFORM5 is assigned to the INLINEFORM6 th label INLINEFORM7 such that INLINEFORM8 . We evaluate the effectiveness of our concept embedding models on the dataless classification task as an extrinsic evaluation. We demonstrate through empirical results the efficiency and effectiveness of our proposed BOC densification scheme in obtaining better classification results compared to the original sparse BOC representation.
We use the 20 Newsgroups dataset (20NG) BIBREF17 which is commonly used for benchmarking text classification algorithms. The dataset contains 20 categories each has INLINEFORM0 1000 news posts. We obtained the BOC representations using ESA from song2014dataless who utilized a Wikipedia index containing pages with 100+ words and 5+ outgoing links to create ESA mappings of 500 dimensions for both the categories and news posts of the 20NG. We designed two types of classification tasks: 1) fine-grained classification involving closely related classes such as Hockey vs. Baseball, Autos vs. Motorcycles, and Guns vs. Mideast vs. Misc, and 2) coarse-grained classification involving top-level categories such as Sport vs. Politics and Sport vs. Religion. The top-level categories are created by combining instances of the fine-grained categories as shown in Table 2.
We compare our models with three prior methods:
ESA which computes the cosine similarity using the sparse BOC vectors.
WE INLINEFORM0 & WE INLINEFORM1 which were proposed by songunsupervised for BOC densification using embeddings obtained from Word2Vec. As the authors reported, we fix the minimum similarity threshold to 0.85. WE INLINEFORM2 finds the best match for each concept, while WE INLINEFORM3 utilizes the Hungarian algorithm to find the best concept-concept alignment on one-to-one basis. Both mechanisms have polynomial time complexity.
Table 3 presents the results of fine-grained dataless classification measured in micro-averaged F1. As we can notice, ESA achieves its peak performance with a few hundred dimensions of the sparse BOC vector. Using our densification mechanism, both the CRC & 3C models achieve equal performance to ESA at much less dimensions. Densification using the CRC model embeddings gives the best F1 scores on the three tasks. Interestingly, the CRC model improves the F1 score by INLINEFORM0 7% using only 14 concepts on Autos vs. Motorcycles, and by INLINEFORM1 3% using 70 concepts on Guns vs. Mideast vs. Misc. The 3C model, still performs better than ESA on 2 out of the 3 tasks. Both WE INLINEFORM2 and WE INLINEFORM3 improve the performance over ESA but not as our CRC model.
In order to better illustrate the robustness of our densification mechanism when varying the # of BOC dimensions, we measured F1 scores of each task as a function of the # of BOC dimensions used for densification. As we see in Figure 1, with one concept we can achieve high F1 scores compared to ESA which achieves zero or very low F1. Moreover, near-peak performance is achievable with the top 50 or less dimensions. We can also notice that, as we increase the # of dimensions, both WE INLINEFORM0 and WE INLINEFORM1 densification methods have the same undesired monotonic pattern like ESA. Actually, the imposed threshold by these methods does not allow for full dense representation of the BOC vector and therefore at low dimensions we still see low overall F1 score. Our proposed densification mechanisms besides their low cost, produce fully densified representations allowing good similarities at low dimensions.
Results of coarse-grained classification are presented in Table 4. Classification at the top level is easier than the fine-grained level. Nevertheless, as with fine-grained classification, ESA still peaks with a few hundred dimensions of the sparse BOC vector. Both the CRC & 3C models achieve equal performance to ESA at very few dimensions ( INLINEFORM0 ). Densification using the CRC model embeddings still performs the best on both tasks. Interestingly, the 3C model gives very close F1 scores to the CRC model at less dimensions (@4 with Sport vs. Politics, and @60 with Sport vs. Religion) indicating its competitive advantage when computational cost is a decisive criteria. The 3C model, still performs better than ESA, WE INLINEFORM1 , and WE INLINEFORM2 on both tasks.
Figure 2 shows F1 scores of coarse-grained classification when varying the # of BOC dimensions used for densification. The same pattern of achieving near-peak performance at very few dimensions recur with the CRC & 3C models. ESA using the sparse BOC vectors achieves low F1 up until few hundred dimensions are considered. Even with the costly WE INLINEFORM0 and WE INLINEFORM1 densifications, performance sometimes decreases.
In this paper we proposed two models for learning concept embeddings based on the skip-gram model. We also proposed an efficient and effective mechanism for BOC densification which outperformed the prior proposed densification schemes on dataless classification. Unlike these prior densification mechanisms, our method scales linearly with the # of the BOC dimensions. In addition, we demonstrated through the results how this efficient mechanism allows generating high quality dense BOC vectors from few concepts alleviating the need of obtaining hundreds of concepts when generating the concept vector.

Figure and table captions:
Table 1 Top-3 concepts generated using ESA [6] for two 20-newsgroups categories (Hockey and Guns) along with top-3 concepts of sample instances
Fig. 1 Densification of the bag-of-concepts vector using weighted average of the learned concept embeddings. The concept space is defined by all Wikipedia article titles. The concept vector is created from the top n hits of searching a Wikipedia inverted index with the given text. The weights are the TF-IDF scores from searching Wikipedia
Table 2 Example three sentences along with sample contexts generated from CRX and CCX. Contexts are generated with a context window of length 3
Table 3 Evaluation of concept embeddings for measuring entity semantic relatedness using Spearman rankorder correlation (ρ)
Table 4 Top-3 rated entities from CRX & CCX models on sample entities from the 4 domains compared to the ground truth
Table 5 Accuracy of concept categorization
Table 6 20NG category mappings Top-level Low-level
Table 7 Evaluation results of dataless document classification of fine-grained classes measured in microaveraged F1 alongwith # of dimensions (concepts) in the BoC at which corresponding performance is achieved
Fig. 2 Micro-averaged F1 scores of fine-grained classes when varying the # of BoC dimensions (color figure online)
Table 8 Evaluation results of dataless document classification of coarse-grained classes measured in micro-averaged F1 along with # of dimensions (concepts) at which corresponding performance is achieved
Fig. 3 Micro-averaged F1 scores of coarse-grained classes when varying the # of concepts (dimensions) in the BoC from 1 to 500 (color figure online)
Table 9 Evaluation results of dataless document classification of coarse-grained classes versus supervised classification with SVM measured in micro-averaged F1 along with # of dimensions (concepts) for CRX & CCX or % of labeled samples for SVM at which corresponding performance is achieved
Table 10 Top-5 related concepts from CRX & CCX models for sample target concepts

Questions about this paper:
which neural embedding model works better?
What is the degree of dimension reduction of the efficient aggregation method?

Answers:
the CRX model
The number of dimensions can be reduced by up to 212 times.