基本思想: 改变训练样本的权重, 学习多个分类器, 将分类器进行线性组合, 提高分类的性能.—”三个臭皮匠顶个诸葛亮”.
强可学习: 一个类, 存在一个多项式的学习算法能够学习它, 并且正确率高. 弱可学习: 一个类, 存在一个多项式的学习算法能够学习它, 正确率仅比随机猜测略好. 强可学习和弱可学习是等价的: 一个概念是强可学习的充要条件是该概念是弱可学习的.
先得到弱分类器, 然后用它们组成强分类器. (1) 每一轮都要改变训练数据的权值分布: 提高前一轮被弱分类器错误分类的样本的权值, 使他们在下一轮得到更高的重视. (2) 将弱分类器组合成强分类器: 给误差率小的弱分类器更高的权值, 使他们在分类中有更强的话语权.
使用二类分类的训练数据集 T={(x1,y1),...,(xN,yN)} T = { ( x 1 , y 1 ) , . . . , ( x N , y N ) } . 输入: 训练数据集T和弱分类算法. 输出: 最终分类器G(x). (1) 初始化训练数据的权值分布(每个样本的权值相同): D1=(w11,...,w1N) D 1 = ( w 11 , . . . , w 1 N ) 其中, w1i=1N w 1 i = 1 N (2) 对于 m=1,...,M m = 1 , . . . , M (a) 使用具有权值分布为D_m的数据集进行学习, 得到基本分类器: Gm(x):X→{−1,+1} G m ( x ) : X → { − 1 , + 1 } (b) 计算 Gm(x) G m ( x ) 的分类误差率: em=∑i=1NwmiI(Gm(x)≠yi) e m = ∑ i = 1 N w m i I ( G m ( x ) ≠ y i ) (c) 计算 Gm(x) G m ( x ) 的系数: αm=12ln1−emem α m = 1 2 ln 1 − e m e m , 明显可以看到 em e m ↑, αm α m ↓ (d) 更新训练数据集的权值分布: Dm+1=(wm+1,1,...,wm1,N) D m + 1 = ( w m + 1 , 1 , . . . , w m 1 , N ) wm+1,i=wmiexp(−αmyiGm(xi))∑i=1Nwmiexp(−αmyiGm(xi)) w m + 1 , i = w m i exp ( − α m y i G m ( x i ) ) ∑ i = 1 N w m i exp ( − α m y i G m ( x i ) ) , 该式调整的其实是 wm+1,i w m + 1 , i 之间的相对大小. (3) 构建分类器的线性组合 f(x)=∑i=1NαmGm(x) f ( x ) = ∑ i = 1 N α m G m ( x ) 得到最终分类器 G(x)=sign(f(x)) G ( x ) = s i g n ( f ( x ) )
Adaboost最基本的性质是它可以在学习的过程中不断减少训练误差. Adaboost具有适应性, 能适应弱分类器各自的训练误差率, 这也是它名字的由来(适应的提升).
