Exam 2

810:161

Artificial Intelligence

Fall Semester 2001

Instructions

• The exam consists of ten questions, two algorithms, and one figure, on three pages.
  Be sure that you have all of these items and that they are all legible.

• Read all questions and their instructions thoroughly before you begin.
  It is almost always worth your time to plan ahead!

• You have also been given three blank pages. Use these sheets for your exam answers.
  Be sure to write your name on each sheet.

• The exam is worth 100 points. Each problem is worth 10 points.

• Keep the exam questions when you are done, for future reference.

• Points will be awarded based on your explicit answers.
  Partial credit will be given where possible, so show all of your work.

• The exam lasts seventy-five (75) minutes. It is due at 3:15 PM.

Problems

1. Why are intelligent agents often forced to act from a position of uncertainty? What are some of the effects of uncertainty on the agent's reasoning and learning processes?

2. Intelligent agents must sometimes explain their reasoning to other intelligent agents.
   Briefly answer these questions about explanation in the context of rule-based reasoning.

   • What makes a good explanation?

   • What information does the agent have to keep track of in the course
     of reasoning in order to make explanation possible?

   • What kind of changes must we make to our logical inference engines
     in order to implement an explanation facility?

3. When building a learning agent, we usually divide the set of examples available to the program into a training set and a test set. Describe the role of these two sets in the process of learning, and discuss some of the issues involved in the dividing process.

4. The "Principle of Convergent Intelligence" states:

   The world manifests constraints and regularities. If an agent is to exhibit intelligence, then it must exploit these constraints and regularities, no matter the nature of its physical make-up.

   What does this principle say about intelligent agents that learn?

5. Show your work as you execute the first pass of the induction algorithm on the data given in this table:

                Apples  Fish  Grapes  Honey  |  Reaction
                ----------------------------------------
             1  yes     yes   yes     yes    |  yes
             2  no      yes   yes     no     |  no
             3  yes     no    no      no     |  yes
             4  yes     no    no      no     |  no
             5  yes     yes   no      yes    |  yes
             6  yes     yes   no      no     |  no
             7  no      yes   no      yes    |  no
   

   At the end of your answer, show the root node of the decision tree and the subset of the cases to be solved on each of the recursive calls.

6. Reproduction of rules or programs is a central idea in the genetic learning metaphor.

   • Describe the three forms of reproduction.

   • Give an example of each.

   • What role does each play in helping the system to learn?

7. In the context of genetic algorithms, what is a fitness function? What role does it play in helping the system to learn?

8. In class, we discussed the story of Zog, the geek caveman roasting his lizard on the end of a pointed stick. Watching him in amazement was a crowd of his less intellectual peers, who had been using their bare hands to hold their food over the fire. From this one experience, the onlookers were able to learn the general principle of painless cooking.

   Explain how they were able to learn a concept from a single example.

9. One of the three key ideas that underlie machine planning is that a planner should be able to decompose its problem into sub-tasks, solve them separately, and then assemble its solution.

   Briefly discuss why this idea is so important. Describe the differences in how goal-stack planning and plan-space planning implement this principle.

10. Explain how the the plan-space planning algorithm can create a plan to solve Sussman's anomaly, whereas the goal-stack planning algorithm cannot.

Appendices

The induction algorithm:

input:

• examples, a training set
• attributes, a set of attributes
• default, the default goal predicate value

output: a decision tree

1. if examples is empty, then return default

2. if all of the remaining examples have the same classification, then return that value

3. if attributes is empty, then return the most common classification of the remaining examples

4. choose the attribute a that best discriminates among the remaining examples

5. create a tree t with a as its root

6. for each possible value v of a
   • select the subset of examples ex having value(a) = v
   • let subtree sub be the result of recursively calling the induction algorithm with ex, (attributes - a), and the most common classification of ex
   • add a branch to t with label v and subtree sub

7. return t

The plan-space planning algorithm:

1. P := empty-plan(I, G)
2. Loop:
   • If P is a solution, return P.
   • Choose F := a flaw in P.
   • Choose M := a method for fixing F in P.
   • If there is no such method, return failure.
   • P := fix-flaw(P, F, M).

Sussman's Anomaly