梯度提升算法原理与计算示例

pc8888888

1 引言

各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
在前面两篇文章中，掌柜分别详细介绍了AdaBoost算法和基于AdaBoost改进的SAMME算法的基本原理和实现过程。在接下来的这篇文章中，掌柜将会介绍另外一种基于Boost策略的算法模型梯度提升（Gradient Boosting, GB）算法。从名字可以看出梯度提升算法有两个关键的地方：梯度和提升。提升表明整个集成模型依旧是串行地进行，且后一个模型是用来对前一个模型的输出结果进行修正；梯度则表明后一个模型在对前一个模型的结果进行修正时是以梯度下降为策略进行优化。
2 梯度提升

Gradient Boosting是Friedman等人[1]于2001年所提出的一种基于梯度下降策略来对模型进行优化的算法，其核心思想是先通过设定一个目标函数，然后再通过梯度下降算法来对预测结果进行优化。梯度提升算法的整体结构类似于之前介绍的线性回归和逻辑回归的求解流程只但是在具体细节部分有着不同的处理方式。
2.1 算法思想

在AdaBoost算法中，我们通过赋予每个样本一个权重值，并且在上一个模型中误差越大的样本（分类问题中即被错分的样本）在下一个模型中将会被给予更高的权重，然后对于每个基模型来说其都有不同的策略来降低高权重样本的误差，以此来提高整个集成模型的预测精度，即在AdaBoost算法中它是通过赋予样本权重来提升模型的精度。对于Gradient Boosting算法来说，它则是通过梯度来提升整个模型的预测精度。
如式(1)所示，便是梯度下降算法的核心公式
w=w-\alpha\cdot\frac{\partial J}{\partial w}\;\;\;\;\;\;\;\;(1) \\
其中w表示待更新的参数对象，J表示关于参数w的目标函数，\alpha表示学习率。更多关于梯度下降算法的详细介绍可以参见这篇文章。
通过式(1)可知，对于参数w来说，我们可以根据其梯度的方向来一步一步迭代计算得到（接近）其最优解。现在假定某个模型的预测输出为\hat{y}=f(x)，预测值与真实值之间的损失误差为J(y,\hat{y})，那么为了提高模型f(x)的预测结果，我们同样可以采用梯度下降算法来对预测结果进行迭代更新，即
f(x)=f(x)-\alpha\cdot\frac{\partial J}{\partial f(x)}\;\;\;\;\;\;\;\;(2) \\
而式(2)便是梯度提升算法的核心思想。
从式(2)可以看出，在梯度提升算法中最重要的便是求得目标函数J关于模型f(x)的梯度，而这通常会通过训练一系列额外的模型来对梯度进行预测，具体可见后续代码实现部分。
2.2 算法原理

在介绍完梯度提升算法的思想后我们再来看它背后的具体原理。假如现在掌柜需要训练一个回归模型，数据样本对应的标签值为y，第m次提升后模型的预测输出为\hat{y}^{(m)}=f^{(m)}(x)，预测值与真实值之间的损失为J(y,\hat{y}^{(m)})，则对于梯度提升算法来说可通过如下步骤求得模型：
第一步：初始化学习率\alpha以及m=0并根据数据集训练得到模型f^{(m)}(x)，
第二步：计算得到损失函数J关于f^{(m)}(x)的梯度，并根据如下公式对模型f^{(m)}(x)进行更新
f^{(m+1)}(x)=f^{(m)}(x)-\alpha\cdot\frac{\partial J}{\partial f^{(m)}(x)}\;\;\;\;\;\;\;\;(3) \\
第三步：判断m<=M是否成立，成立则结束迭代，否则m=m+1，并进入第二步。
以上便是梯度提升算法整个流程的核心步骤，下面分别来看它在回归和分类模型中的详细计算示例。
2.3 梯度提升回归

例如现在某数据集一共5个样本，y_0=2,y_1=4,y_2=2.5,y_3=1.8,y_4=2.4，模型的预测输出为\hat{y}^{(m)}=f^{(m)}(x)，M=3,\alpha=0.5，且采用均方误差作为损失函数，即
J(y,\hat{y}^{(m)})=\frac{1}{2}(y-\hat{y}^{(m)})^2\;\;\;\;\;\;\;(4) \\
由式(4)可知，损失函数J关于\hat{y}^{(m)}的梯度为
\frac{\partial J}{\partial \hat{y}^{(m)}}=-(y-\hat{y}^{(m)})\;\;\;\;\;\;\;(5) \\
假定模型f^{(0)}(x)的预测结果为\hat{y}^{(0)}_0=1.6,\hat{y}^{(0)}_1=2.7,\hat{y}^{(0)}_2=0.5,\hat{y}^{(0)}_3=1.1,\hat{y}^{(0)}_4=0.9，则采用梯度提升算法进行第1次提升后的结果f^{(1)}(x)为
\begin{aligned} f^{(1)}(x)=&f^{(0)}(x)+\alpha\cdot(y-\hat{y}^{(0)})\\[2ex] =&\begin{bmatrix}1.6\\2.7\\0.5\\1.1\\0.9\end{bmatrix}+ 0.1\cdot\begin{bmatrix}2-1.6\\4-2.7\\2.5-0.5\\1.8-1.1\\2.4-0.9\end{bmatrix}=\begin{bmatrix}1.8\\3.35\\1.5\\1.45\\1.65\end{bmatrix} \end{aligned}\;\;\;\;\;\;\;(6) \\
同理可得，第2、3次提升后的结果f^{(2)}(x),f^{(3)}(x)对应的预测结果分别为
f^{(2)}(x)=\begin{bmatrix}1.9\\3.675\\2\\1.625\\2.205\end{bmatrix}, \;\; f^{(3)}(x)=\begin{bmatrix}1.95\\3.837\\2.25\\1.712\\2.213\end{bmatrix},\;\; y=\begin{bmatrix}2\\4\\2.5\\1.8\\2.4\end{bmatrix}\;\;\;\;\;\;(7) \\
上述计算过程代码见AllBooKCode/Chapter08/C23_example_gradient_boost_reg.py文件。
2.4 梯度提升分类

在介绍完梯度提升中的回归计算示例后相信大家对梯度提升算法已经有了一定的认识。不过在分类场景中，应该如何利用梯度下降来对模型的预测结果进行优化提升呢？一个可行的办法便是对每个类别下的预测概率进行梯度提升。
例如现在某三分类数据集一共5个样本，标签分别为y_0=2,y_1=1,y_2=2,y_3=0,y_4=0，模型的预测输出为\hat{y}^{(m)}=f^{(m)}(x)，M=3,\alpha=0.5，且采用多项式误差（Multinomial Deviance）作为损失函数，即对于任意一个样本x来说其在的m次提升后对应的损失为
J(y,p^{(m)}(x))=-\sum_{k=0}^K\mathbb{I}(y=k)f^{(m)}_k(x)+\log\left(\sum_{k=0}^Ke^{f^{(m)}_k(x)}\right)\;\;\;\;\;\;\;(8) \\
其中，\mathbb{I}(\cdot)表示指示函数；y表示样本x对应的真实标签，是一个标量；p^{(m)}(x)表示样本x在第m次提升后预测结果的概率分布；f^{(m)}_k(x)表示样本x在第m次提升后在类别k中的预测概率值，即p^{(m)}(x)=[f^{(m)}_0(x),f^{(m)}_1(x)...,f^{(m)}_k(x)]
注：也可采用其它损失函数，这里为了和sklearn进行对比所以选择了和它一样的损失函数。
由式(8)可知，损失函数J关于样本x在第i个类别下的预测概率f^{(m)}_i(x)的梯度为
\frac{\partial J}{\partial f^{(m)}_i(x)}=-\mathbb{I}(y=i)+\frac{e^{f^{(m)}_i(x)}}{\sum_{k=0}^Ke^{f^{(m)}_k(x)}}\;\;\;\;\;\;(9) \\
假定随机初始化模型f^{(0)}(x)的结果为
f^{(0)}(x)= \begin{bmatrix} 0&0.1&0.3\\ 0.2&0.2&0.1\\ 0.3&0.2&0.1\\ 0&0&0.4\\ 0&0.1&0\\ \end{bmatrix}\;\;\;\;\;\;\;(10) \\
则此种情况下，根据式(8)可知整体损失值为
\begin{aligned} J=\frac{1}{5}[&-(0\times 0.0+0\times 0.1+1\times 0.3)+ \log(e^{0.0}+e^{0.1}+e^{0.3})\\[1ex] &-(0\times 0.2+1\times 0.2+0\times 0.1)+ \log(e^{0.2}+e^{0.2}+e^{0.1})\\[1ex] &-(0\times 0.3+0\times 0.2+1\times 0.1)+ \log(e^{0.3}+e^{0.2}+e^{0.1})\\[1ex] &-(1\times 0.0+0\times 0.0+0\times 0.4)+ \log(e^{0.0}+e^{0.0}+e^{0.4})\\[1ex] &-(1\times 0.0+0\times 0.1+0\times 0.0)+ \log(e^{0.0}+e^{0.1}+e^{0.0})\\[1ex] &\approx1.118 \end{aligned}\;\;\;\;\;\;(11) \\
根据式(9)可知所有样本在第0个类别下的梯度为
\frac{\partial J}{\partial f^{(0)}_0(x)}= -\begin{bmatrix}\mathbb{I}(2=0)\\[1ex]\mathbb{I}(1=0)\\[1ex]\mathbb{I}(2=0)\\[1ex]\mathbb{I}(0=0)\\[1ex]\mathbb{I}(0=0)\end{bmatrix}+ \begin{bmatrix} e^{0.0}/(e^{0.0}+e^{0.1}+e^{0.3})\\[1ex] e^{0.2}/(e^{0.2}+e^{0.2}+e^{0.1})\\[1ex] e^{0.3}/(e^{0.3}+e^{0.2}+e^{0.1})\\[1ex] e^{0.0}/(e^{0.0}+e^{0.0}+e^{0.4})\\[1ex] e^{0.0}/(e^{0.0}+e^{0.1}+e^{0.0})\\[1ex] \end{bmatrix}= \begin{bmatrix}0.289\\[1ex]0.344\\[1ex]0.367\\[1ex]-0.716\\[1ex]-0.678\end{bmatrix}\;\;\;\;\;\;\;(12) \\
进一步，根据式(3)可得，对于所有样本来说第0个类别下更新后的预测概率为
\begin{aligned} f_0^{(1)}(x)&=f_0^{(0)}(x)-\alpha\cdot\frac{\partial J}{\partial f^{(0)}_0(x)}\\[2ex] &=\begin{bmatrix}0\\[1ex]0.2\\[1ex]0.3\\[1ex]0\\[1ex]0\end{bmatrix}-0.5\times \begin{bmatrix}0.289\\[1ex]0.344\\[1ex]0.367\\[1ex]-0.716\\[1ex]-0.678\end{bmatrix}= \begin{bmatrix}-0.145\\[1ex]0.028\\[1ex]0.116\\[1ex]0.357\\[1ex]0.339\end{bmatrix} \end{aligned} \;\;\;\;\;\;\;(13) \\
同理，可以计算得到所有样本在第1次提升后的预测概率为
\begin{aligned} f^{(1)}(x)&= \begin{bmatrix}-0.145&-0.066&0.586\\[1ex]0.028&0.518&-0.045\\[1ex]0.116&0.023&0.430\\[1ex]0.357&-0.128&0.204\\[1ex]0.339&-0.057&-0.149\end{bmatrix} \end{aligned} \;\;\;\;\;\;\;(14) \\
此时，根据式(14)可得，在第1次提升后的预测标签为[2,1,2,0,0]，且损失值为0.816。
可以发现，在第一次提升结束后就已经得到了正确的预测结果。不过继续迭代下去会得到更高的预测概率和更低的损失值，后两次提升结束后的损失值分别为0.6112和0.4732，大家可以手动计算验证一下。
上述计算过程代码见AllBooKCode/Chapter08/C24_example_gradient_boost_cla.py文件。
如果还有不知道怎么有效入门机器学习的朋友，掌柜强烈推荐阅读下面这篇文章，里面详细介绍了掌柜所推荐的通过五个步骤和三个阶段的方法来高效学习机器学习的路线，同时也按顺序整理了客栈了所有与机器学习相关的文章。
2.5 使用示例

在明白梯度提升算法的基本思想和原理后我们再来看如何在sklearn中使用它。首先，需要知道的是梯度提升算法本质上也只是一种模型的训练策略，因此对于弱学习器的选择是任意。但是，通常默认情况下都是以决策树作为弱学习器，因此基于梯度提升方法最常见的一个模型便是梯度提升决策树（Gradient Boosting Decision Tree, GBDT）也简称梯度提升树，而sklearn中的GradientBoostingClassifier模块便是以决策树为弱学习器进行实现的且不可更改。
在sklearn中，可以通过如下方式来使用梯度提升树，实现代码如下：
1 from sklearn.ensemble import GradientBoostingClassifier
2 from sklearn.datasets import load_iris
3 from sklearn.model_selection import train_test_split
4
5 if __name__ == '__main__':
6     x, y = load_iris(return_X_y=True)
7     x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.3)
8     model = GradientBoostingClassifier(learning_rate=0.2, n_estimators=50)
9     model.fit(x_train, y_train)
10     print(model.score(x_test, y_test)) #    0.956
在上述代码中，第6-7行用来返回数据集并划分为训练集和测试集；第8行是实例化一个GradientBoostingClassifier对象，其中learning_rate指式(3)中的学习率\alpha，n_estimators则是指第2.2节算法原理第三步中的M；第9-10行是拟合模型并输出模型在测试集上的准确率。
由于GradientBoostingClassifier是以决策树为弱学习器，因此在第8行中实例化时还可以指定决策树对应的相关参数，例如max_depth，min_samples_leaf等，关于决策树的详细介绍可以参见文章。最后，sklearn中对应的梯度提升回归模块为GradientBoostingRegressor。
上述代码见AllBooKCode/Chapter08/C20_gbdt_train.py文件。
3 总结

在这篇文章中，掌柜首先介绍了梯度提升算法的基本思想原理，并总结了整个算法的迭代流程；然后分别以梯度提升回归和梯度提升分类为例，详细介绍了整个算法的计算过程；最后介绍了在sklearn中如何使用梯度提升树来进行建模。同时，从梯度提升算法的具体原理来看，严格上说掌柜认为它并不算是真正的boosting算法，因为本质上它也是先通过设定一个目标函数，然后再通过梯度下降算法来对结果进行优化，这点类似于一开始介绍的线性回归算法和逻辑回归算法。在下一篇文章中，掌柜将会详细如何从零实现基于不同弱学习器的梯度提升算法。
本次内容就到此结束，感谢您的阅读！如果你觉得上述内容对你有所帮助，欢迎点赞分享！青山不改，绿水长流，我们月来客栈见！
引用