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
|
- (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.
- (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).
Answer the following question and explain your answers:
- (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.
- (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:
- forall x [sum(x,0,x)]
- forall x [forall y [forall z [sum(x,y,z) -> sum(x,s(y),s(z))]]]
- 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
- Operator 1: open(R1,R2)
IF at(robot,R1)
door_closed(R1,R2)
ADD door_open(R1,R2)
DELETE door_closed(R1,R2)
- Operator 2: close(R1,R2)
IF at(robot,R1)
door_open(R1,R2)
ADD door_closed(R1,R2)
DELETE door_open(R1,R2)
- Operator 3: move(R1,R2)
IF at(robot,R1)
door_open(R1,R2)
ADD at(robot,R2)
DELETE at(robot,R1)
- Operator 4: carry(R1,R2,Obj)
IF door_open(R1,R2)
at(robot,R1)
at(Obj,R1)
ADD at(robot,R2)
at(Obj,R2)
DELETE at(robot,R1)
at(Obj,R1)
(20 points) Follow in detail the backward chaining algorithm described in Chapter 15 to
construct a plan to go from the initial situation
to the goal situation.
Show establishes, threatens, and before links.
Problem 6. Machine Vision (20 points)
Solve problem 26.1 from your textbook. See pages 682-683.
Explain your answer.
Please note that there MIGHT be a typo on the first table in that
problem (page 682), depending on the edition of your textbook.
Point B should have an x-value of 3.0 and point C should have an
x-value of 0.
