Decision Trees, Ensembles and Gradient Boosting

Introduction and Context

Decision trees and ensemble methods are among the most effective approaches for structured, tabular data. They are valuable because they can represent nonlinear relationships, capture interactions among variables, accommodate mixed feature types, and require comparatively little feature scaling. Modern implementations of gradient boosting frequently achieve state-of-the-art performance on credit risk, fraud detection, customer analytics, medical prediction, industrial monitoring, and ranking problems.

A decision tree partitions the feature space into regions and assigns a prediction to each region. A single tree is interpretable but can be unstable and prone to overfitting. Ensemble learning addresses these weaknesses by combining many models. Bagging reduces variance by fitting models independently on resampled data; random forests add feature randomisation; boosting constructs models sequentially to correct previous errors; stacking combines heterogeneous models through a meta-learner.

The central engineering challenge is not merely selecting an algorithm. It is designing a valid evaluation procedure, controlling complexity, tuning hyperparameters, interpreting predictions responsibly, and ensuring that model performance remains reliable after deployment.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Explain how decision trees create partitions for classification and regression.

2. Derive and use entropy, information gain, Gini impurity, and variance reduction.

3. Control tree complexity and diagnose overfitting.

4. Distinguish bagging, random forests, boosting, stacking, and blending.

5. Explain the objective and optimization process of gradient boosting.

6. Compare classical gradient boosting with modern frameworks such as XGBoost, LightGBM, and CatBoost.

7. Tune ensemble models using leakage-resistant validation procedures.

8. Interpret feature importance and individual predictions using appropriate tools.

9. Design a robust structured-data solution while addressing governance and fairness risks.

1. Decision Trees as Recursive Partitioning Models

A decision tree consists of internal decision nodes, branches, and terminal leaves. At an internal node, a rule such as “income < 50,000” or “age >= 35” sends an observation to one of two or more child nodes. A leaf produces a prediction. For classification, this may be the majority class or a vector of class probabilities. For regression, it is commonly the mean target value of observations in that leaf.

For an input vector x, a tree defines a piecewise-constant function:

f(x) = c_l if x belongs to leaf l,

where c_l is the prediction associated with leaf l. The model is therefore highly nonlinear even though the prediction within each leaf is simple.

1.1 Classification impurity

Suppose a node contains n observations and K classes. Let p_k be the proportion of observations in class k. Two common impurity measures are:

Entropy:

H(S) = - sum from k=1 to K of p_k log2(p_k).

Gini impurity:

G(S) = 1 - sum from k=1 to K of p_k squared.

Both measures are zero when a node is pure. Entropy reaches its maximum when all classes are equally represented. Gini impurity has a similar interpretation and is computationally simpler. The logarithm base in entropy changes its units but not the ranking of candidate splits.

For a split of node S into child nodes S1 and S2, the weighted post-split impurity is:

I_split = (n1/n) I(S1) + (n2/n) I(S2).

The impurity reduction is:

Gain = I(S) - I_split.

The split with the largest gain is selected, subject to any constraints such as minimum leaf size or maximum depth. The formula assumes that the child proportions n1/n and n2/n represent the relevance of each child to the parent population.

1.2 Regression trees

For regression, a common objective is the residual sum of squares within leaves. If leaf l contains observations with target values y_i, its optimal constant prediction under squared-error loss is:

c_l = (1/n_l) sum over i in l of y_i.

The corresponding within-leaf squared error is:

SSE_l = sum over i in l of (y_i - c_l)^2.

A candidate split is preferred when it produces a large reduction in total SSE. Under absolute-error loss, the optimal leaf prediction is the median rather than the mean, illustrating that the loss function determines the leaf estimator.

1.3 Worked split calculation

Assume a binary classification node has 10 records: 6 positive and 4 negative. Its Gini impurity is:

G_parent = 1 - (0.6 squared + 0.4 squared) = 0.48.

A candidate split creates a left child with 4 positive and 1 negative record, and a right child with 2 positive and 3 negative records. The left impurity is:

