Page cover image

#10: Decision Trees

  • 3 min

#10: Decision Trees content

Created
Topics
+ Random Forest

Decision Trees

Motivation and intuition behind trees

Composition

  • Node: tests a single attribute
  • Branch: one for each value of the attribute
  • Leaf: assign a class to the sample

Function Class

A decision tree can represent any function of the input

What Makes a Good Decision Tree

πŸͺ’
Principle of Occam’s Razor: the simpler the better
  • Learning the simplest & smallest decision tree β‡’ NP-complete problem (exponential computational complexity, hard to solve)

The Greedy Learning Algorithm

  1. Start with an empty tree
  1. Select the best possible attribute to split on
    1. Generate child nodes: one for each value
  1. Partition samples according to their values & assign to appropriate child node
  1. Recurse: repeat for each child node; return if all samples at a node are in the same class

Choosing the Best Variable to Split

More certainty about the classification
  • Good fit: all samples of different classes goes to different nodes
  • Bad fit: equal number of samples fall in both classes

Theorizing Choosing the Best Variable

Entropy H(X)H(X)

The expected number of bits needed to encode a randomly drawn value of under the most efficient code
H(X)=βˆ’βˆ‘i=1kP(X=xi)β‹…log⁑2P(X=xi)H(X)=-\sum_{i=1}^{k} P\left(X=x_{i}\right) \cdot \log _{2} P\left(X=x_{i}\right)
High: uniform-like distribution, less predictable
Low: has peeks, more predictable

Conditional Entropy

Conditioned YY on XX
H(Y∣X)=βˆ’βˆ‘j=1vP(X=xj)βˆ‘i=1kP(Y=yi∣X=xj)β‹…log⁑2P(Y=yi∣X=xj)H(Y \mid X)=-\sum_{j=1}^{v} P\left(X=x_{j}\right) \sum_{i=1}^{k} P\left(Y=y_{i} \mid X=x_{j}\right) \cdot \log _{2} P\left(Y=y_{i} \mid X=x_{j}\right)

Information Gain

Decrease in entropy after splitting at feature XX
IG(X)=H(Y)βˆ’H(Y∣X)IG(X)=H(Y)-H(Y|X)
Choose a variable that maximizes information gain
arg⁑max⁑iIG(Xi)=arg⁑max⁑iH(Y)βˆ’H(Y∣Xi)\arg \max _{i} I G\left(X_{i}\right)=\arg \max _{i} H(Y)-H\left(Y \mid X_{i}\right)

Know When to Stop

  • Biased toward finding a simpler tree
  • If stop too late: all samples will have its own class

Case When Information Gain IG(X)=0IG(X)=0

Involve an over-split hyperparameter
  • Over-split: randomly split & explore a few more levels
  • Then prune unused nodes

Choosing a Best Decision Tree

Decision trees will overfit!
  • Standard D-Tree: Bias = 0
  • High variance: slight change β†’ huge difference

Heuristics Toward Obtaining Simper Trees

  • Lower bounding # of samples per leaf node
  • Upper bounding depth
  • Ensemble Learning (Random Forests)

Continuous Variable Decision Tree

Decision Stumps

Determine a threshold tt (Decision Stumps) to split for variable XX
  • Branch 1: X<tX<t
  • Branch 2: Xβ‰₯tX\geq t
Can allow repeated splits on the same variable w/ different thresholds

Choosing tt

❌ search through all possible values
βœ”οΈ Sort data
  • Consider splits at Xi+(Xi+1βˆ’Xi)/2X_i+(X_{i+1}-X_i)/2
  • Only split at t with most IG

Formulas

H(Y∣Xβ‹šY)=P(X<t)β‹…H(Y∣X<t)+P(Xβ‰₯t)β‹…H(Y∣Xβ‰₯t)IG(Y∣Xβ‹št)=H(Y)βˆ’H(Y∣Xβ‹št)IGβˆ—(Y∣X)=max⁑tIG(Y∣Xβ‹št)\begin{aligned}&H\left(Y \mid X\lesseqgtr Y\right)=P(X<t) \cdot H(Y \mid X<t)+P(X \geq t) \cdot H(Y \mid X \geq t) \\& I G\left(Y \mid X\lesseqgtr t\right)=H(Y)-H\left(Y \mid X\lesseqgtr t\right) \\& I G^{*}(Y \mid X)=\max _{t} I G\left(Y \mid X\lesseqgtr t\right)\end{aligned}

Interpretation of Decision Trees

  1. May be readable but may not use human logic
  1. Need to use heuristics to avoid overfitting (depth limit, leaf bin size threshold, etc.)
  1. Very high variance: a small change in data will result in a completely different tree

Ensemble Learning

Reduce variance in models by
  • Train multiple models trained on the same data set
  • Perform an average over predictions
#11: Ensemble Learning
Β