02_Decision_Trees_and_Random_Forests

Module 1 — Decision Trees and Random Forests

Source: Lec 3–4 — Decision Tree and Random Forest Classifiers.

The running dataset (Quinlan’s weather data, 14 rows). Features: Outlook $\in \{S,O,R\}$ (Sunny, Overcast, Rainy), Temperature $\in \{H,M,C\}$, Humidity $\in \{H,N\}$, Wind $\in \{F,T\}$; class PlayTennis $\in \{Y,N\}$ (9 Yes, 5 No).

#	Out	Temp	Hum	Wind	Play		#	Out	Temp	Hum	Wind	Play
1	S	H	H	F	N		8	S	M	H	F	N
2	S	H	H	T	N		9	S	C	N	F	Y
3	O	H	H	F	Y		10	R	M	N	F	Y
4	R	M	H	F	Y		11	S	M	N	T	Y
5	R	C	N	F	Y		12	O	M	H	T	Y
6	R	C	N	T	N		13	O	H	N	F	Y
7	O	C	N	T	Y		14	R	M	H	T	N

Errata note on the source. The lecture’s printed value "$E(X)=-\frac{9}{5}{\log }_2\frac{9}{5}-\frac{9}{14}{\log }_2\frac{9}{14}$" is a typo; the correct expression is $-\frac{9}{14}{\log }_2\frac{9}{14}-\frac{5}{14}{\log }_2\frac{5}{14}=0.940$. Also, the “gain ratio” denominator written $E(X,f)$ is the split information (defined in C6). Both are corrected below.

---

C4. Entropy and Information Gain

Intuition

Entropy measures how mixed a set is. A bag with only Yes’s is “pure”: no surprise, entropy 0. A bag half Yes half No is maximally mixed: entropy 1 bit. Information gain = how much a question (a feature) reduces mixing. We pick the question that reduces it most.

Formal definition

For a set $X$ with $c$ classes and class proportions $p_i$: $E(X)={\sum }_{i=1}^c-p_i{\log }_2{p}_i,0\log 0:=0.$ Information gain of feature $f$: $IG(X,f)=E(X)-{\sum }_{v\in values(f)}\frac{|X_v|}{|X|}E(X_v),X_v=\{x\in X:f(x)=v\}.$

Mathematical formulation / properties

• $E(X)=0$ iff all members are in one class.
• Two classes: $E=1$ iff $p=\frac{1}{2}$; $E\in [0,1]$.
• $c$ classes: $0\le E\le {\log }_{2}c$, with equality on the right iff all $p_i=1/c$.
• Interpretation: minimum average number of bits to encode the class of a random member.

Derivation (maximum at the uniform distribution, two classes)

