CS4341 Introduction to Artificial Intelligence. D-2001
SOLUTIONS Exam 2 - May 1, 2001

By Chris Shoemaker, Songting Chen, and Carolina Ruiz
Department of Computer Science
Worcester Polytechnic Institute

Instructions

Problem 1. Decision Trees (20 points)

The following table of contains information on whether patients were sent home the day after an operation.

PATIENT ID MAJOR OPERATION? FAMILY AT HOME? OLD? SENT HOME?
1. yes no no no
2. yes no yes no
3. no no no yes
4. no no yes no
5. no yes yes yes

  1. (15 points) Use information theory to construct a minimal decision tree that predicts whether or not a patient is likely to be sent home the day after an operation.
    SHOW EACH STEP OF THE CALCULATIONS. 
                     x      1  1/4  2/3  3/4  1/3  1/2
          ---------------------------------------
           log_2(x)     0   -2 -0.6 -0.4 -1.6  -1

     

    Since Major Operation is the attribute with the lowest entropy, we select it as the root node.  we select it.  The partially constructed tree so far is:

                                        Major Operation
                                       /                           \
                               Yes /                              \ No
                                  1-, 2-                            3+, 4-, 5+
                                                                   

    Only the branch corresponding to Major Operation = no needs further processing.

     

    Since both attributes have the same entropy, we select either one, for example, Family at Home.  The partially constructed tree so far is:

                                        Major Operation
                                       /                           \
                               Yes /                              \ No
                                  1-, 2-                            \    3+, 4-, 5+
                                                                    Family at Home
                                                                  /                           \
                                                          Yes /                              \ No
                                                               5+                              3+, 4-
                                                                                               

    Only the branch corresponding to Family at home = no needs further processing.  Since Old is the last remaining attribute, we select it.  The resulting tree is:

                                        Major Operation
                                       /                           \
                               Yes /                              \ No
                                  1-, 2-                            \    3+, 4-, 5+
                                                                    Family at Home
                                                                  /                           \
                                                          Yes /                              \ No
                                                               5+                              \
                                                                                                Old    3+, 4-
                                                                                              /         \
                                                                                      Yes /            \ No
                                                                                            4-              3+

Problem 2. Genetic Algorithms (20 points)

Consider a genetic algorithm in which individuals are represented using a 5-bit string of the form b1b2b3b4b5. An example of an individual is 001001 for which b1=0, b2=0, b3=1, b4=0, b5=1.

The fitness function is defined over these individuals as follows:
f(b1b2b3b4b5) = b1 + b2 + b3 + b4 + b5 + AND(b1,b2,b3,b4,b5),

where AND(b1,b2,b3,b4,b5)=1 if b1=b2=b3=b4=b5=1; and AND(b1,b2,b3,b4,b5)=0 otherwise.

Answer the following questions. SHOW EACH STEP OF YOUR WORK.

  1. (10 points) Selection Complete the following table showing the probabilities of selecting each of the individuals below according to the standard selection method.
    NOTE: Following Winston's notation, below I'm calling "fitness" (in quotes) the probability that an individual has of being selected under a selection method.
    
  Individual     Fitness               Standard "fitness"
                 or quality            or probability of  
                                       being selected

  00101          0+0+1+0+1+0 = 2       2/14 = .14

  11101		 1+1+1+0+1+0 = 4       4/14 = .29

  00000		 0+0+0+0+0+0 = 0       0/14 = 0

  10010		 1+0+0+1+0+0 = 2       2/14 = .14

  11111  	 1+1+1+1+1+1 = 6       6/14 = .43

                            -------
                              14

  2. (5 points) Crossover Suppose that a single crossover point will be used for crossover. This point has been chosen as the point between the 2nd and the 3rd bits (i.e. between b2 and b3). Show the two offspring that will result from crossing over the following two individuals: 

         PARENTS                     OFFSPRING:
  
     First parent:  00.101       First offspring:  00111

     Second parent: 10.111       Second offspring: 10101

  3. (5 points) Mutation Explain how the standard mutation method is applied after selection and crossover to form the "next" generation of a population.

    For each individual, a bit of the individual will be randomly selected and it will be flipped with a given "mutation rate" probability.

     

Problem 3. Logic-based Systems (20 points)

Consider the following set of axioms:
  1. Every investor bought stocks.
    forall x [investor(x) -> bought(x,stocks)]

  2. If the Dow-Jones Average crashes, then all stocks fall.
    crashes(dow-jones) -> fall(stocks)

  3. Every person who bought something that falls is not happy.
    forall y [forall z [[bought(y,z) && fall(z)] -> !happy(y)]]

  4. Ralph is an investor.
    investor(ralph)

  5. Conclusion: If the Dow-Jones Average crashes then Ralph is not happy.
    crashes(dow-jones) -> !happy(ralph)

here:

Prove the conclusion from the axioms by refutation using resolution:

  1. (10 points) Translate the axioms and the negation of the conclusion into clausal form. Show each step of the translation (remember that the order in which you apply the steps is crucial).

  2. (10 points) Apply resolution (state explicitly what clauses are resolved and which substitutions are made) until the empty clause is found.

Problem 4. 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, AND THE ROBOT IN THE KITCHEN. More precisely,

Problem 5. Machine Vision (20 points)

Suppose that during the analysis of an image, you have found an unknown object in the image. You want to determine what kind of object it is by matching it against a database of templates that you have at hand.
  1. Suppose that you know that the unknown object could have been rotated with respect to only the y-axis and has not been translated. Answer the questions below.

    1. (2 points) How many templates per model are needed to determine if the unknown object matches that model?

      Two (2)

    2. (4 points) Write down the equation that describes the x-coordinate of a point on the unknown object in terms of the x-coordinates of the corresponding points on the templates.

      xIo = alpha * xI1 + beta * xI2

    3. (4 points) How many corresponding points are needed to do the matching? Explain your answer precisely in terms of the equation you provided above.

      Two (2). Given that the equation above has two variables (alpha and beta) then we need two equations to be able to solve the system for those variables.

  2. Suppose that you know that the unknown object could have been rotated and translated with respect to all of the 3-D axes. Answer the questions below.

    1. (2 points) How many templates per model are needed to determine if the unknown object matches that model?

      Three (3).

    2. (4 points) Write down the equation that describes the x-coordinate of a point on the unknown object in terms of the x-coordinates of the corresponding points on the templates.

      xIo = alphax*xI1 + betax*xI2 + gammax*xI3 + deltax

    3. (4 points) How many corresponding points are needed to do the matching? Explain your answer precisely in terms of the equation you provided above.

      Four (4). Given that the equation above has four variables (alphax, betax, gammax, and deltax) then we need four equations to be able to solve the system for those variables.