Lexicalization of Probabilistic Linear Context-free Rewriting Systems

Richard Mörbitz, Thomas RuprechtACL 2020

TL;DR

This paper introduces a method to transform probabilistic linear context-free rewriting systems (PLCFRS) into an equivalent "lexicalized" form. This transformation is crucial for enabling efficient parsing with neural network-based supertagging, combining the interpretability of grammars with the speed and accuracy of modern machine learning models.

What Problem Does This Paper Address?

Natural language parsing aims to uncover the syntactic structure of sentences, often represented as trees. While traditional context-free grammars (CFGs) are simple and interpretable, they struggle to model discontinuous constituents (parts of a sentence that are syntactically related but not adjacent). More expressive formalisms like Linear Context-Free Rewriting Systems (LCFRS) can handle this discontinuity but come with higher parsing complexity.

Recent advances in NLP have leveraged neural networks for "supertagging," a technique that pre-selects likely grammar rules for each word, significantly speeding up parsing for formalisms like Tree-Adjoining Grammars (TAG). However, applying this to the more powerful LCFRS has been hindered by the fact that LCFRS rules are often not "lexical" (i.e., they don't directly associate a rule with a specific word). This paper addresses this gap by providing a theoretical framework to "lexicalize" LCFRS, making them amenable to supertagging-based parsing.

Methods

The core contribution is a three-step procedure to transform a given PLCFRS $G$ into an equivalent lexicalized PLCFRS $G'$. This process ensures that the resulting grammar $G'$ has the same generative power and preserves the original probabilities.

  1. Dechain (Monic Rule Removal): Monic rules (rules with a single non-terminal on the right-hand side) are eliminated by composing them with other rules. This step ensures that all remaining rules have at least two non-terminals on the right-hand side or are terminating rules.
  2. Fuse Terminals (Terminal Insertion): Terminals (actual words) from terminating rules are inserted into non-terminating, terminal-free rules. This step aims to ensure that most rules contain at least one terminal.
  3. Propagate Terminals (Lexicalization): Terminals are further propagated into non-lexical branching rules. This is achieved by "cutting" terminals from terminating rules and "pasting" them into appropriate branching rules, effectively making the grammar lexical.

Crucially, the authors demonstrate that this procedure preserves the "fanout" of the grammar, meaning the parsing complexity does not increase. They also show how to recover the original derivations from the lexicalized grammar, which is important for understanding the full range of possible syntactic structures.

Datasets

Not discussed in the paper. The paper focuses on the theoretical construction of lexicalized grammars from existing LCFRS, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully bridges the gap between expressive, but complex, LCFRS and efficient, neural-based parsing techniques like supertagging.
  • Lexicalization as a Key Step: Lexicalizing LCFRS is presented as a necessary prerequisite for applying supertagging to this powerful grammar formalism.
  • Preserving Parsing Complexity: A significant achievement is that the lexicalization process does not increase the parsing complexity (fanout) of the grammar, a common concern with grammar transformations.
  • Recovering Original Derivations: The ability to map derivations from the lexicalized grammar back to the original grammar is vital for a complete parsing system, allowing for the recovery of all possible syntactic analyses.
  • Theoretical Foundation: The paper lays the theoretical groundwork for building such a parser, demonstrating the feasibility of the approach.

Key Results

The paper presents a constructive procedure for transforming any PLCFRS into an equivalent lexicalized PLCFRS. The key theoretical results are:

  • Equivalence: The constructed lexicalized PLCFRS ($G'$) is shown to be "ldTTR-equivalent" to the original PLCFRS ($G$). This means they generate the same language, and there exist linear, deterministic tree transducers that map derivations between them while preserving probabilities (or at least ensuring the mapped derivation has a weight greater than or equal to the original).
  • No Increased Fanout: The lexicalization process does not increase the fanout of the grammar, implying that the parsing complexity remains bounded by the original grammar's fanout.
  • Recoverability: A method is described to recover all original derivations from the derivations of the lexicalized grammar.

Limitations and Future Work

  • Implementation and Evaluation: The authors explicitly state that an implementation of the supertagger and experimental evaluation are "currently work in progress." This means the practical benefits and performance gains of their approach are yet to be demonstrated empirically.
  • Theoretical Focus: The paper is primarily theoretical, focusing on the construction and equivalence proofs. Real-world performance will depend on the efficiency of the implemented transducers and the effectiveness of the neural supertagger.
  • Future Work: The authors plan to use their approach to implement a supertagging-based LCFRS parser. This will involve building the necessary transducers and training a neural supertagger on data derived from LCFRS.

Summary updated

BibTeX
@inproceedings{morbitz2020lexicalization,
  author = {Richard Mörbitz and Thomas Ruprecht},
  title = {{Lexicalization of Probabilistic Linear Context-free Rewriting Systems}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
}
Figure