集成学习（1）模型误差与集成学习

1 模型误差——偏差与方差

之前我们已经说了不少模型，这些模型的特点是：1、都是有监督模型；2、都是个体模型，基本上都是一个输入、一套参数、一个输出。一般来说，我们的有监督模型不可能做到百分比百的预测准确率，会与真实值存在一定的误差，而我们的目标就是不断的缩小误差，创造出更好的算法，知己知彼百战不殆，鉴于此，我们首先要去了解我们的对手——误差。

试想，如果我们能搞到所有的数据，然后用完美的模型拟合他们，那么就做到零误差了，然而这只能是想想而已，现实中我们的样本数据只能是所有数据的一部分，并且样本数据本身还可能存在一定的噪声，模型本身也不是完美的，因此我们基于这些样本数据做出来的算法的误差就会包含这三个部分：

偏差Bias：是根据样本数据做出来的算法与样本数据本身之间的差异，是期望输出与真实结果的偏离程度。度量了算法的拟合能力，比如我们在射箭，Bias高的意思就是：知道目标在哪，不过弓（算法）不好，对着目标也还是射不准，弓（算法）本身准头不行，那么这种情况就叫做偏差如下图中的下面两幅，所有的点以同样的趋势偏离目标位置；
方差Variance：使用同样大小、不同数据的训练集训练出的模型之间的差异，代表模型是否通过训练数据抓住了数据本质的共性。Variance 高表示模型不稳定，对不同数据表现波动大。同样以射箭为例，就是对着目标射同一个箭（数据点），不同的弓（不同数据训练出的算法模型）射中的位置差异比较大，如下图中的右面两幅，所有的点分散的分布在某一点周围；
Noise：数据本身的误差，也是任何算法无法抹去的误差。

Noise无法避免，所以我们需要尽量降低偏差Bias和方差Variance，就像上图，显然左上角的那个结果才是我们的追求。

以数学语言来描述这些误差，假设存在关系 $Y = f(X) + \epsilon$ ，误差 $\epsilon \sim \mathcal{N}(0,\sigma_\epsilon)$ ，我们用模型 $\hat{f}(X)$ 来拟合 $f(X)$ ，用均方损失来表示预测值与真实值之间的误差：

$Err(x) = E\left[(Y-\hat{f}(x))^2\right]$

把平方展开，可以推导得到误差：

$Err(x) = \left(E[\hat{f}(x)]-f(x)\right)^2 + E\left[\left(\hat{f}(x)-E[\hat{f}(x)]\right)^2\right] +\sigma_e^2$

$= \mathrm{Bias}^2 + \mathrm{Variance} + \mathrm{Noise}$

其中 ${Noise}>0$ 代表着数据本身的固有误差， ${Bias}^2 + Variance>0$ 代表模型本身的不完美，偏差和方差是互相博弈的，他们不可能一直同时减小，最终一方的减小必然导致另一方的增大，所以我们需要寻找 tradeoff，如下图所示，随着模型越来越复杂，bias下降而variance上升，在训练集中 Bias 下降与 Variance 上升的过程中来找到tradeoff ，这时的 Model Complexity 是适中的，此时整体error最小，是拟合能力和泛化能力都比较好的模型：

所以寻找偏差与方差的tradeoff的过程，实质上也就是在平衡欠拟合与过拟合的过程，偏差大说明可能欠拟合，方差大说明可能过拟合，我们之前所说过的算法模型中也有相关的操作，比如对拟合能力非常强的决策树进行剪枝、对SVM严格要求的硬间隔最大化放松限制、对线性回归和逻辑回归等进行正则化处理等，都是寻找 tradeoff 的思路。

2 集成学习

2.1 概述

对于我们之前介绍过的个体模型来说，在大多数情况下，这些个体模型本身的性能还是不够好，有的模型具有较高的偏差（如线性回归、逻辑回归等依赖数据假设），有的模型方差太大，鲁棒性不强（如决策树、KNN等）。因此我们产生了一种想法：如果把这些个体模型综合起来，会不会产生三个臭皮匠的效果？对这方面的研究就是集成学习，集成方法的思想就是通过将这些个体学习器的偏差、方差结合起来，从而创建一个集成模型，获得更好的预测效果。

我们先简单的分析下为什么集成学习可以是模型的预测变得更准确，以二分类问题为例，真实函数为 $f(x)$ ，基模型为 $h_i(x)$ ，假设基模型的错误率为 $\epsilon$ ，即：

$P(h_i(x)\neq f(x))=\epsilon$

假设集成模型的结合策略为投票法，则 $T$ 个基模型中半数以上正确即能得到正确结果：

$H(x)=sign(\sum_{i=1}^Th_i(x))$

假设基模型相互独立，集成模型的错误率为：

$P(H(x)\neq f(x))=\sum_{k=1}^{T/2}(1-\epsilon)^k\epsilon^{T-k}$

根据霍夫丁不等式（ Hoeffding's inequality）知：

$P(H(x)\neq f(x))=\sum_{k=1}^{T/2}(1-\epsilon)^k\epsilon^{T-k}\leq exp(-0.5T(1-2\epsilon)^2)$

可见，随着集成模型中基模型数目 $T$ 的增加，集成模型的错误率将指数级下降，因此集成模型能够有效提高模型的准确率。

