Combining Unsupervised and Supervised Methods for PP Attachment Disambiguation

Martin VolkCOLING 2002

TL;DR

This paper tackles the challenge of prepositional phrase (PP) attachment disambiguation, a crucial task in natural language processing. The authors demonstrate that when manually annotated data is scarce, combining unsupervised and supervised methods yields superior accuracy compared to using either approach alone, offering a practical solution for languages with limited treebanks.

What Problem Does This Paper Address?

Natural language understanding often requires determining how a prepositional phrase (PP) attaches to a sentence. For example, in "I saw the man with the telescope," does "with the telescope" describe how the man was seen, or what the man was holding? This ambiguity, known as PP attachment disambiguation, is vital for accurate parsing and information extraction. Traditional approaches fall into two camps: unsupervised methods that learn from vast amounts of raw text, and supervised methods that rely on manually annotated (treebanked) data. While supervised methods generally achieve higher accuracy, they require extensive, costly manual annotation. This paper addresses the scenario where only a small amount of manually annotated data is available, questioning whether a hybrid approach can outperform purely supervised or unsupervised methods.

Methods

The core of this paper is the development of a hybrid disambiguation algorithm that strategically combines unsupervised and supervised information.

  • Unsupervised Methods: The authors leverage cooccurrence statistics, specifically the frequency with which a verb or noun appears with a preposition. They compute "cooccurrence values" (akin to probability estimates) for verb-preposition and noun-preposition pairs. To address an observed imbalance where cooccurrence values tend to favor verb attachments, they introduce a "noun factor" to strengthen noun-attachment signals. They also explore using triple cooccurrences (verb, preposition, and the noun within the PP) and introduce "support verb units" (pre-defined patterns indicating verb attachment) as highly reliable signals.
  • Supervised Methods: They employ a "Back-off" model, a standard supervised technique. This model prioritizes the most specific information available (e.g., attachment decisions for complete quadruples of (verb, noun1, preposition, noun2)) and "backs off" to less specific information (triples, pairs, or even just prepositions) if the more specific information is missing from the training data.
  • Hybrid Approach: The novel contribution is the integration of these methods into a multi-level decision algorithm. This algorithm prioritizes decisions based on their reliability, starting with the most accurate signals (like support verb units and supervised quadruples/triples) and progressively moving to less reliable but more abundant signals (unsupervised cooccurrences, then supervised pairs, and finally default decisions). The noun factor is applied at various stages to correct for inherent biases.

Datasets

  • NEGRA Treebank: A German treebank containing 10,000 sentences from newspapers. This was used to extract 4-tuples (verb, noun1, preposition, noun2) for supervised training and evaluation.
  • "Computer-Zeitung" (CZ) Corpus: A large corpus (5.5 million words) of a German computer science magazine. This was used for unsupervised training. A subset of 3000 sentences from this corpus, containing ambiguous PP attachments, was manually disambiguated to create a second test set (CZ test set).

Key Insights and Ideas

  • The Power of Combination: The most significant insight is that for PP attachment disambiguation, especially when manual data is scarce, a carefully designed combination of unsupervised and supervised methods significantly outperforms either approach in isolation.
  • Addressing Imbalances: The paper highlights the inherent bias in unsupervised cooccurrence statistics (favoring verb attachments) and proposes a practical solution (the noun factor) to mitigate this.
  • Hierarchical Reliability: The success of the hybrid approach hinges on ordering decision levels by their reliability. Highly accurate but less frequent signals (like supervised triples) are prioritized over more frequent but less accurate signals (like unsupervised pairs).
  • Domain Overlap Matters: For supervised methods, the domain of the training data significantly impacts performance. Using a training set that overlaps in domain with the test set yielded better results than using a larger, but domain-mismatched, training set.

Key Results

  • Unsupervised Methods Alone: Achieved up to 81.3% accuracy on the CZ test set with a noun factor, and 81.67% when incorporating triple cooccurrences and other features.
  • Supervised Methods Alone: Using the NEGRA treebank for training on the CZ test set yielded 73.98% accuracy. Cross-validation on the CZ test set showed that domain overlap was crucial, with a 77% accuracy achieved by training on a subset of the CZ test set itself.
  • Combined Approach: The hybrid algorithm achieved an impressive 80.98% accuracy on the CZ test set (with 100% coverage), outperforming both the best unsupervised result (81.67% but with lower coverage) and the supervised result (73.98%). This demonstrates the benefit of combining the strengths of both approaches.
  • Improved Accuracy on NEGRA: When the roles were reversed (training on CZ, testing on NEGRA), the combined approach improved accuracy to 71.95% from 68.29% for the pure supervised method.

Limitations and Future Work

  • Limited German Treebank: The authors acknowledge that the availability of only a small German treebank (10,000 sentences) constrained their experiments, particularly for supervised methods. They suggest that larger treebanks would likely further improve supervised performance.
  • WWW Cooccurrence Frequencies: The paper briefly mentions future work involving integrating cooccurrence frequencies obtained from WWW search engines, suggesting this as a promising avenue for further improving PP attachment disambiguation.
  • Decision Level Optimization: While the paper presents a well-ordered hierarchy of decision levels, further fine-tuning of this order and the specific thresholds could potentially yield even better results.

Summary updated

BibTeX
@inproceedings{volk2002combining,
  author = {Martin Volk},
  title = {{Combining Unsupervised and Supervised Methods for PP Attachment Disambiguation}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}
Figure