Department of Computing

COMP348 Document Processing and the Semantic Web

Tutorial Week 8

Part of Speech Tagging

1. Suppose that the following probabilities have been estimated from a corpus:

   P(time|V) = 0.2	P(flies|N) = 0.3	P(D|P) = 0.6
   P(flies|V) = 0.4	P(arrow|N) = 0.3	P(N|P) = 0.4
   P(like|V) = 0.4	P(V|{}) = 0.2	P(V|N) = 0.7
   P(an|D) = 0.5	P(N|{}) = 0.8	P(P|N) = 0.2
   P(the|D) = 0.5	P(N|V) = 0.3	P(N|N) = 0.1
   P(like|P) = 1	P(D|V) = 0.4	P(N|D) = 1
   P(time|N) = 0.4	P(P|V) = 0.3

   1. With these probabilities, draw the associated Hidden Markov Model.
   2. Compute the probability of the following PoS tagging: time/N flies/V like/P an/D arrow/N

2. You have the following two sentences: consider the first to be from a tagged corpus and the second the output from the initialisation step of a tagger.

   Fruit/NN flies/NNS like/VBP the/DT oranges/NNS like/IN giraffes/NNS
   like/VBP the/DT leaves/NNS.
   
   Fruit/NN flies/VBZ like/IN the/DT oranges/NNS like/VBP giraffes/NNS
   like/IN the/DT leaves/NNS.
           

   Trace through the operation of the Brill tagger if the following rules were available:
1. VBP IN PREVTAG NNS (interpretation: Change VBP to IN when previous tag is NNS)
2. NN VP PREVTAG TO
3. VBZ NNS NEXTTAG VB
4. VBZ NNS NEXTTAG VBP
5. VBZ NNS PREV1OR2TAG IN
6. VBZ NNS NEXTWD of
7. IN VBP NEXTTAG DT
8. IN VBP PREVTAG NNS

Parsing

In the following exercises consider this grammar:

1. Write the trace of a top-down, left-right, depth-first parser for the sentence "I read the book in the park".
2. Write the trace of a shift-reduce parser that performs reduction whenever it is possible for the same sentence "I read the book in the park".
3. Populate the chart table of a chart parser that uses the bottom-up strategy for the same sentence "I read the book in the park".