Building a Phrase-Based SMT System

Building a Phrase-based SMT System

Graham Neubig & Kevin DuhNara Institute of Science and Technology (NAIST)
5/10/20121

Building a Phrase-Based SMT System

Phrase-based
Statistical Machine Translation (SMT)●Divide sentence into patterns, reorder, combine

Today I will give a lecture on machine translation .
Today
I will give
今日は、 を行います

Today
今日は、

a lecture onの講義

machine translation
機械翻訳

machine translation
機械翻訳

a lecture onの講義

I will giveを行います.
。

.
。

今日は、機械翻訳の講義を行います。
●

Statistical translation models, reordering models,language models learned from text2

Building a Phrase-Based SMT System

This Talk
1) What are the steps required to build a phrase-based
machine translation translation system?
2) What tools implement these steps in Moses* (anopen-source statistical MT system)?
3) What are some research problems related to each ofthese components?

* http://www.statmt.org/moses

3Building a Phrase-Based SMT System

Steps in Training a
Phrase-based SMT System●

Collecting Data●

Tokenization●

Language Modeling●

Alignment●

Phrase Extraction/Scoring●

Reordering Models●

Decoding●

Evaluation●

TuningBuilding a Phrase-Based SMT System

Collecting Data

Building a Phrase-Based SMT System

Collecting Data
●Sentence parallel data●

Used in: Translation model/Reordering model
これはペンです。
This is a pen.
昨日は友達と食べた。 I ate with my friend yesterday.
象は花が長い。
Elephants' trunks are long.

●Monolingual data (in the target language)●

Used in: Language modelThis is a pen.
I ate with my friend yesterday.
Elephants' trunks are long.

Building a Phrase-Based SMT System●Big! →Translation Accuracy

Good Data isLM Data Size (Million Words) [Brants 2007]●Clean●In the same domain as test data

Building a Phrase-Based SMT System

Collecting Data
●For academic workshops, data is prepared for us!

e.g.
IWSLT 2011 →●NameTypeWords

TEDLectures

1.76M

News CommentaryNews

2.52M

EuroParl

Political

45.7M

UN

Political

301M

GigaWeb

576M

In real systems
Data from government organizations, newspapers● Crawl the web● Merge several data sources●

Building a Phrase-Based SMT SystemResearch●Finding bilingual pages [Resnik 03][Image: Mainichi Shimbun]

Building a Phrase-Based SMT SystemResearch●Finding bilingual pages [Resnik 03]●

Sentence alignment [Moore 02]

Building a Phrase-Based SMT System

Research●

Finding bilingual pages [Resnik 03]●

Sentence alignment [Moore 02]●

Crowd-sourcing data creation [Ambati 10]●

Mechanical Turk, duolingo, etc.

Building a Phrase-Based SMT SystemTokenization

Building a Phrase-Based SMT System

Tokenization●

Example: Divide Japanese into words

太郎が花子を訪問した。
太郎 が 花子 を 訪問 した 。
●

Example: Make English lowercase, split punctuation
Taro visited Hanako.
taro visited hanako .

Building a Phrase-Based SMT System

Tools for Tokenization●Most European languages
tokenize.perl en < input.en > output.en
tokenize.perl fr < input.fr > output.fr●JapaneseMeCab: mecab ­O wakati < input.ja > output.ja
KyTea: kytea ­notags < input.ja > output.ja

JUMAN, etc.
●Chinese
Stanford Segmenter, LDC, KyTea, etc...

Building a Phrase-Based SMT System

Research●

What is good tokenization for machine translation?
Accuracy? Consistency? [Chang 08]● Matching target language words? [Sudoh 11]●太郎 が 花子 を 訪問 した 。
Taro <ARG1> visited <ARG2> Hanako .
●Morphology (Korean, Arabic, Russian) [Niessen 01]단 어 란도 대 체무 엇 일 까 요?

단 어란도 대 체무 엇일까 요?
● Unsupervised learning [Chung 09, Neubig 12]

Building a Phrase-Based SMT System

Language ModelingBuilding a Phrase-Based SMT System

Language Modeling●Assign a probability to each sentence

E1: Taro visited Hanako

P(E1)

E2: the Taro visited the HanakoLM

