统计学习(第二版）笔记--提升方法

AdaBoost

提升方法的理论基础：概率近似正确时，一个概念是强可学习的充要条件是弱可学习。弱可学习：学习正确率仅比随机猜测略好。强：高正确率。

因此，可以开发一组弱分类器，通过多次学习，把它们提升为强分类器。AdaBoost基本思想：从基本，弱的分类器开始，如果对某数据样本的分类错误较大，则对这个数据样本配以较高权值，降低被正确分类的数据的权值，从而在下一轮分类中得到弱分类器的更多关注；最后对多个弱分类器加权表决，错误率越低则权值越大，分类误差率越大的基本分类器权值越小。

基本性质：在学习过程中不断减小训练误差，减小对训练数据集上的分类误差率。训练误差界不等式。二分类问题AdaBoost的训练误差界，可以推出AdaBoost的训练误差是以指数速度下降的。也不需要知道下界。能适应弱分类器各自的训练误差率。具有适应性。

例子：P159

对二分类数据(x,y)，其中y=-1 or 1, 不改变数据本身，而是训练权重。首先对初始数据，取平均权重w=1/n，这样得到权重的集合D1 = {1/n, ..., 1/n}，得到基本分类器G1, 一开始只有这一个, f1=a1*G1

这里基本分类器主要是对x设置阈值v, x>v, y=+1; x<v, y = -1，然后看对样本分类是否有错。

关键的三个值：样本权重w，分类器组合系数a，错误率e。另有归一化因子Z

计算基本分类器的分类误差率e，然后再由e计算一个系数a，为log(Exp)的形式。这样e减小，a增大，即分类正确的G有较大的权重，在最终分类器中的作用越大，而对样本，误分类的样本权值w=w/Z*exp(-a1*y*G1), 被放大exp(2a)=(1-e)/e倍，误分类样本在下一轮学习中起更大作用。

通过G1计算w2， 得到数据样本的权重集合D2，找出分类器G2，然后再计算G2的e2，系数a2，。。（第二轮训练）, 得到f2=a1*G1+a2*G2

这样一轮轮下去，第三轮f3 = a1*G1+a2*G2+a3*G3, 得到最终分类器G(x) = sgn( 相加a_i*G_i), 此时对数据集误分类点为0

这里主要巧妙地用了exp函数的衰减性质和exp与log的转换，exp连乘等于指数相加。每一轮选取恰当的Gm使得Zm最小，从而使训练误差下降最快。所以可以被解释为加法模型、损失函数为指数函数、学习方法为前向分步算法时的二分类学习方法。另外exp形式和逻切斯蒂回归很像，有前沿研究。

提升树

是统计学习中性能最好的方法之一。基函数为决策树。分类问题：二叉分类树；回归问题：二叉回归树。x>v or x<v：根节点直接连接两个叶节点的简单决策树，即决策树桩stump。