Ling/CSE 472: Assignment 3: Part-of-Speech Tagging and Parsing

Due May 1st, by 6:00pm

Part 1: Part-of-Speech Tagging

This assignment explores the relationship between the tagsets chosen in a part-of-speech tagging task, and the accuracy of taggers trained with those tagsets. You will need to turn in one python script and one file with answers to some questions, which should be submitted via CollectIt.

You will need the following three python scripts to complete the assignment:

Download them and save them to a directory in your Patas account. These python scripts depend on the NLTK library, which is installed on Patas. They will not work on other machines, even if they have python installed, unless NLTK is installed as well.

In alltags.py, a tagger is trained from Penn Treebank data using all 46 of the Penn Treebank tags. It is a bigram tagger; for unseen bigrams it backs off to a unigram tagger; by default it tags unseen words NN.

In the other two files, a mapping has been defined which is used to convert the tags in the training and test data. For instance, using the mapping

the corpus is converted so that every word tagged with 'NN', 'NNP' or 'NNPS' becomes tagged with 'NN'.

In the file 36tags.py, the mapping collapses the full 46 tags to 36 tags; in the file 23tags.py, the 46 tags are collapsed to just 23 tags.

When you run one of these files in python, for instance:

It will train the tagger, and print out its accuracy against the test data.

For this assignment, turn in two files. The first file should contain the answers to the following questions:

• Is the accuracy of the tagger in 36tags.py higher or lower than that of the tagger in alltags.py?
• Explain why you think that is.
• Is the accuracy of the tagger in 23tags.py higher or lower than that of the tagger in alltags.py?
• Explain why you think that is.
• Explain why you think the mapping you created (see below) led to a tagger with a higher accuracy.
• What generalizations, if any, can you make about the relationship between the size of a tagset and the accuracy of a tagger using that tagset?

The second file should be a python script containing a mapping which leads to a tagger whose accuracy is higher than that of any of the other three. Just copy either 36tags.py or 23tags.py and change the mapping however you like, except there must be at least two different tags in the resulting tagset.

Part 2: Parsing

For this assignment, you will be using the LKB grammar development environment. The LKB is installed on the machines in the Treehouse. It is open source software, available for linux and windows. Installation instructions here.

For this assignment, you will be asked to turn in typed answers. Here is a template answer file into which you can type your answers for Part 2.

Be sure to get an early start so that you have time to ask questions on GoPost.

[These directions assume you are working on the Treehouse machines, which are linux machines.]

Start the LKB, and load the grammar

• Log into one of the Treehouse machines, and start emacs by typing emacs & in a terminal window.
• In emacs, start the LKB by typing M-x lkb (where M is the esc or alt key).
• Download the grammar for this assignment, by saving the file linked here: grammar1.tgz. (Here is a .zip version for folks working on Windows: grammar1.zip.)
• Move the downloaded file to your home directory or somewhere else suitable.
• Unpack the tar archive by executing this command in the directory containing the file you downloaded:

tar xzf grammar1.tgz

• Load the grammar by selecting Load > Complete Grammar in the Lkb Top window. In the dialogue that pops up, navigate to "grammar1" and select "script". Then click the "open" button.

(Note: If the dialogue box isn't doing what you expect, try typing the complete path to the "script" file e.g., /home/ebender/grammar1/script into the "selection" box and then clicking "open".)

A. Charts and trees, edges and nodes

• Familiarize yourself with the contents of rules.tdl and lexicon.tdl. These define the phrase structure rules and lexicon of a baby CFG. Note the funny syntax (rule forms) and make sure you understand how it corresponds to `ordinary' CFG syntax:

  rule1 := A & [ ARGS < B , C > ].

  Is equivalent to:

  A -> B C  (rule1)

  Where "rule1" is just a name for the rule. (The reason for the funny syntax is that the LKB expects typed feature structure grammars, not CFGs. This is a way of coding up a CFG in TFS format, developed by Stephan Oepen. If you're curious about how it works, take a look in types.tdl.)
• Parse Kim snores (In the Lkb Top window, select "Parse > Parse input ...") The LKB should return a tree. You can also view the parse chart by selecting "Parse > Show parse chart" from the Lkb Top window. Compare the tree and the parse chart. In the chart, you can also get small trees for each edge (from the pop-up menu that comes up when you click on an edge). Look at the trees for each edge, and convince yourself that they fit together to form the complete tree.

Note: The edges should have meaningful labels on them (e.g., S, VP). If you see "NIL" instead, it means you're running the alternate user interface called the LUI. To turn it off, in the *common-lisp* buffer of emacs, type (lui-shutdown).

• Parse Kim snores in Oslo, and examine the parse chart. Why are there more edges in the chart than nodes in the tree? Are the `extra' edges warranted? That is, do they indicate a problem with the grammar? Why or why not?
• Parse Kim adores snow, and examine the parse chart. Why are there more edges in the chart than nodes in the tree? Are the `extra' edges warranted? Why or why not?
• Parse Kim adores snow in Oslo. The LKB returns two trees (the sentence is ambiguous), with a total of 18 non-terminal nodes between them. The chart shows only 15 edges. Why?

B. Start symbols

• Parse In Oslo, Kim adores snow, and examine the chart. There are two edges with category S. Why doesn't the parser return either of them?
• Find three other strings made up of the vocabulary in the grammar (see lexicon.tdl) that the grammar won't accept.
• Now change the start symbol from just S to S or NP. You can do this by selecting "Options > Set options..." from the Lkb Top window, and then changing the value for *start-symbol* from (S) to (S NP). The LKB will ask you for a file to save the parameters in. Select globals.lsp, and say okay when it asks about overwriting the existing file. Alternatively, you can accomplish the same thing by editing the file globals.lsp. Change this:

  (defparameter *start-symbol* '(s))

  to this:

  (defparameter *start-symbol* '(s np))

  and reload the grammar.
• Show that the parser now accepts a string that it didn't before. (For your write up, state which string it is.)