### CS4341 Introduction to Artificial Intelligence  Homework - D 2001

#### PROF. CAROLINA RUIZ

This homework assignment is OPTIONAL. It will be counted as 10% of extra credit towards your final grade and is intended as practice for the final exam.

#### Instructions

• Ask in case of doubt
• This is an INDIVIDUAL homework.
• This homework assignment is OPTIONAL. It is worth 10% of extra credit towards your final numeric score.
• The deadline for this OPTIONAL homework is Friday, April 27, 2001 at 5 pm. Please turn in a HARD COPY of your homework assignment by this deadline.

• Homework Problems: This homework consists of six problems:

#### Problem 1. Decision Trees (20 points)

The following table contains training examples that help predict whether a patient is likely to have a heart attack.

 PATIENT ID CHEST PAIN? MALE? SMOKES? EXERCISES? HEART ATTACK? 1. yes yes no yes yes 2. yes yes yes no yes 3. no no yes no yes 4. no yes no yes no 5. yes no yes yes yes 6. no yes yes yes no

1. (15 points) Use information theory to construct a minimal decision tree that predicts whether or not a patient is likely to have a heart attack. SHOW EACH STEP OF THE COMPUTATION.
2. (5 points) Translate your decision tree into a collection of decision rules.

#### Problem 2. Genetic Algorithms (20 points)

Consider a genetic algorithm in which individuals are represented a triples (x,y,z), where x, y, and z are non-negative real numbers. Let the fitness function be given by f(x,y,z) = (x*x) + (y*y) + z.

Complete the following table showing the probabilities of selecting each of the individuals below according to the different selection methods. For the diversity method, suppose that the first individual in the table (4,7,2) has been selected. Compute the diversity rank for each of the remaining individuals with respect to those individuals who have already been selected (namely the first individual (4,7,2)). The distance between two individuals will be given by the Euclidean distance between them, i.e. d((x,y,z),(w,s,t)) = sqrt((x-w)^2 + (y-s)^2 + (z-t)^2), where a^2 means a to the 2nd power, or in other words a*a.

NOTE: Following Winston's notation, below I'm calling "fitness" (in quotes) the probability that an indiviual has of being selected under a given selection method.

SHOW EACH STEP OF YOUR WORK.
 Individuals Fitness  or Quality Rank Standard  "fitness" Rank  "fitness"  p=0.55 1  ----  d^2 Diversity  rank Diversity  + Quality  "fitness" (4, 7, 2) 67 (2, 5, 3) 32 (0, 2, 7) (0, 4, 3) (0, 0, 0)

#### Problem 3. Neural Networks (20 points)

Consider the table containing heart attack data from problem 1. Suppose that "yes" is represented by the number 1 and "no" is represented by the number "0". The purpose of this problem is to design a neural network and to describe the steps that would be needed to train it so that it predicts the whether or not a patient is likely to have a heart attack. (Note that you don't need to run the process on a machine, just to describe in words how the process would take place).

1. (5 points) Neural net topology:
• How many layers would you use? Why?
• How many nodes per layers would you use? Why?
• Draw a picture of your neural net.
2. (15 points) Training of the neural net:
• What does the error backpropagation algorithm search for?
• How would you initialize the weights of your net's connections?
• Carefully describe in words the steps perfomed by the error backpropagation algorithm during one epoch.
• What stopping condition would you use?

#### Problem 4. Logic-based Systems (20 points)

Consider the following set of axioms:
1. forall x [sum(x,0,x)]

2. forall x [forall y [forall z [sum(x,y,z) -> sum(x,s(y),s(z))]]]

3. forall t [exists y [sum(t,y,0)]]
And the conclusion:
• forall x [exists w [sum(x,w,s(0))]]
As usual, 0 denotes a constant; x, y, z, w, and t denote variables; the relation sum(x,y,z) can be read as x+y=z, and s denotes a function symbol, that can be interpreted as the "successor" function (i.e. the increment by 1 function).

Prove the conclusion from the axioms by refutation using resolution:

• (10 points) Translate the axioms and the negation of the conclusion into clausal form.

• (10 points) Apply resolution (state explicitly which substitutions are made) until the empty clause is found.

#### Problem 5. Planning (20 points)

Consider the following planning problem. Fred is in his living room with his robot by his side and his beer is in the kitchen. The target is to have the beer with him in the living room. More precisely,
• Initial State
{at(robot,living_room), at(beer,kitchen),at(fred,living_room), door_closed(kitchen,living_room)}

• Goal State
{at(robot,living_room),at(beer,living_room),at(fred,living_room), door_open(kitchen,living_room)}

• Operators
1. Operator 1: open(R1,R2)
```        IF at(robot,R1)
door_closed(R1,R2)
DELETE door_closed(R1,R2)
```
2. Operator 2: close(R1,R2)
```        IF at(robot,R1)
door_open(R1,R2)
DELETE door_open(R1,R2)
```
3. Operator 3: move(R1,R2)
```        IF at(robot,R1)
door_open(R1,R2)
DELETE at(robot,R1)
```
4. Operator 4: carry(R1,R2,Obj)
```        IF door_open(R1,R2)
at(robot,R1)
at(Obj,R1)