GBDT算法原理
GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升树，想要理解GBDT的真正意义，那就必须理解GBDT中的Gradient Boosting 和Decision Tree。
Decision Tree：CART回归树
GBDT使用的决策树通通都是都是CART回归树。为什么不用CART分类树呢？因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。
对于回归树算法来说最重要的是寻找最佳的划分点，那么回归树中的可划分点包含了所有特征的所有可取的值。
在分类树中最佳划分点的判别标准是熵或者基尼系数，都是用纯度来衡量的，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。
回归树生成算法:
输入: 训练数据集$ D$
输出: 回归树 $f(x)$
在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
-
选择最优切分变量$ j$与切分点 $s$， 求解:
$$
\min_{j,s}[\min_{c_1}\sum_{x_i \in R_1(j, s)} (y_i- c_1)^2+\min_{c_2}\sum_{x_i \in R_2(j, s)} (y_i-c_2)^2]
$$遍历变量$j$，对固定的切分变量$j$扫描切分点 $s$，选择使得上式达到最小值的对 $(j,s)$.
简要解释一下上述公式：中括号里面的公式是求出每个特征变量在哪一个划分点时损失函数最小，最外面的 $min$ 是在所有特征值，求得使损失函数全局最小的特征及其切分点$(j^, s^)$;
-
用选定的对 $(j,s)$ 划分区域并决定相应的输出值：
$$
R_1(j, s)={x|x^{(j)}\leq s},R_2(j, s)={x|x^{(j)} > s}
$$$$
\hat {c_m}=\frac{1}{N}\sum_{x_1 \in R_m(j, s)}y_i, x \in R_m, m=1,2
$$划分区域的输出值就是将该区域的所有样本的输出值求平均。
-
继续对两个子区域调用步骤（1）和（2），直至满足停止条件。
-
将输入空间划分为$M$个区域$R_1,R_2…R_M$，得到决策树
$$
f(x)=\sum_{m=1}^M \hat{c_m}I(x \in R_m)
$$
Gradient Boosting：拟合负梯度
梯度提升树（Grandient Boosting）是提升树（Boosting Tree）的一种改进算法，所以在讲梯度提升树之前先来说一下提升树。
提升树算法:
-
初始化$ f0(x)=0$
-
对$m=1,2…M$
-
计算残差
$$
r_{mi}=y_i-f_{m-1}(x_i), i=1, 2,…,M
$$ -
拟合残差$ r_{mi}$ 学习一个回归树，得到 $h_m(x)$
-
更新 $f_m(x)=f_{m-1}(x)+h_m(x)$
-
-
得到回归树
$$
f_{M}(x)=\sum_{m=1}^Mh_m(x)
$$
上面伪代码中的残差是什么？
在提升树算法中，假设我们前一轮迭代得到的强学习器是
$$
f_{t-1}(x)
$$
损失函数是
$$
L(y, f_{t-1}(x))
$$
我们本轮迭代的目标是找到一个弱学习器
$$
h_{t}(x)
$$
当采用平方损失函数时
$$
\begin{aligned}
& L(y, f_{t-1}(x)+h_t(x)) \
& = (y - f_{t-1}(x) - h_t(x))^2 \
& =(r - h_t(x))^2 \
\end{aligned}
$$
这里，
$$
r = y - f_{t-1}(x)
$$
是当前模型拟合数据的残差（residual）。所以，对于提升树来说只需要简单地拟合当前模型的残差。
当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易，针对这一问题，Freidman提出了梯度提升树算法，这是利用最速下降的近似方法，其关键是利用损失函数的负梯度作为提升树算法中的残差的近似值。
第$t$轮的第$i$个样本的损失函数的负梯度为：
$$
-[\frac{\partial {L(y, f(x_i))}}{\partial {f(x_i)}}]_{f(x)=f_{t-1}(x)}
$$
此时不同的损失函数将会得到不同的负梯度，如果选择平方损失:
$$
L(y, f(x_i))=\frac{1}{2}(y-f(x_i))^2
$$
负梯度为
$$
-[\frac{\partial {L(y, f(x_i))}}{\partial {f(x_i)}}]_{f(x)=f_{t-1}(x)}=-[\frac{\partial \frac{1}{2}(y-f(x_i))^2}{\partial {f(x_i)}}]_{f(x)=f_{t-1}(x)}=y-f(x_i)
$$
此时我们发现GBDT的负梯度就是残差，所以说对于回归问题，我们要拟合的就是残差。
gbdt的残差为什么用负梯度代替？
通过一阶泰勒展开证明负梯度方向是下降最快的方向
$$
f(\theta_{k+1}) \approx f(\theta_k)+\frac{\partial{f(\theta_k)}}{\partial{\theta_k}}(\theta_{k+1}-\theta_k)
$$在GB中，对损失函数展开：
$$
L(y,F_m(x))\approx L(y, F_{m-1}(x))+\frac{\partial{L(y, F_{m-1}(x))}}{\partial{ F_{m-1}(x)}}(F_m(x)-F_{m-1}(x))
$$
即有：
$$
L(y,F_m(x))\approx L(y, F_{m-1}(x))+\frac{\partial{L(y, F_{m-1}(x))}}{\partial{ F_{m-1}(x)}}T_m(x)
$$
则在优化$L(y,F(x))$时，
$$
F_m(x)=F_{m-1}(x)-\eta \frac{\partial{L(y, F_{m-1}(x))}}{\partial{ F_{m-1}(x)}}
$$
即，$T_m(x)=-\eta \frac{\partial{L(y, F_{m-1}(x))}}{\partial{ F_{m-1}(x)}}$所以需要当前的弱学习器来学习负梯度，这里和GBDT中差了一个 $\eta$.
在1和2中都是随机梯度下降，但是不同的是：
- 在参数空间中优化，每次迭代得到参数的增量，这个增量就是负梯度乘上学习率；
- 在函数空间中优化，每次得到增量函数，这个函数会去拟合负梯度，在GBDT中就是一个个决策树。
要得到最终结果，只需要把初始值或者初始的函数加上每次的增量。所以1的优化过程是(假设迭代了M次)：
无论损失函数是什么形式，每个决策树拟合的都是负梯度。准确的说，不是用负梯度代替残差，而是当损失函数是均方损失时，负梯度刚好是残差，残差只是特例。
GBDT算法原理
上面两节分别将Decision Tree和Gradient Boosting介绍完了，下面将这两部分组合在一起就是我们的GBDT了。
GBDT算法：
-
初始化弱学习器
$$
f_0(x)=\arg \min_{c}\sum_{i=1}^{N}L(y_i, c)
$$
当为平方损失时，$f_0(x)=\frac{\sum_{i=1}^N y_i}{N}$ -
对$m=1,2,…,M$有：
a. 对每个样本$i=1,2,…,N$，计算负梯度，即残差
$$
r_{im}=-[\frac{\partial{L(y_i, f(x_i))}}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}
$$b. 将上步得到的残差作为样本新的真实值，并将数据$(x_i, x_im), i=1, 2,…,N$作为下棵树的训练数据，得到一颗新的回归树$ f_m(x)$，其对应的叶子节点区域为 $R_jm, j=1, 2,…,J$。其中J为回归树$t$的叶子节点的个数。
c. 对叶子区域$ j=1,2,…J$计算最佳拟合值
$$
\gamma_{jm}=\arg \min_{\gamma}\sum_{x_i \in R_{jm}}L(y_i, f_{m-1}(x_i)+\gamma) (对 \gamma求导并令导数为0即可求得)
$$d. 更新强学习器
$$
f_m(x)=f_{m-1}(x)+\sum_{j=1}^{J}\gamma_{jm}I(x \in R_{jm})
$$ -
得到最终学习器
$$
f(x)=f_M{x}=f_{0}(x)+\sum_{m=1}^{M}\sum_{j=1}^{J}\gamma_{jm}I(x \in R_{jm})
$$