ML-COMP3020-Lecture 2-Decision Trees

Today: Decision Trees What is decision tree? How to learn a decision tree from data? What is inductive bias? What exactly is generalization?

Decision Trees e Representation o Each node tests a feature (attribute) o Each branch corresponds to a feature value (outcome) o Each leaf node assigns a final decision (classification) m Or adistribution over decisions e A decision tree represents a function that maps examples In XtoaclassinY:-: f. <Weather, Temperature, Humidity, Wind> — PlayBadminton?

Today: Decision Trees What is decision tree? How to learn a decision tree from data? What is inductive bias? What exactly is generalization?

Decision Trees Learning e Find the hypothesis h ¢ H o Such that it minimizes the training error o Or maximizes the training accuracy e Challenges? o H is too large for exhaustive search o We opt for heuristic (greedy) search algorithms that m Pick questions to ask, in order m Such that classification accuracy is maximized 12

Build a decision tree: partition with Wind? [ Wind ] Weak Weather Day Temperature Humidity Wind Play? 1 Sunny Hot High Weak No 2 Cloudy Hot High Weak Yes 3 Sunny Mild Normal Strong Yes 4 Cloudy Mild High Strong Yes 5 Rainy Mild High Strong No 6 Rainy Cool Normal Strong | No 7 Rainy Mild High Weak Yes 8 Sunny Hot High Strong ‘ No 9 Cloudy Hot Normal Weak Yes 10 Rainy Mild High Strong | No - 15

Build a decision tree: partition with Humidity & Wind? [ Wind ] Weak Strong [ Humidity ] High Normal Acc: 0.75 Acc: 1.00 Avg: 0.875 Weather Day Temperature Humidity Wind Play? 1 Sunny Hot f High Weak No \‘ 2 Cloudy Hot J\ahHighg\ ~ Weak =\Yesl%)\ 3 Sunny Mild | Normal Strong Yes | 4 Cloudy Mild High Strong Yes 5 Rainy Mild High Strong No 6 Rainy Cool Normal | Strong No 7 | Rainy ild High | Weak | Yes || 8 Sunny Hot i ngh S;rong | No 9 Cloudy Hot Normal Weak Yes 10 Rainy Mild High Strong | No - 18

Entropy of a random variable e Entropy H(X) of a random variable X- ZP = 1) log, P(X = 1) e H(X)isthe number of expected bits needed to encode a randomly drawn value of X (under most efficient code) 21

Entropy of a random variable Entropy H(X) of a random variable X: ZP = 1) log, P(X = 1) e H(X)isthe number of expected bits needed to encode a randomly drawn value of X (under most efficient code) Why entropy? Information theory o To encode a message X = 7, the most efficient code assigns — log, P(X = 1) bits o So the expected number of bits to encode one random X is: —ZP — i) log, P(X = i) 22

Conditional Entropy Conditional Entropy H(Y | X) of a variable Y conditioned on a random variable X m HY|X)=) P(X=jHY |X=j) H(Y |X=j)=Y PY=i| X =j)log, P(Y =i | X = j 23

Conditional Entropy HY | X)= Y P(X= )Y P(Y =i | X = j)logy P(Y =i | X = j) =1 i=1 X, | %, | Y T|7 T | F |8 T | T B8 T | F BB F| T B F | F [BF

Conditional Entropy HY | X)= Y P(X= )Y P(Y =i | X = j)logy P(Y =i | X = j) =1 i=1 Example: X X1 % LY ple: t/1\f T | T Bk T | F e P(X,=t) = 4/6 Yedih wased 1 P(X,=f) = 2/6 Y=F:0 yef. - T | F el F | T PBE F | F

Conditional Entropy n H(Y | X)= - Y P(X =) P(Y =i| X = j)log, P(Y = | X = j) 7=1 1=1 Example: X, t/\f P(X4=t) = 4/6 Y=t:4 y=t-1 P(X,=f) = 2/6 Y=f:0 vy=f-1 H(Y|X,) =-4/6 (1log,1 + 0 log, 0) - 2/6 (1/2 log, 1/2 + 1/2 log, 1/2) = 2/6 X, | %, | Y T|7 T | F |8 T | T B8 T | F BB F| T B F | F [BF 26

Information Gain e Decrease in entropy (uncertainty) after splitting IGIX)=H(Y)—-H(Y | X) 27

