On Efficient Retrieval of Top Similarity Vectors

Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 5236–5246, Hong Kong, China, November 3–7, 2019. c⃝2019 Association for Computational Linguistics 5236 On Efficient Retrieval of Top Similarity Vectors Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, Ping Li Cognitive Computing Lab Baidu Research USA 1195 Bordeaux Dr, Sunnyvale, CA 94089, USA 10900 NE 8th St, Bellevue, WA 98004, USA {shulongtan,zhixinzhou,v xuzhaozhuo,liping11}@baidu.com Abstract Retrieval of relevant vectors produced by rep- resentation learning critically influences the ef- ficiency in natural language processing (NLP) tasks. In this paper we demonstrate an efficient method for searching vectors via a typical non- metric matching function: inner product. Our method, which constructs an approximate In- ner Product Delaunay Graph (IPDG) for top-1 Maximum Inner Product Search (MIPS), trans- forms retrieving the most suitable latent vec- tors into a graph search problem with great benefits of efficiency. Experiments on data representations learned for different machine learning tasks verify the outperforming effec- tiveness and efficiency of the proposed IPDG. 1 Introduction With the popularity of representation learning meth- ods, such as Word2vec (Mikolov et al., 2013a), words are represented as real-valued embedding vectors in the semantic space. Therefore, retrieval of similar word embeddings is one of the most ba- sic operations in natural language processing with wide applicability in synonym extraction (Yoon et al., 2017), sentence alignment (Levy et al., 2017), polysemous word learning (Sun et al., 2017) and semantic search for documents related to a query. In this work, we address on efficient retrieval of similar word embeddings via inner product (dot product) similarity. Inner product is a general se- mantic matching function with applications in neu- ral probabilistic language models (Bengio et al., 2003), machine translation (Gao et al., 2014), ques- tion answering (Lee et al., 2015), and attention mechanisms (Vaswani et al., 2017). For normal- ized vectors, inner product is equivalent to cosine similarity, which is a common semantic textual similarity utilized in semantic classification and search (Sahami and Heilman, 2006; Ramage et al., 2009; Agirre et al., 2012; Huang et al., 2013; Liu et al., 2015; Faruqui et al., 2016; Sultan et al., 2016; K¨oper and im Walde, 2018; Gong et al., 2018), Re- lation Extraction (RE) (Plank and Moschitti, 2013) and text coherence evaluation (Putra and Toku- naga, 2017). For un-normalized vectors, although cosine similarity is still widely applied, the final matching scores of word embeddings are usually weighted (Acree et al., 2016; Srinivas et al., 2010) by ranking-based coefficients (e.g., the side infor- mation), which transforms the problem back to search via inner product (see Eq. (2)). Formally, retrieving the most similar word with the inner product ranking function is a Maximum Inner Product Search (MIPS) problem. MIPS is a continuously addressed topic (Bachrach et al., 2014; Shrivastava and Li, 2014; Kalantidis and Avrithis, 2014; Shrivastava and Li, 2015; Guo et al., 2016; Wu et al., 2017), and it has non-trivial differ- ences with traditional Approximate Nearest Neigh- bor …

Content truncated to 500 words