CS 188 Introduction to
Spring 2019 Artificial Intelligence Final Exam
• You have 170 minutes. The time will be projected at the front of the room. You may not leave during the last 10 minutes of the exam.
• Do NOT open exams until told to. Write your SIDs in the top right corner of every page.
• If you need to go to the bathroom, bring us your exam, phone, and SID. We will record the time.
• In the interest of fairness, we want everyone to have access to the same information. To that end, we will not be answering questions about the content. If a clarification is needed, it will be projected at the front of the room. Make sure to periodically check the clarifications.
• The exam is closed book, closed laptop, and closed notes except your three-page double-sided cheat sheet. Turn off and put away all electronics.
• We will give you two sheets of scratch paper. Please do not turn them in with your exam. Mark your answers ON THE EXAM IN THE DESIGNATED ANSWER AREAS. We will not grade anything on scratch paper.
• For multiple choice questions:
– means mark ALL options that apply
– means mark ONE choice
– When selecting an answer, please fill in the bubble or square COMPLETELY and
First name
Last name
SID
Student to the right (SID and Name)
Student to the left (SID and Name)
Q1. Agent Testing Today!
/1
Q2. Search
/12
Q3. Pacman’s Treasure Hunt
/14
Q4. Inexpensive Elimination
/9
Q5. Sampling
/10
Q6. HMM Smoothing
/11
Q7. Partying Particle #No Filter(ing)
/8
Q8. Double Decisions and VPI
/11
Q9. Naively Fishing
/11
Q10. Neural Networks and Decision Trees
/13
Total
/100
1
THIS PAGE IS INTENTIONALLY LEFT BLANK
It’s testing time! Not only for you, but for our CS188 robots as well! Circle your favorite robot below.
SID:
Q1. [1 pt] Agent Testing Today!
3
Q2. [12 pts] Search
(a) Consider the class of directed, m × n grid graphs as illustrated above. (We assume that m, n > 2.) Each edge has a cost of 1. The start state is A11 at top left and the goal state at Amn is bottom right.
(i) [2 pts] If we run Uniform-Cost graph search (breaking ties randomly), what is the maximum possible size of the fringe? Write your answer in terms of m and n in big-O style, ignoring constants. For example, if you think the answer is m3n3 + 2, write m3n3.
(ii) [2 pts] If we run Depth-First graph search with a stack, what is the maximum possible size of the stack?
(b) Now answer the same questions for undirected m × n grid graphs (i.e., the links go in both directions between neighboring nodes).
(i) [2 pts] Maximum fringe size for Uniform-Cost graph search?
(ii) [2 pts] Maximum stack size for Depth-First graph search?
(c) ThefollowingquestionsareconcernedwithanundirectedgridgraphGandwithManhattandistanced((i,j),(k,l))= |i − k| + |j − l|. Now the start and goal locations can be anywhere in the graph.
(i) [1 pt] True/False: Let G+ be a copy of G with n extra links added with edge cost 1 that connect arbitrary non-adjacent nodes. Then Manhattan distance is an admissible heuristic for finding shortest paths in G+.
True False
4
(ii) [1 pt] True/False: Let G− be a copy of G with n arbitrarily chosen links deleted, and let h+(s,t) be the exact cost of the shortest path from location s to location t in G+. Then h+(·, g) is an admissible heuristic for finding shortest paths in G− when the goal is location g.
True False
5
SID:
(iii) [2 pts] Suppose that K robots are at K different locations (xk,yk) on the complete grid G, and can move simultaneously. The goal is for them all to meet in one location as soon as possible, subject to the constraint that if two robots meet in the same location en route, they immediately settle down together and cannot move after that. Define dX to be the maximum x separation, i.e., | max{x1, . . . , xK } − min{x1, . . . , xK }|, withdY definedsimilarly.Whichofthefollowingisthemostaccurateadmissibleheuristicforthisproblem? (Select one only.)
⌈dX/2⌉+⌈dY/2⌉
dX +dY
⌈dX/2⌉ + ⌈dY /2⌉ + K/4
max{⌈dX/2⌉,⌈dY/2⌉,K/4} max{⌈dX/2⌉+⌈dY/2⌉,K/4}
6
Q3. [14 pts] Pacman’s Treasure Hunt
Pacman is hunting for gold in a linear grid-world with cells A, B, C, D. Cell A contains the gold but the entrance to A is locked. Pacman can pass through if he has a key. The possible states are as follows: Xk means that Pacman is in cell X and has the key; X−k means that Pacman is in cell X and does not have the key. The initial state is always C−k.
In each state Pacman has two possible actions, left and right. These actions are deterministic but do not change the state if Pacman tries to enter cell A without the key or run into a wall (left from cell A or right from cell D). The key is in cell D and entering cell D causes the key to be picked up instantly.
If Pacman tries to enter cell A without the key, he receives a reward of -10, i.e. R(B−k,left,B−k) = −10. The “exit” action from cell A receives a reward of 100. All other actions have 0 reward.
(a) [2 pts] Consider the discount factor γ = 0.1 and the following policy:
Fill in V π (B−k ) and V π (C−k ) for this policy in the table below.
(b) [3 pts] Now, we will redefine the MDP so that Pacman has a probability β ∈ [0, 1], on each attempt, of crashing through the gate even without the key. So our transition function from B will be modified as follows:
T(B−k,left,A−k) = β and T(B−k,left,B−k) = 1 − β. 7
SID:
Pacman has the key
ABCD
Pacman does not have the key
ABCD
State
Ak
Bk
Ck
Dk
A−k
B−k
C−k
D−k
Action
exit
left
left
left
exit
left
right
right
All other aspects remain the same. The immediate reward for attempting to go through the gate is −10 if Pacman fails to go through the gate, as before, and 0 if Pacman succeeds in crashing through gate. Which of the following are true? (Select one or more choices.)
For any fixed γ < 1, there is some value β < 1 such that trying to crash through the gate is better than fetching the key.
For any fixed β, there is some value of γ < 1 such that trying to crash through the gate is better than fetching the key.
For β = 1 , there is some value of γ < 1 such that trying to crash through the gate is better than fetching 2
the key.
None of the above
(c) Thus far we’ve assumed knowledge of the transition function T(s,a,s′). Now let’s assume we do not.
(i) [2 pts] Which of the following can be used to obtain a policy if we don’t know the transition function? Value Iteration followed by Policy Extraction
Approximate Q-learning
TD learning followed by Policy Extraction Policy Iteration with a learned T(s,a,s′)
(ii) [1 pt] Under which conditions would one benefit from using approximate Q-learning over vanilla Q- learning? (Select one only)
When the state space is very high-dimensional When the transition function is known
When the transition function is unknown
When the discount factor is small
(iii) [4 pts] Suppose we choose to use Q-learning (in absence of the transition function) and we obtain the following observations:
What values does the Q-function attain if we initialize the Q-values to 0 and replay the experience in the table exactly two times? Use a learning rate, α, of 0.5 and a discount factor, γ, of 0.1.
1. 2. 3. 4.
st
a
st+1
reward
Ck
left
Bk
0
Bk
left
Ak
0
Ak
exit
terminal
100
B−k
left
B−k
-10
100 10 10
75 5 5
50 2.5 2.5
0 0 0
Q(Ak,exit):
Q(Bk,left):
Q(Ck,left):
Q(B−k,left): -10 5 −2.5 −7.5
(d) Suppose
States are defined using proposition symbols be At,Bt,Ct,Dt and Kt, where, e.g., At means that Pacman is in cell A at time t and Kt means that the Pacman has the key. The action symbols are Leftt, Rightt, Exitt.
(i) [1 pt] Which of the following statements are correct formulations of the successor-state axiom for At?
At ⇔ (At−1 ⇒ (Leftt−1 ∧ Bt−1 ∧ Kt−1)
8
we want to define the (deterministic) transition model using propositional logic instead of a table.
At ⇔ (At ∧ Leftt) ∨ (Bt−1 ∧ Leftt−1 ∧ Kt−1)
At ⇔ (At−1 ∧ Leftt−1) ∨ (Bt−1 ∧ Leftt−1 ∧ Kt−1) At ⇔(At−1 ∧Leftt−1)∨(Bt ∧Leftt ∧Kt)
At ⇔ (At−1 ∧ Leftt−1) ∨ (Bt−1 ∧ Leftt−1 ∧ ¬Kt−1)
(ii) [1 pt] Which of the following statements are correct formulations of the successor-state axiom for Kt? Kt ⇔ Kt−1 ∧ (Ct−1 ∨ Rightt−1)
Kt⇔Kt∨(Ct∧Rightt)
Kt ⇔ Kt−1 ∨ (Ct−1 ∧ Rightt−1)
Kt ⇔ Kt−1 ∨ Dt−1
SID:
9
Q4. [9 pts] Inexpensive Elimination
In this problem, we will be using the Bayes Net below. Assume all random variables are binary-valued.
ABC
GD
E (a) [1 pt] Consider using Variable Elimination to get P (C, G|D = d).
What is the factor generated if B is the first variable to be eliminated? Comma-separate all variables in the resulting factor, e.g., f(A,B,C), without conditioned and unconditioned variables. Alphabetically order variables in your answer. E.g., P(A) before P(B), and P(A|B) before P(A|C).
f( ) = b
(b) Suppose we want to find the optimal ordering for variable elimination such that we have the smallest sum of factor sizes. Recall that all random variables in the graph are binary-valued (that means if there are two factors, one over two variables and another over three variables, the sum of factor sizes is 4+8=12).
In order to pick this ordering, we consider using A* Tree Search. Our state space graph consists of states which represent the variables we have eliminated so far, and does not take into account the order which they are eliminated. For example, eliminating B is a transition from the start state to state B, then eliminating A will result in state AB. Similarly, eliminating A is a transition from the start state to state A, then eliminating B will also result in state AB. An edge represents a step in variable elimination, and has weight equal to the size of the factor generated after eliminating the variable.
?
?
A AB
?2
Start
? 84
B
AE ABE
2 24
?
E 8 BE
(i) [2 pts] Yes/No: As the graph is defined, we have assumed that different elimination orderings of the same subset of random variables will always produce the same final set of factors. Does this hold for all graphs?
Yes No
(ii) [4 pts] For this part, we consider possible heuristics h(s), for a generic Bayes Net which has N variables left to eliminate at state s. Each remaining variable has domain size D. LetthesetEbethecostsofedgesfromstates(e.g. fors=A,EisthecostsofedgesfromAtoAE, and A to AB). Which of the following would be admissible heuristics?
10
SID:
minE maxE N∗D
2minE max(E)/N Noneareadmissible
(c) [2 pts] Now let’s consider A* tree search on our Bayes Net for the query P (C, G|D = d), where d is observed evidence.
Fill in the edge weights (a) − (d) to complete the graph. (b)
A AB
22
(a)
(c)
Start
84
B
AE ABE
(a) =
(c) =
2 24
(d)
E 8 BE
(b) =
(d) =
11
Q5. [10 pts] Sampling
Variables H,F,D,E and W denote the event of being health conscious, having free time, following a healthy diet, exercising and having a normal body weight, respectively. If an event does occur, we denote it with a +, otherwise −, e.g., +e denotes an exercising and −e denotes not exercising.
• A person is health conscious with probability 0.8.
• A person has free time with probability 0.4.
• If someone is health conscious, they will follow a healthy diet with probability 0.9.
• If someone is health conscious and has free time, then they will exercise with probability 0.9.
• If someone is health conscious, but does not have free time, they will exercise with probability 0.4.
• If someone is not health conscious, but they do have free time, they will exercise with probability 0.3.
• If someone is neither health conscious, nor they have free time, then they will exercise with probability 0.1.
• If someone follows both a healthy diet and exercises, they will have a normal body weight with probability 0.9.
• If someone only follows a healthy diet and does not exercise, or vice versa, they will have a normal body weight with probability 0.5.
• If someone neither exercises nor has a healthy diet, they will have a normal body weight with probability 0.2.
(a) [2 pts] Select the minimal set of edges that needs to be added to the following Bayesian network
WDH
EF
D → H F → E D → E D → W H→D D→W F→D W→D H → F H → W E → W E → W
(b) Suppose we want to estimate the probability of a person being normal body weight given that they exercise (i.e. P (+w| + e)), and we want to use likelihood weighting.
(i) [1 pt] We observe the following sample: (−w, −d, +e, +f, −h). What is our estimate of P (+w| + e) given this one sample? Express your answer in decimal notation rounded to the second decimal point, or express it as a fraction simplified to the lowest terms.
(ii) [2 pts] Now, suppose that we observe another sample: (+w, +d, +e, +f, +h). What is our new estimate for P (+w| + e)? Express your answer in decimal notation rounded to the second decimal point, or express it as a fraction simplified to the lowest terms.
(iii) [1 pt] True/False: After 10 iterations, both rejection sampling and likelihood weighting would typically compute equally accurate probability estimates. Each sample counts as an iteration, and rejecting a sample counts as an iteration.
True False
12
SID:
(c) Suppose we now want to use Gibbs sampling to estimate P (+w| + e)
(i) [2 pts] We start with the sample (+w, +d, +e, +h, +f ), and we want to resample the variable W. What is the probability of sampling (−w,+d,+e,+h,+f)? Express your answer in decimal notation rounded to the second decimal point, or express it as a fraction simplified to the lowest terms.
(ii) [1 pt] Suppose we observe the following sequence of samples via Gibbs sampling:
(+w, +d, +e, +h, +f), (−w, +d, +e, +h, +f), (−w, −d, +e, +h, +f), (−w, −d, +e, −h, +f)
What is your estimate of P (+w| + e) given these samples?
(iii) [1 pt] While estimating P (+w| + e), the following is a possible sequence of sample that can be obtained via Gibbs sampling:
(+w, +d, +e, +h, +f), (−w, +d, +e, +h, +f), (−w, −d, +e, +h, +f), (−w, −d, +e, −h, +f), (−w, −d, −e, −h, +f) True False
13
Q6. [11 pts] HMM Smoothing
Consider the HMM with state variables Xt and observation variables Et. The joint distribution is given by
T−1 T
P(X1:T,E1:T =e1:T)=P(X1)P(Xt+1|Xt)P(Et=et|Xt).
t=1 t=1
where X1:T means X1, ..., XT and E1:T = e1:T means E1 = e1, ..., ET = eT . We learned about how the forward al- gorithm can be used to solve the filtering problem, which calculates P (Xt|E1:t = e1:t). We will now focus on the smoothing problem, which calculates P (Xt |E1:T = e1:T ), where 1 ≤ t < T , for obtaining a more informed estimate of the past state Xt given all observed evidence E1:T .
Now define the following vectors of probabilities:
• α(Xt) ≡ P (E1:t = e1:t, Xt), the probability of seeing evidence E1 = e1 through Et = et and being in state Xt;
• β(Xt)≡P(Et+1:T =et+1:T|Xt),theprobabilityofseeingevidenceEt+1=et+1 throughET =eT havingstarted in state Xt.
(a) [2 pts] Let us consider β(XT−1). Which of the following are equivalent to P(ET =eT|XT−1)? (Select one or more.)
xt P(XT =xt|XT−1)P(ET =eT |XT =xt)
xt P(XT =xt|XT−1)P(ET =eT |XT =xt,XT−1)
P(XT =xt|XT−1)P(ET =eT |XT =xt)
P(XT =xt|XT−1)P(ET =eT |XT =xt,XT−1)
(b) [4 pts] In lecture we covered the forward recursion for filtering. An almost identical algorithm can be derived for computing the sequence α(X1), . . . , α(XT ). For β, we need a backward recursion. What is the appropriate expression for β(Xt) to implement such a recursion? The expression may have up to four parts, as follows:
P(Et+1 =et+1,...,ET =eT|Xt)=
For each blank (i) through (iv), mark the appropriate subexpression. If it is possible to write the expression for β(Xt) without a particular subexpression, mark “None.”
(i)
(ii)
(iii)
(iv)
(i) [1 pt] (ii) [1 pt]
(iii) [1 pt] (iv) [1 pt]
xt−1 xt
α(Xt−1 = xt−1) β(Xt−1 = xt−1)
P (Xt = xt|Xt−1) P(Xt|Xt−1 =xt−1)
P (Et−1 = et−1|Xt−1)
P(Et−1 = et−1|Xt−1 = xt−1) None
None xt+1
α(Xt = xt)
β(Xt+1 = xt+1)
P (Xt+1 = xt+1|Xt) P(Xt+1|Xt =xt)
P (Et = et|Xt)
P(Et = et|Xt = xt)
α(Xt+1 = xt+1) None
None
P (Et+1 = et+1|Xt+1)
P(Et+1 = et+1|Xt+1 = xt+1)
14
SID:
(c) [1 pt] If the number of values that each Xt can take on is K and the number of timesteps is T, what is the
total computational complexity of calculating β(Xt) for all t, where 1 ≤ t ≤ T?
O(K) O(T) OK2T OKT2 OK2T2 None
(d) [2 pts] Which of the following expressions are equivalent to P (Xt = xt|E1:T = e1:T )? (Select one or more.) x′t α(Xt = x′t)β(Xt = x′t)
α(Xt = xt)β(Xt = xt) α(Xt=xt)β(Xt=xt)
x′t α(Xt=x′t)β(Xt=x′t) α(Xt=xt)β(Xt=xt)
′ α(XT=x′) xT
T
(e) [2 pts] If the number of values that each Xt can take on is K and the number of timesteps is T, what is the lowest total computational complexity of calculating P (Xt |E1:T = e1:T ) for all t, where 1 ≤ t ≤ T ?
O(K) O(T) OK2T OKT2 OK2T2 None
15
Q7. [8 pts] Partying Particle #No Filter(ing)
Algorithm 1 Particle Filtering
1: 2: 3: 4: 5: 6: 7: 8: 9:
procedure Particle Filtering(T,N) ◃ T: number of time steps, N: number of sampled particles
x ← sample N particles from initial state distribution P(X0) for t ← 0 to T − 1 do
xi ← sample particle from P(Xt+1|Xt = xi) for i = 1,...,N wi ← P(Et+1|Xt+1 = xi) for i = 1,...,N
x ← resample N particles according to weights w
end for
return x end procedure
◃ Initialize ◃ Xt: hidden state, Et: observed evidence ◃ Time Elapse Update ◃ Evidence Update ◃ Particle Resampling
Algorithm 1 outlines the particle filtering algorithm discussed in lecture. The variable x represents a list of N particles, while w is a list of N weights for those particles.
(a) Here, we consider the unweighted particles in x as approximating a distribution. (i) [1 pt] After executing line 4, which distribution do the particles x represent?
P(Xt+1|E1:t) P(X1:t+1|E1:t) P(Xt+1|E1:t+1) (ii) [1 pt] After executing line 6, which distribution do the particles x represent?
P(Xt+1|Xt,E1:t+1) P(X1:t+1|E1:t+1) P(Xt+1|E1:t+1)
None None
(b) The particle filtering algorithm should return a sample-based approximation to the true posterior distribution P (XT | E1:T ). The algorithm is consistent if and only if the approximation converges to the true distribution as N → ∞. In this question, we present several modifications to Algorithm 1. For each modification, indicate if the algorithm is still consistent or not consistent, and if it is consistent, indicate whether you expect it to be more accurate in general in terms of its estimate of P (XT | E1:T ) (i.e., you would expect the estimated distribution to be closer to the true one) or less accurate. Assume unlimited computational resources and arbitrary precision arithmetic.
(i) [2 pts] We modify line 6 to sample 1 or 2N − 1 particles with equal probability p = 0.5 for each time step (as opposed to a fixed number of particles N). You can assume that P(Et+1|Xt+1) > 0 for all observations and states. This algorithm is:
Consistent and More Accurate Not Consistent Consistent and Less Accurate
(ii) [1 pt] Replace lines 4–6 as follows:
4′: Compute a tabular representation of P(Xt = s|E1:t) based on the proportion of particles in state s. 5′: Use the forward algorithm to calculate P(Xt+1|E1:t+1) exactly from the tabular representation.
6′: Set x to be a sample of N particles from P(Xt+1|E1:t+1).
This algorithm is:
Consistent and More Accurate Not consistent Consistent and Less Accurate
(iii) [1 pt] At the start of the algorithm, we initialize each entry in w to 1s. Keep line 4, but replace lines 5 and 6 with the following multiplicative update:
5′: For i = 1,…,N do
6′ wi ←wi ∗P(Et+1|Xt+1 =xi).
Finally, only at the end of the T iterations, we resample x according to the cumulative weights w just like in line 6, producing a list of particle positions. This algorithm is:
Consistent and More Accurate Consistent and Less Accurate
Not Consistent
16
(c) [2 pts] Suppose that instead of particle filtering we run the following algorithm on the Bayes net with T time steps corresponding to the HMM:
1. Fix all the evidence variables E1:T and initialize each Xt to a random value xt. 2. For i = 1, . . . , N do
• Choose a variable Xt uniformly at random from X1, . . . , XT .
• Resample Xt according to the distribution P(Xt|Xt−1 = xt−1,Xt+1 = xt+1,Et = et). • Record the value of XT as a sample.
Finally, estimate P (XT = s|E1:T = e1:T ) by the proportion of samples with XT = s. This algorithm is:
Consistent
Not Consistent
17
SID:
Q8. [11 pts] Double Decisions and VPI
In both parts of this problem, you are given a decision network with two decision nodes: D1 and D2. Your total utility is the sum of two subparts: Utotal = U1 + U2, where U1 only depends on decision D1 and U2 only depends on decision D2.
(a) Consider the following decision network:
FG
U1 A B U2
For each subpart below, select all comparison relations that are true or could be true.
D1
D2
(i) [1 pt] VPI({A,B})
(iii) [1 pt] VPI({B,G})
(ii) [1 pt]
> >
= VPI(A)+VPI(B) VPI({A,F}) = VPI(A)+VPI(F) < <
>
= VPI(G) <
(b) Now consider the following decision network:
FG
U1 A B U2
For each subpart below, select all comparison relations that are true or could be true.
D1
D2
(i) [2 pts] VPI({F,G})
(iii) [2 pts] VPI({B,G})
(ii) [2 pts]
> >
= VPI(F)+VPI(G) VPI({A,F}) = VPI(A)+VPI(F) < <
>
= VPI(G) <
18
SID:
(c) [2 pts] Select all statements that are true. For the first two statements, consider the decision network above.
IfA,Bareindependent,thenVPI(B)=0
IfA,Bareguaranteedtobedependent,thenVPI(B)>0
In general, Gibbs Sampling can estimate the probabilities used when calculating VPI In general, Particle Filtering can estimate the probabilities used when calculating VPI
19
Q9. [11 pts] Naively Fishing
Pacman has developed a hobby of fishing. Over the years, he has learned that a day can be considered fit or unfit for fishing Y which results in three features: whether or not Ms. Pacman can show up M, the temperature of the day T, and how high the water level is W. Pacman models it as the following Naive Bayes classification problem, shown below:
Y
WTM
(a) We wish to calculate the probability a day is fit for fishing given features of the day. Consider the conditional probability tables that Pacman has estimated over the years:
(i) [1 pt] Using the method of Naive Bayes, what are these conditional probabilities, calculated from the conditional probability tables above? Fill in your final, decimal answer in the boxes below.
P(Y = yes|M = yes,T = cold,W = high) =
P(Y = no|M = yes,T = cold,W = high) =
(ii) [1 pt] Using the method of Naive Bayes, do we predict that the day is fit for fishing if Ms. Pacman is
available, the weather is cold, and the water level is high?
Fit for fishing Not fit for fishing
(b) Assume for this problem we do not have estimates for the conditional probability tables, and that Pacman is still using a Naive Bayes model. Write down an expression for each of the following queries. Express your solution using the conditional probabilities P (M |T ), P (T |Y ), P (W |Y ), and P (Y ) from the Naive Bayes model.
(i) [1 pt] Pacman now wishes to find the probability of Ms. Pacman being available or not given that the temperature is hot and the water level is low. Select all expressions that are equal to P(M|T,W).
f P(f)P(M|f)P(T|f)P(W|f) P(M|f) P(M|f)P(T|f)P(W|f) None of the above f P(f)P(W|f)P(T|f) f f P(T|f)P(W|f)
(ii) [2 pts] Pacman now wants to now choose the class that gives the maximum P(features|class), that is, choosing the class that maximizes the probability of seeing the features. Write an expression that is equal to P(M,T,W|Y).
P(M,T,W|Y) =
(iii) [2 pts] Assume that Pacman is equally likely to go fishing as he is to not, i.e. P (Y = yes) = P (Y = no). Which method would give the correct Naive Bayes classification of whether a day is a good day for fishing if Pacman observes values for M, T, and W?
argmaxy P(M,T,W|Y = y) argmaxy P(Y = y|M,T,W) None of the above 20
T
Y
P(T|Y)
M
Y
P(M|Y)
W
Y
P(W|Y)
cold
yes
0.2
Y
P(Y)
yes
yes
0.5
high
yes
0.1
warm
yes
0.2
yes
0.1
no
yes
0.5
low
yes
0.9
hot
yes
0.5
no
0.9
yes
no
0.2
high
no
0.5
cold
no
0.1
no
no
0.8
low
no
0.5
warm
no
0.2
hot
no
0.6
(c) Assume Pacman now has the underlying Bayes Net model, and the conditional probability tables from the previous parts do not apply. Recall that predictions are made under the Naive Bayes classification using the conditional probability, P(Y|W,T,M), and the Naive Bayes assumption that features are independent given the class. We wish to explore if the Naive Bayes model is guaranteed to be able to able to represent the true distribution.
For each of the following true distributions, select 1) if the Naive Bayes modeling assumption holds and 2) if the Naive Bayes model is guaranteed to be able to represent the true conditional probability, P(Y|W,T,M).
(i) [2 pts]
Y
WT
M
(ii) [2 pts]
Y
AB
WMT
Does the Naive Bayes modeling assumption hold here?
Yes No
Does the Naive Bayes modeling assumption hold here?
Yes No
Can the Naive Bayes model represent the true conditional
distribution P (Y |W, T , M )? Yes No
Can the Naive Bayes model represent the true conditional
distribution P (Y |W, T , M )? Yes No
SID:
21
Q10. [13 pts] Neural Networks and Decision Trees
(a) Given the Boolean function represented by the truth table on the right, indicate which of the models can perfectly represent this function for some choice of parameters. Where no constraints are stated on the archi- tecture (e.g. the number of neurons, activation function), answer yes if there exists some architecture which could represent the function.
(i) [2pts]f(x,y)=x⊕ycanbemodelledby:
A neural network with a single layer (no hidden layer) A neural network with two layers (a single hidden layer) A decision tree of depth one
A decision tree of depth two
(ii) [2pts]f(x,y)=¬(x∨y)canbemodelledby:
A neural network with a single layer (no hidden layer) A neural network with two layers (a single hidden layer) A decision tree of depth one
A decision tree of depth two
xyx⊕y 000
0 1 1 101 110
x y ¬(x∨y) 001
0 1 0 100 110
(b) Ada is training a single layer (no hidden layer) neural network to predict a one-dimensional value from a one-dimensional input:
f(x) = g(Wx + b)
where g(y) = relu(y) = max(0, y). She initializes her weight and bias parameters to be:
W=−1, b=0. (i) [1 pt] The derivative of the ReLU function takes the form:
s y>u, t y
≤ ∂f ≤ ∂W
take on for the current values of W and b?
SID:
(iv) [1 pt] Suppose we now use gradient descent to train W and b to minimize a squared loss. Assume the training data consists only of inputs x > 0. For the given weight initialization, which of the following activation functions will result in the loss decreasing over time? You may find your answer to (b)(iii) helpful.
Rectified Linear Unit: g(y) = relu(y). Hyperbolic Tangent: g(y) = tanh y. Sigmoid Function: g(y) = σ(y).
(c) [1 pt] Suppose you have found a learning rate αb that achieves low loss when using batch gradient descent. A learning rate αs for stochastic gradient descent that achieves similarly low loss would be expected to be:
Higher than for batch gradient descent: αs > αb Lower than for batch gradient descent: αs < αb
(d) Your friend Alex is training a deep neural network, AlexNet, to classify images. He observes that the training loss is low, but that loss on a held-out validation dataset is high. Validation loss can be improved by:
(i) [1 pt]
Decreasing the number of layers. Increasing the number of layers.
(ii) [1 pt]
Decreasing the size of each hidden layer. Increasing the size of each hidden layer.
23