COMPSCI 188 Study Guide - Midterm Guide: Cheat Sheet, Variable Elimination, Perceptron
CS 188
Fall 2013 Introduction to
Artificial Intelligence Midterm 2
•You have approximately 2 hours and 50 minutes.
•The exam is closed book, closed notes except your one-page crib sheet.
•Please use non-programmable calculators only.
•Mark your answers ON THE EXAM ITSELF. If you are not sure of your answer you may wish to provide a
brief explanation. All short answer sections can be successfully answered in a few sentences AT MOST.
First name
Last name
SID
edX username
First and last name of student to your left
First and last name of student to your right
For staff use only:
Q1. Probability: Chain Rule Madness /8
Q2. Bayes’ Nets: Representation /8
Q3. Bayes’ Nets: Independence /9
Q4. Machine Learning: Maximum Likelihood /5
Q5. Independence in Hidden Markov Models /12
Q6. Perceptron /7
Q7. Variable Elimination /9
Q8. Reduced Bayes’ Nets /6
Q9. Finding WALL-E /7
Q10. Decision Networks /14
Q11. Argg! Sampling for the Legendary Treasure /15
Total /100
1
THIS PAGE IS INTENTIONALLY LEFT BLANK
Q1. [8 pts] Probability: Chain Rule Madness
Note that the set of choices is the same for all of the following questions. You may find it beneficial to read all the
questions first, and to make a table on scratch paper.
(a) [2 pts] Fill in the circles of all expressions that are equivalent to P(A,B|C),
given no independence assumptions:
P(C|A)P(A|B)P(B)
P(C)
P(A|C)P(C|B)P(B)
P(B,C)
P(C|A,B)P(B|A)P(A)
P(B|C)P(C)
P(B,C|A)P(A)
P(B,C)
P(A|C)P(B,C)
P(C)
P(A|B, C)P(B|C)
None of the above.
(b) [2 pts] Fill in the circles of all expressions that are equivalent to P(A,B|C),
given that A ⊥⊥ B|C:
P(C|A)P(A|B)P(B)
P(C)
P(A|C)P(C|B)P(B)
P(B,C)
P(C|A,B)P(B|A)P(A)
P(B|C)P(C)
P(B,C|A)P(A)
P(B,C)
P(A|C)P(B,C)
P(C)
P(A|B, C)P(B|C)
None of the above.
(c) [2 pts] Fill in the circles of all expressions that are equivalent to P(A|B,C),
given no independence assumptions:
P(C|A)P(A|B)P(B)
P(C)
P(A|C)P(C|B)P(B)
P(B,C)
P(C|A,B)P(B|A)P(A)
P(B|C)P(C)
P(B,C|A)P(A)
P(B,C)
P(A|C)P(B,C)
P(C)
P(A|B, C)P(B|C)
None of the above.
(d) [2 pts] Fill in the circles of all expressions that are equivalent to P(A|B,C),
given that A ⊥⊥ B|C:
P(C|A)P(A|B)P(B)
P(C)
P(A|C)P(C|B)P(B)
P(B,C)
P(C|A,B)P(B|A)P(A)
P(B|C)P(C)
P(B,C|A)P(A)
P(B,C)
P(A|C)P(B,C)
P(C)
P(A|B, C)P(B|C)
None of the above.
To approach this question, try to get from each expression given as an option to the expression given as the query
(e.g. P(A,B|C)) via application of the rules of probability. Think about what additional rules become true when
a conditional independence is asserted.
3
Document Summary
Midterm 2: you have approximately 2 hours and 50 minutes, the exam is closed book, closed notes except your one-page crib sheet, please use non-programmable calculators only, mark your answers on the exam itself. If you are not sure of your answer you may wish to provide a brief explanation. All short answer sections can be successfully answered in a few sentences at most. First and last name of student to your left. First and last name of student to your right. Note that the set of choices is the same for all of the following questions. P (b,c) (cid:13) p (c|a,b) p (b|a) p (a) P (b|c) p (c) (cid:13) p (b,c|a) p (a) P (c) (cid:13) p (a|c) p (c|b) p (b) P (c) (cid:13) p (a | b, c) p (b | c) (cid:13) none of the above.
