Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

An Unsupervised Model forJoint Phrase Alignment and Extraction
Graham Neubig1,2, Taro Watanabe2, Eiichiro Sumita2,
Shinsuke Mori1, Tatsuya Kawahara1
1

Graduate School of Informatics, Kyoto University
2
National Institute of Information and Communication Technology
1Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Phrase Table
Construction2

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

The Phrase Table●The most important element of phrase-based SMT●Consists of scored bilingual phrase pairs
Sourcelele admettre
admettre

Targetit
admit itadmit

Scores0.05 0.20 0.005 1
1.0 1.0 1e-05 10.4 0.5 0.02 1…
●

Usually learned from a parallel corpus aligned at thesentence level→ Phrases must be aligned3

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Traditional Phrase Table Construction:
1-to-1 Alignment, Combination, Extraction

Parallel
Text

WordAlignment(GIZA++)

f→e
1-ManyCombineWordAlignment(GIZA++)

e→f
1-ManyManyMany

PhraseExtract.

PhraseTable+ Generally quite effective, default for Moses- Complicated, with lots of heuristics- Does not directly acquire phrases, which are the final
goal of alignment- Phrase table is exhaustively extracted and thus large

4Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Previous Work:
Many-to-Many Alignment
Parallel
Text●PhraseAlignment

ManyMany

PhraseExtraction

PhraseTable

Significant recent research on many-to-manyalignment [Zhang+ 08, DeNero+ 08, Blunsom+ 10]+ Model is simplified, gains in accuracy●Short phrases are aligned, then combined into longer
phrases during the extraction step- Some issues still remain●Large phrase table, heuristics, no direct modeling ofextracted phrases

5

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Proposed Model for
Joint Phrase Alignment and Extraction
Parallel
Text●

HierarchicalPhraseAlignment

PhraseTable

Phrases of multiple granularities directly modeled+ No mismatch between alignment goal and final goal
+ Completely probabilistic model, no heuristics+ Competitive accuracy, smaller phrase table●Uses a hierarchical model for Inversion TransductionGrammars (ITG)
6Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Phrasal Inversion
Transduction Grammars(Previous Work)

7Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

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ûteadmit/admettre

EnglishI hateFrenchil me coûteEnglishadmit itit/leFrenchle admettre
8Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

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)9Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Learning Phrasal ITGs withBlocked Gibbs Sampling [Blunsom+ 10]
1) Choose sentence
to sample
D, E, F Corpus
eeeeeeeedieifieeee ffffffeeee ffffff

3) Perform biparsing
using Px and Pt...

cx(di)-- 2) Subtractct(di)-- current diffffffffffffeeeeeeeeffffffffffffeeeeeeeeffffffffffff

Symbol Counts cx
Biphrase Counts ct

PxPt?

eeee ffffffeeee ffffffcx(di)++ 4) Add
ct(di)++ new di5) Replace
di in the corpus

eeee ffffffeeee ffffff… and get a new10
sample for diNeubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Calculating Probabilities given Counts
ct(it/le)=12cx(reg)=415●ct(I/il me)=3cx(inv)=43ct(hate/coûte)=0cx(term)=312…

Adapt Bayesian approach, assume that probabilities weregenerated from Pitman-Yor process, Dirichlet distribution

P t ~ PY d , ,P base P x ~ Dirichlet =1,1/3
●Marginal probabilities can be calculated (in example, ignoring dfor the PY process)c t f ,et P base f ,e
P t f ,e=∑f , e c t f , etc x  x  x /3
P x  x =∑x c x  x  x

11

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Base Measurec t f ,et P base f ,e
P t f ,e=∑f , e c t f , et●Pbase has an effect of smoothing probabilities

Particularly for low frequency pairs● To bias towards good phrase pairs, use geometric meanof word-based Model 1 probabilities [DeNero+ 08]●P base e ,f =P m1 f∣e P uni e P m1 e∣f  P uni f ●12Good word match in both directions = good phrase match
12

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Calculating Counts given Derivations●Elements generated from each distribution Px and Pt
added to the counts used to calculate the probabilities

Px(reg)Px(term)Px(reg)Px(term)Px(term)Pt(base)cx(reg) += 3cx(inv) += 1cx(term) += 5Px(reg)Px(inv)Px(term)Px(term)ct(hate/coûte)++Pt(to/de)Pt(admit/admettre)

Pt(it/le)ct(i/il me)++ P (hate/coûte)base

ct(to/de)++ct(admit/admettre)++ct(it/le)++Pt(i/il me)●

Problem: only minimal phrases are added→Must still heuristically combine into multiple granularities

13

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Joint Phrase Alignmentand Extraction(Our Work)14

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Basic Idea●

