On Approximately Searching for Similar Word Embeddings

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 2265–2275, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics On Approximately Searching for Similar Word Embeddings Kohei Sugawara Hayato Kobayashi Masajiro Iwasaki Yahoo Japan Corporation 1-3 Kioicho, Chiyoda-ku, Tokyo 102-8282, Japan {ksugawar, hakobaya, miwasaki}@yahoo-corp.jp Abstract We discuss an approximate similarity search for word embeddings, which is an operation to approximately find em- beddings close to a given vector. We compared several metric-based search al- gorithms with hash-, tree-, and graph- based indexing from different aspects. Our experimental results showed that a graph-based indexing exhibits robust per- formance and additionally provided use- ful information, e.g., vector normalization achieves an efficient search with cosine similarity. 1 Introduction An embedding or distributed representation of a word is a real-valued vector that represents its “meaning” on the basis of distributional seman- tics, where the meaning of a word is determined by its context or surrounding words. For a given meaning space, searching for similar embeddings is one of the most basic operations in natural lan- guage processing and can be applied to various ap- plications, e.g., extracting synonyms, inferring the meanings of polysemous words, aligning words in two sentences in different languages, solving analogical reasoning questions, and searching for documents related to a query. In this paper, we address how to quickly and accurately find similar embeddings in a continu- ous space for such applications. This is impor- tant from a practical standpoint, e.g., when we want to develop a real-time query expansion sys- tem on a search engine on the basis of an embed- ding similarity. A key difference from the existing work is that embeddings are not high-dimensional sparse (traditional count) vectors, but (relatively) low-dimensional dense vectors. We therefore need to use approximate search methods instead of inverted-index-based methods (Zobel and Moffat, 2006). Three types of indexing are generally used in approximate similarity search: hash-, tree-, and graph-based indexing. Hash-based indexing is the most common in natural language processing due to its simplicity, while tree/graph-based indexing is preferred in image processing because of its per- formance. We compare several algorithms with these three indexing types and clarify which al- gorithm is most effective for similarity search for word embeddings from different aspects. To the best of our knowledge, no other study has compared approximate similarity search meth- ods focusing on neural word embeddings. Al- though one study has compared similarity search methods for (count-based) vectors on the basis of distributional semantics (Gorman and Curran, 2006), our study advances this topic and makes the following contributions: (a) we focus on neu- ral word embeddings learned by a recently devel- oped skip-gram model (Mikolov, 2013), (b) show that a graph-based search method clearly performs better than the best one reported in the Gorman and Curran study from different aspects, and (c) report the useful facts that normalizing vectors can achieve an effective search with cosine similarity, the search performance is more strongly related to a learning model of embeddings …

Content truncated to 500 words