CS 726: Practice Questions on Learning Potentials
1. Consider an undirected graphical model G used to model Pr(x1 , . . . , xn ) with only a single po-
tential over each edge Q (i, j) ∈ G as ψ(xi , xj ) = σ if xi = xj , ψ(xi , xj ) = 1 otherwise. Thus,
Pr(x1 , . . . , xn |σ) = Z1 (i,j)∈G ψ(xi , xj )
Assume each xj takes values from 1 . . . m. Let the training data consist of a single fully labeled
graph, that is, D = {x1 }.
(a) Assume, x1 = [0 0 1 0] and G a chain graph x1 —x2 —x3 —x4 , and m = 2. Write the value of
Pr(x1 |σ) purely in terms of σ, that is, even Z should be written in terms of σ. ..2
σ ns (x)
Pr(x = x1 , . . . , xn ) = Z(σ) where ns (x) is the number of adjacent vertices in x that have the
same label.
1
Pr(x1 |σ) = σZ
For Z, we go over all 16 possible ways of labeling x and count for each value of ns , the count
c(ns ) of labelings x that will have that many adjacent variables with same labels.
This comes to 3ns =0 σ ns c(ns ) = 2 + σ ∗ 6 + σ 2 ∗ 6 + σ 3 ∗ 2
P
1
Thus, we have Pr(x1 |σ) = 2+σ∗6+σσ2 ∗6+σ3 ∗2
(b) Write the gradient of the training objective wrt σ in as simplified a form as possible. [The
gradient should be for general graphs, and not just for the example graph in part (a) above.]
..2
The loglikelihood of the training data
LL(D|σ) = ns (x1 ) log σ − log Z(σ)
Its gradient wrt σ is
ns (x1 ) P P
σ − (i,j)∈E ( ` Pr(xi = `, xj = `))
(c) Solve for σ in closed form in terms of properties of D for the case when G is a tree? ..5 In this
case since we have no node potentials and only the given edge potential, the message that any
node i sends to a node j is uniform. In a tree, the marginal probability of any edge is equal
P σ
to ψij (xi , xj )mi→j (xi )mj→i (xj ). This implies that: ` Pr(xi = `, xj = `) = m mσ+(m−1)m .
σ
Thus, we solve for ns /σ − E σ+(m−1) = 0 to get the value of σ.
(d) Now assume that we have a training dataset D with partially observed set of variables with
n = 3, m = 2, and G a complete graph (a triangle since n = 3.). Let D = {(x11 , x12 ) =
(1, 1), (x22 , x23 ) = (0, 1)}, that is, the first instance has variable x3 hidden and second instance
has x1 hidden. We will use the EM algorithm to solve for σ. Assume at some time t, σt = 2.
For the next iteration, work out the E and M steps. Solve for the optimal value of σ in the
M step.
σt2
i. E-step. ..3 Pr(x13 = 1|(x11 , x12 ) = (1, 1), σt ) = σt2 +1
= 4/(4 + 1) = 4/5.
σt
Pr(x21 = 1|(x22 , x23 )
= (0, 1), σt ) = = 1/2.
σt +σt
ii. M -step. ..3 Z for this problem is 6σ + 2σ 3 .
The M step becomes:
maxσ (4/5 log σ 3 + 1/5 log σ + 1/2 log σ + 1/2 log σ − 2 log(6σ + 2σ 3 ))
2. Consider a n × n grid graph G = (V, E) where V are vertices and E are edges of G. Each node
k ∈ V is a binary random variable yk which takes value 1 or 0 depending on whether it is part
of foreground or background. Each node is attached with a xk that is a real-value denoting its
propensity to be foreground. There are only three features in this UGM
f1 ((yk ), (k), x) = xk yk
f2 ((yk ), (k), x) = yk (1)
f3 ((yk , yj ), (k, j), x) = yk yj + (1 − yk )(1 − yj ) if (k, j) ∈ E, 0 otherwise.
1
Let θ = [θ1 , θ2 , θ3 ] denote the corresponding weights of these three features f = [f1 , f2 , f3 ].
Also, consider an instance (xi , yi ) for a 3 × 3 grid for which the value of features xik and correct
x1 = 0.0, y1 = 0 x2 = 1.5, y2 = 1 x3 = 1.0, y3 = 0
i
label yk are as given as: x4 = 1.4, y4 = 1 x5 = 2.6, y5 = 1 x6 = 1.0, y6 = 1
x7 = 0.5, y7 = 0 x8 = 2.0, y8 = 1 x9 = 0.0, y9 = 0
(a) Write the expression for Pr(y|x) in terms of θ1 , θ2 , θ3 , xk , yk for k ∈ V [Do not use fk ()s but
their defined values above. E.g. use xk yk in place of f1 () etc.] ..1
1 Q Q
Z(xi ) k∈V (exp(θ1 xk yk + θ2 yk )) (k,j)∈E exp(θ3 (yk yj + (1 − yk )(1 − yj ))
(b) Compute the value of the normalizer Z(xi ) at [θ1t , θ2t , θ3t ] = [0, 0, 0] ..2
Since all the θs are zero, we have that for all y the θ.f term is zero, that is numerator above
is 1. Thus, Z(xi ) = number of y combinations possible which is 29
(c) Compute the gradient of log Pr(yi |xi , θt ) wrt θ1 at [θ1t , θ2t , θ3t ] = [0, 0, 0] ..2
Since all y-s are equally likely, the marginal probability for each yk is thePsame at 1/2. Thus, the
gradient: f1 (yi , xi )−EPr(y|xi ,θt ) [f1 (yi , xi )] can be easily computed as. k∈V [xik yki −1/2(xik )] =
i i i
P
k∈V xk yk − xk /2)
3. Consider the problem of training the parameters of a simple HMM of length two where the state and
observation variables are binary. Thus, we have two state variables y1 and y2 and two observation
variables x1 and x2 and all four variables can take one of two possible values. The parameters of the
HMM are Pr(y1 ) Pr(y2 |y1 ) and Pr(x1 |y1 ) and Pr(x2 |y2 ). Assume Pr(x1 |y1 ) = Pr(x2 |y2 ) = Pr(xt |yt )
We use the EM algorithm for training the parameters.
Let the initial values at t = 0 be
Prt (y1 = 0) = θ0t = 0.5
Prt (y2 = 0|y1 = 0) = θ1t = 0.7, Prt (y2 = 0|y1 = 1) = θ2t = 0.2
Prt (xt = 0|yt = 0) = θ3t = 0.1, Prt (xt = 0|yt = 1) = θ4t = 0.8.
For a dataset D consisting of these two sequences x1 = [0, 1], x2 = [1, 1].
(a) E-step: Estimate the values of Pr(y1 |x1 , θt ) ..3
For the E-step
The node potentials at y1 , call them ψ(y1 ) = Pr(y1 ) Pr(xi1 |y1 )
The node potentials at y2 , call them ψ(y2 ) = Pr(xi2 |y2 )
The edge potential ψ(y1 , y2 ) = Pr(y2 |y1 ).
Using this we get that for x1 , ψ(y1 ) = [0.1, 0.8], ψ(y2 ) = [0.9, 0.2],
P
The message from y2 to y1 = y2 ψ(y2 ) Pr(y2 |y1 ) = [0.9 ∗ 0.7 + 0.2 ∗ 0.3, 0.9 ∗ 0.2 + 0.2 ∗ 0.8]
Multiplying this message with ψ(y1 ) gives us Pr(y1 |x1 ).
(b) M-step: In the M-step write the formula for the maximum likelihood estimate of θ0 in terms
of Pr(y1 |x1 , θt ) and Pr(y1 |x2 , θt ). ..1
1 t 2 t
This will just be (Pr(y1 = 0|x , θ ) + Pr(y1 = 0|x , θ ))/2