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.
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.
- 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.
- 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.
- 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.
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