Justify all answers! 1) Consider the following variables and their immediate causes (parents): variable parents ------------------------------- A none E F B A C A D D none F B D a) Is this network a poly-tree? b) Is this network directed-path singly connected? c) Determine the truth of the following independence statements (using d-separation): 1) I({A}, {D} | {}) 2) I({A}, {D} | {F}) 3) I({A}, {D} | {F, B}) 4) I({A}, {D} | {F, B, C} 5) I({A}, {E} | {F}) 6) I({A}, {C, F} | {B}) 7) I({A}, {F} | {B, C}) d) Determine at least 2 different ways to convert the network into a tree using clustering. e) Suppose that P(A) = 0.9, P(D) = 0.3, P(B|A) = 0.1, P(B|~A) = 0.8, P(C|A) = 1, P(C|~A) = 0.5. Find P(A| B, C, E) 2) You need to construct a 4-input neural network that has value 1 in the output just when exactly 3 of its inputs are 1, and 0 otherwise (assume inputs are in {0, 1}). a) Can this be done without hidden units? b) Show a network using threshold elements that performs the required computation (specify the weights, too!) 3) A project leader in the IMG4 consortium would like to construct a decision procedure based on results from hiring employees in the earlier KITE consortium. The decision procedure will be based on a decision tree, using information in the case database. Attributes for each employee are: degree level (A), industrial work experience (B), self-motivation (C), grade in AI (D). The target attribute is the "decision", describing how good the employee is for the project. a) Construct by hand (using the greedy search using the best information gain heuristic) a consistent decision tree for the following table: input variables decision A B C D -------------------------------------------- 2 T H 95 good 2 T H 95 good 2 F H 95 good 1 F H 95 good 1 T L 70 bad 1 F L 70 bad 1 T M 95 average 1 T H 80 average b) Is a more compact (fewer internal nodes) decision tree possible for the above table? If no - prove it. If yes, which tree? 4) Consider the following investment scenario, occuring in a certain middle-eastern country. We will assume that you are risk-neutral, i.e. that your utility function is linear in the amount of money that your assets are worth. You have 1,000,000 NIS you wish to invest, with the following options: 1) Buy a house and rent it out for net gain of 40,000 NIS per year (after taxes, etc.) 2) Buy government bonds for a 5% yearly interest, out of which you need to pay 15% capital gains tax. However, there is talk that the capitals gains tax will be raised to 30% very soon, and suppose that you credit this rumor with a 0.5 probability of being accurate (and that if false, the capital gains tax will remain unchanged). a) Which of the above investments should you make as a rational agent? b) Suppose that a "friend" working at the treasury department can give you a "hint" on whether the capital gains tax will actually be raised. Given that your intended investment is for exactly one year, how much (maximum) should you as an intelligent agent be willing to pay this employee, given that 1) he is pessimistic, i.e. he will always say that taxes will be instated if they are, but if they are NOT he will say with probability 0.1 (erroneously) that there will be taxes, and 2) moral considerations are not part of your utility function. 5) a) Consider a world with the following operators: Op(Action: pickup(x) Precond: Location(Robot, y) and Location(x, y) and not Holding(x) /* Exists y such that... */ Effect: Holding(x)) Op(Action: go(from, to) Precond: Location(Robot, from) Effect: Location(Robot, to) The semantics of the Location predicate is such that an object can only be at one location. a1) The initial state is: Location(Robot, Room1) and not holding(Box1) and Location(Box1, Room2) The final state should have: Holding(Box1) Show the steps for solving this planning problem using partial-order planning (POP). a2) Add an operator that supports the robot carrying the box, and show how from the initial state how a plan is developed for achieving: Location(Box1, Room1) using POP.
Deadline: Tuesday, June 20, 2006 at 12 noon.
Note: submission (as well as WORK) on this exercise is SOLO (that is, NOT in pairs or other groups of size > 1)