Gradient boosting · aiwiki.page

Gradient boosting is a machine learning method that constructs an ensemble by adding predictive models sequentially, each approximating a direction that reduces a chosen loss function. It is principally used in supervised learning for regression and classification. Although the framework permits different base learners, small decision trees are especially common. Tree-based versions are called gradient-boosted decision trees or gradient-boosted regression trees; “regression trees” describes their numerical outputs, even when the overall task is classification. The method combines stagewise model construction with optimization of prediction errors. (scikit-learn.org)

Development and underlying idea

Gradient boosting belongs to the broader family of boosting methods, which construct strong predictors by sequentially combining simpler models. Jerome H. Friedman’s October 2001 paper, Greedy function approximation: A gradient boosting machine, presented an influential general formulation linking stagewise additive expansions to steepest-descent optimization in function space. It developed algorithms for several regression losses and multiclass classification, with particular adaptations for regression trees. (doi.org)

The central distinction from ordinary parameter-based gradient descent is the object being updated. Rather than adjusting a fixed vector of coefficients, gradient boosting extends a prediction function by adding another component. At each stage, the negative gradient of the loss indicates desirable changes to current predictions. A base learner approximates these changes as a function of the input features, allowing the correction to apply beyond the observed examples. This interpretation places boosting within mathematical optimization while preserving its additive model structure. (doi.org)

Mathematical formulation

For training data $\{(x_i,y_i)\}_{i=1}^{n}$ , a standard scalar-output formulation begins with a constant predictor:

F_0(x)=\arg\min_c\sum_{i=1}^{n}L(y_i,c).

At iteration $m$ , it computes pseudo-residuals:

r_{im}= -\left. \frac{\partial L(y_i,f)}{\partial f} \right|_{f=F_{m-1}(x_i)}.

A learner $h_m(x)$ is fitted to these values. A step coefficient can then be selected through line search:

\rho_m=\arg\min_\rho \sum_{i=1}^{n} L\!\left(y_i,F_{m-1}(x_i)+\rho h_m(x_i)\right).

The ensemble is updated as

F_m(x)=F_{m-1}(x)+\nu\rho_m h_m(x),

where $\nu$ is a learning rate, also called a shrinkage factor. Tree implementations may optimize a separate correction in each terminal leaf rather than use one global coefficient. (scikit-learn.org)

For half-squared-error loss, the pseudo-residual is simply $y_i-F_{m-1}(x_i)$ ; this yields the familiar description of fitting successive trees to residual errors and minimizes the same objective as mean squared error. That description is not universal: other losses produce different derivative-based targets. Classification commonly uses logarithmic loss, related to cross-entropy, with additive scores transformed into probabilities. Huber loss provides a regression alternative that treats large errors differently from squared loss. (scikit-learn.org)

Tree structure and regularization

Tree learners divide feature space into regions and assign a numerical prediction to each leaf. Their depth or leaf count controls the complexity of each correction and the feature interactions it can represent. The ensemble’s capacity also depends on its number of stages, so shallow individual trees do not prevent overfitting when many corrections are accumulated. These interacting hyperparameters distinguish model construction from simply growing one large tree. (scikit-learn.org)

Common regularization mechanisms include shrinkage, limits on tree depth and leaf size, and random subsampling of examples or features. Smaller learning rates generally require more boosting stages. In stochastic gradient boosting, each stage uses a randomly selected fraction of the training observations; this can reduce variance while changing bias. Early stopping terminates training when performance on a validation set ceases to improve sufficiently. Cross-validation provides another way to compare configurations rather than relying on training loss alone. (scikit-learn.org)

Relationship to other ensembles

Unlike bagging and a conventional random forest, gradient boosting makes each successive learner depend on the current ensemble. Random forests aggregate diverse trees that can usually be trained independently; boosting builds a sequence of targeted corrections. This distinction affects both statistical behavior and computation: forest construction is readily parallelized across trees, whereas boosting stages ordinarily retain a sequential dependency. Nevertheless, split evaluation and other operations within a boosting stage can exploit parallel computing. (scikit-learn.org)

Implementations and applications

Several implementations extend the basic framework:

XGBoost, described by Tianqi Chen and Carlos Guestrin in 2016, combines a regularized tree objective with first- and second-order loss information. Its system design includes sparsity-aware split finding, approximate split proposals, and optimizations for memory access and distributed computation. (arxiv.org)
LightGBM, presented in a 2017 paper, introduced gradient-based one-side sampling and exclusive feature bundling to reduce computational work. Histogram-based tree construction further reduces the number of candidate split positions considered. (proceedings.neurips.cc)
CatBoost introduced ordered boosting and ordered categorical-feature statistics to address prediction shifts associated with reuse of target information. Its methods are especially relevant to categorical inputs and the data leakage risks of target-based feature encoding. (proceedings.neurips.cc)

Gradient-boosted trees are used for structured, tabular prediction, including sales forecasting, advertising response prediction, and classification. Ranking variants also appear in search systems. Large ensembles are harder to inspect than individual trees; feature-importance measures and response plots summarize their behavior, but do not provide a simple equivalent of one decision tree. Their predictive performance and computational cost depend on the dataset, objective, tree structure, and implementation rather than on the boosting label alone. (arxiv.org)