A Pylonic Decision-Tree Language Model- with Optimal Question Selection

A Pylonic Decision-Tree Language Model with Optimal Question Selection Adrian Corduneanu University of Toronto 73 Saint George St #299 Toronto, Ontario, M5S 2E5, Canada g7adrian@cdf.toronto.edu Abstract This paper discusses a decision-tree approach to the problem of assigning probabilities to words following a given text. In contrast with previ- ous decision-tree language model attempts, an algorithm for selecting nearly optimal questions is considered. The model is to be tested on a standard task, The Wall Street Journal, allow- ing a fair comparison with the well-known tri- gram model. 1 Introduction In many applications such as automatic speech recognition, machine translation, spelling cor- rection, etc., a statistical language model (LM) is needed to assign ~probabilities to sentences. This probability assignment may be used, e.g., to choose one of many transcriptions hypoth- esized by the recognizer or to make deci- sions about capitalization. Without any loss of generality, we consider models that oper- ate left-to-right on the sentences, assigning a probability to the next word given its word history. Specifically, we consider statistical LM's which compute probabilities of the type P{wn ]Wl, W2,..-, Wn--1}, where wi denotes the i-th word in the text. Even for a small vocabulary, the space of word histories is so large that any attempt to estimate the conditional probabilities for each distinct history from raw frequencies is infea- sible. To make the problem manageable, one partitions the word histories into some classes C(wl,w2,...,Wn-1), and identifies the word probabilities with P{wn [ C(wl, w2,. . . , Wn-1)}. Such probabilities are easier to estimate as each class gets significantly more counts from a train- ing corpus. With this setup, building a language model becomes a classification problem: group the word histories into a small number of classes 606 while preserving their predictive power. Currently, popular N-gram models classify the word histories by their last N - 1 words. N varies from 2 to 4 and the trigram model P{wn [Wn-2, wn-1} is commonly used. Al- though these simple models perform surpris- ingly well, there is much room for improvement. The approach used in this paper is to classify the histories by means of a decision tree: to clus- ter word histories Wl,W2,... ,wn-1 for which the distributions of the following word Wn in a training corpus are similar. The decision tree is pylonic in the sense that histories at different nodes in the tree may be recombined in a new node to increase the complexity of questions and avoid data fragmentation. The method has been tried before (Bahl et al., 1989) and had promising results. In the work presented here we made two major changes to the previous attempts: we have used an opti- mal tree growing algorithm (Chou, 1991) not known at the time of publication of (Bahl et al., 1989), and we have replaced the ad-hoc clus- tering of vocabulary items used by Bahl with a data-driven clustering scheme proposed in (Lu- cassen and Mercer, 1984). 2 Description of the Model 2.1 The Decision-Tree Classifier The purpose …

Content truncated to 500 words