概述
AdaBoost是Adaptive Boosting的缩写,即自适应提升法,是最成功的Boosting算法。具体算法如下:
Step1: Initialise the dataset and assign equal weight to each of the data point.
Step2: Provide this as input to the model and identify the wrongly classified data points.
Step3: Increase the weight of the wrongly classified data points.
Step4: if (got required results)
Goto step 5
else
Goto step 2
Step5: End
即初始的时候,赋予每个训练样本相同的权重;然后每次迭代后,增加分类错误样本的权重(数据集还是原来的数据集,只不过各个样本的权重变了),使得下一轮迭代时更加关注这些样本。
AdaBoost一般选用决策树桩(decision stump)作为弱学习器。所谓stump是指由一个决策节点和两个叶子节点组成的二叉树:
算法
AdaBoost的算法描述如下:
下面进行解释。
- “输入”(Given)部分:输入训练数据集包含m个样本,其中$x_i$是属性,取值范围属于集合$X$(实数集的子集),$y_i$是标签,取值是-1或+1.
- “初始化”(Initialize)部分:$D$表示带权重的样本(有时也用$w$表示),$D_i$表示第$i$个权重的样本。刚开始的时候,所有样本权重相同为$D_i = 1/m$.
然后开始循环:
- 使用权值分布为$D_t$的数据集,训练得到一个弱分类器$h_t$
- 计算$h_t$在训练数据上面的误差$\varepsilon_t$
- 根据训练误差$\varepsilon_t$计算出权重调整系数$\alpha_t$
- 更新所有训练样本的权重,用于下一次迭代
- 当训练误差比较低(比如错误率为0)或者弱分类器数目达到预先的设置值(超参控制),就停止循环
- 最终的分类器就是各个各个弱分类器的加权求和,如果是分类问题,就再加上符号函数$sign$(输入数据大于0,输出1;等于0,输出0;小于0,输出-1).
如何计算训练误差$\varepsilon_t$?公式如下:
$$ \varepsilon_t = \frac {\sum_{i=1}^N\omega_iI(y_i \neq h_t(x_i))}{\sum_{i=1}^N\omega_i} $$
其中$I(y_i \neq h_j(x_i))$的含义是如果$y_i \neq h_j(x_i)$ 成立,则返回1,否则返回0。下面看个具体的计算例子:
- 有4个样本的权重分别为:0.5,0.2,0.1,0.2,
- 弱分类器预测的值分别为:1,1,-1,-1
- 实际的真实值为:-1,1,-1,1
- 则$I$的值分别为:1,0,0,1
于是有
$$ \varepsilon_t = \frac{0.5*1+0.2*0+0.1*0+0.2*1}{0.5+0.2+0.1+0.2} = 0.7 $$
有时也称$\varepsilon_t$为“total error”表示的是“所有错误分类的样本权重之和”,其实和上面的公式是一致的,因为权重一般是做过归一化的,所以分母里面的所有权重之和其实为1;而且分子中分类正确的样本的$I$值为0,也就是上面的公式可以简化为:
$$ \varepsilon_t = \frac {\sum_{i=1}^N\omega_iI(y_i \neq h_t(x_i))}{\sum_{i=1}^N\omega_i} \\ = \sum_{i=1}^N\omega_iI(y_i \neq h_t(x_i)) = 错误分类样本的权重之和 = total\ error $$
那权重调整系数$\alpha_t$的作用是什么呢?看个具体的例子。假设现在有3个$\varepsilon$值:0.3、0.5、0.7。则对应的$\alpha$的值如下:
$$ \alpha(\varepsilon=0.3) = \frac{1}{2}*ln\frac{1-0.3}{0.3} = 0.42365 \\ \alpha(\varepsilon=0.5) = \frac{1}{2}*ln\frac{1-0.5}{0.5} = 0 \\ \alpha(\varepsilon=0.7) = \frac{1}{2}*ln\frac{1-0.7}{0.7} = -0.42365 \\ $$
可以看到,当弱分类器的准确率为0.5时,其权重为0;准确率大于0.5(即错误率小于0.5)时,权重大于0;准确率小于0.5(即错误率大于0.5)时,权重小于0。所以,错误率$\varepsilon$越小,$\alpha$越大,即当前模型的表现越好,在最终的生成器中占的权重就越大。所以$\alpha$也称为“amount of say”、“Performance”、“Importance”,都指的是当前分类器在最终分类器中的权重。另外注意计算的时候有时使用自然对数($ln=log_e$),有时使用常用对数($log_{10}$)。
再来看最重要的部分:样本权重更新。在Boosting的迭代中,我们每次要找的是错误率比较低的弱分类器。为了方便我们沿用上面$\alpha(\varepsilon=0.3)$的计算结果,看下分类错误和正确时计算出来的权重值:
- 当在样本$i$上预测正确(即$y_i = h_t(i)$),训练误差为0.3时,计算的新的权重如下:
- 当在样本$i$上预测错误(即$y_i \neq h_t(i)$),训练误差为0.3时,计算的新的权重如下:
可以看到当弱分类器在某个样本上分类正确的时候,该样本的权重会降低;否则就会提升,符合理论预期。最后提一下$Z_t$,这是一个规范化系数(normalization factor ),是为了让新计算出来的权重代表一个真正的分布,一般就是归一化。比如上面的例子所有样本的权重更新后加起来后做一下归一化。上面的公式可以简化一下:
- 对于分类正确的样本:$D_{t+1}(i)=\frac{D_t*e^{-\alpha_t}}{Z_t}$
- 对于分类错误的样本:$D_{t+1}(i)=\frac{D_t*e^{\alpha_t}}{Z_t}$
最后一个问题,增加了预测错误的样本的权重之后,如何在下一轮迭代中更关注他们呢?实质是通过权重影响每一轮迭代数据集的选择来实现:比如我们有一个包含N个样本的数据集,每个样本都有一个权重(第一轮时权重相同,均为1/N),然后每一轮选择本轮使用的$m(m \le N)$个样本时,是根据权重随机采样的。也就是有些样本可能会被选择多次,有的可能一次也不会被选中。特别是当样本的权重被更新后,权重大的样本就更容易被选中,甚至选中多次了。这样这些样本自然会对后面的弱分类器产生比较多的影响。比如Pandas的sample
方法就可以实现在一个数据集上面按照权重采样。
另外,还有一种“Bucket”的方式,思路如下:原来有N个样本,每次选N个样本进行弱学习器的训练。第一轮大家权重一样,第二轮的时候,根据权重先将原数据集划分“Bucket”,权重高的样本会占据多个bucket。而每个bucket被选中的几率是一样的,所以权重高的样本就可能被多选几次。也就是第二轮的时候虽然还是N个样本,但某些权重低的可能没有被选,某些权重高的样本可能被选了多次。比如下面的例子(N=5,ref:AdaBoost Algorithm – A Complete Guide for Beginners):
第一轮,所有样本权重一样,可以理解为每个样本就是一个bucket:
第一轮结束的时候,各个样本的权重已经发生了变化(假设第4条数据分错了,它的权重提升了):
如上图,按照权重重新划分了数据集的bucket,分错的第2个样本占了比较多的bucket。所以在为第二轮迭代选择样本的时候,第4条被选中的概率就会比较大。比如算法随机的5个bucket是:0.38,0.26,0.98,0.40,0.55。那选出的样本就是下图:
可以看到,样本4在第二轮出现了3次,这样后面的分类器必然会对该样本倾斜。
上面的第一种情况其实是后面bucket这种方式的一种特殊情况。所以,需要注意的是,每轮迭代改变了样本的权重后,对下一轮的影响是体现在挑选数据集的时候。当数据集选好后,这些数据集又会被赋予相同的权重,开始新一轮的迭代。后续不断按此方式迭代,直到错误率降到某个阈值或者达到预设的迭代次数。
例子
下面看两个例子,第一个偏理论,第二个偏实现,都有助于理解整个算法的流程和内在逻辑。
A Mathematical Explanation of AdaBoost in 5 Minutes
该例引用自:A Mathematical Explanation of AdaBoost in 5 Minutes。
如下图:有一个包含6个样本的数据集,共3个属性:x1,x2,x3,输出为Y。其中T代表True,F代表False。
Step2:使用上面的数据生成弱学习器stump:分别计算各个属性的基尼不纯度(gini impurity)。
$$ Gini\ Impurity = 1- Pr_{true}^2-Pr_{false}^2 $$
$$ Total \ Impurity(x_2) = 0.375*(\frac{1+3}{6})+0*(\frac{2+0}{6}) = 0.25 $$
同理可以计算出$x_1$和$x_3$的不纯度为:
$$ Total\ Impurity(x_1)=(1-(\frac{2}{2+2})^2-(\frac{2}{2+2})^2)*(\frac{2+2}{6}) \\ + (1-(\frac{1}{1+0})^2-(\frac{0}{1+0})^2)*(\frac{1+0}{6}) \\ = 0.33 \\ \\ Total\ Impurity(x_3)=(1-(\frac{0}{0+1})^2-(\frac{1}{0+1})^2)*(\frac{0+1}{6}) \\ + (1-(\frac{3}{3+2})^2-(\frac{2}{3+2})^2)*(\frac{3+2}{6}) \\ = 0.4 $$
可以看到$x_2$的基尼不纯度最低,所以使用它生成第一个stump。
Step3:计算“amount of say”。使用x2属性生成的stump会将第1个样本分错,其它都正确。这样的话total error就是1/6。所以:
$$ Amount\ of\ say = \frac{1}{2}*log{\frac{1-\frac{1}{6}}{\frac{1}{6}}} = 0.35 $$
Step4:计算下一个弱分类器(stump)的样本权重。
- 分类错误的样本新权重 $w_{incorrect} = \frac{1}{6}* e^{0.35} = 0.24$
- 分类正确的样本新权重 $w_{correct} = \frac{1}{6}* e^{-0.35} = 0.12$
然后归一化得到下一个stump(即下一轮迭代)的样本及权重,如下图:
这样第一轮就结束了。第二轮迭代开始之前,要先根据样本权重选取训练数据,比如选择的样本可能如下(可以看到第一轮分类错误的样本这次被选了3次):
然后,将选中的样本权重初始化为相等的值,继续重复前面的过程:
直到训练误差足够小,或者弱分类器个数达到限制,则迭代终止。对所有弱分类器加权求和得到最终的强分类器。
Implementing the AdaBoost Algorithm From Scratch
上面的例子比较偏理论性,这个例子则是具体到代码实现层面的,限于篇幅和格式,就不在文章里面贴了。具体可以参见我的Github: implement-adaboost-from-scratch.ipynb。里面会根据上面的算法实现一个AdaBoost,并且最终和scikit-learn的AdaBoostClassifier
做对比。
该例参考自:Implementing the AdaBoost Algorithm From Scratch
总结
AdaBoost算法的思想还是比较简单的,算法也容易理解,主要需要理解下面几个关键点:
- 如何计算训练误差$\varepsilon_t$
- 理解权重调整系数$\alpha_t$的作用
- 样本权重是如何更新的,又是如何影响到下一轮迭代的
掌握了这些,在做模型的调优以及一些超参设置上也就可以游刃有余了。
评论已关闭