CMSC422 fall2017 Problems for Midterm 1 with Answers PDF

Preview

Summary

Fall 2017 Review of exam 1 material for CMSC422...

Description

CMSC 422 Fall, 2017 Practice Questions for Midterm 1 These questions should provide a sense of what topics will be covered in the first Midterm, and the types of questions that might be asked. Decision Trees 1. Suppose you have some training data with three binary features. You want to construct the best possible decision tree of depth 3. If you ask questions about the three features in different orders, will you obtain different results on the training data? Or will you always produce the same results, no matter what order you ask questions? Explain your answer. Answer: You will obtain the same results with any depth three decision tree. Each leaf will contain a decision based on a set of training examples that answer all three questions in the same way. In the end, if you make a decision based on all three questions, it doesn’t matter what order you asked them. 2. Suppose you have the following data: Feature 1 Feature 2 70 299 72 160 66 150 67 175 75 225 61 150 63 155 65 160 62 120 60 102 55 110 57 105 58 98

Label 1 1 1 1 1 0 0 0 0 1 1 1 0

Using a greedy algorithm, build a two level decision tree with only questions like Feature < Value? Answer: The best question for Feature 1 will be F1 < 66. If the answer is no, we will choose the label 1, and get 5/5 right. If the answer is yes, we will return a 0 and get 5/8 right. The best question for Feature 2 will be F2 < 161. This will only get three samples right if the answer is no, so it’s not as good.

What about at the second level of the decision tree? If the answer to F1 < 66 is no, we get everything right, so we don’t need to ask any more questions. If we ask F2 < 120, we can return 0 if the answer is no, and 1 if the answer is yes, and we make only one mistake. Notice that we could do equally well if our second question were F1 < 61. In that case, we return 0 for no and 1 for yes, and only make one mistake. So it can be useful to ask more than one question of a feature.

Bayes Optimal Classifier 3. Suppose I have data with one feature, x, and a label, y. x is a continuous feature with a value between 0 and 2. y is a label with the value -1 or 1. If the label y = 1, then x is a random variable with the probability density function: f (x)=x /2 ∀ x :0 ≤ x ≤ 2 f ( x ) =0 ∀ x : x2 As a reminder, saying that f is a probability density function means that: b

Pr ( a< x< b|y=1 ) =∫ f (x )dx a

So, for example, Pr ( x 2 We can visualize this as:

g(x)

1

0

f(x)

2

What is the Bayes optimal classifier for y? Suppose we are equally likely to have a label of 1 or -1. What is the expected loss of the Bayes optimal classifier? Answer: The Bayes optimal classifier will choose a label of -1 for x1. If the label is 1, we will get the wrong answer for 0...