WPI Worcester Polytechnic Institute

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

CS4341 Introduction to Artificial Intelligence 
Solutions - HOMEWORK 4 - C 2000

PROF. CAROLINA RUIZ 

DUE DATE: Friday, Feb. 25 at 5 pm. 
------------------------------------------


Part 1: Practice Problems for the Final Exam (60 points)

Solve all 5 problems. This set of problems is available in the following formats:

Solutions

  1. Solution Problem 1: By Weiyang Lin
    See Constraint Net

  2. Solution Problem 2: By Carolina Ruiz and Weiyang Lin
    Translating formulas into clausal form
    
    (1) forall x (reads(x) -> literate(x))
        !reads(x) or literate(x)
    
    (2) forall y (dolphin(y) -> !literate(y))
        !dolphin(y) or !literate(y)
    
    (3) exists z (dolphin(z) and intelligent(z))
        dolphin(a) and intelligent(a)
    (3.1) dolphin(a)
    (3.2) intelligent(a)
    
    Conclusion:
    (4) exists w (intelligent(w) and !reads(w))
        negated conclusion: 
           !(exists w (intelligent(w) and !reads(w)))   
           forall w (!intelligent(w) or reads(w))
           !intelligent(w) or reads(w)
    
    Proof by refutation using resolution:
    
    (3.2) intelligent(a)
    (4) !intelligent(w) or reads(w)
    -----------------------------------------------------------
    (5) reads(a)             (substituting w by a)
    
    (2) !dolphin(y) or !literate(y)
    (3.1) dolphin(a)
    -----------------------------------------------------------
    (6) !literate(a)         (substituting y by a)
    
    (1) !reads(x) or literate(x)
    (5) reads(a)
    -----------------------------------------------------------
    (7) literate(a)          (substituting x by a)
    
    (6) !literate(a)
    (7) literate(a)
    -----------------------------------------------------------
    (8) empty clause
    

  3. Solution Problem 3: By Carolina Ruiz and Ganga
    See plan

  4. Solution Problem 4: By Carolina Ruiz and Weiyang Lin
    
    				Operator
    	           Patrick / Thomas |  Sally \
    			  /         |         \ 
                         Overtime   Output = low  Output = hight 
                    No /      Yes \    3, 6, 7          5
                      /            \
               Output = high   Output = low
                 1, 4             2, 8
    
    (1) For the first attribute
     Operator: 
       4/8*(-2/4*log(2/4)-2/4*log(2/4))+3/8*(-3/8*log(1))+1/8*(-1/1*log(1))
     = 0.5
    
     Machine:
       2/8*(-1/2*log(1/2)-1/2*log(1/2))+3/8*(-2/3*log(2/3)-1/3*log(1/3))+
       +3/8*(-2/3log(2/3)-1/3log(1/3))
     = 0.94
    
     Overtime:
      3/8*(-3/3*log(1))+5/8*(-3/5*log(3/5)-2/5*log(2/5)) = 0.61
    
     So operator is selected.
    
    (2) For Operator = Patrick
    
     Machine:
       2/4*(-1/2*log(1/2)-1/2*log(1/2))+2/4*(-1/2*log(1/2)-1/2*log(1/2)) = 1
    
     Overtime:
       2/4*(-2/2*log(2/2))+2/4*(-2/2*log(2/2)) = 0
    
     So Overtime is selected.
    

  5. Solution Problem 5: By Carolina Ruiz and Weiyang Lin
     from    x(AI0) = a * x(AI1) + b * x(AI2)
     and     x(BI0) = a * x(BI1) + b * x(BI2)
    
     we get  0.8 = a * 0 + b * 1
     and     1.4 = a * 1 + b * 1
    
     hence,  a = 0.6, b = 0.8.
    
     (we are using a for alpha and b for beta here)
    
     so      x(CI0) = a * x(CI1) + b * x(CI2)
                    = 0.6 * 1 + 0.8 * (-2)
                    = -1
    
             x(DI0) = a * x(DI1) + b * x(DI2)
                    = 0.6 * 0 + 0.8 * (-2)
                    = -1.6
    
     Because the expected value of the x coordinate of point D of the unknown 
     object (-1.6) does not match the actual value of that coordinate (-1.8), 
     the unknown object does not fit the templates.
    

Part 2: Training Neural Nets (20 points)

This problem is available in the following formats:

Solution:

