9.1什么是提升方法与ensemble？
- 提升方法其实就是用多个不同的决策方法组合而成，根据不同方法的决策情况来进行最后的决策。
9.1.1强可学习与弱可学习
如果可以用一个多项式复杂度的学习算法学习一个概念，并且正确率很高，那么这个概念就是强可学习的，如果学习的效果仅仅比随机猜测稍微好一点，那就是弱可学习的。
- 而弱可学习的算法一般比较容易学习，相比于强可学习算法更容易获得并且训练所需要的cost往往也更少，因此我们就产生了一个想法，是不是可以通过多个比较弱的学习算法一起预测结果，然后根据这些算法的预测结果再决定最后的分类结果
- 往往是少数服从多数，即“极大似然法”
- 但是不同的分类器之间可以有不同的权值
- 这类通过组合多个算法共同预测的机器学习算法就是ensemble method
9.1.2 Ensemble Method的有效性
- Ensemble Method就是通过组合多个机器学习算法来综合预测结果的算法，简而言之就是缝合怪，这种方法也叫做Combining Models ，即将很多个不同的model组合，共同来预测学习的结果，如果M个model的权重是相等的，那么学习的结果就可以表示为：
%0A#card=math&code=y%7BCOM%7D%3D%5Cfrac%201%20M%20%5Csum%7Bi%3D1%7D%5EMy_i%28x%29%0A&height=53&width=153)
- 那么为什么这种算法就是有效的算法呢？我们可以假设真实的模型是
#card=math&code=h%28x%29)，那么M个不同的模型组合而成的新模型的误差期望是：
)%5E2)%3DE((%5Cfrac%201%20M%20%5Csum%7Bi%3D1%7D%5EMy_i(x)-h(x))%5E2)%5C%5C%3D%5Cfrac%201%7BM%5E2%7D%5Csum%7Bi%3D1%7D%5EME((yi-h(x)%5E2)%3D%5Cfrac%201M%20E%7BAV%7D%0A#card=math&code=E%7BCOM%7D%3DE%28%28y%7BCOM%7D-h%28x%29%29%5E2%29%3DE%28%28%5Cfrac%201%20M%20%5Csum%7Bi%3D1%7D%5EMy_i%28x%29-h%28x%29%29%5E2%29%5C%5C%3D%5Cfrac%201%7BM%5E2%7D%5Csum%7Bi%3D1%7D%5EME%28%28yi-h%28x%29%5E2%29%3D%5Cfrac%201M%20E%7BAV%7D%0A&height=110&width=724)
- 也就是说通过Ensemble方法，学习训练的误差的期望值变成了原来M个不同模型平均值的
倍，通过组合M个不同的model，总体预测的误差减小了
9.1.3如何生成多个模型？
- Bagging算法：Bootstrap Aggregating
- 可以通过不同的数据集划分方式生成多个模型
- 是一种并行的ensemble method
- 两个key ingredients
- Bootstrap sampling：从数据集D中生成若干组不同的大小为N的训练集
- Aggregating：即模型组合的策略，往往在分类模型中采用voting策略，即选择可能性最高的，而在回归问题中使用averaging，取平均数
- Bagging在基学习器不稳定的时候提升效果非常好
- 基学习器的选择：
- 可以选择各类线性模型、神经网络
- 决策树！
- 优点是一种非线性的分类器，并且容易得到
- bias等于0，但是variance非常高
9.1.4随机森林 Random Forest
- 使用决策树作为基学习器的Bagging算法，因为有一系列的决策🌳，所以感觉就像森林，因此得名。
- 随机森林的生成方法：
9.2 AdaBoost算法
- AdaBoost是一种串行的Ensemble方法，通过若干次迭代的训练将训练数据学习成若干个弱分类器
- 前面说到Bagging是并行的方法，并行和串行的区别就在于，Bagging因为是对数据集进行划分从而生成若干个数据集训练不同的模型，也就是说Bagging可以在划分好数据集之后并行地训练
- 但是AdaBoost是一种迭代式的算法，不能并行
9.2.1算法的具体步骤
第1步：将训练集D中的N个训练数据赋予初始的权重，一般来说是所有样本之间都相等，即：
%5Cquad%20w%7B1i%7D%3D%5Cfrac%201N%0A#card=math&code=D_1%3D%28w%7B11%7D%2Cw%7B12%7D%2C%5Cdots%2Cw%7B1N%7D%29%5Cquad%20w_%7B1i%7D%3D%5Cfrac%201N%0A&height=37&width=267)
对数据进行一共M轮的迭代，第m轮的时候训练数据的权重分布是
，并训练得到一个弱分类器
#card=math&code=G_m%28x%29&height=20&width=48)，然后计算这个分类器的训练误差：
%5Cnot%3Dyi)%3D%5Csum%7Bi%3D1%7D%5ENw%7Bmi%7D%5Cmathbb%20I(G_m(x_i)%5Cnot%3Dy_i)%0A#card=math&code=e_m%3D%5Csum%7Bi%3D1%7D%5ENP%28Gm%28x_i%29%5Cnot%3Dy_i%29%3D%5Csum%7Bi%3D1%7D%5ENw_%7Bmi%7D%5Cmathbb%20I%28G_m%28x_i%29%5Cnot%3Dy_i%29%0A&height=53&width=373)
然后计算该分类器的系数：
然后更新整个训练集的权重分布情况
#card=math&code=D%7Bm%2B1%7D%3D%28w%7Bm%2B1%2C1%7D%2Cw%7Bm%2B1%2C2%7D%2C%5Cdots%2Cw%7Bm%2B1%2CN%7D%29&height=21&width=272)，其中：
)%7D%7BZm%7Dw%7Bm%2Ci%7D%5C%5CZm%3D%5Csum%7Bi%3D1%7D%5EN%5Cexp(-%5Calphamy_iG_m(x_i))w%7Bm%2Ci%7D%0A#card=math&code=w%7Bm%2B1%2Ci%7D%3D%5Cfrac%7B%5Cexp%28-%5Calpha_my_iG_m%28x_i%29%29%7D%7BZ_m%7Dw%7Bm%2Ci%7D%5C%5CZm%3D%5Csum%7Bi%3D1%7D%5EN%5Cexp%28-%5Calphamy_iG_m%28x_i%29%29w%7Bm%2Ci%7D%0A&height=100&width=724)
- 其中
叫做规范化因子，很明显这样的规范化因子使得
前面的系数的和变成了1，也就是说权重系数成为了一个概率分布
最后生成一个各个若分类器进行线性组合，形成权重不同的强分类器：
%3D%5Csum%7Bi%3D1%7D%5EM%5Calpha_mG_m(x)%5C%5CG(x)%3D%5Cmathrm%7Bsign%7D(f(x))%3D%5Cmathrm%7Bsign%7D(%5Csum%7Bi%3D1%7D%5EM%5CalphamG_m(x))%0A#card=math&code=f%28x%29%3D%5Csum%7Bi%3D1%7D%5EM%5CalphamG_m%28x%29%5C%5CG%28x%29%3D%5Cmathrm%7Bsign%7D%28f%28x%29%29%3D%5Cmathrm%7Bsign%7D%28%5Csum%7Bi%3D1%7D%5EM%5Calpha_mG_m%28x%29%29%0A&height=110&width=724)
9.2.2算法的误差
%5Cnot%3Dyi)%5Cle%20%5Cfrac%201N%5Csum_i%5Cexp(-y_if(x_i))%3D%5Cprod_mZ_m%0A#card=math&code=%5Cfrac%201N%5Csum%7Bi%3D1%7D%5EN%5Cmathbb%20I%28G_m%28x_i%29%5Cnot%3Dy_i%29%5Cle%20%5Cfrac%201N%5Csum_i%5Cexp%28-y_if%28x_i%29%29%3D%5Cprod_mZ_m%0A&height=53&width=408)
%7D%5C%5C%20%3D%5Cprod%7Bm%3D1%7D%5EM%5Csqrt%7B1-4%5Cgamma_m%5E2%7D%5Cle%5Cexp(-2%5Cprod%7Bm%3D1%7D%5EM%5Cgamma%5E2m)%0A#card=math&code=%5Cprod%7Bm%3D1%7D%5EMZm%3D%5Cprod%7Bm%3D1%7D%5EM2%5Csqrt%7Bem%281-e_m%29%7D%5C%5C%20%3D%5Cprod%7Bm%3D1%7D%5EM%5Csqrt%7B1-4%5Cgammam%5E2%7D%5Cle%5Cexp%28-2%5Cprod%7Bm%3D1%7D%5EM%5Cgamma%5E2_m%29%0A&height=110&width=724)
- 其中