Generative story in reverse order●

Traditional ITG Model:●●

Generate branches (reordering structure) from Px●Generate leaves (phrase pairs) from Pt

Proposed ITG Model:●

From the top, try to generate phrase pair from Pt●

Divide and conquer using Px to handle sparsity

15

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Derivation in the Proposed Model●

Phrases of many granularities generated from Pt, added to ct
Pt(base)ct(i hate to admit it/il me coûte de le admettre)++Px(reg)Pt(base)Pt(base)ct(i hate/il me coûte)++Px(reg)Pt(base)ct(i/il me)++ Pbase(hate/coûte)Pt(base)ct(admit it/le admettre)++ct(hate/coûte)++Pt(i/il me)cx(base) += 1

ct(to admit it/de le admettre)++Px(reg)Px(base)cx(reg) += 3cx(inv) += 1

Px(inv)Pt(to/de)Pt(admit/admettre)

Pt(it/le)ct(to/de)++ct(admit/admettre)++ct(it/le)++16●

No extraction needed, as multiple granularities are included!

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Recursive Base Measure●●Previous work: high prob. words = high prob. phrases
Proposed: Build new phrase pairs by combining
existing phrase pairs in Pdac (“divide-and-conquer”)
Pt(I/il me)←high

Pt(hate/coûte)←highPdac(I hate/il me coûte)←highc t f ,et P dac f ,e P t f ,e=∑f ,e c t f ,et●High probability sub-phrases → high probability phrases●Pt is included in Pdac, Pdac is included in Pt

17

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Details of Pdac
●Choose from Px one of three patterns for Pdac, like ITG
Regular: Px(reg) * Pt(I/il me) * Pt(hate/coûte) →I hate/il me coûte

Inverted: Px(inv) * Pt(admit/admettre) * Pt(it/le) →admit it/le admettreBase:●Px(base) * Pbase(hate/coûte) →hate/coûte

Pbase is the same as before18

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Phrase Extraction●Traditional Heuristics:
Exhaustively combine
and count all neighboringphrases●●P(f|e) = c(e,f) / c(e)O(n2) phrases per sent.

Model Probabilities:
Calculate phrase tablefrom model probabilities
where c(e,f) >= 1●

Phrase Table Scores
P(e|f) = c(e,f) / c(f)Phrase Table Scores
P(e|f) = Pt(e,f) / Pt(f)P(f|e) = Pt(e,f) / Pt(e)O(n) phrases per sent.
19

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Experiments

20

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Tasks/Data●

4 Languages, 2 tasks: es-en, de-en, fr-en, ja-en
de-en, es-en, fr-en: WMT10 news-commentary● ja-en: NTCIR08 patent translation●●

Data was lowercased, tokenized, and sentences oflength 40 and under were used

TMLM
Tune
Test

WMT
deesfren
1.85M 1.82M 1.56M 1.80M/1.62M/1.35M
52.7M
47.2k 52.6k 55.4k
49.8k
62.7k 68.1k 72.6k
65.6k

NTCIRjaen
2.78M 2.38M
44.7M
80.4k 68.9k
48.7k 40.4k
21Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Setting●Used Moses as a decoder●Evaluated using BLEU score●3 Alignment Methods:
GIZA++ and grow-diag-final-and heuristic● Traditional ITG model (FLAT)● Proposed ITG model (HIER)●●

2 Phrase Extraction Methods:
Heuristic phrase extraction● Using the model probabilities Pt●

22

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Results
Phrase Table Size

24
23
22
2120
1918
17
16

65Million Phrases

BLEU*100Translation Accuracy

de-en es-en fr-en ja-en

4GIZA++

GIZA++FLAT
3HIER
2FLATHIER

10de-en es-en fr-en ja-en●GIZA++ uses heuristic extraction, others use model probabilities●Same accuracy as GIZA++, phrase table smaller
23●Higher accuracy than FLAT (when using model probs.)

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Phrase Table: Heuristic Extraction vs.
Model Probabilities
Phrase Table Size

23

622

521

4FLAT
3HIER

Million Words

BLEU*100Translation Accuracy (fr-en)

20191817●HEURMODFLATHIER210HEUR

MOD

HIER + Model Probabilities has competitive accuracy,
smaller table size
24

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Conclusion●●●

Used a hierarchical model to include phrases ofmultiple granularities in the alignment process
Able to achieve competitive accuracy directly using
model probabilities in the phrase table
Future work:
Expansion to tree-based translation● Further refinement of modeling and search techniques●●Software is released open source:

pialign – Phrasal ITG Aligner
http://www.phontron.com/pialign25

Neubig et al. - An Unsupervised Model for Joint Phrase Alignment and Extraction

Thank You!

26