Dynamic programming for parsing and estimation of stochastic unification-based grammars

Stuart Geman, Mark JohnsonACL 2002 · DOI

Abstract

Stochastic Unification-Based Grammars (SUBGs) provide a powerful framework for capturing complex linguistic constraints, yet their application has been limited by the computational cost of enumerating all possible parses. This paper introduces a dynamic programming framework that treats "packed" parse representations as graphical models. By applying variable elimination algorithms, we enable efficient calculation of maximum-a-posteriori (MAP) parses and training statistics. This approach transforms an intractable enumeration problem into a structured optimization task that is often computationally feasible for natural language datasets.

Introduction

Unification-Based Grammars (UBGs) are essential for modeling non-local constraints in natural language, such as subject-verb agreement. However, extending these to a stochastic framework (SUBGs) introduces a significant "enumeration bottleneck." Traditional methods for training or parsing SUBGs require the exhaustive listing of every valid parse, which can be astronomically large for complex grammars or large-scale corpora like the Penn Treebank. This paper addresses this challenge by leveraging compressed representations and graphical model algorithms.

Methods: From Packed Representations to Graphical Models

The proposed framework bridges formal linguistics and machine learning through two primary mechanisms:

  1. Packed Representations: Utilizing the work of Maxwell and Kaplan (1995), the authors represent the set of all possible parses as a "packed" structure. This format uses logic-based variables to represent shared components across multiple parses, effectively compressing the search space.
  2. Graphical Model Equivalence: The core innovation is the realization that these packed representations are mathematically isomorphic to graphical models, specifically Truth Maintenance Systems (TMS).

By framing the problem as a graphical model, finding the most probable parse becomes a "max-product" problem, while calculating training statistics (conditional likelihood) becomes a "sum-product" problem. The authors adapt dynamic programming techniques, such as variable elimination, to operate directly on these compressed structures.

A dependency graph representing the relationships between variables $X_1$ through $X_7$ in a packed representation, illustrating the structure used for dynamic programming.

Key Insights and Ideas

  • Local Features are Key: For the dynamic programming to work, the "properties" (features) of the grammar must be local to the fragments in the packed representation. Global information can still be captured by encoding it into "diacritic" features within the unification process itself.
  • Structure over Enumeration: You don't need to see every individual parse to understand the aggregate statistics of the whole set. By exploiting the internal structure of the "packed" forest, you can sum up probabilities much faster.

Results and Complexity

The authors provide a mathematical derivation showing how MAP parses and conditional likelihoods can be computed using variable elimination. While the algorithm's worst-case complexity is exponential (due to the NP-complete nature of optimal variable ordering), it typically performs in polynomial time for linguistic data. This efficiency stems from the fact that linguistic dependencies usually factorize into small, non-interacting groups.

Conclusion and Future Work

This dynamic programming framework offers a scalable path for using SUBGs in large-scale NLP tasks. By treating parsing as inference in a graphical model, the authors overcome the enumeration bottleneck, paving the way for more sophisticated probabilistic grammar induction. Future work includes empirical comparisons with other forest-based methods and refining variable ordering heuristics to ensure consistent performance across diverse linguistic structures.

Summary updated

BibTeX
@inproceedings{geman2002dynamic,
  author = {Stuart Geman and Mark Johnson},
  title = {{Dynamic programming for parsing and estimation of stochastic unification-based grammars}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2002},
  doi = {10.3115/1073083.1073130},
}
Figure