1 Tree Learning A story on uncertainty in machine learning Based also on the book by Peter Flach, University of Bristol and Ray Mooney, University of Texas, Lecture 2 Machine learning settings 3 Machine learning settings •  Logical approach - Decision and regression trees, rules •  Probabilistic methods – Bayesian methods •  Linear methods – Linear discriminant, SVM, perceptron, logistic regression •  Distance-based methods – Lazy Learning (kNN), clustering 4 Machine learning settings •  Logical approach - Decision and regression trees, rules •  Probabilistic methods – Bayesian methods •  Linear methods – Linear discriminant, SVM, perceptron, logistic regression •  Distance-based methods – Lazy Learning (kNN), clustering 5 Learning Trees •  Supervised method – data classified into classes, i.e. data contains a target attribute •  Classifier is a tree that represents a hypotheses in a disjunctive normal form •  Finite number of classes >= 2 (for a decision tree), continuous (for regression trees) •  Finding a minimal decision tree (nodes, leaves, or depth) is an NP-hard optimization problem. Heuristic algorithm can be used to build a tree •  Want to pick a feature that creates subsets of examples that are relatively “pure” in a single class so they are “closer” to being leaf nodes. 6 Tree Induction Pseudocode DTree(examples, features) returns a tree If all examples are in one category, return a leaf node with that category label. Else if the set of features is empty, return a leaf node with the category label that is the most common in examples. Else pick a feature F and create a node R for it For each possible value vi of F: Let examplesi be the subset of examples that have value vi for F Add an out-going edge E to node R labeled with the value vi. If examplesi is empty then attach a leaf node to edge E labeled with the category that is the most common in examples. else call DTree(examplesi , features – {F}) and attach the resulting tree as the subtree under edge E. Return the subtree rooted at R. 7 Tree Induction Pseudocode DTree(examples, features) returns a tree If all examples are in one category, return a leaf node with that category label. Else if the set of features is empty, return a leaf node with the category label that is the most common in examples. Else pick a feature F and create a node R for it For each possible value vi of F: Let examplesi be the subset of examples that have value vi for F Add an out-going edge E to node R labeled with the value vi. If examplesi is empty then attach a leaf node to edge E labeled with the category that is the most common in examples. else call DTree(examplesi , features – {F}) and attach the resulting tree as the subtree under edge E. Return the subtree rooted at R. 8 Tree Induction Pseudocode DTree(examples, features) returns a tree If all examples are in one category, return a leaf node with that category label. Else if the set of features is empty, return a leaf node with the category label that is the most common in examples. Else pick/construct a feature F and create a node R for it For each possible value vi of F: Let examplesi be the subset of examples that have value vi for F Add an out-going edge E to node R labeled with the value vi. If examplesi is empty then attach a leaf node to edge E labeled with the category that is the most common in examples. else call DTree(examplesi , features – {F}) and attach the resulting tree as the subtree under edge E. Return the subtree rooted at R. 9 Tree Induction Pseudocode DTree(examples, features) returns a tree If all examples are in one category, return a leaf node with that category label. Else if the set of features is empty, return a leaf node with the category label that is the most common in examples. Else pick/construct a feature F and create a node R for it For each possible value vi of F: Let examplesi be the subset of examples that have value vi for F Add an out-going edge E to node R labeled with the value vi. If examplesi is empty then attach a leaf node to edge E labeled with the category that is the most common in examples. else call DTree(examplesi , features – {F}) and attach the resulting tree as the subtree under edge E. Return the subtree rooted at R. 10 Tree Induction Pseudocode DTree(examples, features) returns a tree If all examples are in one category, return a leaf node with that category label. Else if the set of features is empty, return a leaf node with the category label that is the most common in examples. Else pick/construct a feature F and create a node R for it For each possible value vi of F: Let examplesi be the subset of examples that have value vi for F Add an out-going edge E to node R labeled with the value vi. OR add a label vi. to an existing edge If examplesi is empty then attach a leaf node to edge E labeled with the category that is the most common in examples (mode or mean). else call DTree(examplesi , features – {F}) and attach the resulting tree as the subtree under edge E. Return the subtree rooted at R. 11 Decision Tree Induction 12 Impurity. Picking a Good Split Feature Impurity for classes D1, …, Dl 13 Entropy •  Entropy (disorder, impurity) of a set of examples, S, relative to a binary classification is: where p1 is the fraction of positive examples in S and p0 is the fraction of negatives. •  If all examples are in one category, entropy is zero (we define 0⋅log(0)=0) •  If examples are equally mixed (p1=p0=0.5), entropy is a maximum of 1. •  Entropy can be viewed as the number of bits required on average to encode the class of an example in S where data compression (e.g. Huffman coding) is used to give shorter codes to more likely cases. •  For multi-class problems with c categories, entropy generalizes to: •  Information Gain )(log)(log)( 020121 ppppSEntropy −−= ∑= −= c i ii ppSEntropy 1 2 )(log)( € Gain(S,F) = Entropy(S) − Sv Sv∈Values(F ) ∑ Entropy(Sv ) 14 Hypothesis Space Search •  Performs batch learning that processes all training instances at once rather than incremental learning that updates a hypothesis after each example. •  Performs hill-climbing (greedy search) that may only find a locally-optimal solution. Guaranteed to find a tree consistent with any conflict-free training set (i.e. identical feature vectors always assigned the same class), but not necessarily the simplest tree. •  Finds a single discrete hypothesis, so there is no way to provide confidences or create useful queries. 15 Continuous features Use binary split of the current interval using the same impurity measure as for discrete attributes 16 Missing feature values •  Remove the instance •  Replace with the most common (mode, mean) value •  Replace with the most common (mode, mean) value w.r.t. a class •  Decision trees: use weighted Impurity measure (add relative increment to each atribute value 17 Bias in Decision-Tree Induction •  Information-gain gives a bias for trees with minimal depth. •  Implements a search (preference) bias instead of a language (restriction) bias. 18 History of Decision-Tree Research •  Hunt and colleagues use exhaustive search decision-tree methods (CLS) to model human concept learning in the 1960’s. •  In the late 70’s, Quinlan developed ID3 with the information gain heuristic to learn expert systems from examples. •  Simulataneously, Breiman and Friedman and colleagues develop CART (Classification and Regression Trees), similar to ID3. •  In the 1980’s a variety of improvements are introduced to handle noise, continuous features, missing features, and improved splitting criteria. Various expert-system development tools results. •  Quinlan’s updated decision-tree package (C4.5) released in 1993. •  Weka includes Java version of C4.5 called J48. 19 Computational Complexity •  Worst case builds a complete tree where every path test every feature. Assume n examples and m features. •  At each level, i, in the tree, must examine the remaining mi features for each instance at the level to calculate info gains. •  However, learned tree is rarely complete (number of leaves is ≤ n). In practice, complexity is linear in both number of features (m) and number of training examples (n). F1 Fm ⋅⋅⋅⋅⋅ Maximum of n examples spread across all nodes at each of the m levels )( 1 2 ∑= =⋅ m i nmOni 20 Overfitting Noise in Decision Trees •  Category or feature noise can easily cause overfitting. –  Add noisy instance : pos (but really neg) shape circle square triangle color red bluegreen pos neg pos neg neg 21 Overfitting Noise in Decision Trees •  Category or feature noise can easily cause overfitting. –  Add noisy instance : pos (but really neg) shape circle square triangle color red bluegreen pos neg pos neg : : + small med big posneg neg •  Noise can also cause different instances of the same feature vector to have different classes. Impossible to fit this data and must label leaf with the majority class. –  : neg (but really pos) •  Conflicting examples can also arise if the features are incomplete and inadequate to determine the class or if the target concept is non-deterministic. 22 Overfitting Prevention (Pruning) Methods •  Two basic approaches for decision trees –  Prepruning: Stop growing tree as some point during top-down construction when there is no longer sufficient data to make reliable decisions. –  Postpruning: Grow the full tree, then remove subtrees that do not have sufficient evidence. •  Label leaf resulting from pruning with the majority class of the remaining data, or a class probability distribution. •  Method for determining which subtrees to prune: –  Cross-validation: Reserve some training data as a hold-out set (validation set, tuning set) to evaluate utility of subtrees. –  Statistical test: Use a statistical test on the training data to determine if any observed regularity can be dismisses as likely due to random chance. –  Minimum description length (MDL): Determine if the additional complexity of the hypothesis is less complex than just explicitly remembering any exceptions resulting from pruning. 23 Reduced Error Pruning •  A post-pruning, cross-validation approach. Partition training data in “grow” and “validation” sets. Build a complete tree from the “grow” data. Until accuracy on validation set decreases do: For each non-leaf node, n, in the tree do: Temporarily prune the subtree below n and replace it with a leaf labeled with the current majority class at that node. Measure and record the accuracy of the pruned tree on the validation set. Permanently prune the node that results in the greatest increase in accuracy on the validation set. 24 Issues with Reduced Error Pruning •  The problem with this approach is that it potentially “wastes” training data on the validation set. •  Severity of this problem depends where we are on the learning curve: testaccuracy number of training examples 25 Cross-Validating without Losing Training Data •  If the algorithm is modified to grow trees breadthfirst rather than depth-first, we can stop growing after reaching any specified tree complexity. •  First, run several trials of reduced error-pruning using different random splits of grow and validation sets. •  Record the complexity of the pruned tree learned in each trial. Let C be the average pruned-tree complexity. •  Grow a final tree breadth-first from all the training data but stop when the complexity reaches C. •  Similar cross-validation approach can be used to set arbitrary algorithm parameters in general. 26 Additional Decision Tree Issues •  Features with costs •  Misclassification costs •  Incremental learning •  Mining large databases that do not fit in main memory 27 C4.5 •  Based on ID3 algorithm, author Ross Quinlan •  In all (or most of) non-commercial and commercial data mining tools •  Weka: C4.5 ver.8 -> j48 Scheme of C4.5 algorithm: Run several time and choose the best tree Inner:Take L% of learning data randomly Call ID3 (pre-pruning, see –m parameter) Prune the tree (post-pruning, -cf) Take T% of unseen learning data for validation If validation criterion holds, exit Otherwise add L.increment to L and go to Inner