02_Decision_Trees_and_Random_Forests

Module 1 — Decision Trees and Random Forests

Source: Lec 3–4 — Decision Tree and Random Forest Classifiers. · Prev: 01_Foundations · Next: Module 2 — Evaluation · Index: 00_INDEX_and_Coverage

The running dataset — "Should the club hold practice today?"

Quinlan’s weather data, 14 days. Features: Outlook $\in \{S,O,R\}$ (Sunny, Overcast, Rainy), Temperature $\in \{H,M,C\}$, Humidity $\in \{H,N\}$, Wind $\in \{F,T\}$ (False / True). Class Play $\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 in the source

The lecture prints "$E(X)=-\frac{9}{5}{\log }_2\frac{9}{5}-\frac{9}{14}{\log }_2\frac{9}{14}$" — a typo. Correct: $-\frac{9}{14}{\log }_2\frac{9}{14}-\frac{5}{14}{\log }_2\frac{5}{14}=0.940$. The “gain ratio” denominator written $E(X,f)$ is the split information (C6). Both are corrected below.

Python helpers — run this block once, the checks below reuse it

from math import log2, sqrt, comb
# a node is a tuple of class counts, e.g. (9, 5) = 9 Yes, 5 No
H = lambda *c: -sum(x/sum(c) * log2(x/sum(c)) for x in c if x)     # entropy
G = lambda *c: 1 - sum((x/sum(c))**2 for x in c)                   # Gini
def gain(f, parent, kids):                                         # f = H or G
    n = sum(map(sum, kids))
    return f(*parent) - sum(sum(k)/n * f(*k) for k in kids)
split_info = lambda *sizes: H(*sizes)                              # entropy of the branch sizes

---

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 the mixing. Pick the question that reduces it most — like playing 20 Questions and always asking the most informative one first.

 E(p)
 1.0 |            ****
     |         ***    ***
 0.5 |      ***          ***
     |    **                **
 0.0 +---*--------------------*--→ p (share of Yes)
     0          0.5           1

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 · Inspecting a batch of parts

