当前位置 博文首页 > dastu的博客：学习笔记——Adaboost
1.Kearns 和 Valiant首先提出了“强可学习” 和 “弱可学习”的概念。指出：在概率近似正确学习的框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确的概率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。后来Schapire证明一个概念强可学习的充分必要条件是这个概念是弱可学习的。
2.这样一来，问题便成为，在学习中，发现“弱可学习算法”，能否将它提升为“强可学习算法”。通常来说，“弱可学习算法”比“强可学习算法”容易发现。
3.对于提升方法来说，有两个问题需要解决：第一，如何在每一轮改变训练数据的权值或概率分布。第二，如何将弱分类器组合成强分类器。对于第一个问题，AdaBoost提高被前一轮弱分类器错误分类样本的权值，并降低前一轮被正确分类的样本的权值。对于第二个问题，对于弱分类器的组合，AdaBoost采用加权多数表决。具体来说，分类误差率小的弱分类器权重大，反之则小。
这里以二分类为例，多分类问题可以在此上面推广。
分类器预测结果为-1或1。
Adaboost是一种损失函数为指数函数，模型为加法模型，学习算法为前向分布算法的分类算法。
设训练样本集的m个样本为： T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) . . . ( x m , y m ) } T= \{ (x_1,y_1),(x_2,y_2)...(x_m,y_m) \} T={(x1?,y1?),(x2?,y2?)...(xm?,ym?)}
共有K个分类器： G 1 , G 2 , G 3 . . . G k G_1,G_2,G_3...G_k G1?,G2?,G3?...Gk?
初始时，m个样本的权重(也就是对第一个分类器而言)为： w 11 = w 12 = . . . w 1 m = 1 m w_{11}=w_{12}=...w_{1m}=\frac{1}{m} w11?=w12?=...w1m?=m1?
对于第i个分类器而言，分类误差率的计算： e i = P ( y i =? G ( x i ) ) = ∑ j = 1 m w i , j ? I ( y i =? G ( x i ) ) e_i=P(y_i \not= G(x_i))=\sum_{j=1}^m w_{i,j}*I(y_i\not=G(x_i)) ei?=P(yi??=G(xi?))=j=1∑m?wi,j??I(yi??=G(xi?))
基于得到的分类误差率，可以进一步计算得到第i个分类器的权重系数： α k = 1 2 ? log ? 1 ? e i e i \alpha_k=\frac{1}{2}*\log\frac{1-e_i}{e_i} αk?=21??logei?1?ei??
由此权重系数公式可以看出，分类误差率越大，权重系数越小。
