A7.ps

1

\I hate it when goes like that EOS" We solve this problem using the trigram model. Assume that the rst blank is referred to as b1 and the se ond is b2 . We wish to maximise over all x and y P r(b1 = x; b2 = y j I hate it when b1 goes b2 like that EOS ). This is maximised by

PPr

x goes y like that EOS ) Pr(I hate it when m goes n like that EOS )

(I hate it when

(m;n)

In the term above, the sin e the denominator is a onstant term not dependent on x and y, we an maximise it by just maximising the numerator. P r(I hate it when x goes y like that EOS ) = P r(it j I hate)  P r(when j hate it)  P r(x j it when)  P r(goes j when x) P r(y j x goes)  P r(like j goes y)  P r(that j y like)  P r(EOS j like that):

Sin e the terms not ontaining referen es to x or y are onstant, we are left with the task of maximising P r(xjit when)P r(goesjwhen x)P r(yjx goes)P r(likejgoes y)P r(thatjy like) 2a

P r(k0 ; : : : ; kn ; kn+1 ) =

i P r(k0 ; : : : ; kn+1 ; sn = i) \sin e we ould end up in any state, i" = j i P r(k0 ; : : : ; kn+1 ; sn = i; sn+1 = j ) \sin e the pre eeding state before i ould be any j " = j i P r(kn+1 ; sn+1 = j jk0 ; : : : ; kn ; sn = i)P r(k0 ; : : : ; kn ; sn = i) \using onditional probability" = j i (i; n)P r(kn+1 ; sn+1 = j jk0 ; : : : ; kn ; sn = i) \de nition of " = j i ( P(ri;(kn)P rjs(sn+1==j;jkjk0; ;: :: :: :; ;kkn; ;ssn==i)i) ) n+1 n+1 0 n n \ hain rule for onditional probability"

1

= j i (i; n)P r(sn+1 = j jsn = i)P r(kn+1 jsn+1 = j ) \sin e observation is dependent only on urrent state, and urrent state is dependent only on earlier state" = j i (i; n)p(i; j )b(j; k) \de nition of p and b" = j (j; n + 1) \de nition of " 2b (i; 0) = P r(k0 ; s0 = i) = P r(k0 js0 = i)P r(s0 = i) = b(k0 ; i)(i)

Found an error? Please onta t kswadi s.prin eton.edu

2