CSC 411: Lecture 06: Decision Trees

1 csc 411 : Lecture 06: Decision TreesRichard Zemel, Raquel Urtasun and Sanja FidlerUniversity of TorontoZemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees1 / 39 TodayDecision TreesIentropyIinformation gainZemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees2 / 39 Another Classification IdeaWe learned about linear classification ( , logistic regression), and nearestneighbors. Any other idea?Pick an attribute, do a simple testConditioned on a choice, pick another attribute, do another testIn the leaves, assign a class with majority voteDo other branches as wellZemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees3 / 39 Another Classification IdeaGives axes aligned Decision boundariesZemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees4 / 39 Decision tree : ExampleYes No Yes No Yes No Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees5 / 39 Decision tree : ClassificationZemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees6 / 39 Example with Discrete InputsWhat if the attributes are discrete?

2 Attributes:Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees7 / 39 Decision tree : Example with Discrete InputsThe tree to decide whether to wait (T) or not (F)Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees8 / 39 Decision TreesYes No Yes No Yes No Internal nodes test attributesBranching is determined by attribute valueLeaf nodes are outputs (class assignments)Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees9 / 39 Decision tree : AlgorithmChoose an attribute on which to descend at each levelCondition on earlier (higher) choicesGenerally, restrict only one dimension at a timeDeclare an output value when you get to the bottomIn the orange/lemon example, we only split each dimension once, but that isnot requiredZemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees10 / 39 Decision tree : Classification and RegressionEach path from root to a leaf defines a regionRmof input spaceLet{(x(m1),t(m1)).}

3 ,(x(mk),t(mk))}be the training examples that fall intoRmClassification tree :Idiscrete outputIleaf valueymtypically set to the most common value in{t(m1),..,t(mk)}Regression tree :Icontinuous outputIleaf valueymtypically set to the mean value in{t(m1),..,t(mk)}Note: We will only talk about classification[Slide credit: S. Russell]Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees11 / 39 ExpressivenessDiscrete-input, discrete-output case:IDecision Trees can express any function of the input , for Boolean functions, truth table row path to leaf:Continuous-input, continuous-output case:ICan approximate any function arbitrarily closelyTrivially, there is a consistent Decision tree for any training set w/ one pathto leaf for each example (unlessfnondeterministic inx) but it probablywon t generalize to new examplesNeed some kind of regularization to ensure morecompactdecision Trees [Slide credit: S.]

4 Russell]Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees12 / 39 How do we Learn a DecisionTree?How do we construct a useful Decision tree ?Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees13 / 39 Learning Decision TreesLearning the simplest (smallest) Decision tree is an NP complete problem [if youare interested, check: Hyafil & Rivest 76]Resort to a greedy heuristic:IStart from an empty Decision treeISplit on next best attributeIRecurseWhat is best attribute?We use information theory to guide us[Slide credit: D. Sontag]Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees14 / 39 Choosing a Good AttributeWhich attribute is better to split on,X1orX2?

5 Idea:Use counts at leaves to define probability distributions, so we can measureuncertainty[Slide credit: D. Sonntag]Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees15 / 39 Choosing a Good AttributeWhich attribute is better to split on,X1orX2?IDeterministic: good (all are true or false; just one class in the leaf)IUniform distribution: bad (all classes in leaf equally probable)IWhat about distributons in between?Note: Let s take a slight detour and remember concepts from information theory[Slide credit: D. Sontag]Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees16 / 39We Flip Two Different CoinsSequence 1: 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0.

6 ? Sequence 2: 0 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 1 .. ? 16 2 8 10 0 1 versus 0 1 Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees17 / 39 Quantifying UncertaintyEntropyH:H(X) = x Xp(x) log2p(x)0 1 8/9 1/9 89log289 19log219 120 1 4/9 5/9 49log249 59log259 surprised are we by a new value in the sequence?How much information does it convey?Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees18 / 39 Quantifying UncertaintyH(X) = x Xp(x) log2p(x) p of , Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees19 / 39 Entropy High Entropy :IVariable has a uniform like distributionIFlat histogramIValues sampled from it are less predictable Low Entropy IDistribution of variable has many peaks and valleysIHistogram has many lows and highsIValues sampled from it are more predictableThis slide seems wrong[Slide credit: Vibhav Gogate]Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees20 / 39 Entropy of a Joint DistributionExample.

