Subsampling Techniques (Stochastic Gradient Boosting)

The standard Gradient Boosting algorithm iteratively fits new trees to the pseudo-residuals of the model's current predictions. However, this approach can be susceptible to overfitting, particularly if individual trees are allowed to grow deep or if many boosting rounds are performed. To counteract this, introducing randomness is a common strategy to enhance the stability and generalization of machine learning models. A similar concept can be effectively applied to Gradient Boosting, leading to a variation often called Stochastic Gradient Boosting (SGB), a technique first introduced by Friedman.

Instead of using the entire training dataset to compute the pseudo-residuals and fit each new base learner (tree), SGB introduces randomness by subsampling the data at each iteration. This modification serves two primary purposes: improving generalization by reducing variance and potentially speeding up computation.

There are two main ways subsampling is commonly implemented in GBM frameworks:

Row Subsampling

This is the most common form associated with the term "Stochastic Gradient Boosting". Before fitting each new tree $h_m(x)$, a random fraction of the training instances (rows) is selected without replacement. Let's say the chosen fraction is $\eta_{subsample}$ (often controlled by a parameter named subsample in libraries like Scikit-learn). Only this subset of $N \times \eta_{subsample}$ samples is used to:

1. Calculate the pseudo-residuals for the selected instances based on the current ensemble $F_{m-1}(x)$.
2. Fit the new decision tree $h_m(x)$ using only these selected instances and their corresponding pseudo-residuals.

The pseudo-residuals for the unselected instances are not directly used for fitting tree $m$.

Impact:

• Regularization: Each tree sees a slightly different subset of the data, making the overall model less likely to perfectly memorize the training set noise or outliers. This reduces the variance of the final model.
• Computation: Fitting a tree on a smaller dataset is computationally faster.
• Interaction with Shrinkage: Subsampling often works effectively in conjunction with a small learning rate (shrinkage). The randomness introduced by subsampling helps stabilize the learning process when individual tree contributions are small.

A common range for the subsample parameter is between 0.5 and 0.8. Setting subsample=1.0 recovers the original deterministic GBM algorithm for row selection. Using a value less than 1.0 introduces stochasticity. Too small a fraction might hinder the learning process, increasing bias or requiring significantly more trees.

Row subsampling in Stochastic Gradient Boosting. At each iteration (m, m+1, ...), a different random subset of training instances is used to compute residuals and fit the next tree.

Column Subsampling (Feature Subsampling)

In addition to subsampling rows, we can also subsample features (columns) when constructing each tree. This is analogous to the feature sampling commonly used in Random Forests. Before finding the best split at each node (or sometimes, just once per tree), a random subset of features is considered.

In Scikit-learn's GradientBoostingClassifier and GradientBoostingRegressor, this is controlled by the max_features parameter.

Impact:

• Regularization: Prevents the model from relying too heavily on a small number of potentially dominant features. Encourages diversity among the trees and improves robustness.
• Computation: Reduces the search space for the best split at each node, which can significantly speed up training, especially for datasets with many features.

The max_features parameter can typically be set as:

• An integer: Use exactly that many features.
• A float (fraction): Use max_features * n_features features.
• Specific strings: Like 'sqrt' or 'log2'.

Using max_features=None or max_features=n_features means all features are considered, disabling column subsampling.

Combining Subsampling Techniques

Row and column subsampling are not mutually exclusive; they can be used together. Combining them provides a powerful regularization mechanism and can further improve computational efficiency. For instance, setting subsample=0.8 and max_features=0.8 means each tree is built using 80% of the rows and considers 80% of the features when finding splits.

These techniques transform the deterministic GBM into a stochastic algorithm. While introducing randomness might seem counter-intuitive in an optimization process, it often leads to models that generalize better to unseen data by preventing overfitting and exploring a more diverse set of weak learners during the boosting process. Both subsample and max_features become important hyperparameters to tune during model development, alongside the learning rate (learning_rate) and tree complexity parameters (max_depth, min_samples_split, etc.). The relationship between these parameters is significant; for example, lower subsampling rates might necessitate more boosting iterations (n_estimators) or adjustments to the learning rate.