CS228 Weekly Quiz

CS228: Probabilistic Methods in AI
Winter 2008
Weekly Quiz

Overall Score Statistics:
Mean	Median	Mode	Lowest	Highest
90.82%	90%	100% (27)	50%	100%

Score Frequency Table

Frequency of Scores
Score	Number of Students
100%	27
90%	23
80%	4
70%	4
60%	2
50%	1

Detailed Question/Answer Statistics:

Question 1: In the clique tree below which of the following starting message - passing orders is valid? Answers: 1. C1->C2, C2->C3, C3->C4, C3->C5 2. C1->C2, C2->C3, C5->C3, C3->C4 3. C4->C3, C3->C5, C3->C2 4. C4->C3, C3->C5, C2->C3
Type	Answer	Responses	Percent
Correct:	C1->C2, C2->C3, C5->C3, C3->C4	61	100%
Distractor:	C1->C2, C2->C3, C3->C4, C3->C5	0	0%
Distractor:	C4->C3, C3->C5, C3->C2	0	0%
Distractor:	C4->C3, C3->C5, C2->C3	0	0%
Question 2: In the clique tree above, what is the form of the message from clique 3 to clique 4 where is the initial potential of clique i. Answers: 1. 2. 3. 4.
Type	Answer	Responses	Percent
Correct:	<img src="http://www.stanford.edu/class/cs228/Images/Quiz3/new_qn/img5.png" >	59	97%
Distractor:	<img src="http://www.stanford.edu/class/cs228/Images/Quiz3/new_qn/img4.png" >	1	2%
Distractor:	<img src="http://www.stanford.edu/class/cs228/Images/Quiz3/new_qn/img6.png" >	0	0%
Distractor:	<img src="http://www.stanford.edu/class/cs228/Images/Quiz3/new_qn/img7.png" >	1	2%
Question 3: Consider the pairwise MRF, H, shown below with potentials over {A,B}, {B,C}, {A,D}, {B,E}, {C,F}, {D,E} and {E,F}. Which of the following are not valid cluster graphs for H? Answers: 1. (1) only 2. (2) only 3. (3) only 4. (2) and (3)
Type	Answer	Responses	Percent
Correct:	(2) only	52	85%
Distractor:	(1) only	3	5%
Distractor:	(3) only	1	2%
Distractor:	(2) and (3)	5	8%
Question 4: Which of the following is true regarding the differences between belief propagation over a clique tree and a cluster graph? Answers: 1. using a cluster graph is always preferable 2. using a clique tree and a cluster graph both result in exact answers, but using a cluster graph may be faster 3. clique tree BP is exact but may be intractable, while cluster graph BP is approximate but is often tractable even when clique tree is not 4. using a clique tree is preferable because it is exact, but one may not exist for all graphical models
Type	Answer	Responses	Percent
Correct:	clique tree BP is exact but may be intractable, while cluster graph BP is approximate but is often tractable even when clique tree is not	54	89%
Distractor:	using a cluster graph is always preferable	0	0%
Distractor:	using a clique tree and a cluster graph both result in exact answers, but using a cluster graph may be faster	1	2%
Distractor:	using a clique tree is preferable because it is exact, but one may not exist for all graphical models	5	8%
Question 5: Which of the following ideas can not be used to help handle the problem of non-convergence of Generalized Belief Propagation? Answers: 1. Stopping BP after a fixed amount of time regardless of complete convergence 2. Removing edges from the cluster graph until convergence is achieved 3. Intelligent message scheduling heuristics 4. Dampening changes to messages in successive iterations%%
Type	Answer	Responses	Percent
Correct:	Removing edges from the cluster graph until convergence is achieved	57	93%
Distractor:	Stopping BP after a fixed amount of time regardless of complete convergence	1	2%
Distractor:	Intelligent message scheduling heuristics	2	3%
Distractor:	Dampening changes to messages in successive iterations%%	0	0%
Question 6: Consider the process of rejection sampling to generate samples from the posterior distribution P(X \| e). If we want to keep M samples, what is the expected number of samples that would need to be drawn from P(X)? Answers: 1. M * P(X \| e) 2. M * P(e) 3. M * (1 - P(e)) 4. M / P(e)
Type	Answer	Responses	Percent
Correct:	M / P(e)	55	90%
Distractor:	M * P(X &KPHHASH124; e)	0	0%
Distractor:	M * P(e)	3	5%
Distractor:	M * (1 - P(e))	3	5%
Question 7: If we are given 123 independent samples {X[1], ..., X[123]} from a Bernoulli distribution with p = .15, from which we compute an estimate what bounds can we give for the probability that we will be within 0.1 of the correct value of p? That is, what is the smallest d such that Answers: 1. 0.1709 2. 0.5846 3. 4.143e-7 4. 1.0%%
Type	Answer	Responses	Percent
Correct:	0.1709	53	87%
Distractor:	0.5846	6	10%
Distractor:	4.143e-7	1	2%
Distractor:	1.0%%	0	0%
Question 8: Consider using likelihood weighting sampling in the network below to estimate the conditional probability P(A\|C=0). Assume we have just sampled a particle with A = 0. What will be the weight of the particle? Answers: 1. 0.02 2. 0.1 3. 0.5 4. 0.2
Type	Answer	Responses	Percent
Correct:	0.1	51	84%
Distractor:	0.02	3	5%
Distractor:	0.5	1	2%
Distractor:	0.2	6	10%
Question 9: Consider using unnormalized importance sampling to estimate the expected value of some function relative to P(X,Y) defined by a Bayesian network over binary-valued variables, X and Y. Suppose we sample from a proposal distribution Q(X,Y) = Q(X)Q(Y) with Q(x⁰) = Q(y⁰) = 0.6. We draw sample <x¹, y⁰>. What correction weight should be applied to the sample? Answers: 1. (0.6 * 0.5) / (0.4 * 0.6) 2. (0.4 * 0.6) / (0.6 * 0.5) 3. (0.4 * 0.7) / (0.4 * 0.6) 4. (0.4 * 0.6) / (0.4 * 0.7)
Type	Answer	Responses	Percent
Correct:	(0.4 * 0.7) / (0.4 * 0.6)	54	89%
Distractor:	(0.6 * 0.5) / (0.4 * 0.6)	0	0%
Distractor:	(0.4 * 0.6) / (0.6 * 0.5)	1	2%
Distractor:	(0.4 * 0.6) / (0.4 * 0.7)	6	10%
Question 10: If we are doing importance sampling in the following Bayesian Network, which operations are necessary to create a mutilated network for evidence C=c? . i) remove edge C -> D, C->E ii) remove edges A->C, B->C iii) alter the CPDs of D and E iv) remove edge B->E v) alter the cpd of C Answers: 1. i) ii) and v) 2. i) and iii) 3. ii) and v) 4. iii) and iv) 5. all of them
Type	Answer	Responses	Percent
Correct:	ii) and v)	58	95%
Distractor:	i) ii) and v)	2	3%
Distractor:	i) and iii)	1	2%
Distractor:	iii) and iv)	0	0%
Distractor:	all of them	0	0%