Gradient boosting
Gradient boosting is a machine learning technique used in regression and classification tasks, among others. It gives a prediction model in the form of an ensemble of weak prediction models, which are typically decision trees. When a decision tree is the weak learner, the resulting algorithm is called gradient-boosted trees; it usually outperforms random forest. A gradient-boosted trees model is built in a stage-wise fashion as in other boosting methods, 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, 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. 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 formula_1 to predict values of the form formula_2 by minimizing the mean squared error formula_3, where formula_4 indexes over some training set of size formula_5 of actual values of the output variable formula_6: Now, let us consider a gradient boosting algorithm with formula_12 stages. At each  stage formula_13 (formula_14) of gradient boosting, suppose some imperfect model formula_15 (for low formula_13, this model may simply return formula_17, where the RHS is the mean of formula_6). In order to improve formula_15, our algorithm should add some new estimator, formula_20. Thus, or, equivalently, Therefore, gradient boosting will fit to the "residual" formula_23. As in other boosting variants, each formula_24 attempts to correct the errors of its predecessor formula_15. A generalization of this idea to loss functions other than squared error, and to classification and ranking problems, follows from the observation that residuals formula_20 for a given model are proportional  to the negative gradients of the mean squared error (MSE) loss function (with respect to formula_27): So, gradient boosting could be specialized to a gradient descent algorithm, and generalizing it entails "plugging in" a different loss and its gradient. Algorithm. In many supervised learning problems there is an output variable and a vector of input variables , related to each other with some probabilistic distribution. The goal is to find some function formula_30 that best approximates the output variable from the values of input variables. This is formalized by introducing some loss function formula_31 and minimizing it: The gradient boosting method  assumes a real-valued and seeks an approximation formula_30 in the form of a weighted sum of functions formula_34 from some class formula_35, called base (or weak) learners: We are usually given a training set formula_37 of known sample values of and corresponding values of . In accordance with the empirical risk minimization principle, the method tries to find an approximation formula_30 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 formula_39, and incrementally expands it in a greedy  fashion: where formula_42 is a base learner function. Unfortunately, choosing the best function at each step for an arbitrary loss function 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 the formula_43. In fact, the local maximum-descent direction of the loss function is the negative gradient. Hence, moving a small amount formula_44  such that the linear approximation remains valid: formula_45 Where formula_46. This implies (for small formula_47: formula_48. To prove the following, consider the objective formula_49 Doing a Taylor expansion to first order formula_50 Now differentiating w.r.t to formula_51 only derivative of the second term remains formula_52 this is the direction of steepest ascent and hence we must move in the negative of this direction to move in the direction of steepest descent. Furthermore, we can optimize formula_53 by finding the formula_53 value for which the Loss Function has a minimum: formula_55 If we considered the continuous case, i.e. where formula_56 is  the set of arbitrary differentiable functions on formula_57, we would update the model in accordance with the following equations where the derivatives are taken with respect to the functions formula_60 for formula_61, and formula_62 is the step length. In the discrete case however, i.e. when the set formula_35 is finite, we choose the candidate function closest to the gradient of 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: Input: training set formula_64 a differentiable loss function formula_65 number of iterations . Algorithm: 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 formula_20 to pseudo-residuals. Let formula_75 be the number of its leaves. The tree partitions the input space into formula_75 disjoint regions formula_77  and predicts a constant value in each region. Using the indicator notation, the output of formula_20 for input "x" can be written as the sum: where formula_80 is the value predicted in the region formula_81. Then the coefficients formula_80 are multiplied by some value formula_62, 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 formula_85 for each of the tree's regions, instead of a single formula_62 for the whole tree. He calls the modified algorithm "TreeBoost . The coefficients formula_80 from the tree-fitting procedure can be then simply discarded and the model update rule becomes: Size of trees. formula_89, 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 formula_90 (decision stumps), no interaction between variables is allowed. With formula_91 the model may include effects of the interaction between up to two variables, and so on. Hastie et al. comment that typically formula_92 work well for boosting and results are 	Gradient boosting
22210329	fairly insensitive to the choice of formula_89 in this range, formula_90 is insufficient for many applications, and formula_95 is unlikely to be required. Regularization. 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. Shrinkage. An important part of gradient boosting method is regularization by shrinkage which consists in modifying the update rule as follows: where parameter formula_97 is called the "learning rate". Empirically it has been found that using small learning rates (such as formula_98) yields dramatic improvements in models' generalization ability over gradient  boosting without shrinking (formula_99). 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 bootstrap aggregation ("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 formula_100 of  the size of the training set. When formula_101, the algorithm is deterministic and identical to the one described above. Smaller values of formula_100 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 formula_103 leads to good results for small and moderate sized training sets. Therefore, formula_100 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 error 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. It is 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. Penalize complexity of tree. Another useful regularization techniques for gradient boosted trees is to penalize model complexity of the learned model. The model complexity can be defined as the proportional number of leaves in the learned trees. The joint optimization of loss and model complexity corresponds to a post-pruning algorithm to remove branches that fail to reduce the loss by a threshold. Other kinds of regularization such as an formula_105 penalty on the leaf values can also be added to avoid overfitting. Usage. Gradient  boosting can be used 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. 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. Names. The method goes by a variety of names. Friedman introduced his regression technique as a "Gradient Boosting Machine" (GBM). Mason, Baxter et  al. described the generalized abstract class of algorithms as "functional gradient boosting". Friedman et al. describe an advancement of gradient boosted models as Multiple Additive Regression Trees (MART); Elith et al. describe that approach as "Boosted Regression Trees" (BRT). A popular open-source implementation for R calls it a "Generalized Boosting Model", however packages expanding this work use BRT. 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. XGBoost is another popular modern implementation of the method with some extensions, like second -order optimization. Disadvantages. While boosting can increase the accuracy of a base learner, such as a decision tree or linear regression, it sacrifices intelligibility and interpretability. 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. Furthermore, its implementation may be more difficult due to the higher computational demand. Gradient boosting