Statistical Machine Translation

Statistical Machine Translation

Graham Neubig
Nara Institute of Science and Technology (NAIST)
10/23/2012

1

Statistical Machine Translation

Machine Translation●●Automatically translate between languages
SourceTarget

太郎が花子を訪問した。

Taro
visitedHanako.

Real products/services being created!
NAIST Travel
Conversation
Translation System(@AHC Lab)
2

Statistical Machine Translation

How does machine translation work?

Today I will give a lecture on machine translation .

3

Statistical Machine Translation

How does machine translation work?
●Divide sentence into translatable patterns, reorder,
combineToday I will give a lecture on machine translation .
TodayI will give
今日は、 を行いますToday
今日は、a lecture onの講義

machine translation
機械翻訳

machine translation
機械翻訳a lecture onの講義

I will giveを行います.
。

.
。

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

Statistical Machine Translation

Problem●

There are millions of possible translations!
花子 が 太郎 に 会った
Hanako met Taro
Hanako met to Taro
Hanako ran in to Taro
Taro met Hanako
The Hanako met the Taro●How do we tell which is better?
5

Statistical Machine Translation

Statistical Machine Translation●Translation model:P(“ 今日” |“today”) = highP(“ 今日 は 、” |“today”) = medium

P(“ 昨日” |“today”) = low

P(●Reordering Model:

鶏がchicken eats
●鶏食べる)=highP(をeats食べる鶏)=highchicken

P(がeats食べる)=lowchicken

Language Model:P( “Taro met Hanako” )=highP( “the Taro met the Hanako” )=high6

Statistical Machine Translation

Creating a Machine Translation System●Learn patterns from documents
Documents

ModelsTranslation Model

太郎が花子を訪問した。
Taro visited Hanako.
花子にプレセントを渡した。
He gave Hanako a present.
...

United Nations Text(English/French/Chinese/Arabic ...)
Yomiuri Shimbun, Wikipedia Text(Japanese/English)

Reordering Model
Language Model

7

Statistical Machine Translation

How Do we Learn Patterns?
●For example, we go to an Italian restaurant w/Japanese menu
チーズムースMousse di formaggi
タリアテッレ ４種のチーズソース
Tagliatelle al 4 formaggi
本日の鮮魚
Pesce del giorno
鮮魚のソテー お米とグリーンピース添え
Filetto di pesce su “Risi e Bisi”
ドルチェとチーズ
Dolce e Formaggi●

Try to find the patterns!

8Statistical Machine Translation

How Do we Learn Patterns?
●For example, we go to an Italian restaurant w/Japanese menu
チーズムースMousse di formaggi
タリアテッレ ４種のチーズソース
Tagliatelle al 4 formaggi
本日の鮮魚
Pesce del giorno
鮮魚のソテー お米とグリーンピース添え
Filetto di pesce su “Risi e Bisi”
ドルチェとチーズ
Dolce e Formaggi●

Try to find the patterns!

9Statistical Machine Translation

Steps in Training a
Phrase-based SMT System●

Collecting Data●

Tokenization●

Language Modeling●

Alignment●

Phrase Extraction/Scoring●

Reordering Models●

Decoding●

Evaluation●

TuningStatistical Machine Translation

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.

Statistical Machine Translation●

Big! →Translation Accuracy

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

Statistical Machine Translation

Collecting Data
●High quality parallel data from:Government organizations● Newspapers● Patents●●Crawl the web●Merge several data sources

Statistical Machine Translation

Finding Data on the Web●

Find bilingual pages [Resnik 03][Image: Mainichi Shimbun]

Statistical Machine Translation

Finding Data on the Web●

Finding bilingual pages [Resnik 03]●

Sentence alignment [Moore 02]

Statistical Machine Translation

Question 1:●●

Write down three candidates for sources of parallel
data in English-Japanese, or some other language
pair you are familiar with.
They should all be of different genres.

Statistical Machine Translation

Tokenization●

Example: Divide Japanese into words

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

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

Statistical Machine Translation

Tokenization is Important!
●●●

Just Right: Can translate properly
太郎 がtaro ○太郎 をtaro ○

Too Long: Cannot translate if not in training data
太郎がtaro ○In Data

