Distribution-Based Pruning of Backoff Language Models

Distribution-Based Pruning of Backoff Language Models Jianfeng Gao Microsoft Research China No. 49 Zhichun Road Haidian District 100080, China, jfgao@microsoft.com Kai-Fu Lee Microsoft Research China No. 49 Zhichun Road Haidian District 100080, China, kfl@microsoft.com Abstract We propose a distribution-based pruning of n-gram backoff language models. Instead of the conventional approach of pruning n-grams that are infrequent in training data, we prune n-grams that are likely to be infrequent in a new document. Our method is based on the n-gram distribution i.e. the probability that an n-gram occurs in a new document. Experimental results show that our method performed 7-9% (word perplexity reduction) better than conventional cutoff methods. 1 Introduction Statistical language modelling (SLM) has been successfully applied to many domains such as speech recognition (Jelinek, 1990), information retrieval (Miller et al., 1999), and spoken language understanding (Zue, 1995). In particular, n-gram language model (LM) has been demonstrated to be highly effective for these domains. N-gram LM estimates the probability of a word given previous words, P(wn|w1,…,wn-1). In applying an SLM, it is usually the case that more training data will improve a language model. However, as training data size increases, LM size increases, which can lead to models that are too large for practical use. To deal with the problem, count cutoff (Jelinek, 1990) is widely used to prune language models. The cutoff method deletes from the LM those n-grams that occur infrequently in the training data. The cutoff method assumes that if an n-gram is infrequent in training data, it is also infrequent in testing data. But in the real world, training data rarely matches testing data perfectly. Therefore, the count cutoff method is not perfect. In this paper, we propose a distribution-based cutoff method. This approach estimates if an n-gram is “likely to be infrequent in testing data”. To determine this likelihood, we divide the training data into partitions, and use a cross-validation-like approach. Experiments show that this method performed 7-9% (word perplexity reduction) better than conventional cutoff methods. In section 2, we discuss prior SLM research, including backoff bigram LM, perplexity, and related works on LM pruning methods. In section 3, we propose a new criterion for LM pruning based on n-gram distribution, and discuss in detail how to estimate the distribution. In section 4, we compare our method with count cutoff, and present experimental results in perplexity. Finally, we present our conclusions in section 5. 2 Backoff Bigram and Cutoff One of the most successful forms of SLM is the n-gram LM. N-gram LM estimates the probability of a word given the n-1 previous words, P(wn|w1,…,wn-1). In practice, n is usually set to 2 (bigram), or 3 (trigram). For simplicity, we restrict our discussion to bigram, P(wn|wn-1), which assumes that the probability of a word depends only on the identity of the immediately preceding word. But our approach extends to any n-gram. Perplexity is the most common metric for evaluating a bigram LM. It is defined as, ∑ = = − − N i Pwi wi …

Content truncated to 500 words