CS325 Artificial Intelligence – Spring 2013

Midterm Solution Guide

Instructor: Cengiz Gunay, Ph.D.
March 19, 2013

Instructions
Total points: 50 (25% of course grade, subject to change)
1. Use your own empty sheets to write your answers. I left a lot of free space on this
handout so you can use it for scribbling.
2. On the top of your sheets, write your name and name of students sitting next to
you.
3. You don’t need to repeat the questions on your answer sheets.
4. There are some formulas at the end on page 11. They are referenced from questions
that need them.
(nF) shows popularity of question – n students chose it.

I. Verbal Questions
(10 points) Pick and answer ANY 5 of the following 12 questions.
1. (9F)How do you get started if you wanted make an intelligent agent to solve a
problem? What are the first things you need for building an agent?
Answer: Must define PEAS: Performance, Environment, Actuators, and Sensors.
2. (10F)List some environmental properties that are important for intelligent agents.
Describe the properties of the environment for the Mars Rover.
Answer: Fully/partially observable, discrete/continuous, single/multi agent, stochas-
tic/deterministic, adversarial, dynamic/static. Mars rover: partially observable (be-
cause sensors are limited), single agent, continuous, stochastic (e.g., weather events),
dynamic (slips?), non-adversarial.
3. (18F)Compare breadth-first, depth-first, cheapest-first and A* algorithm strategies
and benefits.
Answer: Breadth-first: siblings first, then go deeper. Complete only if breadth, b, is
finite. Non-optimal if cost not unitary. Time and space complexity are both O(bd ).
Depth-first: go to deeper nodes first, then go to next branch. Complete only if
depth, d, is finite and there are no loops. Non-optimal as in breadth-first. Space
complexity is O(bd), which is smaller than breadth-first.
Cheapest-first: Like breadth first, but minimizes cost of path taken so far. Complete
and optimal if b is finite.
A*: Adds heuristic function in addition to cost. Complete and optimal if heuristic
is admissable.

1
4. (8F)What is the difference between conditional and joint probabilities between two
random variables?
Answer: Conditional probability, P (A|B), is the probability of A when we know
that B happened. Joint probability, P (A, B), is the probability of both events
happening. Only if the two are independent, A⊥B, then P (A, B) = P (A)P (B).
5. (10F)What type of questions can you answer with a Bayes Net?
Answer: When many factors contribute in probabilitic fashion to an outcome. We
can both make predictions about the outcome and diagnose causes.

6. (13F)When can you employ supervised learning to solve a problem?

Answer: When you want to find the relationship between some input data and
desired outcomes. For instance classification based on multiple parameters.
7. (17F)What is unsupervised learning good for in real life problems?
Answer: Finding hidden structure and regularities in data. Practically used for
clustering, dimensionality reduction, etc.
8. (4F)What is the advantage of using logic over other methods of representation?
Answer: Logic not only provides a concise description of knowledge and situation
of an agent, but also allows use of automated reasoning.

9. (14F)Why do we need to alternate between plan and execution?

Answer: Making long-term plans may fail due to several reasons. In partially
observable, uncertain and stochastic environments we need to plan for the goal, but
interleave the execution of the plan with observations to make sure we are on the
right track.

10. (8F)Why do we need a belief state for planning?

Answer: Again, in partially observable, uncertain and stochastic environments, the
agent can be in one of several states, which is why it needs a belief state during
planning to consider all options.

11. (2F)What’s the difference between Markov Decision Processes (MDPs) and Rein-
forcement Learning (RL)?
Answer: MDPs can find the way to known reward locations in a fully observable
environment. In contrast, RL can operate in a partially-observable environment to
discover reward locations.

12. (1F)What is the dilemma between exploration and exploitation for an RL agent?
Answer: In a partially-observable environment, the RL agent needs to explore to
find the rewards, however it should also know when to stop exploring and pursuing
the rewards. Otherwise, it may waste its resources during unnecessary exploration.

II. Simple Knowledge Questions

(20 points) Pick and answer ANY 2 of the following questions. Note that some questions
are slightly different than their homework versions.
1. (1F)(10 points) Describe a single-state agent architecture for the 3-location vacuum
cleaner. Discuss:

2
(a) Size of state space
Answer: Agent’s possible location (3) × possible dirt configurations (23 ) =
3 × 23 = 24 states.
(b) Inital configuration and goal test
Answer: Choose one of the 24 states as described above as initial state. Goal
states are the ones without any dirt in any of the locations, irrespective of
where the agent is located.
(c) Transition function
Answer: Agent can move left or right, which affects its location. Agent can
suck dirt, which affects existence of dirt.
(d) Adequate tree-search algorithm and its complexity for width n and depth d
Answer: Without any costs defined, we can use breadth-first search with time
and space complexity of O(nd ).

