Lattice and Hypergraph MERT

Lattice and Hypergraph MERT

Graham Neubig
Nara Institute of Science and Technology (NAIST)
12/20/2012

1

Lattice and Hypergraph MERTPapers Introduced:●●“Lattice-based Minimum Error Rate Training for Statistical
Machine Translation”
Wolfgang Macherey, Franz Josef Och, Ignacio Thayer,
Jakob Uszkoreit (Google)
EMNLP 2008
“Efficient Minimum Error Rate Training and Minimum
Bayes-Risk Decoding for Translation Hypergraphs andLattices”
Shankar Kumar, Wolfgang Macherey, Chris Dyer, Franz
Och (Google/University of Maryland)
ACL-IJCNLP 20092

Lattice and Hypergraph MERT

Summary●●●●

Minimum error rate training (MERT) is used to train theparameters for machine translation
Normal MERT uses n-best lists
However, there is not enough diversity in n-best lists,→ unstable training & large accuracy fluctuations
As a solution these papers perform MERT overlattices for phrase-based translation [Macherey+ 08]● hypergraphs for tree-based translation [Kumar+ 09]●●

This leads to more stable training in fewer iterations3

Lattice and Hypergraph MERT

Tuning/MERT4

Lattice and Hypergraph MERT

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-2

LM
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

Lattice and Hypergraph MERTMERT●MERT performs iterations to increase the score[Och 03]n-best (dev)source (dev)
太郎が花子を訪問した

ModelDecode

Weights

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

reference (dev)
Taro visited Hanako
Find better
weights

Lattice and Hypergraph MERTMERT●MERT performs iterations to increase the score[Och 03]n-best (dev)source (dev)
太郎が花子を訪問した

ModelDecode

Weights

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

reference (dev)Taro visited Hanako
Find better
weights

These slides

Lattice and Hypergraph MERTMERT Weight Update:●Adjust one weight at a time
wLM

Initial:Optimize wLM:
Optimize wTM:
Optimize wRM:
Optimize wLM:
Optimize wTM:

Weights
wTM
wRM

Score

0.1

0.1

0.1

0.20

0.4

0.1

0.1

0.32

0.4

0.1

0.1

0.32

0.4

0.1

0.3

0.4

0.35

0.1

0.3

0.41

8

Lattice and Hypergraph MERT

Updating One Weight:●We start with:n-best list
f1

φLM φTM φRM BLEU*

f2

φLM φTM φRM BLEU*

e1,1 10-10e2,1 10-20

e1,2 0101

e2,2 3010

e1,3 1010e2,3 2121fixed weights:
wLM=-1, wTM=1weight to be adjusted:
wRM=???
* Calculating BLEU for one sentence is a bit simplified, usually we compute for the whole corpus

Lattice and Hypergraph MERT

Updating One Weight:●

Next, transform each hypothesis into lines:

y =a x+b●

Where:
a is the value of the feature to be adjusted● b is the weighted sum of the fixed features● x is the weight to be adjusted (unknown)●

Lattice and Hypergraph MERT

Updating One Weight:●Example:y =a x+bwLM=-1, wTM=1, wRM=???
f1

a=ϕRM

b=w LM ϕLM +wTM ϕTMφLM φTM φRM

e1,1 10-1

a1,1=-1

b1,1=-1

e1,2 01

0a1,2=0b1,2=1e1,3 101

a1,3=1b1,3=-1

Lattice and Hypergraph MERT

Updating One Weight:●Draw lines on a graph:y =a x+bf1 hypotheses
4e1,1-4-204e2,1

e1,32e1,2f2 hypotheses

24-4-20-2-2-4-4a1,1=-1
a1,2=0a1,3=1e2,320

b1,1=-1
b1,2=1b1,3=-1

a2,1=-2a2,2=1a2,3=-2

BLEU=1
BLEU=0e2,2
02b2,1=-1b2,2=-3b2,3=14

Lattice and Hypergraph MERT

Updating One Weight:●Find the lines that are highest for each range of x:
f1 hypotheses
4e1,1-4●-20

4e2,12e1,2

f2 hypotheses

e1,3

e2,32024-4-20-2-2-4-4

e2,2024

This is called the convex hull (or upper envelope)Lattice and Hypergraph MERT

Updating One Weight:
Using the convex hull, find scores at each range:
4e1,1

f1

f2

e1,3e1,2-4-2-4-20

4e2,12BLEU●e2,32024-4-20e2,20-2-2-4-4

