Justify all answers! 1) A) Use situation calculus (i.e. the result function, and fluents) to write down the axioms for the following modified wumpus world example. The robot needs to get the gold and climb back out. Stairs are at (1, 1) always. Actions are: a) Move(dx, dy): the robot moves by dx in the x direction, and by dy in the y direction (this robot can move omnidirectionally). b) Grab: if the gold is in the same room as the robot, the predicate HasGold becomes true as a result. c) Climb: if the robot is at the room with the stairs, the result is that the robot and all it has gets out (success). Fluents (situation-dependent predicates) are: GoldAt(x, y, s) HasGold(s) (Robot has the gold) RobotAt(x, y, s) (Robot at x, y in situation s) Success(s) (In situation s, robot and gold ouside maze) B) Now, you need to prove that, for the initial situation S where the robot is at (1,1), and the gold at (1,2), the action sequence: Move(0, 1), Grab, Move(0, -1), Climb results in success, that is, prove that: Success(result(Climb, result(Move(0, -1), result(Grab, result(Move(0, 1), S)))) Can you do it with your original formulation (show the proof!). If not, add the requisite axioms and complete the proof. 2) Write down the axioms and facts for example below in FOPC: The taxonomic hierarchy for animals, contains dogs, and cats, which are disjoint but not exhaustive. Dogs in turn contains German shepherds and chihuahuas (which are disjoint). All dogs are carnivorous. German shepherds are large. All large dogs can be guard dogs, unless they are deaf. Fido is a deaf German shepherd. a) Convert the knowledge base into IMPLICATION normal form b) Show how this knowledge-base should be indexed - using a table. c) Prove or disprove by using resolution (or argue that neither can be done): 1) Fido is an animal. 2) Fido is large. 3) Fido can be a guard dog. 4) If Fido is a chihuahua, then Fido is young. 5) Fido is carnivorous. 6) If Poopoo is a cat, then it is not a German Shepherd SHOW ALL STEPS, including the relevant unifiers, etc. d) Would using INPUT RESOLUTION only change the answers to c? e) Can you prove all the above using only either forward or backward chaining? 3) Consider the following variables and their immediate causes (parents): variable parents ------------------------------- A none E none B A C A E D A F B C A a) Is this network a poly-tree? b) Determine the truth of the following independence statements (using d-separation): 1) I({A}, {E} | {}) 2) I({A}, {E} | {B}) 3) I({A}, {E} | {C}) 4) I({A}, {E} | {F}) 5) I({A}, {C, F} | {B}) 6) I({A}, {F} | {B, C}) c) Determine at least 2 different ways to convert the network into a poly-tree using cutset conditioning. d) Suppose that P(A) = 0.9, P(E) = 0.3, P(B|A) = 0.1, P(B|~A) = 0.8. Find P(A|E) 4) You need to construct a 4-input neural network that has value 1 in the output just when exactly 2 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!) 5) a) Using the perceptron learning rule (the "delta" rule), show the steps of learning 3-input function OR with a single perceptron and a step activation function with threshold 1. Initially all weights are 0.7, and the learning rate is 0.4. b) Is it possible to combine back-propagation with simulated annealing, and if so, how? 6) a) Construct by hand a decision tree for the following table, a set of examples for classifying oranges, where the attributes are: color (A), shape (B), surface (C), and smell (D). Use the greedy algorithm studied in class, with information gain as the heuristic for deciding the attribute ate each sub-tree. input variables quality A B C D -------------------------------------------- light sphere rough sharp 1 light sphere rough mild 1 light sphere hairy sharp 0 light oval rough sharp 1 light oval rough mild 0 light oval smooth sharp 1 dark sphere hairy sharp 0 dark sphere rough mild 1 dark sphere smooth mild 1 dark oval hairy sharp 0 dark oval hairy mild 0 dark oval smooth mild 0 b) Is a decision tree with fewer internal nodes possible? Which? c) Which node will be pruned first, based on least information gain?
Deadline: Sunday, June 8, 2003, at 11AM.
Note: submission (as well as WORK) on this exercise is SOLO (that is, NOT in pairs or other groups of size > 1)