General guidelines

Basic instructions are the same as in MP 1. To summarize:

The mp5 code reads data from two files. Your tagging function will be given the training data with tags and the test data without tags. Your tagger should use the training data to to estimate the probabilities it requires, and then use this model to infer tags for the test input. The main mp5 function will compare these against the correct tags and report your accuracy.

The data is divided into sentences. Your tagger should process each sentence independently.

You will need to write two tagging functions:

• Baseline
• Viterbi: HMM tagger

The Baseline tagger considers each word independently, ignoring previous words and tags. For each word w, it counts how many times w occurs with each tag in the training data. When processing the test data, it consistently gives w the tag that was seen most often.

The Viterbi tagger should implement the HMM trellis (Viterbi) decoding algoirthm as seen in lecture or Jurafsky and Martin. That is, the probability of each tag depends only on the previous tag, and the probability of each word depends only on the corresponding tag. This model will need to estimate three sets of probabilities:

• Initial probabilities (How often does each tag occur at the start of a sentence?)
• Transition probabilities (How often does tag $t_b$ follow tag $t_a$?)
• Emission probabilities (How often does tag t yield word w?)

It's helpful to think of your processing in five steps:

• Count occurrences of tags, tag pairs, tag/word pairs.
• Compute smoothed probabilities
• Take the log of each probability
• Construct the trellis. Notice that for each tag/time pair, you must store not only the probability of the best path but also a pointer to the previous tag/time pair in that path.
• Return the best path through the trellis.

You should test your code on the all three datasets. For each dataset, you should report performance of both Baseline and Viterbi on

• the training data (i.e. submit the training data for both input files), and
• the development data.

Performance on the training dataset should be high, because it's cheating. But this is a good way to test for code bugs.

Your report should briefly describe your implemented solution but primarily concentrate on

• How you handled non-obvious details (esp. smoothing and associated parameters), and
• Test results

Be sure to explain why you made the choices that you did. This may include selected test results from configurations that worked less well, to help motivate your final choices.

For this MP, the algorithms are fixed. Do not change them. Your main opportunity for extra credit involves optimizing the smoothing methods to improve performance. Notice that you may need to use different smoothing methods for different groups of probabilities. (See e.g. the lecture 21 summary for some ideas.)

You may also wish to do more extensive experimentation. For example,

• Run the tagger on (slightly) mismatched training and test data. E.g. how well can you get it to perform if trained on Brown but tested on MASC?
• Separately report performance on test sentences that did/didn't contain words not seen in the training data.

You could also try automatically tuning key smoothing parameters, using a loop that systematically tries a variety of settings.

You could try using the form of an unseen word (e.g. its length, its last few characters) to make a better guess at its part of speech.

If you experiment with several configurations, you may wish to add extra flag options to the main mp5 function. If you do this:

• Submit your revised mp5.py
• Make sure that the provided version of mp5.py will run your best configuration, i.e. the one you'd like the autograder to use.