(七)集成学习

个体与集成

现在我们进入书本第八章的内容，即集成学习。今天讲解第八章时，我会讲得比较快。首先，我们谈一谈什么是集成学习。集成学习的英文是ensemble learning，大家注意这个词，ensemble的发音与一般的英文发音不太一样。不要看到这个词就认为其发音不对，因为这个词是英文中的外来语，原本来自法语，法语中这个词是ensemblance，所以英文中保持了这种发音。

那么，集成学习是什么意思呢？从我们上课到现在，讲解的各种算法模型，都是在用一个模型解决问题。而集成学习则告诉你，原来用一个模型解决问题，现在可以改为用多个模型来解决问题。当我们用多个模型来解决问题时，这就是在做集成学习。这里也有不同的情况，比如，如果每一个模型都是相同的，比如都是决策树，我们可以把它叫做决策树集成；都是神经网络，我们可以把它叫做神经网络集成。如果每一个模型都是相同的，我们把它称为同质的集成。如果每一个模型都是不一样的，比如有一个神经网络，一个决策树等，这种情况我们把它称为异质的集成。大家了解即可。那么，这里的每一个模型，我们可以把它叫做一个个体，或者叫做一个成分，很多时候我们称之为一个弱学习器，但这都不是绝对的说法，大家把它称为一个个体，比较客观一些。

那么，为什么集成学习很重要呢？在现实应用中，我们经常会发现，如果要取得好的性能，使用集成学习是最有效的一种途径。比如，我给大家列了一个表，你们可能都听说过KDD Cup是数据挖掘领域最重要的一个竞赛。我这里列了从2007年到2018年，共12年所有比赛的冠军，哪怕同一个比赛分了好几个赛道，冠军甚至第一名、第二名、第三名全都是使用了集成学习的技术。其他还有很多现实中的应用，比如Netflix的比赛、Kaggle里面的很多竞赛等等，最后获胜的往往都会用到集成学习的技术。哪怕在今天深度神经网络这么流行的情况下，很多时候我们还是会选择用深度神经网络进行特征学习，然后把深度神经网络的倒数第二层切出来，把这个输出给一个集成学习器，比如随机森林或者XGBoost，这种做法是很常用的。这时候往往比直接用这个深度神经网络的效果还更好。大家知道，我们用一个深度神经网络，输入数据得到输出。训练好之后，我们把这一层拿出来，把这一层的输出给另外一个模型，比如随机森林或者XGBoost。这样做之后，比直接用神经网络的效果还更好。

其实这更体现出我们使用深度神经网络进行表示学习，将学习到的表示交给基层处理，因此这项技术非常重要。以后很多同学可能会从事现实工程或应用工作，如果基本不考虑创新，那么集成学习技术几乎是必不可少的。集成学习听起来就是构建多个模型，并将其结合起来解决问题，简单来说，就像中国俗语说的“三个臭皮匠，顶一个诸葛亮”。但这件事并不容易，是不是我们只需构建几个模型，然后简单合并就可以了呢？其实并非如此。

好而不同

假设我们要预测三位结果，第一位是绿色，第二位是黄色，第三位是绿色，需进行三位预测。现在假定有三个模型，第一个模型在最右边犯错，将绿色误判为黄色；第二个模型在正中间犯错，将黄色误判为绿色；第三个模型在最左边犯错，将绿色误判为黄色。每个模型都犯了一个错误，其精度为66.6%。但若将这三个模型结合，采用多数投票法，即两人说绿色则判为绿色，两人说黄色则判为黄色，结合后结果将完全准确。虽然每个模型精度不高，但结合后的结果比最佳模型还要好，说明集成方法确实有效。

这一点有时不易理解，即一堆模型中的最佳组合能否比单个最佳模型更好，实际上集成方法确实能提升性能。但并非任意组合都能起作用，需看具体错误情况。若三个模型都犯相同错误，则多数投票无法改进结果。若每个模型错误相同，则集成后无改变。这说明集成机制要起作用，个体必须不同。再看另一情况，若每个模型都犯不同错误，则集成后精度可能降至零，甚至更差。这说明集成要起作用，每个个体不能太差。集成学习的基本道理是，个体必须好且不同。实际上，团队合作有时比个人做得更好。

