COMP5318 — Applied Machine Learning
Week 5: Decision Trees & Ensembles
Week 5 starts with interpretable tree models and ends with some of the most practically strong classical ensembles. The tree lecture explains entropy, information gain, pruning, and gain ratio; the ensemble lecture explains bagging, random forests, AdaBoost, and gradient boosting; the notebook turns those ideas into side-by-side sklearn experiments on iris and the moons dataset.
Course materials
These files together answer two questions: how does a single tree decide where to split, and why do many imperfect trees often outperform one perfectly fitted tree?
| File | What it contributes |
|---|---|
| w5.ipynb | Iris decision trees, graphviz visualisation, pre-pruning, moons-based bagging/random forest/boosting experiments, and concrete sklearn parameters. |
| w5-solutions.ipynb | Interpretation of pruning and comparison of ensemble families. |
| ml5a.pdf | Decision-tree theory: entropy, information gain, pruning strategies, numeric splits, gain-ratio correction, and CART's Gini note. |
| ml5b.pdf | Ensemble theory: why diversity matters, bootstrap aggregation, AdaBoost, gradient boosting, and random forest construction. |
| t5.pdf | By-hand entropy and information-gain calculations for a small toy dataset. |
| t5-solutions.pdf | Worked entropy values, gain comparison, and the final tree root choice. |
Decision trees: purity, splits, and pruning
A decision tree recursively partitions the feature space. Each internal node tests an attribute, each branch corresponds to an outcome, and each leaf predicts a class. The central design question is always: which split should be chosen next?
Entropy
Measures class impurity. For a binary task, entropy is 0 when all examples belong to one class and 1 when the classes are evenly mixed.
Information gain
The reduction in entropy caused by splitting on an attribute. The lecture defines the best split as the one with the highest gain.
Gain ratio
A correction for information gain's bias toward highly branching attributes, such as ID-like features.
Gini note
The lecture mentions that CART uses Gini rather than entropy. Same goal, different impurity measure.
Entropy measures purity, and information gain is the decrease in entropy after a split. The Week 5 tutorial trains you to compute both by hand because that is the logic behind root and branch selection.
Numeric attributes
The lecture discretises numeric features by considering binary thresholds. The procedure is: sort by the numeric value, propose split points where the class changes, evaluate each candidate split, and keep the best one.
Pruning
Deep trees overfit easily. The lecture distinguishes pre-pruning (stop earlier) from post-pruning (grow fully, then remove subtrees using validation performance).
Notebook implementation: the iris example uses DecisionTreeClassifier(criterion='entropy', random_state=42). The pre-pruning example limits tree depth with max_depth=4. The visualisation step exists to make the node statistics legible: sample counts, class counts, and predicted majority class at each node.
Interpretability
The lecture repeatedly frames tree models as transparent. You can follow a single path from root to leaf and explain the prediction as a chain of tests.
Why highly branching features are risky
A feature such as an ID code can create very pure tiny subsets and therefore look artificially attractive to raw information gain, even though it overfits badly.
Validation-set role
When pruning, the lecture explicitly uses a validation set to decide whether replacing a subtree with a leaf improves or preserves generalisation.
Ensembles: why many weak or unstable models can win
The second half of Week 5 is about diversity. Ensembles help when the base models are individually useful but make different mistakes. If all models are identical, voting does nothing.
Bagging
Bagging stands for bootstrap aggregation. Build many models on bootstrap samples and combine their predictions, usually by majority vote for classification.
The notebook uses BaggingClassifier with 500 decision trees, each trained on 100 bootstrapped examples from the moons training split.
Random forest
Random forest adds a second source of randomness: at each split, only a subset of features is considered. The lecture emphasises that this reduces correlation between trees.
The notebook uses 500 trees and highlights max_features as a key parameter because it controls the strength-vs-correlation tradeoff.
AdaBoost
Sequentially focuses on examples that earlier learners handled badly. The lecture describes weighted training data and weighted voting; the notebook uses shallow trees (decision stumps) as base learners.
Gradient boosting
Also adds models sequentially, but instead of reweighting data in the AdaBoost style, it adds new learners that minimise the error of the current ensemble.
Lecture intuition for why ensembles help
- If all base learners make the same mistakes, voting does not improve anything.
- If their errors are less correlated, combining them reduces variance.
- Bagging and random-feature selection are tools for creating that diversity.
Bagging boundary
The notebook explicitly shows that bagging creates a smoother decision boundary than a single unpruned tree on the moons data.
Random-forest comment
The lecture says the ideal forest has accurate individual trees that are still not too correlated with each other.
Boosting comment
AdaBoost can turn weak learners into a strong learner if they are slightly better than random. That is the conceptual point of the theorem slide.
from sklearn.ensemble import BaggingClassifier, RandomForestClassifier, AdaBoostClassifier, GradientBoostingClassifier
from sklearn.tree import DecisionTreeClassifier
bag_clf = BaggingClassifier(
DecisionTreeClassifier(criterion="entropy", random_state=42),
n_estimators=500,
max_samples=100,
bootstrap=True,
random_state=42
)
rnd_clf = RandomForestClassifier(
criterion="entropy",
n_estimators=500,
max_leaf_nodes=16,
random_state=42
)Tutorial calculation: entropy and information gain by hand
The tutorial solution computes the class entropy of the 8-example dataset as:
\(H(S)=0.95\) bits
The solution then computes:
- gain(shape) = 0.45 bits
- gain(color) = 0.34 bits
Therefore shape is selected as the root of the decision tree.
The important exam habit is to show the weighted entropy after the split, not just the parent entropy. You first compute the impurity of each branch subset, weight those impurities by branch size, and subtract the result from the parent entropy. The attribute with the largest reduction is chosen.
Be ready to compare trees with k-NN and linear models. Trees give interpretability and nonlinear splits; ensembles trade away some interpretability for accuracy and stability.
Chapter quizzes
Self-test and math questions for this week are in the Quiz Hub (practice or exam mode).