G_left = 1 - (0.8 squared + 0.2 squared) = 0.32.

The right impurity is:

G_right = 1 - (0.4 squared + 0.6 squared) = 0.48.

The weighted impurity after splitting is:

(5/10)(0.32) + (5/10)(0.48) = 0.40.

Thus, the Gini reduction is 0.48 - 0.40 = 0.08. This split improves purity, although other candidate splits may yield a larger reduction.

2. Tree Construction, Regularisation and Bias–Variance Trade-Off

Greedy tree algorithms examine candidate splits locally rather than searching all possible trees globally. This makes training practical but does not guarantee a globally optimal tree. A fully grown tree often has low training error and high variance: small changes in the training data can produce a substantially different tree.

Important complexity controls include:

• Maximum depth: limits the number of sequential decisions.
• Minimum samples for splitting: prevents unreliable splits based on very small nodes.
• Minimum samples per leaf: discourages highly specific regions.
• Maximum number of leaves: directly controls model size.
• Maximum features: limits features considered at each split.
• Cost-complexity pruning: removes branches whose predictive benefit does not justify their complexity.

A simplified cost-complexity objective is:

R_alpha(T) = R(T) + alpha |T|,

where R(T) is the empirical loss of tree T, |T| is a measure of tree size, and alpha is a nonnegative complexity penalty. Larger alpha produces smaller trees. In practice, pruning or depth selection should be based on validation data rather than training performance.

Trees generally have low bias and high variance when deep, whereas shallow trees have higher bias and lower variance. Ensemble methods exploit this trade-off rather than attempting to make one tree perfect.

3. Bagging and Random Forests

3.1 Bootstrap aggregation

Bagging, or bootstrap aggregation, trains B base learners independently. Each learner is fitted to a bootstrap sample drawn with replacement from the training set. For regression, predictions are averaged:

f_bag(x) = (1/B) sum from b=1 to B of f_b(x).

For classification, predictions may be combined by majority vote or averaged class probabilities. If individual prediction errors are not perfectly correlated, averaging reduces variance. In the idealised case of B equally variable predictors with pairwise error correlation rho and variance sigma squared, the ensemble variance is approximately:

sigma squared times [rho + (1-rho)/B].

This relationship shows why diversity matters. Increasing B reduces the independent component of variance, but the correlated component remains.

3.2 Random forests

A random forest combines bootstrap sampling with random feature selection. At each node, only a randomly selected subset of features is considered for splitting. This reduces correlation among trees, particularly when a few dominant predictors would otherwise appear in nearly every tree.

Random forests typically provide:

• strong nonlinear prediction;
• limited sensitivity to feature scaling;
• useful out-of-bag validation estimates;
• resistance to overfitting as the number of trees increases, although excessively complex individual trees can remain problematic;
• estimates of feature importance.

Out-of-bag observations are records not selected in a particular bootstrap sample. On average, approximately 36.8% of the original observations are out of bag for each bootstrap sample, because the probability that an observation is omitted approaches e^-1. These observations can be used to estimate performance for the corresponding tree without requiring a separate validation set. However, out-of-bag estimates do not remove the need for a carefully designed final test set.

3.3 Limitations of random forests

Random forests may require substantial memory and inference time. Their probability estimates can be poorly calibrated, especially in imbalanced problems. They can also be less accurate than boosting on many tabular datasets. Standard impurity-based importance is biased toward continuous variables and categorical variables with many possible levels. Permutation importance and cross-validated explanation methods are often preferable.

4. Boosting: Sequential Error Correction

Boosting builds a strong learner from a sequence of weak or moderately strong learners. Unlike bagging, which fits models independently, boosting makes later models depend on earlier models.

For an additive model:

F_M(x) = F_0(x) + sum from m=1 to M of eta h_m(x),

where F_0 is the initial prediction, h_m is the learner added at iteration m, M is the number of iterations, and eta is the learning rate. The learning rate controls the contribution of each learner.

A small learning rate generally requires more iterations but often improves generalisation. The number of estimators and learning rate therefore interact and should be tuned together.

4.1 AdaBoost

In binary classification, AdaBoost increases the weights of observations misclassified by the current learner and decreases the relative influence of correctly classified observations. A weak learner is then trained on the reweighted data. The process focuses subsequent learners on difficult cases.

AdaBoost can perform well with simple base learners, but it may be sensitive to noisy labels and extreme outliers because these observations can receive increasingly large weights.

4.2 Gradient boosting

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

L(F) = sum over i of ell(y_i, F(x_i)).

At iteration m, pseudo-residuals are:

r_im = - [partial derivative of ell(y_i, F(x_i)) with respect to F(x_i)] evaluated at F = F_(m-1).

A weak learner h_m is fitted to these pseudo-residuals. The model is then updated as:

F_m(x) = F_(m-1)(x) + eta gamma_m h_m(x),

where gamma_m may be found by a line search or incorporated into the learner fitting procedure. This is functional gradient descent: optimisation occurs over a space of functions rather than a finite-dimensional parameter vector.

For squared-error regression, ell(y,F) = one-half (y-F)^2, so the negative gradient is y-F. Thus, each tree fits the current residuals. For binary logistic classification, the negative gradient is related to the difference between the observed label and the current estimated probability, with the exact form depending on the chosen parameterisation of the score.

Gradient boosting does not require residuals to be interpreted literally for every loss. They are gradients of the loss with respect to the current prediction.

4.3 Regularisation in gradient boosting

Gradient-boosted trees are controlled by:

• learning rate;
• number of boosting rounds;
• tree depth or number of leaves;
• minimum child weight or minimum leaf observations;
• row subsampling;
• feature subsampling;
• L1 and L2 penalties;
• early stopping based on validation performance.

The interaction among these parameters is more important than any single default value. Deep trees capture high-order interactions but can overfit. Shallow trees create smoother additive corrections and usually require more rounds.

5. Modern Gradient-Boosting Frameworks

5.1 XGBoost

XGBoost uses a regularised objective that combines training loss with penalties on tree complexity. It supports shrinkage, row and column subsampling, sparsity-aware split finding, missing-value directions, and efficient parallel computation. Its regularisation options include L1 and L2 penalties and explicit controls on leaf weights and tree structure.

5.2 LightGBM

LightGBM uses histogram-based split finding and is designed for speed and memory efficiency. Its leaf-wise growth strategy can reduce loss rapidly but may overfit when data are limited. Maximum leaves, minimum leaf observations, and depth constraints are therefore important. Categorical feature handling and exclusive feature bundling can improve efficiency in suitable datasets.

5.3 CatBoost

CatBoost is designed to handle categorical variables with ordered statistical procedures intended to reduce target leakage during encoding. It can be particularly effective when high-cardinality categorical variables are important. Its ordered methods require careful understanding of training and validation separation; preprocessing should still be embedded within a leakage-resistant pipeline.

5.4 Framework selection

No framework is universally superior. Selection should consider predictive performance, training latency, memory, categorical-data structure, interpretability requirements, licensing and operational constraints. Benchmarking must use the same splits, preprocessing rules, evaluation metrics, and computational budget.

6. Stacking and Blending

Stacking combines different model families through a second-level model. In a two-level architecture, base learners produce predictions, and a meta-learner uses those predictions as features. To avoid leakage, the meta-learner must be trained on out-of-fold predictions: each training record receives a prediction from a base model that did not train on that record.

A typical stack may combine logistic regression, a random forest, gradient boosting, and a neural network. The meta-learner may be a regularised linear model, which provides a relatively stable combination of complementary errors.

Blending is a simpler alternative in which base-model predictions on a holdout set are used to train the combiner. It is easier to implement but sacrifices training data and may produce a less reliable estimate when the holdout set is small.

Stacking increases engineering complexity and can overfit if the number of base models is large relative to the available data. It should be justified by out-of-sample improvement, not by complexity alone.

7. Evaluation and Hyperparameter Tuning