E3: Taro visited the bibliography●More fluent sentences get higher probability
P(E1) > P(E2)P(E1) > P(E3)

P(E2)
P(E3)

Building a Phrase-Based SMT Systemn-gram Models●

We want the probability ofP(W = “Taro visited Hanako”)●n-gram model calculates one word at a time
●Condition on n-1 previous words
e.g. 2-gram model
P(w1=“Taro”) * P(w2=”visited” | w1=“Taro”)* P(w3=”Hanako” | w2=”visited”)* P(w4=”
” | w3=”Hanako”)
NOTE:
sentence ending symbol 
18

Building a Phrase-Based SMT SystemTools●SRILM Toolkit:
Train:
ngram­count ­order 5 ­interpolate ­kndiscount ­unk
­text input.txt ­lm lm.arpa

Test:ngram ­lm lm.arpa ­ppl test.txt●Others: KenLM, RandLM, IRSTLM

Building a Phrase-Based SMT System

Research Problems●Is there anything that can beat n-grams?
[Goodman 01]
Fast to compute● Easy to integrate into decoding● Surprisingly strong●●

Other methods
Syntactic LMs [Charniak 03]● Neural networks [Bengio 06]● Model M [Chen 09]● etc...
●

Building a Phrase-Based SMT System

Alignment

Building a Phrase-Based SMT System

Alignment●Find which words correspond to each-other

太郎 が 花子 を 訪問 した 。

太郎 が 花子 を 訪問 した 。

taro visited hanako .

taro visited hanako .

●Done automatically with probabilistic methods
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
EnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishP( 花子 |hanako) = 0.99
P( 太郎 |taro) = 0.97
P(visited| 訪問 ) = 0.46
P(visited| した ) = 0.04
P( 花子 |taro) = 0.0001

22

Building a Phrase-Based SMT System

IBM/HMM Models●One-to-many alignment model

ホテル の 受付X
the hotel front desk

the hotel front deskX
ホテル の 受付

IBM Model 1: No structure (“bag of words”)● IBM Models 2-5, HMM: Add more structure●23Building a Phrase-Based SMT System

Combining One-to-Many Alignments
ホテル の 受付X
the hotel front desk

the hotel front deskX
ホテル の 受付

Combinethe hotel front desk
ホテル の 受付●

Several different heuristics

24Building a Phrase-Based SMT SystemTools●mkcls: Find bilingual classes
ホテル の 受付35

the hotel front desk
●

2335

49

12

12

19

GIZA++: Find alignments using IBM models (usesclasses from mkcls for smoothing)
ホテル の 受付
the hotel front desk

+35 49 12

ホテル の 受付23 35 12 19

the hotel front desk●

symal: Combine alignments in both directions●(Included in train-model.perl of Moses)

Building a Phrase-Based SMT System

Research Problems●

Does alignment actually matter? [Aryan 06]●

Supervised alignment models [Fraser 06, Haghighi 09]●

Alignment using syntactic structure [DeNero 07]●

Phrase-based alignment models [Marcu 02, DeNero08]

Building a Phrase-Based SMT System

Phrase Extraction

Building a Phrase-Based SMT System

Phrase Extraction●

Use alignments to find phrase pairs

ホテ 受ルの付
thehotelfrontdesk

ホテル の → hotel
ホテル の → the hotel
受付 → front desk
ホテルの受付 → hotel front desk
ホテルの受付 → the hotel front desk

Building a Phrase-Based SMT System

Phrase Scoring●Calculate 5 standard features●Phrase Translation Probabilities:
P(f|e) = c(f,e)/c(e)P(e|f) = c(f,e)/c(f)e.g. c( ホテル の , the hotel) / c(the hotel)● Lexical Translation Probabilities
Use word-based translation probabilities (IBM Model 1)– Helps with sparsity–P(f|e) = Πf 1/|e| ∑e P(f|e)
e.g.
(P( ホテル |the)+P( ホテル |hotel))/2 * (P( の |the)+P( の |hotel))/2●

Phrase penalty: 1 for each phrase

Building a Phrase-Based SMT SystemTools●

extract: Extract all the phrases●phrase-extract/score: Score the phrases●(Included in train-model.perl)Building a Phrase-Based SMT System

Research
●

●

●

●

