First, 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 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.
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
For any probability distribution, an optimal binary
representation of the events, in the sense of requiring the smallest number of bits
on average to communicate outcomes, can be created using Huffman
coding. Here's the encoding you'd get for the above distribution:
h0 h1 h2 h3 h4 h5 h6 h7
codeP 0 10 110 1110 111100 111101 111110 111111
Illustrate using codeP that the expected value of the length Ep[length(h)] is equal to H(p), the entropy of the distribution. You can simply do the two computations numerically using codeP and confirm that you get the same number, though you'll understand what's going on better if you look at the definitions of Ep[length(h)] and H(p) and show that one is equivalent to the other.
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, there's no basis
for distinguishing them, so obviously the best code we
can invent will 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)]?
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.
If you would like to take a more advanced approach, e.g. a higher order n-gram model or a neural network language model, you are welcome to do so. As usual, please just make sure to explain clearly what you've done, software you used, assumptions you made, etc.
Questions.
.
As your measure comparing any two speeches, use (1/2)*(D(p||q)+D(q||p)), where p and q are bigram distributions for the two speeches being compared. (Averaging the two KL-diverence values is a common way of producing a symmetric value. For related discussion see the Wikipedia page on Jensen-Shannon divergence.) The result can be just a big table of numbers, if you like, though if you want to do a nice-looking matrix heatmap there are many packages for that, e.g. see this one.
a. Show the table that you constructed (or the heatmap).
b. Does the matrix look like you would have expected? Are there any surprises, and if so, what's your explanation? (If you want to explore what's going on in a data-driven way, you could take inspiration from question 3b, above.)
c. How do your table and analysis compare with what's in the Civis Analytics posting? Is what you're seeing generally similar? Any interesting differences? Again, do you have any thoughts about why you might or might not be seeing differences?