A reliable workflow separates model development from final assessment. A common structure is:

1. Training set for fitting.

2. Validation procedure for model and hyperparameter selection.

3. Locked test set for final performance estimation.

For grouped, temporal, spatial, or user-level data, ordinary random cross-validation may be invalid. Use group-aware or time-aware splits when future observations, users, devices, or locations must not leak into training.

For classification, accuracy can be misleading under class imbalance. Relevant measures include precision, recall, F1, balanced accuracy, ROC-AUC, precision–recall AUC, log loss, and calibration error. The metric should reflect the operational cost of false positives and false negatives. For regression, use MAE, RMSE, and problem-specific measures. RMSE penalises large errors more heavily than MAE.

Probability calibration is distinct from discrimination. A model may rank cases well while producing poorly calibrated probabilities. Platt scaling, isotonic regression, or calibrated cross-validation can be used, but calibration must be fitted without contaminating the evaluation set.

Bayesian optimisation, random search, and successive-halving strategies can be more efficient than exhaustive grids. The tuning process should include preprocessing, feature selection, resampling, and calibration within the cross-validation procedure. Early stopping is useful, but the stopping set must not become an indirect substitute for the final test set.

8. Feature Importance and Model Interpretation

Interpretation has several meanings: global variable influence, local explanation, causal effect, and operational reasoning. Predictive importance does not establish causality.

8.1 Impurity importance

Impurity importance sums the reduction in node impurity attributable to a feature across a tree ensemble. It is fast but can favour continuous variables and high-cardinality categorical variables. It can also distribute importance misleadingly among correlated predictors.

8.2 Permutation importance

Permutation importance measures the performance decrease after randomly permuting a feature in validation data. If the score deteriorates substantially, the feature carries predictive information. With correlated features, permuting one feature may show low importance because another correlated feature substitutes for it. Grouped permutation or conditional importance can address this issue.

8.3 Partial dependence and accumulated local effects

Partial dependence estimates the average model response as a feature varies while other features are marginalised over. It can be misleading when the feature combinations created by the procedure are unrealistic. Accumulated local effects are often more reliable under feature dependence because they use local changes within observed regions.

8.4 SHAP explanations

SHAP values allocate a prediction relative to a baseline using cooperative-game-theoretic contributions. Tree-specific algorithms can calculate them efficiently. However, the interpretation depends on the background distribution and on assumptions about feature dependence. A SHAP value explains the model’s prediction, not the real-world causal effect of changing a variable.

For high-stakes use, explanations should be triangulated with domain knowledge, stability analysis, counterfactual plausibility, and subgroup performance analysis.

9. Illustrative Case: Credit-Card Fraud Detection

Background

This illustrative case concerns a payment provider processing millions of card transactions. Fraud is rare, labels arrive with delay, and fraud patterns change over time.

Problem

The provider wants to identify suspicious transactions for manual review while limiting customer disruption. A false negative creates financial loss; a false positive may decline a legitimate payment and damage customer trust.

Analysis

Candidate variables include transaction amount, merchant category, time since prior transaction, device history, geographic consistency, account age, and velocity features. Several variables are time-dependent, so random row-wise splitting could place future information in training and produce optimistic results. The data are divided chronologically, with an additional group-aware check for customer-level leakage.

The baseline is a regularised logistic regression. A random forest captures nonlinearities, while a gradient-boosted model captures interactions such as unusual amount combined with a new device and rapid geographic movement. Class weighting and threshold optimisation are considered because fraud prevalence is low.

Approach and solution

The team uses a time-based validation scheme, evaluates precision–recall AUC and recall at a fixed review capacity, and calibrates probabilities on validation data. Hyperparameters include tree depth, learning rate, number of boosting rounds, row subsampling, and minimum leaf size. Early stopping is based only on the validation period.

Permutation importance is computed separately by time period. SHAP summaries are reviewed by fraud analysts, who discover that a seemingly powerful feature is a proxy for a particular region. The feature is retained only after a fairness and business review, and a constrained model excluding the proxy is compared with the original.

