MIDTERM: CS 6375
INSTRUCTOR: VIBHAV GOGATE
October, 23 2013

The exam is closed book. You are allowed a one-page cheat sheet. Answer the questions in the spaces provided on the question sheets. If you run out of room for an answer, use an additional sheet (available from the instructor) and staple it to your exam.

• NAME

• UTD-ID if known

• SECTION 1:
• SECTION 2:
• SECTION 3:
• SECTION 4:
• SECTION 5:

• Out of 90:

1

CS 6375 FALL 2013

Midterm, Page 2 of 13

October 23, 2013

CS 6375 FALL 2013

Midterm, Page 3 of 13

October 23, 2013

SECTION 1: SHORT QUESTIONS (15 points)
1. (3 points) The Naive Bayes classifier uses the maximum a posteriori or the MAP decision rule for classification. True or False. Explain.
Solution: True. The decision rule for the Naive Bayes classifier is:
P (Xi |Y = y)

arg; max P (Y = y) y i

One can think of P (Y = y) as the prior distribution and P (Xi |Y = y) as the data likelihood.
Note that when we do the learning, we are using the MLE approach. The decision rule is using MAP inference but the learning algorithm is using the MLE approach. Make sure you understand what this distinction means.
2. (6 points) Let θ be the probability that “Thumbtack 1” (we will abbreviate it as T1) shows heads and 2θ be the probability that “Thumbtack 2” (we will abbreviate it as T2) shows heads.
You are given the following Dataset (6 examples).
T1
Tails

T2
Heads

T1
Tails

T1
Tails

T2
Heads

T2
Heads

• What is the likelihood of the data given θ.
Solution: We have 3 tails for T1 and 3 heads for T2.
Therefore, the likelihood is
L(θ) = (1 − θ)3 (2θ)3
The Log-likelihood is:
LL(θ) = 3 log(1 − θ) + 3 log(2) + 3 log(2θ)

• What is the maximum likelihood estimate of θ. (Hint: Derivative of log(x) is 1/x).
Solution: This can be obtained by differentiating the log-likelihood w.r.t. θ, setting it to zero and solving for the value of θ. The derivative of LL(θ) is:
−3

1
1
+6
1−θ
2θ

Setting it to zero and solving for θ, we get: θ = 1/2.

CS 6375 FALL 2013

Midterm, Page 4 of 13

October 23, 2013

3. (2 points) If the data is not linearly separable, then the gradient descent algorithm for training a logistic regression classifier will never converge. True or False. Explain your answer.
Solution: False. Our objective function is always concave. The algorithm will always converge under mild assumptions.
4. (2 points) If the data is linearly separable, then the 3-nearest neighbors algorithm will always have 100% accuracy on the training set. True or False. Explain your answer.
Solution: False. Here is the counter example.
X
Class

0.1
+

0.2
+

1
+

7
−

Here the data is linearly separable. However, the point (7, −) will be misclassified as + by the
3-nearest neighbors algorithm.
5. (2 points) The decision tree classifier has 100% accuracy on the training set (namely, the data is noise-free). Will logistic regression have the same accuracy (100%) on the training set?
Solution: False. Decision tree can learn complex surfaces or Boolean functions (e.g., XOR).
However, logistic regression can only learn linear classification boundaries (e.g., it cannot represent XOR).

CS 6375 FALL 2013

Midterm, Page 5 of 13

October 23, 2013

SECTION 2: Decision Trees (20 points)
1. (4 points) Let x be a vector of n Boolean variables and let k be an integer less than n. Let fk be a target concept which is a disjunction consisting of k literals.
(Let the n variables be denoted by the set {X1 , . . . , Xn }. Examples of f2 : X1 ∨ X2 , X1 ∨ ¬X4 , etc. Examples of f3 : X1 ∨ X2 ∨ X10 , X1 ∨ ¬X4 ∨ X7 , etc.)
State the size of the smallest possible consistent decision tree (namely a decision tree that correctly classifies all possible examples) for fk in terms of n and k and describe its shape.
Solution: The smallest possible decision tree consistent withfk contains 2k + 1 nodes with k internal nodes corresponding to the attributes and k + 1 leaf nodes. Each internal node (except the node at depth k − 1 which has two leaf nodes) has one leaf node corresponding to an assignment of true to the literal and has one child node corresponding to the false assignment to the particular literal.
We wish to learn a decision tree to help students pick restaurants using three aspects – the price, the location of the restaurant and the speed of service. The data for training the tree is given below, where the target concept is the column labeled ”Like?”

