Using an Annotated Language Corpus as a Virtual Stochastic Grammar

Rens BodAAAI 1993

Introduction

In the early 1990s, natural language processing (NLP) faced a significant challenge known as the "multiplicity" problem. Formal grammars often generated an overwhelming number of valid syntactic analyses for a single sentence, many of which were semantically nonsensical. While Stochastic Context-Free Grammars (SCFGs) attempted to mitigate this by assigning probabilities to rules, they were fundamentally limited by their "context-blind" nature—they could not capture how structural choices in one part of a sentence might depend on structures elsewhere.

Rens Bod’s 1992 paper introduces Data Oriented Parsing (DOP), a paradigm shift that abandons the traditional step of "learning" a grammar from a corpus. Instead, the annotated corpus itself serves as the grammar.

The Data Oriented Parsing Framework

The core philosophy of DOP is to use data directly rather than inferring abstract rules. The framework relies on four key components:

  1. Subtrees as Rules: Every connected subgraph of every tree in a corpus is treated as a potential building block. This allows the model to capture both local and long-distance dependencies automatically.
  2. The Substitution Operation: Subtrees are combined using a composition operator ($\circ$), where one subtree is substituted into the leftmost matching leaf node of another.
  3. Summing Derivations: A single parse tree can be formed by many different combinations (derivations) of subtrees. The probability of a parse is the sum of the probabilities of all its possible derivations, allowing the model to account for overlapping context.
  4. Monte Carlo Parsing: Due to the astronomical number of possible subtrees, exhaustive calculation is impossible. Bod introduces a Monte Carlo parser that randomly samples parses, converging to the most probable one in polynomial time.
Figure 5: Illustration of the composition of subtrees to form a complete parse tree.

The power of DOP lies in its ability to use "deep" subtrees that preserve structural context. As shown in Figure 6, larger subtrees can encapsulate specific lexical dependencies, such as the relationship between a verb and its object.

Figure 6: A different derivation of a parse tree using a deeper subtree that includes lexical information.

Experimental Evaluation

The model was evaluated using the Air Travel Information System (ATIS) corpus, utilizing 750 labeled bracketings from the Penn Treebank. The system achieved a remarkable 96% parsing accuracy on the test set when using subtrees of unbounded depth.

A key finding was that "depth matters": accuracy increased rapidly from 87% with subtrees of depth 2 to 92% at depth 3. The highest accuracy was only reached when the model was allowed to use the largest possible subtrees available in the corpus, confirming that redundancy and depth are features that strengthen the statistical model.

Discussion and Future Work

While DOP demonstrated high accuracy and data efficiency, several challenges remain. The "rare subtree" problem suggests that subtrees appearing only once may lead to poor probability estimations, requiring future research into smoothing techniques. Additionally, scaling the approach to massive corpora like the Wall Street Journal presents memory and search bottlenecks. Finally, the author acknowledges that achieving 100% accuracy likely requires integrating semantic or pragmatic analysis, as the current model is purely syntactic.

Despite these limitations, DOP proved that treating an annotated corpus as a virtual stochastic grammar provides a robust mechanism for handling the complexities of natural language.

Summary updated

BibTeX
@inproceedings{bod1993using,
  author = {Rens Bod},
  title = {{Using an Annotated Language Corpus as a Virtual Stochastic Grammar}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure