University of Toronto at Scarborough
CSCD84 – Artificial Intelligence – Winter 2015 ____________________________________________________________
Final Examination
Name (LAST, First): Student Number:
I hereby certify that I understand this test is being held under the UTSC code on academic integrity and plagiarism. I declare that all the answers recorded in this test are my own.
Signature:____________________________
(-5 marks for failing to complete any of the items above) Score:
1
Part 1
/ 20
Part 2
/ 20
Part 3
/ 13
Part 4
/ 15
Part 5
/ 20
Part 6
/ 17
Bonus
/7
Total
/ 105
This test contains 12 pages including this cover page
2
Zombie Attack!
Episode 84(d)
They are looking for brrraaaiiinnnsssss…
They heard a final exam was taking place here. Brains are needed for final exams…
These zombies are special – they have built-in A.I. (could they have been D84 students long ago? – if so, it’s too late for them)
Beware! answer all questions here and you might escape, show any fear and zombies may eat your marks. Worse, you may become an A.I. Zombie!
Part 1
The Search for Brains
3
Zombies look for brains using A* – their heuristic function is based on smell (which makes sense) since brains are smelly.
In the graph below, each node shows the heuristic cost h(n). Edge weights show actual traveling cost between nodes. The zombie’s initial position is shown, as are the positions of food.
BrainsA 2 3 H6
P2 5 4 103
I
4
2 3 G A J2
594 335C2
O2 3 zombie 9 F54
3 6 5 D 4 BrainsB N45
54 32
M 5 E9 9
a) [7] List the nodes in the order they are expanded by A*. Include the start node and the goal node, but the search ends as soon as you find a goal node. For ties, expand in alphabetic order.
b) [3] Is brain smell an admissible heuristic? (yes/no and a short explanation required)
K2 3 L5
Part 1
Search… continued
4
c) Consider a heuristic function that over-estimates the cost to the goal by at most k. The diagram below shows a search graph produced by A* with this heuristic. The optimal path is labeled ‘Optimal’, and the path returned by A* is labeled ‘A* solution’. The node marked N is the last node along the optimal path that was expanded before A* returned the suboptimal path ‘A* solution’. Node P is some node along the path produced by the A* solution.
N
A* solution
P
Optimal
s
g
(with thanks to Robert Benkoczi)
In the statements below:
f(x) is the A* cost for node x
c(x,y) is the actual cost of a path between nodes x and y cost(path) is the cost of a path between nodes
k is a constant
[2 marks each] – For each of the following statements, indicate whether the statement is true, false, or can not be decided.
1) f(P)+k > f(N)
2) c(s,N) + k >= cost(A* solution)
3) c(s,N) > f(p)
4) c(s,N) + c(N,g)+ k >= cost(A* solution)
5) f(N) < cost(A* solution)
Part 2
Constraint Satisfaction Problems
5
The crossword puzzle shown below can be encoded as a CSP. Each vertical entry, and each horizontal entry become a variable in the CSP (to which we must assign a specific word). Each entry then places constraints on all remaining entries with which it shares letters.
* Hint for #7 – It is also a mode for playing music on portable devices...
Part 2
Constraint Satisfaction Problems
6
a) (10 marks) The graph below represents the crossword puzzle on the previous page. However, note that there are mistakes. Correct all mistaken edges either by removing wrong edges or adding missing ones. Keep this clean, or lose marks!
2
1
3
5
4
8
6
7
9
10
11
b) (5 marks) Assuming the domain sizes are as follows: 4-letter words: 4,002 5-letter words: 8,887
6-letter words: 15,727
9-letter words: 29,130 Which variables are tied to be expanded first and what selection criteria are
they tied over. (i.e. which rules of expansion result in ties in this case)
c) (5 marks) You can break the tie between variables above if you consider how to make a choice that affects the order of variable expansion for the next level in the search.
Think about it, and see if you can select the variable to expand that results in the smallest amount of subsequent search! Explain why you made this choice.
7-letter words: 23,958 8-letter words: 29,718
(stats from wordfinder.yourdictionary.com)
Part 3
Minimax and Game Trees
7
Having learned lots during this course, you have decided that your best course of action to survive the zombie invasion is to plan your actions by mimi-maxing. Fortunately, zombies have short attention spans and get randomly distracted (does this sound familiar?). Unfortunately, even if you choose a reasonable action, bad stuff can happen randomly.
Your turn! - MAX
Get the flame-thrower!
(it's right next to the zombie)
Eat the zombie before it eats you!
Run away!
Zombie! - Rand!
.7
.3
-50
.7
Zombie is distracted
.3
.1
-50
.7
Zombie is distracted
.3
.9 .1 +10 -50
Zombie is distracted
.7
.3
.7
.3
-50
.8
+20
.2
-50
.9
+20
+30
.1 .9
-50
+30
+10
a) (6 marks) Complete the expected utilities at each of the chance nodes at the bottom of the
tree
b) (4 marks) Complete the (expected) utilities for the zombie and for the root nodes.
c) (3 marks) What are the optimal action, expected utility, and possible outcomes for you?
Part 4
Reinforcement Learning
8
Some say you can't teach an old zombie new tricks. However, recent research shows that zombies employ a type of reinforcement learning. It's slow (small alpha!), and it has a problem: it does not converge!
a) (5 marks) Given the Q-learning update equation shown below, explain what values of gamma would cause the learning process to not converge and why this is so.
b) (5 marks) Re-write the Q-learning equation so that it accounts for random events (2 marks for indicating which term changes, full marks for rewriting the equation properly).
c) (5 marks) Why is Q-learning a reasonable algorithm to use for a zombie, but a terrible idea if you are not a zombie? (short answer here – or risk tl;dr = 0)
As per majority request – You did not have to memorize the Q-learning equation 🙂
Part 4
Reinforcement Learning
d) (5 bonus marks) Summer movies often are about
9
a) Zombies taking over the world
b) Evil A.I. taking over the world
Evidently, the ultimate summer blockbuster should be about a Zombie A.I. taking over the world!
In the space below, draw your vision for this movie.
- Put some thought into it
- Draw!
- Don't draw something we already know
- If we are amused, entertained, or otherwise find your idea cool, that is great!
Part 5
Bayes Nets and Probabilistic Reasoning
10
An important problem when faced with a zombie outbreak is to determine if someone you know was bitten by a zombie and will turn into one soon. Common symptoms of zombie bites include swelling and fever. Unfortunately these are fairly common. But, luckily, you know Bayes Nets!
GMO spider bite (s)
Zombie bite (z)
Become zombie (x)
Common cold (c)
Cough (u)
Fever (f)
Swelling (q)
Become spider-man (y)
a) (8 marks) Suppose you observe f=1, what should happen (increase, decrease, or no change) to your belief that: (briefly – in one sentence – explain why)
z=1 c=1 f=1 s=1
b) (4 marks) Supose that you now observe u=1. What should happen to your belief that: c=1
z=1
c) (8 marks) Starting from a situation where no observations have been made, assuming that
a zombie bite will inevitably turn a person into a zombie, and a bite from a GMO spider will inevitably turn a person into spider-human. If all you have observed so far is
q=1. Provide a chain of reasoning – supported by the relevant probability equations that can be used to determine which of x=1 or y=1 is most likely.
Part 6 Neural Nets
11
You have just learned that the current zombie outbreak is the result of an attempt by not very careful scientists to create tireless workers to do simple and repetitive jobs (like marking). Unfortunately, they never got the simple neural network right, so their zombies can not learn anything – hence their constant search for braiiinnssss: Zombies want to learn too! See if you can figure out what went wrong.
Consider the neural net shown below:
AB
C
D
a) (5 marks) The zombie's neural net was designed using neurons that contain step activation functions – please write out the mathematical form of the weight update for the weight WBC as would be given by the back-propagation algorithm
b) (3 marks) Will this network learn properly using back-prop? (yes/no and a short explanation)
c) (9 marks) Since simple networks didn't work, scientists tried complex, multi-layer architectures. They never got them to work, though, because they could never figure out exactly which outputs and weights intervene in the weight updates for interior neuron layers.
In the network below, list which inputs, outputs, and network weights intervene in the back-propagation update to WBD
In1 A FOutF D
In2 In3
B GOutG
E
C HOutH
Part 8 – Feedback. Only write here if you have finished the rest of the test
(these are all bonus marks – but only thoughtful, informative answers count) a) (3 bonus)
if (you have taken more than one course with Paco) # List courses taken with Paco
# Tell me which was your favorite, and why
else
# Tell me which part of the D84 course was the best, # and why
12
b) (2 bonus) Give as a
me one suggestion for making the D84 course much better
learning experience (i.e. What would have made the course more useful for you?)
c) (2 bonus) What can Paco do to improve his teaching? Here, think of any things I do not do that would make my courses better in your view – I must become crunchier over time! This is how it starts