• 1. 自适应提升(AdaBoost)
  • 1.1. 特征选择
  • 1.2. AdaBoost
  • 1.3. 算法流程

1. 自适应提升(AdaBoost)

1.1. 特征选择

特征选择：从N个特征中选择M个使识别率最高。选法数：

如果N很大，并且M很小的时候，几乎是不可能的。并且，从N维中选择M维，离散化的问题，没有导数，无法用梯度下降方法。

递增法：对每个特征都构造一个分类器，找一个识别率最高的，比如选了x1，然后在有x1的情况下，固定x1，再从余下的特征中选最好的特征，以此类推，直到加入某个特征后识别率降低。

递减法：对所有的特征构造分类器，记下识别率，然后依次去掉一个特征，看去掉那个使识别率增加最多，比如x1，以此类推。

类似的还有模拟退火法等，目前已经不用，效果不佳，其次神经网络已经做了这些事了，就是某些神经元上的weight很小，你可以直接将其去掉。

1.2. AdaBoost

不断对训练样本采样，然后不断去找适合这些训练样本的特征。

AdaBoost算法基本原理就是将多个弱分类器（弱分类器一般选用单层决策树）进行合理的结合，使其成为一个强分类器。

注意：

• 挑一个或几个特征构成弱分类器。
• 有放回的采样

1.3. 算法流程

Wm+1,i为什么要乘以后面的？

• 当判断正确的时候，y_i和G_m(xi)同号，y_iG_m(xi)>0，-α_my_iG_m(xi)<0，e...<1，使概率变小
• 当判断错误的时候，y_i和G_m(xi)异号，y_iG_m(xi)<0，-α_my_iG_m(xi)>0，e...>1，从而使错误样本选的多

Zm是把所有的W_mi加到一起，是归一化系数。

sign意思是取符号位，大于0，y取+1，小于0，y取-1。

定理：随着M增加，AdaBoost最终分类器G(X)在训练集上错误率将会越来越小。

推导中注意事项：

• G(xi)是最终的分类器，I(G(xi) != yi)的意思是，G(xi)=yi时取0，不等时取1。
• 若G(xi)=yi，则I(G(xi) != yi)=0，而G(xi)是f(xi)的符号位，yi取±1，那么yi和f(xi)符号一样，所以-yif(xi)<0，所以0<exp(-yif(xi)) <1。
• 若G(xi)!=yi，则I(G(xi)!=yi)=1，而G(xi)是f(xi)的符号位，yi取±1，那么yi和f(xi)符号相反，所以-yif(xi)>0，所以exp(-yif(xi)) > 1。
• 得到Zm小于1后，Zm不断累乘，结果将不断变小
• 注意yiGm(Xi)要么是+1，要么是-1，所以最后可以写成 (1-em)e^-αm+em*e^αm

AdaBoost不容易过拟合，因为每个弱分类器不求有功，但求无过。总数可能有四五千，大家以一平均，类似合唱队，一两个生病没什么影响。