Boosting(提升)方法是一种常用的统计学习方法,其中最具有代表性的算法是AdaBoost。AdaBoost起源于PAC可学习性(probably approximately correct learnability)的研究。历史上,Valiant和Kearns首先提出了强可学习(strongly learnable)和弱可学习(weakly learnable)。在PAC框架下,若一个算法的识别准确率很高并能在多项式时间内完成则为强可学习;若一个算法的错误率仅仅比随机猜测略低,则称之为弱可学习。后来Schapire证明强可学习和弱可学习是等价的:在PAC学习的框架下,一个概念是强可学习的充分必要条件是这个概念是弱可学习的。如此,问题就变成了:如果已经发现了一个弱学习算法,是否能够将其提升(boosting)为一个强学习算法。
关于提升方法的研究很多,例如:boostrapping,将多个弱分类器分配不同的权值来组成强分类器;bagging,根据多个弱分类器的投票结果来确定最后的分类结果。这些提升方法中,最有效最具有代表性的则是AdaBoost。
AdaBoost算法过程
AdaBoost通过每一轮的分类结果来改变每个样本的权值,使得分类错误的样本权值变大,分类正确的样本权值变小,这样使得没有正确分类的数据获得更高的关注。对于多个弱分类器,AdaBoost通过加权多数表决来组合,误差率小的分类器权值大,反之,则权值小。具体算法如下:
- 初始化训练数据的权值分布
\(D_1=(w_{11},w_{12},..,w_{1N}), {w_{iN}={1\over N}}, i=1,2,..,N\) - 对m=1, 2, .., M
- 使用具有权值 \(D_m\) 的训练数据集学习,得到基本分类器 \(G_m(x)\)
- 计算 \(G_m(x)\) 在数据集上的分类误差率, \(e_m=P(G_m(x_i)\neq y_i)=\sum_i^N{w_{mi}I(G_m(x_i)\neq y_i)}\)
- 计算 \(G_m(x)\) 的系数 \(\alpha_m={1\over 2}ln{{1-e_m}\over e_m}\)
- 更新数据集的权值分布 \(D_{m+1}=(w_{m+1,1},w_{m+1,2},..,w_{m_1,N})\) ,其中 \(w_{m+1,i}={w_{mi}\over Z_m}e^{-\alpha_my_iG_m(x_i)}\) , \(Z_m=\sum_i^N{w_{mi}e^{-\alpha_my_iG_m(x_i)}}\)
- 构建基本分类器的线性组合 \(f(x)=\sum_m^M \alpha_mG_m(x)\)
- 得到最终的分类器 \(G(x)=sign(f(x))\)