2. (22F)(HW2 – 10 points) Briefly describe what each of the following means:

(a) P (A, B)
Answer: Probability of both A and B happening.
(b) P (A|B, C)
Answer: Probability of A given that we know B and C to be true or false.
(c) A⊥B|C
Answer: A is independent of B conditional on knowing outcome of C.
(d) P (A|B, C) = P (A|B)
Answer: A is independent of C conditional on knowing outcome of B. We do
not know if A is independent of C in general.
(e) P (A, B, C) = P (A|B, C)P (B|C)P (C)
(explain this and also draw it as a Bayes Net)
A
Answer: C is independent; B depends on C; and, A
depends on both B and C.
B C

3. (4F)(HW3 – 10 points) Briefly describe what each of the following means. Explain
whether it is an unsupervised or supervised learning scheme, its advantantages and
disadvantages, and indicate whether it employs a hill climbing (or gradient descent)
method, which is subject to local minima.

(a) k-Means Clustering

Answer: Unsupervised iterative algorithm for finding cluster centers. Not a
gradient-descent method (no derivative), but suffers from local minima.
(b) Expectation-Maximization using Maximum Likelihood
Answer: Unsupervised iterative algorithm to maximize probability of a Bayes
Net. Can be used for maximizing most likely Gaussian representation of clus-
ters. No gradient, has local minima, but works better than k-means.
(c) Multi-layer Perceptron (MLP)
Answer: Supervised learning algorithm with multiple layers of neural units
(perceptrons). They are used for classification and pattern recognition prob-
lems. It suffers from local minima because of the gradient descent method
following the derivative of the loss function.

3
(d) Support Vector Machines (SVM)
Answer: Supervised learning algorithm with transformation such that it con-
verges faster. While still suffering from local minima, it performs much better
than MLPs.
(e) Genetic/Evolutionary Algorithms
Answer: Supervised learning algorithm with no gradient descent. It can find
global minimum, but takes longer to find solution.

4. (20F)(HW4 – 10 points) Select and write one set of true/false values for the vari-
ables A, B, C, D and then answer whether the following logic sentences are true or
false. Also indicate if the sentence is valid, satisfiable or unsatisfiable.
Answer: For A = t, B = t, C = t, D = t;
(a) (A ∧ B) ∨ (¬C ∨ ¬D)
Answer: True, satisfiable.
(b) A ⇒ B
Answer: True, satisfiable.
(c) A ∧ C ⇒ B ∨ D
Answer: True, satisfiable.
(d) (¬B ⇒ ¬A) ⇔ (¬A ∨ B)
Answer: True, valid.
(e) (B ⇒ ¬A) ⇔ (¬C ∧ D)
Answer: True, satisfiable.

4
III. Problem Solving Questions
(20 points) Pick and choose questions that add up to 20 points. You are allowed +10
bonus points if you do more, which will count only WITHIN the points of this exam.
That is, you cannot get more than 50 points from this exam.

LaVist 1

N
a

Shep (N)

Dr
0.5

1
ui
1

0.5
) 0 0.5

