Recovery of Empty Nodes in Parse Structures

Denis Filimonov, Mary HarperEMNLP 2007

TL;DR

This paper introduces a novel probabilistic model for automatically identifying and inserting "empty nodes" (specifically WH-traces) into syntactic parse trees. This is crucial for applications like natural language understanding and speech recognition, as these traces are often omitted by parsers but carry important grammatical information. Their method combines hand-crafted patterns with a probabilistic grammar, achieving state-of-the-art performance on recovering WH-traces.

What Problem Does This Paper Address?

Syntactic parsers, which analyze sentence structure, often produce parse trees that are missing certain grammatical elements called "empty nodes" or "traces." These traces are particularly important for representing the movement of phrases in a sentence, such as when a question word (like "who" or "what") is moved from its original position to the beginning of the sentence. For example, in "Who did you see?", the "who" has moved from the object position of "see." Parsers often omit the trace in the object position.

This omission is problematic for downstream applications that rely on a complete syntactic representation, such as mapping sentences to logical forms or building more accurate language models. The paper focuses on recovering "WH-traces," which are the empty nodes associated with the movement of WH-phrases. While some previous work has addressed this, the authors propose a new approach that combines the strengths of rule-based pattern matching with probabilistic modeling to improve accuracy.

Methods

The core of the proposed method is a two-pronged approach:

  1. Tree-Matching Patterns: A set of hand-written patterns, often using regular expressions, are designed to identify specific subtree structures within a parse tree. These patterns guide the potential locations where a WH-trace might exist. The paper developed numerous patterns for different types of WH-phrases (WHNP, WHADVP, WHPP, WHADJP).
  2. Probabilistic Model: To select the most likely location for a trace when multiple patterns suggest possibilities, a probabilistic model is employed. This model is framed as a probabilistic context-free grammar (PCFG) where the patterns act as terminals. The model learns probabilities from data to decide which pattern chain (sequence of pattern applications) is most likely to correspond to a correct trace insertion.

The authors also introduce the concept of "Tree Classes" to group similar parse tree structures, allowing the probabilistic model to generalize better. They formalize this using a "Pattern Grammar" and a "Gap Automaton" to represent the possible sequences of pattern applications.

Datasets

  • Penn Treebank (PTB): Used for training and evaluating the model. Specifically, sections 00-22 were used for training, and section 23 for evaluation.
  • Broadcast News Penn Treebank (BN): Used to assess the robustness of the algorithm on a different genre of text.

The paper does not introduce new benchmarks but evaluates its performance against existing state-of-the-art methods on these standard datasets.

Key Insights and Ideas

  • Combining Patterns and Probabilities is Key: The paper demonstrates that a hybrid approach, leveraging both the precision of hand-crafted patterns and the generalization power of probabilistic models, is highly effective for WH-trace recovery.
  • Tree Classes for Generalization: Grouping parse trees into "Tree Classes" based on their pattern application history helps the model learn more robustly, especially when dealing with the vast diversity of syntactic structures.
  • Dependency Metric is More Informative: The authors argue that a "head dependency" metric, which focuses on the lexical head of the gap and its co-indexed WH-phrase, is a more direct and informative measure of gap insertion performance than other metrics, particularly when evaluating on automatically parsed trees.
  • Parse Errors are a Major Hurdle: The significant drop in performance when moving from gold-standard trees to automatically parsed trees highlights that parser errors are a primary source of error for gap insertion systems.

Key Results

The paper reports state-of-the-art performance on WH-trace recovery.

  • On gold standard trees, their method achieved results very close to the upper bound for WHNP recovery using the Campbell metric.
  • On automatically generated parses (from Charniak and Bikel parsers), their algorithm compares favorably to existing methods like Johnson (2002) and Gabbard et al. (2006) across various metrics. For instance, on gold trees, their F1 scores for WHNP were 97.9% (Charniak) and 92.6% (Bikel), outperforming previous methods.
  • Performance on WHPP gaps was lower, which the authors attribute to the smaller number of WHPP gaps in the training data and the wider range of possible attachment sites for prepositional phrases.

Limitations and Future Work

  • Limitations:
    • Parse Errors: The performance is significantly impacted by errors in the input parse trees.
  • WHPP Performance: The model's performance on WHPP gaps needs improvement, likely due to data sparsity and the inherent ambiguity of prepositional phrase attachment.
  • Coverage: While expressive, the limited number of patterns means some rare cases might be left uncovered.
  • Annotation Inconsistencies: PTB annotation guidelines can lead to inconsistencies in gap attachment decisions, affecting both training and evaluation.
  • Future Work:
    • Lexicalization: Incorporating lexical information (e.g., the head word of the gap) into the model is suggested to resolve errors, especially for WHADVPs and WHPPs.
  • Automatic Pattern Inference: Developing methods to automatically infer patterns from treebanks would allow for easier adaptation to new languages.
  • Improving WHPP/WHADJP Performance: Further research is needed to address the lower performance on these gap types.

Summary updated

BibTeX
@inproceedings{filimonov2007recovery,
  author = {Denis Filimonov and Mary Harper},
  title = {{Recovery of Empty Nodes in Parse Structures}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure