mim / ling83800hw4

Homework 4 for LING 83800 at the CUNY Graduate Center

LING83800: Homework "4"

In this assignment, you will build a bigram hidden Markov model tagger.

To do this you will:

1. write a script that extracts the sufficient statistics (emission and transition probabilities) from labeled data, and
2. write a script that implements greedy decoding.

Part 1: tagger training

In the first part of this assignment, you will compute sufficient statistics for your HMM tagger using the tagged and tokenized data in data/train.tag.

What to do

Write a script called train_tagger.py that reads this data, sentence by sentence, and computes:

• the bigram transition probabilities where is the tag at time i, and
• the emission probabilities where is the token at time i.

Pad the transition sequence with a special <s> start symbol. Also, apply add-one smoothing to the bigram transition probabilities so that no transition has zero probability. Then, write these probabilities out to a file or files.

What to turn in

• Your trainer script.

Hints

• Do not read the whole file in at once. Process it sentence by sentence.
• You may choose to store the emission and transition probabilities in the same file or in separate files; it's up to you.
• For your output files, use familiar formats like JSON, YAML, TSV, NPZ, etc.; don't invent your own format.

Stretch goals

• Instead of hard-coding the paths to the training data and the output files, pass these in as command-line arguments.
• Instead of using raw probabilities, use negative log probabilities. Then in the latter parts of the assignment, use min instead of max (because smaller negative log probabilities correspond to larger real-valued probabilities) and + instead of * (because addition in the log domain corresponds to multiplication in the real domain).

Part 2: decoding

In the second half of this assignment, you will use a greedy decoding algorithm to tag data.

What to do

Write a script called decode_tagger.py that reads in the sufficient statistics file(s), and then, for each sentence in data/test.tag,

1. computes the most likely tag for each slot, assuming the previous slot is correct, and
2. outputs the tagged sequence in the same two-column format used for tagged data.

What to turn in

• Your decoder script, and
• predicted tags for data/test.tag using this method.

Hints

• Once again, do not read the whole file to be tagged all in at once. Process it sentence by sentence.
• If a word is not present in the emissions table, you can assume that it is equally likely to have been generated by every tag. You can approximate this by simply ignoring the emissions probability for that row in the forward probability table and only using the transition probability.

Stretch goals

• Instead of hard-coding the paths to the sufficient statistics files and the data to be tagged, pass these in as command-line arguments.
• Continuing the stretch goal from part 1 (see above), perform your computations in the negative log probability domain.
• Evaluate your performance on data/test.tag by computing token accuracy (i.e., the percentage of tokens correctly tagged).
• Experiment with case-folding---does it help?