d
l (N .5
0.5 il .5

0.5 Clairmont
M 0

0.
liff n Ma
arc

5
o
Bri u st son
5 Mil

0.5
o .

Cl
1 H 0 0. l (N
5

ift
)

on
H
ay

0.
go

2 0.3
od
0.
5 (N

1
1 )
N Decatur 0.5 0.5

Figure 1: A road map of the Emory vicinity. Numbers show approximate distance in
miles. See Question 1 for details.

1. (19F)(HW1 – 10 points) Starting from the Clairmont Rd. and North Druid Hills
intersection on map in Figure 1, manually simulate the FIRST THREE ITERA-
TIONS of the uniform-cost (cheapest-first) algorithm to target one of the following
destinations:

• Clifton & Houston Mill

• Clifton & Haygood
• N Decatur & Clifton

Write down what you add and remove from the frontier at each step and how you
select which intersection to choose next.
Answer: Traverse the map and manipulate the frontier:

(a) Pop (Clairmont & North Druid Hills, 0)

Add (Clairmont & Mason Mill, 0.5), (North Druid Hills & La Vista, 0.5),
(Clairmont & La Vista, 0.5)
All the same, choose one randomly:
(b) Pop (Clairmont & Mason Mill, 0.5)
Add (Houston Mill & Mason Mill, 1), (Clairmont & North Decatur, 1.5)
(c) Pop (North Druid Hills & La Vista, 0.5)
Add (La Vista & Houston Mill, 1), (North Druid Hills & Briarcliff, 1.5)
(Solution for all destinations are the same for the first three iterations.)

5
Legend
0.6 0.5 0.2
S: Getting sick from the
F H R flu.
P (G) R H G: Getting the flu virus.
0.8 T T R: Rare form of the flu
T G 0.3 F T virus.
0.7 T F
P (T ) F H: Getting the flu shot.
0.9 F F
0.5 T
T: Using Tamiflu antiviral
0 F S medicine.
P (S) T G F: Availability of Tamiflu.
0.6 T T
0.9 F T
0.2 T F
0 F F

Figure 2: A fake flu Bayes net for catching the flu. See text for details.

2. (16F)(HW2 – 10 points) Based on the Bayes net in Figure 2, solve the probability
formula (by explaining each step) described by the following verbal question:

”What’s the probability of getting sick from with the rare form of the flu
if you knew that Tamiflu was not available?”

Answer: I also gave points for a second interpretation for the verbal question:
(a) P (S|¬F, R), which is the probability of getting sick given that we know it’s
the rare form and Tamiflu was unavailable.
i. Eliminate F completely because P (T |¬F ) is impossible:

P (S|¬F, R) = P (S|¬T, R) .

ii. Eliminate H by enumerating P (G|R):

P (G|R) = P (G|R, H)P (H) + P (G|R, ¬H)P (¬H)

= 0.5 × 0.8 + 0.7 × 0.5 = 0.75 .

iii. Use the chain rule and enumeration over possible states of G:
X
P (S|¬T, R) = P (S|¬T, g)P (g|R)
g
= 0.9 × 0.75 = 0.675 .

(b) P (S, R|¬F ) is exactly what I asked.

i. Again, start by eliminating F :

P (S, R|¬F ) = P (S, R|¬T ) .

6
ii. Enumerate the full joint probability:
X
P (S, R|¬T ) = P (S, R, ¬T, h, g)
g,h
X
= P (S|¬T, g)P (g|R, h)P (h)P (R)
g,h

reuse P (G|R) from above:

X
= P (S|¬T, g)P (G|R)P (R)
g
= 0.9 × 0.75 × 0.2 = 0.134 .

because P (S|¬T, ¬G) = 0.

7
Uses
Shopper Milk Bread Beer Soda Water Eggs Price
coupons?
S0 0 0 1 1 0 0 $10 1
S1 1 0 0 1 1 1 $42 0
S2 1 1 1 0 1 1 $12 1
S3 0 1 1 1 1 0 $35 0
S4 0 1 0 0 1 1 $5 1

Table 1: Shopping data from shoppers S0 , . . . , S4 .

3. (5F)(HW3 – 10 points) Simulate the k-Means clustering algorithm (see page 11)
for two iterations to find two clusters (k = 2) in the data of Table 1. Do not use
the “Shopper,” “Price,” or “Uses coupons?” columns, and start with initial cluster
centers of respectively all zeros and all ones.
Answer:
C1 = (1, 1, 1, 1, 1, 1) C2 = (0, 0, 0, 0, 0, 0)
S1 S0
(a) Iteration 1:
S2 S4 (either into C1 or C2 )
S3
C1 = ( 32 , 23 , 32 , 32 , 1, 23 ) C2 = (0, 21 , 12 , 12 , 12 , 12 )
S1 (2.3) S0 (2.5)
(b) Iteration 2:
S2 (2) S4 (2.5)
S3 (2)

4. (2F)(HW3 – 10 points) Now consider all columns in Table 1 to predict which

shoppers have a larger tendency to use coupons. Use the linear perceptron definition
on page 11.

(a) Start with a weight vector, w = [3.0, 6.5, 8.0, 1.0, 5.0, 7.0, −3.0] and threshold,
T = 9.3. Evaluate any three rows in table and report the weighted sum of
the inputs and the perceptron output, and compare it to the expected output.
Look into the weights and discuss which column(s) were most influencial in
the perceptron’s right and wrong decisions.
Answer:
Example, evaluate:
Multiply by weights Guess
S0 · w = 0 + 0 + 8 + 1 + 0 + 0 − 30 = −21 > 9.3? 0 Wrong
S1 · w = 3 + 0 + 0 + 1 + 5 + 7 − 126 = −110 > 9.3? 0 Correct
S2 · w = 3 + 6.5 + 8 + 0 + 5 + 7 − 36 = −6.5 > 9.3? 0 Wrong
Price column is the most influential by far. Other weights need to be trained
more to overcome it.
(b) Then, choose one row from the table and use its values to update the perceptron
weight vector. Use a training rate parameter of α = 0.5 to update the weights.
What changed?
Answer: Use S0 inputs, only non-zero inputs will cause a change:
Weight update Change?
w2 = 8 + 0.5 × (1 − 0) × 1 = 8.5 increase
w3 = 1 + 0.5 × (1 − 0) × 1 = 1.5 increase
w6 = −3 + 0.5 × (1 − 0) × 10 = 2 increase
Large increase in price column as expected from 4a.

8
i. ∀a, b Loves(a, b) ∧ Loves(b, a) ⇒ Happy(a) ∧ Happy(b)
ii. ∀a, b, c Loves(a, b) ∧ Loves(b, c) ∧ ¬(a = c) ⇒ Unrequited(a, b) ∧ Sad(a)
iii. ∃a Happy(a)

iv. ∃a Sad(a)

Table 2: A knowledge base.

5. (13F)(HW4 – 10 points) To the knowledge base (KB) given in Table 2, add THREE
of the following sentences and then answer if the query “Unrequited(John, N ancy)?”
is true, false, or unknown. Explain your logic. Make sure that the KB is consistent;
that is, it includes no contradicting knowledge.

(a) Loves(John, M ary)

(b) Loves(M ary, John)
(c) Loves(John, N ancy)
(d) Loves(N ancy, F red)
(e) Loves(F red, Emma)

Answer: There are a few solutions to this problem.

(a) A full solution can be given by selecting: (a), (b), and (c).
According to i.

Loves(John, M ary) ∧ Loves(M ary, John) ⇒ Happy(John) ∧ Happy(M ary)

According to ii.

Loves(M ary, John)∧Loves(John, N ancy)∧¬(M ary = N ancy) ⇒ Unrequited(M ary, John)∧Sad(M ary)

iii. and iv. are also satisfied because Sad(M ary) and Happy(M ary). Although
unintuitive, the KB is consistent because it doesn’t say same person cannot be
both happy and sad.
(b) Other selections can lead to satisfying iii. or iv. but not both. As long as it
was unknown, I accepted it as consistent.

9
Game objective: Rules:
Swap the places of left arrow tiles
with right arrow tiles. →
I.
Board:

→ → → ← ← ←
→ ←
II.
Figure 3: A simple tile-moving game. You need to reach the objective by only using the
two rules. First rule says a tile can move in the direction of the arrow if its immediate
neighbor is a blank. The second rule says a tile can jump in its arrow direction over a tile
that points the reverse direction if the next tile is blank. Game credits: Machinarium.

6. (4F)(HW4 – 10 points) Consider the tile-moving game in Figure 3. Write the action
schema for the game in classical planning (see page 11). Define the game board, the
tiles, and then write the two rules. Would a depth-first or breadth-first algorithm
work better for this task? Is it more advantageous to start from the initial state or
the goal state? Based on your answer to these questions, manually simulate the first
three steps of the solution by drawing the states from the initial board condition to
match and execute the rules by implementing the graph search.
Answer: Action schemas don’t use first-order logic, just simple parameterization of
variables in propositional logic. Define some predicates:

(a) Location(L1) . . . Location(L7): positions on board

(b) Empty(L4): position being empty
(c) LeftOf(L4, L5): ordering
(d) TileLeft(T L1) & TileRight(T R3): tile with left/right arrow
(e) On(L5, T L1): position of tile
Then, use them to define actions:
(a) Action: MoveR(t, l, b)
Pre: Location(l)∧Location(b)∧TileRight(t)∧On(l, t)∧LeftOf(l, b)∧Empty(b)
Eff: Empty(l) ∧ On(b, t) ∧ ¬On(l, t)
(b) . . .

And you’re done!

10
Appendix
1. k-Means clustering algorithm

(a) Randomly place k cluster centers

(b) Assign each point to closest center
(c) Move each cluster to center of gravity of new set
(d) Go back to step (b) until no change

2. Perceptron equations

y = fW (I)
N
X
sum = Ii Wi
i=1
(
1, if sum ≥ T
y=
0, if sum < T
The perceptron update rule for sample k and input j:

wj ← wj + α(yk − fw (Ik )) × Ij,k

3. Classical planning action schema consists of:

(a) Action
(b) Precondition
(c) Effect

Example:
Action(Fly(p, f rom, to),
Pre: At(p, f rom) ∧ P lane(p) ∧ Airport(f rom) ∧ Airport(to)
Eff: ¬At(p, f rom) ∧ At(p, to))

11