Smoothing

In this assignment you will get some hands-on experience with smoothing for language modeling. You can either implement a smoothing technique yourself, or you are free to use the SRI Language Modeling Toolkit, also known as srilm.

Turn in your code as a tarball, and turn in a hardcopy of the writeup by e-mail. This assignment is due at 5pm Friday, March 9, 2007.

For reference, download Stanley F. Chen and Joshua T. Goodman. An Empirical Study of Smoothing Techniques for Language Modeling. Technical Report TR-10-98, Computer Science Group, Harvard University, 1998. For present purposes, the relevant parts are Section 1 and Section 2 up through Section 2.8 (page 18), excluding Sections 2.3 and 2.5.
Download the version of the Bible at http://www.umiacs.umd.edu/~resnik/parallel/bible/English/bib.EN. Separate the full set of verses into a training set that includes the first five books (GEN, EXO, LEV, NUM, DEU) and a first test set that includes the rest. Discard everything that's not a Bible verse (a seg element), and lowercase and tokenize the text. (You can use any tokenizer you like. Tokenizing just on common punctuation and whitespace is fine; no need to get fancy. You may already have done this step for a previous assignment.) To keep life simple in terms of the boundary case, add two instances of a special start token (e.g. @START@) to the beginning of both sets. Doing this for all data sets guarantees that P(w1) and P(w2|w1) are both equal to 1.)
For the writeup, Item 1: Briefly describe your preprocessing, esp. what your tokenizer does.
Download Adventures of Sherlock Holmes as a second test set. Preprocess the same way that you did in the previous step. N.B. You may already have done this step for a previous assignment.
*See note at the end regarding alternative training and test sets
Train a trigram language model on the training set, smoothing using some version of Good-Turing (GT), Katz backoff (Katz), or Kneser-Ney (KN).
You are free to use srilm for this. If you do your own implementation, you'll want to make sure to work with log probabilities rather than raw probabilities to avoid underflow problems. I would predict that GT is significantly more straightforward than either Katz or KN, since you don't need to worry about combining with or backing off to estimates for lower order n-grams.
For the writeup, Item 2: Describe how you did your smoothing. If you used srilm, be explicit about which parameter settings you used. If you did your own implementation, give any "missing details" of what you implemented. (E.g. for Good-Turing, how did you compute S(Nr)? Did you keep hapax legomena, or did you treat ngrams seen only once as if they were never observed? Etc.)
Evaluation.
For the writeup, Item 3: Which of the two test sets is more likely, according to your trained model? Briefly discuss a few instances (e.g. individual n-grams, phrases, or sentences) where the model does and does not make good predictions.

Note regarding alternative training and test sets

The assignment uses the Bible and Sherlock Holmes because you're likely to have worked with these on previous assignments. However, here are two variants on the assignment that are closer to the real world and therefore, perhaps, more interesting. Feel free to do one of these instead. (Make sure you still turn in answers to Items 1 and 2, above, in your hardcopy. See below for the alternative versions of Item 3.)

Either of these alternatives is worth 10% extra credit.

Using language modeling for authorship identification

The Federalist Papers are an important piece of American history, but there have been well known disputes regarding the authorship for some of them. This on-line version of the Federalist Papers identifies an author for each one following "the consensus of scholars". The Wikipedia list of Federalist papers identifies the twelve whose authorship is disputed.

Training. Create three trigram models by splitting the undisputed Federalist papers up according to their undisputed authors.
Testing. Create a test set for each of the disputed papers.
Evaluation.
Alternative Item 3 for your writeup: For each of the disputed papers, which trigram model best predicts it? How well do your predictions match the consensus of scholars?

Using language modeling to rescore machine translation hypotheses

One common current use of language models is to rescore sytem output for systems that produce hypotheses in the form of English text -- for example, speech recognizers, or machine translation systems.

Training. I will provide training data for an English n-gram language model. I need to find something appropriate that I'm allowed to redistribute for these purposes. What I would like to use is the English language model training data from the NAACL 2006 Workshop on Statistical Machine Translation. However, this may be too large for the entire class to work with it on the GRACE cluster without causing them problems involving CPU utilization and/or disk space. I am looking into this, and in the meantime, you can implement and test your code using some other collection of text, e.g. the Bible corpus.
Testing. For each of N input sentences in Chinese, I will provide M hypotheses that were output by a machine translation system. (Likely values are N = a few dozen, M=1000, but these also will depend on what I find out about available computing resources on the GRACE cluster.)
As an example, see this output file, which contains 1000 hypotheses for a sentence in the NIST 2003 Chinese-English MTeval data set, ranked from best to worst. Each line contains three elements separated by "|||": (a) a sentence ID, (b) a tokenized, lowercase English output from an MT system, and (c) a sequence of feature values from the MT system that go into determining the total score for the hypothesis. We'll be learning more about MT system features later this semester, but you might be interested in nothing that the first feature is the log probability that was assigned by the system's language model. You might also be interested in looking at a correct English translation.
Evaluation. For each sentence, generate the language model scores for all M hypotheses. Re-sort the M hypotheses by language model score. Compare the top hypothesis to the original best hypothesis produced by the MT system (i.e. the one that was on top of the original list), and decide whether you think the translation quality looks worse, better, or about the same, compared to a correct translation (which I'll give you).
Alternative Item 3 for the writeup: report the number of translations in each of those three categories, and discuss an example or two in each category in terms of why you think the translation got worse, better, or stayed the same.