1. The Basics: Probability

We specialize in petbirds including but not limited to dogs , cats , and horses .

You are building a bigram language model p(w_i|w_i-1) using maximum likelihood estimation. You do not add any special symbols/words to the beginning and end of the data (i.e., you use separate unigram distribution for the first position in any given data).

• What is the (raw) probability of  p(cats|,)? ________________________________

• What is the definition of the training data probability (using the bigram approximation)?

2. Tagging

• Describe three different approaches to tagging. Include formulas if/where appropriate.

3. Shift-Reduce Parsing

• Decide which of the following strings belong to the language defined by the grammar G:

• Create the shift-reduce parse tables for this grammar.

• Show how the shift-reduce parser parses the string  abbbrc:

4. Statistical Parsing

• What is a Probabilistic CFG? Use five sentences at most.

Now suppose the following "treebank" data, where the pair of symbols ( ... )XX denotes a (sub)tree rooted in a nonterminal XX.

Sentence 1:

(((the)DET (dog)N)NP ((saw)V (((the)DET (cat)N)NP ((with)PREP (((a)DET (telescope)N)NP ((with)PREP ((a)DET (mirror)N)NP)PP)NP)PP)M2)VP)S

Sentence 2:

(((the)DET (dog)N)NP ((saw)V (((the)DET (cat)N)NP ((with)PREP ((a)DET (mirror)N)NP)PP )NP)VP)S
 

• Draw the usual parse trees, with terminal symbols (words) as leaves, and other nodes labeled by nonterminals:

           the dog saw the cat with a telescope with a mirror
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                 the dog saw the cat with a mirror
 
 

• Write down the (general, non-lexicalized) CFG grammar G as extracted from this training data.

• Now draw the lexicalized parse tree for the second sentence, assuming that  whenever there is a choice of heads in any given subtree, chose (in the following precedence order): VP, V, PREP, N, NP.

                 the dog saw the cat with a mirror

OK. Now you have everything to answer these "numerical" questions:
 

• Estimate p(NP ->  NP PP) = _______________

• Estimate p(NP -> PREP N) = _______________

• Estimate p(VP ->  V NP) = _______________

• Estimate p(VP -> V M2) = _______________

Suppose we stick to the usual three independence asumptions and define a probability of a parse tree s (of a sentence W) as a simple product of p(<rule>) over all rules used in the course of generation of the sentence W.
 
 
 
 

Describe the main idea of the algorithm to compute:

• (a) the best parse given a sentence and a model. Use five sentences at most.

• (b) the probability of a string given the model. Use five sentences at most.

• What is then the probablity of the following parse tree, using the estimated nonlexicalized PCFG:
p(  (((the)DET (dog)N)NP  ((saw)V  ((the)DET (cat)N)NP)VP)S ) = ______________

• What is the probability of the training data parse of sentence 2?
p(s|sentence₂) = _____________

• What is the probability of the string "the dog saw the cat with a mirror"?
p(sentence₂) = _____________

• Now a lexicalized grammar question. What is the (raw) probability estimate of the lexicalized rule p(PP(with) -> PREP(with) NP(mirror))? [Imagine you generate the lexicalized rules, too, under the same independence assumptions; however, to answer this question, there is no need to generate them all, of course. However, do not forget to look at both training sentences!]
p(PP(with) -> PREP(with) NP(mirror)) = __________________

Now check if you have filled in your name. Also, please carefully check your answers and hand the exam in.