Gradient boosting is a machine learning technique for regression problems, which produces a prediction model in the form of an ensemble of weak prediction models, typically decision trees. It builds the model in a stage-wise fashion like other boosting methods do, and it generalizes them by allowing optimization of an arbitrary differentiable loss function. The gradient boosting method can also be used for classification problems by reducing them to regression with a suitable loss function.
The method was invented by Jerome H. Friedman in 1999 and was published in a series of two papers, the first of which introduced the method, and the second one described an important tweak to the algorithm, which improves its accuracy and performance.
In many supervised learning problems one has an output variable y and a vector of input variables x connected together via a joint probability distribution P(x, y). Using a training set of known values of x and corresponding values of y, the goal is to find an approximation to a function that minimizes the expected value of some specified loss function L(y, F(x)):
Gradient boosting method assumes a real-valued y and seeks an approximation in the form of a weighted sum of functions from some class , called base (or weak) learners:
In accordance with the empirical risk minimization principle, the method tries to find an approximation that minimizes the average value of the loss function on the training set. It does so by starting with a model, consisting of a constant function , and incrementally expanding it in a greedy fashion:
where f is restricted to be a function from the class of base learner functions.
However, the problem of choosing at each step the best f for an arbitrary loss function L is a hard optimization problem in general, and so we'll "cheat" by solving a much easier problem instead.
The idea is to apply a steepest descent step to this minimization problem. If we only cared about predictions at the points of the training set, and f were unrestricted, we'd update the model per the following equation, where we view L(y, f) not as a functional of f, but as a function of a vector of values :
But as f must come from a restricted class of functions (that's what allows us to generalize), we'll just choose the one that most closely approximates the gradient of L. Having chosen f, the multiplier γ is then selected using line search just as shown in the second equation above.
Gradient tree boosting
Gradient boosting is typically used with decision trees (especially CART trees) 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 to pseudo-residuals. Let be the number of its leaves. The tree partitions the input space into disjoint regions and predicts a constant value in each region. Using the indicator notation, the output of for input x can be written as the sum:
where is the value predicted in the region .
Then the coefficients are multiplied by some value , chosen using line search so as to minimize the loss function, and the model is updated as follows:
Friedman proposes to modify this algorithm so that it chooses a separate optimal value for each of the tree's regions, instead of a single for the whole tree. He calls the modified algorithm "TreeBoost". The coefficients from the tree-fitting procedure can be then simply discarded and the model update rule becomes:
Size of trees
, the number of terminal nodes in trees, is the method's parameter which can be adjusted for a data set at hand. It controls the maximum allowed level of interaction between variables in the model. With (decision stumps), no interaction between variables is allowed. With the model may include effects of the interaction between up to two variables, and so on.
Hastie et al. comment that typically work well for boosting and results are fairly insensitive to the choice of in this range, is insufficient for many applications, and is unlikely to be required.
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.
An important part of gradient boosting method is regularization by shrinkage which consists in modifying the update rule as follows:
where parameter is called the "learning rate".
Empirically it has been found that using small learning rates (such as ) yields dramatic improvements in model's generalization ability over gradient boosting without shrinking (). However, it comes at the price of increasing computational time both during training and querying: lower learning rate requires more iterations.
Stochastic gradient boosting
Soon after the introduction of gradient boosting Friedman proposed a minor modification to the algorithm, motivated by Breiman's bagging method. Specifically, he proposed that at each iteration of the algorithm, a base learner should be fit on a subsample of the training set drawn at random without replacement. Friedman observed a substantial improvement in gradient boosting's accuracy with this modification.
Subsample size is some constant fraction f of the size of the training set. When f = 1, the algorithm is deterministic and identical to the one described above. Smaller values of f introduce randomness into the algorithm and help prevent overfitting, acting as a kind of regularization. The algorithm also becomes faster, because regression trees have to be fit to smaller datasets at each iteration. Friedman obtained that leads to good results for small and moderate sized training sets. Therefore, f is typically set to 0.5, meaning that one half of the training set is used to build each base learner.
Also, like in bagging, subsampling allows one to define an out-of-bag estimate of the prediction performance improvement by evaluating predictions on those observations which were not used in the building of the next base learner. Out-of-bag estimates help avoid the need for an independent validation dataset, but often underestimate actual performance improvement and the optimal number of iterations.
Number of observations in leaves
Gradient tree boosting implementations often also use regularization by limiting the minimum number of observations in trees' terminal nodes (this parameter is called
n.minobsinnode in the R
gbm package). It's used in the tree building process by ignoring any splits that lead to nodes containing fewer than this number of training set instances.
Imposing this limit helps to reduce variance in predictions at leaves.
Recently, gradient boosting has gained some popularity in the field of learning to rank. The commercial web search engines Yahoo and Yandex use variants of gradient boosting in their machine-learned ranking engines.
The method goes by a wide variety of names. The title of the original publication refers to it as a "Gradient Boosting Machine" (GBM). That same publication and a later one by J. Friedman also use the names "Gradient Boost", "Stochastic Gradient Boosting" (emphasizing the random subsampling technique), "Gradient Tree Boosting" and "TreeBoost" (for specialization of the method to the case of decision trees as base learners.)
A popular open-source implementation for R calls it "Generalized Boosting Model". Sometimes the method is referred to as "functional gradient boosting", "Gradient Boosted Models" and its tree version is also called "Gradient Boosted Decision Trees" (GBDT) or "Gradient Boosted Regression Trees" (GBRT). Commercial implementations from Salford Systems use the names "Multiple Additive Regression Trees" (MART) and TreeNet, both trademarked.
- Multi-threaded MATLAB-compatible implementation of Gradient Boosting with tree weak learners
- gradient boosted regression tree by c++, parallelization with tbb lib
- Several open-source R packages are available:
- Weka has an incomplete implementation in
- TMVA: Toolkit for Multivariate Data Analysis
- RT-Rank: Large Scale Multi-Threaded C++ Implementation of Gradient Boosting
- OpenCV contains the implementation since the version 2.2
- pGBRT: C++/MPI-based parallel/distributed implementation, released September 2011
- TreeNet is a commercial implementation from Salford Systems, possibly "equipped with patent-pending extensions."
- DTREG TreeBoost
- An implementation of stochastic gradient boosting is available in STATISTICA.
- Yahoo and Google have published papers describing an MPI- and a MapReduce-based parallel implementations of gradient boosting. However, they have not made the code publicly available.
- Friedman, J. H. "Greedy Function Approximation: A Gradient Boosting Machine." (February 1999)
- Friedman, J. H. "Stochastic Gradient Boosting." (March 1999)
- Hastie, T.; Tibshirani, R.; Friedman, J. H. (2009). "10. Boosting and Additive Trees". The Elements of Statistical Learning (2nd ed.). New York: Springer. pp. 337–384. ISBN 0-387-84857-6.
- Note: in case of usual CART trees, the trees are fitted using least-squares loss, and so the coefficient for the region is equal to just the value of output variable, averaged over all training instances in .
- Note that this is different from bagging, which samples with replacement because it uses samples of the same size as the training set.
- Ridgeway, Greg (2007). Generalized Boosted Models: A guide to the gbm package.
- Cossock, David and Zhang, Tong (2008). Statistical Analysis of Bayes Optimal Subset Ranking, page 14.
- Yandex corporate blog entry about new ranking model "Snezhinsk" (in Russian)
- OpenCV change logs
- B. Panda, et al. (2009). PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce.
- Jerry Ye, et al. (2009). Stochastic gradient boosted distributed decision trees.