1. Summertime approaches!  After this semester's Artificial Intelligence course, brain power has gone to an all time low.  You decide to give your brain a rest for the summer and let your computer "think" for you.  Your first decision each morning is whether or not to go to the beach.  You decide to program your computer, using decision trees, so that it can make this all important decision for you.  Monitoring your daily beach activity results in the following set of training examples:

 

Day

Outlook

Temperature

Humidity

Wind

Go to beach?

D1

Sunny

Hot

High

Weak

Yes

D2

Sunny

Hot

High

Strong

Yes

D3

Overcast

Hot

High

Weak

Yes

D4

Rain

Mild

High

Weak

No

D5

Rain

Cool

Normal

Strong

No

D6

Rain

Cool

Normal

Weak

No

D7

Overcast

Cool

Normal

Strong

No

D8

Sunny

Mild

High

Strong

Yes

D9

Sunny

Cool

Normal

Weak

Yes

D10

Rain

Mild

High

Strong

No

D11

Overcast

Hot

High

Strong

No

 

a) (4 points) Given the following formula for Entropy, replace the variables (pi ) in the equation with their appropriate values as given by the above table.

 

  

 

b) (5 points) If Entropy (S) = .994  and the formula for Information Gain is:

 

             

 

 

Entropy(Sunny) = 0

Entropy(Overcast) = .918

Entropy(Rain) = 0

 

What is the Information Gain for the attribute Outlook?

 

 

c) (3 points)You calculated the information Gain for each attribute and got the following results:

 

Gain (S, Humidity) = .151

Gain (S, Wind) = .048

Gain (S, Temperature) = .029

Gain (S, Outlook) = what you calculated in b

 

Which attribute labels the root node of the decision tree?

d) (5 points)The resulting decision tree is shown below.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


What are the rules for deciding whether or not to go to the beach?

 

 


2. (15 points) A perceptron is given the following set of training examples.

 

 

x1

x2

result

0

0

0

1

0

0

0

1

0

1

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


The equations for the Perceptron training rule is:

 

 

 

If   h = .1 what are the values for w0 , w1 , w2  after one iteration of the perceptron training algorithm?


3. (6 points) Given the following simple two layer feed forward neural network, with two input, two hidden units and one output node, determine the output of the network if the weights are equal to the following values.  The threshold function used by each unit is tanh.  You only need to set up the equations.  Do not solve them.

 

 

 

nndiagram

 

W13  = .4

 

W14  = .6

 

W23  = .3

 

W24  = .4

 

W35  = .4

 

W45  = .5

 

 

4. The 4 queens problem can be solved using a genetic algorithm.  We can represent the 4X4 chess board as a 4 element array with each cell containing the position of the queen in that column.  For example, the array  4   1   3   4 represents the placement of queens as follows:

 

 

Q

 

 

 

 

 

 

 

 

Q

 

Q

 

 

Q

 

If the population has the following 4 individuals:

 

Individual A  4 1  3  4

Individual B    4  2  2  1

Individual C   3  4  1  3

Individual D   2  4  1  1

 

Which individuals survive into the next generation if we end up with the same number of  individuals (4)?

 

 

 

 

5. We wish to send a message to our mothers (Mom's day is Sunday) expressing our love, but we have almost no minutes left on our cell phone.   Therefore we have to send the shortest message possible.

 

Let's say  our messages are coded by a variable X having five possible values, A, B, C, and D, and E

 

Where:

 

P(X=A) = 1/4

P(X=B) = 1/8

P(X=C) = 3/32

P(X=D) = 1/2

P(X = E) = 1/32

 

6

 

 

 

 

 
If :

bits (A) = - log 2 1/4 = 2

bits (B) = - log 2 1/8 = 3

bits (C) =  - log 2 3/32 = 3.4  which since we can't send a piece of a bit, is 4.

bits (D) = - log 2 1/2 = 1

bits (E) =  - log 2 1/32 = 5

 

a)     (2 points) Find H(X),  the average number of bits for each message.

 

b)    (1 points) What is another name for H(X)?

 

c)     (2 points) Create a code for the above values.

 

Value

Code

A

 

B

 

C

 

D

 

E

 

 

6. Tic tac toe is a children's game that is played as follows:

  1. One person is X the other is O
  2. X goes first
  3. Each person takes turns writing his mark on a 9 square playing board
  4. The person to be first to display 3 of his marks in a row wins.

 

 

Assume we are playing tic tac toe.  The diagram shows the current state of the game.  It is O's move.  He is using minimax search to decide which path to choose in the game tree.

 

O is a maximizing player

 

Taking into account symmetry, there are only 4 possible moves O can make

 

The evaluation function that O uses is:

                        E(n) = O(n) - X(n)

            where O(n) stands for O's possible winning lines

            and     X(n) stands for X's possible winning lines

 

a) (8 points) Calculate the evaluation function to each of O's possible moves. 

b) (2 points) Which choice does O make based on this evaluation function?

c) (2 points) Is this a good evaluation function? Why or why not?  Is there a better move for O than the one minimax picks?