Parsimonious Data-Oriented Parsing

Willem H. ZuidemaEMNLP 2007 · OpenReview

Abstract

Data-Oriented Parsing (DOP) traditionally relies on a "maximalist" approach, utilizing all possible subtrees from a treebank as productive grammar elements. While empirically successful, this leads to massive, computationally expensive grammars. This paper introduces Parsimonious Data-Oriented Parsing (P-DOP), which identifies a succinct subset of informative subtrees. By employing a "Push-n-Pull" algorithm to minimize the discrepancy between expected and observed subtree frequencies, P-DOP achieves significant grammar compression and improved efficiency while maintaining or exceeding state-of-the-art accuracy on the OVIS and WSJ corpora.

1. Introduction: The Maximalist Challenge in DOP

Data-Oriented Parsing (DOP), originally proposed by Scha (1990), operates on the principle that human language processing relies on a large library of previously encountered sentence fragments. In the Probabilistic Tree Substitution Grammar (PTSG) formalism, this is implemented by extracting every possible subtree from an annotated corpus.

While this "maximalist" approach captures complex statistical dependencies, it results in a "gigantic" grammar. For instance, a standard DOP model can easily generate millions of rules, posing severe scalability issues and complicating the linguistic interpretation of the resulting model. This paper addresses this bloat by asking if a manageable subset of trees can still accurately describe the language.

2. The P-DOP Framework

The P-DOP approach seeks a middle ground. It remains true to the core DOP philosophy—allowing any subtree to be a productive element—but aims to find a succinct subset of such trees that accurately describes observed distributions over phrase-structure trees.

Examples of elementary tree fragments extracted from a treebank.

By focusing on a parsimonious set of trees, the model becomes computationally tractable and highlights linguistically significant structures. P-DOP is formulated as an enrichment of a standard Probabilistic Context-Free Grammar (PCFG), allowing it to run on fast, off-the-shelf parsers like BitPar.

3. The Push-n-Pull (PNP) Estimation Algorithm

The core innovation of P-DOP is the Push-n-Pull (PNP) estimation procedure. This algorithm iteratively adjusts the probability mass of subtrees based on their statistical "overrepresentation" relative to a baseline PCFG.

  1. Frequency Comparison: The algorithm calculates the "expected frequency" of a subtree (how often the baseline PCFG predicts it should occur) and compares it to the "observed frequency" in the actual treebank.
  2. Probability Adjustment: If a subtree is overrepresented, the algorithm "pulls" probability mass from its constituent smaller rules into the larger structure. Conversely, underrepresented subtrees "push" mass back down to more general rules.
  3. Parsimony Bias: To avoid overfitting, a built-in bias favors smaller trees, ensuring that larger structures are only included if they provide significant statistical evidence beyond what their components explain.

4. Experimental Evaluation

The P-DOP model was evaluated on the OVIS (Dutch spoken dialogue) and WSJ (Wall Street Journal) benchmarks.

4.1 OVIS Results

On the OVIS corpus, P-DOP demonstrated extraordinary compression. It achieved a Complete Match (CM) score of 87.77% using only 11,411 rules. In contrast, the traditional DOP1 model required 1.4 million rules to reach a slightly lower CM of 87.55%.

4.2 WSJ Results

For the WSJ experiments, the author utilized an enriched version of the Penn Treebank, incorporating linguistic features into the node labels to provide a more competitive baseline.

Linguistically enriched subtrees used in the WSJ experiments, showing complex labels like NP-SBJ/3S/BASE.

Adding just 10,000 P-DOP-selected subtrees to a highly optimized baseline improved the F1 score from 83.40 to 83.77. These selected subtrees often corresponded to meaningful linguistic units, such as multi-word expressions (e.g., "New York Stock Exchange") or non-contiguous dependencies (e.g., "more... than").

5. Conclusion

Parsimonious Data-Oriented Parsing offers a solution to the computational bloat of traditional DOP models. By selecting only the most informative fragments, P-DOP produces grammars that are orders of magnitude smaller and significantly faster to parse. While the estimation process remains computationally intensive—taking several days on the WSJ corpus using 2007-era hardware—the resulting models provide a more theoretically sound and linguistically transparent approach to statistical parsing.

Summary updated

Abstract

This paper explores a parsimonious approach to Data-Oriented Parsing. While allowing, in principle, all possible subtrees of trees in the treebank to be productive elements, our approach aims at nding a manageable subset of these trees that can accurately describe empirical distributions over phrase-structure trees. The proposed algorithm leads to computationally much more tracktable parsers, as well as linguistically more informative grammars. The parser is evaluated on the OVIS and WSJ corpora, and shows improvements on efciency, parse accuracy and testset likelihood. 1 Data-Oriented Parsing Data-Oriented Parsing (DOP) is a framework for statistical parsing and language modeling originally proposed by Scha (1990). Some of its innovations, although radical at the time, are now widely accepted: the use of fragments from the trees in an annotated corpus as the symbolic grammar (now known as itreebank grammarsi, Charniak, 1996) and inclusion of all statistical dependencies between nodes in the trees for disambiguation (the iallsubtrees approachi, Collins & Duffy, 2002). The best known instantiations of the DOPframework are due to Bod (1998; 2001; 2003), using the Probabilistic Tree Substitution Grammar (PTSG) formalism. Bod has advocated a maximalist approach to DOP, inducing grammars that contain all subtrees of all parse trees in the treebank, and using them to parse unknown sentences where all of these subtrees can potentially contribute to the most probable parse. Although Bod’s empirical results have been excellent, his maximalism poses important computational challenges that, although not necessarily unsolvable, threaten both the scalability to larger treebanks and the cognitive plausibility of the models. In this paper I explore a different approach to DOP, that I will call iParsimonious Data-Oriented Parsingi (P-DOP). This approach remains true to Scha’s original program, by allowing, in principle, all possible subtrees of trees in the treebank to be the productive elements. But unlike Bod’s approach, P-DOP aims at nding a succinct subset of such elementary trees, chosen such that it can still accurately describe observed distributions over phrasestructure trees. I will demonstrate that P-DOP leads to computationally more tracktable parsers, as well as linguistically more informative grammars. Moreover, as P-DOP is formulated as an enrichment of the treebank Probabilistic Context-free Grammar (PCFG), it allows for much easier comparison to alternative approaches to statistical parsing (Collins, 1997; Charniak, 1997; Johnson, 1998; Klein and Manning, 2003; Petrov et al., 2006).
BibTeX
@inproceedings{zuidema2007parsimonious,
  author = {Willem H. Zuidema},
  title = {{Parsimonious Data-Oriented Parsing}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
  url = {https://openreview.net/forum?id=rJ-2OGGOZS},
}
Figure