TL;DR
This paper introduces a novel application of Explanation-Based Learning (EBL) to parsing Lexicalized Tree-Adjoining Grammars (LTAG). By immediately generalizing parses and representing them as Finite State Transducers (FSTs), the authors achieve significant speedups in parsing while maintaining high coverage, particularly when combined with a lightweight "stapler" parser.
What Problem Does This Paper Address?
Natural language parsing, especially with complex grammars like LTAG, can be computationally expensive. While EBL has been explored for grammar specialization, previous approaches often required complex tree traversal to generalize parses. This paper tackles the challenge of making EBL more efficient and effective for LTAG parsing, aiming to speed up the process without sacrificing accuracy. The goal is to leverage EBL to create a system that can quickly parse new sentences by reusing knowledge learned from previously parsed examples, especially in the context of wide-coverage grammar development systems.
Methods
The core innovation lies in how EBL is applied to LTAG. Instead of complex generalization procedures, the authors exploit the structure of LTAGs to achieve immediate generalization. This involves:
- Feature-Generalization: Uninstantiating specific lexical items and feature values within the parse trees of training sentences.
- Modifier-Generalization: A novel aspect that allows for generalization over recursive structures (like prepositional phrases) by representing them as regular expressions. This enables parsing sentences with varying numbers of modifiers, not just those of the same length as training examples.
- Finite State Transducer (FST) Representation: The generalized parses are encoded as FSTs. This representation allows for efficient matching and retrieval of generalized parses based on the Part-of-Speech (POS) sequence of the input sentence.
- "Stapler" Parser: A lightweight parser is introduced. Its role is to take the output of the EBL lookup (an "almost parse") and complete it by performing term unification and computing alternate modifier attachments. This significantly speeds up the parsing process compared to using a full LTAG parser alone.
Datasets
The experiments were conducted on several corpora:
- ATIS (Air Travel Information System): Used for both training and testing, with a split of 365 sentences for training and 100 for testing.
- IBM-Manual Corpus: Used for experiments measuring performance across different corpora.
- Alvey Test Set: Composed of noun definitions from the LDOCE dictionary, also used for cross-corpus evaluation.
Key Insights and Ideas
- Immediate Generalization is Key: The inherent structure of LTAGs allows for a more direct and efficient generalization process than previously explored in EBL for NLP.
- Modifier-Generalization is Powerful: The ability to generalize over recursive structures (like multiple prepositional phrases) is a significant advantage, allowing the system to handle variations in sentence length and complexity that are not present in the training data.
- FSTs as a Unified Representation: Encoding generalized parses as FSTs provides a compact and computationally efficient way to store and retrieve learned parsing knowledge.
- The "Stapler" is a Game Changer: Combining the EBL lookup with a simple "stapler" parser offers a substantial speedup, demonstrating the effectiveness of a hybrid approach that leverages both learned knowledge and a lightweight parsing mechanism.
Key Results
The paper reports significant performance improvements:
- Speedup: The combined EBL lookup and "stapler" system achieved a speedup of approximately 15 times compared to a system without EBL.
- Coverage: The EBL lookup component achieved 80% coverage on the ATIS test set. When combined with the XTAG parser, the system achieved 90% coverage.
- Response Times: For the ATIS corpus, the EBL lookup alone took an average of 1.78 seconds per sentence, while the full XTAG system took 125.18 seconds. The EBL + XTAG parser combination reduced this to 62.93 seconds, and the EBL + Stapler system further reduced it to 8.00 seconds.
- Cross-Corpus Performance: The FST representation demonstrated varying coverage (40%-80%) and response times across different corpora, indicating the generalizability of the approach.
Limitations and Future Work
- Modifier Attachment Ambiguity: The paper acknowledges that the modifier-generalization approach might not compute all possible attachments for modifiers, leaving some ambiguity to be resolved by the "stapler."
- Instantiation Issues: For a small percentage of sentences (10% in Experiment 2(c)), the generalized parse retrieved could not be instantiated with the sentence's features, leading to a drop in coverage.
- Future Work: The authors propose extending the approach to corpora with fewer repetitive sentence patterns by generalizing at the phrasal level rather than the sentence level. They also suggest exploring this approach with other lexicalized grammars.
Summary updated