Gradient boosting

Gradient boosting is a machine learning technique for regression and classification 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.(This section follows the exposition of gradient boosting by Li.)In many supervised learning problems one has an output variable y and a vector of input variables x described via a joint probability distribution P ( x , y ) {displaystyle P(x,y)}  . Using a training set { ( x 1 , y 1 ) , … , ( x n , y n ) } {displaystyle {(x_{1},y_{1}),dots ,(x_{n},y_{n})}}   of known values of x and corresponding values of y, the goal is to find an approximation F ^ ( x ) {displaystyle {hat {F}}(x)}   to a function F ( x ) {displaystyle F(x)}   that minimizes the expected value of some specified loss function L ( y , F ( x ) ) {displaystyle L(y,F(x))}  :Input: training set { ( x i , y i ) } i = 1 n , {displaystyle {(x_{i},y_{i})}_{i=1}^{n},}   a differentiable loss function L ( y , F ( x ) ) , {displaystyle L(y,F(x)),}   number of iterations M.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.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.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.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).