Projection Aléatoire Non-Négative pour le Calcul de Word Embedding / Non-Negative Randomized Word Embedding (2017)

Abstract: Non-Negative Randomized Word Embedding We propose a word embedding method which is based on a novel random projection technique. We show that weighting methods such as positive pointwise mutual information (PPMI) can be applied to our models after their construction and at a reduced dimensionality. Hence, the proposed technique can efficiently transfer words onto semantically discriminative spaces while demonstrating high computational performance, besides benefits such as ease of update and a simple mechanism for interoperability. We report the performance of our method on several tasks and show that it yields competitive results compared to neural embedding methods in monolingual corpus-based setups.

## introduction word embedding techniques have become a cornerstone of several modern nlp systems. from a methodological perspective, two broad categories of embedding algorithms are commonly identified and used. following the terminology proposed in @xcite , these are a) the classic count models, which employ the chain of processes of collecting co-occurrence frequencies in highdimensional vectors followed by weighting and dimensionality reduction processes (see @xcite ; and, b) the more recent neural predictive techniques in which the process of learning word embeddings is modelled as a (type of convex) optimisation task, and implemented using a kind of neural network-e.g., @xcite al. (2013b), pennington et al. (2014) , and so on. evidently, both methods capture statistical information about word usage and can be explained using vector space mathematics @xcite . in this paper, we ask which features an ideal vector-based representation of word meaning should have. we maintain that an ideal model must a) show human-like behaviour on linguistic tasks of interest ; b) have low dimensionality for 'easy' manipulation ; c) be efficiently acquirable from large corpora to allow for fast experimentation ; d) be linked to a transparent model, so that linguistic and computational hypotheses and experimental results can be systematically analysed and explained ; and e) be easy to update (e.g., allow the addition of new context elements or target entities and the removal of old ones, as required in the analysis of frequently-updated text data, such as text streams from social media). despite their successes, both count and predictive models fall short of some of these desiderata. due to the heavy-tailed distribution of words' co-occurrences (e.g., figure 1a ), count-based models often fail on a and b, unless they embrace weighting and dimensionality reduction processes. weighting and dimensionality reduction processes, however, are carried out over high-dimensional vectors and thus impose high computational complexity (c). in addition, once count-based models are weighted and compressed, they are fixed and cannot be updated without running those expensive steps anew (e). even with these provisions, in some tasks, the performance of these models lags behind that of predictive models (a), unless a variety of parameters is added to the basic model @xcite , in which case the model becomes more difficult to interpret (d). on the other hand, despite their competitive performance (a), neural-predictive models are relatively slow and resource-intensive to train and involve a time-consuming parameter-tuning process (c). further, neural embeddings are difficult to interpret (d) : there have been a number of publications dedicated to understanding these methods and/or questioning their lack of interpretability, e.g., @xcite . simply put, we do not know exactly what sort of information the dimensions of these models convey. even worse, this lack of interpretability results in the lack of interoperability : there is no guarantee that the comparison of embeddings obtained from different runs of these methods or/and on different corpora will be meaningful. 1 to find a middle ground solution for the above-mentioned problem, we introduce a new technique for generating low-dimensional embeddings using non-negative random projections. the construction of models using our method does not require training but simply generating random vectors and adding these random vectors together. in contrast to previous random-projection-based methods, our proposed embeddings can undergo weighting transformations such as ppmi after their construction. we argue that this model retains the main strengths of both count and predictive models, while smoothing out some of their respective disadvantages. in § 2, we set the problem and propose our solution in § 3. in § 4, we examine parameters of our method and report its performance on several tasks. we conclude in § 5. ## problem statement we regard the problem of producing word embeddings as an operation over raw word-context co-occurrences. to derive an embedding matrix p, a co-occurrence matrix c undergoes a set of transformations t : the given process in equation 1 maps p vectors of dimensionality n to an x-dimensional space p (often, but not necessarily, @xmath0. t can be a composition of several transformations, e.g., a weighting process w followed by a dimensionality reduction r, i.e., t n×@xmath1. the two broad categories of embedding techniques mentioned in § 1 differ in the way that they compute and implement t. in the so-called count models, t is often the combination of ppmi weighting (for increasing the discriminatory power of models) and singular value decomposition (svd) truncation (for dimensionality reduction). the ppmi weight for a component c @xmath2: svd truncation involves solving a least squares problem : computing ℓ 2 distances between column vectors. evidently, weighting process and svd truncation of a large and high-dimensional model is cumbersome and time consuming, and they restrain future updates of the model. in predictive models, t is computed using neural embedding techniques. simply put, t is derived by solving an optimization problem defined by the objective function of the neural net. although neural networks can excel in task such as finding a (near-)optimum t and thus p, their usage (similar to ppmi+svd) can be computationally expensive and their training is time-consuming. moreover, using these methods involves an often complex parameter tuning process, which entails lengthy experiments. the word2vec system @xcite , for instance, involves selecting training parameters of 'negative samples', 'learning rate', 'subsampling rate', and 'smoothing factor', in addition to the dimensionality of the embeddings and the size of context window. it is difficult to understand which particular combination of these parameters gives the best performance for a given corpus and task. apart from the methods mentioned above, t can be computed using a random projection techniques. in the context of this paper, perhaps the most well-known example of this class of algorithms is random indexing (ri) @xcite . in ri, t is a randomly generated matrix that is very sparse and has an asymptotic standard gaussian distribution. as a result, in randomized methods such as ri, devising t and thus deriving p can be faster and easier than count and predictive methods. particularly, since t is determined independently of c, in methods such as ri, p can be built incrementally and be updated and used at any time. furthermore, interoperability can be achieved by sharing and using similar random projection matrices across tasks and corpora. unfortunately, ri and previous random projection-based techniques suffer from low discriminatory power. literally, ri is a distance-preserving randomized dimension reduction technique : the ℓ 2 distances between entities in a p constructed using ri are (approximately) the same as the ℓ 2 distances between entities in c. consequently, although the ri method can be much faster and simpler than other embedding techniques, because crude ℓ 2 distances in c are not sufficient in many tasks, ri lags behind count-based ppmi-weighted and neural embeddings. note that for ri, the sums of components of row and column vectors in p are also always zero (given the standard gaussian distribution of the projections). hence, ri embeddings cannot be weighted after their construction due to the problem of division by zero (e.g., ppmi weighting is not applicable to ri embeddings since the inner summations in equation 2 are always zero-see figure 1b ). likewise, note that the use of ri and distance-preserving random projections is limited to the α-normed space that they are designed for (e.g., α = 2 for ri). hence, these methods cannot be applied after using all types of weightings. in this paper, we propose a method that shows all flexibilities of random projection-based techniques while it displays state-of-the-art performance in semantic similarity assessment tasks. like ri, we propose a t that is generated randomly. however, unlike ri, the sums of row and column vectors in our embeddings are always greater than zero. in contrast to ri and count-based models, weighting of our embeddings can take place after their construction. since vectors resulting from our approach are small (i.e., with a dimensionality of a few hundreds), weighting (e.g., ppmi) can be applied to our models incredibly faster than in classical count-based models. since our method devises t independently of c and skips solving optimization tasks, it is much faster than predictive neural techniques. for similar reasons, models can be built incrementally and updated at any time. our model is interpretable in the sense that the information each dimension of the model conveys can be elucidated using t : each dimension of our model corresponds to a bag of words. by the same token, interoperability can be achieved by the simple mechanism of sharing random projection matrices. in the following, we detail our method. ## conclusion we proposed an embedding method based on positive-only random projections. each dimension of our model represent a randomly chosen bag-of-words (or any other types of context). compared to count and neural-predictive techniques, our method provides a simpler mechanism for building and updating distributional models. thanks to its underlying randomized projection, our method is fast and has low computational complexity. particularly, by allowing weighting at the reduced dimensionality, our method achieves a performance comparable to many recent embedding techniques. however, in contrast to these approaches, our method is more flexible, it can accommodate several types of contexts at once, it can be updated at any time, and it does not require time-consuming training and parameter tuning.