梯度提升（Gradient boosting）是机器学习中用于分类（classification）和回归（regression）问题的技术，是由多个弱学习器集成得到的预测模型，一种典型的弱学习器就是决策树（尤其是CART），由决策树集成得到的模型就是GBDT（Gradient Boosting Decision Tree）。
梯度提升（Gradient Boosting）
原理
与其它的Boosting方法一样，GB将多个弱学习器结合起来提升为一个强学习器。下面通过平方误差损失来解释GB的原理。假设我们的目标是寻找一个模型$F$，使得该模型的预测值$\hat{y}=F(x)$与真实值$y$之间的平方误差$(\hat{y}-y)^2$最小。
在梯度提升的每一步m（$1\le m \le M$）中，假设已经有一个不太完美的模型$F_m$，梯度提升并不会改变该模型，而是重新构造一个估计器（estimator）$h$从而得到一个更好的模型$F_{m+1}(x)=F_m(x)+h(x)$。那么现在面临的问题就是，如何选择估计器$h$？梯度提升算法观察到一个完美的估计器$h$肯定满足：
$$F_{m+1}(x)=F_m(x)+h(x)=y$$
也就是说：
$$h(x)=y-F_m(x)$$
因此，梯度提升会选择估计器$h$去拟合残差$y-F_m(x)$。与其它集成方法的变体一样，每一个$F_{m+1}$的学习都是为了去纠正$F_m(x)$。另外，我们很容易看到，残差$y-F_m(x)$是平方误差损失函数$\frac{1}{2}(y-F_m(x))^2$的负梯度，因此，Gradient Boosting也是一种Gradient descent的Boosting算法。
算法
在一些有监督的学习中，输入变量$x$与输出变量$y$之间是通过联合概率分布$P(x,y)$联系在一起的，假设训练集为$\{(x_1,y_1),\cdots,(x_n,y_n)\}$，我们的目标是寻找一个近似于最优函数$F^*(x)$的$\hat{F}(x)$，使得损失函数$L(y,F(x))$的值最小：
$$\hat{F}(x)=arg\min_F E_{x,y}[L(y,F(x))]$$
梯度提升算法寻找一个由多个函数$h$（弱学习器）的加权的和得到的近似函数$\hat{F}(x)$（强学习器），即：
$$F(x)=\sum^M_{i=1}\gamma_ih_i(x)+const$$
根据经验风险最小化准则，假设模型开始时一个常数函数$F_0(x)$，通过贪心算法不断的替身，也即：
$$F_0(x)=arg\min_\gamma\sum_{i=1}^nL(y_i,\gamma) \\
F_m(x)=F_{m-1}+arg\min_{f}\sum_{i=1}^{n}L(y_i,F_{m-1}(x_i)+f(x_i))$$
那么现在的问题是，如何寻找最优的$f$呢？这里最简单的方法就是最速下降法，我们并不将$L(y,f)$看作是关于$f$的函数，而是可以被当做向量$f(x_1),\cdots,f(x_n)$的值：
$$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)) \\
\gamma_m=arg\min_\gamma\sum^n_{i=1}L(y_i,F_{m-1}(x_i)+\gamma\frac{\partial L(y_i,F_{m-1}(x_i))}{\partial F_{m-1}(x_i)})$$
输入：训练集$\{(x_i,y_i)\}_{i=1}^n$，一个可微的损失函数$L(y,F(x))$，迭代次数$M$
1.使用常数初始化模型：
$$F_0(x)=arg\min_\gamma\sum_{i=1}^nL(y_i,\gamma$$
2.for m = 1 to M:
$\qquad$计算伪残差：
$$r_{im}=-\left [ \frac{\partial L(y_i,F(x_i))}{\partial F(x_i)} \right ]_{F(x)=F_{m-1}(x)} for\quad i=1,\cdots,n.$$
$\qquad$训练学习器$h_m(x)$拟合残差，也就是说，使用训练集$\{(x_i,r_{im})\}$训练学习器$h_m(x)$
$\qquad$计算乘子$\gamma_m$:
$$\gamma_m=arg\min_\gamma\sum^n_{i=1}L(y_i,F_{m-1}(x_i)+\gamma h_m(x_i))$$
$\qquad$更新模型：
$$F_m(x)=F_{m-1}(x)+\gamma_m h_m(x)$$
3.输出$F_M(x)$
梯度提升决策树（GBDT）
原理
梯度提升（Gradient Boosting）的一种典型的应用就是使用决策树作为其弱学习器，尤其是CART数。一般的梯度提升在第m步会训练学习器去拟合残差，让$J$表示叶子的个数，这样树就会被划分为$J$个不相交的空间$R_{1m},\cdots,R_{Jm}$，然后在每个空间上预测一个常数值，也即：
$$h_m(x)=\sum_{j=1}^{J}b_{jm}I(x\in R_{jm})$$
然后让系数$b_{jm}$乘上$\gamma_m$，并使用线性搜索最小化损失函数，这样模型就按下面的方式更新：
$$F_m(x)=F_{m-1}(x)+\gamma_m h_m(x) \\
\gamma_m = arg\min_\gamma\sum^n_{i=1}L(y_i,F_{m-1}(x_i)+\gamma_m h_m(x))$$
缩减（Shrinkage）
梯度提升算法的一个重要组成部分就是在模型更新的过程中加入缩减，即：
$$F_m(x)=F_{m-1}(x)+\eta\gamma_m h_m(x), \qquad 0<\eta\le 1$$
这里的参数$\eta$是学习速率，能很好的避免过拟合。