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.
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.
h0 h1 h2 h3 h4 h5 h6 h7
p 1/2 1/4 1/8 1/16 1/64 1/64 1/64 1/64
Recall that the encoding I gave is actually an
optimal encoding for this distribution (one that
uses the fewest possible number of bits on average, when communicating
horse race outcome events). For any distribution, an optimal binary
representation of the events, in the sense of the smallest number of bits
on average, can be created using Huffman
coding. Here's the encoding from class:
h0 h1 h2 h3 h4 h5 h6 h7
codeP 0 10 110 1110 111100 111101 111110 111111
Show, without any numerical computations, that if you use codeP, the expected value Ep[length(h)] (i.e. the expected value of length(h) under distribution p) is equal to H(p), the entropy of the distribution. (Partial credit for doing the two computations explicitly and confirming that you get the same number.)
h0 h1 h2 h3 h4 h5 h6 h7
q 1/8 1/8 1/8 1/8 1/8 1/8 1/8 1/8
Since the horses all have the same probability, the best code we
can invent will obviously use the same number of bits for each
horse. This means that the smallest number of bits we can use is
log28 = 3 bits:
h0 h1 h2 h3 h4 h5 h6 h7
codeQ 000 001 010 011 100 101 110 111
Now imagine that we communicate lots of horse race outcomes using
codeQ. Encoding winning horses using codeQ, what is
Ep[length(h)]?
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) = sum_{b'} count(a,b')
count(b) = sum_{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.