In this assignment, you will build a bigram hidden Markov model tagger.
To do this you will:
- write a script that extracts the sufficient statistics (emission and transition probabilities) from labeled data, and
- write a script that implements greedy decoding.
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.
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.
- Your trainer script.
- 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.
- 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 ofmax
(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).
In the second half of this assignment, you will use a greedy decoding algorithm to tag data.
Write a script called decode_tagger.py
that reads in the sufficient
statistics file(s), and then, for each sentence in data/test.tag,
- computes the most likely tag for each slot, assuming the previous slot is correct, and
- outputs the tagged sequence in the same two-column format used for tagged data.
- Your decoder script, and
- predicted tags for data/test.tag using this method.
- 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.
- 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?