====================================================================== CS 4611 and CS 7611 AI Problem Solving Spring 2004 Mid-Term Exmination ---------------------------------------------------------------------- Question 1. In class we discussed a matching procedure using semantic networks based on Chapter 2 of the Winston textbook. That procedure cannot address the following problem (A:B::C:?): above A: triangle --------> square B: square left-of C: triangle ---------> circle 1: circle 2: triangle Q1(a): Why cannot the Winston procedure (which is initially due to Evans 1968) address the above problem? Q1(b): How can you generalize the procedure to address this problem? ---------------------------------------------------------------------- Question 2. Let Abbot, Babbitt and Cabot be suspects in a murder case. Abbott has an alibi, in the register of a respectable hotel in Atlanta. Babbitt also has an alibi, for wife his testifies that Babbitt and she were together. Cabot pleads an alibi too, claiming to have been watching a car race at the time of the murder, but we have only his word for it. Further investigation reveals that the murder victim left all his estate to Cabot. So Cabot becomes the prime suspect in the case. Fortunately for him, he is able to find a TV film that captured him at the car race, which validates his alibi. Consider the above assertions in the chronology given above. Q1(a) Show how a truth maintenance system may first reach the conclusion that Cabot committed the murder. Q1(b) Show how the TMS may retract the above conclusion later, when the evidence on the TV film becomes available. ---------------------------------------------------------------------- Question3. Let us consider a computer program whose task is to learn the concept of blocking in Tic-Tac-Toe. initial example: O ? X (blocking ? O ? (enemy-positions (two (row1,col1) (row2,col2))) ? ? X! (friendly-positions (one (row1,col3))) (take-position row3,col3)) Q3(a): Show how the program's concept of blocking may evolve as it is shown the following examples (where X! is a blocking move): positive example: O ? X O ? ? X! ? ? negative example: O ? X O X! ? ? ? ? negative example: O ? ? ? X! ? ? ? ? Q3(b): How does the learning in this example depend on the order of the examples shown above? Q3(c): Your answers above (probably) assumes that the program already has some conceptual knowledge about {\tt Tic-Tac-Toe}? What is this prior conceptual knowledge? ====================================================================== ====================================================================== CS 4611 and CS 7611 AI Problem Solving Spring 2004 Final Exmination ---------------------------------------------------------------------- General Notes: Please answer all questions. You may consult your class notes, including notes posted on the class webpage, as well as handouts given out in the class. Please be specific and percise. Use ilustrations and examples for clarity. ---------------------------------------------------------------------- Question 1 (15 points): Let us suppose that you have the folowing experiences of dining out: Number Restaurent Meal Day Cost Enjoyed? Ex1 Jason's Dinner Saturday Cheap Yes Ex2 Mary's Lunch Saturday Expensive No Ex3 Jason's Lunch Friday Cheap Yes Ex4 Susan's Dinner Sunday Cheap No Ex5 Jason's Dinner Sunday Expensive No In this table, the last column tells whether or not enjoyed your meal, where Meal and Cost are Boolean variables, and Restaurant and Day are multi-valued. Let us suppose the above table is given as input to a standard algorithm for learning conecpts by maintaining different versions for the concept. This algorithm assumes that the first example is always a positive instance of the concept. Let us suppose that the first two rows in the table are switched so that the first example is a negative instance. Does the method of version space converge? Does it converge to the same concept as the original table? ---------------------------------------------------------------------- Question 2 (10 points). What is a "concept" (or, equivalently, a "category")? Give some examples of concepts/categories. Show how the axiomatic concept of a triangle can be represented in logic. Show how the prototypical concept of a dog can be represented by a frame. Classification (or, equivalently, categorization) appears to be ubiquituous in knowledge-based AI. Why? That is, what is the power of classification? ---------------------------------------------------------------------- Question 3 (10 points): The abduction task is characterized as inference to the best explanation for a set of data. Explain why medical diagnosis is an example of the abduction task. Describe (and critique) the method of deductive logic to address the diagnosis task. Describe (and critique) the method of probabilistic reasoning to address the diagnosis task. ---------------------------------------------------------------------- Question 4 (15 points): A simple set-theoretic characterization of the abduction task in Q3 is as follows: D is a set of data DO is a set of observed data H is a set of hypotheses Each hypothesis in H can account for some subset of D ----- Compute HE, a minimal subset of H, that can account for all of DO. This is equivalent to the set-cover problem for which exist many algorithms. Briefly describe any set-cover algorithm you know (or design one). The abduction task becomes specially complex when hypotheses in H can interact with one another. Briefly enumerate some of the possible interactions. How might the set-cover algorithm be modified to accommodate these interactions. =================================================================== Question 5 (10 points): Both case-based and analogical reasoning involve reminding and old problems and transfer of parts of their solutions to new problems. What (if any) are the differences between the two? For what class of problems or situations is case-based reasoning most effective? Analogical Reasoning? =================================================================== Question 6 (5 points): Visual and spatial reasoning are closely related. What (if any) is the difference between visual and spatial reasoning? =================================================================== Question 7 (15 points): What is a "model"? What is "model-based reasoning"? What kinds of inferences does it enable? What is "model-based autonomy"? Design a model-based autonomous robot that can cook a meal for you. Give its high-level architecture; describe the main components and connections among them; explain each major component would work. ====================================================================== Question 8 (15 points): Ever since Samuel's checkers playing program in the fifties, the credit assignment problem has been considered as an important problem in AI. What is the credit assignment problem? Why is it important? Describe how the method of model-based reasoning may address the credit assignment problem in a game-playing program. ====================================================================== Question 9 (5 points): AI research on meta-reasoning raises the issue of infinite regression of meta-reasoning (meta-meta-reasoning and so on). However, AI researchers claim that an intelligent agent needs only two levels: a base (or object) level of reasoning and a meta-level. Why? ======================================================================