2. (4 points) What is the entropy of the collection of examples with respect to the target label
(Like?) ?
Solution: We have 4 +ve and 4 −ve examples. Thus the entropy is 1.

CS 6375 FALL 2013

Midterm, Page 6 of 13

October 23, 2013

SECTION 2: Decision Trees (20 points) — Continued
I have copied the dataset from the previous page to this page for convenience.

3. (4 points) Compute the information gain of the attribute Price.
Solution:
2
1
2
IG = 1 − Entropy(2, 0) − Entropy(1, 3) − Entropy(1, 1)
8
2
8
4. (4 points) Compute the information gain of the attribute Fast?
Solution:
1
1
IG = 1 − Entropy(3, 1) − Entropy(3, 1)
2
2

CS 6375 FALL 2013

Midterm, Page 7 of 13

October 23, 2013

SECTION 2: Decision Trees (20 points) — Continued
I have copied the dataset from the previous page to this page for convenience.

5. (4 points) Choose Price as the root node for the decision tree. With this root node, write down a decision tree that is consistent with the data (namely a decision tree that correctly classifies all the training examples). You do not need to learn the decision tree; just make sure it is consistent with the data.
Solution:

Note. This is just one of the many possible trees.

CS 6375 FALL 2013

Midterm, Page 8 of 13

October 23, 2013

SECTION 3: GRADIENT DESCENT (20 points)
Suppose that the CEO of some startup company calls you and tells you that he sells d items on his web site. He has access to ratings given by n users, each of whom have rated a subset of the the d items. Assume that each rating is a real-number. Your task is to estimate the missing ratings.
(Think of the data as n by d matrix in which some entries are missing and your task is to estimate the missing entries).
Being a good machine learner, you have come up with the following model: xi,j = ai + bj + ui vj where • xi,j is the rating of the j-th product by user i
• ai is the base rating for the user
• bj is the base rating for each item
• ui and vj is some co-efficient for each user and each dimension respectively
Notice that your model has 2(n + d) parameters.
1. (5 points) Set up the machine learning problem of estimating the 2(n + d) parameters as an optimization task of minimizing the squared error. Write down the formula for the squared error and the optimization task.
Solution: Let K denote the set of entries for which the user ratings are known. The formula for the squared error is:
J(K) =

1
2x

(xi,j − ai − bj − ui vj )2 i,j ∈K

The optimization problem is: arg min

ai ,bj ,ui ,vj

J(K)

2. (5 points) Compute the gradient of the error function w.r.t. ai , bj , ui and vj .
Solution: Skipped: Trivial.

CS 6375 FALL 2013

Midterm, Page 9 of 13

October 23, 2013

SECTION 3: GRADIENT DESCENT (20 points) – CONTINUED
3. (5 points) Give the pseudo-code for Batch Gradient Descent for this problem.
Solution: Skipped: Trivial.

4. (5 points) Will you use batch gradient descent or incremental (or stochastic or online) gradient descent for this task. How will the data size measured in terms of n, d and number of missing entries (let us denote these by m) affect your choice?
Solution: If (nd − m) is large, we will use the incremental approach. Otherwise, we will prefer the batch approach.

CS 6375 FALL 2013

Midterm, Page 10 of 13

October 23, 2013

SECTION 4: NEURAL NETWORKS AND PERCEPTRONS (25
POINTS)
Consider the neural network given below:

Assume that all internal nodes compute the sigmoid function. Write an explicit expression to how back propagation (applied to minimize the least squares error function) changes the values of w1 , w2 , w3 , w4 and w5 when the algorithm is given the example x1 = 0, x2 = 1, with the desired response y = 0 (notice that x0 = 1 is the bias term). Assume that the learning rate is α and that the current values of the weights are: w1 = 3, w2 = 2, w3 = 2, w4 = 3 and w5 = 2. Let oj be the output of the hidden units and output units indexed by j.
1. (3 points) Forward propagation. Write equations for o1 , o2 and o3 in terms of the given weights and example.
Answer:
o3 = σ(w1 + w2 x1 ) = σ(3 + 2 ∗ 0) = σ(3) o2 = σ(w3 x3 ) = σ(2 ∗ 1) = σ(2) o1 = σ(w4 o2 + w5 o3 ) = σ(3σ(3) + 2σ(2))
2. (6 points) Backward propagation. Write equations for δ1 , δ2 and δ3 in terms of the given weights and example.
Answer:
δ1 = o1 (1 − o1 )(0 − o1 ) = −o2 (1 − o1 )
1
δ2 = o2 (1 − o2 )(w4 δ1 ) = 3o2 (1 − o2 )δ1 δ3 = o3 (1 − o3 )(w5 δ1 ) = 2o3 (1 − o3 )δ1
3. (5 points) Give an explicit expression for the new weights.
Answer:
w1 = w1 + ηδ2 x0 = 3 + ηδ2 w2 = w2 + ηδ2 x1 = 2