• Problem: Compute $E$ for a batch of 8 parts: (a) 8 pass and 0 fail; (b) 4 pass and 4 fail; (c) 1 pass and 3 fail.
• Asked: Three entropies.
• Concept: Entropy definition.
• Approach: Insert proportions.
• Solution: (a) $p=(1,0)$: $-1{\log }_{2}1-0{\log }_{2}0=0$. (b) $p=(\frac{1}{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. A batch where you can already guess the outcome carries no surprise.

Example 2 — Easy · Entropy of the weather data

• 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}=-0.6374$; ${\log }_2\frac{5}{14}=-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 · Does wind matter?

• 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.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$.

Python check

print(H(9, 5))                                  # 0.9403
print(gain(H, (9, 5), [(6, 2), (3, 3)]))        # 0.0481   Wind = F / T

Key lesson

A tiny gain means the feature barely separates the classes.

Example 4 — Hard · The next split inside the Sunny branch

• 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)=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 $=0.4$. $IG=0.571$.
  • Humidity: High = rows 1,2,8 (all N) $E=0$; Normal = rows 9,11 (all 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 $=0.9510$. $IG=0.020$.
• Final answer: Split Sunny on Humidity (IG 0.971 — a perfect split).

Python check

sunny = (2, 3)
print(gain(H, sunny, [(0,2), (1,1), (1,0)]))    # temperature  0.571
print(gain(H, sunny, [(0,3), (2,0)]))           # humidity     0.971
print(gain(H, sunny, [(1,2), (1,1)]))           # wind         0.020

Key lesson

The best feature depends on the node; recompute gains on the subset.

Example 5 — Very Hard · Where to cut a temperature scale

• Problem: A club records the temperature band $x=1,\dots ,8$ (cold → hot) and whether the match was played: $N,N,Y,Y,Y,N,N,N$ (too cold and too hot are both bad). 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=0.5306+0.4238=0.9544$.

$t$	left	right	IG
1.5	N	3Y 4N	0.092
2.5	NN	3Y 3N	0.204
3.5	1Y 2N	2Y 3N	0.003
4.5	2Y 2N	1Y 3N	0.049
5.5	3Y 2N ($E=0.971$)	NNN ($E=0$)	0.348
6.5	3Y 3N	NN	0.204
7.5	3Y 4N	N	0.092

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$.

Python check

y = "NNYYYNNN"
for t in range(1, 8):                       # cut after x = t  ->  threshold t + 0.5
    L, R = y[:t], y[t:]
    kids = [(L.count("Y"), L.count("N")), (R.count("Y"), R.count("N"))]
    print(t + 0.5, round(gain(H, (3, 5), kids), 4))

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 is 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 · Gini of the weather data

• Problem: $Gini$ of (9 Yes, 5 No).
• Asked: $Gini(X)$.
• Concept: Definition.
• Approach: $1-(p_Y^2+p_N^2)$.
• Solution: $p_Y^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 · Range of Gini

• 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$, not $0.5$.

Example 3 — Moderate · Gini gain of Wind

• 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+4}{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$.

Python check

print(G(9, 5), gain(G, (9, 5), [(6, 2), (3, 3)]))   # 0.4592  0.0306

Key lesson

Same ordering of magnitude as IG (0.048): the two criteria agree on “Wind is weak”.

Example 4 — Hard · CART’s binary grouping of Outlook

• 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.102$.
  • Sunny vs rest: Sunny $0.48$; rest (7Y,2N) $=0.3457$. Weighted $0.1714+0.2222=0.3936$. Gain $0.066$.
  • Rainy vs rest: Rainy $0.48$; rest (6Y,3N) $=0.4444$. Weighted $0.1714+0.2857=0.4571$. Gain $0.002$.
• Final answer: “Overcast vs not Overcast” (gain 0.102).

Python check

for name, a, b in [("Overcast", (4,0), (5,5)), ("Sunny", (2,3), (7,2)), ("Rainy", (3,2), (6,3))]:
    print(name, round(gain(G, (9, 5), [a, b]), 4))      # 0.102  0.0655  0.002

Key lesson

Binary-split algorithms must choose which grouping, not just which feature.

Example 5 — Very Hard · Entropy and Gini disagree

• Problem: A fraud-screening node has 15 fraud and 15 legitimate cases. Rule A produces children (0 fraud, 4 legit) and (15 fraud, 11 legit). Rule B produces (3 fraud, 9 legit) and (12 fraud, 6 legit). Which rule 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 ($n=4$). Child 2: $n=26$, $p=(0.5769,0.4231)$, $E=0.9836$, $G=0.4882$. Weighted $E=\frac{26}{30}(0.9836)=0.8525$ → $I{G}_A=0.148$. 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=0.375$; child 2 $n=18$, $p=(\frac{2}{3},\frac{1}{3})$, $E=0.9183$, $G=0.4444$. Weighted $E=0.8755$ → $I{G}_B=0.1245$. Weighted $G=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.

	IG	Gini gain	Winner
Split A (tiny pure child)	0.148	0.077	entropy
Split B (two moderately pure children)	0.125	0.083	Gini

Python check

A = [(0, 4), (15, 11)]; B = [(3, 9), (12, 6)]
for name, f in [("entropy", H), ("gini", G)]:
    print(name, round(gain(f, (15, 15), A), 4), round(gain(f, (15, 15), B), 4))
# entropy 0.1482 0.1245  -> A    |    gini 0.0769 0.0833  -> 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); for 2 classes $Gini=2p(1-p)$, the Bernoulli variance ×2.

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 · How fragmented is the split?

• 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 · Gain ratio of Outlook

• Problem: $GainRatio$ of Outlook (IG $0.2467$; branch sizes 5, 4, 5).
• Asked: GR.
• Concept: Gain ratio.
• Approach: Compute SplitInfo then divide.
• Solution: $SplitInfo=2\cdot \frac{5}{14}(1.4854)+\frac{4}{14}(1.8074)=1.0610+0.5164=1.5774$. $GR=0.2467/1.5774=0.1564$.
• Final answer: $0.156$.

Key lesson

The division shrinks the gain by $\approx 1.6$.

Example 3 — Moderate · Rank all four weather features

• Problem: Compute GR for all four weather features and rank.
• Asked: Four GRs.
• Concept: Gain ratio.
• Approach: IG and SplitInfo from branch sizes.
• Solution:

Feature	branch sizes	IG	SplitInfo	GR
Outlook	5, 4, 5	0.2467	1.5774	0.156
Humidity	7, 7	0.1518	1.0000	0.152
Wind	8, 6	0.0481	0.9852	0.049
Temperature	4, 6, 4	0.0292	1.5567	0.019

• Final answer: Outlook $0.156$ > Humidity $0.152$ > Wind $0.049$ > Temperature $0.019$.

Python check

for name, ig_, sizes in [("Outlook", .2467, (5,4,5)), ("Humidity", .1518, (7,7)),
                         ("Wind", .0481, (8,6)), ("Temperature", .0292, (4,6,4))]:
    print(name, round(split_info(*sizes), 4), round(ig_ / split_info(*sizes), 4))

Key lesson

Ranking can stay the same while the gap shrinks (0.247 vs 0.152 becomes 0.156 vs 0.152).

Example 4 — Hard · A useless “Day” column

• 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={\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 add extra heuristics), regardless of the criterion.

Example 5 — Very Hard · IG and GR choose different winners

• Problem: Parent: 6 Yes, 6 No. Feature A (say, postcode) 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 (weight $\frac{1}{12}$ each); big child $n=9$: $p=(\frac{2}{3},\frac{1}{3})$, $E=0.9183$. Weighted $=0.6887$; $I{G}_A=0.3113$. $SplitInf{o}_A=1.2075$; $G{R}_A=0.2578$.
  • B: child 1 pure ($n=2$); child 2 $n=10$, $E=0.9710$. Weighted $=0.8091$; $I{G}_B=0.1909$. $SplitInf{o}_B=0.6500$; $G{R}_B=0.2937$.
• Final answer: IG picks A ($0.311>0.191$); GR picks B ($0.294>0.258$).

Python check

A = [(0,1), (0,1), (0,1), (6,3)]; B = [(0,2), (6,4)]
for kids in (A, B):
    g = gain(H, (6, 6), kids); s = split_info(*[sum(k) for k in kids])
    print(round(g, 4), round(s, 4), round(g / s, 4))   # A: .3113 1.2075 .2578   B: .1909 .65 .2936

Key lesson

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. Stop too early and you underfit.

 error
  |  \                         validation
  |   \                      /
  |    \          __________/      ← overfit zone: train ↓, validation ↑
  |     \________/
  |      train \________________
  +----------------------------→ tree depth
      underfit   sweet spot   overfit

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 · Stop or split?

• 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 · Choosing the depth

• 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 · A weak split below threshold

• 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 · Does the big tree overfit?

• 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 · Noisy labels

• Problem: A survey form is mis-transcribed so labels are flipped with noise $\eta =0.10$. (a) What error does a fully grown tree achieve on new data (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 \eta =0.25$.
• Final answer: $0.18$, $0.10$, $\eta =0.25$.

Python check

import numpy as np
eta = np.linspace(0.01, 0.49, 49)
extra = 2*eta*(1-eta) - eta                   # = eta(1 - 2 eta)
print(2*0.1*0.9, eta[extra.argmax()])         # 0.18  0.25

Key lesson

Memorisation costs $\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”.

flowchart LR
    A[Grow full tree] --> B{Pruning rule}
    B -->|held-out set| REP[REP<br/>prune if accuracy does not drop]
    B -->|size vs error| CCP["CCP<br/>prune if α < θ"]
    B -->|pessimistic bound| EBP[EBP<br/>keep · leaf · maxchild]

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 · REP on one node

• 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 · One CCP decision

• 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

The denominator is leaves removed (3), not 4.

Example 3 — Moderate · Pessimistic error

• 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}}=0.03$. ${\epsilon }^{\prime }=0.10+1.645(0.03)=0.1494$.
• Final answer: ${\epsilon }^{\prime }\approx 0.149$.

