Incremental Skip-gram Model with Negative Sampling

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 363–371 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Incremental Skip-gram Model with Negative Sampling Nobuhiro Kaji and Hayato Kobayashi Yahoo Japan Corporation {nkaji,hakobaya}@yahoo-corp.jp Abstract This paper explores an incremental train- ing strategy for the skip-gram model with negative sampling (SGNS) from both em- pirical and theoretical perspectives. Ex- isting methods of neural word embed- dings, including SGNS, are multi-pass al- gorithms and thus cannot perform incre- mental model update. To address this problem, we present a simple incremen- tal extension of SGNS and provide a thorough theoretical analysis to demon- strate its validity. Empirical experiments demonstrated the correctness of the theo- retical analysis as well as the practical use- fulness of the incremental algorithm. 1 Introduction Existing methods of neural word embeddings are typically designed to go through the entire train- ing data multiple times. For example, negative sampling (Mikolov et al., 2013b) needs to pre- compute the noise distribution from the entire training data before performing Stochastic Gradi- ent Descent (SGD). It thus needs to go through the training data at least twice. Similarly, hierarchical soft-max (Mikolov et al., 2013b) has to determine the tree structure and GloVe (Pennington et al., 2014) has to count co-occurrence frequencies be- fore performing SGD. The fact that those existing methods are multi- pass algorithms means that they cannot perform incremental model update when additional train- ing data is provided. Instead, they have to re-train the model on the old and new training data from scratch. However, the re-training is obviously inefficient since it has to process the entire training data received thus far whenever new training data is provided. This is especially problematic when the amount of the new training data is relatively smaller than the old one. One such situation is that the embedding model is updated on a small amount of training data that includes newly emerged words for instantly adding them to the vocabulary set. Another situation is that the word embeddings are learned from ever-evolving data such as news articles and microblogs (Peng et al., 2017) and the embedding model is periodically updated on newly generated data (e.g., once in a week or month). This paper investigates an incremental training method of word embeddings with a focus on the skip-gram model with negative sampling (SGNS) (Mikolov et al., 2013b) for its popularity. We present a simple incremental extension of SGNS, referred to as incremental SGNS, and provide a thorough theoretical analysis to demonstrate its validity. Our analysis reveals that, under a mild assumption, the optimal solution of incremental SGNS agrees with the original SGNS when the training data size is infinitely large. See Section 4 for the formal and strict statement. Additionally, we present techniques for the efficient implemen- tation of incremental SGNS. Three experiments were conducted to assess the correctness of the theoretical analysis as well as the practical usefulness of incremental SGNS. The first experiment empirically investigates the validity of …

Content truncated to 500 words