机器学习算法原理篇之集成学习

2019-02-22 本文已影响9人 TuringWong

1. 集成算法原理

集成学习(ensemble learning)本身不是一个单独的机器学习算法，而是通过构建并结合多个机器学习器来完成学习任务。也就是我们常说的“博采众长”。集成学习可以用于分类问题集成，回归问题集成，特征选取集成，异常点检测集成等等，可以说所有的机器学习领域都可以看到集成学习的身影。

1.1 集成学习概述

对于训练集数据，我们通过训练若干个个体学习器，通过一定的结合策略，就可以最终形成一个强学习器，以达到博采众长的目的。集成学习有两个主要的问题需要解决，第一是如何得到若干个个体学习器，第二是如何选择一种结合策略，将这些个体学习器集合成一个强学习器。

1.2 个体学习器选择

通常情况下，个体学习器有两种选择，一种是所有个体学习器都是同一种类型，称为同质个体学习器；另一种是所有个体学习器不完全相同，称为异质个体学习器。同质个体学习器的应用是最广泛的，一般我们常说的集成学习的方法都是指的同质个体学习器。根据不同的结合策略，可以将集成学习分为bagging算法、boosting算法和stacking算法。

1.3 集成学习之boosting

Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。Boosting系列算法里最著名算法主要有AdaBoost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)。

1.4 集成学习之bagging

bagging的个体弱学习器的训练集是通过随机采样得到的。通过T次的随机采样，我们就可以得到T个采样集，对于这T个采样集，我们可以分别独立的训练出T个弱学习器，再对这T个弱学习器通过集合策略来得到最终的强学习器。

这里一般采用的是自助采样法（Bootstap sampling）,即对于m个样本的原始训练集，我们每次先随机采集一个样本放入采样集，接着把该样本放回，也就是说下次采样时该样本仍有可能被采集到，这样采集m次，最终可以得到m个样本的采样集，由于是随机采样，这样每次的采样集是和原始训练集不同的，和其他采样集也是不同的，这样得到多个不同的弱学习器。

1.5 集成学习之stacking

stacking采用两阶段算法，第一阶段利用一组训练样本训练多个基学习器，第二阶段将训练好的所有基模型对另外一组训练集进行预测，将多个基学习器的预测结果作新的训练集，最后基于新的训练集进行训练得到第二阶段的学习器。同理，预测的过程也要先经过所有基模型的预测形成新的测试集，最后再对测试集进行预测。

stacking中弱学习器与最终学习器的联系有三种方法。第一，直接以弱学习器的输出结果作为最终学习器的输入特征；第二，使用弱学习器输出的概率作为最终学习器的输入特征；第三，对训练基中的特征维度进行操作的，不是给每一个基分类器全部的特征，而是给不同的基分类器分不同的特征进行训练，最终通过StackingClassifier组合起来。

1.6 集成学习之结合策略

平均法
$H(x) = \sum_{i=1}^{n}w_ih_i(x)$
其中 $w_i$ 为基学习器的权重， $h_i(x)$ 为各基学习器的预测结果

投票法

对于分类问题的预测，我们通常使用的是投票法。

最简单的投票法是相对多数投票法，也就是我们常说的少数服从多数，也就是T个弱学习器的对样本x的预测结果中，数量最多的类别ci为最终的分类类别。如果不止一个类别获得最高票，则随机选择一个做最终类别。
稍微复杂的投票法是绝对多数投票法，也就是我们常说的要票过半数。在相对多数投票法的基础上，不光要求获得最高票，还要求票过半数。否则会拒绝预测。
更加复杂的是加权投票法，和加权平均法一样，每个弱学习器的分类票数要乘以一个权重，最终将各个类别的加权票数求和，最大的值对应的类别为最终类别。

学习法

学习法，代表方法是stacking，当使用stacking的结合策略时，我们不是对弱学习器的结果做简单的逻辑处理，而是再加上一层学习器，也就是说，我们将训练集弱学习器的学习结果作为输入，将训练集的输出作为输出，重新训练一个学习器来得到最终结果，具体如上节所示。

2. Adaboost 算法

Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。

boosting算法要解决的几个具体问题：

如何计算学习误差率e?
如何得到弱学习器权重系数α?
如何更新样本权重D?
使用何种结合策略？

2.1 Adaboost算法的基本思路

2.1.1 假设及变量说明

假设训练集样本如下：
$T = \{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\}\tag{1}$
训练集在第 $k$ 个弱学习器的输出权重：
$D(k) = (w_{k1},w_{k2},...w_{km}); w_{1i}=\frac{1}{m};i=1,2...m\tag{2}$

2.1.2 Adaboost分类问题

