A Novel Disambiguation Method for Unification-Based Grammars Using Probabilistic Context-Free Approximations

Bernd Kiefer, Hans-Ulrich Krieger, Detlef PrescherCOLING 2002

TL;DR

This paper introduces a novel method for disambiguating sentence interpretations from Unification-Based Grammars (UBGs) by leveraging simpler, approximated Context-Free Grammars (CFGs). This approach avoids complex probability modeling on the UBG side, enabling efficient training and cubic-time parsing and disambiguation, achieving 88% accuracy in experiments.

What Problem Does This Paper Address?

Unification-Based Grammars (UBGs) are powerful formalisms for linguistic analysis, but they often produce multiple possible interpretations (readings) for a single sentence. Disambiguating these readings to find the most likely one is a significant challenge. Traditional methods attempt to model probability distributions directly over UBG readings. However, these methods often suffer from mathematical "dirtiness" (probabilities not summing to 1) and computational inefficiency, especially with complex features, leading to impractical runtimes that grow exponentially with sentence length. This paper addresses the need for a more efficient, mathematically sound, and practical approach to UBG disambiguation.

Methods

The core of the proposed method is to shift the responsibility of probability modeling from the UBG to simpler Context-Free Grammars (CFGs) that are approximations of the original UBG.

  1. CFG Approximation: The paper utilizes a method (Kiefer and Krieger, 2000) to derive a CFG that approximates a given UBG. This involves generalizing lexicon entries and instantiating grammar rules using unification. A "restrictor" mechanism is applied to prune information that doesn't constrain the search space or leads to infinite growth. This process is iterated until a fixpoint is reached, resulting in a set of CFG productions. Importantly, the resulting CFG is a superset of the UBG's language, meaning it might overgenerate.
  2. Probabilistic CFG (PCFG) Training: Once the CFG approximation is obtained, standard techniques for probabilistic CFGs (PCFGs) are applied. The inside-outside algorithm is used for unsupervised training on a corpus to estimate probabilities for the CFG rules.
  3. Disambiguation via PCFG Ranking: The probabilities from the PCFG are used to rank the CFG trees (approximated readings). The assumption is that a ranking of CFG trees induces a ranking of UBG readings. The most probable CFG trees are then processed by the UBG, effectively establishing an order of best UBG parses.

Datasets

  • Gemini/CLE grammar: A mid-size English grammar written in the Gemini/CLE formalism was used for experiments.
  • Corpus: A corpus of 500 sentences was provided by John Dowding. This corpus was split into a training set (90%, 450 sentences) and a testing set (10%, 50 sentences).

Key Insights and Ideas

  • Shifting the burden: The most significant insight is moving the probabilistic modeling complexity from the UBG to a simpler, approximated CFG. This leverages well-established and efficient PCFG algorithms.
  • Mathematical cleanliness: By using PCFGs, the issue of probabilities not summing to 1, which plagues direct UBG probabilistic models, is avoided.
  • Efficiency gains: The CFG approximation allows for cubic-time parsing and disambiguation, a substantial improvement over methods with exponential complexity.
  • Unsupervised training: The approach enables unsupervised training of probabilistic models, which is crucial for practical applications where large annotated treebanks are scarce.
  • Ranking induction: The paper demonstrates that ranking CFG trees effectively induces a ranking of UBG readings, even if the CFG overgenerates and some CFG trees don't have a direct UBG counterpart.

Key Results

  • Accuracy: An unsupervised trained model achieved 88% accuracy on an exact-match task.
  • Baseline comparison: The proposed method significantly outperformed a random baseline (72% precision) and a symbolic approximated UBG (which served as a baseline for probabilistic methods).
  • Efficiency: The method allows for cubic-time parsing and disambiguation. The paper notes that for the Gemini grammar, the CFG approximation process itself was efficient, with fixpoint computation taking minutes.
  • Overtraining: The experiments showed an overtraining effect for probabilistic models after a certain number of training iterations, suggesting an optimal number of iterations exists.

Limitations and Future Work

  • CFG Overgeneration: The CFG approximation is a superset of the UBG language, meaning it can generate trees that the UBG cannot parse. While this doesn't affect the ranking of valid UBG trees, it's a characteristic of the approximation.
  • Comparison Difficulty: The authors note that direct comparison with other state-of-the-art parsers is difficult due to variations in training data, corpus size, and evaluation criteria.
  • Future Work: The paper suggests that this approach can be a starting point for more sophisticated stochastic parsing models and that the efficiency gains make it practical for real-world applications. The authors also mention that using the '=' operator for feature structure equivalence during approximation can lead to less restrictive grammars, but this comes with higher computational costs.

Summary updated

BibTeX
@inproceedings{kiefer2002novel,
  author = {Bernd Kiefer and Hans-Ulrich Krieger and Detlef Prescher},
  title = {{A Novel Disambiguation Method for Unification-Based Grammars Using Probabilistic Context-Free Approximations}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}
Figure