Gradient boosting is a machine learning technique based on boosting in a functional space, where the target is pseudo-residuals instead of residuals as in traditional boosting. It gives a prediction model in the form of an ensemble of weak prediction models, i.e., models that make very few assumptions about the data, which are typically simple decision trees. When a decision tree is the weak learner, the resulting algorithm is called gradient-boosted trees; it usually outperforms random forest. As with other boosting methods, a gradient-boosted trees model is built in stages, but it generalizes the other methods by allowing optimization of an arbitrary differentiable loss function.
History 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. Explicit regression gradient boosting algorithms were subsequently developed, by Jerome H. Friedman, (in 1999 and later in 2001) simultaneously with the more general functional gradient boosting perspective of Llew Mason, Jonathan Baxter, Peter Bartlett and Marcus Frean. 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.
Informal introduction (This section follows the exposition by Cheng Li.) Like other boosting methods, gradient boosting combines weak "learners" into a single strong learner iteratively. It is easiest to explain in the least-squares regression setting, where the goal is to teach a model F {\displaystyle F} to predict values of the form y ^ = F ( x ) {\displaystyle {\hat {y}}=F(x)} by minimizing the mean squared error 1 n ∑ i ( y ^ i − y i ) 2 {\displaystyle {\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}} , where i {\displaystyle i} indexes over some training set of size n {\displaystyle n} of actual values of the output variable y {\displaystyle y} :
y ^ i = {\displaystyle {\hat {y}}_{i}=} the predicted value F ( x i ) {\displaystyle F(x_{i})}
y i = {\displaystyle y_{i}=} the observed value
n = {\displaystyle n=} the size of the sample, i.e. the number of observations in y {\displaystyle y}
If the algorithm has M {\displaystyle M} stages, at each stage m {\displaystyle m} ( 1 ≤ m ≤ M {\displaystyle 1\leq m\leq M} ), suppose some imperfect model F m {\displaystyle F_{m}} (for low m {\displaystyle m} , this model may simply predict y ^ i {\displaystyle {\hat {y}}_{i}} to be y ¯ {\displaystyle {\bar {y}}} , the mean of y {\displaystyle y} ). In order to improve F m {\displaystyle F_{m}} , our algorithm should add some new estimator, h m ( x ) {\displaystyle h_{m}(x)} . Thus,
F m + 1 ( x i ) = F m ( x i ) + h m ( x i ) = y i {\displaystyle F_{m+1}(x_{i})=F_{m}(x_{i})+h_{m}(x_{i})=y_{i}}
or, equivalently,
h m ( x i ) = y i − F m ( x i ) . {\displaystyle h_{m}(x_{i})=y_{i}-F_{m}(x_{i}).}
… excerpt ends here. Continue reading the full article.
