【十分钟 机器学习 系列课程】讲义（59）：AdaBoost算法 前向分步算法

欢迎回来，周末愉快。上两期【十分钟 机器学习 系列课程】讲义（57）：AdaBoost算法定理8.1中的训练误差上界，【十分钟 机器学习 系列课程】 讲义（58）:AdaBoost算法 定理8.2 二类分类问题 AdaBoost的训练误差界，我们带着大家一起手推「AdaBoost算法的」2个定理和1个推论，明确了训练误差是「以指数速率下降的」由来，那么这期开始我们就要进入到「AdaBoost前向分步算法」中了，好啦，话不多说，开始正题。

壹 什么是回归中的前向思想？

1.如何找到最有用的自变量？

在咱们开始讲解AdaBoost前向分步算法之前，我们先来了解一下回归中的前向思想，这个思想顾名思义，就像下面的「超级玛丽」一层层爬楼一样，逐步升级。

那么转到数学视角下，我们可以举个例子。

❝

线性回归模型中含有 个「自变量」，记为：

相应的「因变量」分别是：

❞

怎么从这么多变量中选出对因变量线性影响最大的自变量呢？

在这里，我们可以先用已知的 个自变量构造出一个线性模型，这里 是一个误差项：

如果对训练数据集

我们想知道哪个变量对 的线性影响大，是不是看谁的系数 大就行？

答案是「否定的」，就比如对于一个自变量 而言，如果它代表的身高，那么当身高分别以 cm 为单位和 m 为单位时，自变量前面必然对应不同的 ，那么就意味着「不能简单地通过比较系数大小来找到线性影响最大的自变量」。

有什么办法能解决这个问题呢？

可能有小伙伴会猜，比较每个自变量  与因变量 的相关系数（皮尔逊相关系数） ：

是不是就可以？

可以是可以，但是单纯比较 只能分别判断哪个自变量对因变量线性影响最大，如果选出相关系数最大的 3 个自变量，

构建线性回归模型

这个模型是否可以充分体现「自变量对因变量的综合线性影响」呢？

这也是不确定的。那怎么办？

如果用个笨法子，我们可以把自变量的所有组合 全部试一下，哪一个效果好就留下哪个。但问题是，如果 很大，这个工作量也是巨大的。

于是就有人想出了局部回归的巧妙方法。

2.Stepwise Reggression

逐步回归，英文是「Stepwise Reggression」，根据是往前还是往后又分成了「Forward」和「Backward」。

这里我们以「逐步向前模型」为例，也就是 Stepwise Forward Reggression 来介绍。

咱们不妨就从「零模型」开始，这里的「零」其实就是代表压根不考虑那些自变量 是谁，而是先观察这些因变量 的特点。

如果我们训练集得到的因变量观测值为

我们通常用一个平均值来代表 。

这就好比对一个产品的价格预测而言，最简单的办法就是把这几年价格取一个平均值来作为预测值，而不是通过考虑这个产品的原材料、工艺、成本等等自变量的因素预测出价格。

列一个式子 来描述这个数学关系：

注意哦，看这个式子里面是「没有自变量」的。

接着，我们考虑进来一个自变量的情况 ，就可以写成：

注意哦，这里咱们说的考虑一个自变量的影响，那么到底选 中的哪一个呢？这里我们可以把它们都依次代入试一试，然后看看谁最合适，当然，你可能会问合适的标准又是什么？莫慌，通常的判断准则很多，比如 「AIC、BIC、F检验」 等等，它们的思路无非就是之前说的体现出良好的 「拟合和泛化能力」。

根据这样的思路选出一个最佳的自变量，比如这里我们选的是 ，记 。

接着我们就要构造下一个模型：

而这里的 就是从刚刚剩下的 个自变量里面去挑选，选出的变量标签记作 。这样每轮都做判断，直到判断的结果不如上轮好就满足了收敛条件，完成了回归模型。

假如经过 轮之后完成，则回归模型就是

❝

同理，「逐步向后模型」也是同样的类似的思路，不同之处在于初始的模型，是一个「全模型」，意味着包含了所有的「自变量」，可以写成：

❞

然后根据前面说的判断准则，逐次剔除掉1个自变量，直到判断的不如上轮好就满足了收敛条件，就完成了向后回归模型。

逐步回归就是向前和向后相结合，便往前走边回顾过去，一边添加自变量一边看是否有多余的自变量可以剔除。

这一思想也凝聚了先贤的智慧，小时候学过的文言文课文就有类似的语句。

❝

子曰：温故而知新，可以为师矣！

子曰：学而时习之，不亦说乎！

曾子曰：吾日三省吾身！

❞

贰 什么是可加模型？

1.Additive model

搞清楚了前面说的「逐步向前模型」的思路，接着我们再来说一个知识点。

