[关闭]
@zhuanxu 2018-04-02T15:24:09.000000Z 字数 2671 阅读 1897

boosting 3大算法总结

机器学习 boost


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

集成学习

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

整个过程有两个难点:

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

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

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

本文重点讲boosting算法。

boosting基本原理

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

GBM

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

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

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

其中每个 通过下面求极小值获取:

针对上面 的求取上,有两种成熟的方法:

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

我们对 极小值的求取上,在 fm上采取一阶泰勒展开,此时求倒数得到:

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

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

当我们学习到了,我们再去看最佳步长应该是多少:

总结下整个过程:

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

先来学习树结构.

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

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


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

我们将其带回入loss函数,可以得到:

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

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

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

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

Adaboost

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

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

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

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

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

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

提升方法

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

Adaboost中loss为指数损失:

此时第m轮迭代,我们要求:

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

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

接着我们对 进行求导,得到:

XGBOOST

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

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

进一步化解得到:

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

此时我们对wjm求导,就能得到最佳的wjm:

代回loss中:

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

整个算法描述如下:

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

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

此时计算增益公式为:

总结

本文介绍了boosting算法中最著名的3个算法

并且介绍了Adaboost是GMB中损失函数为指数损失的特例,后续还会有两篇文章,一篇介绍adaboost 算法的变种,另一篇结合代码来介绍3个算法。

你的鼓励是我继续写下去的动力,期待我们共同进步。
这个时代,每个人都是超级个体!关注我,一起成长!

参考

论文:Tree Boosting With XGBoost: Why Does XGBoost Win “Every” Machine Learning Competition?
Gradient Boosting from scratch
Boosting algorithm: XGBoost
https://ask.hellobi.com/blog/guodongwei1991/10501
https://towardsdatascience.com/boosting-algorithm-adaboost-b6737a9ee60c

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注