Information Gain e Decrease in entropy (uncertainty) after splitting IGIX)=H(Y)—-H(Y | X) In our example: IG(X1)=H(Y) - H(Y | X;) m(m|A|—|[H| M| |7m|d|7n |4 X T (=SS S e < 28

Information Gain e Decrease In entropy (uncertainty) after splitting IG(X)=H(Y) - H(Y | X) In our example: IG(X,)=H(Y)-H(Y | X1) = 0.65 — 0.33 IG(X) > 0 — prefer the split X, | X, | Y T T T|F T T B T|F [ F| T |8 F | F BB 29

Today: Decision Trees What is decision tree? How to learn a decision tree from data? What is inductive bias? What exactly is generalization? 30

Inductive bias in decision tree learning s e The learning algorithm performs /{\ heuristic search through the e e ‘ \ space of all decision trees e |t stops at the smallest, fi% /'?5?\ acceptable tree N e Occam’s Razor: prefer the q . simplest hypothesis that fits the /{ES A ;E data + 31

Why preference for short hypotheses? e Fewer short hypotheses than long ones o Therefore, a short hypothesis that fits the data is less likely to be a statistical coincidence. e But what is so special about short hypothesis? 32

Today: Decision Trees What is decision tree? How to learn a decision tree from data? What is inductive bias? What exactly is generalization? 33

Evaluating the learned hypothesis e Assume that o We've learned a tree h using the top-down induction algorithm o |t fits the training data perfectly e Are we done? o Can we guarantee we have found a good hypothesis? 34

Examples of Class A Examples of Class B | - | Recall: Background in-focus Training Metrics do not tell us anything about generalization! ) £ - ~ - " ; T~ vy : - X Ty ' . A ST - S anityo) e . B Yo A = . - 3 . b i L 4 ) py y . ‘o n . p B - \ : ‘\' N ’ ) l. R . 4y : : -

Recall: Formalizing Induction e Given o a loss function [ o samples from some unknown data distribution D e OQOurtask is to compute a function f that has low expected error over D with respect to [ E (2 4)~n[l(y, £ Zvay y, f(z)) 36

Training error is not sufficient e \We care about generalization to new (unseen) and related examples e A tree can classify training data perfectly, yet classify new examples incorrectly. How? 37

Training error is not sufficient e \We care about generalization to new (unseen) and related examples e A tree can classify training data perfectly, yet classify new examples incorrectly. How? o Training data is only a sample from the data-generating distribution m A feature might correlate with class by coincidence o Training examples can be noisy m e.g., labeling mistakes 38

Day { Weather | Temperature { Humidity Wind : : | » | *1 Add|ng d nO|Sy 1 | Sunny Hot | High - Weak training example , couqy Hot High | Weak 3 | Sunny Mild Normal | Strong Mild High Strong Sunny Cloudy Rainy Mild ' ngh Strong Cool Normal Strong Mild .~ High | Weak High Normal Strong Weak — 1 ——— r / N / N Hot High Strong No Yes No Yes | o ! 9 | Cloudy Hot ~ Normal | Weak 10 Rainy Mild High Strong 11 Sunny Mild | High ;Strong;

Day { Weather | Temperature { Humidity Wind : : | » | *1 Add|ng d nO|Sy 1 | Sunny Hot | High - Weak training example , couqy Hot High | Weak 3 | Sunny Mild Normal | Strong Mild High Strong y ot iy Mild | High Strong Cool Normal Strong Mild .~ High | Weak High Normal Strong Weak — 1 ——— r / N / N Hot High Strong No Yes No Yes | o ! 9 | Cloudy Hot ~ Normal | Weak 10 Rainy Mild High Strong 11 Sunny Mild | High ;Strong;

Overfitting e Given a hypothesis h and its: o Training Error over training data erroriq;,(h) o True Error over all data errory.,.(h) 41

Overfitting e Given a hypothesis h and its: o Training Error over training data erroriq;,(h) o True Error over all data errory.,.(h) e \We say h overfits the training data if: errorirein(h) < erroriue(h) e Amount of overfitting: erroriue(h) — erroripqin(h) 42

The need for test data e We don’t know errory.,.(h) 43

The need for test data e We don’t know errory.,.(h) e Solution: o We set aside a test set m Some examples that will be used for evaluation o We never look at them during training o After learning, we calculate erroriest () 44

Measuring the effect of overfitting in decision trees 0-9 I I I I I I I I I 0.85 0.8 0.75 Accuracy =) < 0.65 - 06 On training data —— . On test data —--— 035 M 0.5 1 1 1 1 1 1 1 1 1 0 10 20 30 40 50 60 70 80 90 100 Size of tree (number of nodes)

Underfitting vs. Overtfitting e \When underfitting? o Learning algorithms had the opportunity to learn more from training data, but didn't e \When overfitting? o Learning algorithms paid too much attention to learn the noisy part of the training data, resulting in a tree that does not generalize well on test data. e \What we want is: o A decision tree that neither underfits nor overfits o Because it is expected to do best in the future 46

Recap: Decision trees e \What is decision tree? e How to learn a decision tree from data? o Top-down induction to minimize (training) classification error e \What is inductive bias? o Occam’s Razor: short trees are preferred e \What exactly is generalization? o Overfitting can be an issue 47