Tree-Bank Grammars

AAAI 1996

TL;DR

This paper challenges the prevailing wisdom that grammars learned directly from hand-parsed sentences (tree-banks) perform poorly. The authors demonstrate that a "tree-bank grammar" derived from the Penn Wall Street Journal tree-bank outperforms other non-word-based statistical parsers on the same corpus, suggesting that tree-bank grammars are more capable than previously assumed.

What Problem Does This Paper Address?

Natural Language Processing (NLP) research has long sought to build parsers that can accurately assign syntactic structure to English sentences. A crucial resource for this endeavor has been "tree-banks" – corpora of sentences meticulously hand-parsed by linguists. While these tree-banks serve as a valuable "gold standard" for evaluating parsers, a common belief within the NLP community is that grammars directly extracted from these tree-banks, termed "tree-bank grammars," are inherently weak. This perception stems from anecdotal evidence and a lack of published performance data. The authors aim to empirically refute this notion and demonstrate the potential of tree-bank grammars.

Methods

The core of the paper's methodology involves constructing a context-free grammar (CFG) by directly reading production rules from the hand-parsed sentences in the Penn Wall Street Journal tree-bank. This grammar is then made probabilistic (a Probabilistic CFG or PCFG) by assigning rule probabilities based on their frequency of occurrence in the training data.

The authors employ a standard chart parser, with two key modifications:

  1. Efficiency Improvement: Enhancements were made to the parser's search mechanism for identifying the most probable parse.
  2. Right-Branching Bias: A heuristic adjustment was introduced to the rule probabilities to favor right-branching structures, addressing a perceived bias in context-free grammars towards center-embedding, which is less common in English. This bias was implemented by adjusting probabilities based on whether a constituent was "ending" (ending just before the final punctuation) or "middle," aiming to correct for an underproduction of ending constituents.

Datasets

The primary dataset used is the Penn Wall Street Journal (WSJ) tree-bank, release 2.1.

  • Training Data: Approximately 1,000,000 words.
  • Testing Data: Approximately 100,000 words, with sentences longer than 40 words excluded due to processing time constraints. The testing data was further split into preliminary and "official" testing sets.

The authors also mention using "held-out data" to estimate the "ending factor" for the right-branching bias modification.

Key Insights and Ideas

  • Tree-bank Grammars are More Powerful Than Believed: The central finding is that grammars directly learned from tree-banks can achieve competitive, and in this case, superior performance compared to other non-word-based parsers. This challenges the widespread skepticism.
  • Lexical Information is Important, But Not Everything: While the authors' grammar relies solely on part-of-speech tags and ignores actual words, it still outperforms parsers that do consider lexical information. This highlights the inherent strength of the syntactic structure captured by the tree-bank. However, they acknowledge that including lexical information would likely further improve performance.
  • Ambiguity is a Major Hurdle: The high ambiguity inherent in Penn tree-bank grammars makes parsing difficult. This ambiguity can lead to a vast number of possible partial constituents, making it challenging for parsers to find the correct parse efficiently.
  • Right-Branching Bias Can Offer a "Free" Improvement: A simple heuristic adjustment to favor right-branching structures, motivated by the nature of English syntax, led to a small but significant improvement in parsing accuracy with minimal added complexity.

Key Results

  • The tree-bank grammar achieved 82.0% precision, 80.0% recall, and 88.0% accuracy on sentences of length 2-40.
  • These results outperform all other non-word-based statistical parsers/grammars tested on the same corpus, including parsers that ignore the actual words.
  • The grammar was able to parse all test sentences, suggesting that "missing rules" are not the primary limitation for tree-bank grammars.
  • The right-branching bias modification resulted in an improvement of 2.4% precision, 2.7% recall, and 2.6% accuracy for sentences of length 2-40, moving from an "unbiased" performance of 79.6% precision, 77.3% recall, and 85.4% accuracy.

Limitations and Future Work

  • Lexical Information: The authors acknowledge that their grammar does not incorporate lexical information (actual words), which they believe is crucial for achieving even higher performance, citing Magerman's [6] work as evidence. They estimate that incorporating word-based statistics could bridge the remaining 5% gap.
  • Ambiguity and Parsing Efficiency: While they made improvements to parsing efficiency, the inherent ambiguity of the grammar remains a challenge. They suggest that further work on parsing techniques, like improved best-first chart parsing, is necessary.
  • Generalizability of Right-Branching Bias: The authors speculate on whether the right-branching bias technique would be effective for grammars other than tree-bank grammars, suggesting further experimentation.
  • Next Steps: The authors' immediate future work involves incorporating word-based statistics on top of their tree-bank grammar to further improve performance.

Summary updated

BibTeX
@inproceedings{1996tree,
  title = {{Tree-Bank Grammars}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure