Decision Trees (SL1)

Expressiveness

• Can model AND and OR (swappable)
• Can model XOR as a representation of entire truth table
• N-OR: Linear Relationship
• N-XOR: Exponential Relationship ($2^N$) nodes

Regression

• For leaf nodes in regression, it is the average (mean) due to min(SSE)
• Pruning can help with overfitting

Info Gain

• Gain = Entropy(Parent) - Entropy(After Split)
• Max entropy = outcome equally distributed (random)
• Min entropy = know outcome

Biases

• Models have inductive biases (restriction + preference)
• Restriction Bias → all possible decision trees
• Preference Bias → shallow trees with good splits at the top

Classification and Regression (SL2)

Goals