========================================================================== CS 6660 Intelligent Agents Fall 2001 Take-Home Final Examination Assigned: December 3, 2001 Due: December 12, by 12 noon, in instructors mailbix in CCB or CRB ========================================================================== Q1. (50 points) Local minima is a very general problem faced by many AI techniques. Explain how this problem occurs in the following techniques: (a) hill climbing (b) delta rule in neural networks (c) reactive control Describe how the following techniques try to address the problem of local minima: (i) genetic algorithms (ii) simulated annealing -------------------------------------------------------------------------- Q2. (50 points) Ordering of examples is a very general issue in many techniques for incremental learning. Explain how this issue impacts the construction of the following: (a) concept definitions (b) discrimination trees (b) Bayes networks Describe why ordering of examples is, or is not, also an issue for the following methods: (i) backpropagation in neural networks (ii) reinforcement learning using temporal differences -------------------------------------------------------------------------- Q3 (50 points): Let us consider a rule-based system that has the following rules in its rule base: R1: If ?x has hair, then ?x is a mammal R2: If ?x is a mammal and ?x eats meat, then ?x is a carnivore R3: If ?x is a mammal and ?x chews cud, then ?x is an ungulate R4: If ?x is a carnivore and ?x has tawny color and ?x has dark spots, then ?x is a tiger R5: If ?x is an ungulate and ?x has white color and ?x has black stripes, then ?x is a zebra Let us now suppose that this system is given the following input about an animail called Stretch: Stretch has hair Stretch eats meat Stretch moves fast Stretch has sharp paws Stretch has tawny color Stretch has dark spots Draw the architecture of a rule-based system showing all major components and connections among them. Show how this system will establish the identity of Stretch. Show the contents of the the working memory at each stage of processing. -------------------------------------------------------------------------- Q4. (25 points) Quadtree is a popular representation for spatial knowledge. Describe the representation. Enumerate the kinds of inferences that the knowledge representation enables. Write a simple grammar for the quadtree representation language. Does this grammar capture the semantics of the representation? If yes, then how? If not, then what characterizes its semantics? -------------------------------------------------------------------------- Q5. (75 points) Let us consider the monkey-and-bananas problem. A monkey in a room wants to get some bananas hanging from ceiling. Since the bananas are too high for the monkey to reach, he pushes a movable box under the bananas and then grasps the bananas. Initially the monkey is at location A, the bananas at B and the box at C. The monkey and box have height Low and the bananas are at height High, but when the monkey climbs on the box, he reaches High. The actions available to the monkey include Go from one location to another, Push an object from one location to another, Climb onto an object, and Grasp an object. Grasping results in monkey holding the object if he is at the same height as the object. Write down the initial state description and the definitions of the four actions. Suppose that the monkey wants to fool the observing scientists, who are off having tea, by grasping the bananas but returning the box to its original location. Write this as a goal state description. Does the monkey need any other action for achieving this goal? If so, write down the definition of the action. Can a partial order planner using least commitment succeed in forming a plan to achieve the goal state? If so, show how. If not, show why and when it fails. -------------------------------------------------------------------------- Q6. (75 points) Let us assume that an inductive learner is given the following training examples, where the decision and each feature is a Boolean variable: F1 F2 F3 F4 F5 Decision Ex1 T T F F F T Ex2 F F T T F T Ex3 T F F T F T Ex4 T F T F F T Ex5 F T F F F F Ex6 T T F T T F Ex7 F T T T T F Construct the simplest decision tree using all the examples. How does this tree classify the following situation? F1 F2 F3 F4 F5 Decision Ex8 F F F T T ? A trivial algorithm for inductive learning works as follows. Create a table out of all the training examples, and determine which output occurs most often (call it d). Then, when given a test input that is not in the table, just return d. For test inputs that are in the table, return the output associated with it, or the most frequent output if there is more than one. Compare the performance of the above two learning and classification methods. -------------------------------------------------------------------------- Q7. (25 points) Both case-based and analogical reasoning involve reminding and transfer, and yet they appear quite different especially in their limiting cases. Enumerate, explain and illustrate the differences between them. -------------------------------------------------------------------------- Q8. (50 points) An admissions committee for a college is trying to determine the probability that an admitted student really is qualified. The relevant probabilities are given in the Bayes network shown below. Calculate p(A|D). A = applicant is qualified B = applicant has high grade point average C = applicant has excellent recommendations D = applicant is admitted p(A) = 0.5 * A / \ / \ / \ B * * C \ / p(B|A) = 1 \ / p(C|A) = 1 p(B|notA) = 0.5 \ / p(C| notA) = 0.5 * D p(D|B,C) = 1 p(D|B,notC) = 0.5 p(D|notB,C) = 0.5 p(D|notB,notC) = 0 ==========================================================================