它叫做 Additive model，在不同的教材中翻译的不同，有叫加法模型的，有叫可加模型的，在《统计学习方法》中称为「加法模型」，但我认为叫做「可加模型」和我们逐步向前模型的思路更为一致，更好理解些。

它的模型是什么样呢？「和线性回归模型不同，在可加模型中，不做自变量和因变量的关系限制，可以列为自变量和因变量之间有个未知的结构」，可以写成：

那么，它们内部的关系可能是「线性的」，也可能是「非线性的」。假如以若干「未知的基函数」表示，有 个函数相加，当然还有对应的系数 ，整理一下可以写成：

因为这里的 是一个期望，所以后面就没有了那个误差项 了。

在回归模型中，这种表达方式会更广泛一些，其中的基函数可以是线性的，也可以是非线性的，甚至是以分类树的形式，比如我们后面就要讲到的「AdaBoost前向分步算法」。

那么，接着我们就把它写成求和的形式：

那么如果想得到这个可加模型的表达式，我们不妨就用刚刚学到的思想，从「零模型」开始逐步向前添加。

2.如何通过逐步向前方法得到可加模型？

它的思路非常简单，可以写成：

❝

第1步：写出零模型

第2步：通过准则判断，得到第一个自变量，并写成：

第3步：通过准则判断，在剩下的自变量中选一个最佳的，并写成：

第n步：同上思路继续判断

以此类推，直到收敛。

❞

那么，关键的问题就是：「判断准则是什么？」

这里，我们用到的就是「损失函数」的思想，对每个样本点都计算一下损失，然后选出损失最小的，它所对应的参数就是最优的，对应的每轮都是这样求出最优解，实现了「基函数的逐步添加」，搞定了可加模型。

叁 解读前向分步算法

1.前向分步算法解读

接着，我们就可以看懂什么是「前向分步算法」了，当然，说过很多次，既然是算法，那就肯定有输入和输出，我们不妨就来详细看看。

「输入：」训练数据集   ，损失函数 ，基函数集 。

如果是分类问题，「对于损失函数而言」，常用的是指数损失；「对于基函数集而言」，这里常见的是二叉树模型。

「输出：」加法模型 。

「步骤：」这个步骤可以简单分成三步走：

Step 1 初始化

令零模型

Step 2 对各个自变量求解损失函数

对 分别求出它的极小化损失函数：

估计出 和 。

从而得到下一个最优模型：

Step 3 得到加法模型

把每轮的模型加在一起就是这个最终的加法模型了，那么各位小伙伴有没有想过，为什么在「AdaBoost算法」 中我们采用的是前向分步算法而不是后向的呢？

「答案很简单」，因为大家要始终记得「AdaBoost算法」的核心思想是逐次提升，适应性相加的思想，正是逐步前向可加的思路呀。

不过，这也不妨碍各位小伙伴尝试一下向后回归或者逐步回归，没准你就能提出个新算法呢。

好啦，那么接着我们就看看「AdaBoost算法」和「加法模型」之间的联系。

2.AdaBoost算法和加法模型

这里我们得搬出前面【十分钟 机器学习 系列课程】讲义（55）：提升方法-AdaBoost算法的例题讲解，【十分钟 机器学习 系列课程】 讲义（56）:AdaBoost算法解读和权重内涵推导出的AdaBoost算法：

大家观察可以看出，这正是每轮加一个，目标是通过每轮得到 ，展开可以写成：

对应的，按照指数损失极小，找到每轮的 。

注意哦，这里蓝色的 既不依赖 也不依赖 ,所以和最小化无关，但是它会由每轮的 决定，随着迭代发生改变。

那么，在「前向分步算法」中是如何得到我们想要的 和 呢？

还是刚才那个式子:

如果想要实现下面的最小值，问题就在后面的指数，令它的最大值最小就可以，在这里我们知道 ，那么对于 的自然乘积为1，指数为负，是个小数，反之，对于 的乘积为-1，指数为正，就是大数了，那么可以写成：

「 就是第 轮加权训练数据分类误差率最小的基本分类器」。

接着，再来看看 同样的思路，我们可以利用求偏导得到：

其中 是分类误差率：

和我们用「AdaBoost算法」得到的 完全一致。

而根据 每轮的更新权重可以写成：

「由此我们就发现了，前向分步算法和AdaBoost算法在生成 、 、 上都一致」，因而等价~

好啦，这就是本期的「AdaBoost前向分步算法解读」，下期我们就开启提升树的内容，感兴趣的小伙伴们不见不散，另外也欢迎新朋友回复「入群」加入我们，我们下期再见！

欢迎大家关注简博士的B站和公众号，在公众号私信“入群”，可以与小伙伴们一起讨论问题哦。