Decision Trees and Ensemble Learning

Introduction and Context

Decision trees are supervised learning models that represent a prediction as a sequence of hierarchical decisions. At each internal node, the model applies a rule to one feature; each branch represents an outcome of that rule; and each terminal leaf produces a prediction. Trees are attractive because their logic is visible, they accommodate nonlinear relationships and interactions, and they can work with numerical and categorical variables. Their principal weakness is instability: small changes in training data can produce substantially different trees.

Ensemble learning addresses this weakness by combining multiple models. Bagging reduces variance by fitting models to different resampled data sets and averaging their predictions. Random forests add feature-level randomisation to bagging. Boosting builds models sequentially so that later models focus on errors made by earlier models. Stacking combines heterogeneous models through a learned meta-model. These methods form a central part of practical machine learning because they often provide strong predictive performance without requiring a highly elaborate feature transformation pipeline.

The central design problem is not simply to maximise accuracy. A suitable ensemble must also be computationally feasible, calibrated, robust to distributional change, sufficiently interpretable, and consistent with legal and ethical requirements.

Learning Objectives

By the end of this chapter, a learner should be able to:

1. Explain how decision trees recursively partition a feature space.
2. Calculate and interpret entropy, Gini impurity, information gain and variance reduction.
3. Apply pruning and regularisation to control tree complexity.
4. Distinguish bagging, random forests, boosting, gradient boosting and stacking.
5. Analyse ensemble behaviour using the bias–variance framework.
6. Tune ensembles using valid resampling and out-of-sample evaluation.
7. Interpret ensemble predictions responsibly and identify their limitations.

1. Decision Trees as Recursive Partitioning Models

A decision tree partitions the input space into regions. For classification, a leaf generally predicts the majority class or a class-probability distribution. For regression, a leaf commonly predicts the mean response of the training observations reaching that leaf.

A binary numerical split may be written as:

where x_j is feature j and t is a candidate threshold. Observations satisfying the condition move to one child node and the remainder move to the other. Categorical features may be split by category membership, although the exact treatment depends on the implementation.

A tree is grown by repeatedly selecting a split that improves node purity. Let a node contain N observations and let its two child nodes contain N_L and N_R observations. If I(·) is an impurity measure, the weighted impurity after splitting is:

The impurity reduction is:

The split is useful when ΔI is large. This expression applies to classification and regression, provided an appropriate impurity function is selected.

1.1 Classification impurity measures

For a node containing class proportions p₁, p₂, …, p_K, entropy is:

Here, K is the number of classes, p_k is the proportion of class k, and the convention 0 log₂ 0 = 0 is used. Entropy is zero for a pure node and is largest when the classes are equally represented.

Gini impurity is:

It can also be interpreted as the probability that a randomly selected observation would be misclassified if its class were assigned according to the node’s class distribution. Both entropy and Gini impurity measure node heterogeneity. Gini impurity is often computationally simpler, while entropy has a direct information-theoretic interpretation.

Information gain using entropy is the reduction in entropy produced by a split. The same weighted-child formula applies to Gini impurity. A tree algorithm may use either criterion; results can differ slightly, but preprocessing and validation usually have a greater practical effect than this choice.

1.2 Regression impurity

For regression, a common node impurity is the within-node sum of squared deviations:

where y_i is the observed response and ȳ_S is the mean response in node S. The mean minimises squared error within a node. A split is selected when it substantially reduces the weighted residual variation of its child nodes.

2. Worked Example: Selecting a Classification Split

Suppose a node contains 10 observations: 6 positive and 4 negative. Its Gini impurity is:

A candidate split produces a left child with 4 observations, all positive, and a right child with 6 observations containing 2 positive and 4 negative cases. The left impurity is zero. The right impurity is:

The weighted post-split impurity is:

Therefore, the impurity reduction is:

This split improves class separation. The calculation assumes that the candidate split is evaluated at the current node and that class proportions are estimated from the training observations reaching that node.

3. Tree Growth, Prediction and Regularisation

A fully grown tree can continue splitting until leaves are pure or contain very few observations. Such a tree may memorise noise. Important controls include:

• Maximum depth: limits the number of decisions along a path.
• Minimum samples per split or leaf: prevents decisions based on very small groups.
• Maximum number of leaves: directly controls model size.
• Minimum impurity decrease: permits a split only when its improvement exceeds a threshold.
• Cost-complexity pruning: grows a large tree and then removes branches whose predictive benefit is insufficient.

