$30
CS4LL5-Assignment 3 Solved
This is a worked example showing convergence of EM training with IBM model 1.
The pairs are
s1 la maisons2 la fleur o1 the houseo2 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 initialised to 13
tr(o|s) la ma fl
the 31 13 13
ho 31 13 13
flo 31 13 13
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
(1)
and in the derivationterms cancelled. In the corresponding derivation disallowing
s alignments to NULL, there will instead be a cancellation ofterms, and exactly the same
s 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. for each possible a determine num(a) (ie. Qj[p(oj|sa(j))])
2. sum these to give the denominator Pa num(a) and then take ratios
Armed with these conditional probabilities can then compute expected counts of o,s combinations across the corpus, and from these recalculate tr(o|s) probabilities.
ITERATION 1
considering the first pair, for each a[1]n calculate num(a1n):
num(a11)
num(a12)
num(a13)
num(a14)
= 13 31
= 19
ditto
ditto
ditto
sim. for each a[2]n calculate num(a2n). At this stage, these all work out as 91.
from these to calculate the conditional probabilities ), need to sum the num(an) by summing across the table and use it as denominator ie.
P(a11|o1,s1)
P(a12|o1,s1)
P(a13|o1,s1)
P(a14|o1,s1)
= 4×1/19/9
= 41
ditto
ditto
ditto
P(a21|o2,s2)
P(a22|o2,s2)
P(a23|o2,s2)
P(a24|o2,s2)
ditto
ditto
ditto
= 41
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 fl
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:–
flo 1:– 1:– 1:–
2:1 3 2:– 2:2 4
based on this we get the following expected counts
cnt
la
ma
fl
the
0
0 2
and for these counts get new tr(o|s) by normalising by column sums
tr(o|s) la ma fl
the 21 12 12
ho 41 12 0
flo 41 0 12
ITERATION 2
using new tr(o|s) value re-calculate for each a1n, num(a1n), and for each a2n, num(a2n):
num(a11) num(a12) num(a13) num(a14)
1 1 1 1 1 1 1 1
2 4 2 2 2 4 2 2
= 81 = 82 = 18 = 82
num(a21) num(a22) num(a23) num(a24)
1 1 1 1 1 1 1 1
2 4 2 2 2 4 2 2
= 81 = 82 = 18 = 82
then re-calculate the conditional probabilities P(a|o,s).
P(a11|o1,s1) P(a12|o1,s1) P(a31|o1,s1) P(a14|o1,s1)
1 1 1 1
6 3 6 3
P(a21|o2,s2) P(a22|o2,s2) P(a32|o2,s2) P(a24|o2,s2)
1 1 1 1
6 3 6 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 fl
the 61 + 26 + 16 + 62 61 + 26
16 + 62 = 36 = 63
= 66
ho 16 + 61 26 + 62 0
= 62 = 46
flo 61 + 61 0 62 + 26
= 62 = 64
and for these counts get new tr(o|s) by normalising by column sums
tr(o|s) la ma fl
the 53 37 37
ho 0
flo
ITERATION 3
using new tr(o|s) value re-calculate for each a1n, num(a1n) and each a2n, num(a2n):
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
fl
the
0.1512+ 0.4321+
0.1512+ 0.4321
= 1.167
0.1080+
0.3086
=
0.4167
0.1080+
0.3086
=
0.4167
ho
0.1512+
0.1080
=
0.2593
0.4321+
0.3086
=
0.7407
0
flo
0.1512+
0.1080
=
0.2593
0
0.4321+
0.3086
=
0.7407
and for these counts get new tr(o|s) by normalising by column sums
tr(o|s)
la
ma
fl
the
0.6923
0.36
0.36
ho
0.1538
0.64
0
flo
0.1538
0
0.64
Over the 3 iterations, tr(the|la), tr(ho|ma) and tr(flo|fl) are steadily increasing.
If the calculations are carried on, after 10 iterations you have the following for the translation probabilities
tr(o|s)
la
ma
fl
the
0.982
0.096
0.096
ho
0.009
0.904
0
flo
this is the history over the 10 iterations
0.009
0
0.904
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
In the end the tr(o|s) table converges to:
0.7
0.76 0.8
0.84
0.86
0.89
0.9
tr(o|s)
la
ma fl
the
1
0 0
ho
0
1 0
flo
0
0 1
[1] 1to read this table the (ho,la) entry has 1:1 3 to indicate in first pair (o ), the (ho,la) pairing occurs
[2] :–
in alignmentsand, and the pairing never occurs in the alignments for the second pair
