Analyse syntaxique profonde à grande échelle: SxLFG

Pierre Boullier, Benoît SagotHAL 2005

TL;DR

This paper introduces SXLFG, a novel parser for Lexical Functional Grammars (LFG) designed for large-scale, deep syntactic analysis of natural language. It achieves efficiency and robustness by integrating a context-free parser with sophisticated functional structure computation and error handling, enabling the analysis of millions of words with grammars that are both broad and ambiguous.

What Problem Does This Paper Address?

Traditional NLP methods often sacrifice deep linguistic analysis for speed, using techniques like Markov models or finite-state automata that provide shallow representations. However, for tasks requiring a nuanced understanding of syntax, such as capturing long-distance dependencies or complex phrasal structures, these methods fall short. LFG offers a powerful framework for deep syntactic analysis, but its computational complexity (NP-complete) has historically made it impractical for large-scale corpus processing. This paper addresses the challenge of building an LFG parser that is both linguistically rich and computationally efficient and robust enough for real-world applications.

Methods

SXLFG employs a multi-stage approach:

  • Context-Free (CFG) Parsing: It uses a modified Earley parser to handle CFG "skeleton" grammars, which are the underlying structure of LFG grammars. This parser is adapted to accept Directed Acyclic Graphs (DAGs) as input, representing words and their potential analyses.
  • Functional Structure (f-structure) Computation: This is the core innovation. Instead of computing f-structures for each individual parse tree, SXLFG computes them on top of a shared CFG forest. This is achieved through:
  • Computation Sharing: Reusing common sub-structures.
  • Lazy Evaluation: Computing structures only when needed.
  • Compact Data Representation: Efficiently storing information.
  • Synthesized Computation: Ensuring that f-structure computation is strictly bottom-up and cumulative.
  • Robustness Techniques:
    • Error Recovery: Mechanisms are implemented at both the CFG and f-structure levels to handle ungrammatical input or insufficient grammar coverage. This involves strategies to "recover" from parsing failures and continue analysis, aiming to produce complete, albeit potentially partial, analyses.
  • Disambiguation: Both internal (on intermediate nodes) and global (at the root) disambiguation techniques are employed, using a set of heuristic rules based on linguistic principles to select the most plausible analyses.

Datasets

The paper evaluates SXLFG on a large corpus of journalistic text:

  • Corpus: Approximately 5 million words (over 5.5 million transitions in the DAGs) extracted from "Le Monde diplomatique."
  • Grammar: An LFG grammar for French, developed by L. Clément for the XLFG system, with broad coverage.
  • Lexicon: The Lefff lexicon, containing morphosyntactic and syntactic information for over 500,000 entries.

Key Insights and Ideas

  • Shared Forest for F-structure Computation: The most significant insight is computing f-structures on the shared CFG forest rather than on individual parse trees. This drastically reduces redundancy and improves efficiency, especially for ambiguous grammars.
  • Synthesized F-structure Computation: The bottom-up, cumulative approach to f-structure calculation is key to enabling sharing and efficiency.
  • Robustness as a Necessity: The paper highlights that for real-world applications, parsers must be robust. SXLFG's error recovery mechanisms are crucial for handling imperfect input and incomplete grammars, ensuring that an analysis is produced even when the input is not perfectly grammatical.
  • Linguistic Heuristics for Disambiguation: The use of linguistically motivated heuristic rules for disambiguation, rather than purely statistical models, is presented as an effective approach, especially when annotated data for statistical models is scarce.

Key Results

  • Efficiency: SXLFG can analyze approximately 5 million words in under 12 hours on standard hardware. With aggressive timeouts (0.1s), the analysis of 5.5 million transitions takes about 2.5 hours.
  • Coverage: The grammar achieves a coverage of 58.5% for phrases for which a coherent and complete f-structure is produced. Error recovery mechanisms contribute to analyzing an additional 0.85% of phrases that would otherwise fail.
  • Ambiguity Handling: Despite the massive ambiguity of the CFG skeleton (millions of trees for some phrases), the f-structure computation and disambiguation techniques manage to produce a reasonable number of analyses.
  • Robustness: Error recovery techniques are effective, with only 6.6% of phrases failing CFG recognition and 12.3% hitting the analysis timeout.

Limitations and Future Work

  • Grammar Dependency: The performance of the generated parser is inherently tied to the quality and ambiguity of the input grammar. The paper acknowledges that while SXLFG is designed to handle ambiguous grammars, its performance is not independent of the grammar's characteristics.
  • No Statistical Disambiguation: The current disambiguation relies on heuristic rules. The paper notes that integrating statistical models for disambiguation is possible and could be explored further.
  • Comparison with Other Systems: Direct quantitative comparison with other LFG parsers like XLE is difficult due to differing evaluation methodologies and the proprietary nature of some results.
  • Future Work: The authors suggest that further research could explore the integration of statistical disambiguation methods and more extensive comparisons with existing systems. The paper also implicitly points towards the potential for SXLFG to be used with other languages and grammars.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{boullier2005analyse,
  author = {Pierre Boullier and Benoît Sagot},
  title = {{Analyse syntaxique profonde à grande échelle: SxLFG}},
  booktitle = {HAL},
  year = {2005},
}
Figure