Guus Bouwens
← Writing & notes

FROM THE NOTEBOOK

Machine Learning Algorithms 4: Ensemble Methods

Ensemble methods are machine learning techniques that combine the predictions from multiple models to achieve better predictive performance than could be obtained from any of the constituent models alone. The core idea is that a diverse group of "weak learners" can come together to form a powerful "strong learner."

Foundational Concepts

The two most fundamental ensemble techniques are Bagging and Boosting. More advanced methods like Stacking build on these core ideas.

Bagging (Bootstrap Aggregating)

Bagging focuses on reducing variance and preventing overfitting. It works by training multiple models in parallel on different random subsets of the training data. These subsets are created through bootstrap sampling (sampling with replacement). The final prediction is made by aggregating the outputs of all models, typically by averaging (for regression) or majority voting (for classification).

Boosting

Boosting focuses on reducing bias and building highly accurate models. It works by training models sequentially, where each new model is trained to correct the errors made by its predecessors. In each iteration, the algorithm gives more weight to the data points that were misclassified by the previous models, forcing the new model to focus on the "hard" cases.

Stacking (Stacked Generalization)

Stacking is a more advanced technique that learns how to best combine the predictions from multiple models. It involves training a meta-model whose job is to take the predictions of several base models as input features and produce a final output.

Covered Algorithms

Random Forest

Random Forest is an ensemble learning method that operates by constructing a multitude of decision trees at training time. It is a classic example of bagging. To improve upon the variance reduction of standard bagging, Random Forest also introduces feature randomness.

Mathematical Framework

  1. Bootstrap Aggregation (Bagging): For a forest of B trees, B bootstrap samples are drawn from the original dataset. Each sample has the same size as the original dataset but is drawn with replacement. A separate decision tree is trained on each bootstrap sample.
  2. Feature Randomness: When building each tree, at each split, a random subset of m features is considered from the total p features. The best split is found only within this random subset. This decorrelates the trees in the forest, which is the key to reducing the variance of the final ensemble.
    • Typical value for m: √p for classification and p/3 for regression.

Prediction

Out-of-Bag (OOB) Error

A significant advantage of Random Forest is that it can provide an unbiased estimate of the generalization error without needing a separate validation set. Since each tree is trained on about 63.2% of the data, the remaining 36.8% (the "out-of-bag" samples) can be used to test its accuracy. The OOB error is the average error for each data point calculated using only the trees that did not have that data point in their bootstrap sample.

Advantages

Limitations

Extra Trees (Extremely Randomized Trees)

Extra Trees is an ensemble learning method that takes the randomization principle of Random Forest a step further. It introduces additional randomness in how splits are chosen in order to further decorrelate the trees, which can reduce variance and computational cost.

Key Differences from Random Forest

  1. No Bootstrap Sampling: Each tree is trained on the entire original training dataset, not a bootstrap sample. This helps to reduce bias.
  2. Randomized Splits: At each node, instead of searching for the optimal split point for a feature, a random split point is selected. Of these randomly generated splits, the one that yields the highest information gain is chosen.

Bias-Variance Trade-off

By using the whole dataset and randomizing splits, Extra Trees aim for a different bias-variance trade-off.

Gradient Boosting Machines (GBMs)

Gradient Boosting is a powerful ensemble technique based on the concept of boosting. It builds a prediction model in the form of an ensemble of weak prediction models, typically decision trees, in a stage-wise fashion. Unlike Random Forest, which builds trees independently, Gradient Boosting builds them sequentially.

Mathematical Framework

GBM is an additive model where each new tree is trained to correct the errors (residuals) of the previous ones. It generalizes boosting methods by allowing the optimization of an arbitrary differentiable loss function.

The core idea is to fit a new weak learner to the negative gradient of the loss function with respect to the current ensemble's prediction. This is analogous to performing gradient descent in a function space rather than a parameter space.

Algorithm Steps

  1. Initialize: Start with a simple initial model, often just the mean of the target variable.
  2. Iterate: For m = 1 to M (number of trees): a. Compute Pseudo-Residuals: Calculate the negative gradient of the loss function. For squared error loss, this is simply the residual (actual - predicted). b. Fit a Weak Learner: Train a decision tree h_m(x) on the pseudo-residuals. c. Update the Model: Add the new tree to the ensemble, scaled by a learning rate ν (shrinkage): F_m(x) = F_{m-1}(x) + ν * h_m(x)
  3. Final Model: The final prediction is the sum of the initial model and all the sequentially trained trees.

Advantages

Limitations

XGBoost (eXtreme Gradient Boosting)

XGBoost is an optimized and distributed gradient boosting library designed for high efficiency, flexibility, and portability. For a long time, it has been the dominant algorithm in machine learning competitions with tabular data.

Key Improvements over Standard GBM

LightGBM (Light Gradient Boosting Machine)

LightGBM is another high-performance gradient boosting framework that is known for its incredible speed and efficiency, especially on large datasets.

Key Innovations

CatBoost (Categorical Boosting)

CatBoost is a gradient boosting library developed by Yandex. Its primary advantage is its exceptional handling of categorical features.

Key Innovations

LinearBoost

LinearBoost is a boosting algorithm that uses linear classifiers as its base learners, in contrast to traditional boosting methods like XGBoost or LightGBM which use decision trees. It has been shown to outperform tree-based boosting methods on several benchmark datasets while also offering significantly faster training times.

EBM (Explainable Boosting Machine)

EBM is a "glass-box" model developed by Microsoft Research that combines the high accuracy of modern boosting techniques with the interpretability of traditional statistical models like Generalized Additive Models (GAMs).

How it works

EBM learns a separate function f() for each feature using gradient boosting. The final prediction is the sum of these individual feature functions (and optional pairwise interaction terms): g(E[y]) = β₀ + Σ fᵢ(xᵢ) + Σ fᵢⱼ(xᵢ, xⱼ)

Because each feature's contribution to the prediction is isolated in its own function, the model is completely interpretable. You can visualize the f() for any feature to understand exactly how it impacts the model's output across its entire range of values. EBM automatically detects and includes important pairwise interaction terms. It achieves performance competitive with state-of-the-art methods like XGBoost while being fully transparent.

Stacking Ensembles

Stacking (or Stacked Generalization) is an ensemble technique that learns how to best combine the predictions from multiple different models. It involves training a meta-model to make a final prediction based on the predictions of several base models.

How it works

  1. Split the data: The training data is split into folds (similar to cross-validation).
  2. Train Base Models: A set of diverse "Level 0" base models (e.g., a Random Forest, an SVM, a LightGBM) are trained on the folds of the training data.
  3. Create a New Dataset: The predictions made by these base models on the hold-out folds are collected. These "out-of-fold" predictions become the input features for the meta-model.
  4. Train a Meta-Model: A "Level 1" meta-model (e.g., Logistic Regression or another GBM) is trained on this new dataset. Its job is to learn the optimal weights to assign to the predictions of each base model.

Voting Classifiers

A Voting Classifier is a simple yet powerful ensemble model that combines the predictions from multiple different models. It makes a final prediction based on a "voting" system.

Neural Oblivious Decision Ensembles (NODE)

NODE is a machine learning model that combines the strengths of decision trees and deep neural networks. It learns hierarchical, non-linear transformations of the input data by using "oblivious" decision trees (where all nodes at the same level use the same feature and split point) within a differentiable architecture. This allows the entire ensemble to be trained end-to-end with gradient descent, making it competitive with gradient boosting methods on tabular data.

All writing