Due: 11:59pm, Friday, Dec. 5, 2008

Total points: 65

Refer to the web page for policies regarding collaboration, due dates, and extensions.

**Particle-Based Approximate Inference #1**

**[15 points]**(programming)

Implement likelihood weighting on the elaborate model of recommendation from subquestions C and D in Homework #2's Part 4 (Clique Trees). Use the same conditional probability tables and parameter values. Answer the same queries as before in subquestion D using different numbers of samples: 10, 100, 1000, 10000, and 100000 samples.

**Particle-Based Approximate Inference #2**

(KF Exercise 11.10) Regular Markov chains**[20 points]**Consider the following two conditions on a Markov chain

*T*:- It is possible to get from any state to any state using a positive probability path in the state graph.
- For each state
*x*, there is a positive probability of transitioning directly from*x*to*x*(a self-loop).

Answer the following questions:

- Show that, for a finite-state Markov chain, these two conditions together imply that
*T*is regular. - Show that regularity of the Markov chain implies condition 1.
- Show an example of a regular Markov chain that does not satisfy condition 2 (with a short explanation of why this is such an example).
- Now let's weaken condition 2, and require only that there exists
*some*state*x*with a positive probability of transitioning directly from*x*to*x*. Show that this weaker condition and condition 1 together still suffice to ensure regularity.

**Learning Undirected Models #1****[10 points]**

(KF Exercise 19.1)

**Note. You should assume the following:**- All X's and Y's are discrete, binary variables.
- All factors (for the original, unconditioned Markov network) are clique factors (pairwise factors).

I.e. don't use (non-reduced) factors with a single variable in their scope. - All factors &phi
_{a,b}(Y_{i}, Y_{j}) or &phi_{a,b}(Y_{i}, X_{j}) are indicator functions.

For example, for the clique {Y_{1}, X_{1}}, we will have four indicator functions:- &phi
_{0,0}(Y_{1}, X_{1}) = Indicator(Y_{1}=0, X_{1}=0) - &phi
_{0,1}(Y_{1}, X_{1}) = Indicator(Y_{1}=0, X_{1}=1) - &phi
_{1,0}(Y_{1}, X_{1}) = Indicator(Y_{1}=1, X_{1}=0) - &phi
_{1,1}(Y_{1}, X_{1}) = Indicator(Y_{1}=1, X_{1}=1)

_{1,1}^{xy}(sorry about the clumsy formatting) will be

a length four vector with one element for each of the above indicator functions. - &phi

**Hint:**Use Koller-Friedman equation 19.7 (gradient for log**conditional**likelihood).**Learning Undirected Models #2****[10 points]**

KF Exercise 19.12:

Let**H***be a Markov network where the maximum degree of a node is d*. Show that if we have an infinitely large data set D generated from**H***(so that independence tests are evaluated perfectly), then the Build-Skeleton procedure of Figure 3.17 (reproduced below) reconstructs the correct Markov structure**H***.

Koller-Friedman Figure 3.17:

Algorithm for recovering undirected skeleton given a distribution

**Inference in Hybrid Networks #1****[10 points]**

(KF Hybrid Networks chapter handout, Exercise 13.1)

Let**X**and**Y**be two sets of continuous variables, with |**X**|= n and |**Y**| = m.

Let p(**Y**|**X**) = N(**Y**;**a**+B**X**, C) where**a**is a vector of dimension m, B is an m × n matrix, and C is an m × m variance-covariance matrix. This dependence is a multi-dimensional generalization of a linear Gaussian CPD. Show how p(**Y**|**X**) can be represented as a canonical form.

**Inference in Hybrid Networks #2**

Dropped from assignment (topic not covered in lecture due to time constraints).