Information Theory Assignment


When turning in this assignment, please make sure you carefully follow the directions from the TA on how to do so. Remember, we're taking off points if you don't follow directions. Thanks.

First, a couple of notes.

For the mathematically inclined and/or those who liked the idea of deriving an information measure from a set of properties such a measure should have, here are several derivations of the definition of entropy based on axioms about such properties. The one I mentioned in class is from A.I. Khinchin, Mathematical Foundations of Information Theory, Dover, New York, 1957.

Also, in case you're curious, here's the pointer to an algorithm for creating optimal codes using Huffman coding (see also this interesting discussion by Huffman's nephew).

Finally, a reminder about notation. If X is a random variable whose distribution is (p1,p2,...,pk) then we usually write H(X) for H(p1,p2,...,pk). I will occasionally write H(p) instead of H(X), where p abbreviates p1,p2,...,pk.


  1. (Manning and Schuetze exercise 2.12) Show that the KL divergence is not symmetric by giving an example of two distributions p and q for which D(p||q) is not equal to D(q||p). Give the two distributions and show the explicit computation of the KL divergences.

    Note that if you understand KL-divergence, this problem should take you no more than 5 minutes, including writing it down. If it's taking you longer, go back and make sure you understand what KL-divergence is.

    Also note that simple toy distributions (e.g. over {heads,tails}) are really boring to grade! You can give us the boring kind of example, but you'll earn more goodwill for an example that is significantly interesting or amusing.

  2. (Based very loosely on Manning and Schuetze exercise 2.10) For this problem, let's use the State of the Union(SOTU) addresses of U.S. presidents, a collection of documents described in the previous assignment. For our purposes here, let's restrict ourselves to Presidents Bush-1 (that is, Republican president George Herbert Walker Bush), Clinton (Democrat), Bush-2 (that is, Republican president George W. Bush), and Obama (Democrat). For simplicity, you can assume that the total vocabulary is the union of all the unigrams in the various texts.

    To answer the questions you'll need to estimate probability distributions over unigrams for each president.

    Speeches will of course need to be tokenized, and you should convert all text to lowercase in order to mitigate sparse data problems. Note that you'll need to do something about zero counts. As the simplest option, you can smooth using Laplace smoothing ("add one", Manning and Schuetze Section 6.2.2) to avoid zero, even though in practice this is not considered the state of the art. (Ok, I'm probably being overly generous. In these tutorial slides about smoothing the author describes Laplace as "a horrible choice".) Or, a bit better, you could use add-k for a different k, e.g. setting k to 1/|V| where |V| is the size of the vocabulary. That's really easy to implement, if you're programming from scratch, and it tends to work ok. State of the art would be modified Kneser-Ney smoothing, though it would be a major distraction from the main point of the assignment for you to implement that from scratch.

    Here's a simple observation that might help you avoid writing a lot of new code from scratch, allowing you to re-use work you've already done in the previous assignment: if you have a bigram frequency table with entries count(a,b), then the unigram counts are just the marginal counts for a and b, i.e.:

    count(a) = ∑b' count(a,b')

    count(b) = ∑a' count(a',b)

    Best practice would be to smooth the bigram counts first, and then compute the unigram counts as above. If you smooth unigrams and bigrams separately, there's no guarantee that summing over smoothed bigram counts to compute the marginals will give you the same number you get from smoothing unigrams separately. But this is a minor point and for this assignment I'm fine with any fairly reasonable smoothing as long as you say clearly what you did.

    Speaking of implementing from scratch, you don't have to do everything completely from scratch. There are, for example, existing language modeling modules (e.g. in NLTK) and toolkits (e.g. KenLM and SRILM), and you're welcome to use those in any way you like. Just make sure to clearly identify any software that you didn't write yourself in your PDF writeup.

    Questions.

Extra credit (up to 20%)