Machine Translation without Words through Substring Alignment

Machine Translation without Words
through Substring Alignment
Graham Neubig1,2,3, Taro Watanabe2,1
1
Shinsuke Mori , Tatsuya Kawahara
12

3

now at1

Machine Translation without Words through Substring Alignment

Machine Translation●●

Translate a source sentence F into a target
sentence E
F and E are strings of words

F = これ は ペン ですf1 f2 f3f4
E = this is a pen
e1 e2 e3 e42Machine Translation without Words through Substring Alignment

Sparsity Problems●Transliteration: For proper names, changefrom one writing system to another

寂原○jakugen☓ 寂原

3

Machine Translation without Words through Substring Alignment

Sparsity Problems●

Inflected or compound words cause large
vocabularies and sparsity

huolestumista○concerned [elative]☓huolestumista

4

Machine Translation without Words through Substring Alignment

Sparsity Problems●

Chinese and Japanese have no spaces, must
be segmented into words

レストン
レストン

レス トン

○Leston☓tons of responses

5

Machine Translation without Words through Substring Alignment(Lots of!) Previous Research●●

Transliteration: [Knight&Graehl 98, Al-Onaizan&Knight
02, Kondrak+ 03, Finch&Sumita 07]
Compounds/Morphology: [Niessen&Ney 00, Brown
02, Lee 04, Goldwater&McClosky 05, Talbot&Osborne
06, Bojar 07, Macherey+ 11, Subotin 11]●

Segmentation: [Bai 08, Chang 08, Zhang 08]●

All focus on solving one of these particular problems

6

Machine Translation without Words through Substring Alignment

Can We Translate Letters?
[Vilar+ 07]●

Problems because we are translating words!

F= こ れ は ペ ン で す
E= this_is_a_pen●

Previously: “Yes, but only for similar languages”●Spanish-Catalan [Vilar+ 07]
Thai-Lao [Sornlertlamvanich+ 08]
Swedish-Norwegian [Tiedemann 09]7

Machine Translation without Words through Substring Alignment

Yes, We Can!
●●We show character-based MT can match
word-based MT for distant languages.
Key: Many-to-many alignment through
Bayesian Phrasal ITG [Neubig+ 11]

Improved speed and accuracy for characterbased alignment● Competitive automatic and human evaluation●●Handles many sparsity phenomena
8Machine Translation without Words through Substring Alignment

Word/Character Alignment9

Machine Translation without Words through Substring Alignment

One-to-Many Alignment(IBM Models, GIZA++)●

Each source word must align to at most one
target word [Brown 93, Och 05]

ホテル の 受付X
the hotel front desk

the hotel front deskX
ホテル の 受付

Combine to get many-to-many alignments

the hotel front desk
ホテル の 受付10

Machine Translation without Words through Substring Alignment

One-to-Many Alignment of
Character Strings●

There is not enough informationin single characters to align well11

Machine Translation without Words through Substring Alignment

One-to-Many Alignment of
Character Strings●●

There is not enough informationin single characters to align well
Words with the same spelling dowork:“proje” ⇔ “proje”● “audaci” ⇔ “audaci”●

12Machine Translation without Words through Substring Alignment

Many-to-Many Alignment●Can directly generate phrasal alignments

the hotel front desk
ホテル の 受付●

Often use the Inversion Transduction Grammar
framework [Zhang 08, DeNero 08, Blunsom 09,
Neubig 11]13

Machine Translation without Words through Substring Alignment

Many-to-Many Alignmentof Character Strings●●

Example of [Neubig+ 11] applied
to characters
Recover many types of alignments:
Words: “project” ⇔ “projet”● Phrases: “both” ⇔ “les deux”● Subwords: “~cious” ⇔ “~cieux”● Even agreement!:“~s are” ⇔ “~s sont”●14Machine Translation without Words through Substring Alignment

Two Problems
1) Alignment algorithm is too slow
●We introduce a more effective beam pruning method
using look-ahead probabilities (similar to A*)

2) Prior probability is still single-unit based●We introduce prior based on sub-string co-occurrence15

Machine Translation without Words through Substring Alignment

Look-Ahead Parsing for ITGs

16

Machine Translation without Words through Substring Alignment

