Homework 8

1. This first exercise provides an opportunity to make sure you understand the CKY (also known as CYK) recognition algorithm. I'm providing an implementation of the algorithm as a way for you to check whether or not you're doing it correctly. This means there is no excuse for turning in incorrect answers! (Feel free to do your own implementation if you prefer the extra programming experience.) Note, that if you just copy the answers given by the program, you won't know how to do it yourself, which could conceivably hurt you if we include a question about this on the final exam...
   • To run my implementation of the algorithm, download my implementation of the CKY parsing algorithm by anonymous ftp:

       % ftp umiacs.umd.edu        <== Get file by anonymous ftp
         Name (umiacs.umd.edu:logname):  anonymous
         Password: enter your e-mail address
         ftp> cd pub/resnik/ling645
         ftp> binary 
         ftp> get cky.tar.gz 
         ftp> quit
       
       % gunzip cky.tar.gz         <== Uncompress
       & tar xvf cky.tar           <== Extract the files
       % rm cky.tar                <== Delete to conserve space
       % cd cky                    <== Go into the code directory
       % gcc -o cky cky.c          <== Compile the program (ignore warnings)
     

   • Look at the comment at the top of cky.c for documentation on how to run the program and what the format of the grammar file is.

   • Take a look at grammar1.txt to see a sample grammar.

   • Run cky grammar1.txt and give it the input baaba. Make sure you understand why the program outputs what it does. You can run cky grammar1.txt -v for a more verbose description of the steps taken as the algorithm runs.

   • (a) To turn in: Work through the CKY recognition algorithm for the input ababab, turning in (i) the V[i,j] matrix and (ii) the chart showing arcs covering spans of the input string, in the same format as we used on the whiteboard in class.

   • (b) To turn in: Suppose that, for use in a speech understanding system, we want to make the parser incremental; that is, we want to modify the CKY algorithm so that as each new input symbol comes in, we build all the constituents we can build up to that point. (For example, when processing abab, we want to have built all the constituents covering the initial ab before we have even looked at the second a.) How would the algorithm change? Give a revised algorithm and describe its behavior using grammar1.txt with the example input abab.

     Note that you don't have to implement an algorithm, just show it on paper. Since we're not working with probabilities here, I recommend you start with the algorithm in the class handout, not the probabilistic CYK algorithm from the book.

2. Using the PCFG in Figure 12.1, show in detail how to compute the probability for the sentence the flights include a book.

3. Add the rules Noun --> books and Verb --> books to the grammar in Figure 12.1. Assuming this revised grammar, is the sentence TWA books flights locally ambiguous, globally ambiguous, both, or neither? Explain clearly.

4. Jurafsky and Martin, 14.6

5. Jurafsky and Martin, 14.8

6. Optional. For those interested in exploring probabilistic CFGs a bit further, use anonymous ftp to umiacs.umd.edu to download pub/resnik/ling645/pcfg.tar.gz, uncompress it, etc. This is an implementation of PCFG training written by Mark Johnson of Brown University, kindly made available for research purposes. Read the README file, run the toy examples for yourself, and note how, even though the grammar allows multiple word orders for VPs, the probabilities for the different rules depend on whether you train on sentences with English word order or with German word order.

   Some other things to try:

   • Try creating a grammar file containing the grammar from Figure 12.1, writing a set of training sentences, and then training up the probabilities.

   • Go back to the end of Assignment 4b and turn example1.train into a file with one sentence per line (by adding a newline after each period or question mark). Create a grammar file for the following grammar.

        
          S    -> NP VP . | Who VP ?
          NP   -> DET N | DET ADJ N | NP PP | all DET N | some of DET N
          VP   -> VPT | VPI | VP PP
          VPT  -> VT NP
          VPI  -> VI
          PP   -> P NP
      
          DET  -> the | those | these
          N    -> men | women | children | cookies | fences | songs | guitars
          VI   -> slept | sang | cried | laughed | jumped | cooked | played
          VT   -> saw | liked | tickled | cooked | played | played with |
                ignored | sang | sang to
          ADJ  -> tall | short | nice | happy
          P    -> with | near | next to | for 
     

     Try training up rule probabilities for this grammar and see what you get.