CS 6375 FALL 2013

Midterm, Page 11 of 13

October 23, 2013

w3 = w3 + ηδ3 x2 = 2 + ηδ3 w4 = w4 + ηδ1 o2 = 3 + ηδ1 o2 w5 = w5 + ηδ1 o3 = 2 + ηδ1 o3
4. (5 points) Draw a neural network that represents the following Boolean function: (X1 ∧ X2 ) ∨
(¬X1 ∧ ¬X2 )
Answer: Trivial: Skipped.

CS 6375 FALL 2013

Midterm, Page 12 of 13

October 23, 2013

SECTION 4: NEURAL NETWORKS AND PERCEPTRONS (25
POINTS) – Continued
Consider the neural network given below. Assume that each unit j is a linear unit and its output is of the form oj = C n wi xi where xi ’s are the inputs to the unit and wi is the weight on the i=1 corresponding edge. For example: o2 = C(w1 x1 + w3 x2 ).

5. (6 points) Can any function that is represented by the above network also be represented by a Perceptron having a single linear unit of the form o = P i wi xi where xi are the inputs, wi are the weights attached to the edges and P is a constant. If your answer is yes, then draw the
Perceptron detailing the weights and the value for P (i.e., express the weights, lets say v1 and v2 as well as P of the Perceptron in terms of w1 ,w2 ,w3 ,w4 , w5 , w6 , and C.) If your answer is no, explain why not?

Solution: Yes. It can be represented using a Perceptron with just two inputs X1 and X2 . o1 = C(w5 C(w1 X1 + w3 X2 ) + w6 C(w2 X1 + w4 X3 )) o1 = C 2 (X1 (w5 w1 + w6 w2 ) + X2 (w5 w3 + w6 w4 )
Thus assuming that the new Perceptron output is of the form: P (v1 X1 + v2 X2 ), we have
P = C2 v1 = (w5 w1 + w6 w2 ) v2 = (w5 w3 + w6 w4 )

CS 6375 FALL 2013

Midterm, Page 13 of 13

October 23, 2013

SECTION 5: K nearest neighbors (10 points)
Let us employ the leave one out cross validation approach to choose k in k nearest neighbors.
As the name suggests, it involves using a single example from the training data as the test (or validation) data, and the remaining examples as the training data. This is repeated such that each example in the training data is used once as the test data.
Formally, given a classifier C, the approach computes the Error of C as follows. Let d be the number of training examples and let us assume that the examples are indexed from 1 to d.
• Error = 0
• For i = 1 to d
– Remove the i-th example from the training set and use it as your test set
– Train the classifier C on the new training set
– If the test example is incorrectly classified by C then Error = Error + 1
– Put back the i-th example in the training set
• Return Error
To select the best classifier among a group of classifiers, you apply the leave-one-out cross validation approach to all the classifiers and choose the one that has the smallest error.
Dataset:

X
Class

-0.1
-

0.7
+

1.0
+

1.6
-

2.0
+

2.5
+

3.2
-

3.5
-

4.1
+

4.9
+

1. (4 points) What is the leave-one-out cross validation error of 1 nearest neighbor algorithm on the dataset given above (use Euclidean distance). Explain your answer.
Solution: 4.

2. (4 points) What is the leave-one-out cross validation error of 3 nearest neighbor algorithms on the dataset given above (use Euclidean distance). Explain your answer.
Solution: 8.

3. (2 points) Will you choose k = 1 or k = 3 for this dataset?
Solution: Choose k = 1. Because the leave one out cross validation error of k = 1 is smaller than that of k = 3