Kneser-Ney Smoothing on Expected Counts

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 765–774, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Kneser-Ney Smoothing on Expected Counts Hui Zhang Department of Computer Science University of Southern California hzhang@isi.edu David Chiang Information Sciences Institute University of Southern California chiang@isi.edu Abstract Widely used in speech and language pro- cessing, Kneser-Ney (KN) smoothing has consistently been shown to be one of the best-performing smoothing methods. However, KN smoothing assumes integer counts, limiting its potential uses—for ex- ample, inside Expectation-Maximization. In this paper, we propose a generaliza- tion of KN smoothing that operates on fractional counts, or, more precisely, on distributions over counts. We rederive all the steps of KN smoothing to operate on count distributions instead of integral counts, and apply it to two tasks where KN smoothing was not applicable before: one in language model adaptation, and the other in word alignment. In both cases, our method improves performance signifi- cantly. 1 Introduction In speech and language processing, smoothing is essential to reduce overfitting, and Kneser-Ney (KN) smoothing (Kneser and Ney, 1995; Chen and Goodman, 1999) has consistently proven to be among the best-performing and most widely used methods. However, KN smoothing assumes inte- ger counts, whereas in many NLP tasks, training instances appear with possibly fractional weights. Such cases have been noted for language model- ing (Goodman, 2001; Goodman, 2004), domain adaptation (Tam and Schultz, 2008), grapheme-to- phoneme conversion (Bisani and Ney, 2008), and phrase-based translation (Andr´es-Ferrer, 2010; Wuebker et al., 2012). For example, in Expectation-Maximization (Dempster et al., 1977), the Expectation (E) step computes the posterior distribution over possi- ble completions of the data, and the Maximiza- tion (M) step reestimates the model parameters as if that distribution had actually been observed. In most cases, the M step is identical to estimating the model from complete data, except that counts of observations from the E step are fractional. It is common to apply add-one smoothing to the M step, but we cannot apply KN smoothing. Another example is instance weighting. If we assign a weight to each training instance to indi- cate how important it is (say, its relevance to a par- ticular domain), and the counts are not integral, then we again cannot train the model using KN smoothing. In this paper, we propose a generalization of KN smoothing (called expected KN smoothing) that operates on fractional counts, or, more precisely, on distributions over counts. We rederive all the steps of KN smoothing to operate on count distri- butions instead of integral counts. We demonstrate how to apply expected KN to two tasks where KN smoothing was not applicable before. One is lan- guage model domain adaptation, and the other is word alignment using the IBM models (Brown et al., 1993). In both tasks, expected KN smoothing improves performance significantly. 2 Smoothing on integral counts Before presenting our method, we review KN smoothing on integer counts as applied to lan- guage models, although, as we will …

Content truncated to 500 words