A common cost-complexity objective is:

Here, R(T) is the empirical loss of tree T, |T_leaves| is the number of terminal leaves, and α ≥ 0 penalises complexity. Larger α favours smaller trees. The loss and penalty must be selected consistently with the task and implementation. Pruning parameters should be chosen using validation data or cross-validation, not by inspecting the test set.

Trees usually require little feature scaling because comparisons such as x_j ≤ t are unaffected by a monotonic rescaling of a feature. Missing-value handling, categorical encoding, high-cardinality identifiers and leakage nevertheless require careful treatment. A tree can exploit an identifier or a post-outcome variable even when the apparent predictive relationship is spurious.

4. Bias, Variance and Generalisation

Expected prediction error can be conceptualised through the bias–variance decomposition. For squared-error regression at an input x, with irreducible noise variance σ²,:

Here, f̂(x) is the fitted predictor over hypothetical training samples. The decomposition assumes a squared-error setting and separates irreducible noise, systematic error from an overly restrictive model, and sensitivity to the training sample.

A shallow tree generally has higher bias and lower variance. A deep tree generally has lower training bias and higher variance. Bagging primarily reduces variance, while boosting can reduce bias and variance depending on its depth, learning rate, number of iterations and regularisation. The decomposition is a conceptual guide rather than a guarantee that every tuning change affects only one component.

5. Bagging and Random Forests

5.1 Bagging

Bootstrap aggregation, or bagging, creates B bootstrap training sets by sampling observations with replacement. A base learner is fitted to each sample. For regression, predictions are averaged:

For classification, the ensemble may use majority voting or average estimated class probabilities. If base-model errors are not perfectly correlated, averaging can reduce variance. If each model has variance σ_f² and pairwise error correlation ρ, the approximate variance of an average of B equally variable models is:

This relationship assumes comparable model variances and a simplified common-correlation structure. It shows why adding models has diminishing returns when errors are highly correlated.

A bootstrap sample of size N contains, on average, approximately 63.2% of the distinct original observations. The remaining observations are called out-of-bag (OOB) for that fitted model. OOB observations can provide an internal performance estimate, although an external validation set remains valuable, especially during extensive tuning or under distribution shift.

5.2 Random forests

A random forest combines bootstrap sampling with random feature selection. At each split, only a randomly selected subset of features is considered. This decorrelates trees, which is often more important than simply increasing their number.

Important hyperparameters include:

Random forests are robust to nonlinearities, interactions and moderate outliers. They are less naturally extrapolative than many parametric regression models: regression predictions are generally bounded by the response values represented in terminal leaves.

6. Boosting and Gradient Boosting

Boosting constructs an additive model sequentially. A general additive predictor is:

where F₀ is the initial model, h_m is the learner added at iteration m, η is the learning rate, and M is the number of iterations. Usually, 0 < η ≤ 1. Small learning rates often require more iterations but can improve generalisation when paired with appropriate regularisation.

6.1 AdaBoost intuition

AdaBoost increases the emphasis placed on observations misclassified by earlier weak learners. The next learner therefore addresses difficult cases. A weighted combination of weak learners can form a strong classifier. AdaBoost can be sensitive to noisy labels and extreme outliers because repeatedly misclassified observations may receive very large weights.

6.2 Gradient boosting

Gradient boosting generalises the idea by fitting each new learner to the negative gradient of the loss function. Let the empirical objective be:

where ℓ is a differentiable or suitably approximated loss and Ω represents regularisation when included by the implementation. At iteration m, the pseudo-residual for observation i is:

A weak learner is fitted to these pseudo-residuals, and the model is updated in their direction. This is functional gradient descent: optimisation occurs over functions rather than only over a finite parameter vector.

For squared-error regression, ℓ(y,F) = 1/2(y−F)², so the negative gradient is y_i − F_m−1(x_i), the ordinary residual. For other losses, the target used for the next learner differs from the raw residual.

Common gradient-boosting controls are learning rate, number of estimators, tree depth, minimum leaf size, row subsampling and column subsampling. Early stopping monitors validation performance and stops when additional iterations cease to improve it. The validation data used for early stopping must be kept separate from the final test data.

