Inducing Probabilistic Grammars by Bayesian Model Merging

Abstract

We describe a framework for inducing probabilistic grammars from corpora of positive samples. First, samples are {\em incorporated} by adding ad-hoc rules to a working grammar; subsequently, elements of the model (such as states or nonterminals) are {\em merged} to achieve generalization and a more compact representation. The choice of what to merge and when to stop is governed by the Bayesian posterior probability of the grammar given the data, which formalizes a trade-off between a close fit to the data and a default preference for simpler models (`Occam's Razor'). The general scheme is illustrated using three types of probabilistic grammars: Hidden Markov models, class-based $n$-grams, and stochastic context-free grammars.

To appear in Grammatical Inference and Applications, Second International Colloquium on Grammatical Inference; Springer Verlag, 1994. 13 pages

References in corpus (1)

• Best-first Model Merging for Hidden Markov Model Induction

Cited by in corpus (9)

• Generalizing Case Frames Using a Thesaurus and the MDL Principle
• FrankenGAN: Guided Detail Synthesis for Building Mass-Models Using Style-Synchonized GANs
• Learning the Dimensionality of Hidden Variables
• Inducing Probabilistic Programs by Bayesian Program Merging
• Discovering Dataset Nature through Algorithmic Clustering based on String Compression
• Probabilistic Modelling of Morphologically Rich Languages
• Identifying Hierarchical Structure in Sequences: A linear-time algorithm
• Clustering Words with the MDL Principle
• Non-Clashing Teaching Maps for Balls in Graphs