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.
Note: Important question clarifications or corrections are marked with an asterisk (*), while other points that simply clarify concepts are not.

Problem Set 2:

(*) Q1: Assume all alpha_i > 1.
Q1: The question has been updated to argmax_theta P(theta | D). Please check the lastest ps2.pdf.
Q2: Implementations that are memory-efficient are preferred. An answer such as "We cache all computations in a hash map, and before each new computation we check to see if it's in the hash" is not only inefficient in terms of memory, it is computationally inefficient due to the hash lookup (practically, hash operations are not exactly O(1)). An answer that specifies exactly which computations are cached, and specifies exactly in which cases and where to find previously computed values is preferred.
Q4c: You are asked to run the usual undirected weighted maximum spanning tree algorithm, meaning that the result is an undirected tree. Thus there are many choices for the directionality of the edges in the BN given this undirected tree. However, the choice of directionality does not matter if you're using a score such as the likelihood score or BIC (think about why this is the case).
Q7: [Definition of feature]: Let D be a subset of variables. We define a feature f[D] to be an indicator function for some event defined over D, i.e., a function that takes on value 1 for some values y in Val(D) and 0 otherwise.
Q7: [Definition of log-linear model over a Markov Network]:

Quiz 8:

For question 19, please refer to the definition of Conditional Random Field (CRF) on pp.75-76 in the reader.

Programming Assignment 3:

For the last portion of question 5, the question asking to describe conditions . . ., we are looking for a very high level and simple answer. If you were faced with a new situation, and you want to learn parameters of a Bayes net, what things would you consider in deciding what parameter learning method to use? Don't worry if your answer seems a little (or a lot) obvious.
For question 2, don't worry if you get similar performance for different cases. You can also try tas_params = 6 or 7 to see the results.

Programming Assignment 2:

On page 4 of the handout pa2.pdf, it said "We can see that our approximate belief state $\hat{\sigma}^{(t)}(X^{(t)})$ is a product of...", that notation has been corrected to $\hat{\sigma}^{(t)}(X^{(t)},{\bf M})$.
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.
Although the CompareFactors function doesn't check the .var field of the factors, we would suggest you simply set SIGMA_DOT_ROBOT.var = 0.

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

In comment lines of RobotSigmaDotUpdate.m and RobotBeliefUpdate.m, the corresponding course reader session should be 11.2, not 15.2.
In RobotSigmaDotUpdate.m, you should use HEADING(t-1), not HEADING(t), to update robot belief on time t. That's shown in the DBN in Figure 2.
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 or README.txt), ensure you use legible notation.
[02/23/2009] world2.mat has been updated. Please copy the newest one.
In UnrollRoxerDBN.m, you need to properly handle the initial robot location and landmark beliefs (ROBOT_BELIEF_0 and LANDMARK_BELIEFS_0). For mine k in LANDMARK_BELIEFS_0, you have a choice over which cluster to associate the initial belief with. In order for your test to pass, you need to associate it with the cluster over M_k, X_1.
The CONDITIONAL_SENSORS structure: Our observation model returns a value D in the range 1-10. In theory it could/should be continuous, but for the sake of this assignment we have quantized the value to 10 bins. CONDITIONAL_SENSORS{d} is a factor over the robot location X and landmark location L that represents P(D = d | X, L). It is merely there for quick access. This should be the same factor as you would get from selecting D = d from the full SENSORS factor P(D | X, L).
In question #8, T(t) is a standard clique tree over X^t and M. S is a standard template clique tree (definition and examples in the reader 11.2) over X^t, X^(t+1), and M. The question doesn't specify how T(t) and S will be constructed. Actually there are many ways you can construct them based on the rules of clique tree and DBN inference.
In 8(a), it is asking what must be held in the term of scopes of cliques in S, T(t), and T(t+1). "Maximally preserving interactions" means that S can't have any more independencies than T does (in a single time slice).
In 8(b), your algorithm should work on the general condition(s) given in 8(a). You can assume that the template clique tree S is already initialized with the transition model and the sensor model. Your task is to pass the factored belief state t from T(t) to S, and to run inference on it conditioning on the observations, and then to extract the belief state at t+1 (not the fully jointed posterior distribution, but in the factored format that T(t+1) can represent.)

Quiz 5:

(*) Question 4 has been updated with a notation correction in the last equation, below the product symbol. The text explanation of how Q is constructed was correct, but the values that y ranged over in the equation was inaccurate.
(*) Question 7 has been updated with a correction in the answers and a clarification in the question.
We have added a note for Question 10 that the equations for submodularity in the book have the inequality sign incorrectly reversed.

Problem Set 1:

(*) Problem 3: For certain graphs, there may be ties between different orderings for a given function f. Since deciding which of those orderings is best a priori is not possible in general, you may assume that these ties may be broken in any arbitrary manner. That is, when you give an example graph G, you may say something like, "f_A may pick one of these two possible orderings, and I will assume that it picks the first ordering." Note: this is the opposite of what we said in office hours on Sunday night, so we apologize for the misinformation.
Problem 3: Showing a case where f_A and f_B produce an ordering with the same computation is insufficient to prove that they do not dominate each other. To show that f_A dominates f_B, for example, you must show a case where f_A's computation is less than f_B's computation.

Programming Assignment 1:

(*) The part of Question (f) that asks about CheckConvergence as well as Question (g) should both be calculated empirically using your implementations of inference for the case of no evidence in the Insurance network.
(*) Question (f) part ii) should actually read "If the message ordering is instead chosen randomly and message passing is run until convergence..."
(*) For Question (f), 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.
(*) For the first three parts of Question (f), you may assume infinite numeric precision.
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 8.3.4.2 of the book).
Clarification about the curve that is produced by det_rpc: We were technically incorrect to call it an ROC curve. It is actually a precision-recall curve (similar to ROC but defined differently). The "precision" means: what percentage of things that you label as "true" are actually true? The "recall" means: what percentage of actually true things did you label as "true"? There is a general tradeoff between precision and recall. If you label everything as "true" (by setting the threshold for labeling something as "true" to be low) then you'll have perfect recall but bad precision. If you label only the things you are very certain about (setting the threshold very high) then you may get high precision, but you'll have lower recall. As you vary the threshold between these two extremes, you'll start exploring this tradeoff, and that's what the precision-recall curve shows.
For Question (d), it means: can you use the same clique tree (or cluster graph) to perform inference on both TAS networks?

Comments to CS228 Staff