Modern implementations such as histogram-based gradient boosting and highly optimised tree-boosting libraries improve speed and memory use. Their additional features may include regularised leaf weights, missing-value routing, categorical-feature handling and efficient distributed training. These capabilities do not remove the need for leakage control, calibration assessment and independent testing.

7. Stacking and Model Diversity

Stacking combines predictions from several base learners using a meta-learner. For example, a linear meta-model may receive predictions from a random forest, a gradient-boosted tree and a regularised linear model.

The critical methodological requirement is that meta-features be generated out of sample. If a base learner predicts the same observations used to fit it, its predictions are overly optimistic, and the meta-learner can learn from leakage. In cross-validated stacking, each training observation receives a prediction from a base model that did not train on that observation. The base models are then refitted on all available training data before predicting the held-out test set.

Stacking is useful when models make complementary errors. Simply combining highly correlated models offers limited benefit. A meta-learner should be regularised and evaluated within a nested or carefully separated validation design, particularly when many candidate models are tried.

8. Comparing Ensemble Families

No method is universally best. Random forests often provide a strong baseline with limited tuning. Gradient boosting may achieve superior accuracy on structured tabular data, but requires more careful tuning. A simple, calibrated model can be preferable where explanation, stability or regulatory defensibility is more important than a small accuracy improvement.

9. Tuning and Evaluation for Robust Performance

A reliable workflow begins with a problem definition: target population, prediction horizon, acceptable errors, operational costs and fairness requirements. Data splitting must reflect deployment. Random splits are inappropriate for many temporal, grouped or spatial problems. For time-dependent data, training must precede validation chronologically. For repeated individuals, all records from an individual should normally remain in the same partition.

Recommended practices include:

1. Establish a simple baseline, such as majority class, mean prediction or regularised linear model.
2. Create training, validation and final test partitions, or use nested cross-validation.
3. Fit preprocessing steps within each training fold.
4. Tune a small, justified hyperparameter space rather than conducting unstructured search.
5. Use early stopping only with an appropriate validation scheme.
6. Report uncertainty, subgroup performance and calibration, not only a single score.
7. Retrain the selected procedure on permitted data and evaluate once on the untouched test set.

For binary classification, accuracy may be misleading under class imbalance. Useful measures include precision, recall, F1 score, ROC-AUC, precision–recall AUC, log loss and calibration. For regression, mean absolute error is:

and root mean squared error is:

MAE treats errors linearly, whereas RMSE gives greater influence to large errors. The choice should reflect the operational loss. Metrics must be computed on observations not used to fit the evaluated predictions.

10. Interpretability and Responsible Use

Tree structure offers local transparency, but a large ensemble is not automatically interpretable. Useful tools include:

• Permutation importance: measures performance degradation after permuting a feature. It is model- and evaluation-set-dependent and can undervalue one of several correlated features.
• Impurity-based importance: aggregates split improvements, but may favour continuous or high-cardinality variables.
• Partial dependence: estimates average predictions as a feature varies, but can be misleading in regions where feature combinations are unrealistic.
• Individual conditional expectation: displays prediction curves for individual observations and can reveal heterogeneity hidden by averages.
• Shapley-based explanations: allocate a prediction difference among features under specified background and dependence assumptions; they are explanations of a model, not proofs of causality.

Interpretability should be tested for stability across samples and model versions. A feature with high importance is not necessarily a cause of the outcome. Sensitive attributes may be excluded from model inputs yet reconstructed through proxies such as location, occupation or purchasing behaviour.

Governance concerns include privacy, discrimination, contestability, documentation, access control and monitoring for drift. In high-impact contexts, the organisation should record the training population, target definition, feature provenance, validation design, threshold rationale, known limitations and human-review procedure. Fairness cannot be inferred from aggregate accuracy alone; subgroup error rates, calibration and the consequences of false positives and false negatives should be examined.

11. Illustrative Case: Credit-Risk Screening

Background

A lender wants to predict whether a small-business applicant will become seriously delinquent within twelve months. The data contain application attributes, repayment history, cash-flow summaries and industry information.

Problem

The historical data are imbalanced: serious delinquency is uncommon. Some records contain variables updated after approval, and applications from the same business may occur repeatedly. The lender requires both predictive performance and an auditable decision process.

Analysis

