Information Theory Assignment


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.


Do BOTH of these on-paper problems

  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.

Do ONE of the following TWO exercises in programming and data exploration

Option 3a

Read Piantadosi et al. (2011), Word lengths are optimized for efficient communication, showing that word length correlates better with the average amount of information conveyed by a word in context than it does with the word's context-independent frequency or information. (Wait, you mean you didn't already read it for last class?!) This seems like it should be a really easy do-it-yourself experiment -- so the problem is to have a try at doing it yourself!

You can do this for the simple case of just bigram probabilities (i.e. context C=c means "the previous word is c"), although it would certainly also be interesting to see what things look like for higher-order ngrams. If you're doing that, I recommend using an existing language modeling module (e.g. in NLTK) or toolkit (e.g. KenLM and SRILM). As usual, just make sure to clearly identify any software that you didn't write yourself in your PDF writeup.

You should do your experiment for English and at least one other language. As one possible source of data to work with, see the NLTK corpora. The Brown corpus would be a smallish but decent source for English (just remove POS tags and lowercase everything; it's already tokenized); you could also augment that with other English corpora, although be careful to make sure that your sources don't overlap, which would throw off your counts. For other languages, one source would be the NLTK samples from the Europarl corpora; if you were feeling more ambitious you could look into the full Europarl corpora, which I believe are quite a bit larger. Or feel free to identify other sources of text. The corpus processing (acquisition, cleanup, etc.) are not the point of this assignment, so I encourage people to share pointers, cleanup code, and even corpus data using Piazza. (Recall that constructive participation on Piazza contributes to your class participation grade.)

You are not required to actually succeed in replicating the research results in the paper -- that would take a lot of work, since they used fairly sizeable corpora that you probably don't have easy access to. In fact, you're not even required to compute correlations (though that would be nice); we'll be happy if you produce charts that look roughly like their Figure 2, no error bars required (though that would be nice also).

What you do need to do involves (a) briefly summarizing what the study is about in your own words to show that you understand it, (b) clearly describing for us what you did in your own experiment (along with any simplifying choices you made and why/how you made them), and (c) clearly showing and telling us what you you found. If your results are very different from what you would have expected, then (d) suggest some explanations why (and ideally support your explanation with data). The more thoughtful and clearly written your writeup the better.

Remember that the goal is not to "get it right", but to show you understand the ideas and that you're taking a thoughtful approach. The writeup matters.

By the way, if you found this interesting, there's a follow-up paper in which Meylan and Griffiths (2017) argue that phonological distinctiveness actually outperforms word length as a predictor of frequency. They define the phonological information content of a word to measure the distinctiveness of its phoneme-to-phoneme transitions. The intuition behind their argument is that it's not just a word's probability in context that influences how much effort it takes to recognize it -- it's also the number of competitors (alternative words) you could have been hearing at that point based on the acoustic evidence.

Option 3b

(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 these days it's also not difficult to find code for neural network language models, e.g. OxLM or this tutorial on implementing a recurrent neural network language model using Theano; see also the CL1 notes on n-gram language models and neural language models. You're welcome to use tools like those in any way you like -- just make sure to clearly identify any software that you didn't write yourself in your PDF writeup. And if you find a particularly good discussion/tutorial on the Web, please post it to the class discussion board!

Questions.

Extra credit (up to 10%)