自适应提升(AdaBoost)笔记

特征选择

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

选法数：

如果N很大，并且M很小的时候，几乎是不可能的。

并且，从N维中选择M维，属于离散化的问题，没有导数，无法用梯度下降方法。

常规方法有：

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

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

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

AdaBoost

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

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

注意：

1. 挑一个或几个特征构成弱分类器

2. 有放回的采样

算法流程：

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

1. 当判断正确的时候，yi和Gm(xi)同号，yiGm(xi)>0，-αmyiGm(xi)<0，e...<1，使概率变小；

2. 当判断错误的时候，yi和Gm(xi)异号，yiGm(xi)<0，-αmyiGm(xi)>0，e...>1，从而使错误样本选的多；

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

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

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

证明：

推导中注意事项：

1. G(xi)是最终的分类器，I(G(xi)!=yi)的意思是，G(xi)=yi时取0，不等时取1。

2. 若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。

3. 若G(xi)!=yi，则I(G(xi)!=yi)=1，而G(xi)是f(xi)的符号位，yi取±1，那么yi和f(xi)符号相反，所以-yif(xi)>0，所以exp(-yif(xi)) > 1。

4. 得到Zm小于1后，Zm不断累乘，结果将不断变小

5. 注意yiGm(Xi)要么是+1，要么是-1，所以最后可以写成(1-em)e-αm+em*eαm

AdaBoost不容易过拟合，因为每个弱分类器不求有功，但求无过。

总数可能有四五千，大家一平均，类似合唱队，一两个生病没什么影响。