A random row-level split would leak information between repeated applications and could allow post-approval variables to enter training. The modelling team therefore defines the prediction timestamp, removes post-timestamp features, groups applications by business, and uses a time-aware validation design. It reports precision–recall performance, calibration and error rates across relevant business segments.

Approach and solution

A regularised logistic model establishes a transparent baseline. A random forest provides a variance-reduced nonlinear benchmark. A gradient-boosted tree model is tuned with shallow trees, learning-rate control, row subsampling and early stopping. The decision threshold is selected using the cost of manual review, missed delinquency and unnecessary referral rather than accuracy alone.

The model card documents data limitations, missing-value treatment, feature definitions and known proxy risks. Permutation explanations are supplemented with case-level review, and an appeal process allows applicants to request human reconsideration. Monitoring checks calibration, approval rates, subgroup performance and feature drift after deployment.

Outcome

The boosted model improves ranking performance over the baseline, but its operational value depends on threshold selection and review capacity. The lender does not deploy the model solely because it has the highest validation score. Instead, it adopts the model subject to calibration monitoring, periodic fairness review, human oversight and a rollback plan.

Learning points

The case demonstrates that ensemble selection is a socio-technical decision. Leakage prevention, temporal validity, group-aware splitting, cost-sensitive evaluation and governance are as important as algorithm choice.

12. Challenges and Contemporary Directions

Ensembles can be computationally expensive, particularly when cross-validation, hyperparameter search and large forests are combined. Distributed training and histogram methods reduce cost, but energy use and latency should be measured. Ensembles may also be poorly calibrated even when they rank observations well; post-hoc calibration using a separate validation set can help.

Current research and practice address uncertainty estimation, conformal prediction, monotonic constraints, causal and invariant prediction, fairness-aware learning, online updating and efficient inference. Monotonic constraints can encode domain knowledge such as the requirement that risk should not decrease as a verified debt burden increases. Such constraints improve plausibility but do not establish causal validity. Under distribution shift, robust monitoring and selective prediction may be more valuable than a marginal improvement on an old benchmark.

Best-Practice Checklist

• Define the deployment population and prediction time before modelling.
• Use a baseline and compare all complex models against it.
• Prevent leakage through preprocessing, grouping and temporal design.
• Tune depth, learning rate, number of estimators and sampling jointly where relevant.
• Use out-of-bag estimates or cross-validation appropriately, not as substitutes for critical external testing.
• Assess calibration, subgroup performance and operational costs.
• Prefer simpler or constrained models when performance is comparable.
• Explain predictions without presenting feature importance as causation.
• Document assumptions, version data and monitor drift after deployment.

Chapter Summary

Decision trees recursively partition data using impurity reduction for classification or residual variation for regression. Entropy, Gini impurity and squared-error criteria provide principled split measures. Deep trees can have low training error but high variance, whereas pruning and structural constraints improve generalisation.

Bagging reduces variance through bootstrap aggregation. Random forests additionally randomise candidate features, lowering correlation among trees. Boosting constructs an additive model sequentially; gradient boosting fits learners to loss gradients and can achieve excellent performance on structured data. Stacking combines out-of-sample predictions from diverse base models through a meta-learner, but requires strict leakage control.

The bias–variance framework explains why model complexity and ensemble diversity matter. Robust tuning requires deployment-relevant validation, appropriate metrics, calibration analysis and an untouched final test set. Interpretability tools are informative but do not establish causality. Responsible deployment requires attention to fairness, privacy, documentation, human oversight, drift and the consequences of errors.

Key Terms

Decision tree: A hierarchical model that predicts through sequential feature-based decisions.

Node: A region or decision point in a tree.

Leaf: A terminal tree region that produces a prediction.

Entropy: An information-based measure of class heterogeneity.

Gini impurity: A classification impurity measure based on squared class proportions.

Information gain: Reduction in entropy produced by a split.

Pruning: Removal of tree branches to reduce unnecessary complexity.

Bagging: Bootstrap aggregation of independently fitted base learners.

Bootstrap sample: A sample formed by drawing observations with replacement.

Out-of-bag estimate: Prediction or performance estimate based on observations omitted from a bootstrap sample.

Random forest: An ensemble using bootstrap trees and random feature subsets.

Boosting: Sequential combination of learners that focuses on correcting prior errors.

Gradient boosting: Boosting that fits learners to negative loss gradients.

