Graham Neubig¹,²,³, Taro Watanabe², Shinsuke Mori¹
•  Long-distance reordering is a weak point of SMT •  Preordering first reorders, then translates • A good preorderer will effectively find F' given F
2

•  Define rules over a syntactic parse of the source •  What if we don't have a parser in the source language? 3 Bracketing Transduction Grammars [Wu 97] •  Binary CFGs with only straight (S) and inverted (I) non-terminals, and pre-terminals (T) • Language independent •  BTG tree uniquely defines a reordering
Testing
•  What if we can reduce three steps to one, and directly maximize ordering accuracy? Training Optimization Framework
•  Input: Source sentence F F= kare wa gohan o tabeta •  Output: Reordered source sentence F' F'= kare wa tabeta gohan o •  Latent: Bracketing transduction grammar derivation D D=

10

•  Out of these, we want easy-to-reproduce trees •  [DeNero+ 11] finds trees with bilingual parsing model •  Our model discovers trees during training 11
• Find •  model parse of maximal score and oracle parse of maximal score among parses of minimal loss • Adjust weights (example: perceptron) − w+φ(F,D)−φ(F,D) W ← Considering Loss in Online Learning •  Consider loss (how bad is the mistake?)
•  Make it easy to choose trees with high loss in training → To avoid high-loss trees, must give a large penalty D=argmax S(F, Ã)+L(F, Ã) Inducing a Discriminative Parser to Optimize Machine Translation Reordering Parser
•  Features independent with respect to each node •  Parsing, reordering possible in O(n³) with CKY •  Multi-word pre-terminals allowed
15
Language Independent Features •  No linguistic analysis necessary •  Lexical: Left, right, inside, outside, boundary words •  Class: Same as lexical but induced classes •  Phrase Table: Whether span exists in phrase table •  Balance: Left branching or right branching?
•  POS Features: Same as lexical, but over POSs •  CFG Features: Whether nodes match supervised parser's spans Reordering Losses Reordering Losses [Talbot+ 11]: Chunk Fragmentation •  How many chunks are necessary to reproduce reference? Loss: (F , Ď )=   Number of Chunks - 1 Accuracy: F , Ď )=  1 - (Number of Chunks - 1)/(J+1) Inducing a Discriminative Parser to Optimize Machine Translation Reordering Reordering Losses [Talbot+ 11]: Kendall's Tau •  How many pairs of reversed words?
kare
tabeta gohan 0 Loss: Ltau (F , Ď )=   Reversed Words Accuracy: Atau (F, Ď)=  1 - Reversed Word/Potential Reversed Words
•  Large-margin training, must calculate loss efficiently D=argmax S(F, Ã)+L(F, Ã) •  Can factor loss by node as well (detail in paper) Inducing a Discriminative Parser to Optimize Machine Translation Reordering Experiments
•  English-Japanese and Japanese-English translation •  Data from the Kyoto Free Translation Task
Manually Aligned
•  Reordering Model Training: • 500 iterations •  Using Pegasos with regularization constant 10 -3 •  Default: chunk fragmentation loss, standard features •  Translation: Moses with lexicalized reordering •  Compare: Original order, 3-step training, the proposed method
24
Result: Proposed Model Improves Reordering •  Results for chunk fragmentation/Kendall's Tau Result:
•  Results for BLEU and RIBES:
26

Result:
•  Optimized criterion is higher on test set as well Result:
•  Optimizing chunk fragmentation generally gives best results
29

32
Conclusion
•  Presented a method to induce a discriminative parser to optimize machine translation reordering •  Favorable results for English ↔ Japanese • Future Work: •  Development of better features •   Incorporation into tree-to-string translation •  Probabilistic inference
Will be!
^ Available Open Source: http://www.phontron.com/lader Inducing a Discriminative Parser to Optimize Machine Translation Reordering Thank you!