A DECISION TREE is a tree in which each INTERNAL NODE tests an attribute each BRANCH corresponds to a value of that attribute each LEAF assigns a classification Classification proceeds by starting at the root and following the branches matching the instance's attribute values until a leaf is reached. A TREE IS EQUIVALENT TO A SET OF RULES — one rule per path from root to leaf, with the tests conjoined: IF Outlook = Sunny AND Humidity = High THEN Play = No IF Outlook = Overcast THEN Play = Yes THAT EQUIVALENCE IS THE SOURCE OF THE INTERPRETABILITY, and it connects trees directly to the rule-based knowledge of ACtE0904 — except that the rules are INDUCED from data rather than elicited from an expert. Decision-tree induction is therefore the automated answer to the knowledge-acquisition bottleneck. THE PROBLEM DECISION-TREE LEARNING SOLVES: given a table of labelled examples, build a tree that classifies them correctly and generalises to new ones. THE STANDARD ALGORITHM IS ID3 (Quinlan), with C4.5 and CART as its descendants. It is a GREEDY, RECURSIVE, TOP-DOWN procedure: function ID3(examples, attributes) if all examples have the same class return a leaf with that class if attributes is empty return a leaf with the majority class A ← the attribute with the HIGHEST INFORMATION GAIN create a node testing A for each value v of A subset ← examples with A = v if subset is empty attach a leaf with the majority class else attach ID3(subset, attributes − {A}) return the node NOTE THAT IT IS GREEDY: it chooses the locally best attribute at each node and NEVER BACKTRACKS. So it does not find the smallest possible tree — that is NP-hard — but it finds a good one cheaply. THE PREFERENCE FOR SHORT TREES IS ID3's INDUCTIVE BIAS, and it is Occam's razor applied to trees.

THE ATTRIBUTE SELECTION MEASURE. This is the examinable calculation, so it is worked in full. ENTROPY measures the IMPURITY of a set of examples — how mixed the classes are: Entropy(S) = − Σ pᵢ log₂ pᵢ where pᵢ is the proportion of examples in class i. For two classes: all one class → entropy 0 (perfectly pure) 50/50 split → entropy 1 (maximally impure) any other split → between 0 and 1 WORKED SANITY CHECKS: 9 yes, 5 no out of 14: p(yes) = 9/14 = 0.6429, p(no) = 5/14 = 0.3571 E = −0.6429 log₂ 0.6429 − 0.3571 log₂ 0.3571 = −0.6429 × (−0.6374) − 0.3571 × (−1.4854) = 0.4098 + 0.5305 = 0.9403 4 yes, 0 no: E = 0 (pure — no further splitting needed) 3 yes, 3 no: E = 1 (maximally mixed) INFORMATION GAIN is the REDUCTION in entropy achieved by splitting on an attribute: Gain(S, A) = Entropy(S) − Σ (|Sᵥ|/|S|) · Entropy(Sᵥ) v ∈ values(A) The second term is the WEIGHTED AVERAGE entropy of the subsets. Gain is how much the split TELLS YOU — how much uncertainty it removes. THE FULL WORKED EXAMPLE — the standard weather dataset, 14 days, 9 yes and 5 no: ┌────┬──────────┬──────┬────────┬────────┬──────┐ │ D │ Outlook │ Temp │Humidity│ Wind │ Play │ ├────┼──────────┼──────┼────────┼────────┼──────┤ │ 1 │ Sunny │ Hot │ High │ Weak │ No │ │ 2 │ Sunny │ Hot │ High │ Strong │ No │ │ 3 │ Overcast │ Hot │ High │ Weak │ Yes │ │ 4 │ Rain │ Mild │ High │ Weak │ Yes │ │ 5 │ Rain │ Cool │ Normal │ Weak │ Yes │ │ 6 │ Rain │ Cool │ Normal │ Strong │ No │ │ 7 │ Overcast │ Cool │ Normal │ Strong │ Yes │ │ 8 │ Sunny │ Mild │ High │ Weak │ No │ │ 9 │ Sunny │ Cool │ Normal │ Weak │ Yes │ │ 10 │ Rain │ Mild │ Normal │ Weak │ Yes │ │ 11 │ Sunny │ Mild │ Normal │ Strong │ Yes │ │ 12 │ Overcast │ Mild │ High │ Strong │ Yes │ │ 13 │ Overcast │ Hot │ Normal │ Weak │ Yes │ │ 14 │ Rain │ Mild │ High │ Strong │ No │ └────┴──────────┴──────┴────────┴────────┴──────┘ STEP 1 — the entropy of the whole set: 9 yes, 5 no → Entropy(S) = 0.9403 STEP 2 — the gain of each attribute. OUTLOOK splits into three subsets: Sunny : 5 examples, 2 yes 3 no → E = 0.971 Overcast : 4 examples, 4 yes 0 no → E = 0.000 Rain : 5 examples, 3 yes 2 no → E = 0.971 weighted = (5/14)(0.971) + (4/14)(0) + (5/14)(0.971) = 0.3468 + 0 + 0.3468 = 0.6936 Gain(Outlook) = 0.9403 − 0.6936 = 0.2467 HUMIDITY splits into two: High : 7 examples, 3 yes 4 no → E = 0.985 Normal : 7 examples, 6 yes 1 no → E = 0.592 weighted = (7/14)(0.985) + (7/14)(0.592) = 0.7885 Gain(Humidity) = 0.9403 − 0.7885 = 0.1518 WIND: Weak : 8 examples, 6 yes 2 no → E = 0.811 Strong : 6 examples, 3 yes 3 no → E = 1.000 weighted = (8/14)(0.811) + (6/14)(1.000) = 0.8922 Gain(Wind) = 0.9403 − 0.8922 = 0.0481 TEMPERATURE: Hot : 4, 2 yes 2 no → E = 1.000 Mild : 6, 4 yes 2 no → E = 0.918 Cool : 4, 3 yes 1 no → E = 0.811 weighted = (4/14)(1.000) + (6/14)(0.918) + (4/14)(0.811) = 0.9111 Gain(Temperature) = 0.9403 − 0.9111 = 0.0292 STEP 3 — THE SUMMARY, and the choice: Gain(Outlook) = 0.2467 ← HIGHEST, so Outlook is the Gain(Humidity) = 0.1518 root Gain(Wind) = 0.0481 Gain(Temperature) = 0.0292 WHY OUTLOOK WINS IS VISIBLE IN THE NUMBERS: its Overcast branch has entropy ZERO — four examples, all yes — so that branch is finished immediately and becomes a leaf. No other attribute produces a pure subset. INFORMATION GAIN REWARDS SPLITS THAT SEPARATE THE CLASSES, and a pure branch is the strongest possible separation. STEP 4 — recurse on the impure branches: Sunny branch (5 examples): compute gains among the remaining attributes. Humidity splits it perfectly — High → all No, Normal → all Yes — so the Sunny subtree is one test. Rain branch (5 examples): Wind splits it perfectly — Weak → Yes, Strong → No. THE RESULTING TREE: Outlook ┌───────────┼───────────┐ Sunny Overcast Rain │ │ │ Humidity YES Wind ┌──┴──┐ ┌──┴──┐ High Normal Weak Strong │ │ │ │ NO YES YES NO FIVE LEAVES, THREE TESTS, and it classifies all 14 examples correctly. Note that TEMPERATURE NEVER APPEARS — it carried too little information, so the tree ignores it entirely. THAT IS FEATURE SELECTION HAPPENING AS A BY-PRODUCT of induction.

