2020 Ling/CS 581 Final: CKY Portion

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

the secret agency head sees codes as 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 or in last year's final. Probabilities, the lexicon, and even some rules have changed.

Probabilistic Context Free Grammar

S -> NP VP, 1.0 
PP -> P NP, 1.0 
X2 -> X1 PP, 1.0 
VP -> VBZ NP, 0.4 
VP -> X1 PP, 0.5 
VP -> X2 PP, 0.1 
AP -> RB A, 1.0 
NP -> DT NBAR, 0.5 
NP -> X3 NP, 0.1 
NP -> AP NBAR, 0.05 
NP -> NBAR PP, 0.2 
NP -> N N, 0.05 
NP -> VBG NP, 0.05 
X3 -> NP CC, 1.0 
X1 -> VBZ NP, 1.0 
NBAR -> AP NBAR, 0.1 
NBAR -> NBAR PP, 0.3 
NBAR -> NBAR N, 0.5 
NBAR -> VBG NP, 0.05

Lexicon

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


a: DT, 0.5; 
and: CC, 1.0; 
use: N, 0.01; NP, 0.01; NBAR, 0.01; 
head: N, 0.01; NP, 0.01; NBAR, 0.01; 
codes: N, 0.01; NP, 0.01; NBAR, 0.01; 
security: N, 0.01; NP, 0.01; NBAR, 0.01; 
sees: VBZ, 0.1; 
of: P, 0.5; 
agency: N, 0.01; NP, 0.01; NBAR, 0.01; 
rapidly: RB, 1.0; 
handling: VBG, 0.5; 
costs: N, 0.01; NP, 0.01; NBAR, 0.01; 
as: P, 0.5; 
controlling: VBG, 0.5; 
keys: N, 0.01; NP, 0.01; NBAR, 0.01; 
the: DT, 0.5; 
growing: AP, 0.3; A, 0.3; 
secret: AP, 0.3; A, 0.3; 
widespread: AP, 0.3; A, 0.3;

Tasks

Your have three tasks.

First, list the daughter records for all the edges used in one of the four parses. 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 1 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. Make your answers neat and readable. Do not use pencil.
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 four parses. If you do not use the Viterbi algorithm, with the proper maxes taken at the proper nodes, you will not get credit for this problem. Note also that if you compute probabilities for trees instead of edges, you are not using the algorithm.
Third, draw the parse tree for all four parses. Note that you will only have computed the probability for one of these trees, the Viterbi parse. Indicate which one that is. Reminder: the way you'll find out how these 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	head 4	sees 5	codes 6	as 7	security 8
0	DT		NP	NP		S		S
1		AP A	NP NBAR	NP NBAR		S		S
2			N NP NBAR	NP NBAR		S		S
3				N NP NBAR		S		S
4					VBZ	VP X1		VP X1 X2
5						N NP NBAR		NP NBAR
6							P	PP
7								N NP NBAR