7 X={Raining, Not raining},Y={Cloudy, Not cloudy}Cloudy'Not'Cloudy'Raining'24/100' 1/100'Not'Raining'25/100'50/100'H(X,Y)= x X y Yp(x,y) log2p(x,y)= 24100log224100 1100log21100 25100log225100 50100log250100 , Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees21 / 39 Specific Conditional EntropyExample:X={Raining, Not raining},Y={Cloudy, Not cloudy}Cloudy'Not'Cloudy'Raining'24/100' 1/100'Not'Raining'25/100'50/100'What is the entropy of cloudinessY,given that it is raining?H(Y|X=x)= y Yp(y|x) log2p(y|x)= 2425log22425 125log2125 used:p(y|x) =p(x,y)p(x),andp(x) = yp(x,y)(sum in a row)Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees22 / 39 Conditional EntropyCloudy'Not'Cloudy'Raining'24/100' 1/100'Not'Raining'25/100'50/100'The expected conditional entropy:H(Y|X)= x Xp(x)H(Y|X=x)= x X y Yp(x,y) log2p(y|x)Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees23 / 39 Conditional EntropyExample:X={Raining, Not raining},Y={Cloudy, Not cloudy}Cloudy'Not'Cloudy'Raining'24/100' 1/100'Not'Raining'25/100'50/100'What is the entropy of cloudiness, given the knowledge of whether or not itis raining?

8 H(Y|X)= x Xp(x)H(Y|X=x)=14H(cloudy|is raining) +34H(cloudy|not raining) bitsZemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees24 / 39 Conditional EntropySome useful properties:IHis always non-negativeIChain rule:H(X,Y) =H(X|Y) +H(Y) =H(Y|X) +H(X)IIfXandYindependent, thenXdoesn t tell us anything aboutY:H(Y|X) =H(Y)IButYtells us everything aboutY:H(Y|Y) = 0 IBy knowingX, we can only decrease uncertainty aboutY:H(Y|X) H(Y)Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees25 / 39 Information GainCloudy'Not'Cloudy'Raining'24/100'1/1 00'Not'Raining'25/100'50/100'How much information about cloudiness do we get by discovering whether itis raining?

9 IG(Y|X)=H(Y) H(Y|X) bitsAlso called information gain inYdue toXIfXis completely uninformative aboutY:IG(Y|X) = 0 IfXis completely informative aboutY:IG(Y|X) =H(Y)How can we use this to construct our Decision tree ?Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees26 / 39 Constructing Decision TreesYes No Yes No Yes No I made the fruit data partitioning just by eyeballing can use the information gain to automate the each level, one must choose:1. Which variable to Possibly where to split them based on how much information we would gain from thedecision! (choose attribute that gives the highest gain)Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees27 / 39 Decision tree Construction AlgorithmSimple, greedy, recursive approach, builds up tree node-by-node1.

10 Pick an attribute to split at a non-terminal node2. split examples into groups based on attribute value3. for each group:Iif no examples return majority from parentIelse if all examples in same class return classIelse loop to step 1 Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees28 / 39 Back to Our ExampleAttributes:[from: Russell & Norvig]Zemel, Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees29 / 39 Attribute SelectionIG(Y) =H(Y) H(Y|X)IG(type) = 1 [212H(Y|Fr.) +212H(Y|It.) +412H(Y|Thai) +412H(Y|Bur.)]= 0IG(Patrons) = 1 [212H(0,1) +412H(1,0) +612H(26,46)] , Urtasun, Fidler (UofT) csc 411 : 06- Decision Trees30 / 39 Which tree is Better?