LING571

Quiz #4

12/6/05

(due 12/8/05 in class)

 

 

                                                                                                        Your name: 

                                                                                    

 

  1. (30 points)  The training data contain only two sentences:

 

Assuming

(1)   there are no NULL Eng word (so there are four alignments for Sentence 1, and one alignment for Sentence 2)

(2)   the uniform distribution at the beginning, which means

                                   t(x|b)=1/2, t(y|b)=1/2

                                   t(x|c)=1/2, t(y|c)=1/2

 

Calculate t(f | e)  in Model 1. Show the results in the first two iterations using both methods:

     (1) the one with alignment prob, and (2) the one without.

 

 

%%%%%%%%%%%%%%%%% Method 1: with alignment prob.

Alignment for the 1st sentence:

 

A1:   b – x     

          c -- y   

         

A2 :   b – y

          c – x

 

A3:    b – x y

          C

 

A4:    b

          C – x y           

 

Alignment for the 2nd sentence:

A5     b – y

 

 

 

 

%%%%%%

1st iteration:

   Alignment prob:  before and after normalization:

       P(A1 | E1,F1) = P(A2|E2,F2) = P(A3|E3,F3) = P(A4|E4,F4) = ½ * ½ = ¼

       P(A5 | E2,F2) = 1

 

  Collect fractional counts for Ct(f,e):

       Ct(x,b) = ¼ + ¼ = ½

       Ct(y,b) = ¼ + ¼ + 1 = 3/2

       Ct(x,c) = ¼ + ¼ = ½

       Ct(y,c) = ¼ + ¼ = ½

 

  Normalize to get t(f|e):

       t(x|b)=1/2 / 2 = ¼

       t(y|b)=3/4

       t(x|c)=1/2

       t(y|c)=1/2

 

 

%%%%%

  2nd iteration:

 

  Alignment prob, before normalization:

       P(A1|E1,F1)=1/4*1/2=1/8

       P(A2|E1,F1)=3/4*1/2=3/8

       P(A3|E1,F1)=1/4*3/4=3/16

       P(A4|E1,F1)=1/2*1/2=1/4

 

       P(A5|E2,F2)=3/4

  

   Alignment prob, after normalization:

       P(A1|E1,F1)=1/8 * 16/15 = 2/15

       P(A2|E1,F1)=3/8 * 16/15 = 6/15

       P(A3|E1,F1)=3/16 * 16/15 = 3/15

       P(A4|E1,F1)=1/4 * 16/15 = 4/15

 

       P(A5|E2,F2) = 1

 

 

Collect fractional counts for (f,e):

     Ct(x,b) = 2/15 + 3/15 = 1/3

     Ct(y,b) = 6/15 + 3/15 + 1 = 8/5

     Ct(x,c) = 6/15 + 4/15 = 2/3

     Ct(y,c) = 2/15 + 4/15 = 2/5

 

 

Normalize to get t(f|3):

    t(x|b) = 1/3 / (1/3 + 8/5) = 5/29

    t(y|b) = 24/29

    t(x|c) = 2/3 / (2/3+2/5) = 5/8

    t(y|c) = 3/8

 

 

 

 

 

%%%%%%%%%%%%%%%%% Method 2

1st iteration:

   Ct(x,b)= t(x|b)/(t(x|b)+t(x|c))=1/2

   Ct(y,b)= t(y|b)/(t(y|b)+t(y|c)) + 1 = 3/2

   Ct(x,c)=t(x|c)/(t(x|b)+t(x|c))=1/2

   Ct(y,c)=t(y|c)/(t(y|b)+t(y|c))=1/2

 

   t(x|b)=1/2 / 2 = ¼

   t(y|b)=3/4

   t(x|c)=1/2

   t(y|c)=1/2

 

 

2nd iteration:

   Ct(x,b)= t(x|b)/(t(x|b)+t(x|c))=1/4 / (1/4+1/2) = 1/3

   Ct(y,b)= t(y|b)/(t(y|b)+t(y|c)) + 1 = ¾ / (3/4+1/2) + 1 = 8/5

   Ct(x,c)=t(x|c)/(t(x|b)+t(x|c))=1/2 / (1/4 + ½) = 2/3

   Ct(y,c)=t(y|c)/(t(y|b)+t(y|c))=1/2 / (3/4+1/2) = 2/5

 

   t(x|b)=1/3 / (1/3+8/5) = 5/29

   t(y|b)=24/29

   t(x|c)=5/8

   t(y|c)=3/8