太郎を太郎を ☓Not in Data

Too Short: May mistranslate
太 郎 が

fat ro ☓太 郎 を

fat ro ☓18

Statistical Machine Translation

Language Modeling●

Assign a probability to each sentence

E1: Taro visited HanakoP(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)

Statistical Machine Translation

n-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 
20

Statistical Machine Translation

Calculating n-gram Models●n-gram models are estimated from data:c (w i−n+1 … wi )P( wi∣w i−n+1 … wi−1 )=c ( wi− n+1 … wi−1)
i live in osaka . 
i am a graduate student . 

my school is in nara . 
P(osaka | in) = c(in osaka)/c(in) = 1 / 2 = 0.5
n=2 →P(nara | in) = c(in nara)/c(in) = 1 / 2 = 0.5
21Statistical Machine Translation

Question 2:●

Calculate the 2-gram probabilities of the n-grams on
the worksheet.

22

Statistical Machine Translation

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

23

Statistical Machine Translation

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●24Statistical Machine Translation

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

the hotel front deskX
ホテル の 受付

Combinethe hotel front desk
ホテル の 受付●

Several different heuristics

25

Statistical Machine Translation

Phrase Extraction●Use alignments to find phrase pairs

ホテ 受ルの付
thehotelfrontdesk

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

Statistical Machine Translation

Phrase Extraction Criterion●Must have1) one alignment inside the phrase● 2) no alignments outside and in the same row/column●

OK!
thehotelfrontdesk

ホテ 受ルの付

No alignments inside“ の” outside

Statistical Machine Translation

Question 3:●

Given the alignments on the work sheet, whichphrases will be extracted by the machine translation
system?

28

Statistical Machine Translation

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

Statistical Machine Translation

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

thethinmanvisited
Taromono

細い → the thinhigh monotone probability●disc.

swap

太郎 を → Tarohigh swap probability

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

Statistical Machine Translation

Decoding●

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]

Statistical Machine Translation

Phrase-Based Decoding●●●

Build translation fromleft to right
Remember which
words were alreadytranslated
Choose translation
with highest scoreen:hevisited

thewhitehouse

ja:
en:

hevisited

thewhitehouse

ja:

彼は

en:

hevisited

thewhitehouseja:

彼はホワイト ハウス を

en:hevisitedja:

彼はホワイト ハウス を 訪問 した

thewhitehouse

Statistical Machine Translation

Question 4:●

How would a phrase-based machine translation
system generate the translation on the work sheet?

33

Statistical Machine Translation

Evaluation●We built a machine translation system, we need toknow:How good is our system?
● Is system A better than system B?
● What are the problems with our system?
●

Statistical Machine Translation

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☓
○

Statistical Machine Translation

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)Statistical Machine Translation

Tuning●Scores of translation, reordering, and language models○ Taro visited Hanako☓ the Taro visited the Hanako☓ Hanako visited Taro
●TM-3-4-3RM-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-2LMTMRM
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

Statistical Machine Translation

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]

Statistical Machine Translation

Question 5:●

Given the list of hypotheses on the worksheet, findweights that maximize the BLEU score.

Statistical Machine Translation

Assignment

Statistical Machine Translation

Assignment (choose one):●Paraphrasing Sentencesa) Use Google Translate to find at least 10 sentences thatare not translated properly, and guess why.
●b) Create a strategy to paraphrase the sentences so they
are easier to translate. Explain why this strategy works.
Manual Evaluation:●●a) Using provided translation results, perform a manual
Adequacy/Fluency evaluation, report the distribution ofscores (1-5) and some examples of good/bad scores.
●b) For 5-10 bad translations, discuss why translation failed.
Creating a Translation System:●●●●a) Follow the steps on this page to make a machinetranslation system and measure the accuracy:
http://www.statmt.org/moses/?n=Moses.Baselineb) Find a setting of the system that changes the accuracy,and discuss its effect.

Statistical Machine Translation

Assignment Submission●

Use the additional materials on the web site if you
choose the “Manual Evaluation” assignment.

●

Length: 500+ words plus figures/tables if necessary●

Address: neubig@is.naist.jp●

Deadline: 2012-10-30, 23:59