\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?

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.

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

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.

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).