详解AdaBoost

  Boosting，顾名思义，这是一个增强算法，而它增强的对象，就是机器学习中我们所熟知的学习器。在Valiant引入的PAC（Probably Approximately Correct，又称可能近似正确）中，学习器可被分为强学习器和弱学习器。其中，在处理二分类问题时，弱学习器被视为只比随机分类更好一点（即准确率略高于0.5）的分类器，而强分类器的准确率在90%以上。但是强学习器的获取要比弱学习器困难得多，而1989年Kearns&Valiant¹提出了一个经典的理论问题：强可学习性和弱可学习性问题是否等价。如果该问题的答案是肯定的，那么就意味着所有的弱学习器都有被提升为强学习器的潜力。幸运的是，这问题答案在后来被Schapire证明是肯定的。由此，就有了弱学习器的增强过程。

  Boosting的基本想法就是给样本赋权，利用权值改变纠正弱学习器的错误。每一轮都会加入新的弱学习器，每轮过后，都会生成一个新的样本分布，那些被分错的样本，其关注度会有所增加。T轮过后，将所有的分类器结合，形成性能提升巨大的强学习器。后来关于Boosting类算法的改进，基本上也都是基于改变调整样本权值和分类器结合方式来的。

 输入：样本分布D；基学习算法L；学习轮数T；  D 1 = D f o r t = , . . . T : h t = L ( D t ) ; ε t = P x ∽ D t ( h t ( x ) ≠   f ( x ) ) ; D t + 1 = A d j u s t _ D i s t r i b u t i o n ( D t , ε t ) .  ⁣ e n d  输出：  H ( x ) = C o m b i n e _ O u t p u t s ( { h 1 ( x ) , . . . , h t ( x ) } ) . \begin{gathered} \fbox{ 输入：样本分布D；基学习算法L；学习轮数T； }\\ D_1=D \\ for\enspace t=,...T:\qquad\\ h_t=L(D_t);\\ \qquad\qquad\qquad \varepsilon _t=P_{x\backsim D_t}(h_t(x)\ne\ f(x));\\ \qquad\qquad\qquad\qquad\qquad D_{t+1}=Adjust\_Distribution(D_t,\varepsilon _t).\\ \!end\qquad\qquad\qquad \\ \fbox{ 输出： }\\ H(x)=Combine\_Outputs(\{h_1(x),...,h_t(x)\}). \end{gathered}  输入：样本分布D；基学习算法L；学习轮数T； ​D1​=Dfort=,...T:ht​=L(Dt​);εt​=Px∽Dt​​(ht​(x)​= f(x));Dt+1​=Adjust_Distribution(Dt​,εt​).end 输出： ​H(x)=Combine_Outputs({h1​(x),...,ht​(x)}).​

  在Boosting过程的基础上，Freund&Schapire²于1997年提出了Adaboost（Adaptive Boosting，又称自适应增强）算法，其经典版在2000年由Friedman³提出。

算法流程

   输入训练数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x N , y N ) } D = \{ ( x_1 , y_1 ) , ( x_2 , y_2 ) , ( x _N , y_N ) \} D={(x1​,y1​),(x2​,y2​),(xN​,yN​)}其中， x i ∈ X , y i ∈ = − 1 , 1 x_i∈X,y_i∈=-1,1 xi​∈X,yi​∈=−1,1迭代总次数为T

1、初始化权重分布， D 1 = ( w 1 , 1 , w 1 , 2 , . . . , w 1 , i ) , w 1 , i = 1 N , i = 1 , 2 , . . . , N D_1=(w_{1,1},w_{1,2},...,w_{1,i}),w_{1,i}=\frac{1}{N},i=1,2,...,N D1​=(w1,1​,w1,2​,...,w1,i​),w1,i​=N1​,i=1,2,...,N
2、迭代t=1,2,…,T

  a.在分布D_t下从D中训练分类器h_t(x)
  b.计算分类器h_t的错误率 ε t = ∑ i = 1 N w t , i I ( h t ( x ) ≠ y i ) \varepsilon _t=\sum\limits_{i=1}^{N} w_{t,i}I\big(h_t(x)\ne y_i\big) εt​=i=1∑N​wt,i​I(ht​(x)​=yi​)
  c.计算h_t的权重 α t = 1 2 l n ( 1 − ε t ε t ) \alpha_t=\frac{1}{2}ln(\frac{1-\varepsilon_t}{\varepsilon_t}) αt​=21​ln(εt​1−εt​​)
  d.更新权重分布，其中Z_t为满足分布条件的归一化因子
w t + 1 , i = w t , i Z t e x p ( − α t y i h t ( x i ) ) w_{t+1,i}=\frac{w_{t,i}}{Z_t}exp\big(-\alpha_ty_ih_t(x_i)\big) wt+1,i​=Zt​wt,i​​exp(−αt​yi​ht​(xi​))
Z t = ∑ i = 1 N w t , i e x p ( − α t y i h t ( x i ) ) Z_t= \sum\limits_{i=1}^{N}w_{t,i}exp(-\alpha_ty_ih_t(x_i)) Zt​=i=1∑N​wt,i​exp(−αt​yi​ht​(xi​))
3、整合分类器 H ( x ) = s i g n ( ∑ i = 1 T α t h t ( x ) ) H(x)=sign\big(\sum\limits_{i=1}^{T}\alpha_th_t(x)\big) H(x)=sign(i=1∑T​αt​ht​(x))
  此方法是通过重赋值的策略，在每一轮根据相应的分布对训练样本赋权来完成的，而对于不能利用样本权值学习的算法，可以采用重采样的方法，即每一轮根据相应的分布对训练样本进行采样。
  对于算法性能，经过证明，Adaboost最终的集成分类器的错误率存在着上界，同时，在迭代之中，错误率呈指数趋势减少，说明Adaboost在降低误差，将弱分类器训练整合为强学习器方面有着很好的表现。不过，这又引出一个问题，Adaboost会过拟合吗？答案是会的。Grove&Schuurmans⁴在1998年证明了在足够多轮之后，Adaboost也会过拟合，所以其只是在通常情况下不会过拟合。对于多少轮后会过拟合，Grove&Schuurmans提出了一个学习轮数T的上界。

存在问题

  虽然Adaboost有着很好的泛化性能，但是由于其采用的是对样本重赋权来实现纠错，其对噪声很敏感。在学习噪声数据时，Adaboost仍然会尽力去拟合这些噪声，并且由于不断错误分类，还会使得噪声数据的权重不断加大，降低分类器预测能力。一个比较好的解决办法是直接为样本的权重设定一个上界，具体改进可参考Domingo&Watanabe⁵于2000年提出的MadaBoost算法。

多分类问题

  以上讨论的是针对于二分类问题的Adaboost，以下我们开始讨论Adaboost在多分类问题中的应用。Adaboost在多分类问题上应用所面对的最大问题，便是对弱分类器的约束过强。在二分类问题中，我们对弱分类器的要求是其分类准确率要比0.5略大，但是在多分类中，1/N，N>2，这明显达不到要求。关于这一点，比较常用的解法是将多分类任务分解为多个二分类任务，包括有“一对其余”和“一对一”分解。“一对其余”就是将N类多分类任务分成N个二分类任务，第i个二分类任务仅判断其是否属于i类。代表算法有Schapire&Singer⁶的Adaboost.MH。“一对一”方法则将N个多分类任务分成N*(N-1)/2个二分类任务，第i个二分类任务仅判断其是属于第i类还是第j类。代表算法有Freund&Schapire的Adaboost.M2。

参考资料