Weblio Pre-reordering SMT System
Zhongyuan Zhu(People call me Raphael Shu)@raphaelshu

1Overview of pre-reordering systems• Reorder input text before translationfJohn hits a ballPre-reordering

Decoderf’John va̲nsubj a ball va̲obj hitse
ジョンはボールを打った
2

Approaches of pre-reordering• Syntactic pre-reordering with parse trees-

Rule-based--Head-finalization (Isozaki et al., 2010)

Supervised learning with word alignments-

Automatically learning Rewrite Patterns (Xia andMcCord, 2004)• Syntactic pre-reordering without parse tree
-LADER (Neubig et al., 2012)3

Pre-reordering model in our system

4Overview of our pre-reordering system
InputfDependency Parse Tree
Pre-reordering ResultDEPf’
CFG
CFG Parse Tree

Tree RestructuringReordering

HRCFG

Head-restructured CFG Parse Tree

5

Head-restructured CFG Parse Tree
• Problem of CFG parse tree
-Hard to capture long-distance reordering
patterns• Problem of Dependency parse tree-

Fully lexicalized parse tree leads to asparse reordering model6

Head-restructured CFG Parse Tree
• Our approach-Restructure a CFG parse tree to inject headinformation into it
Head word is always lexicalized+hits	nsubj

dobj

Johnballdet=a

CFG Parse Tree

Dependency Parse Tree

Head-restructured CFG Parse Tree(HRCFG)
7

Learning reordering model based on LM• Extract tag sequences in golden order

Head-restructured CFG parse tree
SGolden order
nsubj

aux

auxp
ass

NP

canbeprep_bycalculateddetails

nsubj prep_by calculated auxpass aux

PPbyAlignments

NPDERS

NP byLM• Train a language model onreordered tag sequences

詳細は DERS で 計算
Target-side Sentenceできる8Finding golden order with word alignments• Given a bilingual sentence pair, source-side parse tree andword alignments,
the golden order of a node layer is defined asTerminalsn2n1

Non-terminals

11t

t12

For nodes (n1 ,n2 ,...,nk )n3t13

Initial order:t 23

Alignments

w

w13{

11{

Average position (Ranked)

Golden order:{

Target-side words

o0 = (1,2,..., k)

w23

w12

a1 = 1a3 = 2a2 = 3ô = (a1 ,a2 ,...,ak )9

Reordering a input parse tree
1.List all possible orders for a treelet

3. Select the best order to adjust the treelet

nsubj dobj hits

-5.2

dobj nsubj hits

-6.1

hits nsubj dobj -12.3
hits dobj nsubj -19.5
dobj hits nsubj -20.5
nsubj hits dobj -22.7

nsubj dobj hits

2.Score them with language model

10

-5.2

-6.1

-12.3

-19.5

-20.5

-22.7

N-best reordering

-3.6

-7.9

Reordered treelets with LM scores
All 12 possible combinations here
Selected N-best results by accumulated scores (Cube Pruning is applied in the practice)

-8.8

-9.7

-13.1

-14.0

-15.9

-20.2

-23.1

-24.1

-26.3

-27.4

-28.4

-30.6
11

Experiments

12In-house experiments
BLEU

RIBES

1-best parse + 1 best reorder

34.46

0.7817

N-best parse + 1 best reorder

34.80

0.7851

1-best parse + N-best reorder

34.90

0.7857

N-best parse + N- best reorder

35.10

0.7887• For “N-best reorder”, 10 candidate reordering results are considered.
• For “N-best parse”, 30 candidate parse trees are considered.
• We select the final translation by the sum of translation score (given by decoder)and the score of pre-reordering.

13

N-best reordering & N-best parse tree inputs• Incorporating multiple reordering results andparse trees benefits automatic scores.

BLEU

RIBES
14

Official evaluation results
BLEU

RIBES

HUMAN

N-best reorder

34.87

0.7869+43.25N-best reorder + N-best parse

35.04

0.7900+36.00BASELINE PBMT

29.80

0.69190.00

15

Official evaluation results

16Effect of pre-ordering• Identical ordered sentences increases to 15%

Closer in order17

Example of pre-reordering
Original input
the improvement of the life is a large problem of the practical application.
Restructured parse tree

Reordered input
the life of the improvement va_nsubjpass the practical application of a large problem is .

Reference

寿命 の 向上 が 実用 化 の 大きな 課題 で あ る 。
18

Review• Language model is just a quick solution to

the reordering problem, sometimes it fails insimple cases.
-Sparseness problem• To gain more from forest input, it’s necessary

to integrate it inside the pre-reorderingmodel.

19

Online demonstrations
Head-restructured CFG parse tree
http://raphael.uaca.com/demos/hdtree

Pre-reordering
http://raphael.uaca.com/demos/raphreorder20

Thanks.

21