Gradient boosting

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.

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. 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 to predict values of the form \hat{y} = F(x) by minimizing the mean squared error \tfrac{1}{n}\sum_i(\hat{y}_i - y_i)^2 , where i indexes over some training set of size n of actual values of the output variable y : \hat{y}_i = the predicted value F(x_i) y_i = the observed value n = the size of the sample, i.e. the number of observations in y If the algorithm has M stages, at each stage m ( 1 \le m \le M ), suppose some imperfect model F_m (for low m , this model may simply predict \hat y_i to be \bar y , the mean of y ). In order to improve F_m , our algorithm should add some new estimator, h_m(x) . Thus, 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). Therefore, gradient boosting will fit h_m to the residual y_i - F_m(x_i) . As in other boosting variants, each F_{m+1} attempts to correct the errors of its predecessor 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 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 F(x_i) ): L_{\rm MSE} = \frac{1}{n} \sum_{i=1}^n \left(y_i - F(x_i)\right)^2 - \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 generalized to a gradient descent algorithm by plugging in a different loss and its gradient. \hat{F} = \operatorname{argmin}\limits_F \mathbb{E}_{x,y}[L(y, F(x))]. The gradient boosting method assumes a real-valued . It seeks an approximation \hat{F}(x) in the form of a weighted sum of functions h_m (x) from some class \mathcal{H} , called base (or weak) learners: \hat{F}(x) = \sum_{m=1}^M \gamma_m h_m(x) + \mbox{const}, where \gamma_m is the weight at stage m . We are usually given a training set \{ (x_1,y_1), \dots , (x_n,y_n) \} of known values of and corresponding values of . In accordance with the empirical risk minimization principle, the method tries to find an approximation \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 F_0(x) , and incrementally expands it in a greedy fashion: F_0(x) = \underset{h_0 \in \mathcal{H}}{\arg\min} \sum_{i=1}^n {L(y_i, h_0(x_i))}, 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 m \geq 1 , where h_m \in \mathcal{H} is a base learner function. Unfortunately, choosing the best function h_m 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 is to find a local minimum of the loss function by iterating on F_{m-1}(x) . In fact, the local maximum-descent direction of the loss function is the negative gradient. Hence, moving a small amount \gamma such that the linear approximation remains valid: 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 \gamma > 0 . For small \gamma , this implies that L(y_i, F_{m}(x_i)) \le L(y_i, F_{m-1}(x_i)) . To prove the following, consider the objective O = \sum_{i=1}^n L(y_i, F_{m-1}(x_i) + h_m(x_i)) Doing a Taylor expansion around the fixed point F_{m-1}(x_i) up to first order O = \sum_{i=1}^n L(y_i, F_{m-1}(x_i) + h_m(x_i)) \approx \sum_{i=1}^n L(y_i, F_{m-1}(x_i)) + h_m(x_i)\nabla_{F_{m-1}} L(y_i, F_{m-1}(x_i))+\cdots Now differentiating w.r.t. h_m(x_i) , only the derivative of the second term remains \nabla_{F_{m-1}}L(y_i, F_{m-1}(x_i)) . This is the direction of steepest ascent and hence we must move in the opposite (i.e., negative) direction in order to move in the direction of steepest descent. Furthermore, we can optimize \gamma by finding the \gamma value for which the loss function has a minimum: \gamma_m = \underset{\gamma}{\operatorname{argmin}} \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 \mathcal{H} is the set of arbitrary differentiable functions on \R , we would update the model in accordance with the following equations 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 \gamma_m is the step length, defined as \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 \mathcal{H} 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 \{(x_i, y_i)\}_{i=1}^n, a differentiable loss function L(y, F(x)), number of iterations . Algorithm: Initialize model with a constant value: F_0(x) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L(y_i, \gamma). For = 1 to : Compute so-called pseudo-residuals: r_{im} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]_{F(x)=F_{m-1}(x)} \quad \text{for } i=1,\ldots,n. Fit a base learner (or weak learner, e.g. tree) closed under scaling h_m(x) to pseudo-residuals, i.e. train it using the training set \{(x_i, r_{im})\}_{i=1}^n . Compute multiplier \gamma_m by solving the following one-dimensional optimization problem: \gamma_m = \underset{\gamma}{\operatorname{argmin}} \sum_{i=1}^n L\left(y_i, F_{m-1}(x_i) + \gamma h_m(x_i)\right). Update the model: F_m(x) = F_{m-1}(x) + \gamma_m h_m(x). Output F_M(x). h_m(x) = \sum_{j=1}^{J_{m}} b_{jm} \mathbf {1}_{R_{jm}}(x), where b_{jm} is the value predicted in the region R_{jm} . Then the coefficients b_{jm} are multiplied by some value \gamma_m , chosen using line search so as to minimize the loss function, and the model is updated as follows: 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 \gamma_{jm} for each of the tree's regions, instead of a single \gamma_m for the whole tree. He calls the modified algorithm "TreeBoost". The coefficients b_{jm} from the tree-fitting procedure can be then simply discarded and the model update rule becomes: 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). When the loss L(\cdot, \cdot) is mean-squared error (MSE) the coefficients \gamma_{jm} coincide with the coefficients of the tree-fitting procedure b_{jm} . The number J of terminal nodes in the trees is a parameter which controls the maximum allowed level of interaction between variables in the model. With J = 2 (decision stumps), no interaction between variables is allowed. With J = 3 the model may include effects of the interaction between up to two variables, and so on. J can be adjusted for a data set at hand. Hastie et al. comment that typically 4 \leq J \leq 8 work well for boosting and results are fairly insensitive to the choice of J in this range, J = 2 is insufficient for many applications, and J > 10 is unlikely to be required. F_m(x) = F_{m-1}(x) + \nu \cdot \gamma_m h_m(x), \quad 0 where parameter \nu is called the "learning rate". Empirically, it has been found that using small learning rates (such as \nu ) yields dramatic improvements in models' generalization ability over gradient boosting without shrinking ( \nu = 1 ). However, it comes at the price of increasing computational time both during training and querying: lower learning rate requires more iterations. 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 0.5 \leq f \leq 0.8 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 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. == External links== How to explain gradient boosting Gradient Boosted Regression Trees LightGBM

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373672597 under CC BY-SA 4.0; modifications have been made.