集成学习系列1：boosting和bagging

1. 概念

集成学习实质是通过多个学习器集成到一起的模型。相应的将多个同种算法组合在一起，比如多个C4.5算法集成到一起叫做基学习器，而不同的算法集合到一起叫做个体学习器。

为什么集成学习是有用的，这和通常社会中投票是类似的，即大多数人说的很可能是对的。比如去看一部电影，100个人中有90个人都推荐你去看，那么这部电影很可能真的不错。我们可以将这里的人理解成每一个机器学习的算法（不一定是不同的）。

再看西瓜书上的一个图：

通过这个图我们可以看出来了，再(a)中，集成提升了性能，达到了100%，而(b)终集成并未起作用，到c中直接起的就是一个反作用了。
可见要获得一个比较好的集成效果，分类器应当好而不同，也就是具有一定的准确性，但也不是要特别的好，并且每个学习器之间具有一定的差异。
我们再来看一张图，这张图比较明显的展示了，为什么正确率不用太高：

2. 强可学习和弱可学习

• 在概率近似正确（probably approximately correct, PAC)学习的框架中，一个概念（类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，称这个概念是强可学习的；
• 一个概念（类），如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，则称这个概念是弱可学习的。

3. Boosting的逻辑线

Boosting的最重要的考虑是：只要找到一个比随机猜测略好的弱学习算法就可以直接将其提升为强学习算法，而不必直接去找很难获得的强学习算法，这就是为什么集成学习中一直出现boosting了。

基于这样考虑，我们的问题就是怎么样实现弱学习转化成强学习？
举个例子：学习算法A在a情况下失效，学习算法B在b情况下失效，那么在a情况下可以用B算法，在b情况下可以用A算法解决。这说明通过某种合适的方式把各种算法组合起来，可以提高准确率。
所以怎么样实现弱学习转化成强学习，实际上是通过弱学习之间的互补来实现的。

到这里我们的问题又转变了，很明显互补是需要一些弱分类器，然后将它们组合起来的。这样问题就变成了：

1. 怎么样获取不同的弱分类器？
2. 怎么样组合弱分类器？

怎么样获取不同的弱分类器？

• 不同的弱学习算法，比如svm、逻辑回归、神经网络等等
• 相同的弱学习算法，不同的超参数
• 相同输入对象的不同特征
• 不同的训练集，比如放回取样（bootstraping）和不放回取样（pasting）

怎样组合弱分类器？

• 多专家组合，一种并行结构，所有的弱分类器都给出各自的预测结果，通过“组合器” 把这些预测结果转换为最终结果。 eg.投票（voting）及其变种、混合专家模型
• 多级组合，一种串行结构，其中下一个分类器只在前一个分类器预测不够准（不够自信）的实例上进行训练或检测。 eg. 级联算法（cascading）、AdaBoost等。

4. bagging

Bagging与Boosting的串行训练方式不同，Bagging方法在训练过程中，各基分类器之间无强依赖，可以进行并行训练。其中很著名的算法之一是基于决策树基分类器的随机森林（Random Forest）。为了让基分类器之间互相独立，将训练集分为若干子集（当训练样本数量较少时，子集之间可能有交叠）。Bagging方法更像是一个集体决策的过程，每个个体都进行单独学习，学习的内容可以相同，也可以不同，也可以部分重叠。但由于个体之间存在差异性，最终做出的判断不会完全一致。在最终做决策时，每个个体单独作出判断，再通过投票的方式做出最后的集体决策。

针对bagging，比如我有三个算法，分别是逻辑回归、决策树和SVM，对同样的一组样本进行学习，然后进行预测，对于一个样本点来说，使用三个算法分别预测，比如得到了1 、1、0，那么将这个结果预测为1，这是一种少数服从多数的算法，也是一种hard的算法，会有一定的问题，比如下面这种图中，按照少数服从多数的算法，模型应该被预测成B，但是我们一眼看过去也知道，这个模型很可能是A，因为模型1和模型4预测为A的概率都达到了90%以上，在此时这种少数服从多数的预测方式就不是很合理了。

现实生活中，在选秀类综艺节目中，音乐界的人进行投票往往占的权重更大，而普通观众占的权重更小，这是一种很常规的想法，所以有了第二种想法，让每个模型有自己的权重，对应的权重实际上就是模型的输出概率，这就要求每个集合的模型都能够输出概率，常见的像逻辑回归、决策树和svm等都可以输出概率。

5. bagging 和 boosting比较

Bagging和Boosting的区别：

1. 样本选择上：
   Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
   Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
2. 样例权重：
   Bagging：使用均匀取样，每个样例的权重相等
   Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
3. 预测函数：
   Bagging：所有预测函数的权重相等。
   Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
4. 并行计算：
   Bagging：各个预测函数可以并行生成
   Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果，但是也增大了计算量。

下面是将决策树与这些算法框架进行结合所得到的新的算法：
1）Bagging + 决策树 = 随机森林
2）AdaBoost + 决策树 = 提升树
3）Gradient Boosting + 决策树 = GBDT

参考

《机器学习》周志华
《统计学习方法》
Bagging和Boosting 概念及区别