CS 228: FAQ

CS 228
Structured Probabilistic Models: Principles and Techniques
Frequently Asked Questions

FAQ Sections

This page will be updated regularly with clarifications for the problem set and other commonly asked questions.

Problem Set 4:

Problem 1: The figure referenced as a concrete example of the abstract plate model in Figure 1 is Figure 6.6 in the book. The pdf has been updated to reflect this.
Problem 1: As in the figure, there are M copies of Plate 1 and N copies of Plate 2.
Problem 1c: The hidden variables are a subset of the union, not intersection, of the sets of variables X, Y, and Z. This correction has been added to the posted handout.
Problem 1c: Clarification: Your computations for each step must be as tractable as the normal EM algorithm. For example, normal EM includes a step that runs inference, which we consider to be tractable.
Problem 3: Assume that the operators we consider during structure search only consider adding or deleting one edge at a time.

Problem Set 3:

Problem 1b: X, Y, and Z should all be state variables. This clarification has also been posted on the book wiki for Theorem 15.2.5.
Problem 2: You do not need to derive the normalized form of the Dirichlet prior. It will be Z(alpha)*product_i (theta_i ^ a_(i-1)), where the normalization constant Z will be Gamma(sum_i alpha_i)/(product_i Gamma(alpha_i)).
Problem 4: The third (rightmost) leaf of the bottom tier of Figure 1 should be (2,1,4,3).
Problem 4: You may save computations that are done to compute the BIC score from one step to the next (as long as this is efficient).
Problem 4: Your answer should consist of pseudo-code and maybe a (very short) text justification. Concise answers are best.

Programming Assignment 2:

If you have trouble passing the full Forward Inference tests, and your answers seem "close" but not exact, it is quite possible that your landmark update equations are wrong.
For question 2, when we refer to "forward-backward inference approaches" we mean the forward inference algorithm you implemented in part 1 (including the approximation part).

We have provided you with new world1.mat and world2.mat files, which contain intermediate results for our forward inference code. Loading the new world files, will define new true beliefs GOOD_FI_ROBOT_BELIEF_2, GOOD_LANDMARK_BELIEFS_2, GOOD_FI_ROBOT_BELIEF_5, GOOD_LANDMARK_BELIEFS_5, which where generated as follows:

[GOOD_FI_ROBOT_BELIEF_2 GOOD_FI_LANDMARK_BELIEFS_2] =
    ForwardInference(N,K,2,ROBOT_BELIEF_0, ...
                     LANDMARK_BELIEFS_0,HEADING, OBSERVATION,...
	             CONDITIONAL_SENSORS,...
	             TRANSITION_MODELS);
	      
[GOOD_FI_ROBOT_BELIEF_5 GOOD_FI_LANDMARK_BELIEFS_5] =
                   ForwardInference(N,K,5,ROBOT_BELIEF_0, ...
                   LANDMARK_BELIEFS_0,HEADING, OBSERVATION,...
                   CONDITIONAL_SENSORS,...
                   TRANSITION_MODELS);

You can use these to debug your Forward Inference (and Robot/Landmark belief update) code.

For your written answers, the best thing to do would be to include a README.pdf file with your submission. If you choose to use a text file (README.txt), ensure you use legible notation.
The visualization routines in ForwardInference.m do not take in the true state of the system (robot and landmark locations). You should not really need to use them at all.

Problem Set 2:

Problem 1b: Clique separator is the same thing as sepset.
Problem 2 correction: There were several typos in the original handout: we referred to the wrong page of the reader; we mentioned an outgoing message from the figure over (B,C) rather than (B,D); the cliques were called C1 and C2 rather than C0 and C1 (which didn't match the figure); there was a typo in the definition of the factored message from 2->3 over (B,D). All these have been corrected in the current version of the handout posted online (correction posted on 2/6).
Problem 2: It should be the case that *if* the incoming messages were exact marginals, the outgoing approximate marginals would be marginals of the exact (full) outgoing message. That is, in the example for part (a), if the incoming messages delta(A) and delta(D) were exact, then the approximate outgoing factors delta(B) and delta(D) would be marginals of the exact outgoing message delta(B,D).
Problem 5: P_m^t(L) is the distributional part of the particle that is equal to P(L | x^(1:t)[m],o^(1:t)[m]).
Problem 5: For part (b)ii., the weight of particle m should be P(o^(t+1)[m] | x^(1:t+1)[m], o^(1:t)[m]).
Problem 5: In addition to the observation and transition models, you are also given the prior probability of each L_i, P(L_i).
Problem 5: It would be helpful for this problem to do the reading from section 15.3 in the book.
Problem 5: You may consider all variables to be discrete; the analysis is the same whether they are discrete or continuous.

Programming Assignment 1:

The graph-viewing application 'dot' seems to have problems on some of the Stanford machines. It should work from myth.stanford.edu, so try to ssh to there if you want to do any visualization.
Instructions on submitting the assignment can be found here.
In general, it is possible for a clique (or cluster) to have no factors assigned to it initially. In this case, instead of setting the initial clique potential to be the product of the factors assigned to the clique, you can set the potential to be all 1's -- similar to how messages are initialized to 1's in Cluster Graph message passing. In our implementation of the programming assignment, you can also simply leave the initial potential empty (as they are initalized in line 34 of CliqueTreeCalibrate.m) in this case, because FactorProduct will produce the same output either way.
For those who are interested, the cluster graph that we've provided (insurance_cluster_graph) was constructed using the Bethe approximation (described in Section 12.2.4.2 of the book).
For question (e), part i) asks what would happen if we used a different ordering while still respecting the "ready clique" criteria, while part ii) asks what would happen if we used a random ordering that may not respect that criteria.
Question (e) part ii) should actually read "If the message ordering is instead chosen randomly and message passing is run until convergence..."
Question (f) should be calculated using your implementation of exact and approximate inference for the case of no evidence in the Insurance network.

Problem Set 1:

Problem 1 incorrectly referred to Definition 2.1.3 for the definition of conditional independence. This has been corrected to 2.1.4.
Definition 2.1.4 has an important typo: the end of the statement should read "... or if P(beta intersect gamma) = 0" rather than "... or if P(alpha intersect gamma) = 0". This correction has also been posted to the book wiki.
Problem 2a. The variables listed in the text are not in topological order, they are simply the set of variables in the network. A valid topological order is: B, E, S, A, N, J, M.
Problem 4: Concept number corrected from 4.3 to 4.2.

Comments to CS228 Staff