Learning rate: The multiplier controlling each boosting update.

Early stopping: Termination of training when validation performance ceases to improve.

Stacking: Combination of base-model predictions using a meta-learner.

Bias: Systematic prediction error caused by restrictive assumptions.

Variance: Prediction sensitivity to the training sample.

Calibration: Agreement between predicted probabilities and observed frequencies.

Data leakage: Unintended use of information unavailable at prediction time.

Review Questions

5 Short Answer Questions

1. What is the purpose of an impurity measure in a decision tree?
2. Distinguish entropy from Gini impurity.
3. Why does random feature selection help a random forest?
4. What is the role of the learning rate in gradient boosting?
5. Why must stacking use out-of-sample base-model predictions?

5 Long Answer Questions

1. Explain how a classification tree is grown, including split evaluation, stopping and pruning.
2. Compare bagging, random forests and gradient boosting in terms of construction, bias, variance and computational behaviour.
3. Derive and interpret the weighted impurity reduction for a binary split.
4. Discuss how validation design should change for temporal, grouped and imbalanced data.
5. Evaluate the benefits and limitations of permutation importance, partial dependence and Shapley-based explanations.

3 Analytical / Application Questions

1. A classification node contains 12 observations, 9 belonging to class A and 3 to class B. Calculate its Gini impurity. Then evaluate a split whose child nodes contain 5 A observations and 1 B observation on the left, and 4 A observations and 2 B observations on the right. Determine the impurity reduction.
2. Design a validation strategy for a fraud model in which the same customer may appear many times and transaction patterns change over time. Justify the split, metric and monitoring choices.
3. A random forest and a gradient-boosted model have similar test AUC, but the boosted model is poorly calibrated and the forest has unstable subgroup error rates. Recommend a deployment decision and identify the additional analyses required before release.

Multiple Choice Questions with Answers

Question 1

Which measure is zero for a completely pure classification node?

A. Entropy and Gini impurity

B. RMSE only

C. Bias only

D. Bootstrap variance

Correct Answer: A. Entropy and Gini impurity

Question 2

What is the principal variance-reduction mechanism in bagging?

A. Sequentially increasing observation weights

B. Averaging models trained on bootstrap samples

C. Scaling all input features

D. Removing all noisy observations

Correct Answer: B. Averaging models trained on bootstrap samples

Question 3

How does a random forest usually decorrelate its trees?

A. It uses only one tree at a time

B. It forces every tree to have identical splits

C. It randomly restricts features considered at splits

D. It fits trees only to misclassified observations

Correct Answer: C. It randomly restricts features considered at splits

Question 4

For squared-error regression, the negative gradient used by gradient boosting is what?

A. The absolute prediction

B. The residual y − prediction

C. The class proportion

D. The feature variance

Correct Answer: B. The residual y − prediction

Question 5

What is the main danger of using in-sample base-model predictions in stacking?

A. Underflow

B. Data leakage and optimistic meta-model training

C. Automatic feature scaling

D. Excessive class balance

Correct Answer: B. Data leakage and optimistic meta-model training

Question 6

Which change generally increases the complexity of an individual tree?

A. Reducing maximum depth

B. Increasing minimum leaf size

C. Increasing maximum depth

D. Increasing pruning strength

Correct Answer: C. Increasing maximum depth

Question 7

If two ensemble models make highly correlated errors, averaging them will usually provide what benefit?

A. A limited variance reduction

B. Guaranteed elimination of bias

C. Guaranteed causal interpretation

D. Perfect calibration

Correct Answer: A. A limited variance reduction

Question 8

For a highly imbalanced classification problem, which metric is often more informative than accuracy for identifying positive cases?

A. Precision–recall AUC

B. The number of tree leaves

C. Training entropy only

D. Feature scale

Correct Answer: A. Precision–recall AUC

Question 9

What does a larger cost-complexity parameter generally encourage?

A. Larger and deeper trees

B. Smaller trees with fewer leaves

C. More leakage

D. More bootstrap observations per row

Correct Answer: B. Smaller trees with fewer leaves

Question 10

Which statement about feature importance is correct?

A. Importance proves that a feature causes the outcome

B. Impurity importance can favour high-cardinality features

C. Permutation importance is independent of the evaluation data

D. Importance values guarantee fairness

Correct Answer: B. Impurity importance can favour high-cardinality features