COMP5318 — Week 5 Supplement
Mathematical Foundations
Impurity measures for decision trees, information gain, Gini, and the probability logic behind bagging, Random Forests, and boosting.
How trees decide where to split
A decision tree wants child nodes that are purer than the parent. Week 5 presents two main impurity measures: entropy and Gini. Both are zero when a node contains only one class and larger when the classes are mixed.
Entropy and information gain
\[ H(S)=-\sum_k p_k \log_2 p_k \]
If attribute \(A\) splits \(S\) into child subsets \(S_1,\dots,S_r\), then the remaining entropy is
\[ H(S\mid A)=\sum_{j=1}^r \frac{|S_j|}{|S|}H(S_j) \]
Information gain is
\[ \operatorname{Gain}(S,A)=H(S)-H(S\mid A) \]
Gini impurity
\[ G(S)=1-\sum_k p_k^2=\sum_k p_k(1-p_k) \]
Lower is better. A split is good when the weighted average Gini of the children is much smaller than the parent Gini.
Worked Example 1: entropy and information gain
Use the tutorial dataset of 8 examples with class labels \(+\) and \(-\): five positives and three negatives.
Parent entropy
\[ H(S)=I\left(\frac{5}{8},\frac{3}{8}\right) =-\frac{5}{8}\log_2\frac{5}{8}-\frac{3}{8}\log_2\frac{3}{8} \approx 0.95 \]
This is the impurity before any split.
Split on shape
The child entropies from the tutorial solution are:
\(H(S_{\text{circle}})=0\)
\(H(S_{\text{square}})=1\)
\(H(S_{\text{triangle}})=0\)
Weighted remainder:
\[ H(S\mid \text{shape})=\frac{3}{8}(0)+\frac{4}{8}(1)+\frac{1}{8}(0)=0.5 \]
So \[ \operatorname{Gain}(S,\text{shape})=0.95-0.5=0.45 \]
Since the tutorial computes \(\operatorname{Gain}(S,\text{color})=0.34\), the root attribute is shape.
Worked Example 2: Gini impurity and split reduction
Suppose a node contains 10 examples: 6 positives and 4 negatives.
Parent node Gini
\[ G_{\text{parent}}=1-\left(\frac{6}{10}\right)^2-\left(\frac{4}{10}\right)^2 =1-0.36-0.16=0.48 \]
Now split into:
Left child: 4 positive, 0 negative
Right child: 2 positive, 4 negative
Weighted child Gini
Left child is pure, so \(G_L=0\).
For the right child:
\[ G_R=1-\left(\frac{2}{6}\right)^2-\left(\frac{4}{6}\right)^2 =1-\frac{1}{9}-\frac{4}{9}=\frac{4}{9}\approx0.444 \]
Weighted post-split impurity:
\[ G_{\text{split}}=\frac{4}{10}(0)+\frac{6}{10}(0.444)\approx0.267 \]
Impurity reduction: \(0.48-0.267\approx0.213\). This is a strong split because it creates one pure node and one much cleaner mixed node.
Why ensembles help and what each method changes
Ensembles work best when the base models are individually decent and not all making the exact same mistakes. The lecture’s error-rate graph makes this explicit: diversity matters, not just quantity.
Bagging
Train each tree on a bootstrap sample. Because trees are unstable learners, averaging many of them mainly reduces variance.
Random Forest
Bagging plus random feature subsets at each split. This decorrelates the trees, which improves the value of averaging.
AdaBoost
Sequentially increases the weight of previously misclassified examples, so later models focus on harder cases.
Gradient Boosting
Adds new models that correct the current ensemble’s residual errors stage by stage.
Lecture probability insight
If 25 binary classifiers each have error rate \(\varepsilon=0.35\) and their errors are independent, the ensemble majority-vote error is
\[ \varepsilon_{\text{ensemble}}=\sum_{i=13}^{25}\binom{25}{i}\varepsilon^i(1-\varepsilon)^{25-i}\approx 0.06 \]
That is the mathematical reason bagging and Random Forest can outperform one tree: averaging many slightly different, better-than-random models collapses variance.