Deriving Transfer Rules from Dominance-Preserving Alignments

Adam Meyers, Roman Yangarber, Ralph Grishman, Catherine Macleod, Antonio Moreno-SandovalACL 1998

TL;DR

This paper introduces a novel algorithm for aligning parse trees of parallel sentences, specifically focusing on preserving dominance relationships rather than strict least common ancestor constraints. This allows for more flexible and accurate alignment, leading to the derivation of more robust transfer rules for machine translation.

What Problem Does This Paper Address?

Building effective machine translation (MT) systems often relies on acquiring translation rules from parallel corpora. A common approach involves parsing sentences and then aligning these parsed structures. However, previous methods that enforced a "least common ancestor" (LCA) constraint on alignments were too restrictive, limiting the quality of the derived rules. This paper addresses the challenge of creating more flexible and accurate alignments between source and target language parse trees, which is crucial for learning better transfer rules for MT. The core issue is finding a way to match substructures within these parse trees that accurately reflects translation, even when the hierarchical relationships don't perfectly mirror each other.

Methods

The paper proposes a dominance-preserving alignment algorithm that replaces the stricter LCA constraint. This algorithm uses dynamic programming to compute scores for matching nodes in the source and target trees. The key innovation lies in how it handles the alignment of children nodes. Instead of requiring that the LCA of aligned children in the source tree maps to the LCA of their aligned counterparts in the target tree, it only requires that if node a dominates node b in the source, then f(a) dominates f(b) in the target.

The algorithm works by:

  1. Constructing a child-scoring matrix: For each pair of parent nodes (v, v'), a matrix M is created to score potential pairings of their children. This matrix includes scores for direct child-to-child matches and penalties for collapsing edges (i.e., not directly aligning a child).
  2. Finding legitimate pairings: A "legitimate pairing" is a set of child-to-child matches that respects the one-to-one mapping constraint (each child can be matched at most once). The algorithm efficiently finds the best legitimate pairing of children.
  3. Recursive score computation: The score for aligning parent nodes S(v, v') is computed based on the best child pairing score, plus a lexical score for the parent nodes themselves. This process is applied recursively to build up the alignment for the entire trees.
  4. Deriving transfer rules: Once the optimal dominance-preserving alignment is found, the paper describes how to "chop up" the aligned trees into substructures. These substructures, representing connected groups of nodes and their relationships, form the transfer rules.

Datasets

The paper describes using a training corpus of about 1,000 sentences and a test corpus of about 100 sentences for translating Microsoft Help files from English to Spanish. The authors note that these sentences are "moderately simple and quite parallel in structure," making the corpus suitable for their initial system development. No new datasets or benchmarks are introduced.

Key Insights and Ideas

  • Dominance-Preserving is More Flexible: Relaxing the LCA constraint to a dominance-preserving one significantly improves alignment flexibility. This allows for more accurate matching of substructures, especially when sentence structures differ more substantially between languages.
  • Scoring Child Pairings is Crucial: The core of the algorithm's success lies in its ability to efficiently score and select the best pairings of children nodes, even when direct parent-child alignments aren't perfect.
  • Transfer Rules from Substructures: The method of deriving transfer rules by "chopping up" aligned parse tree substructures provides a structured way to capture translation patterns beyond simple word-for-word replacements.
  • Lexical and Arc Scores Matter: The scoring mechanism effectively balances the quality of lexical translations (word-to-word) with the cost of structural transformations (arc penalties).

Key Results

The paper reports an evaluation of their dominance-preserving alignment algorithm against an LCA-preserving version.

  • The dominance-preserving version produced output for 88 out of 91 test sentences with an average score of 0.29.
  • The LCA-preserving version produced output for only 83 sentences with an average score of over 0.30. The average score is calculated as a ratio reflecting translation quality (lower is better). The dominance-preserving approach led to more translated sentences and a slightly better average score, suggesting improved translation quality.

Limitations and Future Work

  • Paraphrases are Penalized: The evaluation metric used penalizes paraphrases, meaning an otherwise good translation might receive an imperfect score.
  • Greedy Alignment for Efficiency: While the dynamic programming approach is described, the paper mentions using a greedy approach for finding the best child pairings to reduce computation time, which might not always yield the absolute optimal pairing.
  • Empirical Parameter Tuning: The performance of the algorithm relies on empirically chosen parameters for lexical translation quality, arc label translation, and penalties.
  • Future Work: The paper implicitly suggests further refinement of the scoring and alignment mechanisms, as well as exploring the application of these transfer rules in a full MT system. The evaluation also hints at the need for more nuanced evaluation metrics that can better handle paraphrases.

Summary updated

BibTeX
@inproceedings{meyers1998deriving,
  author = {Adam Meyers and Roman Yangarber and Ralph Grishman and Catherine Macleod and Antonio Moreno-Sandoval},
  title = {{Deriving Transfer Rules from Dominance-Preserving Alignments}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1998},
}
Figure