📄 Loosely Tree-Based Alignment for Machine Translation

Summary

Syntax-based translation models, such as the reordering model of Yamada and Knight (2001), can only produce alignments that respect the bracketing of a parse tree. Real parallel text often breaks this assumption, because languages differ structurally and because translations can be loose. Gildea proposes a "loosely" tree-based approach. A new clone operation copies a whole source subtree and attaches it anywhere in the target structure. This makes non-isomorphic alignments possible, but at a probability penalty. The operation is added to two models: a tree-to-string model and a new tree-to-tree model, which works like a synchronous tree substitution grammar over parallel parse trees. The clone probabilities are kept deliberately simple, so EM training stays polynomial and the asymptotic cost does not grow. The models are tested on a syntactically annotated Korean-English corpus by measuring alignment error rate (AER) against human word alignments. Cloning improves both tree-based models and brings them level with the IBM models. The tree-to-tree variant is also much faster, which matters for training syntax-based systems on longer sentences and larger corpora.

Key points

• The baseline tree-to-string model of Yamada and Knight (2001) has three kinds of operations:

  • it reorders the children of each node;
  • it inserts target words at nodes;
  • it translates the leaves.

• Training this baseline costs O(n⁴) in sentence length, while the tree-to-tree model is quadratic.

• Cloning design:

  • Whether a clone is inserted is governed by one EM-estimated probability, P_ins(clone).
  • Which node gets copied is chosen uniformly from the source tree.
  • There is no limit on how often a single node may be copied.
  • Treating each copy as independent in this way is what lets the dynamic program remain tractable.

• AER on Korean-English (lower is better):

  Model	AER
  IBM Model 1	.37
  IBM Model 2	.35
  IBM Model 3	.43
  Tree-to-String	.42
  Tree-to-String, Clone	.36
  Tree-to-String, Clone, fixed P_ins = .5	.32
  Tree-to-Tree	.49
  Tree-to-Tree, Clone	.36

• The tree-to-tree model lets two source nodes be grouped into one elementary tree, and it allows insertions and deletions of children during alignment.

• On sentences of up to 60 words, tree-to-tree alignment ran about 20 times faster than tree-to-string. The author presents these as the first published results for tree-to-tree statistical alignment.

Interesting ideas

• I1. Soften hard structural constraints with a priced escape operation. Instead of forbidding alignments that violate the tree, the model allows them at a cost. This keeps the syntactic bias but tolerates noisy or divergent data. The same trick could help any structured model with an overly strict grammar.
• I2. Pick independence assumptions to protect tractability. Making the clone choice uniform and independent of earlier copies keeps inference within the existing chart algorithm. Without it, the problem becomes parsing with crossing dependencies, which is exponential. This is a useful design rule when extending dynamic-programming models.
• I3. Tune a few meta-parameters against the real metric. Fixing the insertion probability by hand, instead of learning it with EM, reduced over-alignment and gave the best AER. EM's likelihood objective can differ from what human annotation rewards, which is worth checking in any unsupervised setup.
• I4. Structure on both sides can buy speed even without accuracy gains. Parsing both languages narrows the search space enough to make training far faster. That makes the approach attractive for scaling to longer sentences or bigger corpora.
• I5. Stop training by the target metric. Results were reported at the iteration with minimum AER, and training was stopped once error began to rise. This is a simple guard for EM-trained models evaluated against gold annotations.