HW3 (Due 10/10)

  1. (5 points) Consider two distributions \(p=[0.199, 0.599, 0.199, 0.001, 0.001, 0.001]\) and \(q=[0.1, 0.3, 0.1, 0.1, 0.3, 0.1]\). Compute \(KL(p||q)\) and \(KL(q||p)\). Note that they are significantly different from one another. You may also want to check out this tweet to get some more insight.

  2. (5 points) Use the tropical island example in class again, say we have 5 rainy days with temperatures 20,21,23,25,25 and 6 sunny days with temperatures 22,24,26,27,28,29. Let's denote \(T_{th}\) be a threshold temperature and \(Q=1\) if \(T > T_{th}\) and \(Q=0\) otherwise.

    1. Compute \(H(W|Q)\) when \(T_{th}=24.5\)

    2. Compute \(H(W|Q)\) when \(T_{th}=25.5\)

  3. (10 points) Extra credit. Write a program to compute \(H(W|Q)\) for all possible \(T_{th}\) so as to determine the best split. Please submit your source code in pdf and a screenshot running your code. You get a maximum 5 points implementing the \(O(n^2)\) version and a maximum all 10 points implementing the \(O(n)\) version.