Figure 1: A decision tree for estimating whether the patron will be willing to wait for a table at a restaurant.
Suppose that, on the entire set of training samples available for constructing the decision tree of Figure 1, 80 people decide to wait, and 20 people decide not to wait. What is the initial entropy at node A (before the test is applied)? Write an expression that fully specifies the answer numerically.
Answer: We denote by log2(x) the logarithm base 2 of x. Then:
Entropy(A) = -80/100 * log2(80/100) - 20/100 * log2(20/100) = 0.7219
In the decision tree of Figure 1, node D uses the exact same test (whether it is weekend or not) as node A. What is the information gain, at node D, of using the weekend test? Justify your answer.
Answer: The information gain is 0, because all training examples at node D give the same answer (answer=yes) to the question of whether it is weekend.
Your boss at a software company gives you a binary classifier H that predicts, for any basketball game, whether the home team will win or not. Classifier H has a 28% accuracy, and your boss assigns you the task of improving that classifier, so that you get an accuracy that is better than 60%. How do you achieve that task?
Answer: Create a classifier H' that, for any basketball game, outputs the opposite of what H outputs. This is easy to do, since we are given classifier H, so we always know what H outputs. Then, the accuracy of H' will be 72%, more than the 60% we were asked to achieve.
You are a meteorologist that places temperature sensors all of the world, and you set them up so that they automatically e-mail you, each day, the high temperature for that day. Unfortunately, you have forgotten whether you placed a certain sensor S in Maine or in the Sahara desert (but you are sure you placed it in one of those two places) . The probability that you placed sensor S in Maine is 5%. The probability of getting a daily high temperature of 80 degrees or more is 20% in Maine and 90% in Sahara. Assume that probability of a daily high for any day is independent of the daily high for the previous day.
In the following questions, you do not have to perform all numerical calculations, but you have to fully specify the numerical value of each answer.
a. (15 points) Given that the first e-mail you got from sensor S indicates a daily high under 80 degrees, what is the maximum likelihood estimate that sensor S is placed in Maine? Show how you derive your answer.
Answer: The ML estimate is that indeed the sensor S was placed in Maine, since that hypothesis (that the sensor was placed in Maine) maximizes the probability of the data:
P(observation | Maine) = 0.8 > P(observation | Sahara) = 0.1
b. (15 points) Given that the first e-mail you got from sensor S indicates a daily high under 80 degrees, what is the probability that the sensor is placed in Maine?
Answer: Let o1u80 stand for "first observation = daily high under 80 degrees". We first need to compute P(o1u80):
p(o1u80) = p(o1u80 | Maine) * P(Maine) + p(o1u80 | Sahara) * P(Sahara)
= 0.8 * 0.05 + 0.1 * 0.95 = 0.135
Then, we compute P(Maine | o1u80):
p(Maine | o1u80) = p(o1u80 | Maine) * P(Maine) / P(o1u80)
= 0.8 * 0.05 / 0.135 = 0.2963
c. (15 points) Given that the first e-mail you got from sensor S indicates a daily high under 80 degrees, what is the probability that the second e-mail also indicates a daily high under 80 degrees?
Answer: We use these abbreviations:
Then, using the answer from Problem 4b, we compute P(o2u80 | o1u80):
p(o2u80 | o1u80) = p(o2u80 | Maine, o1u80) * P(Maine | o1u80) + p(o2u80 | Sahara, o1u80) * P(Sahara | o1u80)
= 0.8 * 0.2963 + 0.1 * (1 - 0.2963) = 0.3074