1100024-4-202424

Lattice and Hypergraph MERT

Updating One Weight:
Combine multiple sentences into a single error plane:
f1-4-2f2

110002-4

4-2

total accuracy
1BLEU

BLEU

●-4-20024024

Lattice and Hypergraph MERT

Updating One Weight:
Choose middle of best region:
total accuracy
1BLEU●-4-2002wRM ←1.04

Lattice and Hypergraph MERT

Summary●For each sentence:
Create lines for each n-best hypothesis● Combine lines and find upper envelope● Transform upper envelope into error surface●●Combine error surfaces into one●

Find the range with the highest score●

Set the weight to the middle of the range

Lattice and Hypergraph MERT

Summary●For each sentence:

Problem! (not enough diversity)

Create lines for each n-best hypothesis● Combine lines and find upper envelope● Transform upper envelope into error surface●●Combine error surfaces into one●Find the range with the highest score●Set the weight to the middle of the range

Lattice and Hypergraph MERT

Result of Lack of Diversity●

Unstable training:

Traditional MERT
in Green[Macherey 08]

Lattice and Hypergraph MERT

Lattice MERT20

Lattice and Hypergraph MERTTranslation Lattice●Represent many hypotheses compactly:
Tarothe TarometHanako

visited the Hanako

8 hypotheses
in only
6 edges●MERT on lattices can solve the diversity problem

Lattice and Hypergraph MERT

Factoring Feature Functions●Each edge in the lattice has a feature value:
φLM=1, φTM=1, φRM=2

φLM=1, φTM=1, φRM=-1

Taro

met

Hanakothe Tarovisitedthe Hanako

φLM=2, φTM=0, φRM=1●

φLM=0, φTM=-1, φRM=-1

φLM=-2, φTM=-1, φRM=-1

φLM=2, φTM=0, φRM=0

Hypothesis's features are sum of edge features:
φLM=1, φTM=1, φRM=2

Taro

φLM=0, φTM=-1, φRM=-1

met

φLM=2, φTM=1, φRM=0

φLM=1, φTM=1, φRM=-1

HanakoLattice and Hypergraph MERTMERT on Lattices:●For each sentence:

Only different part!!

Transform each edge into lines● Find the upper envelope for the lattice● Transform upper envelope into error surface●●

Combine error surfaces into one●

Find the range with the highest score●

Set the weight to the middle of the range

Lattice and Hypergraph MERTFirst, Transform each Edge into Lines
φLM=1, φTM=1, φRM=2

φLM=0, φTM=-1, φRM=-1

φLM=1, φTM=1, φRM=-1

TarometHanakothe Tarovisitedthe Hanako

φLM=2, φTM=0, φRM=1

φLM=-2, φTM=-1, φRM=-1

wLM=-1, wTM=1, wRM=???

φLM=2, φTM=0, φRM=0

y =a x+ba=ϕRM b=w LM ϕLM +wTM ϕTM

a=2, b=0

a=-1, b=-1

a=-1, b=0

Taro

metHanako

the Tarovisitedthe Hanako

a=1, b=-2

a=-1, b=1

a=0, b=-2

Lattice and Hypergraph MERT

Finding the Upper Envelope for Lattices:●

Can be done with dynamic programming●

1) Start with flat envelope for initial node●2) Calculate upper envelope for next node usingprevious nodes

Lattice and Hypergraph MERT

Start with Flat Envelope
a=2, b=0

a=-1, b=-1

a=-1, b=0

Taro

metHanako

the Tarovisitedthe Hanako

a=1, b=-2

a=-1, b=1

a=0, b=-2

42-4-20-2

02-4

y =a x+b4

a=0 b=0 “”Lattice and Hypergraph MERT

Add First Node-4-2

a=2, b=0

a=-1, b=-1

a=-1, b=0

Taro

metHanako

the Tarovisitedthe Hanako

a=1, b=-2

a=-1, b=1

a=0, b=-2

44220-202-4

y =a x+b4

a=0 b=0 “”

a=2 b=0 “Taro”-4-20-2024-4
a=1 b=-2 “the Taro”

Lattice and Hypergraph MERT

Add Second
a=2, b=0

a=-1, b=-1

a=-1, b=0

TarometHanakothe Tarovisitedthe Hanako

a=1, b=-2

a=-1, b=1

a=0, b=-2442-4-20-2

a=1 b=1 “Taro visited”

02-4

y =a x+ba=2 b=0 “Taro”
4 a=1 b=-2 “the Taro”

