Computer Science 248/448

Homework

Fall 2011

Homework 6

Due Tue Nov 29, 3:25pm by TURN_IN script

Implement the fertility-HMM alignment model of Zhao and Gildea (2010) using Gibbs sampling. Compare Viterbi alignments from Model1 to the result of the fertility-HMM model with Gibbs sampling for the first few sentences of the test corpus.

Homework 5

Due Thu Nov 10, 3:25pm by TURN_IN script

Your assignment is to implement IBM Model 1. You will train parameters using Expectation Maximization on a parallel French-English corpus, and evaluating the results on held-out test data in terms of model perplexity. In particular, your implementation should include:

• Insertion from the dummy NULL token
• Many-to-one mappings in one direction
• Calculation of perplexity on training and test data
• Output of parameters in human-readable format

Training data can be found here: /u/cs448/data/hw4/. This directory contains parallel French-English text from the Canadian Parliament. Both sides (French and English) have been run through a tokenizer to split off punctuation from words.

You should floor all probabilities to a low number, say 1e-07, to avoid numerical problems as well as dead-ends in the EM training. Similarly, you may need to prune low-valued parameters in order to make memory usage and file sizes manageable.

Please turn in:

• your source code
• a graph of perplexity over ten training iterations on training and test data
• some discussion of the translation table learned: examples of good and bad lexical pairs, what sort of problems might be "fooling" the algorithm, or whatever strikes your eye.

This is a big data set, and training is time- and memory-intensive.

Homework 4

Due Tues Oct 3, 3:25pm by TURN_IN script

• Implement CRF training for POS tagging using the data of HW 2 and HMM-style emissions and transition as features. You may use an existing Perl/Python implementation of LBFGS. Plot log-likelihood and performance on held-out data as a function of LBFGS iteration. Does the CRF outperform the HMM using the same features?

Homework 3

Due Thur Sep 22, 3:25pm by TURN_IN script

• Implement EM and variational bayes for HMM part of speech tagging. Evaluate against gold labels using variation of information (see Johnson). You can use this numerical approximation of the digamma function.

Homework 2

Due Tues Sep 13, 3:25pm by TURN_IN script

• Implement Viterbi and posterior decoding for a POS HMM using the data in /u/cs448/data/hw2 for training and testing. Which does better in per-word and per-sentence accuracy?
• Experiment with Dirichlet smoothing parameters - do they improve results, and what is a good value for alpha?

Homework 1

Due Tues Sep 6, 3:25pm by email to mehdih at cs.

• Write a Perl program to count the number occurrences of each word in the file hansard.36.1.house.debates.e. Your program should be able to output the counts sorted by frequency and alphabetically.
• Plot rank vs. frequency. How closely does the curve follow Zipf's law? Estimate the exponent of the curve, and calculate a coefficient of correlation in the log/log domain.
• Can you identify regions of function words, content words, and proper names in the sorted list? Are they visible in the plot?