Span-Based LCFRS-2 Parsing

Miloš Stanojević, Mark SteedmanACL 2020

TL;DR

This paper introduces a novel span-based chart parsing algorithm for discontinuous constituency structures, achieving state-of-the-art results on German and English treebanks. By combining a restricted grammar formalism (LCFRS-2) with a powerful neural scoring model, they achieve both high accuracy and practical parsing speeds, outperforming previous chart-based parsers and competing with transition-based methods.

What Problem Does This Paper Address?

Modeling long-range dependencies in natural language is a fundamental challenge in computational linguistics. Traditional parsers often produce "projective" or continuous tree structures, which struggle to represent these dependencies. While discontinuous constituency formalisms like LCFRS (Linear Context-Free Rewriting Systems) can capture these structures, existing grammar-based parsers have been hampered by computationally expensive algorithms and less powerful probabilistic models. Conversely, modern transition-based parsers, while flexible, often rely on approximate search and may not fully leverage the structural constraints that a grammar can provide. This paper aims to bridge this gap by developing a chart-based parser that is both grammatically constrained and capable of using sophisticated neural models for accurate scoring, while maintaining efficient parsing.

Methods

The core of this work is a new span-based chart parsing algorithm designed for LCFRS-2 grammars. Instead of relying on explicit grammars during parsing, the algorithm uses a neural model to score possible spans (contiguous or discontinuous segments of text) and their associated non-terminal labels.

Key methodological contributions include:

  • Span-Based Neural Scoring: A neural network, built upon bi-LSTMs for word embeddings, scores potential constituents. This approach preserves the dynamic programming properties of chart parsers.
  • LCFRS-2 Formalism: The parser restricts its output to trees representable by LCFRS-2, a formalism that allows discontinuous constituents with a fan-out of at most 2. This restriction is crucial for managing computational complexity.
  • Decomposition of Discontinuous Spans: To handle discontinuous constituents efficiently, the scoring of a discontinuous span is decomposed into scoring three continuous spans (left, gap, and right components), allowing for a more efficient neural computation.
  • Novel Objective Function: The authors move away from traditional max-margin training, which proved unstable for discontinuous structures, and adopt a binary classification approach for each (span start, span end, label) triple. This method is more stable and computationally efficient for training.
  • Direct CKY Algorithm: A modified CKY-style algorithm is implemented to handle the specific rule shapes of LCFRS-2, using multi-dimensional arrays for efficient chart lookup and avoiding the overhead of priority queues found in traditional deductive parsers.

Datasets

The parser was trained and evaluated on:

  • German Negra Treebank: Used for development and hyper-parameter tuning.
  • German Tiger Treebank: Used for test set evaluation.
  • English Discontinuous Penn Treebank (DPTB): Used for test set evaluation.

The paper notes that these treebanks were preprocessed using the treetools package, and evaluation was performed with the discodop package.

Key Insights and Ideas

  • Grammar Constraints are Still Valuable: Despite the success of grammar-less transition-based parsers, this work demonstrates that leveraging grammatical constraints (like LCFRS-2) can significantly improve accuracy by restricting the search space for dynamic programming.
  • Span-Based Neural Models are Powerful: The span-based approach, combined with modern neural architectures, allows for rich probabilistic scoring without sacrificing the efficiency of chart parsing.
  • Decomposition is Key for Efficiency: Breaking down the scoring of discontinuous constituents into smaller, continuous parts is a critical step for making neural scoring computationally feasible.
  • Objective Function Matters for Discontinuity: The choice of training objective is crucial. The proposed binary classification approach for span triples proves more stable and effective for discontinuous structures than traditional max-margin methods.
  • Well-Nestedness Trade-off: While well-nestedness simplifies parsing and improves speed, it significantly limits the parser's coverage of actual discontinuous structures, as shown by oracle experiments.

Key Results

  • State-of-the-Art Accuracy: The proposed span-based LCFRS-2 parser achieves the best results among previous chart-based parsers for discontinuous structures on both German and English test sets.
  • Competitive with Transition-Based Parsers: The parser's performance is on par with, and in some cases outperforms, leading transition-based parsers, particularly in all-constituency evaluation.
  • Improved Speed: The parser offers significant speed improvements over previous chart-based LCFRS parsers, with parsing times remaining tractable for sentences up to 45 words without pruning. The well-nested variant (LCFRS-wn-nr-2) is particularly fast.
  • Formalism Impact: Results show a clear correlation between the expressiveness of the grammar formalism (CFG < LCFRS-wn-nr-2 < LCFRS-wn-2 < LCFRS-2) and parsing accuracy, indicating that more powerful formalisms are needed for better coverage.

Limitations and Future Work

  • Formalism Limitations: Even the most expressive LCFRS-2 formalism is not sufficient for complete coverage of all discontinuous structures, as indicated by oracle experiments showing a recall gap. This suggests a need for formalisms that can generate more complex, potentially ill-nested, structures.
  • Fan-out Restriction: The restriction to fan-out 2, while necessary for tractability, might limit the parser's ability to model certain complex discontinuous phenomena.
  • Future Work: The authors suggest that future work should explore formalisms with higher fan-out and the ability to generate non-well-nested trees to further improve accuracy and coverage. They also note the potential for further optimization of the parsing algorithm.

Summary updated

BibTeX
@inproceedings{stanojevic2020span,
  author = {Miloš Stanojević and Mark Steedman},
  title = {{Span-Based LCFRS-2 Parsing}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
}
Figure