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 discussion about 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 properties that a measure of uncertainty should have. The one I used 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 the 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 simple toy distributions (e.g. over {heads,tails}) are boring to grade. You'll earn less goodwill on this problem for the boring kind of example, and more goodwill for an example that is significantly interesting or amusing.

  2. Suppose I am upstairs with my two young kids, giving them a bath, and my wife, Becky, is downstairs enjoying a rare moment of rest, drinking a cup of tea and reading a book. (Note that this is not the usual situation. They’re active kids and bathtime is generally a damp two-parent job!) If Becky hears one of the kids wail, she’ll most likely take another sip of tea and continue reading. If she hears me wail, she’ll probably sprint upstairs to see what’s wrong. Explain Becky’s behavior in explicit information-theoretic terms. (That means you should be using concepts, terminology, and argumentation based on information theory.)

  3. (Based loosely on Manning and Schuetze exercise 2.10) Compute three probability distributions over unigrams: one for the Republican speeches in the congressional speech corpus, one for the Democrats, and one for Obama's inaugural address of January 20, 2009.

    Obama's address will need to be tokenized, and you should convert all text to lowercase in order to mitigate sparse data problems. Note that you'll still need to do something about zero counts. As the simplest option, you can smooth using Laplace ("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. Or, slightly 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. For simplicity, you can also assume that the total vocabulary is the union of all the unigrams in the three texts.

    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.

    Questions.