A low-complexity, broad-coverage probabilistic Dependency Parser for English

Gerold SchneiderNAACL 2003

TL;DR

This paper introduces a probabilistic dependency parser for English that prioritizes speed and broad coverage over absolute accuracy. By combining finite-state techniques, statistical parsing, and a simplified linguistic grammar, it achieves parsing complexity low enough for real-world applications, making linguistic data more accessible for knowledge management tasks.

What Problem Does This Paper Address?

Modern knowledge management systems, like Information Retrieval and Data Mining, are increasingly leveraging advances in Natural Language Processing (NLP). However, many existing parsing systems are computationally expensive, making them impractical for processing large volumes of unrestricted text. This paper addresses the need for a parser that is fast, robust, and linguistically grounded, capable of producing meaningful syntactic information for downstream applications without prohibitive computational cost.

Methods

The parser employs a hybrid approach, integrating several key techniques:

  • Finite-State Preprocessing: Low-level tasks like Part-of-Speech (POS) tagging and chunking (identifying base noun phrases and verb groups) are handled by fast finite-state methods. This reduces the search space for the main parser.
  • Dependency Grammar (DG): The parser adheres to the principles of Dependency Grammar, a theory known for its relatively flat structures and lack of empty nodes, which simplifies parsing.
  • Probabilistic Models: Two main probabilistic models are used:
  • Lexical Probabilities: Based on Maximum Likelihood Estimation (MLE), these models capture the probability of specific syntactic relations between lexical heads of phrases.
  • PCFG for VP Production: A Probabilistic Context-Free Grammar is used to model verb subcategorization frames, a crucial aspect of DG.
  • Cocke-Younger-Kasami (CYK) Algorithm: This efficient parsing algorithm is adapted for the head-of-chunk-based parsing, contributing to the parser's speed.
  • Restrictive Linguistic Grammar: A hand-written grammar is used, focusing on essential relations and simplifying complex phenomena to maintain efficiency.
  • Beam Search: Unlikely parse candidates are discarded early using a beam search, further improving speed.

Datasets

The parser was trained, developed, and tested on the Penn Treebank (Marcus et al., 1993).

Key Insights and Ideas

  • Speed vs. Accuracy Trade-off: The paper demonstrates that a deliberate choice to reduce complexity, even at the cost of a slight decrease in performance, can yield a parser practical for large-scale applications.
  • Leveraging Finite-State for Efficiency: Offloading tasks like POS tagging and chunking to fast finite-state methods significantly reduces the computational burden on the main parsing engine.
  • Dependency Grammar's Suitability: The flat structure of Dependency Grammar, compared to some constituency-based approaches, is highlighted as a key factor enabling lower complexity and faster parsing.
  • Hybrid Probabilistic Models: Combining lexical probabilities with PCFGs for specific structures (like VPs) provides a robust way to capture linguistic regularities while managing data sparsity.
  • Practicality for Knowledge Management: The output of this parser, functional dependency structures, is presented as a valuable bridge to semantic interpretation and knowledge management tasks, making NLP more accessible to these fields.

Key Results

The paper reports provisional precision and recall values for subject, object, and PP-attachment relations. While slightly lower than state-of-the-art parsers, these figures are presented as a proof of concept for a fast, broad-coverage system. The parser achieves a parsing speed of approximately 30 minutes for 46,527 words on an 800 MHz Pentium 3 PC, including tagging and chunking. This speed is a significant improvement over more complex parsers.

Limitations and Future Work

The authors acknowledge several limitations:

  • Performance Sacrifice: The pursuit of low complexity leads to a slight decrease in parsing accuracy compared to state-of-the-art systems.
  • Tagging and Chunking Errors: Errors from the finite-state preprocessing stages can propagate and affect parsing accuracy.
  • Treebank Mapping Challenges: The mapping from the Treebank's configurational paradigm to functional dependency is not perfect, leading to potential missed or doubled structures.
  • Limited PP Interaction Model: The current grammar does not fully support complex PP interactions, affecting the analysis of relational nouns.

Future work suggested includes:

  • Improving the probabilistic models and dependency extraction.
  • Enhancing the linguistic grammar.
  • Developing more robust evaluation methods, potentially using a standardized DG test suite.
  • Further integration with tagger and chunker approaches.

Summary updated

BibTeX
@inproceedings{schneider2003low,
  author = {Gerold Schneider},
  title = {{A low-complexity, broad-coverage probabilistic Dependency Parser for English}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2003},
}
Figure