2017 Ling 581 Final: CKY Portion

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

The secret agency codes have keys with high security.

This sentence has four parses.

We first give the grammar the parser uses (in Chomsky Normal Form), as well as the lexicon. The grammar includes probabilities. Careful. This grammar is not the same as the one used in the homework problem. Probabilities, the lexicon, and even some rules have changed.

Probabilistic Context Free Grammar

pp -> p 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, .4
np -> X3 np, .1
np -> ap nbar, .05
np -> nbar pp, .2
np -> nbar nbar, .1
np -> vbg np, .05
X3 -> np cc, 1.0
X1 -> vbz np, 1.0
nbar -> ap nbar, .1
nbar -> nbar pp, .3
nbar -> nbar nbar, .5
nbar -> vbg np, ..05

Lexicon

Some words you don't need have been left out so that not all the lexicon probs sum to 1.

a: dt, .33
and: cc, 1.0
use: n, .01; np, 01; nbar, .01
codes: n, .01; np, .01; nbar, .01
sees: vbz, 0.25
uses: vbz, 0.25; n, .01; np, .01, nbar, .01
keys: vbz, 0.25; n, .01; np, .01, nbar, .01
have: vbz, 0.25
security: n, .01; np, .01, nbar, .01
of: p, .33
with: p, .33
agency: n, .01; np, .01; nbar, .01
rapidly: rb, 1.0
handling: vbg, 0.5
as: p, 0.33
costs: n, .01; np, .01 nbar, .01
controlling: vbg, .5
way: n, .01; np, .01; nbar, .01
growing: a, 0.33 ap, 0.33
the: dt, 0.33
every: dt, 0.33
widespread: a,.33; ap,.33
secret: a,.33; ap,.33
high: a,.33; ap,.33

Tasks

Your have three tasks.

First, list the daughter records for all the edges contributing to one of the two parses the sentence has. Two cautions: First, you will actually lose points for listing edges that don't contribute to a parse of the sentence, so don't just list all edges. Second, remember daughter records come in one of two forms:
1. Lexical daughter record. For example.
2. Rule daughter record. For example,
  ATTN: You must list the rule daughter records in a table that has exactly the same form as the chart table below. A daughter record like (ap 2 nbar) must be directly underneath the edge it is the record for: (ap 2 nbar) has no meaning on its own We need to know the span (the start and end indices of the edge we are building) and the category of that edge; that's what putting the record in right cell in the table under the right edge tells me.
Second, find the Viterbi parse and show your computations for computing the probability of that Viterbi parse. In showing your computations, use the format used in giving the model answer for the probability parsing assignment. Note that in showing these computations you need only compute Viterbi values for edges that contribute to one of the two parses. Reminder: the way you'll find out how these two parse trees differ is by finding ambiguous edges. Those ambiguous edges do not have be in the last column.

Chart

	the 1	secret 2	agency 3	codes 4	have 5	keys 6	with 7	high 8	security 9
0	dt		np	np		s			s
1		a ap	np nbar	np nbar		s			s
2			np nbar n	np nbar		s			s
3				np nbar n		s			s
4					vbz	vp X1			vp X2 X1
5						np vbz nbar n			np nbar
6							p		pp
7								a ap	np nbar
8									np nbar n