Inversion Transduction Grammar (ITG)●Like a CFG over two languages
Have non-terminals for regular and inverted productions● One pre-terminal● Terminals specifying phrase pairs●reginv

term

term

term

term

I/il mehate/coûte

admit/admettre

EnglishI hateFrenchil me coûteEnglishadmit it

it/leFrenchle admettre
17

Machine Translation without Words through Substring Alignment

Two Steps in ITG Parsing
2.
Non-Terminal
Combinationstr
strstr
term

term

term

inv
term

i/il mehate/coûte

to/deadmit/admettretermit/le1.
Terminal
Generation●

Step 1 is calculated by looking up all phrase pairs●

Step 2 is calculated by combining neighboring pairs●Takes most of the time18

Machine Translation without Words through Substring Alignment

Beam Search for ITGs [Saers+ 09]●

Stacks of elements with same number of words
Size 1i/ε
ε/il
ε/le
to/ε
ε/me
ε/deit/ε
hate/ε…
●

P=1e-6P=1e-6P=7e-7P=6e-7P=3e-7P=2e-7P=2e-7P=5e-8Size 2Size 3P=1e-3P=1e-5i/mei/il me
P=5e-4 hate/me coûte P=1e-6
to/deit/le
P=4e-4 i hate/coûte P=8e-7i/il
to/il me P=4e-7
P=2e-4hate/coûte P=1e-4 admit/le admettre P=8e-8ε/il me P=4e-5 admit it/admettre P=5e-8admit/admettre P=2e-5i/me coûte P=2e-8
to/me
to/me
P=5e-6P=1e-8…

…

Do not expand elements outside of fixed beam (1e-1)

19Machine Translation without Words through Substring Alignment

Problem with Simple Beam Search●Does not consider competing alignments!

e1e2f1f2f3
les années 60-5
the -2 -121960s -8

Has competitor “les/the”= can be pruned-8-8

Has no good competitor= should not be pruned
20* scores are log probabilities

Machine Translation without Words through Substring Alignment

Proposed Solution:
Look Ahead Probabilities and A* Search●Minimum probability to translate monolingual spane1e2

●f1f2
f3
les années 60-5
the -2 -12
1960s -8-0-2-10α(u)-8-0 -2α(s)-8β(t)-0 -0 -8-5-13β(v)Beam score: inside prob * outside probabilities
α(u)+log(P(s,t,u,v))+β(v),min( α(s)+log(P(s,t,u,v))+β(t) )21

Machine Translation without Words through Substring Alignment

Substring Co-occurrence
Prior Probability

22

Machine Translation without Words through Substring Alignment

Substring Occurrence Statistics●For each input sentence count every substring●●Use enhanced suffix arrayfor efficiency (esaxx library)

Make a matrix

こ れ は ペ ン で すF1

そ れ は 鉛 筆 で す
F2

…

これ
これはれは
これはペはペれはペ
これはペ

F1F210111011111010

101010…

23

Machine Translation without Words through Substring Alignment

Substring Co-occurrence Statistics●Take the product of two matrices to get co-occurrence
F1F2

こ

10

れ

11

これ

10

は1

1

れは11

これは10

ペ10

はペ

10

れはペ

10

これはペ 10t… *hthihi

thi

s is

his

this

E1 1 1 1 1 1 1 1 1 1

1E2 1 1 1 1 0 0 1 1 00…

c(f,e)
24

Machine Translation without Words through Substring Alignment

Making Probabilities and Discount●●Convert counts to probabilities by taking geometricmean of conditional probabilities (best results)
In addition, discount counts by fixed d (=5)●Reduces memory usage (do not store ce,f <= 5)●Helps prevent over-fitting of the training datac e , f −d c e , f −d
P e , f =/Z
c e −d c f −d25Machine Translation without Words through Substring Alignment

Experiments

26

Machine Translation without Words through Substring Alignment

Experimental Setup●4 languages with varying characteristics ⇔ English:
German: Some compounding● Finnish: Very morphologically rich
● French: Mostly word-word correspondence● Japanese: Requires segmentation, transliteration●TMLMTuneTest●●de2.56M
15.3M
55.1k
54.3k

fi
2.23M
11.3M
42.0k
41.4k

