Subword Language Model for Query Auto-Completion

Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 5022–5032, Hong Kong, China, November 3–7, 2019. c⃝2019 Association for Computational Linguistics 5022 Subword Language Model for Query Auto-Completion Gyuwan Kim Clova AI, NAVER Corp. gyuwan.kim@navercorp.com Abstract Current neural query auto-completion (QAC) systems rely on character-level language mod- els, but they slow down when queries are long. We present how to utilize subword language models for the fast and accurate generation of query completion candidates. Represent- ing queries with subwords shorten a decod- ing length significantly. To deal with issues coming from introducing subword language model, we develop a retrace algorithm and a reranking method by approximate marginal- ization. As a result, our model achieves up to 2.5 times faster while maintaining a sim- ilar quality of generated results compared to the character-level baseline. Also, we pro- pose a new evaluation metric, mean recover- able length (MRL), measuring how many up- coming characters the model could complete correctly. It provides more explicit meaning and eliminates the need for prefix length sam- pling for existing rank-based metrics. More- over, we performed a comprehensive analysis with ablation study to figure out the impor- tance of each component1. 1 Introduction Query auto-completion (QAC) is one of the es- sential features for search engines. When a user types a query in the search box, QAC systems sug- gest most likely completion candidates (Cai et al., 2016). It not only saves time for users to enter search terms but also provides new information more than what was initially expected. Recent neural QAC models in the literature em- ploy character-level language models (Park and Chiba, 2017). It is a natural choice in that QAC systems need to respond whenever a user enters a query as input character-by-character. In addition to the accuracy, speed in terms of latency is also an 1Code is available at https://github.com/ clovaai/subword-qac. indispensable prerequisite for practical QAC sys- tems. The generation process is auto-regressive, and the size of the search space is exponential to the sequence length. Long character sequences make prediction slow and inaccurate in the con- straints of limited computation. Also, character- level models are prone to errors due to long-range dependency (Sennrich, 2016). Therefore, these limitations arouse to consider alternatives to rep- resent a query in a shorter sequence. In this paper, we apply a subword language model for query auto-completion. Compared to character language models, subword language models reduce sequence length and the number of decoding steps significantly, thus resulting in much faster decoding. For subword-level model- ing, a segmentation algorithm is necessary. Byte pair encoding (BPE) (Sennrich et al., 2015) is widely used, but noise in the data makes segmen- tation ambiguous and degrades BPE output. To address this issue, as well as BPE, we use subword regularization (SR) algorithm proposed by Kudo (2018) that stochastically samples multiple seg- mentations by utilizing a unigram language model. To our knowledge, we are the first to …

Content truncated to 500 words