A Linear Observed Time Statistical Parser Based on Maximum Entropy Models

Adwait RatnaparkhiEMNLP 1997

TL;DR

This paper introduces a novel statistical parser that achieves state-of-the-art parsing accuracy (87% precision, 86% recall) on the Wall Street Journal corpus. It uniquely combines a simple, human-effort-light feature engineering process with a linear-time parsing algorithm, demonstrating that even higher accuracy (93%) is achievable by considering multiple top-ranked parses.

What Problem Does This Paper Address?

Parsing natural language sentences into their underlying syntactic structures (parse trees) is a fundamental task in Natural Language Processing (NLP). Accurately and efficiently constructing these trees is crucial for many downstream applications like machine translation, information extraction, and question answering. Previous statistical parsers often struggled with either achieving high accuracy or maintaining computational efficiency, especially for longer sentences. This paper aims to bridge this gap by developing a parser that is both highly accurate and computationally efficient, running in linear time with respect to sentence length.

Methods

The parser is built upon a maximum entropy framework, a powerful statistical modeling technique that allows for the flexible combination of various features to make predictions. The core innovation lies in how these features are defined and utilized:

  • Tree-Building Procedures: The parser employs a three-pass, incremental approach to build parse trees. These passes use procedures like TAG (Part-of-Speech tagging), CHUNK (identifying flat phrase structures), and BUILD/CHECK (constructing hierarchical constituents), inspired by shift-reduce parsing but with a more incremental approach.
  • Contextual Predicates and Features: Instead of relying on complex, hand-crafted linguistic rules, the parser uses contextual predicates that check for specific information in the current parsing context. These predicates are then automatically converted into features for the maximum entropy models. This significantly reduces the human effort required for feature engineering.
  • Maximum Entropy Models: These models learn the probability of different parsing actions (like assigning a POS tag or forming a constituent) based on the extracted features. The framework allows for the easy integration of diverse features, including those related to words, POS tags, and constituent labels.
  • Linear-Time Search Heuristic: To find the best parse tree, the parser uses a top-K breadth-first search (BFS). This heuristic explores only the top K most promising partial parses at each step, ensuring that the search remains efficient and runs in linear time with respect to sentence length. This is a significant improvement over algorithms that might explore a much larger search space.

Datasets

  • Training: The parser was trained on sections 2 through 21 of the Penn Treebank Wall Street Journal corpus (release 2), which contains approximately 40,000 sentences.
  • Testing: The parser was evaluated on section 23 of the same corpus, comprising 2,416 sentences.
  • Semantic Tags and Punctuation: For both training and testing, semantic tags (e.g., -LOC, BNF) and reference information (e.g., *-1) were stripped from the trees, and quotation marks were ignored.

Key Insights and Ideas

  • Human Effort Reduction: The paper highlights that by defining contextual predicates and automatically generating features, the human effort required for feature engineering is drastically reduced compared to traditional parsers. This makes the parser more adaptable and easier to improve.
  • The Power of Maximum Entropy: The maximum entropy framework proves to be highly effective in integrating diverse linguistic information, leading to superior parsing accuracy. Its flexibility allows for the incorporation of features that might be difficult to handle with other modeling techniques.
  • Linear Time Parsing is Achievable: The combination of incremental tree-building and the top-K BFS search heuristic demonstrates that high-accuracy parsing can be achieved in linear observed time, a critical factor for real-world applications.
  • Reranking Top N Parses: The paper strongly suggests that considering multiple top-ranked parses (not just the single best one) can significantly boost accuracy. This opens up avenues for secondary models to refine the parsing results.

Key Results

  • State-of-the-Art Accuracy: The parser achieved a parsing accuracy of approximately 87% precision and 86% recall on the Wall Street Journal domain, surpassing previous best results.
  • Linear Observed Time: The parser runs in linear time with respect to sentence length, as confirmed by experimental results (Figure 8).
  • Potential for Higher Accuracy: By considering the top 20 ranked parses, a "perfect" reranking scheme could achieve a dramatic increase in accuracy to 93% precision and recall.
  • Exact Match Improvement: The "Exact Match" metric (where the predicted parse must be identical to the treebank parse, ignoring POS tags) rose from 30% to about 53% when using the top N reranking scheme.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while the feature engineering is simplified, the initial creation of the annotated corpus (Penn Treebank) still requires significant linguistic expertise.
  • The "perfect" reranking scheme is hypothetical; actual reranking schemes would need to be developed.
  • Future Work:
    • The paper strongly advocates for research into reranking schemes to leverage the top N parses and achieve higher accuracy.
  • The flexibility of the maximum entropy framework suggests that further improvements can be made by incorporating additional features.

Summary updated

BibTeX
@inproceedings{ratnaparkhi1997linear,
  author = {Adwait Ratnaparkhi},
  title = {{A Linear Observed Time Statistical Parser Based on Maximum Entropy Models}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {1997},
}
Figure