Key lesson

The pessimistic estimate exceeds the raw error.

Example 4 — Hard · Ordering nodes by α

• 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 rule "$\alpha <\theta$" and $\theta =0.015$: $t_2$ 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. In a full CCP sequence, $\alpha$ must be recomputed after each prune.

Example 5 — Very Hard · EBP three-way choice

• 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}=0.02375$; ${\epsilon }^{\prime }=0.06+1.645(0.02375)=0.0991$. (ii) leaf: same $\epsilon$ and $n$ → $0.0991$. (iii) $\sqrt{0.025\cdot 0.975/40}=0.02469$; ${\epsilon }^{\prime }=0.025+1.645(0.02469)=0.0656$. Minimum is (iii).
• Final answer: Replace $t$ by its maxchild subtree.

Python check

ebp = lambda e, n, z=1.645: e + z * sqrt(e * (1 - e) / n)
print(ebp(.06, 100), ebp(.06, 100), ebp(.025, 40))   # 0.0991  0.0991  0.0656

Key lesson

EBP is a three-way decision; option (iii) 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 and 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 tree for the weather data (IG-based, Figure 3.5)

Figure 3.3 in the lecture 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. The lecture’s point: IG yields a smaller and shallower tree for the same data.

flowchart TD
    O{Outlook}
    O -->|Sunny| H{Humidity}
    O -->|Overcast| Y1([Yes])
    O -->|Rainy| W{Wind}
    H -->|High| N1([No])
    H -->|Normal| Y2([Yes])
    W -->|True| N2([No])
    W -->|False| Y3([Yes])

Derivation: tree ⇒ rules

Each root-to-leaf path is a conjunction of conditions; the leaf gives the class. The IG-based weather tree 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 · Match algorithm to score

