Gradient boosting

The idea of gradient boosting originated in the observation by Leo Breiman that boosting can be interpreted as an optimization algorithm on a suitable cost function.[4] Explicit regression gradient boosting algorithms were subsequently developed, by Jerome H. Friedman,[5][6] simultaneously with the more general functional gradient boosting perspective of Llew Mason, Jonathan Baxter, Peter Bartlett and Marcus Frean.[7][8] The latter two papers introduced the view of boosting algorithms as iterative functional gradient descent algorithms. That is, algorithms that optimize a cost function over function space by iteratively choosing a function (weak hypothesis) that points in the negative gradient direction. This functional gradient view of boosting has led to the development of boosting algorithms in many areas of machine learning and statistics beyond regression and classification.

(This section follows the exposition of gradient boosting by Cheng Li.[9])

Like other boosting methods, gradient boosting combines weak "learners" into a single strong learner in an iterative fashion. It is easiest to explain in the least-squares regression setting, where the goal is to "teach" a model ${\displaystyle F}$ to predict values of the form ${\displaystyle {\hat {y}}=F(x)}$ by minimizing the mean squared error ${\displaystyle {\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}}$, where ${\displaystyle i}$ indexes over some training set of size ${\displaystyle n}$ of actual values of the output variable ${\displaystyle y}$:

• ${\displaystyle {\hat {y}}_{i}=}$ the predicted value ${\displaystyle F(x_{i})}$
• ${\displaystyle y_{i}=}$ the observed value
• ${\displaystyle n=}$ the number of samples in ${\displaystyle y}$

Now, let us consider a gradient boosting algorithm with ${\displaystyle M}$ stages. At each stage ${\displaystyle m}$ (${\displaystyle 1\leq m\leq M}$) of gradient boosting, suppose some imperfect model ${\displaystyle F_{m}}$ (for low ${\displaystyle m}$, this model may simply return ${\displaystyle {\hat {y}}_{i}={\bar {y}}}$, where the RHS is the mean of ${\displaystyle y}$). In order to improve ${\displaystyle F_{m}}$, our algorithm should add some new estimator, ${\displaystyle h_{m}(x)}$. Thus,

${\displaystyle F_{m+1}(x_{i})=F_{m}(x_{i})+h_{m}(x_{i})=y_{i}}$

or, equivalently,

${\displaystyle h_{m}(x_{i})=y_{i}-F_{m}(x_{i})}$.

Therefore, gradient boosting will fit ${\displaystyle h_{m}}$ to the residual ${\displaystyle y_{i}-F_{m}(x_{i})}$. As in other boosting variants, each ${\displaystyle F_{m+1}}$ attempts to correct the errors of its predecessor ${\displaystyle F_{m}}$. A generalization of this idea to loss functions other than squared error, and to classification and ranking problems, follows from the observation that residuals ${\displaystyle h_{m}(x_{i})}$ for a given model are proportional to the negative gradients of the mean squared error (MSE) loss function (with respect to ${\displaystyle F(x_{i})}$):

${\displaystyle L_{\rm {MSE}}={\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-F(x_{i})\right)^{2}}$

${\displaystyle -{\frac {\partial L_{\rm {MSE}}}{\partial F(x_{i})}}={\frac {2}{n}}(y_{i}-F(x_{i}))={\frac {2}{n}}h_{m}(x_{i})}$.

So, gradient boosting could be specialized to a gradient descent algorithm, and generalizing it entails "plugging in" a different loss and its gradient.

In many supervised learning problems there is an output variable y and a vector of input variables x, related to each other with some probabilistic distribution. The goal is to find some function ${\displaystyle {\hat {F}}(x)}$ that best approximates the output variable from the values of input variables. This is formalized by introducing some loss function ${\displaystyle L(y,F(x))}$ and minimizing it in expectation:

${\displaystyle {\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))]}$.

The gradient boosting method assumes a real-valued y. It seeks an approximation ${\displaystyle {\hat {F}}(x)}$ in the form of a weighted sum of M functions ${\displaystyle h_{m}(x)}$ from some class ${\displaystyle {\mathcal {H}}}$, called base (or weak) learners:

${\displaystyle {\hat {F}}(x)=\sum _{m=1}^{M}\gamma _{m}h_{m}(x)+{\mbox{const}}}$.

We are usually given a training set ${\displaystyle \{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$ of known sample values of x and corresponding values of y. In accordance with the empirical risk minimization principle, the method tries to find an approximation ${\displaystyle {\hat {F}}(x)}$ that minimizes the average value of the loss function on the training set, i.e., minimizes the empirical risk. It does so by starting with a model, consisting of a constant function ${\displaystyle F_{0}(x)}$, and incrementally expands it in a greedy fashion:

${\displaystyle F_{0}(x)={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},\gamma )}}}$,

${\displaystyle F_{m}(x)=F_{m-1}(x)+\left({\underset {h_{m}\in {\mathcal {H}}}{\operatorname {arg\,min} }}\left[{\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}\right]\right)(x)}$,

for ${\displaystyle m\geq 1}$, where ${\displaystyle h_{m}\in {\mathcal {H}}}$ is a base learner function.

Unfortunately, choosing the best function ${\displaystyle h_{m}}$ at each step for an arbitrary loss function L is a computationally infeasible optimization problem in general. Therefore, we restrict our approach to a simplified version of the problem.

The idea is to apply a steepest descent step to this minimization problem (functional gradient descent).

The basic idea behind the steepest descent is to find a local minimum of the loss function by iterating on ${\displaystyle F_{m-1}(x)}$. In fact, the local maximum-descent direction of the loss function is the negative gradient.[10]

Hence, moving a small amount ${\displaystyle \gamma }$ such that the linear approximation remains valid:

