15.097 Lecture 8: Decision Trees

Decision Trees MIT 15.097 Course Notes Credit: Russell & Norvig, Mitchell, Kohavi & Quinlan, Carter, Vanden Berghen Why trees? • interpretable/intuitive, popular in medical applications because they mimic the way a doctor thinks • model discrete outcomes nicely • can be very powerful, can be as complex as you need them • C4.5 and CART - from “top 10” - decision trees are very popular Some real examples (from Russell & Norvig, Mitchell) • BP’s GasOIL system for separating gas and oil on offshore platforms - decision trees replaced a hand-designed rules system with 2500 rules. C4.5-based system outperformed human experts and saved BP millions. (1986) • learning to fly a Cessna on a flight simulator by watching human experts fly the simulator (1992) • can also learn to play tennis, analyze C-section risk, etc. How to build a decision tree: • Start at the top of the tree. • Grow it by “splitting” attributes one by one. To determine which attribute to split, look at “node impurity.” • Assign leaf nodes the majority vote in the leaf. • When we get to the bottom, prune the tree to prevent overfitting Why is this a good way to build a tree? 1 I have to warn you that C4.5 and CART are not elegant by any means that I can define elegant. But the resulting trees can be very elegant. Plus there are 2 of the top 10 algorithms in data mining that are decision tree algorithms! So it’s worth it for us to know what’s under the hood... even though, well... let’s just say it ain’t pretty. Example: Will the customer wait for a table? (from Russell & Norvig) Here are the attributes: 1. Alternate: whether there is a suitable alternative restaurant nearby. 2. Bar: whether the restaurant has a comfortable bar area to wait in. 3. Fri/Sat: true on Fridays and Saturdays. 4. Hungry: whether we are hungry. 5. Patrons: how many people are in the restaurant (values are None, Some, and Full). 6. Price: the restaurant's price range ($, $$, $$$). 7. Raining: whether it is raining outside. 8. Reservation: whether we made a reservation. 9. Type: the kind of restaurant (French, Italian, Thai or Burger). 10. WaitEstimate: the wait estimated by the host (0-10 minutes, 10-30, 30-60, >60). Image by MIT OpenCourseWare, adapted from Russell and Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 2009. Here are the examples: Example Attributes Goal Alt Bar Fri Hun Pat Price Rain Res Type Est WillWait X1 Yes No No Yes Some $$$ No Yes French 0-10 Yes X2 Yes No No Yes Full $ No No Thai 30-60 No X3 No Yes No No Some $ No No Burger 0-10 Yes X4 Yes No Yes Yes Full $ No No Thai 10-30 Yes X5 Yes No Yes No Full $$$ No Yes French >60 No X6 No Yes No Yes Some $$ Yes Yes Italian 0-10 Yes X7 No Yes No No None $ Yes No Burger 0-10 No X8 No No No Yes Some $$ Yes Yes Thai 0-10 Yes X9 No Yes Yes No Full $ Yes No Burger >60 No X10 Yes Yes Yes Yes Full $$$ No Yes Italian 10-30 No X11 No No No No None $ No No Thai 0-10 No X12 Yes Yes Yes Yes $ No No 30-60 Yes Full Burger Image by MIT OpenCourseWare, adapted from Russell and Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 2009. Here are two options for the first feature to split at the top of the tree. Which one should we choose? Which one gives me the most information? 2 X1,X3,X4,X6,X8,X12 X2,X5,X7,X9,X10,X11 +: -: (a) Patrons? None Some +: - : X7,X11 +: X4,X12 - : X2,X5,X9,X10 +: X1,X3,X6,X8 -: X1,X3,X4,X6,X8,X12 X2,X5,X7,X9,X10,X11 +: -: Type? (b) French +: -: Full Italian +: X6 - : X10 X1 X5 Burger Thai +: X4,X8 +: X3,X12 - : X2,X11 - : X7,X9 Image by MIT OpenCourseWare, adapted from Russell and Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 2009. What we need is a formula to compute “information.” Before we do that, here’s another example. Let’s say we pick one of them (Patrons). Maybe then we’ll pick Hungry next, because it has a lot of “information”: +: -: (c) X1,X3,X4,X6,X8,X12 X2,X5,X7,X9,X10,X11 Patrons? None +: - : X7,X11 Yes Some Full +: X1,X3,X6,X8 -: +: X4,X12 - : X2,X5,X9,X10 No Hungry? Yes No +: X4,X12 +: - : X2,X10 - : X5,X9 Image by MIT OpenCourseWare, adapted from Russell and Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 2009. We’ll build up to the derivation of C4.5. Origins: Hunt 1962, ID3 of Quinlan 1979 (600 lines of Pascal), C4 (Quinlan 1987). C4.5 is 9000 lines of C (Quinlan 1993). We start with some basic information theory. 3 Information Theory (from slides of Tom Carter, June 2011) “Information” from observing the occurrence of an event := #bits needed to encode the probability of the event p = − log2 p. E.g., a coin flip from a fair coin contains 1 bit of information. If the event has probability 1, we get no information from the occurrence of the event. Where did this definition of information come from? Turns out it’s pretty cool. We want to define I so that it obeys all these things: • I(p) ≥ 0, I(1) = 0; the information of any event is non-negative, no information from events with prob 1 • I(p1 · p2 ) = I(p1 ) + I(p2 ); the information from two independent events should be the sum of their informations • I(p) is continuous, slight changes in probability correspond to slight changes in information Together these lead to: I(p2 ) = 2I(p) or generally I(pn ) = nI(p), this means that  I(p) = I (p 1/m m )   = mI p 1/m    1 1/m so I(p) = I p m and more generally, n I(p). m This is true for any fraction n/m, which includes rationals, so just define it for all positive reals: I(pa ) = aI(p).  I p n/m  = The functions that do this are I(p) = − logb (p) for some b. Choose b = 2 for “bits.” 4 Flipping a fair coin gives − log2 (1/2) = 1 bit of information if it comes up either heads or tails. A biased coin landing on heads with p = .99 gives − log2 (.99) = .0145 bits of information. A biased coin landing on heads with p = .01 gives − log2 (.01) = 6.643 bits of information. Now, if we had lots of events, what’s the mean information of those events? Assume the events v1 , ..., vJ occur with probabilities p1 , ..., pJ , where [p1 , ..., pJ ] is a discrete probability distribution. Ep∼[p1 ,...,pJ ] I(p) = J X pj I(pj ) = − j=1 X pj log2 pj =: H(p) j where p is the vector [p1 , ..., pJ ]. H(p) is called the entropy of discrete distribution p. So if there are only 2 events (binary), with probabilities p = [p, 1 − p], H(p) = −p log2 (p) − (1 − p) log2 (1 − p). If the probabilities were [1/2, 1/2], 1 1 H(p) = −2 log2 = 1 (Yes, we knew that.) 2 2 Or if the probabilities were [0.99, 0.01], H(p) = 0.08 bits. As one of the probabilities in the vector p goes to 1, H(p) → 0, which is what we want. Back to C4.5, which uses Information Gain as the splitting criteria. 5 Back to C4.5 (source material: Russell & Norvig, Mitchell, Quinlan) We consider a “test” split on attribute A at a branch. In S we have #pos positives and #neg negatives. For each branch j, we have #posj positives and #negj negatives. The training probabilities in branch j are:   #posj #negj , . #posj + #negj #posj + #negj The Information Gain is calculated like this: Gain(S, A) = expected reduction in entropy due to branching on attribute A = original entropy − entropy after branching   #pos #neg = H , #pos + #neg #pos + #neg   J X #posj + #negj #posj #negj − H , . #pos + #neg #pos + #neg #pos + #neg j j j j j=1 Back to the example with the restaurants.      1 1 2 4 6 2 4 Gain(S, Patrons) = H , − H([0, 1]) + H([1, 0]) + H , 2 2 12 12 12 6 6 ≈ 0.541 bits.      2 1 1 2 1 1 Gain(S, Type) = 1 − H , + H , 12 2 2 12 2 2     4 2 2 4 2 2 + H , + H , ≈ 0 bits. 12 4 4 12 4 4 6 Actually Patrons has the highest gain among the attributes, and is chosen to be the root of the tree. In general, we want to choose the feature A that maximizes Gain(S, A). One problem with Gain is that it likes to partition too much, and favors numerous splits: e.g., if each branch contains 1 example: Then,   #posj #negj H , = 0 for all j, #posj + #negj #posj + #negj so all those negative terms would be zero and we’d choose that attribute over all the others. An alternative to Gain is the Gain Ratio. We want to have a large Gain, but also we want small partitions. We’ll choose our attribute according to: Gain(S, A) ← want large SplitInfo(S, A) ← want small where SplitInfo(S, A) comes from the partition: SplitInfo(S, A) = − J X |Sj | j=1  |Sj | log |S| |S|  where |Sj | is the number of examples in branch j. We want each term in the |S | sum to be large. That means we want |S|j to be large, meaning that we want lots of examples in each branch. Keep splitting until: 7 • no more examples left (no point trying to split) • all examples have the same class • no more attributes to split For the restaurant example, we get this: Patrons? None No Full Some Hungry? Yes No Yes Type? No French Italian Yes Thai No Burger Fri/Sat? No Yes No Yes Yes The decision tree induced from the 12-example training set. Image by MIT OpenCourseWare, adapted from Russell and Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 2009. A wrinkle: actually, it turns out that the class labels for the data were themselves generated from a tree. So to get the label for an example, they fed it into a tree, and got the label from the leaf. That tree is here: 8 Patrons? None Some No YES Full WaitEstimate? >60 30-60 No Alternate? 10-30 0-10 Hungry? Yes No Yes No Reservation? Fri/Sat? Yes Yes Alternate? No Yes No Yes No Yes Bar? Yes No Yes Yes Raining? No Yes No Yes No Yes No Yes A decision tree for deciding whether to wait for a table. Image by MIT OpenCourseWare, adapted from Russell and Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 2009. But the one we found is simpler! Does that mean our algorithm isn’t doing a good job? There are possibilities to replace H([p, 1 − p]), it is not the only thing we can use! One example is the Gini index 2p(1 − p) used by CART. Another example is the value 1 − max(p, 1 − p).1 1 If an event has prob p of success, this value is the proportion of time you guess incorrectly if you classify the event to happen when p > 1/2 (and classify the event not to happen when p ≤ 1/2). 9 0.5 0.4 Entropy Gini index 0.3 Misclassification error 0.2 0.1 0.0 0.0 0.2 0.4 0.6 0.8 1.0 p Node impurity measures for two-class classification, as a function of the proportion p in class 2. Cross-entropy has been scaled to pass through (0.5, 0.5). Image by MIT OpenCourseWare, adapted from Hastie et al., The Elements of Statistical Learning, Springer, 2009. C4.5 uses information gain for splitting, and CART uses the Gini index. (CART only has binary splits.) Pruning Let’s start with C4.5’s pruning. C4.5 recursively makes choices as to whether to prune on an attribute: • Option 1: leaving the tree as is • Option 2: replace that part of the tree with a leaf corresponding to the most frequent label in the data S going to that part of the tree. • Option 3: replace that part of the tree with one of its subtrees, corresponding to the most common branch in the split Demo To figure out which decision to make, C4.5 computes upper bounds on the probability of error for each option. I’ll show you how to do that shortly. • Prob of error for Option 1 ≤ UpperBound1 • Prob of error for Option 2 ≤ UpperBound2 10 • Prob of error for Option 3 ≤ UpperBound3 C4.5 chooses the option that has the lowest of these three upper bounds. This ensures that (w.h.p.) the error rate is fairly low. E.g., which has the smallest upper bound: • 1 incorrect out of 3 • 5 incorrect out of 17, or • 9 incorrect out of 32? For each option, we count the number correct and the number incorrect. We need upper confidence intervals on the proportion that are incorrect. To calculate the upper bounds, calculate confidence intervals on proportions. The abstract problem is: say you flip a coin N times, with M heads. (Here N is the number of examples in the leaf, M is the number incorrectly classified.) What is an upper bound for the probability p of heads for the coin? Think visually about the binomial distribution, where we have N coin flips, and how it changes as p changes: p=0.5 p=0.1 p=0.9 We want the upper bound to be as large as possible (largest possible p, it’s an upper bound), but still there needs to be a probability α to get as few errors as we got. In other words, we want: PM ∼Bin(N,preasonable upper bound ) (M or fewer errors) ≥ α 11 which means we want to choose our upper bound, call it pα ), so that it’s the largest possible value of preasonable upper bound that still satisfies that inequality. That is, PM ∼Bin(N,pα ) (M or fewer errors) ≈ α M X Bin(z, N, pα ) ≈ α z=0 M  X z=0  N z pα (1 − pα )N −z ≈ α for M > 0 z (for M = 0 it’s (1 − pα )N ≈ α) We can calculate this numerically without a problem. So now if you give me α M and N , I can give you pα . C4.5 uses α = .25 by default. M for a given branch is how many misclassified examples are in the branch. N for a given branch is just the number of examples in the branch, |Sj |. So we can calculate the upper bound on a branch, but it’s still not clear how to calculate the upper bound on a tree. Actually, we calculate an upper confidence bound on each branch on the tree and average it over the relative frequencies of landing in each branch of the tree. It’s best explained by example: Let’s consider a dataset of 16 examples describing toys (from the Kranf Site). We want to know if the toy is fun or not. 12 Color Max number of players Fun? red 2 yes red 3 yes green 2 yes red 2 yes green 2 yes green 4 yes green 2 yes green 1 yes red 2 yes green 2 yes red 1 yes blue 2 no green 2 yes green 1 yes red 3 yes green 1 yes Think of a split on color. To calculate the upper bound on the tree for Option 1, calculate p.25 for each branch, which are respectively .206, .143, and .75. Then the average is: 1 1 Ave of the upper bounds for tree = (6 · .206 + 9 · .143 + 1 · .75) = 3.273 × 16 16 Let’s compare that to the error rate of Option 2, where we’d replace the tree with a leaf with 6+9+1 = 16 examplesPin it, where 15 are positive, and 1 is 1 negative. Calculate pα that solves α = z=0 Bin(z, 16, pα ), which is .157. The average is: 1 1 Ave of the upper bounds for leaf = 16 · .157 = 2.512 × . 16 16 Say we had to make the decision amongst only Options 1 and 2. Since 2.512 < 3.273, the upper bound on the error for Option 2 is lower, so we’ll prune the tree to a leaf. Look at the data - does it make sense to do this? 13 CART - Classification and Regression Trees (Breiman, Freedman, Olshen, Stone, 1984) Does only binary splits, not multiway splits (less interpretable, but simplifies splitting criteria). Let’s do classification first, and regression later. For splitting, CART uses the Gini index. The Gini index again is variance of Bin(n, p) = variance of Bernoulli(p). n For pruning, CART uses “minimal cost complexity.” p(1 − p) = Each subtree is assigned a cost. The first term in the cost is a misclassification error. The second term is a regularization term. If we choose C to be large, the tree that minimizes the cost will be sparser. If C is small, the tree that minimizes the cost will have better training accuracy. X X cost(subtree) = 1[yi 6=leaf’s class] + C [#leaves in subtree] . leaves j xi ∈leaf j We could create a sequence of nested subtrees by gradually increasing C. Draw a picture Now we need to choose C. Here’s one way to do this: • Step 1: For each C, hold out some data, split, then prune, producing a tree for each C. • Step 2: see which tree is the best on the holdout data, choose C. • Step 3: use all data, use chosen C, run split, then prune to produce the final tree. There are other ways to do this! You’ll use cross-validation in the homework. Review C4.5 and CART 14 CART’s Regression Trees Partitions and CART X2 X2 R5 R2 R3 t2 R1 t4 R4 t1 t3 X1 X1 (a) General partition that cannot be obtained from recursive binary splitting. (b) Partition of a two-dimensional feature space by recursive binary splitting, as used in CART, applied to some fake data. X1 < t1 X2 < t2 R1 R2 X1 < t3 R3 X2 < t4 X2 R4 R5 (c) Tree corresponding to the partition in the top right panel. X1 (d) A perspective plot of the prediction surface. Image by MIT OpenCourseWare, adapted from Hastie et al., The Elements of Statistical Learning, Springer, 2009. CART decides which attributes to split and where to split them. In each leaf, we’re going to assign f (x) to be a constant. Can you guess what value to assign? Consider the empirical error, using the least squares loss: X Rtrain (f ) = (yi − f (xi ))2 i 15 Break it up by leaves. Call the value of f (x) in leaf j by fj since it’s a constant. X X train R (f ) = (yi − f (xi ))2 = leaves j i∈leaf j X X leaves j i∈leaf j X 2 (yi − fj ) =: Rjtrain (fj ). leaves j To choose the value of the fj ’s so that they minimize Rjtrain , take the derivative, set it to 0. Let |Sj | be the number of examples in leaf j. 0 = d X (yi − f˜)2 ˜ df i∈leaf j f˜=fj ! = −2 X (yi − f˜) i fj f˜=fj = −2 X i yi ! − |Sj |f˜ f˜=fj 1 X = yi = ȳSj , |Sj | i∈leaf j where ȳSj is the sample average of the labels for leaf j’s examples. So now we know what value to assign for f in each leaf. How to split? Greedily want attribute A and split point s solving the following.   X X min (yi − C1 )2 + min (yi − C2 )2  . min C1 C2 A, s xi ∈{leaf|x(A) ≤s} xi ∈{leaf|x(A) >s} for each attribute A do a linesearch over s The first term means that we’ll choose the optimal C1 = ȳ{leaf|x(A) ≤s} . The second term means we’ll choose C2 = ȳ{leaf|x(A) >s} . For pruning, again CART does minimal cost complexity pruning: X X cost = (yi − ȳSj )2 + C[# leaves in tree] leaves j xi ∈Sj 16