ABL: Alignment-Based Learning

Menno van ZaanenCOLING 2000

TL;DR

This paper introduces ABL, a novel unsupervised grammar learning algorithm that induces syntactic structure from plain text by aligning sentences based on string edit distance. By identifying interchangeable parts of sentences, ABL learns constituents and their types, offering a promising approach to unsupervised parsing without requiring pre-annotated data.

What Problem Does This Paper Address?

Unsupervised learning of syntactic structure is a notoriously difficult problem in Natural Language Processing (NLP). While humans effortlessly acquire grammatical understanding, modeling this process for computers remains a significant challenge. Traditional supervised methods, which rely on meticulously hand-annotated data, achieve high performance but are prohibitively expensive and time-consuming to create. This paper tackles the gap by proposing an unsupervised method that can learn grammatical structure directly from raw, unbracketed sentences, aiming to discover the underlying syntactic organization without prior linguistic knowledge.

Methods

The ABL algorithm operates in two main phases:

  1. Alignment Learning: This phase takes a corpus of plain sentences and compares them in pairs. It uses a string edit distance algorithm (specifically, a variation of Wagner and Fischer's algorithm) to find identical words and phrases between sentences. By identifying these commonalities and the differing, yet interchangeable, segments, the algorithm proposes potential constituents. The core idea is that if a group of words in one sentence can be replaced by a group of words in another sentence, and the result is still a valid sentence, then these groups likely represent constituents of the same type. This phase also handles the merging of constituent types when new sentences reveal existing structures.
  2. Selection Learning: After the alignment phase generates a set of possible constituents, this phase selects the most probable ones. The paper explores three methods:
  3. ABL:incr: A simple approach that keeps the first learned constituent and ignores any overlapping new ones.
  4. ABL:leaf: A probabilistic method that calculates the probability of a constituent based on the frequency of its constituent words appearing together in the learned corpus.
  5. ABL:branch: A more sophisticated probabilistic method that considers not only the constituent words but also their context (the surrounding sentence structure and the constituent's non-terminal type). This method uses a Viterbi-style algorithm to efficiently select the best combination of constituents, especially when dealing with overlapping structures.

Datasets

The ABL algorithm was tested on two corpora:

  • ATIS (Air Travel Information System): A corpus of 716 sentences with 11,777 pre-existing constituents.
  • OVIS (Openbaar Vervoer Informatie Systeem): A larger Dutch corpus containing 10,000 sentences, from which sentences with only one word were removed, resulting in 6,797 sentences and 48,562 constituents.

Key Insights and Ideas

  • Leveraging String Edit Distance for Structure: The core innovation is using string edit distance not just for sequence comparison, but as a foundation for discovering syntactic relationships by identifying interchangeable sentence segments.
  • Constituent Interchangeability as a Learning Signal: The paper operationalizes Harris's linguistic idea that constituents of the same type can be substituted for each other, turning it into a computational mechanism for learning.
  • Two-Phase Learning (Alignment + Selection): The separation of generating potential constituents (alignment) and then refining them (selection) provides a structured approach to unsupervised grammar induction.
  • Probabilistic Selection for Robustness: The probabilistic methods (ABL:leaf and ABL:branch) are crucial for handling ambiguity and selecting the most likely structures, leading to more stable results than the purely incremental approach.
  • Handling Recursion: The algorithm demonstrates the ability to learn recursive structures, a key feature of natural language grammar.

Key Results

The ABL algorithm, particularly the ABL:branch method, achieved promising results on both corpora.

  • On the ATIS corpus, ABL:branch achieved 85.31% precision (NCBP) and 89.31% recall (NCBR).
  • On the OVIS corpus, ABL:branch achieved 89.25% precision (NCBP) and 85.04% recall (NCBR).
  • The ZCS (Zero-Crossing Sentences) metric, indicating the percentage of sentences without any overlapping constituents, reached up to 29.75% for ABL:branch on ATIS and 42.20% on OVIS.
  • ABL significantly outperformed a previous unsupervised method (Pereira and Schabes, 1992) on the ATIS corpus, achieving 85.31% precision compared to 37.35%.
  • The probabilistic methods showed significantly lower standard deviations compared to the ABL:incr method, indicating more stable and reliable results.

Limitations and Future Work

  • Ambiguous Alignments: The paper acknowledges that edit distance can sometimes produce unintended constituents due to linking words that are too far apart. Biasing the cost function with distances between words is suggested as a solution.
  • Wrong Syntactic Type: The assumption that a constituent in a certain context can only have one type can lead to errors, such as assigning the same type to a noun ("morning") and an adverb ("nonstop"). Future work aims to incorporate context to differentiate these types.
  • Weakening Exact Match: For completely distinct sentences, learning is difficult. The paper suggests weakening the exact match by using equivalence classes of words to allow learning even when sentences don't share identical words.
  • Alternative Statistics: The authors mention exploring other statistical models, such as those based on Tree-Adjoining Grammars (TAG) or Dependency Grammar, and incorporating the inner structure of constituents (like in DOP models).
  • Larger Domain Corpora: The current experiments were on small conceptual domains. Applying ABL to larger, more diverse corpora is a planned future step.

Summary updated

BibTeX
@inproceedings{zaanen2000abl,
  author = {Menno van Zaanen},
  title = {{ABL: Alignment-Based Learning}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2000},
}
Figure