Matching-oriented Embedding Quantization For Ad-hoc Retrieval

Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 8119–8129 November 7–11, 2021. c⃝2021 Association for Computational Linguistics 8119 Matching-oriented Product Quantization For Ad-hoc Retrieval Shitao Xiao1†, Zheng Liu2∗, Yingxia Shao1∗, Defu Lian3, Xing Xie2 1: Beijing University of Posts and Telecommunications, Beijing, China 2: Microsoft Research Asia, Beijing, China 3: University of Science and Technology of China, Hefei, China {stxiao,shaoyx}@bupt.edu.cn {zhengliu,xingx}@microsoft.com defulian@ustc.edu.cn Abstract Product quantization (PQ) is a widely used technique for ad-hoc retrieval. Recent stud- ies propose supervised PQ, where the embed- ding and quantization models can be jointly trained with supervised learning. However, there is a lack of appropriate formulation of the joint training objective; thus, the improve- ments over previous non-supervised baselines are limited in reality. In this work, we pro- pose the Matching-oriented Product Quantiza- tion (MoPQ), where a novel objective Multi- noulli Contrastive Loss (MCL) is formulated. With the minimization of MCL, we are able to maximize the matching probability of query and ground-truth key, which contributes to the optimal retrieval accuracy. Given that the exact computation of MCL is intractable due to the demand of vast contrastive sam- ples, we further propose the Differentiable Cross-device Sampling (DCS), which signif- icantly augments the contrastive samples for precise approximation of MCL. We conduct extensive experimental studies on four real- world datasets, whose results verify the effec- tiveness of MoPQ. The code is available at https://github.com/microsoft/MoPQ. 1 Introduction Ad-hoc retrieval is critical for many intelligent services, like web search and recommender sys- tems (Liu et al., 2021; Zhu et al., 2021; Ma et al., 2019). Given a query (e.g., a search request from user), ad-hoc retrieval selects relevant keys (e.g., webpages) from a massive set of candidates. It is usually treated as an approximate nearest neighbour search (ANNS) problem, where prod- uct quantization (PQ) (Jegou et al., 2010) is one of the most popular solutions thanks to its competi- tive memory and time efficiency. PQ is built upon †. Work is done during the internship at Microsoft. ∗. Corresponding author. “codebooks”, with which an input embedding can be quantized into a Cartesian product of “code- words” (preliminaries about the codebooks and codewords will be given in Section 2.1). By this means, the original embedding can be compressed into a highly compact representation. More im- portantly, it significantly improves the retrieval ef- ficiency, as query and key’s similarity can be ap- proximated based on the pre-computed distances between query and codewords. Existing Limitation. The original PQ algo- rithms (Jegou et al., 2010; Ge et al., 2013) are non-supervised: based on the well-trained em- beddings, the quantization model is learned with heuristic algorithms (e.g., k-means). In recent years, many works are dedicated to supervised PQ (Cao et al., 2016, 2017; Klein and Wolf, 2019; Gao et al., 2019; Chen et al., 2020), where the embedding model and the quantization model are trained jointly. The supervised PQ requires an explicit training objective for the quantization model. Most of the time, “the minimization of re- construction …

Content truncated to 500 words