Bayesian Grammar Induction for Language Modeling

Bayesian Grammar Induction for Language Modeling Stanley F. Chen Aiken Computation Laboratory Division of Applied Sciences Harvard University Cambridge, MA 02138 sfc@das, harvard, edu Abstract We describe a corpus-based induction algo- rithm for probabilistic context-free gram- mars. The algorithm employs a greedy heuristic search within a Bayesian frame- work, and a post-pass using the Inside- Outside algorithm. We compare the per- formance of our algorithm to n-gram mo- dels and the Inside-Outside algorithm in three language modeling tasks. In two of the tasks, the training data is generated by a probabilistic context-free grammar and in both tasks our algorithm outperforms the other techniques. The third task involves naturally-occurring data, and in this task our algorithm does not perform as well as n-gram models but vastly outperforms the Inside-Outside algorithm. 1 Introduction In applications such as speech recognition, hand- writing recognition, and spelling correction, perfor- mance is limited by the quality of the language mo- del utilized (7; 7; 7; 7). However, static language modeling performance has remained basically un- changed since the advent of n-gram language mo- dels forty years ago (7). Yet, n-gram language mo- dels can only capture dependencies within an n- word window, where currently the largest practical n for natural language is three, and many dependen- cies in natural language occur beyond a three-word window. In addition, n-gram models are extremely large, thus making them difficult to implement effi- ciently in memory-constrained applications. An appealing alternative is grammar-based lan- guage models. Language models expressed as a pro- babilistic grammar tend to be more compact than n-gram language models, and have the ability to mo- del long-distance dependencies (7; 7; 7). However, to date there has been little success in constructing grammar-based language models competitive with n-gram models in problems of any magnitude. In this paper, we describe a corpus-based indue- tion algorithm for probabilistic context-free gram- mars that outperforms n-gram models and the Inside-Outside algorithm (7) in medium-sized do- mains. This result marks the first time a grammar- based language model has surpassed n-gram mode- ling in a task of at least moderate size. The al- gorithm employs a greedy heuristic search within a Bayesian framework, and a post-pass using the Inside-Outside algorithm. 2 Grammar Induction as Search Grammar induction can be framed as a search pro- blem, and has been framed as such almost without exception in past research (7). The search space is taken to be some class of grammars; for example, in our work we search within the space of probabilistic context-free grammars. The objective function is ta- ken to be some measure dependent on the training data; one generally wants to find a grammar that in some sense accurately models the training data. Most work in language modeling, including n- gram models and the Inside-Outside algorithm, falls under the maximum-likelihood paradigm, where one takes the objective function to be the likelihood of the training data given the grammar. However, the optimal grammar under this objective function is one which generates only strings …

Content truncated to 500 words