@zhuanxu 2018-04-02T23:24:09.000000Z 字数 2671 阅读 4407

boosting 3大算法总结

机器学习 boost

之前的两篇文章 adaboost 原理和 boosting原理写完后，感觉还是没有特别弄明白boost，所有就有了本文。

集成学习

首先我们需要知道什么是集成学习？
集成学习是通过训练弱干个弱学习器，并通过一定的结合策略，从而形成一个强学习器。

整个过程有两个难点：

如何得到若干个个体学习器
如何选择一种结合策略

先来看第一个问题如何获取个体学习器，在选择上有两个：

同质学习器，例如随机森林都使用cart树
异质学习器，例如使用不同的分类器，最终采取投票的方式

其中用的比较多的是同质学习器。同质学习器按照个体学习器之间是否存在依赖关系可以分为两类：

第一个是个体学习器之间存在强依赖关系，一系列个体学习器基本都需要串行生成，代表算法是boosting系列算法；
第二个是个体学习器之间不存在强依赖关系，一系列个体学习器可以并行生成，代表算法是bagging和随机森林（Random Forest）系列算法。

本文重点讲boosting算法。

boosting基本原理

关于boosting算法，我们需要知道其中最有名的3个算法：

Adaboost(Adaptive Boosting)
GBM(Gradient Boosting Machine)
XGBoost

GBM

我们先来看 GBM ，其思路是逐步提升，怎么理解呢？

我们先看来梯度提升算法：首先给定一个损失函数 L(y,F(x))，其输入是训练对：（x1,y1）,（x2,y2）,...,（xn,yn）,目标是找到最优的F(x)，使得损失函数L最小，按照传统梯度下降的方法，我们会将训练数据(xi,yi)带入，然后求L对参数的偏导，再用负梯度进行参数更新：

这么做的一个前提是我们需要保证损失函数Loss对F可微，F对参数 $\theta$ 可微，第二个可微可以说比较困难，于是我们直接在函数空间F中对F进行求解，我们假设f是一系列数值叠加而来：

其中每个 $\theta$ 和 $\phi$ 通过下面求极小值获取：

针对上面 $\theta$ 和 $\phi$ 的求取上，有两种成熟的方法：

Gradient Descent
Newton’s Method

也就分别对应了 GBM 和 XGBoost，先来讲 GBM。

我们对 $\theta$ 和 $\phi$ 极小值的求取上，在 fm上采取一阶泰勒展开，此时求倒数得到：

那根据一阶泰勒，此时求loss的极小值，相当让f沿着负梯度的方向走，则必然随着f的迭代，loss是减小的，现在我们来总结下问题：

我们将已知输入数据从 (xi,yi) 转变到了 (xi,-gm(xi))，我们现在要用函数 $\phi_m$ 去拟合 (xi,-gm(xi))，并且评判标准如下：

当我们学习到了 $\phi_m$ ，我们再去看最佳步长应该是多少：

总结下整个过程：

有了上面这个过程后，我们还有一步需要确认的是怎么求最优的 $\phi_m$ ，现在我们假设 $\phi_m$ 是树模型，此时我们需要学习树的结构以及每个叶子节点的权重。

先来学习树结构.

我们假设树可以分为T个节点，并且每个节点权重为wj，则：

其中 n_jm 是在第j个叶子数据点的个数，针对上面的式子，我们定义 G_jm 为第j个叶子节点中所有数据的梯度和，并且将常数项gm去除，我们得到：

因此如果树的结构固定，我们可以得到所有的叶子权重为：

我们将其带回入loss函数，可以得到：

下面我们来决定一个叶子节点是否应该继续分裂，我们可以计算分裂后的loss变化：

如果gain>0则分裂，否则则为叶子节点。

现在当我们学习到真正的树结构后，我们再去重新学习最优的树权重：

wjm是第j个叶子节点的权重，现在整个算法的流程如下：

Adaboost

我们在Adaboost原理一文中给出了算法流程：

我们可以从下面4个问题来理解Adaboost算法：

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

第一个问题：学习误差率e的计算，第m个弱分类器的误差率为训练集上的加权错误率：

此处分母其实为1，可以省略。
第二个问题：弱分类器权重。

为什么这样计算弱学习器权重系数？从上式可以看出，如果分类误差率ek越大，则对应的弱分类器权重系数αm越小。也就是说，误差率小的弱分类器权重系数越大。
第三个问题：如何进行权重更新

对于分类正确的，权重降低，对于分类错误的，权重增加
第四个问题：集合策略。Adaboost分类采用的是加权平均法，最终的强分类器为

提升方法

以上内容是我们在文章 Adaboost 原理中讲的，我们本文来看看其实怎么符合上文GBM原理的.GBM的算法原理如下：

Adaboost中loss为指数损失：

此时第m轮迭代，我们要求：

接下去是重点了，我们此处如何求最佳的 $\alpha_m , G_m$ ，因为loss函数是指数损失，我么很容易的通过化解、求导直接得到最佳的 $\alpha_m , G_m$ ，下面是具体的推导：

于是我们求最佳的G_m即为：

接着我们对 $\alpha_m$ 进行求导，得到：

XGBOOST

XGBOOST希望直接求解下面的式子从而得到最优的fm

我们可以在fm-1处进行二阶泰勒展开，得到：

进一步化解得到：

我们让G_jm和H_jm分别表示在Region j中的和，于是有：

此时我们对wjm求导，就能得到最佳的wjm：

代回loss中：

此时根据loss，我么就可以学习到树的结构：

整个算法描述如下：

在xgboost中，还加入了正则项来防止过拟合：

其中γ是对叶节点的惩罚，α 和 λ 分别是L1和L2正则，此时最优的wjm为：

此时计算增益公式为：