EM ON IBM MODEL 1 (BRUTE FORCE) Solution

This is a worked example showing convergence of EM training with IBM model 1.




The pairs are












S1
la maison






S2
la fleur








O1
the house






O2
the flower






To apply the brute force EM algorithm, for each pair, each of its possible alignments has to be considered. Including the possibility of aligning positions in O with NULL, there are 32 = 9 possibilities. To save a little in the pencil-and-paper calculations, we will consider a version which does NOT allow aligning positions in O with NULL. In this case, there are 22 = 4 possibilities:



la
ma
la
ma
la
ma
la
ma


































the
ho




the


ho
the
ho
the


ho
la
fl
la
fl
la
fl
la
fl
























































the
flo


the
flo
the
flo
the
flo






use a11 . . . a14 for the 4 possible alignments between O1 and S1 use a21 . . . a24 for the 4 possible alignments between O2 and S2




table shows translations probabilites, with tr(o|s) shown at row o, col s, and they are all ini-tialised to 13




tr(o|s)




the




ho




f lo







la
ma
f l
1


1


1




















3


3


3


1


1


1




















3


3


3


1


1


1




















3


3


3





To execute the brute force EM algorithm we need first for the pairs O1, S1 and O2, S2 to determine the conditional alignment probabilities so p(a|O1, S1) and p(a|O2, S2). The slides gave a derivation of the formula for p(a|O, S), it came out to be








p(a|O, S) =
j
[p(oj |sa(j))]


(1)




a′
j [p(oj |sa′ (j))]








and in the derivation
1
terms cancelled.
In the corresponding derivation disallowing
(ℓS +1)ℓO








1


alignments to NULL, there will instead be a cancellation of


terms, and exactly the same
(ℓS)ℓO
formula for the conditional alignment probability (1) will be derived.




As a name for the numerator term in (1) we will use num(a)




So to determine the p(a|O, S) values for each pair we need to



1






1. for each possible a determine num(a) (ie. j [p(oj |sa(j))])




2. sum these to give the denominator a num(a) and then take ratios




Armed with these conditional probabilities can then compute expected counts of o, s combina-tions across the corpus, and from these recalculate tr(o|s) probabilities.




ITERATION 1




considering the first pair, for each a1n calculate num(a1n):




num(a1)
num(a1)
num(a1)
num(a1)




1
2
3
4
=
1


1


ditto
ditto
ditto


3
3








=
1


























9















sim. for each a2n calculate num(a2n). At this stage, these all work out as 19 .




from these to calculate the conditional probabilities P (adn|O, S), need to sum the num(an) by summing across the table and use it as denominator ie.




d d
d


num(and)


P (an|O
, S
) =






n
′ num(ad
′ )






n





P (a11|O1, S1) P (a12|O1, S1) P (a13|O1, S1) P (a14|O1, S1)

=
1/9
ditto
ditto
ditto
4×1/9








14



P (a21|O2, S2) P (a22|O2, S2) P (a23|O2, S2) P (a24|O2, S2)

=
1/9
ditto
ditto
ditto
4×1/9








14



Notice these numbers make intuitive sense: with all tr(o|s) set equal, all alignments should be equally probable, giving a value of 14 for each.




Now for each possible vocabulary combination o, s combination we have to make a count by going through all the alignments and incrementing the count by how many times o is paired with s in the alignment and multiplying that by the above conditional alignment probabilities




For these short sentences the o, s count for any alignment is at most 1, and it will be handy for the calculations to note for each (o, s) the alignments where it occurs once1






la
ma
f l
the
1:1 2
1:3 4
1:–


2:1 2
2:–
2:3 4
ho
1:1 3
1:2 4
1:–


2:–
2:–
2:–
f lo
1:–
1:–
1:–


2:1 3
2:–
2:2 4



based on this we get the following expected counts







to read this table the (ho,la) entry has 1:1 3to indicate in first pair (O1, S1), the (ho,la) pairing occurs
2:–

in alignments A11 and A13, and the pairing never occurs in the alignments for the second pair






















2









cnt
la


ma


f l


the
4 ×
1
2 ×
1
2
×
1
4


4




4




ho
2 ×
1
2 ×
1


0


4










4






f lo
2 ×
1
0


2
×
1
4


4















and for these counts get new tr(o|s) by normalising by column sums




tr(o|s)




the




ho




f lo




ITERATION 2







la
ma
f l
1


1


1




















2


2


2


1


1


0












4


2












1


0
1














4


2















using new tr(o|s) value re-calculate for each a1n, num(a1n), and for each a2n, num(a2n):




num(a11)
num(a21)
num(a31)
num(a41)


