1    Overview

The purpose of this assignment is to give you practice working with sequential data and models. In particular, you will be implementing a hidden Markov model with an adjustable number of hidden states, training it with the Expectation Maximization algorithm, and em- pirically investigating applications using the Forward-Backward (sum-product) algorithm. The ultimate goal of this project will be to train two separate hidden Markov models and to use the models to solve a natural language classification task.

This project is due Thursday, December 8th by 1159PM EDT. We would like Since this deadline is pushing near to the end of the semester, students are strongly encouraged to submit their work by this deadline.

You are allowed to complete this project either on your own, or in teams of up to three students.  Students completing this project as a team will be required to include a col- laboration statement in their writeup, outlining the contributions of the individual team members. All students in a given group will receive the same grade on the project.

2    Working with Language

Many interesting machine learning applications pertain to natural language. Natural lan- guage has the nice property that all values are discrete, so most applications work by first building a vocabulary which maps tokens to unique integers.

It  is  possible  to  work  at  the  level  of words  or  at  the  level  of characters.    Both  ap- proaches have advantages and disadvantages, mostly in terms of flexibility of the model and data/memory/cpu requirements. Word level models tend to have trouble with proper nouns and require significant memory.   Character level models perform well with novel words and use less memory; however, viewing a text as a sequence of characters necessarily means they have to process longer sequences, which introduces a new set of challenges.

A typical person may have a vocabulary around 20k words. If one includes proper nouns, the number of unique words is likely in the millions.  If one narrows it down to lemmas, it may be a few hundred thousand.  Regardless, there are a LOT of words!  Word-based language models do not perform well on unknown words encountered at test time. In order to compensate, a special  “UNK” symbol is normally used which stands in for a generic “Unknown Word” .

An alternative representation is to build a character based model. Character models indi- vidually encode each character as a part of the input, including punctuation and whitespace. This is advantageous in that new words (such as unique names) can be encountered at test time without breaking the model.  It is also advantageous because the emission distribu- tions are much simpler – even allowing for case sensitivity and some punctuation, there may only be on the order of a hundred (or fewer) unique characters.  These advantages come at a price – character based models are prone to produce gibberish words, and have more difficulty with long-term dependence because they must process longer sequences.

A  “directory of files” is a typical way to represent a large text-based dataset.   In this representation, each data point is a separate file. This is particularly common when working with sequential data, because one of the advantages of sequential models are their ability to handle inputs of varying length.  It also eliminates small problems such as delimiters showing up in inputs (as would happen with CSV data).

It is common for sequential models to identify sample boundaries with sentence boundaries; however, there is no requirement that models stop working when encountering the end of a sentence.   In fact, it would be much better if they could coherently process entire documents.   Representing each sample as a separate file also eliminates the problem of sentence boundary detection and segmentation.

Another common representation  (the one used by our textbook) is the  “1-of-k” or  “1- hot” encoding, where each word (or character) is assigned a unique integer, and the input is viewed as a sequence of integers.   The individual integers are then represented as 1- hot vectors.  While this approach makes the math convenient, this can result in VERY SIGNIFICANT memory requirements.

This is an extremely active area of current research in computer science; you can find an abundance of papers on word and character encodings for language models. (Note that the majority of recent papers are focused on deep learning approaches to this problem, but the general problem area reaches back decades!)

2.1    The IMDB Dataset

Your instructor has included a sample text dataset with this assignment.  It consists of 50,000 movie reviews posted to the website IMDB. (See Mass et al 2011 for more infor-mation.)  The data is organized into balanced classes based on the polarity of the review (positive or negative).   The data is also organized into separate train and testing sets. Your instructor has lightly edited the data to remove HTML tags, tokenize the words and

At a minimum, you must implement log likelihood calculation, the em algorithm, saving and loading of models, and sampling of additional sequence outputs (forward backward is fine; Viterbi not required.)

4    Experiments

You are being asked to explore the limits of hidden markov models for sequence prediction, and how these limits are related to the number of hidden states in specific models.  You must pick one experiment per member of your team (solo students still pick one; teams of two pick two; teams of three do all three.)

1. Building a  Classifier.  What number of hidden states do you feel results in the most effective model, considering the practical limitations of the hardware you’re using to complete this project?  E.g., what number of hidden states results in good classification?   Perhaps the answer is a single hidden state  (i.e., a bag of words). Perhaps it is hundreds of hidden states. Investigate.

Do you ever observe overfitting? Do you observe underfitting?

2. Exploring Convergence.

How many iterations of EM do you need?

(a) Decide what it means for EM to converge.   A technical definition is a local maximum of the likelihood function with respect to the parameters.   A less precise definition is “when the likelihood stops improving” .

Run EM until it stops improving with 1 hidden state (just a few iterations should work).  Then try again with 2 hidden states, then 10, ...  and so on, until you find the iterations become too slow.

Try your best to quantify how increasing the number of hidden states impacts the number of iterations of EM until convergence. (Use graphs and explanations.)

3. Exploring the Future.

When exploring predictive power, try to establish a distribution over the maximum number of correct predicted states – e.g., form a histogram of the number of times

the HMM predicts one step accurately, two steps, three steps, and so on.                  The simplest number to obtain is the proportion of one step predictions that are correct with the real data (no Viterbi needed).