机器学习（5）：提升算法（boosting algorithm）

最近自己会把自己个人博客中的文章陆陆续续的复制到****上来，欢迎大家关注我的 个人博客，以及我的github。

本文将讲解有关提升算法的知识，主要包括提升算法的基本思想，以及几个具体的提升算法——AdaBoost算法、梯度提升决策树。以及梯度提升、加法模型和前向分步算法等内容。在本文中会先给出每个算法的思想和算法流程，最后再对其中用到的某些定义做总结。

本文主要是依据李航老师的《统计学习方法》和邹博老师的机器学习教学视频总结编写的。文中所用到的有关机器学习的基本概念和方法可以参考本人博客中该系列之前的文章，或者直接上网搜索相关的内容。以下文章所列出的公式以及公式的推导读者们最好是在草稿本上自己推导一遍。由于本人水平所限，文章中难免有错误和不当之处，欢迎大家多多批评指正！

一、提升算法的基本思想

先来了解几个概念。对于一个概念（一个类），如果存在一个多项式的学习算能够学习它，并且正确率很高，那么就称这个概念为强可学习的；反之，如果正确率仅仅比随机猜测的略好，则称这个概念是弱可学习的。有趣的是，后来有人证明强可学习和弱可学习两者是等价的。

提升（boosting）算法就是从弱可学习算法出发， 通过改变训练集中每个训练样本的权重，从而学习到多个弱分类器（又称基本分类器），并将这些弱分类器进行线性组合，从而得到一个强分类器。可以这样理解，强分类器的分类效果要比弱分类器好。又因为寻找一系列弱分类器比寻找一个强分类器简单，所以这种方式总是行之有效的。

二、AdaBoost算法

从上述提升算法的基本思想中可知，在该算法中有两个问题需要解决，一是如何改变训练集中每个样本的权重？二是如何将若干弱分类器线性组合成一个强分类器？在AdaBoost算法中，解决第一个问题的方法是：提高那些被前一轮弱分类器错误分类的样本的权值，而降低那些被正确分类的样本的权值；而解决第二个问题的方法是：采用加权多数表决的方式。

AdaBoost算法的思想有点类似于随机森林，不同的是随机森林是采用多数表决的方式，并且生成每一个弱分类器（决策树）的方式也和AdaBoost不同。可以简单的总结为AdaBoost既对样本数据进行加权，又对分类器进行加权。需要说明的是，AdaBoost算法常用于二分类问题。

算法流程如下：

(1) 初始化训练数据的权值分布
$W_1=(w_{11},w_{12},...,w_{1N}),\quad w_{1i}=\frac{1}{N}\quad i=1,2,...,N$W1​=(w11​,w12​,...,w1N​),w1i​=N1​i=1,2,...,N
​ 初始化时，默认每个训练样本的权重都是相同的，它们的权重之和为1。

(2) 对于第m轮训练，m=1,2,…,M

​ **（a）**使用具有权值$W_m$Wm​的训练集数据学习，得到一个弱分类器
$G_m(x):\chi \rightarrow\{-1,+1\}$Gm​(x):χ→{−1,+1}
​ 上式含义是该分类器的取值只有-1和+1两种情况。

**（b）**计算$G_m(x)$Gm​(x)在训练集上的分类误差率
$e_m=\sum_{i=1}^N{P(G_m(x_i\neq y_i))}=\sum_{i=1}^N{w_{mi}I(G_m(x_i)\neq y_i)}$em​=i=1∑N​P(Gm​(xi​​=yi​))=i=1∑N​wmi​I(Gm​(xi​)​=yi​)
​ $P(G_m(x_i\neq y_i))$P(Gm​(xi​​=yi​))表示预测值和实际值不相等的概率，$I()$I()是指示函数，当其条件满足时值为1，反之为0。

​ 值得注意的是，在二分类问题中，一个分类器的效果往往要优于随机分类的效果，所以以上分类误差率的取值范围应该为 [0, 0.5]

​ **（c）**计算$G_m(x)$Gm​(x)的系数
$\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}$αm​=21​logem​1−em​​
​ 该系数在由弱分类器线性组合为强分类器时起作用，它表示分类器$G_m(x)$Gm​(x)在最终分类器中的重要程度。$\log\frac{1-x}{x}$logx1−x​的函数图像如下所示，当自变量（分类误差率）的取值范围为 [0, 0.5] 时，$\alpha_m$αm​是恒大于0的。

​ **（d）**更新训练数据集的权值分布
$W_{m+1}=(w_{m+1,1},w_{m+1,2},...,w_{m+1,N})$Wm+1​=(wm+1,1​,wm+1,2​,...,wm+1,N​)

$w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_m y_i G_m(x_i))$wm+1,i​=Zm​wmi​​exp(−αm​yi​Gm​(xi​))

​ 上式中$Z_m$Zm​是规范化因子，它可以使更新后的权重成为一个概率分布。
$Z_m=\sum_{i=1}^N{w_{mi}exp(-\alpha_m y_iG_m(x_i))}$Zm​=i=1∑N​wmi​exp(−αm​yi​Gm​(xi​))
​ 当某样本分类正确时，$y_iG_m(x_i)$yi​Gm​(xi​)大于0，又$\alpha_m$αm​是非负数，所以更新后该样本的权重是小于1的；反之，更新后样本的权重是大于1的。这也就满足了误分类样本的权值得以扩大，而正确分类的样本的权值得以缩小（更重视分类错误的样本）。

**(3) ** 得到M个弱分类器及其系数$\alpha_m$αm​后，则可以得到它们的线性组合
$f(x)=\sum_{m=1}^M{\alpha_mG_m(x)}$f(x)=m=1∑M​αm​Gm​(x)
​ 值得注意的是，$\alpha_m$αm​之和并不为1。

​ 于是最终的强分类器是：
$G(x)=sign(f(x))=sign(\sum_{m=1}^M{\alpha_mG_m(x)})$G(x)=sign(f(x))=sign(m=1∑M​αm​Gm​(x))

三、加法模型和前向分步算法

加法模型：
$f(x)=\sum_{m=1}^M{\beta_mb(x;\gamma_m)}$f(x)=m=1∑M​βm​b(x;γm​)
其中，$b(x;\gamma_m)$b(x;γm​)是一个基函数，$\gamma_m$γm​是该基函数的参数，$\beta_m$βm​是该基函数的系数。

前向分步算法：

对于以上加法模型，在给定损失函数 L(y, f(x)) 的前提下，要学习使得模型最优的$\beta_m$βm​和$\gamma_m$γm​就是求解以下损失函数最小化问题：
$min_{\beta_m,\gamma_m}\sum_{i=1}^N{L(y_i,\sum_{m=1}^M{\beta_mb(x;\gamma_m))}}$minβm​,γm​​i=1∑N​L(yi​,m=1∑M​βm​b(x;γm​))
而要同时求出从m=1到M的所有参数是比较困难的，所以人们提出了前向分步算法（foward stagewise algorithm），它的思想是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其参数，并逐步逼近优化目标函数式（以上损失函数最小化公式），那么就可以简化优化的复杂度。

算法流程如下：

(1) 初始化加法模型：
$f_0(x)=0$f0​(x)=0
(2) 对m=1,2,…,M

​ (a) 极小化损失函数
$(\beta_m,\gamma_m)=arg\min_{\beta,\gamma}\sum_{i=1}^N{L(y_i,\sum_{m=1}^M{\beta_mb(x;\gamma_m))}}$(βm​,γm​)=argβ,γmin​i=1∑N​L(yi​,m=1∑M​βm​b(x;γm​))
​ 得到参数$\beta_m,\gamma_m$βm​,γm​，从而也就确定了第m个基函数

​ (b) 更新第m个加法模型
$f_m(x)=f_{m-1}(x)+\beta_mb(x;\gamma_m)$fm​(x)=fm−1​(x)+βm​b(x;γm​)
​ 即第m个加法模型为当前（第m-1个）加法模型和第m个基函数的加权和。

(3) 得到最终的加法模型：
$f(x)=f_M(x)=\sum_{m=1}^M{\beta_mb(x;\gamma_m)}$f(x)=fM​(x)=m=1∑M​βm​b(x;γm​)
前向分步算法将同时求出从m=1到M的所有参数$\beta_m,\gamma_m$βm​,γm​的优化问题简化为了逐步求解各个$\beta_m,\gamma_m$βm​,γm​的优化问题。

四、梯度提升决策树

梯度提升决策树（GBDT）是提升决策树和梯度提升算法相结合的产物，下面先来讲解提升（决策）树，这是一种采用加法模型和前向分步算法的决策树，其模型为：
$f_M(x)=\sum_{m=1}^M{T(x;\theta_m)}$fM​(x)=m=1∑M​T(x;θm​)
其中$T(x;\theta_m)$T(x;θm​)是决策树，$\theta_m$θm​是该决策树的参数，M是决策树的个数。本模型是《统计学习方法》中给出的，我有点好奇为什么每个决策树之前没有系数，有知道的朋友还请告知~

提升树算法流程如下：

(1) 初始的加法模型为：
$f_0(x)=0$f0​(x)=0
(2) 在生成第m个加法模型时

​ (a) 根据当前模型$f_{m-1}(x)$fm−1​(x)，找到一个可以使得第m个加法模型最优的决策树$T(x;\theta_m)$T(x;θm​)
$\hat{\theta_m}=arg\min_{\theta_m}\sum_{i=1}^N{L(y_i,f_{m-1}(x_i)+T(x;\theta_m))}$θm​^​=argθm​min​i=1∑N​L(yi​,fm−1​(xi​)+T(x;θm​))
​ 也就是找到该决策树的参数$\hat{\theta_m}$θm​^​

​ (b) 生成第m个加法模型：
$f_m(x)=f_{m-1}(x)+T(x;\theta_m)$fm​(x)=fm−1​(x)+T(x;θm​)
(3) 最终的加法模型为：
$f_M(x)=\sum_{m=1}^M{T(x;\theta_m)}$fM​(x)=m=1∑M​T(x;θm​)
在以上第(2)步，(a)步骤时，如果损失函数是平方误差损失，则
$L(y_i,f_{m-1}(x_i)+T(x;\theta_m))=[y-f_{m-1}(x)-T(x;\theta_m)]^2$L(yi​,fm−1​(xi​)+T(x;θm​))=[y−fm−1​(x)−T(x;θm​)]2
其中$y-f_{m-1}(x)$y−fm−1​(x)是数据的残差，即观测值与估计值之差。

对于一般的损失函数来说，求解最优的$\hat{\theta_m}$θm​^​是不容易的，所以有人提出了用**梯度提升（gradient boosting）**算法，用损失函数的负梯度在当前模型的值来作为上式中残差值的近似，从而简化求解$\hat{\theta_m}$θm​^​的过程。

加入了梯度提升算法的提升决策树就被称为梯度提升决策树。

五、XGBoost

XGBoost是一种二分类器，它的基本思想和GBDT类似，学习该方法应该提前掌握加法模型、前向分步算法和决策树的相关内容。

先来回顾一下，决策树的基本思想是：从根节点开始，每次选择一个最优特征对当前样本进行划分，并生成相应的子节点，递归的进行这一过程，直到叶节点中包含的样本都是同一类别或没有合适的特征为止。对于决策树中的叶子节点来说，它表示其内的样本属于该类别的概率值。通常来说只用一棵决策树进行分类的效果是不怎么好的，所以有人就考虑——如果使用多棵决策树进行分类呢？如果在决策树$T_1$T1​中样本$S$S所属的叶节点权重为1.3，而在决策树$T_2$T2​中样本$S$S所属的叶节点权重为0.8，则该样本最终的权重是2.1（可以理解为得分，得分越高，属于该类别的概率越大）。

XGBoost的算法流程：

(1) 初始的预测模型（加法模型）为：
$\hat{y}_i^{(0)}=0$y^​i(0)​=0
(2) 在生成第t个预测模型时

​ (a) 根据一定的规则生成一棵当前最优的决策树$f_{t-1}(x_i)$ft−1​(xi​)，具体生成方面后面会说明；

​ (b) 生成第t个预测模型：
$\hat{y}_i^{(t)}=\hat{y}_i^{(t-1)}+f_{t-1}(x_i)$y^​i(t)​=y^​i(t−1)​+ft−1​(xi​)
(3) 最终的预测模型为：
$\hat{y}_i^{(T)}=\sum_{t=1}^M{f_{t}(x_i)}$y^​i(T)​=t=1∑M​ft​(xi​)
在上述第(2)步，(a)步骤的时候，设生成决策树的目标函数为：
$J(f_t)=\sum_{i=1}^nL(y_i,\hat{y}_t^{(t-1)}+f_t(x_i))+\Omega(f_t)$J(ft​)=i=1∑n​L(yi​,y^​t(t−1)​+ft​(xi​))+Ω(ft​)
在某些书籍中以上目标函数还会有个常数项$c$c，上式中n是样本个数，$L()$L()是损失函数，$\Omega(f_t)$Ω(ft​)是关于决策树的正则项，其定义如下：
$\Omega(f_t)=\gamma\cdot T_t+\lambda\cdot\frac{1}{2}\sum_{i=1}^T{w_j^2}$Ω(ft​)=γ⋅Tt​+λ⋅21​i=1∑T​wj2​
上式中，$T_t$Tt​是当前决策树的叶节点个数，$w_j$wj​是叶节点的权重，$\gamma$γ和$\lambda$λ是系数。即正则项为节点总数和叶节点权值平方和的加权和。