Outcome

The boosted model improves recall at the available review capacity over the baseline, but performance declines in a later period because fraud behaviour changes. The provider therefore adopts drift monitoring, monthly threshold review, and periodic retraining rather than treating the initial model as permanent.

Learning points

The case demonstrates that algorithm selection alone does not solve the operational problem. Temporal validation, leakage control, cost-sensitive thresholding, calibration, interpretability, fairness review, and monitoring are equally important.

10. Challenges, Governance and Best Practices

Tree ensembles can encode historical discrimination, exploit proxy variables, and obscure responsibility behind complex predictions. In regulated applications, documentation should cover data provenance, feature definitions, training dates, validation design, model version, intended use, known limitations, and approval decisions.

Important governance practices include:

• prohibit target leakage and post-outcome features;
• preserve an untouched temporal or external test set;
• assess performance across relevant demographic and operational groups;
• monitor calibration and error rates, not only aggregate accuracy;
• document human override and escalation procedures;
• protect sensitive data and restrict explanation outputs that could expose personal information;
• test robustness to missingness, drift, adversarial manipulation, and distribution shift;
• establish rollback and incident-response procedures.

Fairness metrics can conflict, particularly when base rates differ across groups. No single fairness measure is universally correct; the chosen criterion must be justified by the application, legal context, and stakeholder impact. Feature removal alone does not guarantee fairness because proxies may remain.

Best practice is to begin with a transparent baseline, use a leakage-resistant pipeline, tune only with an appropriate validation design, compare several model families, calibrate when probabilities drive decisions, interpret using multiple methods, and monitor after deployment.

Contemporary Developments

Current research and industry practice increasingly focus on histogram-based boosting, categorical feature algorithms, monotonic constraints, missingness-aware learning, distributed training, uncertainty estimation, and explainability under feature dependence. Monotonic constraints can encode domain knowledge, such as requiring predicted risk not to decrease as debt burden increases, although constraints must be validated carefully because an incorrect constraint can reduce accuracy or create misleading behaviour.

Research also examines probabilistic boosting, conformal prediction for distribution-free prediction intervals or sets, robust learning under distribution shift, and hybrid systems combining tree models with embeddings for high-cardinality entities. These developments do not remove the need for sound statistical validation; they make experimental design more important.

Chapter Summary

Decision trees recursively partition the feature space and produce interpretable piecewise-constant predictions. Classification trees commonly use entropy or Gini impurity, while regression trees minimise within-leaf loss. Tree depth, leaf size, pruning, and feature restrictions control the bias–variance trade-off.

Bagging reduces variance by averaging independently trained models. Random forests add feature subsampling to reduce correlation among trees. Boosting builds an additive model sequentially, and gradient boosting fits new learners to negative loss gradients. Learning rate, number of rounds, tree complexity, subsampling, regularisation, and early stopping jointly determine performance.

XGBoost, LightGBM, and CatBoost provide efficient and specialised gradient-boosting implementations. Stacking combines out-of-fold predictions from heterogeneous models, but requires careful leakage control. Evaluation must reflect temporal, group, class-imbalance, calibration, and operational considerations. Feature importance and explanation methods are useful but do not establish causality. Responsible deployment requires fairness analysis, documentation, monitoring, drift management, and human governance.

Key Terms

Decision tree: A recursive partitioning model that assigns predictions to terminal regions.

Leaf: A terminal node containing the prediction for observations reaching it.

Entropy: An impurity measure based on the negative logarithm of class probabilities.

Gini impurity: One minus the sum of squared class proportions.

Information gain: Reduction in impurity produced by a split.

Pruning: Removal of tree branches to reduce complexity.

Bagging: Averaging or voting across models trained on bootstrap samples.

Bootstrap sample: A sample drawn with replacement from the observed data.

Random forest: An ensemble of bootstrap-trained trees with random feature selection.

Out-of-bag estimate: Performance estimated using observations omitted from a tree’s bootstrap sample.

Boosting: Sequential construction of an ensemble in which later models address earlier errors.

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

