\underline{Problem Set 4}

MAS 622J/1.126J: Pattern Recognition and Analysis

Due: 5:00 p.m. on October 22

[Note: All instructions to plot data or write a program should be carried out using Matlab. In order to maintain a reasonable level of consistency and simplicity we ask that you do not use other software tools.]

If you collaborated with other members of the class, please write their names at the end of the assignment. Moreover, you will need to write and sign the following statement: “In preparing my solutions, I did not look at any old homeworks, copy anybody’s answers or let them copy mine.”

Problem 1: Expectation Maximization and Missing Data [20 points]

Consider data, D = \{( \begin{matrix}1 \\ 3 \end{matrix} ) , ( \begin{matrix}4 \\ 5 \end{matrix} ) , ( \begin{matrix}2 \\ ∗ \end{matrix} )\}, sampled from a two-dimensional

(separable) distribution, p(x_{1}, x_{2}) = p_{x_{1}}(x_{1})p_{x_{2}}(x_{2}), with

p_{x_{1}}(x_{1}) = \{ \begin{matrix}\frac{1}{θ_{1}} e^{−x_{1}/θ_{1}} if x_{1} ≥ 0 \\ 0  otherwise \end{matrix}  p_{x_{2}}(x_{2}) = \{ \begin{matrix}\frac{1}{θ_{2}}  if 0 ≤ x_{2} ≤ θ_{2} \\ 0  otherwise \end{matrix}

and a missing feature value, *.

a. What can you infer from θ_{2} by looking at D? Solution: θ_{2} is necessarily greater or equal to 5 because 0 < x_{12} = 3 <

x_{22} = 5 ≤ θ_{2}.

b. Start with an initial estimate \underline{θ}^{0} = ( \begin{matrix}3 \\ 6 \end{matrix} ) and analytically calculate

Q(\underline{θ}; \underline{θ}^{0}). This is the estimate step in the EM algorithm.

Solution: The probability of one sample can be determined by:

p(x|\underline{θ}) = p(x_{1}, x_{2}|\underline{θ}) = p_{x1}(x_{1}|\underline{θ})p_{x_{2}}(x_{2}|\underline{θ})

= \{ \begin{matrix}(\frac{1}{θ_{1}} e^{−x_{1}/θ_{1}}) (\frac{1}{θ_{2}} ) if x_{1} ≥ 0 and 0 ≤ x_{2} ≤ θ_{2} \\ 0 otherwise \end{matrix}

= \{ \begin{matrix}\frac{1}{θ_{1}θ_{2}} e^{−x_{1}/θ_{1}} if x_{1} ≥ 0 and 0 ≤ x_{2} ≤ θ_{2} \\ 0 otherwise \end{matrix}

Formulating the log likelihood of the data and marginalizing over the possible values of the unknown data:

Q(\underline{θ}; \underline{θ}^{0}) = E_{x_{32}}[ln p(x_{g}, x_{b}; \underline{θ})|\underline{θ}^{0}; D_{g}]

= ∫_{−∞}^{∞} [∑_{k=1}^{2} ln p(x_{k}|\underline{θ}) + ln p(x_{3}|\underline{θ})]p(x_{32}|x_{31} = 2; \underline{θ}^{0})dx_{32}

= ∑_{k=1}^{2} ln p(x_{k}|\underline{θ}) + ∫_{−∞}^{∞} ln p ([ \begin{matrix}2 \\ x_{32} \end{matrix} ] |\underline{θ}) \frac{p ([ \begin{matrix}2 \\ x_{32} \end{matrix} ] |\underline{θ}^{0})}{∫_{−∞}^{∞} p ([ \begin{matrix}2 \\ x′_{32} \end{matrix} ] |\underline{θ}^{0})dx′_{32}} dx_{32}

Note that x_{31} and x_{32} are independent with each other. Thus,

\begin{matrix}p ([ \begin{matrix}2 \\ x_{32} \end{matrix} ] |\underline{θ}^{0}) = p_{x_{1}} (x_{31} = 2|\underline{θ}^{0}) p_{x_{2}}(x_{32}|\underline{θ}^{0}), \\ ∫_{−∞}^{∞} p ([ \begin{matrix}2 \\ x′_{32} \end{matrix} ] |\underline{θ}^{0})dx′_{32} = p_{x_{1}} (x_{31} = 2|\underline{θ}^{0}) ∫_{−∞}^{∞} p_{x_{2}}(x′_{32}|\underline{θ}^{0})dx′_{32} = p_{x_{1}} (x_{31} = 2|\underline{θ}^{0}) \end{matrix}

Therefore,

Q(\underline{θ}; \underline{θ}^{0}) = ∑_{k=1}^{2} ln p(x_{k}|\underline{θ}) + ∫_{−∞}^{∞} ln p ([ \begin{matrix}2 \\ x_{32} \end{matrix} ] |\underline{θ}) p_{x_{2}}(x_{32}|\underline{θ}^{0})dx_{32}

Note that p ([ \begin{matrix}2 \\ x_{32} \end{matrix} ] |\underline{θ}) is different than zero if 0 ≤ x_{32} ≤ θ_{2}, and p_{x_{2}}(x_{32}|\underline{θ}^{0}) is different than zero if 0 ≤ x_{32} ≤ θ_{2}^{0} = 6. Therefore, p ([ \begin{matrix}2 \\ x_{32} \end{matrix} ] |\underline{θ})p_{x_{2}}(x_{32}|\underline{θ}^{0}) is different than zero between [0, min(θ_{2} , 6)]

∑_{k=1}^{2} ln p(x_{k}|\underline{θ}) = ln \frac{1}{θ_{1}θ_{2}} e^{−1/θ_{1}} + ln \frac{1}{θ_{1}θ_{2}} e^{−4/θ_{1}} = 2 ln \frac{1}{θ_{1}θ_{2}} − \frac{5}{θ_{1}}

∫_{−∞}^{∞} ln p ([ \begin{matrix}2 \\ x_{32} \end{matrix} ] |\underline{θ}) p_{x_{32}} (x_{32}|\underline{θ}^{0})dx_{32} = ∫_{0}^{min(θ_{2},6)} (ln \frac{1}{θ_{1}θ_{2}} e^{−2/θ_{1}}) (\frac{1}{6}) dx_{32}

= \{ \begin{matrix}θ_{2} \frac{1}{6} (ln \frac{1}{θ_{1}θ_{2}} − \frac{2}{θ_{1}} ) if min(θ_{2}, 6) = θ_{2}, where 5 ≤ θ_{2} < 6 \\ ln \frac{1}{θ_{1}θ_{2}} − \frac{2}{θ_{1}} if min(θ_{2}, 6) = 6, where θ_{2} ≥ 6 \end{matrix}

Finally,

Q(\underline{θ}; \underline{θ}^{0}) = ∑_{k=1}^{2} ln p(x_{k}|\underline{θ}) + ∫_{−∞}^{∞} ln p ([ \begin{matrix}2 \\ x_{32} \end{matrix} ] |\underline{θ}) p_{x_{32}} (x_{32}|\underline{θ}^{0})dx_{32}

= \{ \begin{matrix}2 ln \frac{1}{θ_{1}θ_{2}} − \frac{5}{θ_{1}} + \frac{1}{6}θ_{2} (ln \frac{1}{θ_{1}θ_{2}} − \frac{2}{θ_{1}} ) where 5 ≤ θ_{2} < 6 \\ 3 ln \frac{1}{θ_{1}θ_{2}} − \frac{7}{θ_{1}} where θ_{2} ≥ 6 \end{matrix}

c. Find the \underline{θ} that maximizes your Q(\underline{θ}; \underline{θ}^{0}) – the maximization step of the EM algorithm. Solution:

First,

\frac{∂Q(\underline{θ}; \underline{θ}^{0})}{∂θ_{2}} = \{ \begin{matrix}−\frac{2}{θ_{2}} − \frac{1}{6} (\frac{2}{θ_{1}} − ln \frac{1}{θ_{1}θ_{2}} ) − \frac{1}{6} where 5 ≤ θ_{2} < 6 \\ −\frac{3}{θ_{2}} where θ_{2} ≥ 6 \end{matrix}

Thus, Q(\underline{θ}; \underline{θ}^{0}) < 0 where θ_{2} ≥ 5. (Note \frac{2}{θ_{1}} − ln \frac{1}{θ_{1}θ_{2}} = \frac{1}{θ_{1}} + (\frac{1}{θ_{1}} − ln \frac{1}{θ_{1}} ) + ln θ_{2} > 0 because \frac{1}{θ_{1}} > 0, (\frac{1}{θ_{1}} − ln \frac{1}{θ_{1}} ) ≥ 1 and ln θ_{2} > 0 where θ_{1} > 0 and θ_{2} ≥ 5.)

Second, Q(\underline{θ}; \underline{θ}^{0}) is continuous at θ_{2} = 6, because the two equations corresponding to the two intervals (5 ≤ θ_{2} < 6, θ_{2} ≥ 6) have the same value at θ_{2} = 6, which is 3 ln \frac{1}{6θ_{1}} − \frac{7}{θ_{1}} .

From these two facts, we can conclude that Q(\underline{θ}; \underline{θ}^{0}) is a monotonically decreasing continuous function with respect to θ_{2}. Thus, the maximum occurs when θ_{2} = 5.

To find the value of θ_{1} that maximizes Q when θ_{2} = 5, \frac{∂Q(\underline{θ};\underline{θ}^{0})}{∂θ_{1}} =

−\frac{2}{θ_{1}} + \frac{5}{θ_{1}^{2}} − \frac{5}{6θ_{1}} + \frac{10}{6θ_{1}^{2}} = 0. Thus, we find that arg max_{θ_{1}} Q(\underline{θ}; \underline{θ}^{0}) = \frac{40}{17}

(i.e., θ_{1} = \frac{40}{17} and θ_{2} = 5).

Thus, \underline{θ} = (\frac{33}{14}, 4) and max Q(\underline{θ}; \underline{θ}^{0}) ≅ −9.0825.

Problem 2: Baum-Welch Algorithm and Discrete HMMs [40 points]

Download the datasets from the course webpage. The datasets consist of training and testing sequences belonging to two classes. We assume the two HMMs for the two classes have the same configuration, i.e. the same number of states, zero transition probabilities and the number of output states.

Implement the Baum-Welch algorithm for training a discrete HMM. Train HMMs with one, three, and five states with transition probabilities in a strictly left-to-right configuration (see the figure below for a two-state HMM in left-to-right configuration). The visible output has four possible states 0, 1, 2 or 3. and

Repeat the following steps for each of the three HMM configurations with one, three, and five states:

a. Train two HMMs, one for each class of data. State very clearly the threshold you are using and the maximum number of iterations. List the output probabilities and state transition probabilities of each HMM.

b. Implement the Viterbi algorithm to decode each test sequence using both HMMs. Show the log probability of each test sequence using each

HMM.

c. Show the confusion matrix of the test set.

Include a complete listing of your source code. Solution:

The MATLAB code for this problem can be downloaded from the course website. The code was developed by Ashish Kapoor (ash@media.mit.edu). 1.

Problem 3: Bayes Networks [20 points]

Consider the following Bayesian Network where the three events are B (Burglary), E (Earthquake) and A (Alarm). Assume that the three nodes are binary nodes that can take on the value f (false) or t (true). Here, B and E are marginally independent. That is, P (B, E) = P (B)P (E) (Note that this relation implies P (B|E) = P (B) or P (E|B) = P (E).) Now we want to show B and E are conditionally dependent given A. In other words, P (B, E|A) ≠ P (B|A)P (E|A).

a. Prove that the relation P (B, E|A) ≠ P (B|A)P (E|A) implies P (B|E, A) ≠ P (B|A). Note that by the symmetry between B and E, this also means P (E|B, A) ≠ P (E|A).

Solution: From P (B, E|A) ≠ P (B|A)P (E|A), we get the relation

\frac{P (B,E|A)}{P (E|A)} ≠ P (B|A)

Also, we know that P (B|E, A) = \frac{P (B,E|A)}{P (E|A)} by Bayes’ rule.

Therefore, P (B|E, A) ≠ P (B|A)

b. First, we consider a very simple case. Suppose A = B + E where the + sign means “Logical OR.” This means that B and E are independent deterministic causes of A. Construct the CPT (conditional probability table) for P (A |B, E).

1Copyright 2002 by the Massachusetts Institute of Technology. All rights reserved.

Permission to use, copy, or modify this software and its documentation for educational and research purposes only and without fee is hereby granted, provided that this copyright notice and the original authors’ names appear on all copies and supporting documentation.

Solution: \begin{matrix}B, E & P (A = f |B, E), P (A = t |B, E) \\ f, f & 1  0 \\ t, f & 0  1 \\ f, t & 0  1 \\ t, t & 0  1 \end{matrix}

c. For the obtained CPT above, prove that P (B = t|A = t) = P (B = t)/P (A = t). Which is greater between P (B = t|A = t) and P (B = t)? What is the meaning of this?

Solution: P (B = t|A = t) = P (A = t, B = t)/P (A = t) by Bayes’

rule. Now for P (A = t, B = t), P (A = t, B = t) = ∑_{E=t,f} P (A = t, B = t, E) (by marginalization)

= ∑_{E=t,f} P (B = t)P (E)P (A = t|B = t, E) (from the graphical model)

= P (B = t)P (E = t)P (A = t|B = t, E = t) + P (B = t)P (E = f)P (A = t|B = t, E = f) = P (B = t)P (E = t) + P (B = t)P (E = f) = P (B = t) (P (E = t) + P (E = f)) = P (B = t)

Therefore, P (B = t|A = t) = P (B = t)/P (A = t)

Since P (A = t) ≤ 1, P (B = t|A = t) ≥ P (B = t)

Note that P (B = t) means your belief on B = t (Burglary happened) without being given any information about E and A. However, P (B = t|A = t) means your belief on B = t (Burglary happened) when you know A = t (Alarm happened). Thus, P (B = t|A = t) ≥ P (B = t) means that your belief of B = t (Burglary happend) increases when you know A = t (Alarm happened).

d. For the obtained CPT above, prove that P (A = t) = P (B = t)+P (E = t) − P (B = t)P (E = t). If P (B = t) and P (E = t) are small, what happens to P (B = t|A = t), compared with P (B = t)?

Solution:

P (A = t)

= ∑_{B=t,f} ∑_{E=t,f} P (A = t, B, E)

= ∑_{B=t,f} ∑_{E=t,f} P (B)P (E)P (A = t|B, E)

= P (B = t)P (E = t)P (A = t|B = t, E = t) + P (B = t)P (E = f)P (A = t|B = t, E = f) +P (B = f)P (E = t)P (A = t|B = f, E = t) + P (B = f)P (E = f)P (A = t|B = f, E = f) = P (B = t)P (E = t) + P (B = t)P (E = f) + P (B = f)P (E = t) = P (B = t) (P (E = t) + P (E = f)) + (1 − P (B = t)) P (E = t) = P (B = t) + P (E = t) − P (B = t)P (E = t)

Thus, as P (B = t) and P (E = t) gets smaller, P (A = t) also gets smaller. Since P (B = t|A = t) = P (B = t)/P (A = t) (from (d)), P (B = t|A = t) becomes much greater than P (B = t).

e. For the obtained CPT above, prove that P (B = t|E = t, A = t) = P (B = t). Which is greater between P (B = t|E = t, A = t) and P (B = t|A = t)? What is the meaning of this? Hint: Note that the observation of Earthquake (E = t) alone is enough to explain the cause of Alarm (A = t). This occurrence is called “Explaining Away.”

Solution:

P (B = t|E = t, A = t)

= \frac{P (B=t,E=t,A=t)}{P (E=t,A=t)}

= \frac{P (B=t)P (E=t)P (A=t|B=t,E=t)}{P (E=t,A=t)} (from the graphical model)

= \frac{P (B=t)P (E=t)P (A=t|B=t,E=t)}{P (E=t)} (since P (E = t, A = t) = P (E = t))

= P (B = t)

Note that in (c), we proved P (B = t, A = t) = P (B = t). In like manner, we can prove P (E = t, A = t) = P (E = t).

Since P (B = t|E = t, A = t) = P (B = t) and P (B = t|A = t) ≥ P (B = t) (from (c)), we get

P (B = t|A = t) ≥ P (B = t) = P (B = t|E = t, A = t)

Note that P (B = t|E = t, A = t) denotes your belief on B = t (Burglary happened) when you know both Earthquake and Alarm happened (E = t, A = t). Here the observation of Earthquake (E = t) alone is enough to explain the cause of Alarm (A = t). Therefore, since the fact that Earthquake happened can “explain away” the fact that Alarm happened, there is no increase in your belief on B = t (Burglary happened). Thus, P (B = t|E = t, A = t) = P (B = t).

f. We assume that P (B = t) = 0.15 and P (E = t) = 0.005. Calculate P (A = t), P (B = t|A = t), P (B = t|E = t, A = t), P (E = t|A = t), P (E = t|B = t, A = t) by hand.

Solution:

P (A = t) = P (B = t) + P (E = t) − P (B = t)P (E = t) = 0.15 + 0.005 − 0.15 × 0.005 = 0.15425 P (B = t|A = t) = P (B = t)/P (A = t) = 0.15/0.15425 = 0.97245 P (B = t|E = t, A = t) = P (B = t) = 0.15 P (E = t|A = t) = P (E = t)/P (A = t) = 0.005/0.15425 = 0.0324 P (E = t|B = t, A = t) = P (E = t) = 0.005