漫谈 Boosting 算法（文字版）

点击这里收听本期节目音频版

编辑： 肖怡婷

本期嘉宾： 张家鹏（UCSD 博士候选人） (G)

主播： 舒晏 (S), 阿拉法特 (A)

A: 这一期的德塔赛节目比较特别，以往我们都是在和嘉宾一起讨论他们自己的研究，但是我们想尝试一些新的内容，比如说能不能和嘉宾一起讨论一些经典的算法。今天这期节目我们是和嘉宾讨论了一类经典的机器学习算法，叫做 Boosting，希望你会喜欢我们这次的尝试。不过即便你还是觉得更喜欢和嘉宾聊他们自己的研究也没有关系，你可以期待我们下一期节目。接下来就是我们正式的节目了。
A: 大家好，欢迎收听德塔赛。我是阿拉法特。
S: 我是舒晏。今天加入我们节目的是张家鹏，他也是UCSD的博士学生。
A: 张家鹏给我的印象是研究主题涉猎非常的广泛，我也不知道应该怎么去总结你的研究。要不你先给我们介绍一下你自己吧。
G: 我主要是研究布尔函数分析，还有计算复杂性，然后根据这些作为根基再来研究一些相关的应用，比如机器学习理论或者是密码学理论。
S: 那你之前的研究和 boosting 有什么关系呢？你是通过什么方式开始了解 boosting 呢？
G: 我最先看到 boosting 的东西是在复杂性领域里面，boosting 在复杂性领域里面也有很多的应用。我自己的第一个工作也是用 boosting 来做的。
A: 那我们今天话题的中心是这个 boosting 算法。我觉得这个算法的起源是一个非常有趣的故事，它起源于这样一个问题，就是强学习器和弱学习器是不是等价的。
S: 那家鹏，你可以和大家介绍一下什么是强学习器和弱学习器吗？
G: 强学习器就是说我在机器学习的过程中，我希望能够有一个学习的算法，学完之后可以非常非常精准的预测需要预测的东西。弱学习器就是说我这个预测只是比随机猜要好一点点，比如说好 1% 就是好一点点，这就叫弱学习器。
A: 对于强学习器和弱学习器之间的区别，张家鹏这样的解释可以说是一个比较直观的印象。如果大家想更正式的理解它们之间的区别的话，我觉得可以从PAC Learning这个模型上去理解。对于一个强学习器，我们一般是期望如果我们给它足够多的训练样本，那么它最终能够实现任意小的一个错误率，但是对于弱学习器我们是没有这样的要求的，也就是说你可以允许它有一个正确率的极限，超过这个极限，你给它再多的样本，它也不一定能够再改进自己的正确率了。
S: 刚才我们说到 boosting 起源于一个强学习器和弱学习器是不是等价这样一个问题，那我们怎么理解这句话呢？
G: 我们可以看到它们两个的定义是不一样的。说它们等价是说如果对于任何一个学习的问题，你都有弱学习器，可能是不同的弱学习器。我们可以用一些算法把它们拼接起来，最后成为一个强学习器。在这个过程中 boosting 就是一个很有力的算法。
S: 感觉这就是怎么把几个臭皮匠变成诸葛亮的故事。
A: 那这是一个音频节目，所以我觉得刚刚我们的解释得有些过于抽象。张家鹏能举一些例子吗？一些强学习和弱学习器的例子。
G: 我可以引用一下之前一篇很有名的文章里面引用到的例子。假设今天要去炒股，然后有很多个专家，里面有一些专家很厉害，但是我现在不知道是谁，我要怎么去把这些专家给找出来。这就是一个在线学习的问题，就是说我要找最好的（专家集合）。Boosting 的想法就是说我先在第一天在每一个专家上都投一样的钱，然后看第一天之后的反馈，谁猜的比较准，我第二天的时候就在他们身上加码，猜的不准就减码，直觉上来说很多天之后我这个算法就会越来越准的，因为在那些很厉害的专家身上的码会越来越大，因为他猜准的天数比较多，然后在那些比较弱的人身上的码会越来越少，这就是通过一个弱学习器慢慢变成一个强学习器的过程，因为你每一天的信息都是拿到一点点，然后你就可以有一点点反馈，然后就不断地改变你这个学习器，最后可以理论上来证明它可以达到非常非常接近于最好的那一个方法。
S: 那这个时候我们是应该把每一个专家独立的当成一个弱学习器，然后把他们最后组合得出来的一个意见当成一个强学习器吗？
G: 可以这么说，对。
A: 这个例子很有趣，你刚说的时候我就在笑，因为我想起来我之前听过的一个节目，那个节目是在采访 Kickstarter 的创始人Perry Chen。Kickstarter 是一个众筹网站，就是如果你有一个项目，你可以把它放到上面，大家可能会筹钱帮助你把这个项目做起来。后面你可能需要把一些初期做出来的产品再卖回给当年赞助你的这些网上的朋友。那 Perry Chen 在节目里面说他在做 Kickstarter 之前做了很多不一样的工作，其中有一个工作就和你这个例子很像。当时是 1999 年左右，就是互联网泡沫之前，股市上尤其是互联网相关的这些公司的股票可以说是价格非常的高。因此当时是可能有一种假象，就是只要你进去炒股你就能够赚到钱。大家也知道后来到 2000 年的时候泡沫破碎，也是出现了一个比较严重的经济危机，但是这个故事是发生在泡沫破裂之前。Perry Chen 就是听到这么一个工作机会，说是没有任何的背景上的要求，只要你知道怎么操作电脑就可以了。那么他就去应聘了，接受了五天的培训。工作的内容就是帮助一个富豪管理资产，说是管理资产，其实本质内容就是他雇了很多人，然后给每个人一小部分钱，让他们就随着自己的想法用他的钱在股市上交易股票。如果你股票交易的比较好，他就给你更多的钱；如果交易得不好也没关系，他不会让你去承担这个损失。他给你的工资提成就相当于你帮他赚了多少钱，他就可能给你给提成。当然这个工作他当时说他只做了两年，后来就觉得没有什么意思就辞职了，然后开始想怎么创办自己的公司。可能作为一个人类来讲，做一个弱学习器并不是特别有趣的事情吧！
G: 我会比较好奇的是他最后赚到了钱吗？
A: 那他提到他自己是赚了比较满意的回报，经济上来说。但是他没有提到这个富翁，他后来有没有通过这种方式赚到钱，尤其考虑到后面其实是经济危机，所以我并不是特别的乐观。如果大家对这个有兴趣，我会把这个节目放在我们节目的描述里面，大家可以自己去听一下。那个采访也是在一个播客节目中做的，那播客节目叫 How I Built This，可以说是我最喜欢的播客节目。那我们是一直在聊 boosting 的一个基本的思想，但是具体要拿 boosting 去把弱学习器强化成一个强学习器是需要实现具体的算法的。有非常多的 boosting 这一类别的算法，其中最有名的，也是早期的 boosting 算法中最有效的一个，应该是 AdaBoost。
S: AdaBoost 其实是一个被写进了各种机器学习教科书的算法，也是小阿的导师 Yoav Freund 的成名大作。他在 2003 年因为 AdaBoost 这个工作得到了哥德尔奖。家鹏，你可以给大家解释一下 AdaBoost 这个算法吗？
G: AdaBoost 这个算法呢，它这个 Ada 的意思就是 Adaptive，就是它是可以自适应的去做 boosting 的一个算法。我们知道在这个学习的过程中，一开始的时候每一个训练数据都有一个权重，最开始的权重我会用一个弱学习器去学它。
A: 一开始的这个权重，我们一般是全部给它们一样的权重吗？
G: 这个取决于你。因为我们知道在机器学习的时候，都会有一个最先验的数，先验权重，就是以那个权重为准。然后我在上面做弱学习器。就是说学完一轮弱学习器之后，我看哪些数据错，哪些数据对。直观上的说法就是说我在训练错误的那些数据集上的把它的权重稍微加大一点点，然后那些训练对的小一点点，然后继续再用弱学习器来学，之后又会有一个新的学习器出来。这样不断的迭代，最后会迭代出一个最终的学习器，我们可以证明这个最终的学习器就是一个比较强的学习器了，因为我之前在错误的上不断的去迭代的去学。
S: 那 AdaBoost 对弱学习器有什么要求或者是假设吗？
G: 不需要有特别的假设，它可以是任何的算法，唯一的要求就是它要比一个随机乱答的学习器要稍微好一点点。
S: 也就是说对于所有的弱学习器，有一些比如说可以是回归算法，有一些可以是神经网络，有一些可以是决策树，它们甚至不需要是同一类的，我们可以把它当成一个黑盒子，对吧？
G: 对。
A: 那我想补充一点，在这一期节目中我们没有特意的区分一个学习算法和算法学习出来的模型，我们都统称他们为学习器。但如果我们想更严谨的描述，学习器，或者说一个 weak learner，可能更多还是指一个训练出来的模型——我们给它一个样例，它会给你一个它预测样例的标签，而不是说一个训练模型的算法。那么当 AdaBoost 拿到一个数据之后，它先给它赋予一个初始的权重，然后它就把这个权重和数据一起交给一个训练弱学习器的算法。接着算法就会给它返回一个弱学习器，也是一个非常具体的模型。那么它会根据这个弱学习器来调整所有的这些样例的权重，让那些模型目前会犯错的样例的权重增加，让那些弱学习器已经能够正确判断的样例的权重减小，从而使得新的权重会更加地聚集在那些我们目前不能够正确的判别的样例。之后 AdaBoost 会重新再把这个新的权重交给我们的算法。算法这次会给它返回一个新的弱学器。这一次训练出来的新的弱学习器就会在那些我们之前判断错的样例上表现更好一点。
S: 那刚才家鹏和小阿都提到了说每个训练数据都会根据它的这个有多么的难或者有多么的重要有一个权重，那么我们这些弱学习器也是有权重的吗？还是我们自始至终都假设它们是一样重要的呢？
G: 我们在训练的时候可以把这些弱学习器也给他们一些权重。在 AdaBoost 的算法中是会给它一些权重，但也有一些算法是不给它们权重的。
S: 那刚才我们说到 AdaBoost 的一个巨大的优势就是在于给定任意的一些弱学习器，我们都可以把它提高成一个强学习器。那么除了这一点以外，AdaBoost 还有什么其他的优点吗？
A: 我想讲一个我自己平时研究的例子。大家在实验上会发现 AdaBoost 是一个比较不容易过拟合的算法。一般直观上大家会认为如果你训练一个算法训练很长时间，它会慢慢的在训练集上表现的越来越好，但是在测试集上它就开始表现越来越差。但是这个现象在 AdaBoost 和其他 Boosting 算法上还是比较难出现的；它还是会出现，但是不太经常出现。我觉得这个问题是有几个论文在谈，其中有一个说的特别清楚的一篇论文，他是提了一个叫做 Margin Explanation（的理论），就是用 margin 去解释这个现象。举例来说，AdaBoost 去训练一个问题的时候，很快你在训练样本上的错误率就已经达到了零，但是如果你还是接着训练，并没有让算法停下来，你会发现测试数据上的错误率也还是在继续下降。对于这个现象的解释就是说，虽然在训练数据错误率达到零的时候，看起来算法已经没有什么别的事情可以做了，但实际上还还可以做另外一件事是：它可以改进自己在说一个样例是正样例或者负样例的时候的一个信心，这个信心的衡量方法就是 margin。关于这个概念一个最有名的例子应该是 SVM 这一系列算法中。大家可以想象 SVM 是在找正负样例之间的一个分界面，如果你的样例离这个分界面越远，你就会对你的判断越有信心。这也最后成了 SVM 算法的一个目标，就是让样例离分界面的距离越远越好。同样的想法也被运用在 boosting 算法上，算法在让训练数据上的错误率达到零之后还在继续改进，就是在把训练数据中的样本推的离这个分界面越来越远。由于这个过程，测试数据上的错误率也很可能会继续的下降，因为训练数据上算法正在持续的提高它在做决策时的信心，那么即便是在没有见过的样例上，犯错误的概率也会相应的减小。
S: 那在 boosting 算法里面这个 margin 或者说信心到底是怎么体现的呢？
A: AdaBoost 算法里 margin 的表达式实际上是它的 AdaBoost 损失函数的一部分，算法直接优化的目标是最小化这个损失函数的值。如果大家具体去看它的损失函数，就会发现为了最小化损失函数的值，我们需要尽可能最大化每一个数据点的 margin，所以在训练过程中相当于一个副作用是去最大化的每个数据点的 margin，这也是我们想要的。
S: 这也是为什么它可以达到减少过拟合的这个原因。
A: 对，因为如果对于每个样本的 margin 大，你对你的判断的信心也就比较高，所以就降低了你在没有见过的样例上犯错误的概率。关于 boosting 我其实有一个问题，是源于最近我们学校的一个教授叫 Russell Impagliazzo，他做了一系列的讲座去解释，把这个 boosting 和 Generative adversarial networks (GANs) 这一类的神经网络联系起来，但是我自己其实并没有太多的理解他的讲座的内容。张家鹏你对这方面的工作了解吗？
G: 我大概知道一些。我们之前有讨论过 AdaBoost 的想法，大概就是说我每次下一轮的时候都会集中研究之前那些训练错误的样本。GANs 主要的想法是用对抗网络的方式不断的帮你去找哪些点你是之前没有学习好的。有了这个之后，你就可以更好地去做 AdaBoost。
A: 直观上是感觉它们俩在做一样的事情。
G: 它们两个在做互相对抗。AdaBoost ：我就是想要知道我哪里学的不好，之后就可以学得更好；然后对抗网络就是帮你去找你哪里学的不好。
S: 听起来 AdaBoost 是一个很适合用来解决实际问题的方法，因为其实有很多很困难的实际问题是很难直接找到一个非常非常好的假设的。但是找到一些略好于随机的假设却不难，所以说我在想 AdaBoost 一开始有没有用来解决什么实际问题呢？
A: 我印象比较深刻的一个早期应用是照相机里面的人脸识别。大家现在已经习惯了，无论你是拿手机还是一些便携照相机对准一个人的时候，你会看到这个人的脸的周边会出现一个长方形的框。在早期的时候，并没有一个算法可以实时的在这样小型的设备上跑起来，因为大多数人脸识别算法需要的特征数量非常高，同时在这些特征上学习的算法所需要的时间也会和特征的数量成比例的增长，所以就需要很长时间去做运算。
在 AdaBoost 算法提出来之后就这么个应用，它其实是一个比较通用的应用，只不过一开始应该是在人脸识别上先具体化的。我们先描述一下这个问题，就是给你给一个照片中的一个区域，比如一个照片中的一个长方形的框，然后你需要判断的是一个简单的是或者不是的问题：这个区域里包含的是不是就是一个人脸。当然有很多方法可以在这个区域里面提取特征，具体它提取什么特征和 AdaBoost 其实没有太大的关系，所以我们就不展开讲了。他把这些特征提取出来之后，这些特征的数量还是比较高的，一些其他的机器学习算法所需要的运算量非常大，那他当时就想了这么一个 AdaBoost 算法的应用，就是说他定义了一系列的弱学习器，每一个弱学习器可以简单地用一个条件判断语句来形容，就是如果特征向量第K位大于等于或者小于等于某一个 threshold，那么这个就是一个人脸。
这样的判断语句大家可以想象，它肯定是要么就完全随机，要么即便不是完全随机，它也是正确的概率不是很高，可能 51% 或 52%，但这就符合了我们弱学习器的定义。这一系列的弱学习器最后经过 AdaBoost 增强就产生了一个强的判断算法。为了加快这个运算时间，你其实并不需要把这些所有的弱学习器都加到你最终的强学习器里面，你可以只加一小部分的特征。假设对于这个特定的人脸识别问题，你有一万个特征，那么你就相应有一万个弱学习器。但是你并不需要一个包含了一万个弱学习器的强学习算法，你可以让它只包含，比如一千个，那么你的这个 AdaBoost 算法就只迭代一千次，它实际上也只看了这一千个特征。如果它的最后的正确率能够达到你的要求，运行的时间上它肯定是远远快于你考虑所有这一万个特征。
G: 我知道 AdaBoost 最近也有一个很大的应用，就是在差分隐私里面带来的应用。差分隐私是最近在隐私研究领域比较重要的一个完成隐私保护的方式，它一方面是希望能够泄露一些信息出来让大家做研究，另外一方面又不希望把个体的隐私给暴露出来。所以就有了差分隐私这个概念，就是我泄露该泄露的信息，但是保护该保护的信息。怎么完成这一点一直是一个问题。最近就是可以用 AdaBoost 来完成这个问题，这是一个很漂亮的解法。
A: 所以这是已经有一个相关论文发出来了吗？
G: 对，已经有了。
A: 我觉得到这里我们提了很多不同的 AdaBoost 的应用，可能大家会觉得有点信息过载的感觉。我会把所有这些我们提到的资料都放在我们的节目的笔记里面。如果你对某一个方面的问题有更多的兴趣，你可以去读那一方面的内容。
S: 我看到 AdaBoost 在特征选择上有很多应用，但是我没理解 AdaBoost 是怎么和特征选择联系在一起的呢？因为在 AdaBoost 里面我们所选择的对象不是某一条数据比较困难，比较重要吗？那它和每一个特征有什么关系呢？
A: 谈到这个问题，我觉得比较好的例子是一种叫做 Specialist 的弱学习器，在我们最早的节目、和张驰丞师兄录的时候，我们有提到过有一类的学习器，它可以对一些样例回答不知道。那么这种学习器我们可以统称为 Specialist，就是它只对某些特定的样例是专家，当它看到这方面的样例的时候它会回答它们的标签，但是对于其他一些它不太了解的样例，它就根本不会回答。当我们有了 Specialist 这种弱学习器的时候，我们可以做很多有趣的事情。Feature Selection 就是其中一个，在这里我可以举一个例子。这几年，机器学习在基因序列中的应用越来越多，比如说我们现在有个问题想预测一段基因序列和某一个疾病的相关性，那么我们可以定义一系列的 Specialist 专家，每一个 Specialist 都只专注于一小段基因序列。一个 boosting 算法就要在这些 Specialist 中选择一部分，把它们加到你最终的学习器集合中，并且每次加的时候 boosting 算法会给每一个专家一个权重。那么最后在 boosting 算法在这个问题上完成训练之后，我们会得到一个学习器集合，就是我们给算法的一系列 Specialist 以及它们相应的权重。根据这个权重的大小，我们就可以认识到哪些专家更重要，再预测这个疾病的相关性上，哪些专家不那么重要。有了这个重要性，由于每一个专家是指专注于一小段的基因序列，它就可以翻译成这一段基因序列对于预测这个疾病有多么的重要。所以从机器学习的角度来说，这可以看作是对一段基因序列的一个特征选择。
S: 那刚才我们说到 boosting 的几个应用都是比较早期的工作，那在近几年 boosting 领域有什么比较大的突破吗？
A: 近几年最有名的一个 boosting 软件，应该是陈天琪写的 XGBoost，它可以说是 Kaggle 上的最常用的一个包。记得有一种说法，说 Kaggle 上的这些问题就基本上就是要么用神经网络解决，要么就用 XGBoost 来解决。但是 XGBoost 它并不是实现了 AdaBoost ，而是实现了 Gradient Boosting 的算法。张家鹏能给我们介绍一下这个 boosting 和 gradient 梯度下降有什么联系吗？
G: 在我们平常做理论的研究中，我们一般不太用梯度下降这个描述，我们一般是用 KL Divergence。所以说因为我们知道我们有个目标函数我们要学它，但是我们在学的过程中不一定一步就能到位，就是说我们每一次有一个弱学习器来了之后，我就是把它拼一下，然后我们在理论就是证明我每拼一个弱学习器之后，你当前有的这个函数跟那个目标函数的 KL Divergence 是会逐渐的减少。从结论上来说，就是它的 KL Divergence 在减少，然后就是一种刻画它们距离的方式。
A: 对，KL Divergence 是一个信息论上比较常用的刻画两个不同的概率分布之间距离的方式，所以在这里我们是说你用弱学习器拟合出来的这个函数和你要拟合的真实的函数之间的距离在不断的下降。
G: 是。
A: 其实 AdaBoost 也是可以从梯度下降的角度来解释。AdaBoost 算法每一步完成之后，对于样例权重的调整以及对于新加入的弱学习器所赋予的权重都是为了能够最大化的下降 loss function 的值。
那么回到 XGBoost，XGBoost 给我最深的印象是它的运行速度非常快，而且内存占用也相对非常小。我之前是用 Spark 和 XGBoost 同时跑过同一个数据集。Spark 可能有很多人用过，是一个相对来说已经是非常好用的分布式数据处理软件。但是 XGBoost 还是无论在运行时间上还是内存占用上都远远好过了 Spark 默认提供的 Gradient Boosting 的实现。XGBoost 另外一个好处是它提供了很多不同语言的支持，比如说我知道的你可以直接用 Python 和 R 语言去调用 XGBoost 提供的 Gradient Decent 算法，所以说在使用上是非常的方便好学的。如果有人问我说他想用 boosting 去解决一个特定的机器学习问题，应该用什么软件包，XGBoost 可能会是我最推荐的一个，除非说你不想在电脑上安装一些新的软件包，更想用比如说比较流行的Python的机器学习的库，那么 scikit-learn 里面应该也是有 AdaBoost 和 Gradient Boosting 的实现，但是效率上肯定是远远比不上 XGBoost 的。
S: 今天我们跟大家讨论了 boosting，主要说了 AdaBoost 和 Gradient Boosting 两种方法，那今天的节目呢就是这些。我们非常感谢家鹏和我们来录这期节目。
G: 谢谢邀请。
A: 今天也是我们第一次以一个经典算法作为一期节目的主题，而不是像往常一样以这个嘉宾的工作为主，我心里其实很忐忑，不知道录出来效果怎么样。
S: 我们也希望听众朋友们能够给我们留言，告诉我们你更喜欢哪一种形式。
A: 那么今天这期节目就到这里了，我们下期节目见。
S: 再见。