The solution table was generated using Janet Burge's error back propagation code. (Thanks Janet for letting us post your code here). Below the table there are some sample computations.
+-----------+-----------+---------+---------+---------+---------+----------+
| Variables | Initial W |  ex. 1  |  ex. 2  |  ex. 3  |  ex. 4  | Final W  |
+-----------+-----------+---------+---------+---------+---------+----------+
|  A        |           |   0.000 |   0.000 |   1.000 |   1.000 |          |
|  B        |           |   0.000 |   1.000 |   0.000 |   1.000 |          |
| Des. Out  |           |   0.000 |   1.000 |   1.000 |   0.000 |          |
+-----------+-----------+---------+---------+---------+---------+----------+
| W a->c    |    0.100  |   0.100 |   0.100 |   0.100 |   0.100 |    0.100 |
| W a->d    |    0.200  |   0.200 |   0.200 |   0.200 |   0.200 |    0.199 |
| W b->c    |   -0.100  |  -0.100 |  -0.100 |  -0.100 |  -0.100 |   -0.100 |
| W b->d    |    0.050  |   0.050 |   0.050 |   0.050 |   0.050 |    0.049 |
| W c->e    |   -0.200  |  -0.200 |  -0.200 |  -0.200 |  -0.200 |   -0.204 |
| W d->e    |    0.300  |   0.300 |   0.300 |   0.300 |   0.300 |    0.295 |
+-----------+-----------+---------+---------+---------+---------+----------+
| C Output  |           |  0.3775 |  0.3543 |  0.4013 |  0.3775 |          |
| D Output  |           |  0.3775 |  0.3894 |  0.4256 |  0.4378 |          |
| E Output  |           |  0.5094 |  0.5115 |  0.5118 |  0.5140 |          |
+-----------+-----------+---------+---------+---------+---------+----------+
| Beta C    |           |  0.0255 | -0.0244 | -0.0244 |  0.0257 |          |
| Beta D    |           | -0.0382 |  0.0366 |  0.0366 | -0.0385 |          |
| Beta E    |           | -0.5094 |  0.4885 |  0.4882 | -0.5140 |          |
+-----------+-----------+---------+---------+---------+---------+----------+
| D W a->c  |           |  0.0000 | -0.0000 | -0.0059 |  0.0060 |          |
| D W a->d  |           | -0.0000 |  0.0000 |  0.0089 | -0.0095 |          |
| D W b->c  |           |  0.0000 | -0.0056 | -0.0000 |  0.0060 |          |
| D W b->d  |           | -0.0000 |  0.0087 |  0.0000 | -0.0095 |          |
| D W c->e  |           | -0.0481 |  0.0433 |  0.0489 | -0.0485 |          |
| D W d->e  |           | -0.0481 |  0.0475 |  0.0519 | -0.0562 |          |
+-----------+-----------+---------+---------+---------+---------+----------+

Sample Computations for example 1, i.e. A = 0, B = 0:
(here e^y means e to the power y)

Oc = 1/[1 + e^{y}] where  y = A*Wac + B*Wbc + (-1)*1/2
   = 0.377541               = 0*0.1 + 0*(-0.1) - 0.5 = -0.5

Od = 1/[1 + e^{y}] where  y = A*Wad + B*Wbd + (-1)*1/2
   = 0.377541               = 0*0.1 + 0*(0.05) - 0.5 = -0.5

Oe = 1/[1 + e^{y}] where  y = Oc*Wcd + Od*Wde 
   = 0.509437               = 0.377541*(-0.2) + 0.377541*(0.3)

New Wde (after processing all 4 examples):

New Wde :=  0.300 -0.0481 + 0.0475 + 0.0519 -0.0562 = 0.295

Part 3: Genetic Algorithms (20 points)

Solve Exercise 25.2 (page 680) from your textbook.

Solution:

By Weiyang Lin
Part 1
 Tent type Quality  Standard Fitness 
   T1         5        5/30 = 0.167
   T2        10       10/30 = 0.333
   T3        15       15/30 = 0.5

 sum(qi) = 5 + 10 + 15 = 30

Part 2
 Tent type Quality  Standard Fitness 
   T1        41       41/150 = 0.273
   T2        50       50/150 = 0.333
   T3        59       59/150 = 0.393

 sum(qi) = 41 + 50 + 59 = 150

Part 3

 From Parts 1 and 2 above it's clear that, when the stardard selection
 method is used, the probability of selecting an individual changes
 depending on the units in which the fitness is measured (C or F).
 This is a drawback of the stardard method.

 Celsius        0.5/0.167 = 2.99
 Fahrenheit   0.393/0.273 = 1.44

 Note that, with the stardard method, the probability of selecting the 
 fittest individual (T3) is almost 3 times 
 the probability of selecting the least fit individual (T1)
 when Celsius degrees are used, but only 1 and a half times when 
 Fahrenheit degrees are used.