在集成学习领域，有理论分析给出漂亮公式，这来自于误差-分歧分解公式，E是集成后的误差，即多个模型结合后作为整体学习器的误差。是每个个体误差的平均值，即平均性能；

是平均分歧度，后来被称为多样性，即个体之间的差异度。我们如何理解这个式子呢？我们构建了一个集成学习模型，希望其误差小。首先，希望每个个体的误差小。其次，希望这些个体间的差异大。这就是我们刚才直觉上说的，每个个体要好而不同。事实上，理论上给了我们支撑

这个漂亮的式子，是在1994年证明出来的，1995年发表的。这告诉我们，越精确且个体差异越大，最后得到的集成就会越好。得到这个式子后，是不是一切问题就解决了呢？

比如，训练很多模型后，我们可以通过模型评估方法知道其误差，从而控制平均误差。如果我们也能通过模型选择方法测出平均差异，那最后就能找出一个误差最小的集成。但问题是，我们做不到。为什么呢？后面要说的diversity没有一个可操作的定义，在证明过程中，它是从数学上强制定义出来的，而这个东西需要知道理想的ground truth结果，如果不知道ground truth结果，我们就不知道这个东西怎么来。所以，在现实生活中不知道ground truth时，这是没法定义出来的。第二，error ambiguity的分解，首先它只是针对回归问题，我们得到这样的分解；只有在square loss的情况下，我们才能得到这样的分解。比如，我们更多的是做分类问题，分类问题做01损失时，其实猜不出这个东西来。

所以，这个理论只能从理论上给我们一个直觉和非常好的支撑，但不是直接可操作的东西。所以我们要研究很多有效的算法。事实上，真正要做到我们刚才说的这两件事情非常不容易。你想，如果差异要大，同时误差还要小，大家想一想，假设我做五个模型，每个模型的精度都已经是99%了，这时候这些模型会不会高度相似？那这时候如果我要追求让差异大一些，一定意味着要损失一部分性能来换取这个差异。那什么时候换来的差异是值得的呢？这里面就有一个error和ambiguity的取舍问题。而这个tradeoff不是那么容易找到的，给设计算法带来了很大的挑战。

两类常用的集成学习方法

经过多年发展，我们已拥有一些有效算法。此处仅介绍代表性技术，集成学习方法大致可分为两大类：一类为序列化方法，另一类为并行化方法。从名称可知，序列化方法中，每个个体生成后，与前面个体存在依赖关系，需逐个生成，后续个体依赖前面个体，可理解为串行做法。并行化方法则允许所有个体同时生成，通过并行与串行对比可理解此点。

第一类方法最著名的算法代表是Boosting，它是这类算法的起点。目前最常用的算法实际上是Gradient Boosting，很多同学可能参加过比赛，应用过XGBoost算法，它是Gradient Boosting的一种高效实现。算法的好坏不仅取决于算法本身，工程化实现也至关重要。该算法由斯坦福大学的Friedman于2001年提出，但长期使用者较少，直至后来一位华人学生陈天琪实现了XGBoost，其实现过程非常巧妙，运用了许多工程化技术，如内存调度等，使算法运行快速且效果良好。因此，大家广泛使用XGBoost，但从算法角度看，它实为工具。Gradient Boosting是目前最常用的算法，此外还有许多著名的Boosting变体。LPBoost算法利用数学优化技术解决问题。

并行化算法中最著名的是Bagging，它被视为一种基准，但目前最常用的是Random Forest，可视为Bagging的改进版，两者均由Leo Breiman提出。此外，还有随机子空间方法Random Subspace，也是并行化方法的一种。接下来，我们将分别介绍这两大类方法的重要代表。

Boosting算法

