CSE 471 – Practice Final Spring 2019
Note: These questions are meant to help guide your studying for the exam only. It is not guaranteed that this practice midterm covers all of this material (though we have tried to cover as much as possible) and it is not guaranteed that every topic on this practice will show up on the midterm. We will go over this practice midterm and its solutions in the review session. Goodluck!
The Final Exam will be comprehensive which means that it will cover material from the entire semester including the material covered since midterm 2. This practice test only includes the new material covered since midterm 2 but note that you are responsible for material from the entire course. Therefore, please revisit your practice midterms 1 and 2 for a more complete study guide for the final exam. Below is a list of topics that may be covered on the final exam:
Topics List
I.
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Uninformed search (BFS, DFS, A*) Informed search
Adversarial search
Constraint Satisfaction Problems Reinforcement learning
Markov Models and Markov Decision Processes Hidden Markov Models
Inference with Hidden Markov Models Bayesian Networks and Inference
Machine Learning and Perceptrons
Bayesian Networks
1. Consider the following Bayesian Network containing four Boolean random variables.
i. [4] Compute P(¬A, B, ¬C, D)
A. 0.216
B. 0.054
C. 0.024
D. 0.006
E. None of the above
ii. [4] Compute P(A | B, C, D)
A. 0.0315
B. 0.0855
C. 0.368
D. 0.583
E. None of the above
The next two questions do NOT refer to the specific Bayesian Network shown above, but rather are about other Bayesian Networks.
iii. [2] True or False: The Bayesian Network associated with the following computation of a joint probability: P(A) P(B) P(C | A, B) P(D | C) P(E | B, C) has arcs from node A to C, from B to C, from B to E, from C to D, from C to E, and no other arcs.
A. True
B. False
iv. [2] True or False: The following product of factors corresponds to a valid Bayesian Network over the variables A, B, C and D: P(A | B) P(B | C) P(C | D) P(D | A).
a. True
b. False
2. The Bayes’ net R represents the joint distribution P (A, B, C, D, E). Observing or summing out a variable results in a reduced Bayes’ net R’ without that variable.
Important: these questions are about separate reductions of the joint distribution. Your answer to one should not affect the others.
a) Consider the reduced distribution P (A, B, D, E) = Σc P (A, B, c, D, E) after C has been summed out. Draw a Bayes’ net structure with the minimal number of edges that can represent this distribution. If no edges are needed, write “NONE” next to the diagram.
(b) Consider the reduced distribution P (B, C, D, E| + a) when A has been observed.
Draw a Bayes’ net structure with the minimal number of edges that can represent this distribution. If no edges are needed, write “NONE” next to the diagram.
(c) Consider the reduced distribution P (A, B, C, D| − e) when E has been observed.
Draw a Bayes’ net structure with the minimal number of edges that can represent this distribution. If no edges are needed, write “NONE” next to the diagram.
3. For the Bayes’ Net shown below, compute the requested quantities.
P(D)
+d
0.1
−d
0.9
P(X|D)
+d
+x
0.7
+d
−x
0.3
−d
+x
0.8
−d
−x
0.2
P(B|D)
+d
+b
0.7
+d
−b
0.3
−d
+b
0.5
−d
−b
0.5
P(A|D,X)
+d
+x
+a
0.9
+d
+x
−a
0.1
+d
−x
+a
0.8
+d
−x
−a
0.2
−d
+x
+a
0.6
−d
+x
−a
0.4
−d
−x
+a
0.1
−d
−x
−a
0.9
(a) What is the probability of having disease D and getting a positive result on test A? P (+d, +a) =
(b) What is the probability of not having disease D and getting a positive result on test A? P (−d, +a) =
(c) What is the probability of having disease D given a positive result on test A? P (+d| + a) =
(d) What is the probability of having disease D given a positive result on test B? P (+d| + b) =
II. Perceptrons
4. (i) Suppose we have a multiclass perceptron with three classes A, B, C and with weights initially set to wA = [1, 2], wB = [2, 0], wC = [2, −1]. Write out the vectors wA, wB, wC of the perceptron after training on the following two dimensional training example once.
wA = [ _____, _____ ] wB = [_____ , _____ ] wC = [_____, _____ ]
(ii) Suppose we have a different multiclass perceptron with three classes A, B, C and with weights initially set to wA = [2, 4], wB = [−1, 0], wC = [2, −2]. Write out the vectors wA, wB, wC of the perceptron after training on the following two dimensional training example once.
wA = [ _____, _____ ] wB = [_____ , _____ ] wC = [_____, _____ ]
(i) Suppose we have a different multiclass perceptron with three classes A, B, C and with weights initially set to wA = [1, 0], wB = [1, 1], wC = [3, 0]. After training on the following set of training data an infinite number of times, select which of the following options must be True given no additional information. Convergence indicates that the values do not change even within a pass through the data set.
III. Artificial Neural Networks
5. Below is a diagram if a single artificial neuron (unit):
a. The node has three inputs x=(x1,x2,x3) that receive only binary signals (either 0 or 1). How many different input patterns can this node receive? What if the node had four inputs? Five? Can you give a formula that computes the number of binary input patterns for a given number of inputs?
b. Consider the unit shown in Figure 1. Suppose that the weights corresponding to the three inputs have the following values:
And the activation of the unit is given by the step-function:
Calculate what will be the output value y of the unit for each of the following input patterns:
6. For the following questions, mark ALL neural networks that can compute the same function as the boolean expression. If none of the neural nets can do this, mark None. Booleans will take values 0, 1, and each perceptron will output values 0, 1. You may assume that each perceptron also has as input a bias feature that always takes the value 1. It may help to write out the truth table for each expression. Note that X ⇒ Y is equivalent to (NOT X) OR Y.
a. A 1
2
3
4 None
b. AORB 1
2
3
4 None
c. BXORC 1
2
3
4 None
d. (AXORB)XORC 1
2
3
4 None
e. (¬AAND¬BAND¬C)OR(AANDBANDC) 1
2
3
4 None
f. (A⇒B)⇒C 1
2
3
4 None
IV. Learning in Artificial Neural Networks
7. Use the L2 loss function and logistic regression update rule (activation function is the sigmoid) to learn the weights for a single layer logical AND network. Specifically, complete one weight update iteration to learn 𝑤”,$, 𝑤%,$, 𝑤&,$ for the network with output 𝑎$ = 𝑔(𝑤”,$ + 𝑤%,$𝑥% + 𝑤&,$𝑥&. You may use the initialization 𝑤”,$ = −1, 𝑤%,$ = 1, 𝑤&,$ = 1.