$E(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. Differentiate: $E^{\prime }(p)=-{\log }_{2}p-\frac{1}{\ln 2}+{\log }_2(1-p)+\frac{1}{\ln 2}={\log }_2\frac{1-p}{p}.$ $E^{\prime }(p)=0⟺p=\frac{1}{2}$; $E^{\prime }>0$ for $p<\frac{1}{2}$ and $<0$ for $p>\frac{1}{2}$ → maximum, $E(\frac{1}{2})=1$. ∎

Why $IG\ge 0$: $IG$ equals the mutual information between feature and class, which is non-negative (Jensen’s inequality / concavity of entropy: the weighted average of child entropies cannot exceed the parent entropy).

Key insights

• IG is the expected reduction in entropy from learning $f$.
• IG is biased toward features with many values (a unique-ID column gives pure singleton children, IG = full entropy) → fixed by gain ratio (C6).
• Greedy: IG is only a one-step lookahead (see C9, XOR failure).

Worked examples

Example 1 — Very Easy

• Problem: Compute $E$ for (a) 8 Yes and 0 No; (b) 4 Yes and 4 No; (c) 1 Yes and 3 No.
• Asked: Three entropies.
• Concept: Entropy definition.
• Approach: Insert proportions.
• Solution: (a) $p=(1,0)$: $-1{\log }_{2}1-0{\log }_{2}0=0-0=0$. (b) $p=(\frac{1}{2},\frac{1}{2})$: $-\frac{1}{2}{\log }_2\frac{1}{2}-\frac{1}{2}{\log }_2\frac{1}{2}=\frac{1}{2}+\frac{1}{2}=1$. (c) $p=(\frac{1}{4},\frac{3}{4})$: $-\frac{1}{4}{\log }_2\frac{1}{4}-\frac{3}{4}{\log }_2\frac{3}{4}=\frac{1}{4}(2)+\frac{3}{4}(0.4150)=0.5+0.3113=0.8113$.
• Final answer: $0,1,0.811$ bits.
• Key lesson: Purer ⇒ smaller entropy.

Example 2 — Easy

• Problem: Entropy of the weather data (9 Yes, 5 No).
• Asked: $E(X)$.
• Concept: Entropy.
• Approach: $p_Y=\frac{9}{14}$, $p_N=\frac{5}{14}$.
• Solution: ${\log }_2\frac{9}{14}={\log }_{2}0.6429=-0.6374$; ${\log }_2\frac{5}{14}={\log }_{2}0.3571=-1.4854$. $E=0.6429(0.6374)+0.3571(1.4854)=0.4098+0.5305=0.9403$.
• Final answer: $E(X)=0.940$ bits.
• Key lesson: Nearly 1 because the classes are fairly balanced.

Example 3 — Moderate

• Problem: Compute $IG(X,\text{Wind})$ for the weather data.
• Asked: $IG$.
• Concept: Information gain.
• Approach: Partition by Wind, compute child entropies, weight them.
• Solution: Wind=F: rows 1,3,4,5,8,9,10,13 → 8 rows; Yes: 3,4,5,9,10,13 (6), No: 1,8 (2). $E=-\frac{6}{8}{\log }_2\frac{6}{8}-\frac{2}{8}{\log }_2\frac{2}{8}=0.75(0.4150)+0.25(2)=0.3113+0.5=0.8113$. Wind=T: rows 2,6,7,11,12,14 → 6 rows; Yes: 7,11,12 (3), No: 2,6,14 (3). $E=1$. Weighted: $\frac{8}{14}(0.8113)+\frac{6}{14}(1)=0.4636+0.4286=0.8922$. $IG=0.9403-0.8922=0.0481$.
• Final answer: $IG(X,\text{Wind})=0.048$.
• Key lesson: A tiny gain means the feature barely separates the classes.

Example 4 — Hard

• Problem: Within the Sunny branch (rows 1,2,8,9,11: 2 Yes, 3 No), choose the best next feature among Temperature, Humidity, Wind.
• Asked: The IG of each and the winner.
• Concept: Recursive greedy splitting.
• Approach: Compute $E$ of the branch, then IG for each feature restricted to this subset.
• Solution: $E(S)=-\frac{2}{5}{\log }_2\frac{2}{5}-\frac{3}{5}{\log }_2\frac{3}{5}=0.4(1.3219)+0.6(0.7370)=0.5288+0.4422=0.9710$. Temperature: Hot = rows 1,2 (N,N) $E=0$; Mild = rows 8,11 (N,Y) $E=1$; Cool = row 9 (Y) $E=0$. Weighted $=\frac{2}{5}\cdot 0+\frac{2}{5}\cdot 1+\frac{1}{5}\cdot 0=0.4$. $IG=0.9710-0.4=0.571$. Humidity: High = rows 1,2,8 (N,N,N) $E=0$; Normal = rows 9,11 (Y,Y) $E=0$. Weighted $=0$. $IG=0.971$. Wind: F = rows 1,8,9 (N,N,Y) $E=0.9183$; T = rows 2,11 (N,Y) $E=1$. Weighted $=\frac{3}{5}(0.9183)+\frac{2}{5}(1)=0.5510+0.4=0.9510$. $IG=0.020$.
• Final answer: Split Sunny on Humidity (IG 0.971 — a perfect split).
• Key lesson: The best feature depends on the node; gains must be recomputed on the subset.

Example 5 — Very Hard

• Problem: A numeric feature $x$ takes values $1,\dots ,8$ with labels $N,N,Y,Y,Y,N,N,N$. Using binary splits ”$x<t$ vs $x\ge t$” at midpoints, find the best threshold by IG. Also state which thresholds need to be considered at all.
• Asked: Best $t$ and candidate set.
• Concept: IG for continuous features (C4.5-style thresholds).
• Approach: Parent entropy; evaluate midpoints; observe that only label-change boundaries can be optimal.
• Solution: Parent: 3 Yes, 5 No: $E=-\frac{3}{8}{\log }_2\frac{3}{8}-\frac{5}{8}{\log }_2\frac{5}{8}=0.5306+0.4238=0.9544$. $t=2.5$: left $\{N,N\}$ $E=0$; right (3Y,3N) $E=1$. $IG=0.9544-\frac{6}{8}(1)=0.2044$. $t=5.5$: left (3Y,2N) $E=0.9710$; right $\{N,N,N\}$ $E=0$. $IG=0.9544-\frac{5}{8}(0.9710)=0.9544-0.6069=0.3475$. $t=3.5$ (inside the Y-block): left (1Y,2N) $E=0.9183$; right (2Y,3N) $E=0.9710$. $IG=0.9544-\frac{3}{8}(0.9183)-\frac{5}{8}(0.9710)=0.9544-0.3444-0.6069=0.0031$. Other midpoints give $0.092,0.049,0.204,0.092$ for $1.5,4.5,6.5,7.5$ respectively. The maximum is at $t=5.5$. Candidates: only midpoints between adjacent values with different labels ($2.5$ and $5.5$) can be optimal, since moving a cut inside a same-label run can only mix classes.
• Final answer: $t^{\ast }=5.5$, $IG=0.348$.
• Key lesson: For numeric features, scan label-boundary midpoints; the best cut need not be near the median.

Common mistakes

• Using $\ln$ instead of ${\log }_2$ (changes units, not the argmax, but changes numbers).
• Forgetting the weights $|X_v|/|X|$.
• Computing IG over the whole data instead of the current node’s subset.

Exam traps

• $0\log 0=0$ must be stated.
• Entropy range $[0,1]$ is only for two classes.
• IG favours many-valued features.

Connections

Gain ratio (C6), Gini (C5), mutual information in NMI (C42), cross-entropy loss in logistic regression (C27).

Mastery checklist

• Compute $E$ and $IG$ by hand.
• Prove the two-class maximum at $p=\frac{1}{2}$.
• Explain the many-valued bias.
• Choose numeric thresholds.

---

C5. Gini Index and Gini Gain

Intuition

Gini measures the probability that two random draws (with replacement) from the node belong to different classes. Pure node → never different → 0.

Formal definition

For a node $X$ with proportions $p_i$: $Gini(X)=1-{\sum }_{i=1}^c{p}_i^2.$ For feature $f$ (weighted over its branches, as in the lecture): $Gini(X,f)={\sum }_v\frac{|X_v|}{|X|}Gini(X_v),GiniGain(X,f)=Gini(X)-Gini(X,f).$ Choose the feature with the smallest $Gini(X,f)$, equivalently the largest gain.

Mathematical properties

• $Gini=0$ iff pure. Maximum $1-\frac{1}{c}$ at uniform proportions (two classes: $0.5$).
• Proof of max: minimise $\sum p_i^2$ subject to $\sum p_i=1$ → Lagrange: $2p_i=\lambda$ ⇒ all $p_i$ equal $=1/c$ ⇒ $\sum p_i^2=1/c$.
• Used by CART; CART splits are binary (e.g. “Outlook = Overcast?” yes/no).

Derivation: Gini as misclassification probability

Label a random item by sampling a label from the node’s class distribution. $P(\text{wrong})={\sum }_i{p}_i(1-p_i)=\sum p_i-\sum p_i^2=1-\sum p_i^2$. ∎

Key insights

• No logarithms → cheaper than entropy.
• Tends to isolate the largest class.
• Usually ranks features like entropy, but not always (Example 5).

Worked examples

Example 1 — Very Easy

• Problem: $Gini$ of (9 Yes, 5 No).
• Asked: $Gini(X)$.
• Concept: Definition.
• Approach: $1-(p_Y^2+p_N^2)$.
• Solution: $p_Y^2=(9/14{)}^2=81/196=0.4133$; $p_N^2=25/196=0.1276$. Sum $=0.5408$. $Gini=0.4592$.
• Final answer: $0.459$.
• Key lesson: Max for two classes is $0.5$.

Example 2 — Easy

• Problem: Gini of a pure node, a 50/50 node and a 4-class uniform node.
• Asked: Three values.
• Concept: Range of Gini.
• Approach: Direct.
• Solution: Pure: $1-1=0$. 50/50: $1-(0.25+0.25)=0.5$. Uniform 4 classes: $1-4(\frac{1}{16})=0.75=1-\frac{1}{4}$.
• Final answer: $0,0.5,0.75$.
• Key lesson: Max is $1-1/c$.

Example 3 — Moderate

• Problem: Gini gain of Wind on the weather data.
• Asked: $GiniGain(X,\text{Wind})$.
• Concept: Weighted Gini.
• Approach: Use the Wind partition from C4 Ex. 3: F=(6Y,2N), T=(3Y,3N).
• Solution: $Gini(F)=1-(\frac{36}{64}+\frac{4}{64})=1-\frac{40}{64}=0.375$. $Gini(T)=0.5$. Weighted: $\frac{8}{14}(0.375)+\frac{6}{14}(0.5)=0.2143+0.2143=0.4286$. Gain $=0.4592-0.4286=0.0306$.
• Final answer: $0.031$.
• Key lesson: Same ordering of magnitude as IG (0.048).

Example 4 — Hard

• Problem: CART builds binary splits. For the categorical feature Outlook list the three binary splits ("$=v$" vs "$\ne v$") and pick the best by Gini gain.
• Asked: Best binary split.
• Concept: Binary CART split of a multi-valued feature.
• Approach: Counts: Sunny (2Y,3N), Overcast (4Y,0N), Rainy (3Y,2N).
• Solution: Overcast vs rest: Overcast Gini $0$; rest (5Y,5N) $=0.5$. Weighted $\frac{4}{14}\cdot 0+\frac{10}{14}\cdot 0.5=0.3571$. Gain $0.4592-0.3571=0.1020$. Sunny vs rest: Sunny $1-(\frac{4}{25}+\frac{9}{25})=0.48$; rest (7Y,2N): $1-\frac{49+4}{81}=0.3457$. Weighted $\frac{5}{14}(0.48)+\frac{9}{14}(0.3457)=0.1714+0.2222=0.3936$. Gain $0.0656$. Rainy vs rest: Rainy $0.48$; rest (6Y,3N): $1-\frac{36+9}{81}=0.4444$. Weighted $0.1714+0.2857=0.4571$. Gain $0.0021$.
• Final answer: “Overcast vs not Overcast” (gain 0.102).
• Key lesson: Binary-split algorithms must choose which grouping, not just which feature.

Example 5 — Very Hard

• Problem: A parent node has 15 Yes and 15 No. Split A produces children (0Y,4N) and (15Y,11N). Split B produces (3Y,9N) and (12Y,6N). Which split does information gain prefer? Which does Gini prefer? Explain.
• Asked: Two rankings.
• Concept: Entropy vs Gini disagree.
• Approach: Compute both criteria for both splits.
• Solution: Parent: $E=1$, $Gini=0.5$. Split A: child 1 pure ($E=0$, $G=0$), $n=4$. Child 2: $n=26$, $p=(\frac{15}{26},\frac{11}{26})=(0.5769,0.4231)$, $E=0.9836$, $G=1-\frac{225+121}{676}=0.4882$. Weighted $E=\frac{26}{30}(0.9836)=0.8525$ → $I{G}_A=0.1475$ (more precisely $0.1482$). Weighted $G=\frac{26}{30}(0.4882)=0.4231$ → $G{G}_A=0.0769$. Split B: child 1 $n=12$, $p=(\frac{1}{4},\frac{3}{4})$, $E=0.8113$, $G=1-\frac{9+81}{144}=0.375$; child 2 $n=18$, $p=(\frac{2}{3},\frac{1}{3})$, $E=0.9183$, $G=1-\frac{144+36}{324}=0.4444$. Weighted $E=0.4(0.8113)+0.6(0.9183)=0.3245+0.5510=0.8755$ → $I{G}_B=0.1245$. Weighted $G=0.4(0.375)+0.6(0.4444)=0.15+0.2667=0.4167$ → $G{G}_B=0.0833$. Comparison: IG: $0.148>0.125$ → A. Gini: $0.0769<0.0833$ → B.
• Final answer: Entropy prefers A; Gini prefers B.
• Key lesson: Entropy rewards carving out a small perfectly pure node more strongly than Gini. They usually agree but are not equivalent.

Common mistakes

• Using entropy’s range for Gini.
• Forgetting weights; minimising Gini gain instead of maximising it (or maximising the weighted Gini instead of minimising).

Exam traps

• “Smallest Gini index” ⇔ “largest Gini gain” — be consistent.
• Max Gini for $c$ classes is $1-1/c$, not $0.5$.

Connections

Entropy (C4), CART (C9), random forests (C10), logistic/Bernoulli variance link: for 2 classes $Gini=2p(1-p)$.

Mastery checklist

• Compute Gini and Gini gain.
• Do binary subset splits of a categorical feature.
• Explain when Gini and IG disagree.

---

C6. Gain Ratio

Intuition

Information gain loves features with many values — a Day-ID column perfectly “explains” the class by memorising each row. Gain ratio divides by how finely the feature fragments the data (its split information) to penalise that.

Formal definition

$SplitInfo(X,f)=-{\sum }_v\frac{|X_v|}{|X|}{\log }_2\frac{|X_v|}{|X|},GainRatio(X,f)=\frac{IG(X,f)}{SplitInfo(X,f)}.$ (The lecture writes the denominator as $E(X,f)$; it is the entropy of the partition sizes.) Undefined when $SplitInfo=0$ (feature has a single value).

Mathematical formulation

$SplitInfo$ is the entropy of the feature’s own value distribution; for $k$ equal-size branches it is ${\log }_{2}k$.

Derivation (why it penalises ID-like features)

For a feature with $n$ unique values in $n$ rows, $IG=E(X)$ (all children pure) but $SplitInfo={\log }_{2}n$. So $GR=E(X)/{\log }_{2}n\to 0$ as $n$ grows.

Key insights

• Used by C4.5.
• It can over-correct (favours very unbalanced splits with tiny $SplitInfo$).

Worked examples

Example 1 — Very Easy

• Problem: $SplitInfo$ of a binary split with sizes 7 and 7; of a 3-way equal split.
• Asked: Two values.
• Concept: SplitInfo.
• Approach: Entropy of proportions.
• Solution: $(\frac{1}{2},\frac{1}{2})$: $1$. Equal 3-way: $-3\cdot \frac{1}{3}{\log }_2\frac{1}{3}={\log }_{2}3=1.585$.
• Final answer: $1$ and $1.585$.
• Key lesson: More branches ⇒ larger SplitInfo.

Example 2 — Easy

• Problem: $GainRatio$ of Outlook (IG $0.2467$; branch sizes 5, 4, 5).
• Asked: GR.
• Concept: Gain ratio.
• Approach: Compute SplitInfo then divide.
• Solution: $SplitInfo=-\frac{5}{14}{\log }_2\frac{5}{14}\cdot 2-\frac{4}{14}{\log }_2\frac{4}{14}=2(0.3571)(1.4854)+0.2857(1.8074)=1.0610+0.5164=1.5774$. $GR=0.2467/1.5774=0.1564$.
• Final answer: $0.156$.
• Key lesson: The division shrinks gain by $\approx 1.6$.

Example 3 — Moderate

• Problem: Compute GR for all four weather features and rank.
• Asked: Four GRs.
• Concept: Gain ratio.
• Approach: IG and SplitInfo from branch sizes.
• Solution: Outlook: $0.2467/1.5774=0.1564$. Temperature (sizes 4,6,4; IG $0.0292$): $SplitInfo=2(\frac{4}{14})(1.8074)+\frac{6}{14}(1.2224)=1.0328+0.5239=1.5567$ → $0.0292/1.5567=0.0188$. Humidity (7,7; IG $0.1518$): $SplitInfo=1$ → $0.1518$. Wind (8,6; IG $0.0481$): $SplitInfo=\frac{8}{14}(0.8074)+\frac{6}{14}(1.2224)=0.4614+0.5239=0.9852$ → $0.0488$.
• Final answer: Outlook $0.156$ > Humidity $0.152$ > Wind $0.049$ > Temperature $0.019$.
• Key lesson: Ranking can stay the same while the gap shrinks.

Example 4 — Hard

• Problem: Add a “Day” feature with 14 distinct values to the weather data. Compute its IG, SplitInfo, GR and compare to Outlook under both criteria.
• Asked: The bias and how much GR corrects it.
• Concept: Bias of IG.
• Approach: All 14 children are singletons.
• Solution: Each child pure → weighted child entropy 0 → $IG=0.9403$. $SplitInfo=-14\cdot \frac{1}{14}{\log }_2\frac{1}{14}={\log }_{2}14=3.8074$. $GR=0.9403/3.8074=0.2470$. Under IG, Day beats Outlook $0.940$ vs $0.247$ (ratio $3.8$). Under GR, Day beats Outlook $0.247$ vs $0.156$ (ratio $1.6$).
• Final answer: GR greatly reduces but does not remove the bias; a useless ID still wins here.
• Key lesson: In practice drop identifier-like columns (or use extra heuristics), regardless of the criterion.

Example 5 — Very Hard

• Problem: Parent: 6 Yes, 6 No. Feature A has four values: three singletons each containing 1 No, and one value with (6Y, 3N). Feature B is binary: (0Y, 2N) and (6Y, 4N). Which does IG pick? Which does GR pick?
• Asked: Rankings that disagree.
• Concept: GR changes the winner.
• Approach: Compute IG, SplitInfo, GR of each.
• Solution: Parent $E=1$. A: three pure children ($E=0$, weight $\frac{1}{12}$ each); big child $n=9$: $p=(\frac{2}{3},\frac{1}{3})$, $E=0.9183$. Weighted $=\frac{9}{12}(0.9183)=0.6887$; $I{G}_A=0.3113$. $SplitInf{o}_A=3\cdot \frac{1}{12}{\log }_{2}12+\frac{9}{12}{\log }_2\frac{12}{9}=0.8962+0.3113=1.2075$; $G{R}_A=0.2578$. B: child 1 pure ($n=2$); child 2 $n=10$, $p=(0.6,0.4)$, $E=0.9710$. Weighted $=\frac{10}{12}(0.9710)=0.8091$; $I{G}_B=0.1909$. $SplitInf{o}_B=\frac{2}{12}{\log }_{2}6+\frac{10}{12}{\log }_2\frac{12}{10}=0.4308+0.2192=0.6500$; $G{R}_B=0.2937$.
• Final answer: IG picks A ($0.311>0.191$); GR picks B ($0.294>0.258$).
• Key lesson: Criteria encode different preferences: IG wants the biggest absolute purity gain; GR wants gain per unit of fragmentation.

Common mistakes

• Dividing by $E(X)$ (class entropy) instead of SplitInfo.
• Using GR when SplitInfo $=0$.

Exam traps

• GR fixes, but does not eliminate, the many-valued bias.
• C4.5 uses GR; ID3 uses IG; CART uses Gini.

Connections

C4, C9.

Mastery checklist

• Compute SplitInfo and GR.
• Explain the ID-column pathology.
• Give a case where IG and GR disagree.

---

C7. Stopping Criteria and Overfitting

Intuition

A tree can keep splitting until every training example sits in its own leaf — perfect on training data, hopeless on new data (it memorised noise). Stopping early (pre-pruning) trades some training accuracy for generalisation. Too early → underfit.

Formal definitions

• Stopping criteria: (i) maximum depth reached; (ii) all samples in the node share a class; (iii) best split score does not exceed a threshold (or too few samples).
• Overfitting (Mitchell): hypothesis $h\in H$ overfits training data if there exists $h^{\prime }\in H$ with $er{r}_{train}(h)<er{r}_{train}(h^{\prime })$ but $er{r}_{\mathcal{D}}(h)>er{r}_{\mathcal{D}}(h^{\prime })$ ($\mathcal{D}$ = true distribution).
• Pre-pruning: stop growing early. Post-pruning: grow fully, then cut (C8).

Mathematical formulation

Generalisation gap: $er{r}_{\mathcal{D}}(h)-er{r}_{train}(h)$. Overfit ⇔ gap grows while training error shrinks.

Derivation: noise makes memorisation costly

Suppose true labels are deterministic given $x$ but each observed label is flipped independently with probability $\eta$. A fully grown tree puts a test point in a leaf labelled by a (noisy) training point from the same region. Error $=P(\text{train wrong})P(\text{test right})+P(\text{train right})P(\text{test wrong})=\eta (1-\eta )+(1-\eta )\eta =2\eta (1-\eta )$, whereas a tree that learns the true label has error $\eta$ (the unavoidable noise). Since $2\eta (1-\eta )>\eta ⟺\eta <\frac{1}{2}$, memorisation is strictly worse.

Key insights

• Tight stopping ⇒ small trees ⇒ underfit; loose ⇒ big trees ⇒ overfit.
• Choose depth by validation error.

Worked examples

Example 1 — Very Easy

• Problem: Which stops a decision tree: (a) node has only Yes’s; (b) node has 5 Yes and 5 No and a feature exists; (c) max depth reached?
• Asked: Stop or continue.
• Concept: Stopping criteria.
• Approach: Check each criterion.
• Solution: (a) pure → stop. (b) impure and a split exists → continue (if no criterion fires). (c) depth limit → stop.
• Final answer: (a) stop, (b) continue, (c) stop.
• Key lesson: Pure node ⇒ leaf.

Example 2 — Easy

• Problem: Depth vs (train error, validation error): $d=1$: (0.30,0.32); $2$: (0.20,0.22); $3$: (0.10,0.15); $4$: (0.05,0.18); $5$: (0.00,0.25). Choose $d$ and identify under/overfitting.
• Asked: Best depth.
• Concept: Validation-based depth selection.
• Approach: Minimise validation error.
• Solution: Validation errors $0.32,0.22,0.15,0.18,0.25$; minimum $0.15$ at $d=3$. $d=1,2$: both errors high → underfit. $d=4,5$: train falls, validation rises → overfit.
• Final answer: $d=3$.
• Key lesson: Training error alone always prefers the deepest tree.

Example 3 — Moderate

• Problem: A node’s best split has $IG=0.004$; threshold $\theta =0.01$. The node has 40 samples (22 Yes, 18 No). What does the tree do and what is the leaf’s label and training error?
• Asked: Action, label, error.
• Concept: Threshold stopping.
• Approach: Compare IG to $\theta$; majority label.
• Solution: $0.004<0.01$ → stop. Leaf label = majority = Yes. Errors $=18$ of 40 → $0.45$.
• Final answer: Leaf “Yes”, training error $0.45$ at this node.
• Key lesson: Thresholding saves tree size at the cost of local accuracy.

Example 4 — Hard

• Problem: 10 training points; a hypothesis $h_1$ (large tree) has training error 0 and true error 0.30. $h_2$ (small tree) has training error 0.20 and true error 0.12. Does $h_1$ overfit? Which would you deploy?
• Asked: Overfit judgement.
• Concept: Mitchell’s definition.
• Approach: Test the definition with $h=h_1$, $h^{\prime }=h_2$.
• Solution: $er{r}_{train}(h_1)=0<0.20=er{r}_{train}(h_2)$ ✓; $er{r}_{\mathcal{D}}(h_1)=0.30>0.12=er{r}_{\mathcal{D}}(h_2)$ ✓. Both conditions hold ⇒ $h_1$ overfits. Deploy $h_2$.
• Final answer: Yes, $h_1$ overfits; deploy $h_2$.
• Key lesson: Overfitting is relative: it needs a better-generalising alternative in $H$.

Example 5 — Very Hard

• Problem: Labels are flipped with noise $\eta =0.10$. (a) What error does a fully grown tree achieve on new data (in the idealised leaf model)? (b) What error does the ideal pruned tree achieve? (c) For what $\eta$ is the full tree’s error $1.5\times$ the pruned tree’s?
• Asked: Two errors and a ratio solve.
• Concept: Noise and memorisation.
• Approach: Use $2\eta (1-\eta )$ vs $\eta$.
• Solution: (a) $2(0.10)(0.90)=0.18$. (b) $\eta =0.10$. (c) $2\eta (1-\eta )=1.5\eta \Rightarrow 2(1-\eta )=1.5\Rightarrow 1-\eta =0.75\Rightarrow \eta =0.25$.
• Final answer: $0.18$, $0.10$, $\eta =0.25$.
• Key lesson: Memorisation cost is $\eta (1-2\eta )$ extra error — largest near $\eta =0.25$.

Common mistakes

• Judging a tree by training accuracy.
• Equating “large tree” with “overfit” without a comparison.

Exam traps

• “Tight” stopping ⇒ underfit; “loose” ⇒ overfit.
• The definition of overfit uses true distribution error.

Connections

Pruning (C8), cross-validation (C13), 1-NN error (C23).

Mastery checklist

• List three stopping criteria.
• State Mitchell’s overfit definition.
• Derive $2\eta (1-\eta )$.

---

C8. Post-Pruning: Reduced-Error, Cost-Complexity, Error-Based

Intuition

Grow a big tree, then cut off branches that don’t earn their keep. Three ways to decide “earns its keep”.

Formal definitions

Notation: $\epsilon (T,X)$ error rate of tree $T$ on $X$; $|leaves(T)|$; $pruned(T,t)$ = $T$ with subtree at $t$ replaced by a leaf (majority class).

1. Reduced-Error Pruning (REP, Quinlan 1987). Hold out a pruning (validation) set. Bottom-up, replace node $t$ by its majority-class leaf if accuracy on the pruning set does not decrease. Stop when any further pruning would decrease accuracy.
2. Cost-Complexity Pruning (CCP, Breiman; CART). For each internal node $t$: $\alpha (t)=\frac{\epsilon (pruned(T,t),X)-\epsilon (T,X)}{|leaves(T)|-|leaves(pruned(T,t))|}.$ Prune if $\alpha <\theta$ (preset $\theta >0$). $\alpha$ = error increase per leaf removed.
3. Error-Based Pruning (EBP; C4.5). Replace the training error by an upper confidence bound: ${\epsilon }^{\prime }(T,X)=\epsilon (T,X)+Z_{\alpha }\sqrt{\frac{\epsilon (T,X)(1-\epsilon (T,X))}{|X|}}.$ Bottom-up at node $t$, compare ${\epsilon }^{\prime }$ of: (i) $subtree(T,t)$ on $X_t$; (ii) $pruned(T,t)$ on $X_t$; (iii) $subtree(T,maxchild(T,t))$ on $X_{maxchild}$. Take the minimum: keep, prune to leaf, or replace $t$ by its most-travelled child subtree.

Derivation: where EBP’s formula comes from

$\hat{\epsilon }$ from $N$ samples is approximately normal with mean $\epsilon$ and standard error $\sqrt{\epsilon (1-\epsilon )/N}$ (binomial). The one-sided $(1-\alpha )$ upper bound is mean $+z\cdot$ s.e. A tiny node has a large s.e., so its estimated error is inflated: small nodes are distrusted. For $\alpha =0.05$ (one-sided), $Z_{\alpha }=1.645$.

Key insights

• REP needs held-out data (or cross-validation).
• CCP’s $\alpha$ makes a size-versus-error trade-off explicit: small $\alpha$ ⇒ branch barely helps ⇒ prune.
• EBP needs no separate pruning set.

Worked examples

Example 1 — Very Easy

• Problem (REP): At node $t$, the pruning set has 20 samples reaching $t$; the subtree misclassifies 5 and the majority leaf misclassifies 5. Prune?
• Asked: Decision.
• Concept: REP rule “does not reduce accuracy”.
• Approach: Compare errors.
• Solution: Accuracy with subtree $=15/20$; with leaf $=15/20$. Not reduced → prune.
• Final answer: Prune.
• Key lesson: Ties prune (simpler wins).

Example 2 — Easy

• Problem (CCP): Subtree at $t$ has 4 leaves. $\epsilon (T)=0.05$, $\epsilon (pruned(T,t))=0.08$. Threshold $\theta =0.02$. Prune?
• Asked: $\alpha$ and decision.
• Concept: $\alpha$ formula.
• Approach: Leaves removed $=4-1=3$.
• Solution: $\alpha =\frac{0.08-0.05}{3}=0.01$. $0.01<0.02$ → prune.
• Final answer: $\alpha =0.01$, prune.
• Key lesson: Denominator is leaves removed, not 4.

Example 3 — Moderate

• Problem (EBP): A node has $|X_t|=100$, training error $\epsilon =0.10$. With $Z=1.645$ find ${\epsilon }^{\prime }$.
• Asked: Upper bound.
• Concept: EBP formula.
• Approach: Substitute.
• Solution: $\sqrt{\frac{0.10\cdot 0.90}{100}}=\sqrt{0.0009}=0.03$. ${\epsilon }^{\prime }=0.10+1.645(0.03)=0.10+0.04935=0.1494$.
• Final answer: ${\epsilon }^{\prime }\approx 0.149$.
• Key lesson: The pessimistic estimate exceeds the raw error.

Example 4 — Hard

• Problem (CCP ordering): Tree $T$: $\epsilon (T)=0.04$, 9 leaves. Candidate nodes: $t_1$: subtree has 3 leaves, pruning gives error $0.07$; $t_2$: 2 leaves, pruning gives $0.05$; $t_3$: 4 leaves, pruning gives $0.10$. Compute each $\alpha$ and the pruning order; with $\theta =0.015$ which are pruned (considered independently)?
• Asked: $\alpha$‘s, order, set.
• Concept: Weakest-link idea.
• Approach: $\alpha =\Delta \epsilon /\Delta leaves$.
• Solution: $t_1$: $(0.07-0.04)/(3-1)=0.015$. $t_2$: $(0.05-0.04)/(2-1)=0.010$. $t_3$: $(0.10-0.04)/(4-1)=0.020$. Order (smallest first): $t_2<t_1<t_3$. With $\theta =0.015$ and the rule "$\alpha <\theta$": $t_2$ ($0.010<0.015$) pruned; $t_1$ ($0.015$, not strictly less) kept; $t_3$ kept.
• Final answer: $\alpha =(0.015,0.010,0.020)$; only $t_2$ is pruned.
• Key lesson: Strict inequality matters at the boundary; also $\alpha$ must be recomputed after each prune in a full CCP sequence.

Example 5 — Very Hard

• Problem (EBP three-way): Node $t$ has $|X_t|=100$. $subtree(T,t)$ has $\epsilon =0.06$ on $X_t$. $pruned(T,t)$ (leaf) has $\epsilon =0.06$ on $X_t$. $maxchild$ receives 40 of the 100 samples; its subtree has $\epsilon =0.025$ on those 40. With $Z=1.645$ choose the action.
• Asked: Keep / prune / replace by maxchild.
• Concept: EBP comparison.
• Approach: Compute three ${\epsilon }^{\prime }$.
• Solution: (i) $\sqrt{0.06\cdot 0.94/100}=\sqrt{0.000564}=0.02375$; ${\epsilon }^{\prime }=0.06+1.645(0.02375)=0.06+0.03907=0.0991$. (ii) leaf: same $\epsilon$ and $n$ → $0.0991$. (iii) $\sqrt{0.025\cdot 0.975/40}=\sqrt{0.000609}=0.02469$; ${\epsilon }^{\prime }=0.025+1.645(0.02469)=0.025+0.04061=0.0656$. Minimum is (iii).
• Final answer: Replace $t$ by its maxchild subtree.
• Key lesson: EBP is a three-way decision; the third option can win because a narrower subtree has lower observed error, even though its bound uses a smaller $n$.

Common mistakes

• Using the number of leaves in $T$ (not the number removed) in $\alpha$.
• Pruning using the training set in REP.
• Treating ${\epsilon }^{\prime }$ as a probability estimate rather than an upper bound.

Exam traps

• REP: “does not reduce accuracy” (ties prune).
• CCP rule is prune if $\alpha <\theta$.
• EBP compares three values.

Connections

Overfitting (C7), cross-validation (C13), CART/C4.5 (C9).

Mastery checklist

• Apply each of the three pruning rules.
• Derive the EBP bound.
• Order nodes by $\alpha$.

---

C9. ID3, C4.5, CART; Merits and Limits of Decision Trees

Intuition

All three algorithms grow a tree greedily top-down: choose the best split, recurse, never backtrack. They differ in score, branching, numeric/missing support and pruning.

Comparison

	ID3 (Quinlan 1986)	C4.5 (Quinlan 1993)	CART (Breiman 1984)
Split score	Information gain	Gain ratio	Gini index
Branching	Multiway on categorical	Multiway	Binary
Stopping	all one class, or best IG $\le 0$	too few samples to split	—
Pruning	none	error-based pruning	cost-complexity pruning
Numeric / missing	No	Yes	Yes
Regression	No	No	Yes

Merits (lecture)

Handles nominal & numeric features; non-parametric (no distribution assumption); can handle missing values; interpretable — a tree is a rule set.

Limits (lecture)

Optimal tree learning is NP-hard/NP-complete → greedy heuristics; sensitive to training set, noise, irrelevant features; ID3 needs discrete targets.

The two trees in the lecture’s figures

Figure 3.3 (checked against the PDF) is a larger tree that tests Temperature under Sunny and Rainy and has “No Instance” leaves — it was built without choosing by information gain; Figure 3.5 is the compact IG-based tree below (root Outlook; Sunny → Humidity; Overcast → Yes; Rainy → Wind). The lecture’s point: IG yields a smaller and shallower tree for the same data.

Derivation: tree ⇒ rules

Each root-to-leaf path is a conjunction of conditions; the leaf gives the class. The tree of the weather data (IG-based) yields five rules:

1. Outlook=Sunny ∧ Humidity=High → No
2. Outlook=Sunny ∧ Humidity=Normal → Yes
3. Outlook=Overcast → Yes
4. Outlook=Rainy ∧ Wind=True → No
5. Outlook=Rainy ∧ Wind=False → Yes

Worked examples

Example 1 — Very Easy

• Problem: Which algorithm uses Gini? Gain ratio? Information gain?
• Asked: Match.
• Concept: Comparison table.
• Approach: Recall.
• Solution: CART–Gini; C4.5–gain ratio; ID3–information gain.
• Final answer: As stated.
• Key lesson: Memorise the triple.

Example 2 — Easy

• Problem: Classify the day (Sunny, Cool, High, True) with the weather tree and compute the tree’s training accuracy.
• Asked: Prediction and accuracy.
• Concept: Tree traversal.
• Approach: Follow the rules.
• Solution: Outlook=Sunny → test Humidity=High → rule 1 → No. Training check: Sunny/High rows 1,2,8 → all N ✓; Sunny/Normal rows 9,11 → Y,Y ✓; Overcast rows 3,7,12,13 → all Y ✓; Rainy/Wind=T rows 6,14 → N,N ✓; Rainy/Wind=F rows 4,5,10 → Y,Y,Y ✓. All $14/14$.
• Final answer: No; training accuracy $100\%$.
• Key lesson: Fully grown trees fit training data exactly (consistent data).

Example 3 — Moderate

• Problem: Choose the algorithm: (a) numeric features with missing values, categorical target; (b) predicting a numeric target with binary splits; (c) a small, purely categorical dataset with no missing values where simplicity is desired.
• Asked: Algorithm per scenario.
• Concept: Capabilities.
• Approach: Use the table.
• Solution: (a) needs numeric+missing support → C4.5. (b) regression + binary → CART. (c) ID3 suffices.
• Final answer: (a) C4.5, (b) CART, (c) ID3.
• Key lesson: Match algorithm to data type.

Example 4 — Hard

• Problem: Compare the root choice of ID3 (IG) and CART (binary Gini) for the weather data and count the leaves each would produce for the root split (before further splitting).
• Asked: Root splits.
• Concept: Split criteria and branching.
• Approach: From C4 and C5: IG picks Outlook (0.247); CART’s best binary Gini split is “Outlook = Overcast?” (gain 0.102, from C5 Ex. 4); check Humidity/Wind binary gains are lower: Humidity (H=(3Y,4N),N=(6Y,1N)): $G_H=1-\frac{9+16}{49}=0.4898$, $G_N=1-\frac{36+1}{49}=0.2449$; weighted $0.3673$; gain $0.0918$ < 0.102. So CART also starts on Outlook but as a binary split.
• Solution: ID3: 3 children (S,O,R). CART: 2 children (Overcast, not Overcast); the latter child (5Y,5N) is then split further.
• Final answer: Same feature, different branching: ID3 3-way; CART 2-way.
• Key lesson: Branching factor changes tree shape, not necessarily the feature.

Example 5 — Very Hard

• Problem: Eight points $(x_1,x_2,x_3\mid y)$ with $y=x_1\oplus x_2$ and $x_3$ irrelevant: $(0,0,0|0),(0,0,1|0),(0,1,0|1),(0,1,1|1),(1,0,0|1),(1,0,1|1),(1,1,0|0),(1,1,1|0)$. Run ID3. What happens, and what is the best tree?
• Asked: ID3’s tree vs optimal.
• Concept: Greedy one-step look-ahead fails on XOR.
• Approach: Compute IG of all features at the root.
• Solution: Class counts: 4 Yes(1), 4 No(0) → $E=1$. $x_1$: $x_1=0$ rows have $y=0,0,1,1$ → $E=1$; $x_1=1$ rows $y=1,1,0,0$ → $E=1$. Weighted $=1$, $IG=0$. $x_2$: same, $IG=0$. $x_3$: $x_3=0$ rows $y=0,1,1,0$ → $E=1$; $x_3=1$ rows $y=0,1,1,0$ → $E=1$; $IG=0$. All gains are $0$: ID3’s stopping rule (“best IG not greater than zero”) fires → single leaf with a tie, accuracy $50\%$. Optimal: split $x_1$ then $x_2$ → 4 leaves, accuracy $100\%$.
• Final answer: ID3 returns a one-leaf tree (50 %); the depth-2 tree on $x_1,x_2$ is perfect.
• Key lesson: Greedy splitting cannot see interactions; a feature useless alone may be essential in combination (random forests and deeper lookahead partially help).

Common mistakes

• Saying C4.5 uses Gini or ID3 uses gain ratio.
• Believing greedy trees are optimal.

Exam traps

• ID3: no pruning, no numeric, no missing values.
• CART is binary; Gini is its splitting measure (the lecture’s “Gini index is used to prune” is a slip: CART prunes by cost-complexity).

Connections

C4–C8, C10.

Mastery checklist

• Fill the comparison table from memory.
• Convert a tree to rules.
• Give the XOR failure example.

---

C10. Random Forest

Intuition

One tree is unstable: change a few training rows and the tree changes a lot (high variance). Average many different trees and the instabilities cancel. To make the trees different, each sees a bootstrap resample of rows and, at each split, only a random subset of features.

Formal algorithm (lecture)

For $b=1,\dots ,B$:

1. Draw a bootstrap sample $Z_b$ of size $Z$ with replacement from the training set $X$.
2. Grow a tree on $Z_b$: at each node pick $V$ ($=m$) features at random from all features $F$; choose the best split among those by a criterion (e.g. Gini); split.
3. Predict a test sample by majority vote of the $B$ trees. Default $m=\sqrt{|F|}$. Out-of-bag (OOB) samples = those not drawn for a tree; the error on them is the OOB error, a built-in generalisation estimate.

Mathematical formulation

• Probability a given row is not in a bootstrap sample of size $n$: $(1-\frac{1}{n}{)}^n\stackrel{n\to \infty }{\to }{e}^{-1}\approx 0.368$.
• Variance of the average of $B$ identically distributed trees with pairwise correlation $\rho$ and variance ${\sigma }^2$: $\mathrm{Var}\left(\frac{1}{B}{\sum }_b{T}_b\right)=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2.$

Derivation of the variance formula

$\mathrm{Var}(\frac{1}{B}\sum T_b)=\frac{1}{B^2}[{\sum }_b\mathrm{Var}(T_b)+{\sum }_{b\ne b^{\prime }}\mathrm{Cov}(T_b,T_{b^{\prime }})]=\frac{1}{B^2}[B{\sigma }^2+B(B-1)\rho {\sigma }^2]=\frac{{\sigma }^2}{B}+\frac{(B-1)}{B}\rho {\sigma }^2=\rho {\sigma }^2+\frac{(1-\rho ){\sigma }^2}{B}$. ∎ (This is a standard result, not stated in the lecture; it explains why decorrelating trees via feature subsampling helps.)

Key insights

• More trees never overfit more, but the variance floor is $\rho {\sigma }^2$.
• Feature subsampling lowers $\rho$.
• Costs: interpretability is lost compared with one tree.

Worked examples

Example 1 — Very Easy

• Problem: A dataset has 16 features. What is the default number of features tried per split?
• Asked: $m$.
• Concept: $m=\sqrt{|F|}$.
• Approach: Square root.
• Solution: $\sqrt{16}=4$.
• Final answer: 4.
• Key lesson: Subset size is a fixed small number.

Example 2 — Easy

• Problem: Five trees vote for a test sample: Yes, No, Yes, Yes, No. Output?
• Asked: Majority class.
• Concept: Majority voting.
• Approach: Count.
• Solution: Yes: 3, No: 2.
• Final answer: Yes.
• Key lesson: Use an odd $B$ for two classes to avoid ties.

Example 3 — Moderate

• Problem: With $n=10$ rows, find the probability a given row is out-of-bag for one tree, the expected number of distinct rows in one bootstrap sample, and the limit as $n\to \infty$.
• Asked: Three quantities.
• Concept: Bootstrap sampling.
• Approach: $(1-1/n{)}^n$.
• Solution: $(0.9{)}^{10}=0.3487$. Expected distinct $=n(1-0.3487)=6.513$. Limit $e^{-1}=0.3679$.
• Final answer: $0.349$; $6.51$ rows; $0.368$.
• Key lesson: About one third of the data is free validation data for each tree.

Example 4 — Hard

• Problem: Each tree is independently correct with probability $0.6$. Find the probability that a majority vote of $B$ trees is correct for $B=1,3,5$.
• Asked: Three probabilities.
• Concept: Why ensembles help (independence idealisation).
• Approach: Binomial tail.
• Solution: $B=1$: $0.6$. $B=3$: need $\ge 2$: $\left(\genfrac{}{}{0ex}{}{3}{2}\right)(0.6{)}^2(0.4)+(0.6{)}^3=3(0.36)(0.4)+0.216=0.432+0.216=0.648$. $B=5$: need $\ge 3$: $\left(\genfrac{}{}{0ex}{}{5}{3}\right)(0.6{)}^3(0.4{)}^2+\left(\genfrac{}{}{0ex}{}{5}{4}\right)(0.6{)}^4(0.4)+(0.6{)}^5=10(0.216)(0.16)+5(0.1296)(0.4)+0.07776=0.3456+0.2592+0.07776=0.6826$.
• Final answer: $0.600,0.648,0.683$.
• Key lesson: Voting improves accuracy — if errors are (nearly) independent, which is what feature subsampling tries to achieve.

Example 5 — Very Hard

• Problem: Each tree has variance ${\sigma }^2=4$. Compute the variance of the forest average for ($\rho =0.5$, $B=10$), ($\rho =0.5$, $B\to \infty$), and ($\rho =0.1$, $B=10$). What does it say about feature subsampling?
• Asked: Three variances.
• Concept: Variance of correlated averages.
• Approach: Use the derived formula.
• Solution: (i) $0.5(4)+\frac{0.5(4)}{10}=2+0.2=2.2$. (ii) $B\to \infty$: $2$. (iii) $0.1(4)+\frac{0.9(4)}{10}=0.4+0.36=0.76$.
• Final answer: $2.2,2.0,0.76$.
• Key lesson: Adding trees only shrinks the $\frac{1-\rho }{B}$ term; reducing $\rho$ lowers the floor — the reason random forests restrict features at each split.

Common mistakes

• Using the same bootstrap sample for every tree (then all trees equal if no feature randomness).
• Sampling without replacement.
• Believing forests are interpretable like a single tree.

Exam traps

• OOB samples are the ones left out; OOB error needs no separate validation set.
• The feature subset is redrawn at every node, not per tree.

Connections

Trees (C4–C9), bias–variance, bagging, cross-validation (C13).

Mastery checklist

• Write the algorithm.
• Compute OOB fraction.
• State the variance formula and its implication.