1©2005-2007 Carlos Guestrin1Decision TreesMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityFebruary 5th, 2007©2005-2007 Carlos Guestrin2Linear separability A dataset is linearly separable iff ∃ a separating hyperplane: ∃ w, such that: w0+ ∑iwixi> 0; if x={x1,…,xn} is a positive example w0+ ∑iwixi< 0; if x={x1,…,xn} is a negative example2©2005-2007 Carlos Guestrin3Not linearly separable data Some datasets are not linearly separable!©2005-2007 Carlos Guestrin4Addressing non-linearly separable data – Option 1, non-linear features Choose non-linear features, e.g., Typical linear features: w0+ ∑iwixi Example of non-linear features: Degree 2 polynomials, w0+ ∑iwixi+ ∑ijwijxixj Classifier hw(x) still linear in parameters w As easy to learn Data is linearly separable in higher dimensional spaces More discussion later this semester3©2005-2007 Carlos Guestrin5Addressing non-linearly separable data – Option 2, non-linear classifier Choose a classifier hw(x) that is non-linear in parameters w,e.g., Decision trees, neural networks, nearest neighbor,… More general than linear classifiers But, can often be harder to learn (non-convex/concave optimization required) But, but, often very useful (BTW. Later this semester, we’ll see that these options are not that different)©2005-2007 Carlos Guestrin6A small dataset: Miles Per GallonFrom the UCI repository (thanks to Ross Quinlan)40 Recordsmpg cylinders displacement horsepower weight acceleration modelyear makergood 4 low low low high 75to78 asiabad 6 medium medium medium medium 70to74 americabad 4 medium medium medium low 75to78 europebad 8 high high high low 70to74 americabad 6 medium medium medium medium 70to74 americabad 4 low medium low medium 70to74 asiabad 4 low medium low low 70to74 asiabad 8 high high high low 75to78 america:: : : : : : ::: : : : : : ::: : : : : : :bad 8 high high high low 70to74 americagood 8 high medium high high 79to83 americabad 8 high high high low 75to78 americagood 4 low low low low 79to83 americabad 6 medium medium medium high 75to78 americagood 4 medium low low low 79to83 americagood 4 low low medium high 79to83 americabad 8 high high high low 70to74 americagood 4 low medium low medium 75to78 europebad 5 medium medium medium medium 75to78 europeSuppose we want to predict MPG4©2005-2007 Carlos Guestrin7A Decision Stump©2005-2007 Carlos Guestrin8Recursion StepTake theOriginalDataset..And partition it accordingto the value of the attribute we split onRecords in which cylinders = 4 Records in which cylinders = 5Records in which cylinders = 6 Records in which cylinders = 85©2005-2007 Carlos Guestrin9Recursion StepRecords in which cylinders = 4 Records in which cylinders = 5Records in which cylinders = 6 Records in which cylinders = 8Build tree fromThese records..Build tree fromThese records..Build tree fromThese records..Build tree fromThese records..©2005-2007 Carlos Guestrin10Second level of treeRecursively build a tree from the seven records in which there are four cylinders and the maker was based in Asia(Similar recursion in the other cases)6©2005-2007 Carlos Guestrin11The final tree©2005-2007 Carlos Guestrin12Classification of a new example Classifying a test example – traverse tree and report leaf label7©2005-2007 Carlos Guestrin13Are all decision trees equal? Many trees can represent the same concept But, not all trees will have the same size! e.g., φ = A∧B ∨¬A∧C ((A and B) or (not A and C))©2005-2007 Carlos Guestrin14Learning decision trees is hard!!! Learning the simplest (smallest) decision tree is an NP-complete problem [Hyafil & Rivest ’76] Resort to a greedy heuristic: Start from empty decision tree Split on next best attribute (feature) Recurse8©2005-2007 Carlos Guestrin15Choosing a good attributeTTTTFTFFFFTFFFFTTFTFTTTTYX2X1©2005-2007 Carlos Guestrin16Measuring uncertainty Good split if we are more certain about classification after split Deterministic good (all true or all false) Uniform distribution badP(Y=C) = 1/4P(Y=B) = 1/4 P(Y=D) = 1/4P(Y=A) = 1/4P(Y=C) = 1/8P(Y=B) = 1/4 P(Y=D) = 1/8P(Y=A) = 1/29©2005-2007 Carlos Guestrin17EntropyEntropy H(X) of a random variable YMore uncertainty, more entropy!Information Theory interpretation: H(Y) is the expected number of bits needed to encode a randomly drawn value of Y (under most efficient code) ©2005-2007 Carlos Guestrin18Andrew Moore’s Entropy in a nutshellLow Entropy High Entropy10©2005-2007 Carlos Guestrin19Low Entropy High Entropy..the values (locations of soup) unpredictable... almost uniformly sampled throughout our dining room..the values (locations of soup) sampled entirely from within the soup bowlAndrew Moore’s Entropy in a nutshell©2005-2007 Carlos Guestrin20Information gain Advantage of attribute – decrease in uncertainty Entropy of Y before you split Entropy after split Weight by probability of following each branch, i.e., normalized number of records Information gain is differenceTTTTFTFFFTTFTFTTTTYX2X111©2005-2007 Carlos Guestrin21Learning decision trees Start from empty decision tree Split on next best attribute (feature) Use, for example, information gain to select attribute Split on Recurse©2005-2007 Carlos Guestrin22Look at all the information gains…Suppose we want to predict MPG12©2005-2007 Carlos Guestrin23A Decision Stump©2005-2007 Carlos Guestrin24Base Case OneDon’t split a node if all matching records have the same output value13©2005-2007 Carlos Guestrin25Base Case TwoDon’t split a node if none of the attributes can create multiple non-empty children©2005-2007 Carlos Guestrin26Base Case Two: No attributes can distinguish14©2005-2007 Carlos Guestrin27Base Cases Base Case One: If all records in current data subset have the same output then don’t recurse Base Case Two: If all records have exactly the same set of inputattributes then don’t recurse©2005-2007 Carlos Guestrin28Base Cases: An idea Base Case One: If all records in current data subset have the same output then don’t recurse Base Case Two: If all records have exactly the same set of inputattributes then don’t recurseProposed Base Case 3:If all attributes have zero information gain then don’t recurse•Is this a good idea?15©2005-2007 Carlos Guestrin29The problem with Base Case 3aby000011101110y = a XOR bThe information
View Full Document
Unlocking...