Probabilistic CKY Assignment

    Below we give the CKY chart for a parse of the 10-word sentence:

      The agency sees use of the codes as a way.

    The assignment is to assign probabilities to each of the edges used in the 5 parses the example sentence has using the probabilities in the Probabilistic CF grammar below. You do not have to assign probabilities to edges not used in any of the 5 parses. You will find it helpful to use the solution to the last assignment as a guide to make sure you are considering all possible ways of building each edge.

    What you need to hand in is a version of the chart below that has the Viterbi values associated with each edge in the chart used in one of the 5 parses. and your calculations. For example, a four word sentence chart might look like the chart below, using the grammar below:

        1
      the       		2
      agency       		3
      sees       		4
      codes
      0 dt, .5
      		np, .0025
      		  s, .0001
      1  
      		n, .01
      nbar, .01
      		    
      2  
      		  

      vbz, 1.0       		vp, .004
      2  
      		  
      		  
      n, .01
      nbar, .01

We first give the grammar the parser uses (in Chomsky Normal Form), as well as the lexicon.

    Probabalistic Context Free Grammar

    pp -> p np, 1.0
vpg -> vbg np, 1.0
X2 -> X1 pp, 1.0
vp -> vbz np, .4
vp -> X1 pp, .5
vp -> X2 pp, .1
ap -> rb a, 1.0
s -> np vp, 1.0
np -> dt nbar, .5
np -> X3 np, .1
np -> ap nbar, .05
np -> nbar pp, .2
np -> n n, .05
np -> vbg np, .05
X3 -> np cc, 1.0
X1 -> vbz np, 1.0
nbar -> ap nbar, .1
nbar -> nbar pp, .3
nbar -> n n, .5
nbar -> vbg np, ..05

    Lexicon

    a: dt, .5
and: cc, 1.0
use: n,.01; np,01; nbar.01
codes: n,.01; np,01; nbar,.01
sees: vbz,1.0
of: p,.5
agency: n,.01; np,.01; nbar,.01
rapidly: rb,1.0
handling: vbg,.5
labor: n,.01; np,.01, nbar
as: p,.5
costs: n,.01; np,.01 nbar,.01
controlling: vbg,.5
way: n,.01; np,.01; nbar,.01
growing: a,.5 ap,.5
the: dt,.5
widespread: a,5, ap,5

    k
      1
    the     		2
    agency     		3
    sees     		4
    use     		5
    of     		6
    the     		7
    codes     		8
    as     		9
    a     		10
    way
    0 dt
    		np
    		s
    		s
    		s
    1   np
    nbar
    n
    		s
    		s
    		s
    2     vbz
    		vp
    X1
    		vp
    X2
    X1
    		vp
    X2
    X1
    3       np
    nbar
    n
    		np
    nbar
    		np
    nbar
    4         p
    		pp
    		pp
    5           dt
    		np
    		np
    6             np
    nbar
    n
    		np
    nbar
    7               p
    		pp
    8                 dt
    		np
    9                   np
    nbar
    n