Boosting我们将其视为一个框架进行介绍，后续会详细讲解。现在，大家先了解boosting的大致流程。由于adaboost衍生出一个以boost结尾的大家族，通常我们称之为boosting。整个家族的工作流程如下：首先，我们获取一个初始训练集，即大家手中的训练数据集，假设其为dataset1。接着，我们选择一个算法，比如决策树或神经网络，这里假设使用决策树作为机器学习算法。注意，我们通常有几个术语，即base learning algorithm，这是什么意思呢？

在集成学习中，有同质的和异质的。一般来说，我们重点考虑同质的，因为它有很多好处，且实现起来比较方便。只需用一个算法进行多次训练，就可以得到多个模型。与异质的集成不同，异质集成需要实现神经网络、决策树等多种算法，实现起来更麻烦。但这两类技术在技术上差别较大，我们要做到“好而不同”，对吧？如果是同质的，都是从同一个数据集生成的。比如生成若干个决策树，如何使它们既好又不同呢？让它们好是有办法的，可以通过模型选择来实现。但让它们不同就很麻烦了。因此，在同质的集成中，最麻烦的是如何保持多样性，即保持差异。而异质的集成虽然也是从同一个数据集生成，但模型本身就不一样，所以，差异已经存在，只需做好每个模型即可。但问题是，不同模型产生的输出不能直接比较。比如，在进行预测时，一个神经网络给出a是0.7，b是0.3；另一个logistic regression给出a是0.6，b是0.4。能否简单地将这两个结果相加并比较呢？不能简单地相加，因为不同算法的输出不能直接比较。在这种情况下，如果两边都是a大，我们还好处理一些，可以取两边排第一的。但如果反过来，0.4对应0.6，怎么办呢？不能简单地认为0.7比0.6大。不能仅根据数值大小来选择，必须进行比较。对不同模型的输出进行比较时，必须有一个过程，叫做alignment，即配准。这件事相当困难，就好比两个专家，第一个专家给出的0.7和第二个专家说的0.7其实不是一回事。其实大家想一想，参加很多体育比赛时，有些人分数打得低，即使表现最好也可能只打60分，而有些人表现最差也可能得80分，无法直接比较。这需要进行对齐和配准，而配准这件事非常困难。如果大家有兴趣，可以回头看一看西瓜书中支持向量机那一章的阅读材料，其中提到了一些常见的配准技术，如plato scaling等，比较麻烦。在集成学习里，我们重点关注的是同质情况。如果是同质的，意味着我们有一个算法，输入数据后会生成很多个同样类型的模型。在这种情况下，我们把这个算法叫做基学习算法，对应的学习器就叫基学习器。比如，如果每个模型都是C4.5决策树，那么现在的集成方法就是C4.5决策树，基学习算法就是C4.5学习算法，大家需要理解“base”的意思。那么boosting是怎么做的呢？

首先，我们把训练集叫做dataset one，然后把基学习算法应用上去，这样就会产生一个模型，即learner1。如果我们现在用的是决策树，那么这就是一个决策树模型；如果用的是神经网络，那么就会产生一个神经网络模型。有了这个模型之后，我们下一步怎么做呢？我们可以用它来对原始的训练集进行预测和判断，相当于用这个数据对它进行测试。在boosting中，我们一定能看到有些预测做对了，有些做错了。那么，boosting是怎么处理的呢？它会让数据集产生第二个数据集。这个第二个数据集是怎么产生的呢？假设数据集中有一部分是做对了的，有一部分是做错了的。假设我们为每一个样本维持一个权重，做对了的权重下降，做错的权重上升，根据这个权重，再进行采样就得到第二个数据集。能明白这个意思吧。

