统计机器学习09：提升Boosting与Ensemble
基本介绍
提升方法其实就是用多个不同的决策方法组合而成，根据不同方法的决策情况来进行最后的决策，也就是说不在一棵树上直接吊死，而是多找几棵树看看那棵树的风水最好再吊上去。
强可学习与弱可学习
如果可以用一个多项式复杂度的学习算法学习一个概念，并且正确率很高，那么这个概念就是强可学习的，如果学习的效果仅仅比随机猜测稍微好一点，那就是弱可学习的。如果预测的正确率还不如随机猜测，那这种算法属实没有存在的必要
弱可学习的算法一般比较容易学习，相比于强可学习算法更容易获得并且训练所需要的cost往往也更少，因此我们就产生了一个想法，是不是可以通过多个比较弱的学习算法一起预测结果，然后根据这些算法的预测结果再决定最后的分类结果。
但是决策的结果往往是少数服从多数，即"极大似然法"，我们暂且不讨论是否会出现多数人的暴政
可以给不同的分类器设定一个不同的权重，分类效果比较好的可以设置比较大的权重，这类通过组合多个算法共同预测的机器学习算法就是ensemble method
ensemble有效性的证明
这种看似缝合怪的机器学习方法也叫做Combining Models，顾名思义也就是将多个不同的model组合到一起共同预测结果，如果M个模型的权重是相同的，那么预测结果可以表示成：
如何生成多个模型：Bagging
我们现在已经知道模型的组合可以提高预测结果的稳定性，那么我们如何来生成多个模型进行组合呢？常见的方法有两种，一种是Bagging，另一种是Boosting
Bagging是通过不同的数据集划分方式来训练出多个模型，是一种可以并行的模型训练方式，它的两个关键步骤可以概括为：
Bootstrap sampling：从数据集D中生成若干组不同的大小为N的训练集，并训练出一系列基学习器(Base Learner)
Aggregating：即模型组合的策略，往往在分类模型中采用voting策略，即选择可能性最高的，而在回归问题中使用averaging，取平均数
Bagging方法在基学习器是弱可学习的时候提升效果非常好，这一点也可以理解，因为Bagging方法的本质是生成了一系列乌合之众，然后用voting策略来预测结果，但是乌合之众的规模变大的时候准确度也会有所提高。
这里的基学习器可以选择各类线性模型或者神经网络，也可以使用决策树，因为决策树是一种比较容易获得的非线性分类器，并且bias非常小而variance非常高，我们用ensemble的方式刚好可以降低决策树的variance，得到bias和variance都比较小的模型，而这种使用决策树作为基学习器的Bagging模型叫做随机森林(Random Forest)，这个名字也比较形象，很多"树"聚集成了森林。
Boosting方法与AdaBoost
与Bagging方法不同Boosting方法是一种迭代式的训练算法，其中比较著名的就是AdaBoost，这是一种串行的Ensemble方法，通过若干次迭代的训练将训练数据学习成若干个弱分类器，然后通过调整权重来提高模型预测的准确度。
AdaBoost算法步骤
将训练集D中的N个训练数据赋予初始的权重，一般来说是所有样本之间都相等，即
对数据进行一共M轮的迭代，第m轮的时候训练数据的权重分布是
，并训练得到一个弱分类器 ，然后计算这个分类器的训练误差： 然后计算该分类器的系数：
更新整个训练集的权重分布
，其中 叫做规范化因子，很明显这样的规范化因子使得前面的系数的和变成了1，也就是说权重系数成为了一个概率分布 最后生成一个各个若分类器进行线性组合，形成权重不同的强分类器：
AdaBoost误差分析
AdaBoost存在一个误差上界：