THE PROBLEMS WITH BASIC ID3, and the standard fixes: 1. OVERFITTING — the central danger A tree grown until every leaf is pure fits the training data perfectly, including its noise, and generalises badly. With enough attributes a tree can memorise the training set. THE FIXES: PRE-PRUNING (early stopping): stop splitting when a node has too few examples, or when the best gain is below a threshold. Cheap, and risks stopping too early — a split with low gain may enable a very good split below it. POST-PRUNING: grow the full tree, then remove subtrees that do not improve accuracy on a VALIDATION SET. Generally better, because it can see the consequences of a split before deciding. REDUCED-ERROR PRUNING and RULE POST-PRUNING (used by C4.5) are the standard implementations. 2. INFORMATION GAIN FAVOURS ATTRIBUTES WITH MANY VALUES A unique identifier — a student's roll number — splits the data into singletons, every subset is pure, and the gain is maximal. THE TREE IS PERFECT ON TRAINING DATA AND USELESS. THE FIX: GAIN RATIO (C4.5), which divides the gain by the intrinsic information of the split itself: SplitInfo(S, A) = − Σ (|Sᵥ|/|S|) log₂ (|Sᵥ|/|S|) GainRatio(S, A) = Gain(S, A) / SplitInfo(S, A) SplitInfo is large for many-valued attributes, so the ratio penalises them. A roll-number attribute has SplitInfo = log₂ 14 = 3.807 on our dataset, which divides its gain down substantially. ALTERNATIVE: the GINI INDEX, used by CART: Gini(S) = 1 − Σ pᵢ² For 9 yes and 5 no: 1 − (9/14)² − (5/14)² = 1 − 0.4133 − 0.1276 = 0.4592. Gini and entropy usually choose the same attribute and Gini is cheaper to compute — no logarithms. 3. CONTINUOUS ATTRIBUTES ID3 assumes discrete values. For a continuous attribute, sort the values and consider THRESHOLD splits (A < t), choosing the threshold with the best gain. C4.5 does this automatically. 4. MISSING VALUES Options: assign the most common value; assign a value probabilistically; or send the example down all branches with fractional weight, which is C4.5's approach. 5. INSTABILITY (high variance) A small change in the training data can produce a completely different tree, because a different attribute wins at the root and everything below changes. This is the high-variance end of the bias–variance trade-off. THE FIX IS ENSEMBLES, and it is the reason trees are almost never used singly in practice: RANDOM FORESTS: train many trees on bootstrap samples of the data, each considering a random subset of attributes at each split, and vote. Averaging cancels the variance. GRADIENT BOOSTING: train trees in sequence, each correcting the errors of the previous ones. THESE REMAIN AMONG THE STRONGEST METHODS FOR TABULAR DATA, frequently outperforming neural networks on it — which is worth knowing, because it contradicts the assumption that deep learning always wins. THE ADVANTAGES OF DECISION TREES, which is why they persist: · INTERPRETABLE — the path to a leaf is the explanation, and this is the property the AI applications topic identified as a regulatory requirement · handle both numeric and categorical attributes · require no feature scaling · perform automatic FEATURE SELECTION, as Temperature's absence demonstrated · fast to train and to apply · robust to irrelevant attributes THE DISADVANTAGES: · overfit readily without pruning · HIGH VARIANCE — unstable · greedy, so not optimal · axis-aligned splits only, so a diagonal boundary needs many steps to approximate · biased toward many-valued attributes without gain ratio · poor at learning some simple functions — parity and XOR need an exponentially large tree