Page 1 – Decision Trees: Structure, Splitting, and Training

1.1 Motivation: Why Trees?

Decision trees represent predictive models as hierarchical structures, where internal nodes correspond to questions about feature values and leaves correspond to predictions. Trees are:

• Interpretable: mimic human decision processes.
• Non-linear: capture complex interactions between features.
• Versatile: work for regression and classification.
• Invariant to scaling: do not require feature normalisation.
• Robust to irrelevant features (especially when pruned).

1.2 Structure of a Decision Tree

A decision tree consists of:

• Root node – first splitting condition.
• Internal nodes – further splits.
• Branches – outcomes of decisions.
• Leaf nodes – predicted value or class.

For classification, each leaf stores a class label. For regression, each leaf stores a numeric value (often the average of points in the leaf).

1.3 Splitting Criteria

The core of tree-building is selecting the best feature and threshold to split the data at each node. Common criteria:

Classification

• Gini Impurity

  G = Σ pk (1 − pk)

• Entropy

  H = − Σ pk log₂(pk)

Regression

• Variance reduction
• Mean squared error reduction

1.4 Greedy Recursive Partitioning

Trees are trained via a greedy algorithm known as recursive binary splitting. At each node:

1. Evaluate all possible feature–threshold splits.
2. Select the split that produces the largest purity improvement.
3. Recursively split resulting subsets.
4. Stop when a stopping criterion is triggered.

1.5 Stopping Criteria

To avoid extremely deep or overfitted trees, training stops when:

• Maximum depth is reached.
• Number of samples per leaf falls below a threshold.
• Purity improvement becomes negligible.
• Minimum number of samples per split is violated.

1.6 Tree Pruning

Overly deep trees overfit the training data. Cost-complexity pruning removes nodes that do not provide sufficient improvement relative to their complexity.

Cost(T) = Error(T) + α × (# of leaves)

Tuning α controls underfitting vs. overfitting.

Page 2 – Random Forests: Bagging, Voting, and Variance Reduction

2.1 Motivation for Ensembles

Individual decision trees have high variance: small changes in data can lead to vastly different trees. Ensemble learning reduces variance by aggregating multiple models.

2.2 Bagging (Bootstrap Aggregation)

Bagging constructs multiple datasets via random sampling with replacement:

D₁, D₂, …, DB

For each dataset, train a decision tree. The final prediction is obtained via:

• Majority vote (classification)
• Mean (regression)

2.3 Random Forest Algorithm

Random Forests extend bagging with feature randomness:

• At each node, only a random subset of features is considered.
• This decorrelates trees and enhances ensemble diversity.

2.4 Hyperparameters

• Number of trees (n_estimators).
• Maximum tree depth.
• Minimum samples per split/leaf.
• Max features (e.g., sqrt(d), log₂(d)).

2.5 Out-of-Bag Error

Each tree is trained on roughly 63% of the data (bootstrap sample). The remaining 37%—the out-of-bag (OOB) data—can be used as a built-in validation set.

2.6 Feature Importance

Random forests provide:

• Gini importance (split-based).
• Permutation importance (model-agnostic).

These measures help interpret the influence of different features.

Page 3 – Gradient Boosting Machines (GBM)

3.1 Motivation: Sequential Ensembles

Unlike bagging, which trains trees independently, boosting trains trees sequentially. Each new tree attempts to correct errors of previous trees.

3.2 Additive Model

Gradient boosting builds a model as:

F₀(x) = initial prediction
Fₘ(x) = Fₘ₋₁(x) + η × hₘ(x)

where:

• η is the learning rate.
• hₘ(x) is the new tree (weak learner).

3.3 Gradient Descent View

For a loss function L(y, F(x)), boosting fits each new tree to the gradient of the loss with respect to predictions:

Residual = − ∂L / ∂F(x)

3.4 Advantages of Boosting

• High predictive accuracy.
• Handles mixed feature types.
• Works well for small and large datasets.
• Allows customised loss functions.

3.5 Hyperparameters

• Number of trees.
• Learning rate (η).
• Tree depth for weak learners (typically 3–6).
• Subsample rate for stochastic boosting.

3.6 Popular Implementations

• XGBoost (Extreme Gradient Boosting).
• LightGBM (histogram-based optimisations).
• CatBoost (handles categorical features naturally).

3.7 Overfitting and Regularisation

Boosted trees can overfit if too deep or too numerous. Regularisation strategies include:

• Shrinkage (small η).
• Tree depth limits.
• Early stopping.
• Subsampling rows and columns.

Page 4 – Comparing Decision Trees, Random Forests, and Boosting

4.1 Decision Trees Summary

Pros:

• Interpretable.
• Handles non-linearity.
• No scaling required.
• Fast to train on moderate datasets.

Cons:

• High variance.
• Can overfit without pruning.
• Piecewise constant predictions.

4.2 Random Forests Summary

Pros:

• Strong performance out-of-the-box.
• Reduces variance significantly.
• Robust to noise.
• Good for feature importance.

Cons:

• Less interpretable than a single tree.
• Large models can be slow to predict.

4.3 Gradient Boosting Summary

Pros:

• State-of-the-art performance on structured/tabular data.
• Highly flexible with custom losses.
• Interpretable via importance and SHAP values.

Cons:

• Sensitive to hyperparameters.
• Easily overfits if not tuned.
• Training can be compute-intensive.

4.4 Choosing the Right Method

A typical guideline:

• Start with Decision Trees for interpretability.
• Use Random Forests for robust baseline performance.
• Use Gradient Boosting (XGBoost/LightGBM) for maximum accuracy.

4.5 Interpretability Tools

• Feature importance (permutation > Gini).
• SHAP values (model-agnostic).
• Partial dependence plots.
• Tree visualisation tools.

Page 5 – Practical Workflow, Tuning, and Best Practices

5.1 Data Preparation for Tree Models

Trees are robust and require minimal preprocessing:

• No feature scaling required.
• Handle mixed data types.
• Insensitive to monotonic transformations.

However, practitioners should still consider:

• Imputing missing values.
• Removing constant or near-constant features.
• Encoding categorical variables (depending on implementation).

5.2 Hyperparameter Tuning

Tuning trees and ensembles usually involves:

• Maximum depth.
• Minimum samples per leaf.
• Maximum number of features per split.
• Learning rate (for boosting).
• Number of trees.
• Subsample ratios.

Tools:

• Grid search.
• Random search.
• Bayesian optimisation (Optuna, Hyperopt).

5.3 Preventing Overfitting

• Prune trees.
• Restrict tree depth.
• Use subsampling in boosting.
• Use small learning rates.
• Apply early stopping.

5.4 Model Evaluation

Evaluate ensembles using:

• Train/validation/test splits.
• k-fold cross-validation.
• ROC–AUC and PR–AUC for imbalanced data.
• Calibration curves for probability assessment.

5.5 Practical Notes for Deployment

Although tree ensembles are powerful, they require considerations at deployment:

• Model size can be large → consider model compression.
• Prediction latency may be high → use optimised libraries.
• Consistency between training and inference pipelines is crucial.
• Monitor feature drift and importance drift over time.

5.6 Summary

In this module, we covered:

• Decision trees and their splitting mechanics.
• Random forests and bagging for variance reduction.
• Gradient boosting machines for high accuracy.
• Model selection guidelines.
• Interpretability techniques.
• Deployment considerations.

In Module 4, we will move into Neural Networks and Deep Learning, extending the concept of learnable functions to highly flexible, multi-layered architectures.