WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

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


  • 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 

    ---- 
    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:

    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: 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:


    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, (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.