Parsing the LOB Corpus

Carl de MarckenACL 1990 · DOI

In the early 1990s, computational linguistics faced a significant hurdle: the transition from parsing clean, hand-crafted sentences to processing the messy, complex reality of "real-world" text. Carl G. de Marcken's classic MIT AI Lab paper describes a system specifically engineered for this challenge, prioritizing speed and robustness to handle the million-word Lancaster/Oslo-Bergen (LOB) corpus.

The Robustness Gap in Early NLP

Traditional parsers of the era often struggled with sentences exceeding a dozen words, frequently succumbing to exponential time complexity or failing entirely on ungrammatical structures. Real-world corpora like the LOB contain sentences that often stretch beyond 50 words, filled with parentheticals and complex syntactic constructions. De Marcken’s goal was to build a system that wouldn't "choke" on such data, providing useful syntactic analyses even when a complete parse was unattainable.

Methodology: Speed through Flexibility

The system's success rests on two primary innovations: a novel statistical disambiguator and a hybrid parsing strategy.

Method D: The Power of "Maybe"

Most part-of-speech (POS) taggers at the time were designed to select a single best tag for each word. De Marcken argued that this premature commitment often led to cascading errors. Instead, he introduced Method D, a "multivalued" disambiguator. It returns a set of likely categories for a word if their probabilities are within a certain factor ($F$) of the most likely tag. This allows the parser to use broader syntactic context to resolve ambiguities that a local statistical model cannot.

The Hybrid Parser and "Lowering"

The parser itself combines bottom-up recognition (identifying local structures like Noun Phrases) with top-down firing of higher-level rules. To maintain efficiency, de Marcken introduced a "lowering" heuristic. When a phrase is accepted into a rule, it is "lowered" to the bottom of the processing queue. This deterministic, greedy search bias prevents the parser from exploring an exhaustive search space, which is critical for processing long sentences in linear time.

Efficiency metrics: Number of phrases built and processing time vs. sentence length.

As shown in the performance graphs above, the number of phrases built remains manageable even as sentence length increases, a direct result of the lowering heuristic and the efficient internal grammar.

Key Results and Robustness

The system demonstrated remarkable performance on the LOB corpus:

  • Accuracy: Method D achieved a disambiguation accuracy of 265 words per error, a ten-fold improvement over standard algorithms of the time.
  • Efficiency: The entire million-word corpus could be parsed in just a few hours.
  • Graceful Failure: Perhaps most importantly, the parser was designed to fail gracefully. If a full sentence parse was impossible, it would return the longest valid constituent phrases found.
Number of phrases returned vs. sentence length, demonstrating the system's ability to provide useful partial analyses for long sentences.

This "graceful failure" is illustrated by the relationship between sentence length and the number of phrases returned. Even for very long sentences where a single spanning tree might be elusive, the system consistently provides a set of high-quality constituent phrases, ensuring the output remains valuable for downstream data gathering tasks.

Conclusion

De Marcken's work highlighted that for large-scale NLP, theoretical completeness is often less important than robustness and speed. By embracing ambiguity at the tagging stage and using clever heuristics to prune the search space, he created a system capable of tackling the LOB corpus's million words with unprecedented efficiency. This approach paved the way for modern, robust statistical parsers that dominate the field today.

Summary updated

BibTeX
@inproceedings{marcken1990parsing,
  author = {Carl de Marcken},
  title = {{Parsing the LOB Corpus}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1990},
  doi = {10.3115/981823.981854},
}
Figure