$24
Assignment 1 Solution
1.0 Basics
Staple the pages of your homework assignment. Also, write your name, your student PID, the course num-ber (CSE 250A), and the problem set number in the top right corner of every page. Homeworks will be submitted and returned according to the first letter of your last name; therefore your last name should be especially legible!
1.1 Conditioning on background evidence
It is often useful to consider the impact of specific events in the context of general background evidence, rather than in the absence of information.
Denoting such evidence by E, prove the conditionalized version of the product rule: P (X; Y jE) = P (XjY; E)P (Y jE):
Also, prove the conditionalized version of Bayes rule:
P (XjY; E) = P (Y jX; E)P (XjE):
P (Y jE)
(c) Also, prove the conditionalized version of marginalization:
X
P (XjE) = P (X; Y = yjE):
y
1.2 Conditional independence
Show that the following three statements about random variables X, Y , and E are equivalent:
(1) P (X; Y jE) = P (XjE)P (Y jE)
P (XjY; E) = P (XjE)
(3) P (Y jX; E) = P (Y jE)
In other words, show that (1) implies (2) & (3), that (2) implies (1) & (3), and that (3) implies (1) & (2). You should become fluent with all these ways of expressing that X is conditionally independent of Y given E.
1
1.3 Creative writing
Attach events to the binary random variables X, Y , and Z that are consistent with the following patterns of commonsense reasoning. You may use different events for the different parts of the problem.
(a) Cumulative evidence:
P (X = 1) < P (X = 1jY = 1) < P (X = 1jY = 1; Z = 1)
(b) Explaining away:
P (X = 1jY = 1) P (X = 1);
P (X = 1jY = 1; Z = 1) < P (X = 1jY = 1)
(c) Conditional independence:
P(X =1; Y =1) 6= P(X =1)P(Y =1)
P (X = 1; Y = 1jZ = 1) = P (X = 1jZ = 1)P (Y = 1jZ = 1)
1.4 Bayes Rule
Suppose that 1% of competitive cyclists use performance-enhancing drugs and that a particular drug test has a 5% false positive rate and a 10% false negative rate.
Let D 2 f0; 1g indicate whether a cyclist is doping, and let T 2 f0; 1g indicate the outcome of the drug test. Draw the belief network for these random variables, and use the information above to deduce the (conditional) probability tables for P (D) and P (T jD).
Cyclist A tests negative for drug use. What is the probability that Cyclist A is not using drugs?
Cyclist B tests positive for drug use. What is the probability that Cyclist B is using drugs?
1.5 Entropy
Let X be a discrete random variable with P (X = xi) = pi for i 2 f1; 2; : : : ; ng. The entropy H[X] of the random variable X is a measure of its uncertainty. It is defined as:
n
H[X] =
Xi
pi log pi:
=1
Show that the entropy H[X] is maximized when pi = n1 for all i. You should do this by computing the
P
gradient with respect to pi and using Lagrange multipliers to enforce the constraint that i pi = 1.
Later in the course, we will use similar calculations for learning probabilistic models.
2
Despite this asymmetry, it is still common to refer to KL(p; q) as a measure of distance. Many algo-rithms for machine learning are based on minimizing KL distances between probability distributions.
1.7 Mutual information
The mutual information I(X; Y ) between two discrete random variables X and Y is defined as
(c) Using the inequality in (a), as well as the simple equality log x = 2 log bound:
KL(p; q)
X(ppi
pqi)2:
x, derive the tighter lower
p
i
(b) The joint entropy of n discrete random variables (X1; X2; : : : ; Xn) is defined as:
X X X
H(X1; X2; : : : ; Xn) = : : : P (x1; x2; : : : ; xn) log P (x1; x2; : : : ; xn);
x1 x2 xn
where the sums range over all possible instantiations of X1; X2; : : : ; Xn. Show that if the variables Xi
are independent, then their joint entropy is the sum of their individual entropies: namely,
n n
Y X
P (x1; x2; : : : ; xn) = P (xi) implies H(X1; X2; : : : ; Xn) = H(Xi):
i=1 i=1
1.6 Kullback-Leibler distance
Consider two discrete probability distributions, pi and qi, with
pi =
qi = 1. The Kullback-Leibler (KL)
distance between these distributions (also known as the relative entropy) is defined as:
KL(p; q) = Xi
P
P
pi log(pi=qi):
(a) Consider the natural logarithm (in base e). By sketching graphs of log(x) and x
1, verify the
inequality:
x
log(x)
1;
with equality if and only if x= 1. Confirm this result by differentiation of log(x) (x
1).
Use the previous result to prove that KL(p; q) 0; with equality if and only if the two distributions pi and qi are equal.
Provide a counterexample to show that the KL distance is not a symmetric function of its arguments:
KL(p; q) 6= KL(q; p):
I(X;Y) =
x y
P (x; y) log
P (x; y)
;
P (x) P (y)
X X
where the sum is over all possible values of the random variables X and Y . Note how the mutual information is related to the definitions in the previous two problems.
3
Show that the mutual information is nonnegative. (Hint: use the result of the previous problem.)
Show that the mutual information I(X; Y ) vanishes if and only if X and Y are independent random variables. (Thus, I(X; Y ) provides one quantitative measure of dependence between X and Y .)
1.8 Compare and contrast
Consider the different belief networks (BNs) shown below for the discrete random variables X, Y , and Z.
belief network #1
belief network #2
belief network #3
X
X
X
Y
Z
Y
Z
Y
Z
Does the first belief network imply a statement of marginal or conditional independence that is not implied by the second? If yes, provide an example.
Does the second belief network imply a statement of marginal or conditional independence that is not implied by the third? If yes, provide an example.
Does the third belief network imply a statement of marginal or conditional independence that is not implied by the first? If yes, provide an example.
1.9 Hangman
Consider the belief network shown below, where the random variable W stores a five-letter word and the random variable Li 2 fA; B; : : : ; Zg reveals only the word’s ith letter. Also, suppose that these five-letter words are chosen at random from a large corpus of text according to their frequency:
COUNT(w)
P (W = w) = Pw0 COUNT(w0 );
where COUNT(w) denotes the number of times that w appears in the corpus and where the denominator is a sum over all five-letter words. Note that in this model the conditional probability tables for the random variables Li are particularly simple:
P (Li = ‘jW = w) =
(
0
otherwise.
1
if ‘ is the ith letter of w,
Now imagine a game in which you are asked to guess the word w one letter at a time. The rules of this game are as follows: after each letter (A through Z) that you guess, you’ll be told whether the letter appears in
4
the word and also where it appears. Given the evidence that you have at any stage in this game, the critical question is what letter to guess next.
W
L1 L2 L3 L4 L5
Let’s work an example. Suppose that after three guesses—the letters D, I, M—you’ve learned that the let-ter I does not appear, and that the letters D and M appear as follows:
M
D
M
Now consider your next guess: call it ‘. In this game the best guess is the letter ‘ that maximizes
P L2 = ‘ or L4 = ‘ L1 = M; L3 = D; L5 = M; L2 62fD; I; Mg; L4 62fD; I; Mg :
In other works, pick the letter ‘ that is most likely to appear in the blank (unguessed) spaces of the word.
For any letter ‘ we can compute this probability as follows:
P L2
= ‘ or L4 = ‘ L1 = M; L3 = D; L5 = M; L2 62fD; I; Mg; L4 62fD; I; Mg
=
w
P W = w; L2 = ‘ or L4 = ‘ L1 = M; L3 = D; L5 = M; L2 62fD; I; Mg; L4 62fD; I; Mg ;
marginalization
X
=
w
P (W = wjL1 = M; L3 = D; L5 = M; L2 62fD; I; Mg; L4 62fD; I; Mg P (L2 = ‘ or L4 = ‘jW = w)
product rule & CI
X
where in the third line we have exploited the conditional independence (CI) of the letters Li given the word W . Inside this sum there are two terms, and they are both easy to compute. In particular, the second term is more or less trivial:
P (L2 = ‘ or L4 = ‘jW = w) = (
1
if ‘ is the second or fourth letter of w
0
otherwise.
And the first term we obtain from Bayes rule:
P (W = wjL1 = M; L3 = D; L5 = M; L2 62fD; I; Mg; L4 62fD; I; Mg
P (L1 = M; L3 = D; L5 = M; L2 62fD; I; Mg; L4 62fD; I; MgjW = w P (W = w)
=
Bayes rule
P(L1 =M; L3 =D; L5 =M; L2
62fD; I; Mg; L4 62fD; I; Mg)
In the numerator of Bayes rule are two terms; the left term is equal to zero or one (depending on whether the evidence is compatible with the word w), and the right term is the prior probability P (W = w), as
5
determined by the empirical word frequencies. The denominator of Bayes rule is given by:
P (L1 = M; L3 = D; L5 = M; L2 62fD; I; Mg; L4 62fD; I; Mg)
X
=
P (W = w; L1 = M; L3 = D; L5 = M; L2 62fD; I; Mg; L4 62fD; I; Mg);
marginalization
w
X
=
P (W = w)P (L1 = M; L3 = D; L5 = M; L2 62fD; I; Mg; L4 62fD; I; MgjW = w);
product rule
w
where again all the right terms inside the sum are equal to zero or one. Note that the denominator merely sums the empirical frequencies of words that are compatible with the observed evidence.
Now let’s consider the general problem. Let E denote the evidence at some intermediate round of the game: in general, some letters will have been guessed correctly and their places revealed in the word, while other letters will have been guessed incorrectly and thus revealed to be absent. There are two essential computations. The first is the posterior probability, obtained from Bayes rule:
P (EjW = w) P (W = w)
P (W = wjE) = Pw0 P (EjW = w0 ) P (W = w0 ):
The second key computation is the predictive probability, based on the evidence, that the letter ‘ appears somewhere in the word:
P Li = ‘ for some i2f1; 2; 3; 4; 5g E
=
w
P Li = ‘ for some i2f1; 2; 3; 4; 5g
W = w P W = w E :
X
Note in particular how the first computation feeds into the second. Your assignment in this problem is implement both of these calculations. You may program in the language of your choice.
Download the file hw1 word counts 05.txt that appears with the homework assignment. The file contains a list of 5-letter words (including names and proper nouns) and their counts from a large corpus of Wall Street Journal articles (roughly three million sentences). From the counts in this file compute the prior probability P (w) = COUNT(w)= Pw0 COUNT(w0 ). As a sanity check, print out the fifteen most frequent 5-letter words, as well as the fourteen least frequent 5-letter words. Do your results make sense?
Consider the following stages of the game. For each of the following, indicate the best next guess— namely, the letter ‘ that is most likely (probable) to be among the missing letters. Also report the probability P (Li = ‘ for some i 2 f1; 2; 3; 4; 5gjE) for your guess ‘. Your answers should fill in the last two columns of this table. (Some answers are shown so that you can check your work.)
correctly guessed
incorrectly guessed
best next guess ‘
P (Li = ‘ for some i2f1; 2; 3; 4; 5gjE)
–––––
fg
–––––
fE, Ag
A–––S
fg
A–––S
fIg
––O––
fA, E, M, N, Tg
–––––
fE, Og
I
0.6366
D––I–
fg
A
0.8207
D––I–
fAg
E
0.7521
–U–––
fA, E, I, O, Sg
Y
0.6270
6
Turn in a hard-copy printout of your source code. Do not forget the source code: it is worth many points on this assignment.
More fun: The demo on Piazza (also under resources) implements this program for words of length 6-10. You will also find count files for words of these lengths on Piazza, and if you modify your code to handle these different word lengths, you will also be able to check your answers against the demo. (This is totally optional, though.) Just to be perfectly clear, you are not required in this problem to implement a user interface or any general functionality for the game of hangman. You will only be graded on your word lists in (a), the completed table for (b), and your source code in (c).
7
