For this lab, we will be compiling the code you write into the program EvalLMLab3. Here is an outline of what this program does:
reset all n-gram counts to 0
for each sentence in the training data
update n-gram counts (A)
for each sentence to be evaluated
for each n-gram in the sentence
call smoothing routine to evaluate probability of n-gram given training counts (B)
compute overall perplexity of evaluation data from n-gram probabilities
In this part, you will be writing code to collect all of the n-gram counts needed in building a trigram model given some text. For example, consider trying to compute the probability of the word KING following the words OF THE. The maximum likelihood estimate of this trigram probability is:
Before we continue, let us clarify some terminology. Consider the maximum likelihood estimate for the bigram probability of the word THE following OF:
In practice, instead of working directly with strings when collecting counts, all words are first converted to a unique integer index; e.g., the words OF, THE, and KING might be encoded as the integers 1, 2, and 3, respectively. In this lab, the words in the training data have been converted to integers for you. To see the mapping from words to integers, check out the file vocab.map in the directory ~stanchen/e6884/lab3/. As mentioned in lecture, in practice it is much easier to fix the set of words that the LM assigns (nonzero) probabilities to beforehand (rather than allowing any possible word spelling); this set of words is called the vocabulary. When encountering a word outside the vocabulary, one typically maps this word to a distinguished word, the unknown token, which we call <UNK> in this lab. The unknown token is treated like any other word in the vocabulary, and the probability assigned to predicting the unknown token (in some context) can be interpreted as the sum of the probabilities of predicting any word not in the vocabulary (in that context).
To prepare for the exercise, create the relevant subdirectory and copy over the needed files:
mkdir -p ~/e6884/lab3/ cd ~/e6884/lab3/ cp ~stanchen/e6884/lab3/Lab3_LM.C . cp ~stanchen/e6884/lab3/.mk_chain .
count_sentence()in the file Lab3_LM.C. Read this file to see what input and output structures need to be accessed. This routine corresponds to step (A) in the pseudocode listed in Section 2.1. In this function, you will be passed a sentence (expressed as an array of integer word indices) and will need to update all relevant regular n-gram counts (trigram, bigram, and unigram) and all relevant history n-gram counts (bigram, unigram, and 0-gram). All of these counts will be initialized to zero for you.
In addition, for Witten-Bell smoothing (to be implemented in Part 3), you will also need to compute how many unique words follow each bigram/unigram/0-gram history. We refer to this as a “1+” count, since this is the number of words with one or more counts following a history.
It is a little tricky to figure out exactly which n-grams to count in a sentence, namely at the sentence begins and ends. For more details, refer to slide 39 (entitled “Technical Details: Sentence Begin and Ends”) in the week 5 language modeling slides. The trigram counts to update correspond one-to-one to the trigram probabilities used in computing the trigram probability of a sentence. Bigram history counts can be defined in terms of trigram counts using the equation described earlier. How to do counting for lower-order models is defined analogously.
Your code will be compiled into the program EvalLMLab3, which constructs an n-gram language model from training data and then uses this LM to evaluate the probability and perplexity of some test data. To compile this program with your code, type
To run this program (training on 100 Switchboard sentences and evaluating on 10 other sentences), run
The instructions in lab3.txt will ask you to run the script lab3p1b.sh, which does the same thing as lab3p1a.sh except on a different 10-sentence test set.