1 1




1 1




1 1




1 1


























































2 4
1


2 2
2


2 4
1


2 2


2


=


=


=


=




8


8
8
8








































num(a12)
num(a22)
num(a32)
num(a42)


1 1




1 1




1 1




1 1


























































2 4
1


2 2
2


2 4
1


2 2


2


=


=


=


=




8


8


8


8













































then re-calculate the conditional probabilities P (a|O, S).



(a11|O1, S1)



1

6




(a21|O2, S2)



1

6




(a12|O1, S1)



1

3




(a22|O2, S2)



1

3




(a13|O1, S1)



1

6




(a23|O2, S2)



1

6




(a14|O1, S1)



1

3




(a24|O2, S2)



1

3



then re-calculate the expected counts of o, s combinations as shown in the table below (eg. the expected count for (the,la) is coming from a11, a12, a21, a22)




cnt






la






ma






f l
the


1
+
2
+


1
+
2




1
+
2
6




6
6
6
6








6




3






3






1
+
2




=






=






6
6
















6










6










6






=


















































































6




































ho


1
+
1






2
+
2






0
6
6




6
6










2








4


















=










=


























































6














6


















f lo


1
+
1








0




2
+
2
6
6










6
6




2






















4




=
























=












































6




























6







and for these counts get new tr(o|s) by normalising by column sums





















3









tr(o|s)




the




ho




f lo




ITERATION 3













la
ma
f l
3


3


3




















5


7


7


1


4


0












5


7












1


0
4














5


7















using new tr(o|s) value re-calculate for each a1n, num(a1n) and each a2n, num(a2n):




num(a1)
num(a1)
num(a1)
num(a1)
1
2
3
4


3 1


3 4


3 1


3 4












































5 5


5 7


7 5


7 7


num(a12)
num(a22)
num(a32)
num(a42)


3 1


3 4


3 1


3 4












































5 5


5 7


7 5


7 7





then re-calculate the conditional probabilities P (a|O, S).




P (a11|O1, S1) P (a12|O1, S1) P (a13|O1, S1) P (a14|O1, S1)

0.1512 0.4321 0.1080 0.3086




P (a21|O2, S2) P (a22|O2, S2) P (a23|O2, S2) P (a24|O2, S2)

0.1512 0.4321 0.1080 0.3086




then re-calculate the expected counts of o, s combinations




cnt
la
ma
f l
the
0.1512+
0.1080+
0.1080+


0.4321+
0.3086
0.3086


0.1512+
=
=


0.4321
0.4167
0.4167


= 1.167




ho
0.1512+
0.4321+
0


0.1080
0.3086




=
=




0.2593
0.7407


f lo
0.1512+
0
0.4321+


0.1080


0.3086


=


=


0.2593


0.7407



and for these counts get new tr(o|s) by normalising by column sums




tr(o|s)
la
ma
f l
the
0.6923
0.36
0.36
ho
0.1538
0.64
0
f lo
0.1538
0
0.64



Over the 3 iterations, tr(the|la), tr(ho|ma) and tr(f lo|f l) are steadily increasing.




If the calculations are carried on, after 10 iterations you have the following for the translation probabilities






4

















tr(o|s)
la
ma
f l
















the
0.982
0.096
0.096
















ho
0.009
0.904
0
















f lo
0.009
0
0.904








this is the history over the 10 iterations


























O|S AT EACH ITERATION


































OBS
SRC
0
1
2
3
4
5
6
7
8
9
10
THE
LA
0.33
0.5
0.6
0.69
0.77
0.84
0.89
0.93
0.95
0.97
0.98
HOUSE
LA
0.33
0.25
0.2
0.15
0.11
0.081
0.056
0.037
0.024
0.015
0.009
flOWER
LA
0.33
0.25
0.2
0.15
0.11
0.081
0.056
0.037
0.024
0.015
0.009
THE
MAISON
0.33
0.5
0.43
0.36
0.3
0.24
0.2
0.16
0.14
0.11
0.096
HOUSE
MAISON
0.33
0.5
0.57
0.64
0.7
0.76
0.8
0.84
0.86
0.89
0.9
flOWER
MAISON
0.33
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0
THE
flEUR
0.33
0.5
0.43
0.36
0.3
0.24
0.2
0.16
0.14
0.11
0.096
HOUSE
flEUR
0.33
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0
flOWER
flEUR
0.33
0.5
0.57
0.64
0.7
0.76
0.8
0.84
0.86
0.89
0.9



In the end the tr(o|s) table converges to:




tr(o|s)
la
ma
f l
the
1
0
0
ho
0
1
0
f lo
0
0
1



































































































5