EuroParl
KFTTfrenjaen
3.05M 2.80M/3.10M/2.77M 2.34M 2.13M
15.6M 16.0M/15.5M/13.8M 11.9M 11.5M
67.3k
58.7k 34.4k 30.8k
66.2k
58.0k 28.5k 26.6k

Sentences of 100 characters and under were used
Evaluate with word/character BLEU, METEOR

27Machine Translation without Words through Substring AlignmentSystems●Which unit?
Word-Based: Align and translate words● Char-Based: Align and translate characters●●Which alignment method?
One-to-many: IBM Model 4 for words, HMM model forcharacters● Many-to-many: ITG-based model with proposedimprovements●28

Machine Translation without Words through Substring Alignment

BLEU Score (Word)
0.35

BLEU (Word)

0.3
0.25

IBM-word
ITG-word
IBM-char
ITG-char

0.2
0.15
0.1
0.05
0de-en

fi-en

fr-en

ja-en

ITG-Char vs.

IBM-Char: +0.1374 +0.1147 +0.1565 +0.0638
ITG-Word: -0.0208 -0.0245 -0.0322 -0.0130

29Machine Translation without Words through Substring Alignment

BLEU Score (Char)
0.8

BLEU (Char)

0.7
0.6

IBM-word
ITG-word
IBM-char
ITG-char

0.5
0.4
0.3
0.2
0.1
0de-en

fi-en

fr-en

ja-en

ITG-Char vs.

IBM-Char: +0.1946 +0.2082 +0.1853 +0.0939
ITG-Word: -0.0042 +0.0140 -0.0188 +0.0181

30

Machine Translation without Words through Substring Alignment

Human Adequacy Evaluation●●

200 sentences in each language, 0-5 rating

ITG-Word

ITG-Char

ja-en

2.085

2.154

fi-en

2.851

2.826

Systems are comparable (no difference at P<0.05)

31Machine Translation without Words through Substring Alignment

Notable Improvements●Examples where ITG-Char was 2+ points better
Ref
directive on equality

Unknown (13/26)

Target Unknown(5/26)

Uncommon (5/26)●Wordtasa-arvodirektiivi

Charequality directive

Refyoshiwara-juku station

Wordyoshiwara no ekiCharyoshiwara-juku station

Refworld health organisation

Word

world healthCharworld health organisation

ITG-Word was often better at reordering32

Machine Translation without Words through Substring Alignment

Effect of Proposed Improvementsover [Neubig+ 11] (METEOR)
0.4

METEOR

0.35
0.3
0.25
0.2

●ITG -cooc -look
ITG +cooc -look
ITG -cooc +look
ITG +cooc +look

fi-en

en-fi

ja-en

en-ja

Look-ahead also allowed for a 2x improvement in speed

33

Machine Translation without Words through Substring Alignment

Conclusion●

Character-based SMT can achieve comparable results
to word-based SMT●●+ Is able to handle sparsity issues

Remaining challenges:
Improve decoding to allow for better reordering● Treat spaces differently than other characters toimprove alignment/decoding●Available Open Source:
http://www.phontron.com/pialign34

Machine Translation without Words through Substring Alignment

Thank You!

35

Machine Translation without Words through Substring Alignment

METEOR Score (Word)
Counts reordering, matches using lemmatization,synonyms

METEOR

●

0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0

ITG-Char vs.

IBM-word
ITG-word
IBM-char
ITG-char
de-en

fi-en

fr-en

ja-en

IBM-Char: +0.1477 +0.1455 +0.1467 +0.0624
ITG-Word: -0.0059 +0.0048 -0.0182 -0.0031

36

Machine Translation without Words through Substring Alignment

Biparsing-based Alignment with ITGs
●Non/pre-terminal distribution Px, and phrase distribution Pt

i hate to admit it
il me coûte de le admettre
Px(reg)Px(reg)Px(term)Pt(i/il me)

Sentence Pair <e,f>Px(term)Pt(hate/coûte)Px(reg)Px(term)Pt(to/de)Px(inv)

Derivation dPx(term)Px(term)Pt(admit/admettre)

Pt(it/le)ihatetoadmit

itAlignment ail me coûte de le admettre●Viterbi parsing and sampling both possible in O(n 6)37