Creating a Finite-State Parser with Application Semantics

Owen Rambow, Srinivas Bangalore, Tahir Butt, Alexis Nasr, Richard SproatCOLING 2002

TL;DR

This paper introduces PARSLI, a finite-state parser that can be easily tailored to specific application semantics using a declarative lexicon. This approach offers greater control to application designers and is more efficient than using general-purpose parsers for domain-specific Natural Language Understanding (NLU) tasks.

What Problem Does This Paper Address?

Many NLU applications, such as database access or command interfaces, require mapping user input to a fixed set of application-specific actions or semantics. While off-the-shelf parsers exist, adapting them for these "application-semantic NLU" tasks is challenging. This often involves complex post-processing to correct the parser's output and map it to the domain's semantics. Furthermore, general-purpose parsers can be overkill, and retraining them for a specific domain is difficult without annotated data. The authors aim to provide a more direct and controllable way to build parsers for these specialized NLU needs.

Methods

The core of PARSLI is a finite-state (FS) parser built from a lexicalized Tree Adjoining Grammar (TAG). The process involves:

  1. Lexicalized TAG: Each lexical item is associated with elementary trees representing its syntactic structure and valency.
  2. Mapping TAG to FS: Elementary TAG trees are converted into finite-state transducers (FSTs). This involves a depth-first traversal of the tree, where nodes become states in the FST, and transitions represent syntactic functions and semantic roles.
  3. Declarative Lexicon: Application semantics are defined in a hand-editable declarative lexicon, which is then mapped to the TAG structure. This allows designers to easily specify how words and their syntactic roles map to application-specific semantic arguments.
  4. Syntactic Machine: The FSTs derived from elementary trees are combined to form a syntactic machine. This machine directly outputs the desired dependency structure and semantic roles.

This approach separates the lexicon from the syntactic machine, potentially reducing the overall size and complexity.

Datasets

  • Training: The Wall Street Journal (WSJ) corpus is used for training lexical probabilities (p(s|w) and p(w|c)) to map words to syntactic classes.
  • Evaluation: A custom dataset of 205 sentences, randomly chosen from developer inputs to the WORDSEYE system, was used for evaluation. These sentences were manually annotated with the desired dependency structure.

Key Insights and Ideas

  • Application-Specific Parsers are Often Simpler: For many NLU tasks, the full recursive power of general-purpose parsers is unnecessary. A finite-state approach can be sufficient and significantly faster.
  • Declarative Lexicons for Control: Using a hand-editable declarative lexicon, defined in terms of a TAG, gives application designers direct and easier control over the NLU component compared to post-processing general parsers.
  • TAG as a Bridge: Tree Adjoining Grammar serves as an effective intermediate representation, bridging the gap between application semantics and syntactic structure, and facilitating the conversion to finite-state machines.
  • Efficiency Gains: Finite-state approaches offer significant speed advantages, which are crucial for interactive applications.

Key Results

  • Accuracy: The PARSLI parser achieved an accuracy of 0.78 (correct dependency arcs) and a correctness of 0.58 (correct dependency tree) on the evaluated test set.
  • Speed: The average transduction time per sentence was 0.29 seconds, demonstrating the efficiency of the FS approach.
  • Sentence Length Impact: Performance (accuracy and correctness) degrades with increasing sentence length, as expected.
  • N-best Analyses: The system can produce n-best analyses, with scores improving as 'n' increases, suggesting potential for further refinement by better path selection.

Limitations and Future Work

  • Limited Semantic Annotation: The evaluation focused on syntactic behavior because a corpus annotated with semantics was not available. Future work could incorporate semantic annotations.
  • Improving Path Selection: The authors believe further improvements to the 1-best results can be achieved by better choosing the correct path from the FST, potentially using probabilities of syntactic combinations or bilexical probabilities.
  • Extending to Chart Parsers: The approach of using TAG as an interface between application semantics and syntax can also be applied to chart parsers, as discussed in related work.
  • Syntactic Complexity: While sufficient for many interactive systems, the FS approach might not capture the full syntactic complexity of texts like the Wall Street Journal.

Summary updated

BibTeX
@inproceedings{rambow2002creating,
  author = {Owen Rambow and Srinivas Bangalore and Tahir Butt and Alexis Nasr and Richard Sproat},
  title = {{Creating a Finite-State Parser with Application Semantics}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}
Figure