Homework # 9
1. Attached you will find the Hidden Markov chapter from the Murphy machine learning book. Be careful, in the book zt represents the hidden Markov chain (our X(t)) and xt repre- sents the observables (our Y (t)). In this problem we will revisit the cheating casino model of Problem 1 in homework 9. Let Y (0), Y (1), . . . , Y (200) be the die rolls you generated in 1(a) of homework 9.
(a) Read section 17.4.2 in Murphy. Provide your own deriva- tion of the forward algorithm for computing,
αt =P(X(t)|Y(0),…,Y(t)). (1)
(In this setting αt is a 2-dimensional vector corresponding to the fair and cheating states of X(t). Write a function Forward(Y) that accepts a vector Y giving the values Y(0),Y(1),…,Y(200) and returns αt for all values of t.
(b) Read section 17.4.3.1 in Murphy. Provide your own deriva- tion of the backward algorithm for computing,
βt =P(Y(t+1),Y(t+2),…,Y(200)|X(t)). (2) Write a function that computes βt over all t given the die
roll data.
(c) Explain equation 17.50 in Murphy. Write a function that computes the smoothing probability,
P (X (t) = C | Y (0)Y (1), . . . , Y (T )) (3) Plot the smoothing probability as a function of t and com-
pare to your estimate in hw 9.
(d) There are 10 parameters in the cheating casino model; let θ represent the vector formed by these parameters. Four parameters form the transition probability matrix of X(t) and 6 parameters determine the probabilities of the cheating die roll. (We’ll assume that we know the fair die roll probabilities.) Use a hard or soft EM ap- proach to estimate these parameters. (Hint: You know the
1
die rolls Y (0), Y (1), . . . , Y (200). Suppose you also knew X (0), X (1), . . . , X (200), then you can estimate the param- eters. Suppose you knew the parameters, then you can make soft or hard assignments of X(t) using the smooth- ing probabilities. Now iterate: pick a θ, assign the X(t), update θ.) Murphy writes down the EM formulas in sec- tion 17.5.2. Don’t go through his formulas! Choose some way of assigning the X(t) and updating θ and iterate. It’s ok if the assignment or update isn’t exactly right!
2. In this homework we will develop the theory behind using pseudolikelihoods to fit a undirected graphical model and in the next homework we will actually fit some data. Let X = (X1, X2, . . . , X8). Consider the following probabilistic model for X,
188
P (X | θ) = Z exp[η · X + wij XiXj ] (4)
i=1 j=i
where θ contains the parameters η, which is a 8-dimensional
vector, and the wij.
(a) Write an expression for φ(X) so that,
P(X|θ)= 1exp[θ·φ(X)] (5) Z
(b) Show the following,
i.
ii.
P(Xj |X−j,θ)= 1 exp[θ·φ(X)] (6) Z′
and give an expression for Z′. (Conditioning on X−j means we condition on all coordinates of X except the jth.). Your expression for Z′ should be the sum of two terms.
1 ∂Z′
Z′ ∂θ = E[(φ(X))k | X−j,θ] (7)
k
iii.
∇θlogP(Xj |X−j,θ)=φ(X)−E[φ(X)|X−j,θ] (8)
2
(c) Consider the pseudolikelihood, N 1 n
p(θ) = logP(X(i) | X(i),θ) (9) n j −j
i=1 j=1 Show using (b) that,
N N1n ∇p(θ)=φ(X(i))− E[φ(X)|X−j =X(i),θ]
n −j i=1 i=1 j=1
(10) (d) Write an expression for the following expectation,
E[f(X) | X−j,θ], (11) in terms of Z′ in (b.i), where f(X) : R8 → R. You expres-
sion should be the sum of two terms.
3