UIUC, CS498, Section EA - Autumn 04 - Final Sample (3 hours)Given by: Eyal AmirDecember 13, 20041 Short Questions (20%)Circle the most appropriate answer1. The Markov Blanket of a variable X within a Bayes Net consists exactly of(a) parents of X(b) children of X(c) (1a) and (1b)(d) (1a) and (1b) and parents of children of X2. Let hX1, ..., Xni be a total ordering of the variables in a Bayes Net, where for all 1 ≤ i ≤ n all themembers of P a(Xi) appear before Xiin the ordering. The following defines the semantics of the BayesNet:(a) P (Xi) = P (P a(Xi))(b) P (Xi) = P (Xj) for all Xjin P a(Xi)(c) P (Xi) = P (Xj) for all Xjin the Markov Blanket of Xi(d) P (X1, ..., Xn) =Qni=1P (Xi|P a(Xi))3. In a stationary Dynamic Bayes Net with n binary state variables and a transition model linking everyvariable at time t + 1 to exactly one variable at time t, the number of parameters required for a beliefstate at time t with no observations (starting from a fully factored belief state at time 0) is(a) n(b) n2(c) 2n− n(d) 2n4. A multi-variate gaussian with n variables takes the following time to compute a marginal over mvariables(a) O(mn)(b) O(m2n)(c) O(n2m)(d) O(n3)(e) other5. Gibbs sampling may not converge1(a) over a Bayes Net that is fully factored(b) over a Markov Field that is fully connected(c) over a Bayes Net with an OR node (X takes the value X = Y ∨ Z deterministically)(d) over a naive-Bayes model2 The Hanks-McDermott shooting problem (20%)The Hanks-McDermott shooting problem (sometimes refered to as the “Yale shooting Problem”) is thefollowing story: A person can be either ALIVE or DEAD . A gun can be either LOADED or UNLOADED.At a known situation the person is alive. A gun becomes loaded whenever a LOAD action occurs. Any timea person is shot (i.e., a SHOOT action) with a loaded gun, he becomes dead.1. Formalize the problem in Situation Calculus. Emphasize which are your Frame Axioms.2. Write successor-state axioms instead of your Effect and Frame Axioms.3. Show the process of LOAD;SHOOT as a chain of situations, emphasising what sentences are true ineach situation.4. Add the action WAIT (with the apropriate axioms) to your database. Show the process of LOAD;WAIT;SHOOTas a chain of situations, emphasising what sentences are true in each situation.3 Probabilistic Graphical Models (20%)1. Give an algorithm for deciding d-separation in a Bayes Network (with some variables observed).2. Prove that your algorithm is correct (i.e., correctly reflects conditional independence) from the defini-tion of Bayes Net semantics that you chose in problem 1.4 Dynamic Probabilistic Graphical Models (20%)1. Give an algorithm for smoothing in a DBN.2. Suppose we relax the Markov assumption and make it a second-order Markov assumption. Describebriefly how you will change the algorithm above to compute the smoothed belief state at time k.5 Paramodulation (20%)Joe’s phone number is the same as Jill’s phone number. We know that this can happen only when the twopeople live in the same house. Mary lives in the same house as Bob, but they have different phone numbers.Finally, we also know that Joe’s house has exactly one phone line.1. Represent this information using FOL (with equality).2. Prove using paramo dulation that Mary or Bob do not live in the same house as Jill.3. Can you prove the same with demodulation? Is so, prove it. Otherwise, argue why
View Full Document
Unlocking...