Aspects of Pattern-matching in Data-Oriented Parsing

Guy De PauwCOLING 2000

TL;DR

This paper proposes reinterpreting Data-Oriented Parsing (DOP) as a pattern-matching problem, aiming to improve efficiency by directly matching larger syntactic substructures from memory. By focusing on maximizing the size of matched patterns rather than just probability, they introduce a Memory-Based Learning approach to parsing that shows promise when combined with traditional probabilistic methods.

What Problem Does This Paper Address?

Data-Oriented Parsing (DOP) is a powerful parsing technique known for its high accuracy and its grounding in psycholinguistic insights about how humans process language. However, a major drawback of DOP is its computational cost. This is largely due to the need to consider multiple derivations for a single parse tree to accurately capture probabilistic information. This process is computationally intensive and doesn't directly align with a clear linguistic backbone. The authors aim to address this by finding a more efficient way to achieve similar results, drawing inspiration from Memory-Based Learning (MBL) and focusing on pattern matching.

Methods

The core idea is to reframe DOP as a pattern-matching problem. Instead of generating numerous derivations and then calculating their probabilities, the system tries to match the largest possible syntactic substructures (patterns) from a memory (a treebank of previously seen structures) to the input sentence. This is inspired by Memory-Based Learning, where new problems are solved by referencing similar past experiences.

The paper introduces a "Pattern-Matching Probabilistic Grammar" (PMPG) approach. This involves:

  1. Indexing Substructures: All substructures in the training treebank are indexed.
  2. Bottom-up Matching: A chart parser generates a parse forest for the input sentence.
  3. Pattern Matching: The PMPG algorithm then attempts to match these indexed substructures (patterns) from memory to the parse forest. The goal is to maximize the size of the matched patterns.
  4. Disambiguation: The system prioritizes parses that are constructed using larger retrieved substructures.

To further improve performance, they also propose a combined system (PCFG+PMPG) that leverages the strengths of both traditional Probabilistic Context-Free Grammars (PCFGs) and their proposed PMPG approach.

Datasets

The experiments were conducted on an edited version of the ATIS-II corpus (Marcus, Santorini, and Marcinkiewicz, 1993), which contains 578 sentences. The corpus was pre-processed by limiting sentence length to 15 words and removing certain semantic flags to make it more suitable for the parsing task. The edited corpus retained 562 sentences for evaluation.

Key Insights and Ideas

  • DOP as Pattern Matching: The most significant insight is the reinterpretation of DOP as a pattern-matching problem. This shifts the focus from pure probabilistic calculation of derivations to maximizing the retrieval of larger, meaningful syntactic chunks from memory.
  • Memory-Based Learning for Syntax: The paper demonstrates that principles from Memory-Based Learning, successful in lower-level NLP tasks, can be adapted for syntactic parsing by treating syntactic structures as memory items to be matched.
  • Efficiency Through Pattern Matching: By directly matching larger substructures, the hope is to bypass the computationally expensive process of generating and evaluating numerous derivations, leading to more efficient parsing.
  • Complementary Strengths of PCFG and PMPG: The authors found that while PMPG excels at capturing context-sensitivity through large pattern matching, it can sometimes overlook common-sense probabilistic rules. Conversely, PCFGs are good at providing a baseline probabilistic ordering but struggle with deeper context. Combining them offers a more robust solution.

Key Results

  • PCFG Baseline: A standard PCFG achieved 66.4% parse accuracy overall and 81.8% on parsable sentences.
  • PMPG Performance: The PMPG approach, while aiming for context-sensitivity, showed significantly lower performance, with 58.2% overall parse accuracy and 71.7% on parsable sentences. This suggests that PMPG alone overestimates the importance of substructure size.
  • Combined PCFG+PMPG: The combined system achieved 71.5% overall parse accuracy and a strong 88.2% on parsable sentences, approaching the performance of the original DOP1 model. This indicates that combining probabilistic rules with pattern matching is a promising direction.
  • Grammar Sparseness Bottleneck: A significant issue identified was grammar sparseness, where the parser couldn't find rules for certain NP structures, limiting overall parse accuracy to 81%.

Limitations and Future Work

  • Grammar Sparseness: The paper acknowledges that grammar sparseness is a major bottleneck, preventing the full exploitation of the pattern-matching algorithm's potential. Future work could involve grammatical smoothing or using larger, more comprehensive grammars.
  • PMPG Overestimation: PMPG, in its standalone form, overestimates the value of large substructure matches, leading to lower accuracy.
  • Computational Efficiency Optimization: The authors suggest optimizing the PCFG+PMPG system for computational efficiency, potentially by using a PCFG to pre-filter candidates for the PMPG.
  • Comparison with Full DOP: A direct comparison of the PMPG+PCFG system with the full DOP model on identical datasets is recommended.
  • GRAEL System: The paper mentions the GRAEL system, which uses evolutionary techniques to address grammatical sparseness, as a potential avenue for future research.
  • Parameter Optimization: Future work will involve optimizing parameters for the PMPG+PCFG system, such as the number of most probable parses to consider and the weighting of different algorithms.

Summary updated

BibTeX
@inproceedings{pauw2000aspects,
  author = {Guy De Pauw},
  title = {{Aspects of Pattern-matching in Data-Oriented Parsing}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2000},
}
Figure