由于多元分类是二元分类的推广，这里假设我们是二元分类问题，分类标签输出为 $\{-1,1\}$ ，Adaboost算法采用指数损失函数评估模型
$loss\_function = \sum_{i=1}^{m}exp(-y_if(x_i))\tag{3}$
其中 $f(x)$ 为强学习器，Adboost采用前向分布学习算法，利用前
一个弱学习器的结果来更新后一个弱学习器的训练权重，第k-1轮强学习器为
$f_{k-1}(x)=\sum_{i=1}^{k-1}\alpha_iG_i(x)\tag{4}$
第k轮强学习器为
$f_{k}(x)=\sum_{i=1}^{k}\alpha_iG_i(x)=f_{k-1}(x)+\alpha_kG_k{(x)}\tag{5}$
其中 $G_k(x)$ 为第k轮弱学习器, $\alpha_k$ 为第k轮弱学习器的权重，前向分布学习算法本质上是一种局部寻优的贪心算法，每次只针对本轮强学习器的损失函数进行优化，具体如下：
$(\alpha_k,G_k(x))=\underbrace{argmin}_{\alpha,G}\sum_{i=1}^{m}exp[(-y_i)(f_{k-1}(x_i)+{\alpha_k}G_k(x_i))]\tag{6}$
令 $w_{ki}^{'}=exp(-y_if_{k-1}(x_i))$ ，它的值不依赖于 $\alpha_k,G_k$ ，仅仅与 $f_{k-1}(x)$ 有关，随着每一轮迭代而改变，将该式代入上式中，损失函数转化如下：
$(\alpha_k,G_k(x))=\underbrace{argmin}_{\alpha,G}\sum_{i=1}^{m}{w_{ki}^{'}}exp[{-y_i\alpha_k}G_k(x_i)]\tag{7}$
其中 $y_i,G_k(x_i)\in\{-1,1\}$ ，可进一步转化为
$(\alpha_k,G_k(x))=\underbrace{argmin}_{\alpha,G}(\sum_{y_i=G_k(x_i)}{w_{ki}^{'}}exp(-\alpha_k)+\sum_{y_i\neq{G_k(x_i)}}{w_{ki}^{'}}exp\alpha_k)\tag{8}$
$\Downarrow$
$(\alpha_k,G_k(x))=\underbrace{argmin}_{\alpha,G}(\sum_{i=1}^{m}{w_{ki}^{'}}exp(-\alpha_k)+\sum_{y_i\neq{G_k(x_i)}}{w_{ki}^{'}}[exp(\alpha_k)-exp(-\alpha_k)])\tag{9}$
$\Downarrow$
$(\alpha_k,G_k(x))=\underbrace{argmin}_{\alpha,G}(exp(-\alpha_k)\sum_{i=1}^{m}{w_{ki}^{'}}+[exp(\alpha_k)-exp(-\alpha_k)]\sum_{i=1}^{m}{w_{ki}^{'}I(y_i\neq{G_k(x_i))}})\tag{10}$
对于任意 $\alpha_k$ ,使上式最优，则有最优第k轮弱学习器必须满足
$G_{k}^{*}(x)=\underbrace{argmin}_{G}\sum_{i=1}^{m}{w_{ki}^{'}I(y_i\neq{G_k(x_i))}}\tag{11}$

Notice:
由式(11)可知，要使第k轮强学习器损失函数最小，必须先保证第k轮弱学习器对于带权重的样本拟合效果最优。

进一步将 $G_{k}^{*}(x)$ 代入式(10),并对 $\alpha_k$ 求导，并使导数为0，可得到最优的 $\alpha_k$
$\alpha_k^*=\frac{1}{2}\log\frac{1-e_k}{e_k}\tag{12}$
其中
$e_k=\frac{\sum_{i=1}^{m}{w_{ki}^{'}I(y_i\neq{G_k(x_i))}}}{\sum_{i=1}^{m}{w_{ki}^{'}}}=\sum_{i=1}^{m}\frac{w_{ki}^{'}}{\sum_{i=1}^{m}{w_{ki}^{'}}}I(y_i\neq{G_k(x_i))}=\sum_{i=1}^{m}w_{ki}I(y_i\neq{G_k(x_i))}\tag{13}$

推导到这里，我们不得不稍作停歇，回到本节开头提到的boosting算法要解决的4个问题，发现由式（12）和式（13）基本上已经解决了误差率和弱学习器权重的问题，接下来要解决的就是如何更新样本权重！

由以上可知
$w_{k+1,i}^{'}=exp(-y_if_{k}(x_i))=w_{k,i}^{'}exp(-y_i\alpha_kG_{k}(x_i))\tag{14}$
$\Downarrow$
$w_{k+1,i}=\frac{w_{k+1,i}^{'}}{\sum_{i=1}^{m}{w_{k+1,i}^{'}}}=\frac{w_{k,i}^{'}exp(-y_i\alpha_kG_{k}(x_i))}{\sum_{i=1}^m{w_{k,i}^{'}exp(-y_i\alpha_kG_{k}(x_i))}}=\frac{w_{k,i}exp(-y_i\alpha_kG_{k}(x_i))}{\sum_{i=1}^m{w_{k,i}exp(-y_i\alpha_kG_{k}(x_i))}}\tag{15}$
式（15）就定义了样本权重的迭代方式，同时，我们发现对于同一个弱学习器的同一个样本，分类错误样本权重放大，分类正确则样本权重缩小，二者相比，权重放大了 $exp^{2\alpha_k}$ 倍。

接下就解决第4个问题——使用何种组合策略？
Adboost的组合策略可以采用以下方式，最终的强学习器表达如下：
$F(x)=sign(f(x))=sign(\sum_{i=1}^{K}\alpha_iG_i(x))\tag{16}$
Adaboost二元分类算法流程：

初始化样本集权重为

$D(1) = (w_{11},w_{12},...w_{1m}); w_{1i}=\frac{1}{m};i=1,2...m$
对于 $k=1,2,...K$
- 使用具有权重 $D_k$ 的样本集来训练数据，得到弱分类器 $G_k(x)$
- 计算 $G_k(x)$ 的分类误差率
  $e_k=\sum_{i=1}^{m}w_{ki}I(y_i\neq{G_k(x_i))}$
- 计算弱分类器的系数
  $\alpha_k=\frac{1}{2}\log\frac{1-e_k}{e_k}$
- 更新样本集权重 $w_{k+1,i}$
  $w_{k+1,i}=\frac{w_{ki}exp(-y_i\alpha_kG_{k}(x_i))}{\sum_{i=1}^m{w_{ki}exp(-y_i\alpha_kG_{k}(x_i))}}$
构建最终分类器为：
$F(x)=sign(f(x))=sign(\sum_{i=1}^{K}\alpha_iG_i(x))$

对于Adaboost多元分类算法，其实原理和二元分类类似，最主要区别在弱分类器的系数上。比如Adaboost SAMME算法，它的弱分类器的系数
$\alpha_k=\frac{1}{2}\log\frac{1-e_k}{e_k}+\log(R-1)$
其中R为类别数。从上式可以看出，如果是二元分类，R=2，则上式和我们的二元分类算法中的弱分类器的系数一致。

2.2 Adaboost算法的正则化

为了防止Adaboost过拟合，我们通常也会加入正则化项，这个正则化项我们通常称为步长(learning rate)。定义为 $\upsilon$ ,对于前面的弱学习器的迭代
$f_{k}(x)=f_{k-1}(x)+\alpha_kG_k{(x)}$
如果加了正则化项，则有
$f_{k}(x)=f_{k-1}(x)+\upsilon\alpha_kG_k{(x)}$
$\upsilon$ 的取值范围为 $0<\upsilon≤1$ 。对于同样的训练集学习效果，较小的 $\upsilon$ 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

2.3 Adaboost小结

理论上任何学习器都可以用于Adaboost.但一般来说，使用最广泛的Adaboost弱学习器是决策树和神经网络。对于决策树，Adaboost分类用了CART分类树，而Adaboost回归用了CART回归树。

Adaboost优点
- Adaboost作为分类器时，分类精度很高
- 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
- 作为简单的二元分类器时，构造简单，结果可理解。
- 不容易发生过拟合
Adaboost缺点
- 对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

3. GBDT 算法

在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是 $f_{t−1}(x)$ , 损失函数是 $L(y,f_{t−1}(x))$ , 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器 $h_t(x)$ ，让本轮的损失损失 $L(y,f_t(x)=L(y,f_{t−1}(x)+h_t(x))$ 最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。

GBDT算法中的几个关键说明：

弱学习器只能是CART回归树
GBDT可以用于分类也可以用于回归

3.1 GBDT算法的基本思路

3.1.1 GBDT的负梯度拟合

GBDT算法每轮拟合的对象是前一轮损失函数的负梯度，采用的基学习器是CART回归树，第t轮的第i个样本的损失函数的负梯度表示如下：
$r_{ti}=-[\frac{\partial{L(y_i,f(x_i))}}{\partial{f(x_i)}}]_{f(x)=f_{t-1}(x)}$
利用 $(x_i,r_{ti})(i=1,2,..m)$ ,我们可以拟合一颗CART回归树，得到了第t颗回归树，其对应的叶节点区域 $R_{tj},j=1,2,...,J$ 。其中J为叶子节点的个数。针对每一个叶子节点里的样本，我们求出使损失函数最小，也就是拟合叶子节点最好的的输出值 $c_{tj}$ 如下：
$c_{tj}=\underbrace{argmin}_c\sum_{x_i\in{R_{tj}}}L(y_i,f_{t-1}(x_i)+c)$
这样我们就得到了本轮的决策树拟合函数如下：
$h_t(x)=\sum_{j=1}^Jc_{tj}I(x\in{R_{tj}})$
从而本轮最终得到的强学习器的表达式如下：
$f_t(x)=f_{t-1}(x)+\sum_{j=1}^{J}c_{tj}I(x\in{R_{tj}})$
通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。

3.1.2 GBDT回归算法

输入是训练集样本 $T=\{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\}$ ，弱学习器算法为 $G_k(x)$ ，最大迭代次数T, 损失函数L，输出强学习器 $f(x)$

初始化弱学习器
$f_0(x)=\underbrace{argmin}_c\sum_{i=1}^{m}L(y_i,c)$
对迭代轮数有
- 对样本 $i=1,2，...m$ ，计算负梯度
  $r_{ti}=-[\frac{\partial{L(y_i,f(x_i))}}{\partial{f(x_i)}}]_{f(x)=f_{t-1}(x)}$
- 利用 $(x_i,r_{ti})(i=1,2,..m)$ , 拟合一颗CART回归树,得到第t颗回归树，其对应的叶子节点区域为 $R_{tj},j=1,2,...,J$ 。其中J为回归树t的叶子节点的个数。
- 对叶子区域 $j =1,2,..J$ ,计算最佳拟合值
  $c_{tj}=\underbrace{argmin}_c\sum_{x_i\in{R_{tj}}}L(y_i,f_{t-1}(x_i)+c)$
- 更新强学习器
  $f_t(x)=f_{t-1}(x)+\sum_{j=1}^{J}c_{tj}I(x\in{R_{tj}})$
得到强学习器 $f(x)$ 的表达式
$f(x)=f_T(x)=f_0(x)+\sum_{t=1}^{T}\sum_{j=1}^Jc_{tj}I(x\in{R_{tj}})$

3.1.3 GBDT分类算法

GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。

二元GBDT分类算法

对于二元GBDT，如果用类似于逻辑回归的对数似然损失函数，则损失函数为：
$L(y,f(x))=-\log{p(y|x)}=\log(1+e^{-yf(x}))$
其中 $y\in\{-1,+1\}$ ，
$p(y=+1|x)=\frac{1}{1+e^{-f(x)}}$
,
$p(y=-1|x)=\frac{e^{-f(x)}}{1+e^{-f(x)}}$
$f(x)=\log{\frac{p(y=+1|x)}{p(y=-1|x)}}$

则此时的负梯度误差为
$r_{ti}=-[\frac{\partial{L(y_i,f(x_i))}}{\partial{f(x_i)}}]_{f(x)=f_{t-1}(x)}=\frac{y_i}{1+e^{y_if(x_i)}}$
算法步骤如下：

初始化弱学习器
$f_0(x)=\frac{1}{2}\log{\frac{\sum_{i=1}^{m}{I(y_i=+1)}}{\sum_{i=1}^{m}{I(y_i=-1)}}}$
对迭代轮数有
- 对样本 $i=1,2，...m$ ，计算负梯度
  $r_{ti}=-[\frac{\partial{L(y_i,f(x_i))}}{\partial{f(x_i)}}]_{f(x)=f_{t-1}(x)}$
- 利用 $(x_i,r_{ti})(i=1,2,..m)$ , 拟合一颗CART回归树,得到第t颗回归树，其对应的叶子节点区域为 $R_{tj},j=1,2,...,J$ 。其中J为回归树t的叶子节点的个数。
- 对叶子区域 $j =1,2,..J$ ,计算最佳拟合值
  $c_{tj}=\underbrace{argmin}_c\sum_{x_i\in{R_{tj}}}L(y_i,f_{t-1}(x_i)+c)$
  由于上式比较难优化，我们一般使用近似值代替
  $c_{tj}=\frac{\sum_{x_i\in{R_tj}}r_{tj}}{\sum_{x_i\in{R_tj}}|r_{tj}|(1-|r_{tj}|)}$
- 更新强学习器
  $f_t(x)=f_{t-1}(x)+\eta\sum_{j=1}^{J}c_{tj}I(x\in{R_{tj}})$
得到强学习器 $f(x)$ 的表达式
$f(x)=f_T(x)=f_0(x)+\eta\sum_{t=1}^{T}\sum_{j=1}^Jc_{tj}I(x\in{R_{tj}})$

3.1.4 GBDT正则化

和Adaboost一样，我们也需要对GBDT进行正则化，防止过拟合。GBDT的正则化主要有三种方式。

第一种是和Adaboost类似的正则化项，即步长(learning rate)。定义为 $\upsilon$ ,对于前面的弱学习器的迭代
$f_k(x)=f_{k-1}(x)+\upsilon{h_k(x)}$
第二种正则化的方式是通过子采样比例（subsample）。取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。
第三种是对于弱学习器即CART回归树进行正则化剪枝。

3.1.5 GBDT小结

优点
1. 可以灵活处理各种类型的数据，包括连续值和离散值；
2. 在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对SVM来说的。
3. 使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
缺点
1. 由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

4. xgboost算法

由于GBDT除了L2损失函数之外，对其它的损失函数推导比较复杂。而XGBoost采用对损失函数进行二阶Taylor展开来近似。简化了求解与推导。理论上xgboost可以选用任何算法作为弱学习器，但一般还是用决策树，下面针对以决策树为弱分类器进行xgboost算法的推导。

4.1 xgboost的拟合对象与损失函数

我们知道xgboost算法属于boosting族中的一种，最终的学习器是由多个弱学习器直接线性相加而成（注意GBDT在线性组合时针对每个弱学习器会增加学习率系数），用数学表达式如下：
$\hat{y_i}=\sum_{k=1}^Kf_k(x_i),f_k\in{F}$
这里的K就是树的棵数，F表示所有可能的CART树，f表示一棵具体的决策树。那 $f(x)$ 具体取值是什么呢？（或者我们拟合的对象是什么呢）我们知道GBDT算法拟合的是负梯度，也可以叫做伪残差，弱学习器的拟合对象线性组合起来的强学习器拟合指标直接对应着回归问题的值或者分类问题的概率（或者其他可以基于该指标进行分类的对象），xgboost拟合的对象也是如此，这点我们可以从上面模型表达式看出。

模型表示出来后，我们自然而然就想问，第一，这个模型的参数是什么？因为我们知道，“知识”蕴含在参数之中。第二，用来优化这些参数的损失函数又是什么？

4.1.1 xgboost损失函数

我们先来看第二个问题，模型的损失函数，如下所示：
$L(F)=\sum_{i=1}^nl(y_i,\sum_{k=1}^Kf_k(x_i))+\sum_{k=1}^K\Omega(f_k)=\sum_{i=1}^nl(y_i,\hat{y_i})+\sum_{k=1}^K\Omega(f_k),f_k\in{F}$
其中 $y_i$ 为训练样本的标签实际值， $f_k$ 为第k个弱学习器， $f_k(x_i)$ 为第k个弱学习器对于样本 $x_i$ 的拟合输出值， $l$ 为弱学习器选用的损失函数（这里并没有明确是哪个）， $\Omega(f_k)$ 为第k个弱学习器的正则化项，具体表达式是什么这里先不明确，后面有介绍。

可知，xgboost的损失函数由两部分组成，第一部分是弱学习器选用的损失函数，第二部分是弱学习器正则化项的线性相加。

4.1.2 xgboost模型参数

回到机器学习的通识问题，训练模型的本质是什么呢？模型训练的本质就是找到一个映射关系 $f$ （中学课本叫函数），使得 $x\longrightarrow^{f}{\hat{y}}$ 尽可能的接近实际 $y$ ，这里 $f$ 涉及到两方面，第一， $f$ 的类型（多项式函数、指数函数...）；第二， $f$ 中具体的参数。同理，xgboost算法训练的目的也是类似，第一，弱学习器的组合方式，这个已经确定加法组合；第二，弱学习器的函数形式，当选用决策树时，我们要确定树的结构，即每一层选择的特征、特征的阈值、树的层数等等；第三，每个叶子节点的输出值。

让我们想像一下，如果K棵树的结构都已经确定，那么整个模型剩下的就是所有K棵树的叶子节点的值，模型的正则化项也可以设为各个叶子节点的值的平方和。此时，整个目标函数其实就是一个K棵树的所有叶子节点的值的函数，我们就可以使用梯度下降或者随机梯度下降来优化损失函数。现在这个办法不灵了，必须另外寻找办法。

4.2 xgboost推导之加法训练

所谓加法训练，本质上是一个元算法，适用于所有的加法模型，它是一种启发式算法。运用加法训练，我们的目标不再是直接优化整个损失函数，这已经被我们证明是行不通的。而是分步骤优化损失函数，首先优化第一棵树，完了之后再优化第二棵树，直至优化完K棵树。整个过程如下图所示：
$\begin{align} \hat{y_i}^{(1)}&=f_1(x_i)=0\\ \hat{y_i}^{(2)}&=\hat{y_i}^{(1)}+f_2(x_i)\\ \hat{y_i}^{(3)}&=\hat{y_i}^{(2)}+f_3(x_i)\\ &...\\ \hat{y_i}^{(t)}&=\sum_{k=1}^tf_k(x_i)=\hat{y_i}^{(t-1)}+f_t(x_i)\\ \end{align}$
在第t步时，我们添加了一棵最优的决策树 $f_t$ ，这棵最优的决策树 $f_t$ 是怎么得来的呢？非常简单，就是在现有的 $t-1$ 棵树的基础上，使得目标函数最小的那棵决策树，如下图所示：
$\begin{align} L^{(t)}(f_t)&=\sum_{i=1}^nl(y_i,\hat{y_i}^{(t)})+\sum_{k=1}^t\Omega(f_k)\\ &=\sum_{i=1}^nl(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant \end{align}$
其中 $constant$ 为前 $t-1$ 棵树的正则化项，在训练第 $t$ 棵树时作为常量存在，与 $f_t$ 无关。
假如我们使用的损失函数是均方误差MSE，那么上述表达式会变成这个样子：
$\begin{align} L^{(t)}(f_t)&=\sum_{i=1}^nl(y_i,\hat{y_i}^{(t)})+\sum_{k=1}^t\Omega(f_k)\\ &=\frac{1}{2n}\sum_{i=1}^n[y_i-(\hat{y_i}^{(t-1)}+f_t(x_i))]^2+\Omega(f_t)+constant\\ &=\frac{1}{2n}\sum_{i=1}^n[2(\hat{y_i}^{(t-1)}-y_i)f_t(x_i)+f_t^2(x_i)]+\Omega(f_t)+constant \end{align}$
这个式子非常漂亮，因为它含有 $f_t(x_i)$ 的一次式和二次式，而且一次式项的系数是残差。你可能好奇，为什么有一次式和二次式就漂亮，因为它会对我们后续的优化提供很多方便，继续前进你就明白了。

注意： $f_t(x_i)$ 是什么？它其实就是 $f_t$ 的某个叶子节点的值。之前我们提到过，叶子节点的值是可以作为模型的参数的。
但是对于其他的损失函数，我们未必能得出如此漂亮的式子，所以，对于一般的损失函数，我们需要将其作泰勒二阶展开，如下所示：
$\begin{align} L^{(t)}(f_t)&=\sum_{i=1}^nl(y_i,\hat{y_i}^{(t)})+\sum_{k=1}^t\Omega(f_k)\\ &=\sum_{i=1}^nl(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant\\ &=\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)+constant \end{align}$
其中：
$g_i=\frac{\partial{l(y_i,\hat{y_i}^{(t-1)})}}{\partial{\hat{y_i}^{(t-1)}}}\\ h_i=\frac{\partial^2{l(y_i,\hat{y_i}^{(t-1)})}}{\partial{(\hat{y_i}^{(t-1)}})^2}\\$
这里有必要再明确一下， $g_i和h_i$ 的含义。 $g_i$ 怎么理解呢？现有 $t-1$ 棵树是不是？这 $t-1$ 棵树组成的模型对第 $i$ 个训练样本有一个预测值 $\hat{y_i}^{(t-1)}$ 是不是？这个 $\hat{y_i}^{(t-1)}$ 与第 $i$ 个样本的真实标签 $y_i$ 肯定有差距是不是？这个差距可以用 $l(y_i,\hat{y_i}^{(t-1)})$ 这个损失函数来衡量是不是？
为了加深理解，我们来看一个具体的例子，假设我们正在优化第11棵决策树，也就是说前10棵决策树已经确定了。这10棵树对样本 $(x_i,y_i=1)$ 的预测值是 $\hat{y_i}=-1$ ，假设我们现在是做分类，我们的损失函数是：
$L(\hat{y_i})=\sum_{i=1}^n\ln(1+e^{-y_i\hat{y_i}})$
我们可以求出这个损失函数对于 $\hat{y_i}$ 的偏导数，如下所示：
$\frac{\partial{L}}{\partial{\hat{y_i}}}=\frac{1}{1+e^{-y_i\hat{y_i}}}e^{-y_i\hat{y_i}}(-y_i)=\frac{-y_ie^{-y_i\hat{y_i}}}{1+e^{-y_i\hat{y_i}}}$
好，现在我们来审视下这个式子，哪些是常量，哪些是变量。式子最后有一个 $constant$ 项，聪明如你，肯定猜到了，它就是前 $t-1$ 棵树的正则化项、 $l(y_i, \hat{y_i}^{(t-1)})$ 以及 $o(f_t^2(x_i))$ 之和。剩下的三个变量项分别是第t棵决策树的一次式，二次式，和整棵树的正则化项。再次提醒，这里所谓的树的一次式，二次式，其实都是某个叶子节点的值的一次式，二次式。

我们的目标是让这个目标函数最小化，常数项显然没有什么用，我们把它们去掉，就变成了下面这样：
$\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)$
好，现在我们可以回答之前的一个问题了，为什么一次式和二次式显得那么漂亮。因为这些一次式和二次式的系数是 $g_i和h_i$ ，而 $g_i和h_i$ 可以并行地求出来。而且， $g_i和h_i$ 是不依赖于损失函数的形式的，只要这个损失函数二次可微就可以了。这有什么好处呢？好处就是xgboost可以支持自定义损失函数，只需满足二次可微即可。强大了我的哥是不是？

4.3 xgboost推导之正则化项

上面的式子已然很漂亮，但是，后面的 $\Omega(f_t)$ 仍然是云遮雾罩，不清不楚。现在我们就来定义如何衡量一棵树的正则化项。这个事儿并没有一个客观的标准，可以见仁见智。为此，我们先对决策树作另一番定义，如下所示：
$f_t(x)=w_{q(x)},w\in{R^T},q:R^d\rightarrow\{1,2,...,T\}$
需要解释下这个定义，首先，一棵树有T个叶子节点，这T个叶子节点的值组成了一个T维向量w， $q(x)$ 是一个映射，用来将样本映射成1到T的某个值，也就是把它分到某个叶子节点， $q(x)$ 其实就代表了决策树的结构。 $w_{q(x)}$ 自然就是这棵树对样本x的预测值了。
有了这个定义，xgboost就使用了如下的正则化项：
$\Omega(f)=\gamma{T}+\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2$
注意：这里出现了 $\gamma$ 和 $\lambda$ ，这是xgboost自己定义的，在使用xgboost时，你可以设定它们的值，显然， $\gamma$ 越大，表示越希望获得结构简单的树，因为此时对较多叶子节点的树的惩罚越大。 $\lambda$ 越大也是越希望获得模型参数小、结构简单的树。

4.4 xgboost推导之 $f_t(x)$ 拟合

至此，我们关于第 $t$ 棵树的损失函数优化目标已然很清晰，下面我们对它做如下变形：
$\begin{align} L^{(t)}(f_t)&\approx\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)\\ &\approx\sum_{i=1}^n[g_iw_{q(x_i)}+\frac{1}{2}h_iw^2_{q(x_i)}]+\gamma{T}+\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2\\ &\approx\sum_{j=1}^T[(\sum_{i\in{I_j}}g_i)w_j+\frac{1}{2}(\sum_{i\in{I_j}}h_i+\lambda)w^2_j]+\gamma{T}\\ \end{align}$
$I_j$ 代表一个集合，集合中每个值代表一个训练样本的序号，整个集合就是被第t棵树分到了第j个叶子节点上的训练样本集合。理解了这一点，再看这步转换，其实就是内外求和顺序的改变。

进一步，我们可以做如下简化：
$L^{(t)}(w)=\sum_{j=1}^T[G_jw_j+\frac{1}{2}(H_j+\lambda)w^2_j]+\gamma{T}$
其中 $G_j=\sum_{i\in{I_j}}g_i,H_j=\sum_{i\in{I_j}}h_i$
第t棵树的某一个确定的结构（可用q(x)表示），所有的 $G_j和H_j$ 都可以通过解决凸优化问题唯一确定的。而且上式中各个叶子节点的值 $w_j$ 之间是互相独立的。上式其实就是一个简单的二次式，我们很容易求出各个叶子节点的最佳值以及此时目标函数的值。如下所示：
$\frac{\partial{L}}{\partial{w_j}}=G_j+(H_j+\lambda)w^*_j=0\\ \Downarrow\\ w_j^*=-\frac{G_j}{H_j+\lambda}\\ \Downarrow\\ w_j^*=-\frac{G_j}{H_j+\lambda}\\ \Downarrow\\ L^*=-\frac{1}{2}\sum_{j=1}^T\frac{G^2_j}{H_j+\lambda}+\gamma{T}$
$L^*$ 表示了这棵树的结构有多好，值越小，代表这样结构越好！也就是说，它是衡量第t棵树的结构好坏的标准。但要注意，这个值仅仅是用来衡量结构的好坏的，与叶子节点的值可是无关的。通过上面的表达式，可以知道， $L^*$ 只和 $G_j和H_j$ 和T有关，而他们又只和树的结构 $q(x)$ 有关，与叶子节点的值可是半毛钱关系也没有。
这里，我们对 $w^*_j$ 给出一个直觉的解释，以便能获得感性的认识。我们假设分到j这个叶子节点上的样本只有一个。那么， $w^*_j$ 就变成如下这个样子：
$w_j^*=(\frac{1}{h_j+\lambda})\cdot(-g_i)$
这个式子告诉我们， $w^*_j$ 的最佳值就是 $\hat{y_i}$ 的负梯度乘以一个权重系数，该系数类似于随机梯度下降中的学习率。观察这个权重系数，我们发现， $h_j$ 越大，这个系数越小，也就是学习率越小。 $h_j$ 越大代表什么意思呢？代表在该点附近梯度变化非常剧烈，可能只要一点点的改变，梯度就从10000变到了1，所以，此时，我们在使用反向梯度更新时步子就要小而又小，也就是权重系数要更小。

4.5 xgboost推导之 $f_t$ 拟合

好了，通过4.4节我们知道当树的结构确定时，树的每个叶子结点的输出值也是确定，即当 $f_t$ 确定了， $w_j$ 也唯一确定（当然如果训练样本发生变化就另当别论了），另外我们可以通过上面的损失函数评判一颗树的好坏。那么现在的问题是，我们该如何确定每棵树的结构 $f_t$ 呢？

我们知道，树的结构近乎无限多，一个一个去测算它们的好坏程度，然后再取最好的显然是不现实的。所以，我们仍然需要采取一点策略，这就是逐步学习出最佳的树结构。这与我们将K棵树的模型分解成一棵一棵树来学习是一个道理，只不过从一棵一棵树变成了一层一层节点而已。

我们以网上比较有名的判断一个人是否喜欢计算机游戏为例子。最简单的树结构就是一个节点的树。我们可以算出这棵单节点的树的好坏程度 $L^*$ 。假设我们现在想按照年龄将这棵单节点树进行分叉，我们需要知道：

1、按照年龄分是否有效，也就是是否减少了obj的值

2、如果可分，那么以哪个年龄值来分。

为了回答上面两个问题，我们可以将这一家五口人按照年龄做个排序。如下图所示：

image
按照这个图从左至右扫描，我们就可以找出所有的切分点。对每一个确定的切分点，我们衡量切分好坏的标准如下：

Gain=\frac{1}{2}[\frac{G^2_L}{H_L+\lambda}+\frac{G^2_R}{H_R+\lambda}+\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]-\gamma

这个 $Gain$ 实际上就是单节点的 $L^*$ 减去切分后的两个节点的树 $L^*$ ， $Gain$ 如果是正的，并且值越大，表示切分后 $L^*$ 越小于单节点的 $L^*$ ，就越值得切分。同时，我们还可以观察到， $Gain$ 的左半部分如果小于右侧的 $\gamma$ ，则 $Gain$ 就是负的，表明切分后L反而变大了。 $\gamma$ 在这里实际上是一个临界值，它的值越大，表示我们对切分后L下降幅度要求越严。这个值也是可以在xgboost中设定的。这里我们有必要跟GBDT算法做个比较，我们都知道GBDT算法选用的弱学习器是CART回归树，而CART回归树选择特征和特征切分点的标准是均方误差MSE,这也是xgboost与gbdt算法最重要的差别。

扫描结束后，我们就可以确定是否切分，如果切分，对切分出来的两个节点，递归地调用这个切分过程，我们就能获得一个相对较好的树结构。

注意：xgboost的切分操作和普通的决策树切分过程是不一样的。普通的决策树在切分的时候并不考虑树的复杂度，而依赖后续的剪枝操作来控。xgboost在切分的时候就已经考虑了树的复杂度, 就是那个 $\gamma$ 参数。所以，它不需要进行单独的剪枝操作。

4.6 xgboost 总结

优点：
1. xgboost可以自由选择弱学习器
2. xgboost 支持自定义损失函数，只需满足二阶可微即可
3. xgboost可以实现并行训练，提高训练效率
4. xgboost选用决策树作为弱学习器时，不需要额外的剪枝
缺点：
1. xgboost训练过程中要计算损失函数的一阶偏导数和二阶偏导，当样本量较大时，计算量会变得比较大。

5. 参考文章

1. xgboost的原理没你想像的那么难
 2.XGboost/Adaboost/GBDT学习笔记

机器学习算法原理篇之集成学习

1. 集成算法原理

1.1 集成学习概述

1.2 个体学习器选择

1.3 集成学习之boosting

1.4 集成学习之bagging

1.5 集成学习之stacking

1.6 集成学习之结合策略

2. Adaboost 算法

2.1 Adaboost算法的基本思路

2.1.1 假设及变量说明

2.1.2 Adaboost分类问题

推导到这里，我们不得不稍作停歇，回到本节开头提到的boosting算法要解决的4个问题，发现由式（12）和式（13）基本上已经解决了误差率和弱学习器权重的问题，接下来要解决的就是如何更新样本权重！

2.2 Adaboost算法的正则化

2.3 Adaboost小结

3. GBDT 算法

3.1 GBDT算法的基本思路

3.1.1 GBDT的负梯度拟合

3.1.2 GBDT回归算法

3.1.3 GBDT分类算法

3.1.4 GBDT正则化

3.1.5 GBDT小结

4. xgboost算法

4.1 xgboost的拟合对象与损失函数

4.1.1 xgboost损失函数

4.1.2 xgboost模型参数

4.2 xgboost推导之加法训练

4.3 xgboost推导之正则化项

4.4 xgboost推导之 $f_t(x)$ 拟合

4.5 xgboost推导之 $f_t$ 拟合

4.6 xgboost 总结

5. 参考文章

猜你喜欢

热点阅读

机器学习算法原理篇之集成学习

1. 集成算法原理

1.1 集成学习概述

1.2 个体学习器选择

1.3 集成学习之boosting

1.4 集成学习之bagging

1.5 集成学习之stacking

1.6 集成学习之结合策略

2. Adaboost 算法

2.1 Adaboost算法的基本思路

2.1.1 假设及变量说明

2.1.2 Adaboost分类问题

推导到这里，我们不得不稍作停歇，回到本节开头提到的boosting算法要解决的4个问题，发现由式（12）和式（13）基本上已经解决了误差率和弱学习器权重的问题，接下来要解决的就是如何更新样本权重！

2.2 Adaboost算法的正则化

2.3 Adaboost小结

3. GBDT 算法

3.1 GBDT算法的基本思路

3.1.1 GBDT的负梯度拟合

3.1.2 GBDT回归算法

3.1.3 GBDT分类算法

3.1.4 GBDT正则化

3.1.5 GBDT小结

4. xgboost算法

4.1 xgboost的拟合对象与损失函数

4.1.1 xgboost损失函数

4.1.2 xgboost模型参数

4.2 xgboost推导之加法训练

4.3 xgboost推导之正则化项

4.4 xgboost推导之拟合

4.5 xgboost推导之拟合

4.6 xgboost 总结

5. 参考文章

猜你喜欢

热点阅读

4.4 xgboost推导之 $f_t(x)$ 拟合

4.5 xgboost推导之 $f_t$ 拟合