比如：这是我们一开始的数据集，包含12345个样本，假设每个样本的权重都是1。然后，我们用这些数据做了第一个模型，并用这个模型对原始数据集进行预测。结果发现，有些预测做对了，有些做错了。接下来，我们调整一下权重。假设我们做个调整，但这不是一个有理论保证的调整方式。我这里只是举个例子，我要把这个权重变小，那么怎么变呢？我把所有权重都变成二分之一。都变成二分之一之后，多出来的部分怎么办呢？比如，原本权重是五分之一的，现在变成二分之一，那么我就把它加到其他样本的权重上。这样调整权重后，总的权重还是五个样本的权重之和。那么，接下来我们怎么做呢？我下面根据权重进行采样以产生第二个数据集，该数据集包含五个样本，但我对它进行了采样，使得只有三个样本，具有二分之一的可能性被选择，而原本就有二分之一的可能性被选中的样本，现在被选中的可能性更多。实际上，新得到的数据集就会呈现这样的特点，即原本做错的两个样本在数据集中将受到更多关注，这是采样的做法。当然，也可以不采样，直接将权重带入，如果是决策树作为机器学习器，它能直接处理带权重的样本。大家还记得，直接带入权重即可，这样前面做错的样本就会受到更多关注。如果算法无法处理权重，比如神经网络，就不适合直接处理权重，这时我们就进行采样。通过采样，我们可以使第二个数据集更加关注第一个数据集做错的样本。

有了第二个数据集后，我们再对其训练一个模型，使用原来的算法在这个数据集上学习，得到一个新的模型。这样不断训练，假设进行t轮，就会得到t个模型。可以看出，前面的模型解决的是相对简单的问题，越到后面，面对的问题就越困难。这是因为前面做错的样本被重点交给后面的模型去解决。打个比方，我先给第一个学生十道题，他做对了八道，做错了两道。然后给第二个学生，重点让他攻克这两道，而前面的八道，他只需要做三道，并且可能又做对了一道。再往后面呢？再做前面困难的题目，明白这个意思吧。所以，前面的模型性能会好一些，后面的模型性能会差一点，因为后面面对的问题比前面困难得多。

所以，我们不能简单地把它们合并起来，而是需要用加权结合的方法，即每个学习期都有一个权重。这个权重实际上在算法中是自动确定的，这是算法的基本流程。我们可以用这样的思想来做分类、回归，甚至排序等各种机器学习任务。它是一个框架，都可以用这样的思想去解决，但是具体的算法，针对不同任务，肯定要做不同的推导。但大体上的思想就是这样，大家明白了吧？其实，如果你们统计学学得特别好，看到这个过程，应该想起一件事：残差最小化或者说残差逼近，实际上你可以从这个角度去理解adaboost算法，它实际上是对统计上残差最小化过程的一个高效计算机算法的实现。这个算法的设计是非常了不起的。

Bagging算法

接下来讨论bagging，这更容易理解。我们拿到一个数据集，然后从这个数据集生成多个学习器。想象一下，给定100个数据，每次使用C4.5决策树，生成一个C4.5模型。如果每次生成的都一样，生成的都一样，再将其结合就没有用了。所以现在怎么做呢？我们采用一种技术，从数据集0生成1、2、3等n个数据集时，使用bootstrap sampling，即可重复采样。大家还记得吗？袋子里有很多球，每次从这里面取四个，但每次取出一个球后，可以将其放回去，这样同一个球有可能被多次取到，有些球可能每次都取不到。这样，我们可以生成多个模型和数据集，每个数据集都会不同。我们知道，大概63.2%的数据会被取到，所以还有30%多留在外面，这样每个数据集都不太一样。

然后，在每个数据集的基础上建立一个模型，最后将这些模型全部结合起来，这叫做bagging算法。在结合时，通过投票进行分类，通过平均进行回归。这很容易实现，因为此时每个模型都应该被平等对待。这与之前的adaboost不同，boosting是序列化的，前面的模型简单，后面的模型复杂，不能同等对待。现在则可以同等对待，这是一个非常了不起的想法，实现起来也非常简单。这个想法很有意思，而且确实非常有用。它的改进版就是随机森林，至今仍在广泛使用random forest。所以，集成学习中这两个最重要的代表性方法：boosting的XGboost和bagging的代表性方法random forest，至今仍在广泛使用。