Learning rate: The shrinkage factor applied to each new boosting contribution.

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

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

Calibration: Agreement between predicted probabilities and observed frequencies.

Permutation importance: Performance change caused by permuting a feature.

SHAP value: A model-specific contribution assigned to a feature relative to a baseline prediction.

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

Concept drift: Change over time in the relationship between inputs and the target.

Review Questions

Short Answer Questions

1. What is the purpose of Gini impurity in a classification tree?

2. How does random feature selection reduce correlation among random-forest trees?

3. Distinguish bagging from boosting.

4. Why must stacking use out-of-fold predictions for training its meta-learner?

5. What is the difference between discrimination and probability calibration?

Long Answer Questions

1. Explain the construction of a decision tree and discuss the principal methods for controlling its complexity.

2. Derive the gradient-boosting update conceptually and explain the roles of loss function, learning rate, and weak learner.

3. Compare random forests, gradient boosting, and stacking in terms of bias, variance, computational cost, and interpretability.

4. Discuss impurity importance, permutation importance, partial dependence, accumulated local effects, and SHAP explanations.

5. Design a complete validation and governance strategy for a high-stakes tabular prediction system.

Analytical / Application Questions

1. A classification node contains 12 observations, 9 positive and 3 negative. Calculate its Gini impurity and explain what a value of zero would mean.

2. You are given transaction data with delayed fraud labels and repeated customers. Design a leakage-resistant training, validation, and testing scheme.

3. A boosted model has excellent ROC-AUC but poor calibration and declining performance in recent months. Analyse possible causes and propose remediation steps.

Multiple Choice Questions with Answers

Question 1

For a node containing class proportions 0.6 and 0.4, what is its Gini impurity?

A. 0.24

B. 0.40

C. 0.48

D. 0.60

Correct Answer: C. 0.48

Question 2

Which method primarily reduces variance by averaging independently trained models on bootstrap samples?

A. Bagging

B. Gradient descent

C. Pruning

D. Stacking

Correct Answer: A. Bagging

Question 3

In gradient boosting, a new learner is generally fitted to what quantity?

A. Random labels

B. Negative gradients of the loss

C. The test-set predictions

D. Feature variances only

Correct Answer: B. Negative gradients of the loss

Question 4

What is the main purpose of a learning rate in gradient boosting?

A. To select the class threshold automatically

B. To scale the contribution of each new learner

C. To remove missing values

D. To increase the number of features

Correct Answer: B. To scale the contribution of each new learner

Question 5

Why are out-of-fold predictions required when training a stacking meta-learner?

A. To guarantee all base models are identical

B. To prevent the meta-learner from using in-sample base predictions

C. To eliminate the need for a test set

D. To convert regression into classification

Correct Answer: B. To prevent the meta-learner from using in-sample base predictions

Question 6

Which feature-importance method measures the change in validation performance after randomly shuffling a feature?

A. Permutation importance

B. Entropy

C. Cost-complexity pruning

D. Bootstrap sampling

Correct Answer: A. Permutation importance

Question 7

Which validation design is most appropriate when future observations must not influence training?

A. Randomly duplicate the latest observations

B. Chronological or time-aware splitting

C. Training evaluation only

D. Shuffle labels before splitting

Correct Answer: B. Chronological or time-aware splitting

Question 8

What is a major limitation of impurity-based feature importance?

A. It cannot be computed for trees

B. It is always causal

C. It can favour continuous or high-cardinality variables

D. It requires calibrated probabilities

Correct Answer: C. It can favour continuous or high-cardinality variables

Question 9

Which framework is particularly designed to handle categorical variables using ordered statistical procedures?

A. CatBoost

B. Ordinary least squares

C. PCA

D. K-means

Correct Answer: A. CatBoost

Question 10

A model has strong ranking performance but predicted probabilities do not match observed frequencies. Which property is deficient?

A. Calibration

B. Bootstrap diversity

C. Tree depth

D. Feature scaling

Correct Answer: A. Calibration