• 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: ID3 – IG, C4.5 – GR, CART – Gini.

Example 2 — Easy · Classify a day and check training accuracy

• 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 consistent training data exactly.

Example 3 — Moderate · Pick the right tool

• Problem: Choose the algorithm: (a) numeric features with missing values, categorical target; (b) predicting a numeric target (e.g. house price) 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) numeric + missing support → C4.5. (b) regression + binary → CART. (c) ID3 suffices.
• Final answer: (a) C4.5, (b) CART, (c) ID3.

Key lesson

Match the algorithm to the data type.

Example 4 — Hard · Root splits: ID3 vs CART

• Problem: Compare the root choice of ID3 (IG) and CART (binary Gini) for the weather data and count the children each produces at the root split.
• 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 the binary Humidity split: High=(3Y,4N), Normal=(6Y,1N): $G_H=0.4898$, $G_N=0.2449$; weighted $0.3673$; gain $0.0918<0.102$.
• Solution: ID3: 3 children (S, O, R). CART: 2 children (Overcast, not Overcast); the latter (5Y,5N) is then split further.
• Final answer: Same feature, different branching: ID3 3-way; CART 2-way.

Python check

print(gain(G, (9, 5), [(3, 4), (6, 1)]))     # Humidity binary: 0.0918  < Overcast-vs-rest 0.102

Key lesson

Branching factor changes tree shape, not necessarily the feature chosen.

Example 5 — Very Hard · The XOR trap

• 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$: both children $y=0,1,1,0$ → $E=1$; $IG=0$. All gains are $0$: ID3’s stopping rule (“best IG not greater than zero”) fires → a single leaf, accuracy $50\%$. Optimal: split $x_1$ then $x_2$ → 4 leaves, accuracy $100\%$.

        x1 = 0           x1 = 1
 x2=0:    0               1
 x2=1:    1               0      ← y = XOR; no single feature separates classes

• Final answer: ID3 returns a one-leaf tree (50 %); the depth-2 tree on $x_1,x_2$ is perfect.

Python check

rows = [(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)]
for j in range(3):
    kids = [(sum(r[3] for r in rows if r[j] == v), sum(1 - r[3] for r in rows if r[j] == v)) for v in (0, 1)]
    print(f"x{j+1}", gain(H, (4, 4), kids))      # 0.0 for every feature

Key lesson

Greedy splitting cannot see interactions: a feature useless alone may be essential in combination. Random forests and deeper lookahead only partly 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 — like asking a panel of doctors instead of one. To make the trees different, each sees a bootstrap resample of rows and, at each split, only a random subset of features.

flowchart LR
    X[(Training set X)] --> B1[Bootstrap 1] --> T1[Tree 1]
    X --> B2[Bootstrap 2] --> T2[Tree 2]
    X --> B3[Bootstrap B] --> T3[Tree B]
    T1 --> V{{Majority vote}}
    T2 --> V
    T3 --> V
    V --> P[Prediction]

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}$. ∎ (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$.
• Cost: interpretability is lost compared with one tree.

Worked examples

Example 1 — Very Easy · Features per split

• 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

The subset size is a fixed small number, not a fraction of the data.

Example 2 — Easy · A vote

• 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 · How much is out-of-bag?

• 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$.

Python check

import numpy as np
print(0.9**10, 10 * (1 - 0.9**10), np.exp(-1))      # 0.3487  6.513  0.3679
rng = np.random.default_rng(0)
print(np.mean([len(set(rng.integers(0, 10, 10))) for _ in range(20000)]))   # ≈ 6.51

Key lesson

About one third of the data is free validation data for each tree.

Example 4 — Hard · A panel of 60 %-accurate doctors

• Problem: Each of $B$ independent diagnostic trees is correct with probability $0.6$. Find the probability that a majority vote 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$: $3(0.36)(0.4)+0.216=0.648$. $B=5$: need $\ge 3$: $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$.

Python check

maj = lambda B, p=.6: sum(comb(B, k) * p**k * (1-p)**(B-k) for k in range(B//2 + 1, B + 1))
print([round(maj(B), 4) for B in (1, 3, 5, 25, 101)])   # 0.6  0.648  0.6826  0.8462  0.9791

Key lesson

Voting improves accuracy — if errors are (nearly) independent, which is what feature subsampling tries to achieve.

Example 5 — Very Hard · Correlation sets the floor

• 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.2$. (ii) $B\to \infty$: $2$. (iii) $0.1(4)+\frac{0.9(4)}{10}=0.76$.
• Final answer: $2.2,2.0,0.76$.

$\rho$	$B$	Var
0.5	10	2.2
0.5	∞	2.0 (floor)
0.1	10	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.
• 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.