Experiments with Corpus-based LFG Specialization

Nicola Cancedda, Christer SamuelssonANLP 2000 · OpenReview

TL;DR

This paper tackles the inefficiency of powerful but overly ambiguous grammar formalisms like LFG. They demonstrate a corpus-based grammar pruning technique that significantly speeds up parsing by removing spurious ambiguities, achieving speedups of up to 6x with a manageable loss in coverage.

What Problem Does This Paper Address?

Modern grammar formalisms, such as Lexical Functional Grammar (LFG), are incredibly expressive, allowing linguists to concisely capture complex language phenomena. However, this expressiveness comes at a cost: grammars can become excessively ambiguous, leading to inefficient parsing. While some approaches try to disambiguate statistically after parsing, this paper focuses on making the parsing process itself more efficient by reducing the grammar's inherent ambiguity before parsing. The challenge is to achieve this efficiency gain without sacrificing too much of the grammar's ability to parse valid sentences (coverage).

Methods

The core technique is corpus-based grammar pruning. The authors leverage a corpus of actual sentences and their parsed representations (treebanks) to identify which parts of the grammar are actually used in correct parses.

Here's how it works:

  • Rule Schemata: LFG grammars use "rule schemata" which are like templates that can expand into many specific phrase-structure rules using regular expression operators (like Kleene star * or alternation |).
  • Identifying Used Paths: By analyzing how sentences in the treebank are parsed, the system determines the specific "paths" taken through these rule schemata.
  • Pruning: The grammar is then "pruned" by replacing the general rule schemata with new ones that only include the specific expansions that were observed in the corpus. This effectively removes unused or rarely used alternatives and complex operators.
  • Two-Stage Architecture: To mitigate the risk of losing coverage, they simulate a two-stage parsing system. If the pruned (specialized) grammar fails to parse a sentence, it's passed to the original, unpruned grammar. This ensures that the "anyparse" measure (whether any parse is found) is preserved.

Datasets

The experiments were conducted using two broad-coverage LFG grammars:

  • French Grammar: Developed within the Pargram project, consisting of 133 rule schemata.
  • English Grammar: Also from the Pargram project, with 85 rule schemata.

These grammars were trained and evaluated on treebanks derived from technical documentation corpora. For each language, a corpus of approximately 960-970 sentences was used, where human experts selected the most appropriate parse for each sentence.

Key Insights and Ideas

  • Pruning is Effective: Corpus-based pruning can drastically reduce the complexity and ambiguity of LFG grammars.
  • Speed vs. Coverage Trade-off: There's a clear trade-off: more aggressive pruning leads to greater speedups but also a reduction in grammatical coverage.
  • Two-Stage Architecture Preserves Coverage: A simple two-stage approach (specialized grammar first, then original if it fails) can maintain the original grammar's ability to parse all sentences, effectively "hiding" the coverage loss.
  • Complex Operators are Key Ambiguity Sources: Operators like "ignore" and "shuffle" in LFG rule schemata are significant contributors to spurious ambiguity and are prime targets for pruning.
  • Training Data Size Matters: Even after processing 90% of the corpus, adding the final 10% still yielded gains, suggesting that the training corpora might have been somewhat small for optimal specialization.

Key Results

  • Speedup: Achieved speedups of up to 6x for the French grammar and 2.67x for the English grammar with full pruning.
  • Coverage Loss: A reduction in grammatical coverage of about 13% was observed with full pruning.
  • Ambiguity Reduction: The average number of parses per sentence decreased significantly, by almost a factor of 9 for the French grammar.
  • Two-Stage Performance: The simulated two-stage architecture showed that the best trade-off (balancing speedup and coverage) was achieved by the fully pruned grammars, as the penalty for uncovered sentences in the simulation effectively accounted for the coverage loss.

Limitations and Future Work

  • Coverage Loss: The primary limitation acknowledged is the reduction in grammatical coverage. While the two-stage architecture mitigates this in terms of anyparse, it doesn't recover the specific parses lost.
  • Training Data Size: The authors suggest that larger training corpora might yield further improvements and potentially reduce the coverage loss for a given speedup.
  • Future Work: The authors propose extending this work to "higher-order grammar pruning," which would involve removing not just grammar rules but entire grammar-rule combinations, akin to more advanced explanation-based learning techniques. They also aim to apply these techniques to other grammar formalisms.

Summary updated

BibTeX
@inproceedings{cancedda2000experiments,
  author = {Nicola Cancedda and Christer Samuelsson},
  title = {{Experiments with Corpus-based LFG Specialization}},
  booktitle = {ANLP},
  year = {2000},
  url = {https://openreview.net/forum?id=taFjZ1UYhP},
}
Figure