Normalized Log-Linear Interpolation of Backoff Language Models is Efficient

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 876–886, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Normalized Log-Linear Interpolation of Backoff Language Models is Efficient Kenneth Heafield University of Edinburgh 10 Crichton Street Edinburgh EH8 9AB United Kingdom kheafiel@inf.ed.ac.uk Chase Geigle Sean Massung University of Illinois at Urbana-Champaign 707 S. Mathews Ave. Urbana, IL 61801 United States {geigle1,massung1,lanes}@illinois.edu Lane Schwartz Abstract We prove that log-linearly interpolated backoff language models can be efficiently and exactly collapsed into a single nor- malized backoff model, contradicting Hsu (2007). While prior work reported that log-linear interpolation yields lower per- plexity than linear interpolation, normaliz- ing at query time was impractical. We nor- malize the model offline in advance, which is efficient due to a recurrence relationship between the normalizing factors. To tune interpolation weights, we apply Newton’s method to this convex problem and show that the derivatives can be computed ef- ficiently in a batch process. These find- ings are combined in new open-source in- terpolation tool, which is distributed with KenLM. With 21 out-of-domain corpora, log-linear interpolation yields 72.58 per- plexity on TED talks, compared to 75.91 for linear interpolation. 1 Introduction Log-linearly interpolated backoff language mod- els yielded better perplexity than linearly interpo- lated models (Klakow, 1998; Gutkin, 2000), but experiments and adoption were limited due the im- practically high cost of querying. This cost is due to normalizing to form a probability distribution by brute-force summing over the entire vocabu- lary for each query. Instead, we prove that the log-linearly interpolated model can be normalized offline in advance and exactly expressed as an or- dinary backoff language model. This contradicts Hsu (2007), who claimed that log-linearly inter- polated models “cannot be efficiently represented as a backoff n–gram model.” We show that offline normalization is efficient due to a recurrence relationship between the normalizing factors (Whittaker and Klakow, 2002). This forms the basis for our open- source implementation, which is part of KenLM: https://kheafield.com/code/kenlm/. Linear interpolation (Jelinek and Mercer, 1980), combines several language models pi into a single model pL pL(wn | wn−1 1 ) = � i λipi(wn | wn−1 1 ) where λi are weights and wn 1 are words. Because each component model pi is a probability distri- bution and the non-negative weights λi sum to 1, the interpolated model pL is also a probability dis- tribution. This presumes that the models have the same vocabulary, an issue we discuss in §3.1. A log-linearly interpolated model pLL uses the weights λi as powers (Klakow, 1998). pLL(wn | wn−1 1 ) ∝ � i pi(wn | wn−1 1 )λi The weights λi are unconstrained real numbers, allowing parameters to soften or sharpen distribu- tions. Negative weights can be used to divide a mixed-domain model by an out-of-domain model. To form a probability distribution, the product is normalized pLL(wn | wn−1 1 ) = � i pi(wn | wn−1 1 )λi Z(wn−1 1 ) where normalizing factor Z is given by Z(wn−1 1 …

Content truncated to 500 words