A Discriminative Learning Model for Coordinate Conjunctions

Masashi Shimbo, Kazuo HaraEMNLP 2007

TL;DR

This paper introduces a novel discriminative learning framework for automatically detecting and disambiguating coordinate conjunctions (like "and" or "or") in natural language. By adapting sequence alignment techniques and using a perceptron-based approach, their model can learn from less strictly annotated data, significantly reducing the cost of training and achieving state-of-the-art results on a challenging dataset.

What Problem Does This Paper Address?

Natural language is rife with ambiguity, and one significant source is the way we coordinate phrases, clauses, or even sentences. For example, in "I saw the man with the telescope and the woman with the binoculars," it's unclear if "with the telescope" modifies "man" or the entire phrase "man and woman." This ambiguity, known as coordination ambiguity, is a persistent challenge for natural language processing systems, including advanced parsers. While previous work has tackled this, it often relies on restrictive assumptions, such as knowing the exact boundaries of coordinated phrases beforehand, which is impractical in real-world scenarios. Furthermore, combining various heuristic rules for disambiguation has been difficult. This paper aims to address these limitations by proposing a flexible and robust method for detecting and disambiguating these coordinations.

Methods

The core of the proposed method is a discriminative learning model built upon sequence alignment. Instead of relying on hand-crafted rules, the model learns to adapt a "substitution matrix" (which assigns scores to different alignment operations) from training data. A key innovation is their ability to handle training examples where only the boundaries of coordinated conjuncts are marked, not full word-by-word alignments. This significantly reduces annotation costs.

They adapt the Viterbi algorithm, commonly used in computational biology for sequence alignment, to their problem. They define an "edit graph" where paths represent potential alignments of coordinated phrases. To reconcile the differences between biological sequence alignment and natural language coordination detection, they introduce a more fine-grained state space with "nodes" and "arcs" that allow for higher-order feature interactions.

Two specific learning methods are proposed:

  • Path-based method: This method directly learns weights for features associated with paths in the edit graph. It's an extension of Collins's averaged-perceptron algorithm for sequence labeling.
  • Box-based method: This method addresses the challenge of less strictly annotated data by distributing feature weights within a rectangular "box" representing a potential alignment region. This allows the model to learn from examples where only conjunct boundaries are known.

Datasets

The primary dataset used for training and evaluation is the GENIA Treebank beta corpus. This corpus, derived from Medline abstracts, is chosen because it provides more detailed bracketing for coordinations compared to other standard corpora like the Penn Treebank, making it suitable for this task. They specifically focus on coordinated noun phrases (NP-COOD) within this corpus.

Key Insights and Ideas

  • Reduced Annotation Cost: The ability to train on boundary-only annotations is a major breakthrough, making the approach much more practical for real-world applications.
  • Flexible Feature Integration: The discriminative learning framework allows for the easy incorporation of a large number of overlapping features, enabling the model to capture complex interactions and heuristics for disambiguation.
  • Bridging Biological and Linguistic Alignment: The paper effectively adapts techniques from biological sequence alignment to the linguistic problem of coordination, highlighting the universality of certain computational approaches.
  • Handling Ambiguity: The model is designed to handle the inherent ambiguity in coordination, moving beyond simple rule-based systems.

Key Results

The proposed methods, particularly the path-based method, achieved state-of-the-art performance on the GENIA corpus for both conjunct bracketing and coordination detection.

  • The path-based method (without word and suffix features) showed 2.0 and 1.3 point improvements over linear-chain CRF chunkers in conjunct identification (chunk-based evaluation).
  • It also achieved 3.8 and 3.0 point improvements in pairwise evaluation for conjuncts.
  • For coordination identification, the path-based method showed a 0.5 point improvement over a baseline.
  • The proposed methods consistently outperformed baseline parsers like Bikel and Charniak-Johnson.

Limitations and Future Work

  • Nested Coordinations: The current model cannot handle nested coordinations (e.g., "A, B, and (C and D)"). This is identified as a limitation.
  • External Similarity Measures: While the framework is well-suited to incorporate external similarity measures (like thesauri or corpus statistics), these were not used in the reported experiments. The authors suggest this as a promising avenue for future work.
  • Algorithm Choice: The authors plan to reimplement their algorithms using Conditional Random Fields (CRFs) instead of the averaged perceptron algorithm, which might offer further improvements.

Summary updated

BibTeX
@inproceedings{shimbo2007discriminative,
  author = {Masashi Shimbo and Kazuo Hara},
  title = {{A Discriminative Learning Model for Coordinate Conjunctions}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure