Computer Science 248/448

Homework

Fall 2005

Homework 8

Due Tues Nov 29

Combine your Model 1 t-table and your bigram language model to do translation from French to English on the first 10 sentences from last assignment's held-out data. Assume:

• No reordering - alignments are monotonic.
• French words may be deleted
• No English words are inserted

For efficiency, limit the number of possible English words each French word can be translated as to five.

Try translation with and without language model probabilities. How often do they affect the choice of English output? Do the translations with the LM look better to you?

Homework 7

Due Tues Nov 15

Your assignment is to implement IBM Model 1, decribed in Section 27 of the Knight tutorial. 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/cs248/hw7/. 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 6

Due Tues Nov 8

• MS 12.3
• MS 12.5
• MS 12.8

Homework 5

Due Wed Oct 19 5pm

• Write a program to compute the t score for every bigram in the wsj file from hw 1. Print the top 100 scroring bigrams. How much overlap is there between the 100 most frequent bigrams and the 100 bigrams with the highest t score?
• Make a scatter plot of t-score vs. frequency (you will probably need to plot a sampling of the points to make the plot readable).
• Plot t score against the backoff weight alpha of the first word in the bigram, which you computed in hw 3.
• Plot bigram frequency against alpha of the first word.
• What trends are apparent in the plots and how would you explain them? Give some representative bigrams from different regions of the plots.

Homework 4

Due Tue Oct 4 in class

• Show that if we estimate two bigram language models using unsmoothed relative frequencies (MLE), one from a text corpus and the second from the same corpus in reverse order, the models will assign the same probability to new sentences (when applied in forward and backward order respectively).
• Show that the same result holds for two HMMs, trained on the same corpus forward and backward, if all states are observed in the training data, and unsmoothed relative frequencies are used for observation and state transition probabilities. (Hint: define a new version of one forward probability, and show it is equal to the other model's backward probability.) To simplify things and avoid the pesky initial state distribution pi, assume special START and STOP states at the beginning and end of each sequence, and assume that the model must predict the STOP symbol.

By Friday Sep 30, mail to zhanghao @ cs a trace of your bigram LM program, run on the first three test sentences, showing:

• the probability assigned to each word
• backoff scaling factor and unigram prob for words where you backed off
• the perplexity for these three sentences

Homework 3

Due Fri Sep 23 5pm

• Implement a bigram langauge model using each of the following three smoothing techniques: Lidstone's (MS p 204), Good-Turing, and Good-Turing with backoff to unigram probs. Train each version on the file wsj.txt from hw1, and evaluate perplexity on /u/cs248/hw3/wsj_test.txt. Use the 20,000 most frequent words in the training data as your vocabulary. What is the best value for lambda in Lidstone's estimator? How do the models compare overall? Which models over/underestimate the probability for frequent/infrequent words?

Homework 2

Due Thu Sep 15 in class

• Prove that the two definitions of variance in equation 2.12 (page 47) are equivalent.
• Give an example of two random variables X and Y such that Var(X+Y) != Var(X) + Var(Y).
• Give an example of two random variables X and Y such that Var(X+Y) == Var(X) + Var(Y).
• MS 2.12

Homework 1

Due Wed Sep 7 2005, 5pm

• Write a Perl program to count the number occurrences of each word in the three files in /u/cs248/hw1/. Your program should be able to output the counts sorted by frequency and alphabetically.
• Plot rank vs. frequency for each corpus. How closely do they follow Zipf's law?
• Calculate and plot frequencies for all bigrams in each file.
• What is similar and different across the corpora, both in terms of the curves and the frequent words/bigrams themselves?

Due Thu Sep 8 2005, in class

• MS 1.1
• MS 2.9
• MS 2.10