Abstract: This paper proposes a novel class of PCFG parameterizations that support linguistically reasonable priors over PCFGs. To estimate the parameters is to discover a notion of relatedness among context-free rules such that related rules tend to have related probabilities. The prior favors grammars in which the relationships are simple to describe and have few major exceptions. A basic version that bases relatedness on weighted edit distance yields superior smoothing of grammars learned from the Penn Treebank (20% reduction of rule perplexity over the best previous method).
Introduction
In natural language processing, Probabilistic Context-Free Grammars (PCFGs) are fundamental for structural sentence analysis. However, these models suffer from a severe data sparsity problem. Standard "Treebank grammars" are often too rigid, assigning zero probability to valid but unseen sentences. Conversely, Markov models that decompose rules into smaller chunks often lose the specific subcategorization requirements of individual lexical items. The challenge lies in finding a smoothing method that captures linguistic regularities—such as the fact that adverbs can be inserted flexibly—while respecting the idiosyncratic behaviors of specific words.
The Transformation Model
Eisner introduces a "Transformation Model" that treats the space of all possible grammar rules as a giant graph. In this framework, every possible grammar rule is a vertex, and arcs between these vertices represent linguistic "edits" such as insertion, deletion, swapping, or retyping of constituents.
The probability of a specific grammar rule is modeled as the likelihood of a random walk starting from a generic START state and terminating at that rule's vertex. Instead of learning individual probabilities for every possible arc, the model learns weights ($\theta$) for features of those arcs using a log-linear approach. A Gaussian prior centered at zero encourages the model to prefer simple, regular transformations, only allowing for "expensive" exceptions when supported by strong evidence in the training data.
Experimental Results
The model was evaluated using the Penn Treebank (Wall Street Journal corpus), with data flattened into dependency-style rules to focus on verb arguments and adjuncts. The transformation model demonstrated significant improvements in rule perplexity and predictive accuracy.
As shown in the results table, the transformation model achieved a rule perplexity of 108.6, representing a roughly 20% reduction compared to the basic bigram Markov baseline (135.2). Furthermore, on a pseudo-disambiguation task—choosing the more likely of two unseen rules for a specific verb—the model achieved 92.2% accuracy, outperforming the bigram baseline of 88.1%. The best overall performance was achieved by averaging the transformation model with standard bigram models, indicating that the transformational prior captures complementary linguistic information.
Conclusion
By treating grammar rules as a system of related edits rather than independent strings, the transformational prior effectively addresses the sparsity problem in PCFGs. While computationally intensive, requiring approximate relaxation algorithms for tractability, the model's efficiency is notable: it performs as well on half the training data as previous models do on the full set. Future work may extend this approach to unsupervised grammar induction, where strong linguistic priors are even more critical for navigating large search spaces.
Summary updated