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

#### PROF. CAROLINA RUIZ

DUE DATE: Friday, Feb. 25 at 5 pm. • Instructions for Homework 4:
• This is an INDIVIDUAL homework.
• The homework is due Friday, February 25, 2000 at 5 pm.
• Parts of the homework are in PDF format, as well as in DVI and PS formats. If you are unable to handle those formats, send email to cs4341_ta@cs.wpi.edu, and we'll make paper copies of the HW assignment available to you.

• Homework Problems: This homework consists of three parts:

### 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
• Every two persons X and Y sitting together need to satisfy constraint
C1: These two persons X and Y don't hate each other.
• Every three persons sitting together need to satisfy constraint
C2: If the middle person X comes with a spouse, then the spouse is either the person to the left of X or the one to the right of X.

2. Solution Problem 2: By Carolina Ruiz and Weiyang Lin
```Translating formulas into clausal form

(1) forall x (reads(x) -> 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:

Proof by refutation using resolution:

(3.2) intelligent(a)
-----------------------------------------------------------
(5) reads(a)             (substituting w by a)

(2) !dolphin(y) or !literate(y)
(3.1) dolphin(a)
-----------------------------------------------------------
(6) !literate(a)         (substituting y by 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.

```