Homework #3 -- Cmput651 (Fall 2008)

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

Total points: 65

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


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


  2. Particle-Based Approximate Inference #2
    (KF Exercise 11.10) Regular Markov chains
    [20 points]

    Consider the following two conditions on a Markov chain T:

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

    Answer the following questions:

    1. Show that, for a finite-state Markov chain, these two conditions together imply that T is regular.
    2. Show that regularity of the Markov chain implies condition 1.
    3. 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).
    4. 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.

  3. Learning Undirected Models #1
    [10 points]
    (KF Exercise 19.1)





    Note. You should assume the following:
    1. All X's and Y's are discrete, binary variables.
    2. 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.
    3. All factors &phia,b(Yi, Yj) or &phia,b(Yi, Xj) are indicator functions.
      For example, for the clique {Y1, X1}, we will have four indicator functions:
      • &phi0,0(Y1, X1) = Indicator(Y1=0, X1=0)
      • &phi0,1(Y1, X1) = Indicator(Y1=0, X1=1)
      • &phi1,0(Y1, X1) = Indicator(Y1=1, X1=0)
      • &phi1,1(Y1, X1) = Indicator(Y1=1, X1=1)
      In this case, the parameter vector &theta1,1xy (sorry about the clumsy formatting) will be
      a length four vector with one element for each of the above indicator functions.

    Hint: Use Koller-Friedman equation 19.7 (gradient for log conditional likelihood).

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


  5. 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 +BX, 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.

  6. Inference in Hybrid Networks #2
    Dropped from assignment (topic not covered in lecture due to time constraints).