基于梯度的boosting方法推导

一、基础知识

一般来说，损失函数具有线性可加性。
设我们有数据集$D=\{(x_i,y_i){\}}_{i=1}^n$，估计模型$F$，损失函数$L$，那么
$$L(y_1,\dots ,y_n;F(x_1),\dots ,F(x_n))=\sum _{i=1}^{n}L(y_i,F(x_i)).$$
直观的，损失函数在数据集的损失等于损失函数在数据集的所有样本之和。
理解可加性对于理解基于梯度的boosting方法至关重要。

下面给出两种常见的损失函数，请读者自行验证其具有可加性。
均方误差损失：
$$L(F)=\sum _{i=1}^n{\left(y_i-F(x_i)\right)}^2.$$
交叉熵损失：
$$L(F)=-\sum _{i=1}^n\left[y_i\log F(x_i)+(1-y_i)\log (1-F(x_i))\right]$$
学过数理统计的读者可以验证交叉熵损失最小化与伯努利分布的似然函数最大化等价。

基于梯度的提升方法的核心是对损失函数求模型的导数，即计算$\frac{\partial L(F)}{\partial F}$. 这个步骤似乎很抽象，因为模型是一个函数，损失函数和模型之间似乎又没有简单的函数关系，应该如何求导？

如果损失函数具有可加性，那么有：
$$\frac{\partial L(F)}{\partial F}=\frac{\partial }{\partial F}\sum _{i=1}^{n}L(y_i,F(x_i))=\sum _{i=1}^n\frac{\partial L(y_i,F(x_i))}{\partial F}.$$
因为可加性的存在，我们可以对损失函数先“拆解”，再对每个$F(x_i)$求导，最后求和。
类似的，对于二阶导，我们有：
$$\frac{{\partial }^{2}L(F)}{\partial F^2}=\frac{{\partial }^2}{\partial F^2}\sum _{i=1}^{n}L(y_i,F(x_i))=\sum _{i=1}^n\frac{{\partial }^{2}L(y_i,F(x_i))}{\partial F^2}$$

boosting方法本质上属于加法模型。有标签的统计学习模型本质上是一个函数，对于相同的数据集，模型的自变量都是相同的。因此，显然相加后的函数还是以模型原本的自变量为输入。
现在我们有基学习器$F_{m-1}(x_i)$，我们把这个基学习器加上这新学习器$f_m(x_i)$，就可以得到新的学习器$F_{m-1}(x_i)+f_m(x_i)$

一元函数在$x_0$的泰勒展开为：
$$f(x)\approx f(x_0)+f^{\prime }(x_0)(x-x_0)+\frac{1}{2}{f}^{\prime \prime }(x_0)(x-x_0{)}^2$$
那么，损失函数的其中一项$L(y_i,F_{m-1}(x_i)+f_m(x_i))$在$(y_i,F_{m-1}(x_i))$的泰勒展开为：
$$L(y_i,F_{m-1}(x_i)+f_m(x_i))\approx L(y_i,F_{m-1}(x_i))+\frac{\partial L}{\partial F(x_i)}{f}_m(x_i)+\frac{1}{2}\frac{{\partial }^{2}L}{\partial F(x_i{)}^2}{f}_m(x_i{)}^2$$

这个泰勒展开是什么意思？直观上讲，$F_{m-1}(x_i)+f_m(x_i)$就是一个“老”学习器加一个新学习器，顾名思义，老学习器是已知的，新学习器是未知的，因此$L(y_i,F_{m-1}(x_i)+f_m(x_i))$其实就是以新学习器$f_m(x_i)$为自变量的函数。泰勒展开就是再将损失函数$L(y_i,F_{m-1}(x_i)+f_m(x_i))$近似为一个二次函数。
类似的，如果只保留泰勒展开的前两项，就是将$L(y_i,F_{m-1}(x_i)+f_m(x_i))$近似为一个一次平面，这里不做额外说明。

二、Boosting

现在，假设我们已经得到了一个统计学习模型$F_{m-1}(x)$，接下来，我们考虑一个新的学习器$f_m(x)$，使得$F_m(x)=F_{m-1}(x)+f_m(x)$. 现在的问题是，我们已知老模型的损失函数${\sum }_{i=1}^{n}L(y_i,F_{m-1}(x_i))$，新模型的损失函数${\sum }_{i=1}^{n}L(y_i,F_{m-1}(x_i)+f_m(x_i))$是以$f_m(x_i)$为自变量的函数，应该如何得到一个使得${\sum }_{i=1}^{n}L(y_i,F_{m-1}(x_i)+f_m(x_i))$最小的$f_m(x_i)$？
可以发现，此时的问题是一个优化问题，此时我们的目标是寻找优化问题的最优解。根据泰勒展开可知其一阶导与二阶导均已知，我们既可以使用梯度下降法、也可以使用牛顿法。

这里不加推导地给出梯度下降法的搜索方向${\Delta }_{\text{gradient}}=-\frac{\partial L}{\partial F(x_i)}$，这实际上就是二阶泰勒展开的一次项的负系数。
因此，我们的新基学习器$f_m(x)$应当尽可能拟合$\eta {\Delta }_{\text{gradient}}$，其中$\eta$是学习率，代表搜索的步长。
Gradient Boosting的命名来自于其使用的Gradient Descent优化方法。

这里不加推导地给出牛顿法的搜索方向
${\Delta }_{\text{newton}}=-\frac{\frac{\partial L}{\partial F}}{\frac{{\partial }^{2}L}{\partial F^2}}$，这实际上就是二阶泰勒展开后的二次函数的最优解方向。
因此，我们的新基学习器$f_m(x)$应当尽可能拟合$\eta {\Delta }_{\text{newton}}$，其中$\eta$是学习率，代表搜索的步长。
Newton Boosting的命名来自于其使用的Newton-Raphson method。

三、例子

首先对损失函数求一阶导：
$$\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}=2\left(F(x_i)-y_i\right).$$
因此，负梯度方向为：
$$-\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}=2\left(y_i-F(x_i)\right).$$

因此：均方误差损失下的gradient boosting是在拟合$\eta$倍的残差。
下面对损失函数求二阶导：
$$\frac{{\partial }^{2}L(y_i,F(x_i))}{\partial F(x_i{)}^2}=2.$$
请读者自行验证此时Newton Boosting和Gradient Boosting等价。

首先对损失函数求一阶导：
$$\frac{\partial L_i(F)}{\partial F(x_i)}=-\frac{y_i}{F(x_i)}+\frac{1-y_i}{1-F(x_i)}$$
因此，负梯度方向为：
$$-\frac{\partial L_i(F)}{\partial F(x_i)}=\frac{y_i-F(x_i)}{F(x_i)(1-F(x_i))}$$
此时负梯度方向是Gradient Boosting的搜索方向。
下面对损失函数求二阶导：
$$\frac{{\partial }^2{L}_i(F)}{\partial F(x_i{)}^2}=\frac{y_i}{F(x_i{)}^2}+\frac{1-y_i}{(1-F(x_i){)}^2}$$
因此，牛顿法搜索方向为：
$$-\frac{\frac{\partial L_i(F)}{\partial F(x_i)}}{\frac{{\partial }^2{L}_i(F)}{\partial F(x_i{)}^2}}=F(x_i)-y_i$$
可以发现，交叉熵损失下的Newton Boosting是在拟合$\eta$倍的残差。