Administration Questions Registration [Ask NOW] Hw0: Solution is out; make sure you understand it. Hw1 is out. Please start working on it as soon as possible; Discussion sessions will start next week; come ready with questions Projects Small (2-3) groups; your choice of a topic. 25% of the grade needs to be a substantial project Extra credit for undergrads Quiz 1: Avg. score: 4.51/5 Only 165 of you attempted it (???) Check out the solution. No Quiz in the coming week. DECISION TREES CS446 Spring17 1 What Did We Learn? Learning problem: Find a function that best separates the data What function?
Whats best? How to find it? Linear: x= data representation; w= the classifier Y = sgn {wT x} A possibility: Define the learning problem to be: Find a (linear) function that best separates the data DECISION TREES CS446 Spring17 2 Introduction - Summary We introduced the technical part of the class by giving two (very important) examples for learning approaches to linear discrimination. There are many other solutions. Question 1: Our solution learns a linear function; in principle, the target function may not be linear, and this will have implications on the performance of our learned hypothesis. Can we learn a function that is more flexible in terms of what it does with the feature space? Question 2: Can we say something about the quality of what we learn (sample complexity, time complexity; quality) DECISION TREES CS446 Spring17 3 Decision Trees Earlier, we decoupled the generation of the feature space from the learning. Argued that we can map the given examples into another
space, in which the target functions are linearly separable. Think about the Badges problem Do we always want to do it? How do we determine what are good mappings? Whats the best learning algorithm? The study of decision trees may shed some light on this. Learning is done directly from the given data representation. x2 The algorithm ``transforms the data itself. x DECISION TREES CS446 Spring17 4 This Lecture Decision trees for (binary) classification Non-linear classifiers Learning decision trees (ID3 algorithm) Greedy heuristic (based on information gain) Originally developed for discrete features Some extensions to the basic algorithm Overfitting
DECISION TREES Some experimental issues CS446 Spring17 5 Re p re se nt ati o n Representing Data Think about a large table, N attributes, and assume you want to know something about the people represented as entries in this table. E.g. own an expensive car or not; Simplest way: Histogram on the first attribute own Then, histogram on first and second (own & gender) But, what if the # of attributes is larger: N=16 How large are the 1-d histograms (contingency tables) ? 16 numbers How large are the 2-d histograms? 16-choose-2 = 120 numbers How many 3-d tables? 560 numbers With 100 attributes, the 3-d tables need 161,700 numbers DECISION TREES We need to figure out a way to represent data in a better way, and figure out what are the important attributes to look at first.
Information theory has something to say about it we will use it to better represent the data. CS446 Spring17 6 Decision Trees A hierarchical data structure that represents data by implementing a divide and conquer strategy Can be used as a non-parametric classification and regression method Given a collection of examples, learn a decision tree that represents it. Use this representation to classify new examples B A CS446 Spring17 7 C DECISION TREES The Representation De ci s io n Tr ee s
Decision Trees are classifiers for instances represented as A feature vectors (color=B; shape= ; label= ) Nodes are tests for feature values C There is one branch for each value of the feature Leaves specify(color= the category (labels) RED ;shape=triangle) Can categorize instances into multiple disjoint categories Color Evaluation of a Decision Tree Blue Shape triangle circle square B DECISION TREES C A CS446 Spring17 Learning a Decision Tree red B Green Shape
square B circle A 8 Expressivity of Decision Trees As Boolean functions they can represent any Boolean function. Can be rewritten as rules in Disjunctive Normal Form (DNF) The disjunction of these rules is equivalent to the Decision Tree What did we show? What is the hypothesis space here? 2 dimensions, 3 values each |X| = 9; |Y| = 2; |H| = 2X|X| = 9; |Y| = 2; |H| = 2 = 9; |X| = 9; |Y| = 2; |H| = 2Y|X| = 9; |Y| = 2; |H| = 2 = 2; |X| = 9; |Y| = 2; |H| = 2H|X| = 9; |Y| = 2; |H| = 2 = 29 Color De ci s io n Tr ee s Green^square positive Blue^circle positive Blue^square positive Blue Shape triangle
circle square - DECISION TREES red Green Shape + circle square + + + CS446 Spring17 9 Output is a discrete category. Real valued outputs are possible (regression trees) There are efficient algorithms for processing large amounts of data (but not too many features) There are methods for handling noisy data (classification noise and attribute noise) and for handling missing attribute values Color De ci s io n Tr ee
s Decision Trees Blue Shape triangle circle red + square DECISION TREES + + CS446 Spring17 Green Shape square + circle 10 Decision Boundaries De ci s io n Tr ee
s Usually, instances are represented as attribute-value pairs (color=blue, shape = square, +) Numerical values can be used either by discretizing or by using thresholds for splitting nodes In this case, the tree divides the features space into axis-parallel rectangles, each labeled with one of the labels X<3 Y + + + 7 + + - + Y>7 no - 5 DECISION TREES 1 -
- 3 X CS446 Spring17 no yes yes + Y<5 yes no + + - X<1 11 - Decision Trees Can represent any Boolean Function Can be viewed as a way to compactly represent a lot of data. Natural representation: (20 questions) The evaluation of the Decision Tree Classifier is easy Clearly, given data, there are many ways to represent it as a decision tree.
Learning a good representation from data is the challenge. DECISION TREES CS446 Spring17 Outlook Sunny Overcast Rain Humidity Yes Wind High Normal Yes No StrongWeak Yes No 12 Will I play tennis today? Features Outlook: Temperature: Humidity: Wind: {Sun, Overcast, Rain} {Hot, Mild, Cool} {High, Normal, Low} {Strong, Weak} Labels
DECISION TREES Binary classification task: Y = {+, -} CS446 Spring17 13 Will I play tennis today? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 O S S O R R R O S S R S O O
R T H H H M C C C M C M M M H M H H H H H N N N H N N N H N H DECISION TREES W W S
W W W S S W W W S S W S Play? + + + + + + + + + - Outlook: S(unny), O(vercast), R(ainy) Temperature: H(ot), M(edium), C(ool) Humidity: H(igh), N(ormal), L(ow)
Wind: S(trong), W(eak) CS446 Spring17 14 Administration Registration [Ask NOW] Hw1 is out. Due on Friday. Questions You should be working on it already. You have noticed that the goal of the Hw is to teach you something. Discussion sessions will start next week; come ready with questions. Projects Small (2-3) groups; your choice of a topic. Anything with a significant Machine Learning component works. More details will come. 25% of the grade needs to be a substantial project Extra credit for undergrads Quiz 2: will be made available over the weekend. Check the website for office hours, discussion sessions etc. DECISION TREES CS446 Spring17
15 Basic Decision Trees Learning Algorithm Data is processed in Batch (i.e. all the data available) Recursively build a decision tree top down. DECISION TREES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 O T H W Play? S H H W S H H S O H H W + R M H W + R C N W + R C N S O C N S
+ S M H W S C N W + R M N W + S M N S + O M H S + O H N W + R CS446 M HSpring17 S - Algorithm? Outlook Sunny Overcast Rain Humidity Yes High Normal Yes No Wind StrongWeak Yes No 16 Basic Decision Tree Algorithm Let S be the set of Examples Label is the target attribute (the prediction)
Attributes is the set of measured attributes ID 3 ID3(S, Attributes, Label) If all examples are labeled the same return a single node tree with Label Otherwise Begin A = attribute in Attributes that best classifies S (Create a Root node for tree) for each possible value v of A Add a new tree branch corresponding to A=v Let Sv be the subset of examples in S with A=v if Sv is empty: add leaf node with the common value of Label in S why? Else: below this branch add the subtree For evaluation time ID3(Sv, Attributes - {a}, Label) End Return Root DECISION TREES CS446 Spring17 17 Picking the Root Attribute The goal is to have the resulting decision tree as small as possible (Occams Razor) But, finding the minimal decision tree consistent with the data is NP-hard The recursive algorithm is a greedy heuristic search for a simple tree, but cannot guarantee optimality. The main decision in the algorithm is the selection of the next attribute to condition on.
DECISION TREES CS446 Spring17 18 Picking the Root Attribute Consider data with two Boolean attributes (A,B). < (A=0,B=0), - >: 50 examples < (A=0,B=1), - >: 50 examples < (A=1,B=0), - >: 0 examples < (A=1,B=1), + >: 100 examples What should be the first attribute we select? 1 A Splitting on A: we get purely labeled nodes. 1 B 1 A + 0 - DECISION TREES 0 + - 0 Splitting on B: we dont get purely labeled nodes. What if we have: <(A=1,B=0), - >: 3 examples CS446 Spring17 19
Picking the Root Attribute Consider data with two Boolean attributes (A,B). < (A=0,B=0), - >: 50 examples < (A=0,B=1), - >: 50 examples < (A=1,B=0), - >: 0 examples 3 examples < (A=1,B=1), + >: 100 examples Trees looks structurally similar; which attribute should we choose? 1 B 1 A 0 + 100 50 DECISION TREES 1 A 0 53 1 B Advantage A. But Need a way to quantify things CS446 Spring17 + 100 0 0 100 3 20
Picking the Root Attribute The goal is to have the resulting decision tree as small as possible (Occams Razor) The main decision in the algorithm is the selection of the next attribute to condition on. We want attributes that split the examples to sets that are relatively pure in one label; this way we are closer to a leaf node. The most popular heuristics is based on information gain, originated with the ID3 system of Quinlan. DECISION TREES CS446 Spring17 21 Entropy Entropy (impurity, disorder) of a set of examples, S, relative to a binary classification is: Entropy(S) p log(p ) p log(p ) where P+ is the proportion of positive examples in S and P- is the proportion of negatives. If all the examples belong to the same category: Entropy = 0 If all the examples are equally mixed (0.5, 0.5): Entropy = 1 Entropy = Level of uncertainty. In general, when pi is the fraction of examples labeled i: Entropy({p 1 , p 2 ,...pk }) k p log(p i i
) i 1 Entropy can be viewed as the number of bits required, on average, to encode the class of labels. If the probability for + is 0.5, a single bit is required for each example; if it is 0.8 -- can use less then 1 bit. DECISION TREES CS446 Spring17 22 Entropy Entropy (impurity, disorder) of a set of examples, S, relative to a binary classification is: Entropy(S) p log(p ) p log(p ) where P+ is the proportion of positive examples in S and P- is the proportion of negatives. If all the examples belong to the same category: Entropy = 0 If all the examples are equally mixed (0.5, 0.5): Entropy = 1 Entropy = Level of uncertainty. 1 1 -DECISION TREES +
1 -CS446 Spring17 + -- + 23 High Entropy High level of Uncertainty Entropy Low Entropy No Uncertainty. Entropy (impurity, disorder) of a set of examples, S, relative to a binary classification is: Entropy(S) p log(p ) p log(p ) where p is the proportion of positive examples in S and p is the proportion of negatives. If all the examples belong to the same category: Entropy = 0 If all the examples are equally mixed (0.5, 0.5): Entropy = 1 1 DECISION TREES 1 CS446 Spring17 1 24
High Entropy High level of Uncertainty Low Entropy No Uncertainty. Information Gain Outlook Sunny Overcast Rain The information gain of an attribute a is the expected reduction in entropy caused by partitioning on this attribute | Sv | Gain(S, a) Entropy(S) Entropy(S v ) vvalues(a) | S | where Sv is the subset of S for which attribute a has value v, and the entropy of partitioning the data is calculated by weighing the entropy of each partition by its size relative to the original set Partitions of low entropy (imbalanced splits) lead to high gain Go back to check which of the A, B splits is better DECISION TREES CS446 Spring17 25 Will I play tennis today? 1 2 3
4 5 6 7 8 9 10 11 12 13 14 O S S O R R R O S S R S O O R T H H H M C C C M C M
M M H M H H H H H N N N H N N N H N H DECISION TREES W W S W W W S S W W W S S W S
Play? + + + + + + + + + - Outlook: S(unny), O(vercast), R(ainy) Temperature: H(ot), M(edium), C(ool) Humidity: H(igh), N(ormal), L(ow) Wind: S(trong), W(eak) CS446 Spring17 26 Will I play tennis today? 1 2
3 4 5 6 7 8 9 10 11 12 13 14 O S S O R R R O S S R S O O R T H H H M C C C M C
M M M H M H H H H H N N N H N N N H N H DECISION TREES W W S W W W S S W W W S S W S
Play? + + + + + + + + + - Current entropy: p = 9/14 n = 5/14 H(Y) = (9/14) log2(9/14) log2(5/14) 0.94 CS446 Spring17 (5/14) 27 Information Gain: Outlook 1 2 3 4 5 6 7 8 9 10 11
12 13 14 O S S O R R R O S S R S O O R T H H H M C C C M C M M M H M H H H
H H N N N H N N N H N H DECISION TREES W W S W W W S S W W W S S W S Play? + + + + + + +
+ + - Outlook = sunny: p = 2/5 n = 3/5 HS = 0.971 Outlook = overcast: p = 4/4 n = 0 Ho= 0 Outlook = rainy: p = 3/5 n = 2/5 HR = 0.971 Expected entropy: (5/14)0.971 + (4/14)0 + (5/14)0.971 = 0.694 Information gain: 0.940 0.694 = 0.246 CS446 Spring17 28 Information Gain: Humidity 1 2 3 4 5 6 7 8 9 10 11 12 13 14 O S S
O R R R O S S R S O O R T H H H M C C C M C M M M H M H H H H H N N N H N
N N H N H DECISION TREES W W S W W W S S W W W S S W S Play? + + + + + + + + + - Humidity = high: p = 3/7 n = 4/7 Hh = 0.985 Humidity = Normal:
p = 6/7 n = 1/7 Ho= 0.592 Expected entropy: (7/14)0.985 + (7/14)0.592= 0.7785 Information gain: 0.940 0.151 = 0.1515 CS446 Spring17 29 Which feature to split on? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 O S S O R R R O S S R S
O O R T H H H M C C C M C M M M H M H H H H H N N N H N N N H N H DECISION TREES W
W S W W W S S W W W S S W S Play? + + + + + + + + + - Information gain: Outlook: 0.246 Humidity: 0.151 Wind: 0.048 Temperature: 0.029 Split on Outlook CS446 Spring17 30 An Illustrative Example (III)
Gain(S,Humidity)=0.151 Gain(S,Wind) = 0.048 Gain(S,Temperature) = 0.029 Gain(S,Outlook) = 0.246 Outlook DECISION TREES CS446 Spring17 31 An Illustrative Example (III) Outlook Sunny 1,2,8,9,11 2+,3? DECISION TREES Overcast 3,7,12,13 4+,0Yes Rain 4,5,6,10,14 3+,2? CS446 Spring17 1 2 3 4 5 6 7
8 9 10 11 12 13 14 O S S O R R R O S S R S O O R T H H H M C C C M C M M M H M
H H H H H N N N H N N N H N H W W S W W W S S W W W S S W S Play? + + + + +
+ + + + - 32 An Illustrative Example (III) Outlook Sunny 1,2,8,9,11 2+,3? Overcast 3,7,12,13 4+,0Yes Rain 4,5,6,10,14 3+,2? Continue until: Every attribute is included in path, or, All examples in the leaf have same label DECISION TREES CS446 Spring17 1 2 3 4 5 6 7 8
9 10 11 12 13 14 O S S O R R R O S S R S O O R T H H H M C C C M C M M M H M
H H H H H N N N H N N N H N H W W S W W W S S W W W S S W S Play? + + + + + +
+ + + - 33 An Illustrative Example (IV) Gain(S sunny , Humidity) .97-(3/5) 0-(2/5) 0 = .97 Gain(S sunny , Temp) .97- 0-(2/5) 1 = .57 Outlook Gain(S sunny , Wind) .97-(2/5) 1 - (3/5) .92= .02 Sunny Overcast Rain 1,2,8,9,11 2+,3? 3,7,12,13 4+,0Yes 4,5,6,10,14 3+,2? Day 1 2 8 9 11 DECISION TREES Outlook Temperature Humidity Wind
Sunny Hot High Weak Sunny Hot High Strong Sunny Mild High Weak Sunny Cool Normal Weak Sunny Mild Normal Strong CS446 Spring17 PlayTennis No No No Yes Yes 34 An Illustrative Example (V) Outlook DECISION TREES Sunny Overcast Rain
1,2,8,9,11 2+,3? 3,7,12,13 4+,0Yes 4,5,6,10,14 3+,2? CS446 Spring17 35 An Illustrative Example (V) Outlook Sunny Overcast Rain 1,2,8,9,11 2+,3Humidity 3,7,12,13 4+,0Yes 4,5,6,10,14 3+,2? High No DECISION TREES Normal Yes
CS446 Spring17 36 induceDecisionTree(S) 1. Does S uniquely define a class? if all s S have the same label y: S have the same label y: return S; 2. Find the feature with the most information gain: i = argmax i Gain(S, Xi) 3. Add children to S: for k in Values(Xi): Sk = {s S have the same label y: S |X| = 9; |Y| = 2; |H| = 2 xi = k} addChild(S, Sk) induceDecisionTree(Sk) return S; DECISION TREES CS446 Spring17 37 An Illustrative Example (VI) Outlook Sunny Overcast Rain 1,2,8,9,11 2+,3Humidity 3,7,12,13 4+,0Yes 4,5,6,10,14 3+,2Wind
High No DECISION TREES Normal Yes CS446 Spring17 Strong No Weak Yes 38 Hypothesis Space in Decision Tree Induction Conduct a search of the space of decision trees which can represent all possible discrete functions. (pros and cons) Goal: to find the best decision tree Best could be smallest depth Best could be minimizing the expected number of tests Finding a minimal decision tree consistent with a set of data is NP-hard. Performs a greedy heuristic search: hill climbing without backtracking Makes statistically based decisions using all data DECISION TREES CS446 Spring17
39 Todays key concepts Learning decision trees (ID3 algorithm) Greedy heuristic (based on information gain) Originally developed for discrete features Overfitting What is it? How do we deal with it? How can this be avoided with linear classifiers? Some extensions of DTs Principles of Experimental ML DECISION TREES CS446 Spring17 40 History of Decision Tree Research Hunt and colleagues in Psychology used full search decision tree methods to model human concept learning in the 60s Quinlan developed ID3, with the information gain heuristics in the late 70s to learn expert systems from examples Breiman, Freidman and colleagues in statistics developed CART (classification and regression trees simultaneously) A variety of improvements in the 80s: coping with noise, continuous attributes, missing data, non-axis parallel etc. Quinlans updated algorithm, C4.5 (1993) is commonly used (New: C5) Boosting (or Bagging) over DTs is a very good general purpose algorithm DECISION TREES CS446 Spring17
41 Example Outlook = Sunny, Temp = Hot, Humidity = Normal, Wind = Strong, NO Outlook Sunny 1,2,8,9,11 2+,3Humidity High No DECISION TREES Rain Overcast 3,7,12,13 4+,0Yes Normal Yes 4,5,6,10,14 3+,2Wind Strong No CS446 Spring17 Weak Yes 42 Overfitting - Example Outlook = Sunny, Temp = Hot, Humidity = Normal, Wind = Strong, NO Outlook
Sunny 1,2,8,9,11 2+,3Humidity High No 3,7,12,13 4+,0Yes Weak Yes Rain 4,5,6,10,14 3+,2Wind Strong No Normal Wind Strong No DECISION TREES Overcast Weak Yes This can always be done may fit noise or other coincidental regularities CS446 Spring17 43 Our training data
DECISION TREES CS446 Spring17 44 The instance space DECISION TREES CS446 Spring17 45 Overfitting the Data Learning a tree that classifies the training data perfectly may not lead to the tree with the best generalization performance. There may be noise in the training data the tree is fitting The algorithm might be making decisions based on very little data A hypothesis h is said to overfit the training data if there is another hypothesis h, such that h has a smaller error than h on the training data but h has larger error on the test data than h. On training accuracy On testing Complexity of tree DECISION TREES CS446 Spring17 46
Reasons for overfitting Too much variance in the training data Training data is not a representative sample of the instance space We split on features that are actually irrelevant Too much noise in the training data Noise = some feature values or class labels are incorrect We learn to predict the noise In both cases, it is a result of our will to minimize the empirical error when we learn, and the ability to do it (with DTs) DECISION TREES CS446 Spring17 47 Pruning a decision tree Prune = remove leaves and assign majority label of the parent to all items Prune the children of S if: DECISION TREES all children are leaves, and the accuracy on the validation set does not decrease if we assign the most frequent class label to all items at S.
CS446 Spring17 48 Avoiding Overfitting Two basic approaches How can this be avoided with linear classifiers? Pre-pruning: Stop growing the tree at some point during construction when it is determined that there is not enough data to make reliable choices. Post-pruning: Grow the full tree and then remove nodes that seem not to have sufficient evidence. Methods for evaluating subtrees to prune Cross-validation: Reserve hold-out set to evaluate utility Statistical testing: Test if the observed regularity can be dismissed as likely to occur by chance Minimum Description Length: Is the additional complexity of the hypothesis smaller than remembering the exceptions? This is related to the notion of regularization that we will see in other contexts keep the hypothesis simple. Hand waving, for now. Next: a brief detour into explaining generalization and overfitting DECISION TREES CS446 Spring17 49
The i.i.d. assumption Training and test items are independently and identically distributed (i.i.d.): There is a distribution P(X, Y) from which the data D = {(x, y)} is generated. Sometimes its useful to rewrite P(X, Y) as P(X)P(Y|X| = 9; |Y| = 2; |H| = 2X) Usually P(X, Y) is unknown to us (we just know it exists) DECISION TREES Training and test data are samples drawn from the same P(X, Y): they are identically distributed Each (x, y) is drawn independently from P(X, Y) CS446 Spring17 53 Overfitting On training data Accuracy Why this shape of curves? On test data Size of tree A decision tree overfits the training data when its accuracy on the training data goes up but its accuracy on unseen data goes down
DECISION TREES CS446 Spring17 54 Overfitting Empirical Error ?? Model complexity Empirical error (= on a given data set): The percentage of items in this data set are misclassified by the classifier f. DECISION TREES CS446 Spring17 55 Overfitting Empirical Error Model complexity Model complexity (informally): How many parameters do we have to learn? Decision trees: complexity = #nodes DECISION TREES CS446 Spring17 56 Overfitting
Expected Error Model complexity Expected error: What percentage of items drawn from P(x,y) do we expect to be misclassified by f? (Thats what we really care about generalization) DECISION TREES CS446 Spring17 57 Variance of a learner (informally) Variance Model complexity How susceptible is the learner to minor changes in the training data? (i.e. to different samples from P(X, Y)) Variance increases with model complexity Think about extreme cases: a hypothesis space with one function vs. all functions. The larger the hypothesis space is, the more flexible the selection of the chosen hypothesis is as a function of the data. More accurately: for each data set D, you will learn a different hypothesis h(D), that will have a different true error e(h); we are looking here at the variance of this random variable. DECISION TREES CS446 Spring17
58 Bias of a learner (informally) Bias Model complexity How likely is the learner to identify the target hypothesis? Bias is low when the model is expressive (low empirical error) Bias is high when the model is (too) simple The larger the hypothesis space is, the easiest it is to be close to the true hypothesis. More accurately: for each data set D, you learn a different hypothesis h(D), that has a different true error e(h); we are looking here at the difference of the mean of this random variable from the true error. DECISION TREES CS446 Spring17 59 Impact of bias and variance Expected Error Variance Bias Model complexity Expected error bias + variance DECISION TREES CS446 Spring17
60 Model complexity Expected Error Variance Bias Model complexity Simple models: High bias and low variance DECISION TREES Complex models: High variance and low bias CS446 Spring17 61 Underfitting and Overfitting Underfitting Overfitting Expected Error Variance Bias Model complexity Simple models: High bias and low variance Complex models: High variance and low bias
This can be made more accurate for some loss functions. We will develop a more precise and general theory that trades expressivity of models with empirical error DECISION TREES CS446 Spring17 62 Avoiding Overfitting Two basic approaches How can this be avoided with linear classifiers? Pre-pruning: Stop growing the tree at some point during construction when it is determined that there is not enough data to make reliable choices. Post-pruning: Grow the full tree and then remove nodes that seem not to have sufficient evidence. Methods for evaluating subtrees to prune Cross-validation: Reserve hold-out set to evaluate utility Statistical testing: Test if the observed regularity can be dismissed as likely to occur by chance Minimum Description Length: Is the additional complexity of the hypothesis smaller than remembering the exceptions? This is related to the notion of regularization that we will see in other contexts keep the hypothesis simple. Hand waving, for now. Next: a brief detour into explaining generalization and overfitting
DECISION TREES CS446 Spring17 63 Trees and Rules Decision Trees can be represented as Rules (outlook = sunny) and (humidity = normal) then YES (outlook = rain) and (wind = strong) then NO Sometimes Pruning can be done at the rules level Sunny 1,2,8,9,11 2+,3Humidity DECISION TREES Outlook Rules are generalized by erasing a condition (different!) Overcast 3,7,12,13 4+,0Yes High Normal Yes No CS446 Spring17 Rain
4,5,6,10,14 3+,2Wind Strong No Weak Yes 64 Real-valued attributes can, in advance, be discretized into ranges, such as big, medium, small Alternatively, one can develop splitting nodes based on thresholds of the form A
Check the mid-point as a possible threshold, i.e. Sa x, Sa y DECISION TREES CS446 Spring17 65 Continuous Attributes Example: How to find the split with the highest gain ? Ad d iti o na l Is su es I Length (L): 10 15 21 28 32 40 50 Class: - + + - + + Check thresholds: L < 12.5; L < 24.5; L < 45
Subset of Examples= {}, Split= k+,j- For each continuous feature A: Sort examples according to the value of A For each ordered pair (x,y) with different labels Check the mid-point as a possible threshold. I.e, Sa x, Sa y DECISION TREES CS446 Spring17 66 Missing Values Diagnosis = < fever, blood_pressure,, blood_test=?,> Training: evaluate Gain(S,a) where in some of the examples a value for a is not given Ad d iti o na l Is su es I I
Many times values are not available for all attributes during training or testing (e.g., medical diagnosis) DECISION TREES CS446 Spring17 67 Gain(S, a) Ent(S) Missing Values Outlook Sunny Overcast | Sv | | S | Ent(S v ) Gain(S sunny ,Temp) .97- 0-(2/5) 1 = .57 Gain(S sunny , Humidity) Rain 1,2,8,9,11 3,7,12,13 4,5,6,10,14 2+,34+,03+,2? Yes ? Fill in: assign the most likely value of Xi to s: argmax k P( Xi = k ): Normal 97-(3/5) Ent[+0,-3] -(2/5) Ent[+2,-0] = .97 Assign fractional counts P(Xi =k) for each value of Xi to s .97-(2.5/5) Ent[+0,-2.5] - (2.5/5) Ent[+2,-.5] < .97 Other suggestions?
Day Outlook Temperature Humidity Wind PlayTennis 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 8 Sunny Mild ??? Weak No 9 Sunny Cool Normal Weak Yes 11 Sunny Mild Normal Strong Yes 68 DECISION TREES CS446 Spring17 Missing Values Diagnosis = < fever, blood_pressure,, blood_test=?,> Training: evaluate Gain(S,a) where in some of the examples a value for a is not given
Testing: classify an example without knowing the value of a Ad d iti o na l Is su es I I Many times values are not available for all attributes during training or testing (e.g., medical diagnosis) DECISION TREES CS446 Spring17 69 Missing Values Outlook = Sunny, Temp = Hot, Humidity = ???, Wind = Strong, label = ?? Normal/High Outlook = ???, Temp = Hot, Humidity = Normal, Wind = Strong, label = ?? Outlook Sunny Overcast Rain 1,2,8,9,11
2+,3Humidity 3,7,12,13 4+,0Yes 4,5,6,10,14 3+,2Wind High No DECISION TREES 1/3 Yes + 1/3 Yes +1/3 No = Yes Normal Yes CS446 Spring17 Strong No Other suggestions? Weak Yes 70 Other Issues Attributes with different costs Change information gain so that low cost attribute are preferred Dealing with features with different # of values Alternative measures for selecting attributes Ot h
er I ss u es Oblique Decision Trees Decisions are not axis-parallel Incremental Decision Trees induction DECISION TREES When different attributes have different number of values information gain tends to prefer those with many values Update an existing decision tree to account for new examples incrementally (Maintain consistency?) CS446 Spring17 71 Fe at u re s Decision Trees as Features
Rather than using decision trees to represent the target function it is becoming common to use small decision trees as features When learning over a large number of features, learning decision trees is difficult and the resulting tree may be very large (over fitting) Instead, learn small decision trees, with limited depth. Treat them as experts; they are correct, but only on a small region in the domain. (what DTs to learn? same every time?) Then, learn another function, typically a linear function, over these as features. Boosting (but also other linear learners) are used on top of the small decision trees. (Either Boolean, or real valued features) DECISION TREES CS446 Spring17 72 Experimental Machine Learning Machine Learning is an Experimental Field and we will spend some time (in Problem sets) learning how to run experiments and evaluate results First hint: be organized; write scripts Basics: Split your data into two (or three) sets: Training data (often 70-90%) Test data (often 10-20%) Development data (10-20%) You need to report performance on test data, but you are not allowed to look at it.
DECISION TREES You are allowed to look at the development data (and use it to tweak parameters) CS446 Spring17 73 N-fold cross validation Instead of a single test-training split: test train Split data into N equal-sized parts Train and test N different classifiers Report average accuracy and standard deviation of the accuracy DECISION TREES CS446 Spring17 74 Evaluation: significance tests You have two different classifiers, A and B You train and test them on the same data set using Nfold cross-validation For the n-th fold: accuracy(A, n), accuracy(B, n) pn = accuracy(A, n) - accuracy(B, n) Is the difference between A and Bs accuracies significant? DECISION TREES CS446 Spring17 75
Hypothesis testing You want to show that hypothesis H is true, based on your data (e.g. H = classifier A and B are different) Define a null hypothesis H0 (H0 is the contrary of what you want to show) H0 defines a distribution P(m |H0) over some statistic e.g. a distribution over the difference in accuracy between A and B Can you refute (reject) H0? DECISION TREES CS446 Spring17 76 Rejecting H0 H0 defines a distribution P(M |H0) over some statistic M (e.g. M= the difference in accuracy between A and B) Select a significance value S (e.g. 0.05, 0.01, etc.) You can only reject H0 if P(m |H0) S
Compute the test statistic m from your data e.g. the average difference in accuracy over your N folds Compute P(m |H0) Refute H0 with p S if P(m |H0) S DECISION TREES CS446 Spring17 77 Paired t-test Null hypothesis (H0; to be refuted): There is no difference between A and B, i.e. the expected accuracies of A and B are the same That is, the expected difference (over all possible data sets) between their accuracies is 0: H0: E[pD] = 0 We dont know the true E[pD] N-fold cross-validation gives us N samples of pD DECISION TREES CS446 Spring17 78 Paired t-test Null hypothesis H0: E[diffD] = = 0 m: our estimate of based on N samples of diffD m = 1/N n diffn The estimated variance S2: S2 = 1/(N-1) 1,N (diffn m)2
Accept Null hypothesis at significance level a if the following statistic lies in (-ta/2, N-1, +ta/2, N-1) Nm ~ tN 1 S DECISION TREES CS446 Spring17 79 Decision Trees - Summary Hypothesis Space: Variable size (contains all functions) Deterministic; Discrete and Continuous attributes Search Algorithm ID3 - batch Extensions: missing values Issues: What is the goal? When to stop? How to guarantee good generalization? Did not address: DECISION TREES
How are we doing? (Correctness-wise, Complexity-wise) CS446 Spring17 80