TL;DR
This paper introduces SXLFG, a novel parser for the Lexical-Functional Grammars (LFG) formalism that efficiently handles natural language text by processing word lattices and computing functional structures on a shared forest. It offers robust parsing capabilities, even for complex or slightly ungrammatical sentences, by incorporating error recovery mechanisms and a novel over-segmentation strategy.
What Problem Does This Paper Address?
Parsing natural language with formalisms like LFG, which offer rich linguistic expressivity, often comes at a significant computational cost, making them impractical for real-world applications. Traditional robust parsing methods (e.g., Markov models) sacrifice linguistic depth. This paper aims to bridge this gap by developing an LFG parser that is both linguistically expressive and computationally efficient and robust, capable of handling the variability and potential errors found in natural language text.
Methods
The core of SXLFG is built upon a general Context-Free Grammar (CFG) parser, specifically an adaptation of the Earley algorithm. This parser takes word lattices as input and represents the analysis as a shared forest. A subsequent phase computes the LFG functional structures by traversing this shared forest in a bottom-up manner. A key innovation is the efficient computation of functional structures by sharing common substructures, preventing the exponential blow-up often associated with LFG parsing.
To enhance robustness, SXLFG incorporates several error recovery techniques. During the CFG parsing phase, it can recover from errors in the input or grammar. If functional structure computation fails, a second attempt is made with relaxed coherence checks. For sentences that remain unanalyzed, a "sur-segmentation" strategy is employed, breaking down unanalyzable sentences into smaller, potentially parsable segments at various levels (e.g., sentence boundaries, punctuation, conjunctions). Disambiguation is handled using a set of rules applied to the functional structures.
Datasets
The paper evaluates SXLFG on the following corpora:
- EUROTRA: A corpus of 334 phrases.
- TSNLP: A corpus of 1661 phrases.
- EASY corpus: A large-scale corpus of 40859 phrases.
These corpora are used to assess the parser's efficiency and coverage. The paper does not introduce new annotated datasets but rather leverages existing ones for evaluation.
Key Insights and Ideas
- Shared Forest for LFG: Representing LFG analyses as a shared forest is crucial for computational efficiency, allowing for the sharing of common substructures across multiple analyses.
- Bottom-Up Functional Structure Computation: Computing functional structures in a bottom-up fashion on the shared forest enables efficient sharing and avoids recomputing structures for common sub-analyses.
- Robustness through Multi-Level Error Recovery: The combination of Earley-based error recovery during CFG parsing and the novel sur-segmentation strategy for unanalyzable sentences makes SXLFG remarkably robust to grammatical errors and incomplete coverage.
- Trade-off between Coverage and Speed: The paper acknowledges that increasing robustness (e.g., through higher time-out values or more aggressive segmentation) can impact analysis speed, highlighting a common trade-off in NLP systems.
Key Results
The evaluation demonstrates SXLFG's efficiency and robustness:
- Efficiency: On the EASy corpus, the parser achieves high coverage (66.62% without coherence checks, 41.95% with) within a 15-second time-out. For valid CFG analyses, the average parsing time is very low (0.01s for CFG support, 3.35s for complete analysis).
- Robustness: The sur-segmentation mechanism allows for analysis of sentences that would otherwise fail, albeit with a potential decrease in analysis quality at deeper segmentation levels.
- Coverage: The parser achieves reasonable coverage on various corpora, with the highest coverage reported on the TSNLP corpus (98.50% without coherence checks).
Limitations and Future Work
The authors acknowledge several limitations and suggest future research directions:
- Grammar Coverage: The current French grammar is not fully comprehensive, particularly for complex constructions like clivées, comparatives, and elliptical coordinations. Future work should focus on extending and refining this grammar.
- Ambiguity of CFG Support: While the Earley parser is relatively insensitive to ambiguity, a highly ambiguous CFG support grammar can still lead to prohibitive computation times for functional structures.
- Performance of Functional Structure Computation: Further improvements in the efficiency of computing functional structures are desirable.
- Disambiguation Techniques: While rule-based disambiguation is used, exploring probabilistic methods could offer further enhancements.
- LFG Formalism Extension: Ideas for extending the LFG variant to better handle certain linguistic phenomena, such as coordinated structures, are mentioned.
Summary updated