Domain adaptation of translation models [Koehn 07,
Matsoukas 09]
Reducing phrase table size [Johnson 07]
Generalized phrase extraction (Geppetto toolkit) [Ling10]
Phrase sense disambiguation [Carpuat 07]

Building a Phrase-Based SMT System

Reordering Models

Building a Phrase-Based SMT System

Lexicalized Reordering●Probability of monotone, swap, discontinuous
細太 訪しい男が郎を問た

thethinman
visitedTaromono

細い → the thinhigh monotone probability●disc.

swap

太郎 を → Tarohigh swap probability

Conditioning on input/output, left/right, or both

Building a Phrase-Based SMT SystemTools●

extract: Same as phrase extraction●

lexical-reordering/score: Scores lexical reordering●(included in train-model.perl)Building a Phrase-Based SMT SystemResearch●Still a very open research area (especially en↔ja)●

Change the translation modelHierarchical phrase-based [Chiang 07]● Syntax-based translation [Yamada 01, Galley 06]●●Pre-ordering [Xia 04, Isozaki 10]

F

彼は パンを 食べた

F'彼は 食べたをE

heateパンriceBuilding a Phrase-Based SMT SystemDecoding

Building a Phrase-Based SMT SystemDecoding●

Given the models, find the best answer (or n-best)model

太郎が花子を訪問した●●DecoderTaro visited Hanako
the Taro visited the Hanako
Taro met Hanako
Hanako visited Taro

4.5
3.2
2.4-2.9

Exact search is NP-hard! [Knight 99]
Decoding uses beam-search to find an approximate
solution [Koehn 03]

Building a Phrase-Based SMT SystemTools●Moses!
moses ­f moses.ini < input.txt > output.txt●Also: moses_chart, cdec (for Hiero, syntax-basedmodels)Building a Phrase-Based SMT SystemResearch●

Decoding for lattice input [Dyer 08]●

Decoding for syntax models [Mi 08]●

Minimum Bayes risk decoding [Kumar 04]●

Exact decoding [Germann 01]

Building a Phrase-Based SMT System

Evaluation

Building a Phrase-Based SMT System

Human Evaluation●Adequacy: Is the meaning correct?

●Fluency: Is the sentence natural?

●

Pairwise: Is X a better translation than Y?
太郎が花子を訪問した

Taro visited Hanako the Taro visited the Hanako Hanako visited TaroAdequate? ○Fluent?
○Better?
B, C○
☓C☓
○

Building a Phrase-Based SMT System

Automatic Evaluation●

How well does the translation match a reference?
●●(or multiple references: more than one correct translation)

BLEU: n-gram precision, brevity penalty [Papineni 03]
Reference: Taro visited Hanako
System: the Taro visited the Hanako

Brevity: min(1, |System|/|Reference|) = min(1, 5/3)

1-gram: 3/5
2-gram: 1/4
brevity penalty = 1.0
BLEU-2 = (3/5*1/4)1/2 * 1.0= 0.387●