${\displaystyle F_{m}(x)=F_{m-1}(x)-\gamma \sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}}$

where ${\displaystyle \gamma >0}$. For small ${\displaystyle \gamma }$, this implies that ${\displaystyle L(y_{i},F_{m}(x_{i}))\leq L(y_{i},F_{m-1}(x_{i}))}$.

Furthermore, we can optimize ${\displaystyle \gamma }$ by finding the ${\displaystyle \gamma }$ value for which the loss function has a minimum:

${\displaystyle \gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},F_{m}(x_{i}))}}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}}.}$

If we considered the continuous case, i.e., where ${\displaystyle {\mathcal {H}}}$ is the set of arbitrary differentiable functions on ${\displaystyle \mathbb {R} }$, we would update the model in accordance with the following equations

${\displaystyle F_{m}(x)=F_{m-1}(x)-\gamma _{m}\sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}}$

where ${\displaystyle \gamma _{m}}$ is the step length, defined as

$${\displaystyle \gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}}.}$$

In the discrete case however, i.e. when the set ${\displaystyle {\mathcal {H}}}$ is finite, we choose the candidate function h closest to the gradient of L for which the coefficient γ may then be calculated with the aid of line search on the above equations. Note that this approach is a heuristic and therefore doesn't yield an exact solution to the given problem, but rather an approximation. In pseudocode, the generic gradient boosting method is:[5][2]

Gradient boosting is typically used with decision trees (especially CARTs) of a fixed size as base learners. For this special case, Friedman proposes a modification to gradient boosting method which improves the quality of fit of each base learner.

Generic gradient boosting at the m-th step would fit a decision tree ${\displaystyle h_{m}(x)}$ to pseudo-residuals. Let ${\displaystyle J_{m}}$ be the number of its leaves. The tree partitions the input space into ${\displaystyle J_{m}}$ disjoint regions ${\displaystyle R_{1m},\ldots ,R_{J_{m}m}}$ and predicts a constant value in each region. Using the indicator notation, the output of ${\displaystyle h_{m}(x)}$ for input x can be written as the sum:

${\displaystyle h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x),}$

where ${\displaystyle b_{jm}}$ is the value predicted in the region ${\displaystyle R_{jm}}$.[11]

Then the coefficients ${\displaystyle b_{jm}}$ are multiplied by some value ${\displaystyle \gamma _{m}}$, chosen using line search so as to minimize the loss function, and the model is updated as follows:

${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x),\quad \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})).}$

Friedman proposes to modify this algorithm so that it chooses a separate optimal value ${\displaystyle \gamma _{jm}}$ for each of the tree's regions, instead of a single ${\displaystyle \gamma _{m}}$ for the whole tree. He calls the modified algorithm "TreeBoost". The coefficients ${\displaystyle b_{jm}}$ from the tree-fitting procedure can be then simply discarded and the model update rule becomes:

${\displaystyle F_{m}(x)=F_{m-1}(x)+\sum _{j=1}^{J_{m}}\gamma _{jm}\mathbf {1} _{R_{jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma ).}$

Fitting the training set too closely can lead to degradation of the model's generalization ability. Several so-called regularization techniques reduce this overfitting effect by constraining the fitting procedure.

One natural regularization parameter is the number of gradient boosting iterations M (i.e. the number of trees in the model when the base learner is a decision tree). Increasing M reduces the error on training set, but setting it too high may lead to overfitting. An optimal value of M is often selected by monitoring prediction error on a separate validation data set. Besides controlling M, several other regularization techniques are used.

Another regularization parameter is the depth of the trees. The higher this value the more likely the model will overfit the training data.

Gradient boosting can be used in the field of learning to rank. The commercial web search engines Yahoo[16] and Yandex[17] use variants of gradient boosting in their machine-learned ranking engines. Gradient boosting is also utilized in High Energy Physics in data analysis. At the Large Hadron Collider (LHC), variants of gradient boosting Deep Neural Networks (DNN) were successful in reproducing the results of non-machine learning methods of analysis on datasets used to discover the Higgs boson.[18] Gradient boosting decision tree was also applied in earth and geological studies – for example quality evaluation of sandstone reservoir.[19]

The method goes by a variety of names. Friedman introduced his regression technique as a "Gradient Boosting Machine" (GBM).[5] Mason, Baxter et al. described the generalized abstract class of algorithms as "functional gradient boosting".[7][8] Friedman et al. describe an advancement of gradient boosted models as Multiple Additive Regression Trees (MART);[20] Elith et al. describe that approach as "Boosted Regression Trees" (BRT).[21]

A popular open-source implementation for R calls it a "Generalized Boosting Model",[13] however packages expanding this work use BRT.[22] Yet another name is TreeNet, after an early commercial implementation from Salford System's Dan Steinberg, one of researchers who pioneered the use of tree-based methods.[23] XGBoost is another popular modern implementation of the method with some extensions, like second-order optimization.

While boosting can increase the accuracy of a base learner, such as a decision tree or linear regression, it sacrifices intelligibility and interpretability.[1][24] For example, following the path that a decision tree takes to make its decision is trivial and self-explained, but following the paths of hundreds or thousands of trees is much harder. To achieve both performance and interpretability, some model compression techniques allow transforming an XGBoost into a single "born-again" decision tree that approximates the same decision function.[25] Furthermore, its implementation may be more difficult due to the higher computational demand.

• AdaBoost
• Random forest
• Catboost
• LightGBM
• XGBoost
• Decision tree learning

• Boehmke, Bradley; Greenwell, Brandon (2019). "Gradient Boosting". Hands-On Machine Learning with R. Chapman & Hall. pp. 221–245. ISBN 978-1-138-49568-5.

• How to explain gradient boosting
• Gradient Boosted Regression Trees
• LightGBM