要想求一棵当前最优的决策树，则就要求一棵决策树从而使得其目标函数最小。为了方便处理，我们需要对决策树的目标函数做一系列变换。我们知道泰勒展开的二阶形式如下：
$f(x+\Delta x)=f(x)+f^`(x)\Delta x+\frac{1}{2}f^{``}(x)\Delta x^2$f(x+Δx)=f(x)+f‘(x)Δx+21​f‘‘(x)Δx2
对于损失函数$L()$L()，将其看作函数$f()$f()，将其中的$\hat{y}_i^{(t-1)}$y^​i(t−1)​看作$x$x，将$f_t(x_i)$ft​(xi​)看作$\Delta x$Δx，另：
$g_i=\frac{\partial L(y_i,\hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}$gi​=∂y^​i(t−1)​∂L(yi​,y^​i(t−1)​)​

$h_i=\frac{\partial^2 L(y_i,\hat{y}_i^{(t-1)})}{\partial^2 \hat{y}_i^{(t-1)}}$hi​=∂2y^​i(t−1)​∂2L(yi​,y^​i(t−1)​)​

然后将损失函数在$x=0$x=0处进行二阶泰勒展开，并带入到目标函数中得：
$J(f_t)=\sum_{i=1}^n{[L(y_i,\hat{y}_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]}+\Omega(f_t)$J(ft​)=i=1∑n​[L(yi​,y^​i(t−1)​)+gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)
然后对上式进行整理：

上图中第一行到第二行之间，因为$L(y_i,\hat{y}_i^{(t-1)})$L(yi​,y^​i(t−1)​)是一个常数，在求解最优决策树时不会产生影响，所以就给去除了。第三行中$q(x_i)$q(xi​)表示样本$x_i$xi​所在叶节点编号，$w_{q(x_i)}$wq(xi​)​表示该叶节点的权重。此外，第三行中的$\sum$∑是遍历的样本，第四行中的$\sum$∑是遍历的叶节点，这个点需要注意。

为了方便表示，我们定义：
$G_j=\sum_{i\in I_j}{g_i}$Gj​=i∈Ij​∑​gi​

$H_j=\sum_{i\in I_j}{h_i}$Hj​=i∈Ij​∑​hi​

经过以上的化简和整理，得到目标函数：
$J(f_t)=\sum_{j=1}^T{[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2]}+\gamma\cdot T$J(ft​)=j=1∑T​[Gj​wj​+21​(Hj​+λ)wj2​]+γ⋅T
到目前为止，我们做的只是对目标函数的化简，下一步就要根据目标函数构造出一棵使得目标函数值最小的决策树，也就是求决策树最优的叶节点的权值。让目标函数对叶节点权值$w_j$wj​求偏导，并令其为0得：
$\frac{\partial J(t_t)}{\partial w_j}=G_j+(H_j+\lambda)w_j=0$∂wj​∂J(tt​)​=Gj​+(Hj​+λ)wj​=0

$\Rightarrow\quad w_j=-\frac{G_j}{H_j+\lambda}$⇒wj​=−Hj​+λGj​​

再将最优的权值带入到目标函数，可得：
$J(f_t)=-\frac{1}{2}\sum_{j=1}^T{\frac{G_j^2}{H_j+\lambda}}+\gamma\cdot T$J(ft​)=−21​j=1∑T​Hj​+λGj2​​+γ⋅T
需要说明的是，在XGBoost算法中，所构建的决策树是二叉树。已经知道了叶节点权值最优时目标函数的表达式，那么如何构建决策树呢？这里采用的是贪心的策略，如果根据某个特征对决策树进行划分，则划分后比划分前目标函数值降低的量越大，说明该划分越优。所以可以遍历所有可能的划分，取目标函数值降低最大的特征进行划分。

设划分后形成的左子树为L，右子树为R，则划分后目标函数值降低的量为：
$Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]-\gamma$Gain=21​[HL​+λGL2​​+HR​+λGR2​​−HL​+HR​+λ(GL​+GR​)2​]−γ
以上Gain就相当于普通决策树中的信息增益/信息增益率/Gini系数了。

XGBoost与BGDT的主要区别：

(1) XGBoost的损失函数增加了正则项，而GBDT没有。

(2) XGBoost损失函数是误差部分是二阶泰勒展开，GBDT 是一阶泰勒展开。因此损失函数近似的更精准。