a=1 b=-1 “Taro met”

2-4-20-2-40

2

4 a=0 b=-1 “the Taro visited”
a=0 b=-3 “the Taro met”

Lattice and Hypergraph MERT

Add Second
a=2, b=0

a=-1, b=-1

a=-1, b=0

TarometHanako

the Tarovisitedthe Hanako

a=1, b=-2

a=-1, b=1

a=0, b=-244

2-4-20-2

a=1 b=1 “Taro visited”

02-4

y =a x+ba=2 b=0 “Taro”
4 a=1 b=-2 “the Taro”

X

2-4-2

0-2-402X

a=1 b=-1 “Taro met”
4 a=0 b=-1 “the Taro visited”

X Taro met”
X a=0 b=-3 “theDelete all lines not in upper envelope

Lattice and Hypergraph MERT

Add Seconda=2, b=0

a=-1, b=-1

a=-1, b=0

Taro

met

Hanakothe Tarovisitedthe Hanako

a=1, b=-2

a=-1, b=1

a=0, b=-2

4

4

2-4-2

0-2

a=1 b=1 “Taro visited”

02-4

y =a x+ba=2 b=0 “Taro”
4 a=1 b=-2 “the Taro”

2-4-2

0-2-4

0

2

4 a=0 b=-1 “the Taro visited”

Lattice and Hypergraph MERT

Add Third
a=2, b=0

a=-1, b=-1

a=-1, b=0

Taro

met

Hanakothe Tarovisitedthe Hanako

a=1, b=-2

a=-1, b=1

a=0, b=-2a=1 b=1 “Taro visited”
a=0 b=-1 “the Taro visited”-4-2

442200-2-402

y =a x+b4-4-2-2-4

a=1 b=-1 “Taro visited the Hanako”
a=0 b=1 “Taro visited Hanako”
024
a=0 b=-3 “the Taro visited the Hanako”
a=-1 b=-1 “the Taro visited Hanako”

Lattice and Hypergraph MERT

Add Third
a=2, b=0

a=-1, b=-1

a=-1, b=0

TarometHanako

the Tarovisitedthe Hanako

a=1, b=-2

a=-1, b=1

a=0, b=-2

a=1 b=1 “Taro visited”
a=0 b=-1 “the Taro visited”

-4-2

442

200-2-402

y =a x+b4-4-2-2

a=1 b=-1 “Taro visited the Hanako”
a=0 b=1 “Taro visited Hanako”
0-4 X

24X

a=0 b=-3 “the Taro visited the Hanako”
a=-1 b=-1 “the Taro visited Hanako”

Lattice and Hypergraph MERT

Add Third
a=2, b=0

a=-1, b=-1

a=-1, b=0

TarometHanako

the Tarovisitedthe Hanako

a=1, b=-2

a=-1, b=1

a=0, b=-2

a=1 b=1 “Taro visited”
a=0 b=-1 “the Taro visited”-4-2442200-2-402

y =a x+b4-4-2-2-4

a=1 b=-1 “Taro visited the Hanako”
a=0 b=1 “Taro visited Hanako”
024
a=-1 b=-1 “the Taro visited Hanako”

Lattice and Hypergraph MERT

Improved Stability
Lattice MERTin RedTraditional MERT
in GreenLattice and Hypergraph MERTHypergraph MERT35

Lattice and Hypergraph MERTTranslation Hypergraph
VP0-5
VP2-5

PP0-1
N0P1

友達とPP2-3

VP4-5

N2P3

V4 SUF5

ご飯を食べたVP0-5

x1 with x0: 0.56
N0friend: 0.12
my friend: 0.3

VP2-5x1 x0: 0.6
N2a meal: 0.5 rice: 0.3

VP4-5
ate: 0.536

Lattice and Hypergraph MERTHypergraph MERT
●Almost exactly the same as lattice MERT
Lattice MERT-4

420-2 0-2-424

a=2, b=0

TaroHypergraph MERT
VP0-5x1 with x0: a=2 b=0

VP2-5N0

the Taro
a=1, b=-2-4

420-2 0-2-4-42420-2 0-2-42437

4

Lattice and Hypergraph MERT

Summary38

Lattice and Hypergraph MERT

Summary●●●n-best MERT is unstable because of lack of diversity inthe n-best list
This problem can be solved by lattice or hypergraph
MERT
Algorithm finds the upper envelope for each sentence
efficiently using dynamic programming

39