Riemannian Optimization for Skip-Gram Negative Sampling

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 2028–2036 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1185 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 2028–2036 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1185 Riemannian Optimization for Skip-Gram Negative Sampling Alexander Fonarev1,2,4,*, Oleksii Hrinchuk1,2,3,*, Gleb Gusev2,3, Pavel Serdyukov2, and Ivan Oseledets1,5 1Skolkovo Institute of Science and Technology, Moscow, Russia 2Yandex LLC, Moscow, Russia 3Moscow Institute of Physics and Technology, Moscow, Russia 4SBDA Group, Dublin, Ireland 5Institute of Numerical Mathematics, Russian Academy of Sciences, Moscow, Russia Abstract Skip-Gram Negative Sampling (SGNS) word embedding model, well known by its implementation in “word2vec” software, is usually optimized by stochastic gradi- ent descent. However, the optimization of SGNS objective can be viewed as a prob- lem of searching for a good matrix with the low-rank constraint. The most stan- dard way to solve this type of problems is to apply Riemannian optimization frame- work to optimize the SGNS objective over the manifold of required low-rank matri- ces. In this paper, we propose an algo- rithm that optimizes SGNS objective us- ing Riemannian optimization and demon- strates its superiority over popular com- petitors, such as the original method to train SGNS and SVD over SPPMI matrix. 1 Introduction In this paper, we consider the problem of embed- ding words into a low-dimensional space in order to measure the semantic similarity between them. As an example, how to find whether the word “table” is semantically more similar to the word “stool” than to the word “sky”? That is achieved by constructing a low-dimensional vector repre- sentation for each word and measuring similarity between the words as the similarity between the corresponding vectors. One of the most popular word embedding mod- els (Mikolov et al., 2013) is a discriminative neu- ral network that optimizes Skip-Gram Negative Sampling (SGNS) objective (see Equation 3). It aims at predicting whether two words can be found close to each other within a text. As shown in Sec- tion 2, the process of word embeddings training ∗The first two authors contributed equally to this work using SGNS can be divided into two general steps with clear objectives: Step 1. Search for a low-rank matrix X that pro- vides a good SGNS objective value; Step 2. Search for a good low-rank representation X = WC⊤ in terms of linguistic metrics, where W is a matrix of word embeddings and C is a matrix of so-called context em- beddings. Unfortunately, most previous approaches mixed these two steps into a single one, what entails a not completely correct formulation of the optimization problem. For example, popular approaches to train embeddings (including the original “word2vec” implementation) do not take into account that the objective from Step 1 depends only on the prod- uct X = WC⊤: instead of straightforward com- puting of the derivative w.r.t. X, these methods are explicitly based on the derivatives …

Content truncated to 500 words