Also METEOR (normalizes synonyms), TER (# ofchanges), RIBES (reordering)Building a Phrase-Based SMT System

Research●

Metrics with focus on a particular thing
Reordering [Isozaki 10]● Accuracy of meaning [Lo 11]●●

Tunable metrics [Cer 10]●

Metric aggregation [Albrecht 07]●

Crowdsourcing human evaluation [Callison-Burch 11]

Building a Phrase-Based SMT SystemTuning

Building a Phrase-Based SMT SystemTuning●Scores of translation, reordering, and language models○ Taro visited Hanako☓ the Taro visited the Hanako☓ Hanako visited Taro●

TM-3-4-3

RM-1-1-2-8-10-7 BestScore ☓If we add weights, we can get better answers:○ Taro visited Hanako☓ the Taro visited the Hanako☓ Hanako visited Taro●

LM-4-5-2LM
TMRM
0.2*-4 0.3*-3 0.5*-1
0.2*-5 0.3*-4 0.5*-1
0.2*-2 0.3*-3 0.5*-2-2.2-2.7-2.3

Best
Score ○

Tuning finds these weights: wLM=0.2 wTM=0.3 wRM=0.5

Building a Phrase-Based SMT System

Tuning Methods●

Minimum error rate training: MERT [Och 03]
n-best (dev)source (dev)
太郎が花子を訪問した

ModelDecodeWeights

the Taro visited the Hanako
Hanako visited Taro
Taro visited Hanako...

reference (dev)
Taro visited Hanako
Find betterweights●Others: MIRA [Watanabe 07] (online update), PRO(ranking) [Hopkins 11]

Building a Phrase-Based SMT System

Research●

Tuning with millions of features (e.g. MIRA, PRO)●

Tuning with lattices [Macherey 08]●

Speeding up tuning [Suzuki 11]●

Tuning with multiple metrics [Duh 12]

Building a Phrase-Based SMT System

Last Words

Building a Phrase-Based SMT System

Last Words●MT is fun! Join us.

●Improving very quickly, but still many problems.

●

System is big, but you can focus on one problem.
ありがとうございますDankeThank YouMT謝謝Gracias감 사 합 니 다
Terima Kasih

Building a Phrase-Based SMT System

Bibliography

Building a Phrase-Based SMT System
●

●

●

●

●

●

●

●

●

●

●
●
●
●

●

●

●

J. Albrecht and R. Hwa. A re-examination of machine learning approaches for sentence-level mt evaluation.
In Proc. ACL, pages 880-887, 2007.
V. Ambati, S. Vogel, and J. Carbonell. Active learning and crowdsourcing for machine translation. Proc.
LREC, 7:2169-2174, 2010.
N. Ayan and B. Dorr. Going beyond AER: an extensive analysis of word alignments and their impact on MT.
In Proc. ACL, 2006.
Y. Bengio, H. Schwenk, J.-S. Sencal, F. Morin, and J.-L. Gauvain. Neural probabilistic language models. InInnovations in Machine Learning, volume 194, pages 137-186. 2006.
T. Brants, A. C. Popat, P. Xu, F. J. Och, and J. Dean. Large language models in machine translation. In Proc.
EMNLP, pages 858-867, 2007.
C. Callison-Burch, P. Koehn, C. Monz, and O. Zaidan. Findings of the 2011 workshop on statistical machinetranslation. In Proc. WMT, pages 22-64, 2011.
M. Carpuat and D. Wu. How phrase sense disambiguation outperforms word sense disambiguation for
statistical machine translation. In Proc. TMI, pages 43-52, 2007.
D. Cer, C. Manning, and D. Jurafsky. The best lexical metric for phrasebased statistical MT system
optimization. In NAACL HLT, 2010.
P.-C. Chang, M. Galley, and C. D. Manning. Optimizing Chinese word segmentation for machine translation
performance. In Proc. WMT, 2008.
E. Charniak, K. Knight, and K. Yamada. Syntax-based language models for statistical machine translation. In
MT Summit IX, pages 40-46, 2003.
S. Chen. Shrinking exponential language models. In Proc. NAACL, pages 468-476, 2009.
D. Chiang. Hierarchical phrase-based translation. Computational Linguistics, 33(2), 2007.
T. Chung and D. Gildea. Unsupervised tokenization for machine translation. In Proc. EMNLP, 2009.
J. DeNero, A. Bouchard-C^ote, and D. Klein. Sampling alignment structure under a Bayesian translation
model. In Proc. EMNLP, 2008.
J. DeNero and D. Klein. Tailoring word alignments to syntactic machine translation. In Proc. ACL, volume 45,
2007.
K. Duh, K. Sudoh, X. Wu, H. Tsukada, and M. Nagata. Learning to translate with multiple objectives. In Proc.
ACL, 2012.
C. Dyer, S. Muresan, and P. Resnik. Generalizing word lattice translation. In Proc. ACL, 2008.

Building a Phrase-Based SMT System
●

●

●

●
●

●
●

●

●

●

●
●

●
●

●

●

●

A. Fraser and D. Marcu. Semi-supervised training for statistical word alignment. In Proc. ACL, pages 769776, 2006.
M. Galley, J. Graehl, K. Knight, D. Marcu, S. DeNeefe, W. Wang, and I. Thayer. Scalable inference andtraining of context-rich syntactic translation models. In Proc. ACL, pages 961-968, 2006.
U. Germann, M. Jahr, K. Knight, D. Marcu, and K. Yamada. Fast decoding and optimal decoding for machinetranslation. In Proc. ACL, pages 228-235, 2001.
J. T. Goodman. A bit of progress in language modeling. Computer Speech & Language, 15(4), 2001.
A. Haghighi, J. Blitzer, J. DeNero, and D. Klein. Better word alignments with supervised ITG models. In Proc.
ACL, 2009.
M. Hopkins and J. May. Tuning as ranking. In Proc. EMNLP, 2011.
H. Isozaki, T. Hirao, K. Duh, K. Sudoh, and H. Tsukada. Automatic evaluation of translation quality for distantlanguage pairs. In Proc. EMNLP, pages 944-952, 2010.
H. Isozaki, K. Sudoh, H. Tsukada, and K. Duh. Head nalization: A simple reordering rule for sov languages. InProc. WMT and MetricsMATR, 2010.
J. H. Johnson, J. Martin, G. Foster, and R. Kuhn. Improving translation quality by discarding most of thephrasetable. In Proc. EMNLP, pages 967-975, 2007.
K. Knight. Decoding complexity in word-replacement translation models. Computational Linguistics, 25(4),1999.
P. Koehn, F. J. Och, and D. Marcu. Statistical phrase-based translation. In Proc. HLT, pages 48-54, 2003.
P. Koehn and J. Schroeder. Experiments in domain adaptation for statistical machine translation. In Proc.
WMT, 2007.
S. Kumar and W. Byrne. Minimum bayes-risk decoding for statistical machine translation. In Proc. HLT, 2004.
W. Ling, T. Lus, J. Graca, L. Coheur, and I. Trancoso. Towards a General and Extensible Phrase-Extraction
Algorithm. In M. Federico, I. Lane, M. Paul, and F. Yvon, editors, Proc. IWSLT, pages 313-320, 2010.
C.-k. Lo and D. Wu. Meant: An inexpensive, high-accuracy, semiautomatic metric for evaluating translation
utility based on semantic roles. In Proc. ACL, pages 220-229, 2011.
W. Macherey, F. Och, I. Thayer, and J. Uszkoreit. Lattice-based minimum error rate training for statisticalmachine translation. In Proc. EMNLP, 2008.
D. Marcu and W. Wong. A phrase-based, joint probability model for statistical machine translation. In Proc.
EMNLP, 2002.

Building a Phrase-Based SMT System
●

●
●

●

●

●
●

●
●

●

●

●
●

S. Matsoukas, A.-V. I. Rosti, and B. Zhang. Discriminative corpus weight estimation for machine translation.
In Proc. EMNLP, pages 708717, 2009.
H. Mi, L. Huang, and Q. Liu. Forest-based translation. In Proc. ACL, pages 192-199, 2008.
R. Moore. Fast and accurate sentence alignment of bilingual corpora. Machine Translation: From Research
to Real Users, pages 135-144, 2002.
G. Neubig, T. Watanabe, S. Mori, and T. Kawahara. Machine translation without words through substringalignment. In Proc. ACL, Jeju, Korea, 2012.
S. Niessen, H. Ney, et al. Morpho-syntactic analysis for reordering in statistical machine translation. In Proc.
MT Summit, 2001.
F. J. Och. Minimum error rate training in statistical machine translation. In Proc. ACL, 2003.
K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu. BLEU: a method for automatic evaluation of machinetranslation. In Proc. COLING, pages 311-318, 2002.
P. Resnik and N. A. Smith. The web as a parallel corpus. Computational Linguistics, 29(3):349-380, 2003.
J. Suzuki, K. Duh, and M. Nagata. Distributed minimum error rate training of smt using particle swarm
optimization. In Proc. IJCNLP, pages 649-657, 2011.
T. Watanabe, J. Suzuki, H. Tsukada, and H. Isozaki. Online largemargin training for statistical machinetranslation. In Proc. EMNLP, pages 764-773, 2007.
F. Xia and M. McCord. Improving a statistical MT system with automatically learned rewrite patterns. In Proc.
COLING, 2004.
K. Yamada and K. Knight. A syntax-based statistical translation model. In Proc. ACL, 2001.
O. F. Zaidan and C. Callison-Burch. Crowdsourcing translation: Professional quality from non-professionals.
In Proc. ACL, pages 1220-1229, 2011.