既然集成模型这么棒，我们就要考虑怎么进行集成了，要进行个体模型的集成，必然要考虑：
1.个体模型的特性：对于要集成的个体模型，一般称为弱学习器，这里的弱应该也不是真的弱，是个相对的概念，强学习器当然也可以集成，我觉得应该是一开始研究的就是集成弱学习器，所以就延续下来了这个概念，不过被集成的弱学习器也不能太弱，正确率要大于50%，不然就不是“三个臭皮匠顶个诸葛亮”，而是“乌合之众”、“成事不足败事有余”了；
2.个体模型之间的关系：个体模型间关系不大，认为相互独立，可并行运行，个体模型间不独立，只能串行运行；
3.对他们集成的方法：只包含同种类型的个体学习器，称为同质集成 ，包含不同类型的个体学习器，为异质集成 。

综合考虑这三个因素，我们一般将集成学习分为三类：
1.bagging（Bootstrap Aggregating）：针对独立的同质弱学习器，相互独立地并行学习这些弱学习器，并按照某种确定性的平均过程将它们组合起来。（注意这里所说的独立并不是绝对的独立，只是没有强依赖关系，下同）
2.boosting：针对不独立的同质弱学习器。它以一种高度自适应的方法顺序地学习这些弱学习器（每个基础模型都依赖于前面的模型），并按照某种确定性的策略将它们组合起来。
3.stacking：针对独立的异质弱学习器，并行地学习它们，并通过训练一个元模型将它们组合起来，根据不同弱模型的预测结果输出一个最终的预测结果。

2.2 bagging

上一小节我们说，bagging集成的独立的同质弱学习器，同质弱学习器好找，这个“独立”怎么保证呢？bagging采用的方法是对训练样本进行随机抽样（有放回抽样），用不同的训练样本集来训练不同的模型来使模型间尽量独立，实际上，如果两次抽样结果是有交集的，那么其还是不能算完全独立的，只能说是尽量保证独立性吧。bagging通过训练抽样得到的自训练集来训练得到多个基模型，对所有基模型预测的结果进行综合（比如投票，少数服从多数）产生最终的预测结果：

bagging这种集成模型有什么好处呢？可以说，bagging是最贴合“三个臭皮匠顶个诸葛亮”这一说法的，bagging靠大家集思广益来降低预测误差，并且是通过降低方差来实现，不会降低模型的偏差，所以一般采用低偏差高方差的算法作为基模型，比如没有剪枝的决策树。为什么说bagging降低方差variance而不降低偏差bias呢？因为基模型都是同质的，并且子训练集来自同样的样本数据，可以认为基模型有近似相等的bias和variance，假设基模型都是相互独立的（当然一般并不是完全独立），因此可以计算集成模型的预测值期望与方差：

$E(X)=E(\frac{\sum_{i=1}^n X_i}{n})=\frac{\sum_{i=1}^n E(X_i)}{n}=E(X_i)$

$Var(X)=Var(\frac{\sum_{i=1}^n X_i}{n})=\frac{\sum_{i=1}^n Var(X_i)}{n^2}=\frac{Var(X_i)}{n}$

显然，预测值的期望并没有什么变化，而方差减小了很多，当然，这是基模型相互独立的结果，如果不是相互独立的话方差的降幅会小一些，极限是所有的基模型都是一样的，那么集成模型就完全没有优化。

2.3 boosting

如果说bagging是“三个臭皮匠顶个诸葛亮”的体现，那boosting就应该是“如果说我看得比别人更远些，那是因为我站在巨人的肩膀上”。
boosting的训练过程为阶梯状，基模型按顺序串行进行训练（工程实现可以做到并行），基模型的训练集按照某种策略每次都进行一定的转化（比如更新每次的权重），对所有基模型预测的结果进行线性综合产生最终的预测结果：

boosting的思想是：先从初始训练集训练出一个基学习器，再根据其表现对训练样本分布进行调整，使得此基学习器预测错误的训练样本在接下来的训练中受到更多关注，所以boosting实际上一直通过改变样本的分布来优化loss function，在降低loss，同时因为boosting中的基学习器都是高度相关的，所以其集成后也没法降低整体的方差，那么很显然，boosting实际上是减少bias，而不会减少方差variance，因此一般采用高偏差低方差的算法作为基模型。

2.4 stacking

stacking没用过，不太了解，听说在比赛里特别厉害，以后有空研究研究。。。。。。看到资料上说：

Stacking算法分为2层，第一层是用不同的算法形成T个弱分类器，同时产生一个与原数据集大小相同的新数据集，利用这个新数据集和一个新算法构成第二层的分类器。Stacking 就像是 Bagging的升级版，Bagging中的融合各个基础分类器是相同权重，而Stacking中则不同,Stacking中第二层学习的过程就是为了寻找合适的权重或者合适的组合方式。

3 总结

所谓集成学习，就是面对比较难一些的问题时，把多个水平一般的选手，通过合体术合体成一个更强的合体人来对付，就像孙悟空和贝吉塔合体变成贝吉特一样，同样我们的结合策略不同，形成的集成模型也不同，就像悟空和贝吉塔使用耳环合体变成贝吉特，舞步合体变成悟吉塔。

耳环合体变成贝吉特

各种集成学习的优缺点就不说了，上面都已经比较清楚了，在集成学习中，有一些比较经典的常用算法，如下图所示，像bagging中的随机森林（Random Forest, RF），boosting中的自适应提升算法（Adaptive Boosting，Adaboost）、梯度提升树(Gradient Boosting Decison Tree, GBDT)、极端梯度提升(eXtreme Gradient Boosting，XGBoost)：

接下来几篇中我们来一起看一看这些常用的算法。

主要参考
《机器学习》——周志华
Understanding the Bias-Variance Tradeoff