从离散型adaboost 到概率型 adaboost

2020 年 6 月 27 日
AI

最近整理gbdt知识点的时候，重新温习了一下这篇神论文，整理了一些要点：

adaboost被提出之初，其版本是Discrete AdaBoost，也就是离散型adaboost，就是我们目前在百度上最常见的那个解释版本：

这里展开说下吧，adaboost和gbdt一样，整个算法可以用简单的公式进行表示：

也就是我们常说的“加性模型”，然后我们写出adaboost的目标函数的形式：

这是前向分布法的目标函数的形式，其中：

前向分步算法就通过不断迭代求得了从 $m=1$ 到 $m=M$ 的所有基分类器及其权重，问题得到了解决。

那么adaboost和指数损失函数是什么关系呢？首先我们需要知道，指数损失函数的地位和二元的logloss损失函数是一样的，他们都是作为0-1损失函数的代理函数来代替原始问题的目标函数的：

我们将其带入adaboost的目标函数的式子可以得到：

令

我们知道：

是前面m-1轮的基学习器的求和与yi的乘积，在本轮即第m轮的计算过程中，前面的m-1个基学习器已经是固定的了（例如tree的深度、tree的叶子节点以及叶子节点值等都已经是固定的），yi表示实际的标签值也是固定的，因此，常量对于优化问题来说是可以忽略的，所以最终原始的目标函数可以转化为：

这里，yi是-1或者1（注意，离散adaboost的标签是和svm一样设为1或者-1的），G(xi)，即第m轮的基学习器的输出，离散adaboost的基学习器是卡阈值直接输出-1或1的。

这个时候，我们需要求解两个变量：

离散adaboost采用的是分布求解的策略，即先固定 $\alpha$ ，求解G，然后求解出G之后再求解 $\alpha$ 。

此时，我们就可以将上式继续转化：

这里的转化就很有灵性了，针对于：

$\alpha$ 固定并且yi和G(xi)输出均为1或者-1的情况下，上述的两个最优化的函数时等价的，因为其最优值都是在y1=G（xi）=1或-1的情况下取到的。那么此时我们的目标函数就是：

这个问题如何求解呢，实际上这个时候的Gm(xi)就是一个基学习器正常训练的过程，具体的过程是，我们在当前的权重和样本上，正常fit一个cart tree，仅此而已，cart tree的拟合过程和上述的目标函数是无关的。

这样，我们就求解出了Gm(xi)了。（这里为了方便省事，Gm(xi)）,Gm(x),G(xi),G(x)都是一个意思。。懒得改了， $\alpha$ 也是一样的处理）

此时我们又回到了当初的起点：

只不过这个时候Gm(x)已经求解出来了，就好像分手之后你前女友嫁人了一样是没法改变的事实了。此时我们的重心就放在了 $\alpha$ 的求解上了，对上式进行展开：

注意，这里

这里是把分段函数合并成一个了，当yi=G(xi)的时候只有第一个式子参与了计算，当yi!=G(xi)的时候只有第二个式子参与了计算，这一点要注意清楚。

这一步的推导，这个挺简单的但是说起来很麻烦，就是构造新式子，懒得写了。。自行体会吧，然后就是求导了，可以得到：

其中em是带权分类误差率：

注意啊，这里样本是带权重的和我们常规的所有样本等权计算是不一样的。并且分母加入了

是希望整体的样本权重为1。

这里我们贴出这篇文章的作者写的ppt上的演示图:

这里作者为了画图方便用了决策树状，因此每一个基cart的分界面都是一条线，实际上如果树的深度较大的化分界面是一条折线的。

这里作者做了一个测试，左边这个图不用注意主要是为了让你知道每条线代表了啥，右边才是需要注意的，stumps使用的是决策树桩，可以看到bagging对决策树状进行集成效果是很渣的，bagging框架只能减少方差而无法降低偏差，因此对于基学习器的拟合能力是有要求的，但是adaboost就很神奇了，不仅能降低偏差还能降低方差！降低偏差好理解，每一轮的基学习器都是拟合上一轮的预测偏差，那么为啥adaboost还能降低方差呢？

主要原因就在于，adaboost每一轮的样本权重都是在变化的，实际上使用的是广义的采样方案。我们知道bagging每一轮是随机选择部分样本进行训练的，实际上这等同于每一轮对部分样本赋权为0，部分样本赋权为1。

而adaboost则是通过对每一样本进行赋权从而达到了bagging的效果。因此，实际上boosting的框架是既能起到减少方差的效果也能起到降低偏差的效果的。。

上图我们还看到，有一个叫做real adaboost的东西。我们前面提到过离散型的adaboost每一轮直接输出分类标签，因此需要我们去卡不同的分类阈值，大佬不甘寂寞，又想到了一种更好的处理方法：