【高中生讲机器学习】25. AdaBoost 算法详解+推导来啦！

创建时间：2024-11-08
首发时间：2024-11-13
最后编辑时间：2024-11-13
作者：Geeker_LStar

你好呀~这里是 Geeker_LStar 的人工智能学习专栏，很高兴遇见你~
我是 Geeker_LStar，一名高一学生，热爱计算机和数学，我们一起加油~！
⭐(●’◡’●) ⭐

hi!!! 上一篇开了个坑，大概介绍了一下集成学习。这篇我们来讲集成学习之 Boosting 中很经典的一个算法——AdaBoost!

AdaBoost 是 Boosting 的代表之一，so 它具有 Boosting 算法的各种共性，so 可以先大概了解一下 Boosting 再看 AdaBoost 噢!

启动！

主要思想

在上一篇中我们说过，Boosting 算法用那些过于简单的、欠拟合的学习器（模型）作为基学习器，以串行的方式对这些基学习器进行组合，以获得性能更好的模型。Boosting 算法旨在解决基学习器高偏差的问题。

这里放一张图来复习一下 Boosting，尤其是它的 “串行”：

remember，在 Boosting 中，每个基学习器都是在前一个基学习器的基础上生成的，这个基准会贯穿整篇文章（或者说关于 Boosting 的所有文章）。

嗯，从 Boosting 的主要思想出发，很自然地就有以下这两个问题：

第一，选择什么模型作为弱学习器？
第二，怎样组合这些弱学习器？

第二个问题又可以引出更多的问题：每个弱学习器拥有一样的权重吗？每个弱学习器学习的数据是相同的吗？组合到什么时候算结束呢？…

上面这些都是 AdaBoost，或者说 Boosting 家族的算法的核心问题。Boosting 家族为什么有不同的算法呢？因为这些问题可以有很多种答案。

可以说，Boosting 家族的每一种算法都给出了对以上问题的不同回答，搞懂了这几个问题，对应的算法也就搞明白啦！

嗯！那我们就从 adaboost 开始吧嘿嘿嘿。（eeea 原谅我真的懒得每次都把 A 和 B 大写（（（

首先，对于第一个问题，adaboost 选择决策树桩作为基学习器，决策树桩就是只有一个根节点和两个子节点的决策树，这在决策树那篇当中我讲过。

为什么这么选呢？因为决策树桩简单，它一定是个高偏差的模型，这非常符合 boosting 的口味。boosting 就是要选择那些欠拟合的学习器作为基学习器。

接下来是第二个问题，或者说是一系列问题——怎样组合这些基学习器？

在这里先给个概括：adaboost 算法串行生成每个基学习器，相同的样本在每个基学习器上有不同的权重，每个基学习器本身也有不同的权重，这些权重都是可量化的。

可以细化为以下三点：

• 关于串行：后一个基学习器是在前一个基学习器的基础上生成的。

• 关于样本权重：在前一个基学习器上产生较高损失的样本会被后一个基学习器赋予更高的权重；换言之，后一个基学习器会更关注在前一个基学习器上产生较高损失的样本。

• 关于基学习器权重：在最终的基学习器组合中，每个基学习器拥有不同的权重。性能越好（表现为损失函数越小）的基学习器会获得更高的权重。

这些都是很直观的想法，adaboost 之所以好用，或许就是因为它把这些很直观的想法们结合在了一起。

adaboost 既可以用于分类（二分类 & 多分类），也可以用于回归。后面我将以分类问题为例叙述 adaboost 的各种操作，然后提一下如果是回归问题，在各个步骤上应该做什么样的修改。

（其实也就损失函数会有差别啦，别的地方的差别都很小。

我们先来看 adaboost 算法的数学表述，其中包含了更多细节。

正向解释：数学叙述

这一部分中，我们以二分类为例，展示 adaboost 算法的数学表示。

首先还是来规定一些 notation。

我们有一个包含 $N$ 个样本的二分类数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中 y i ∈ { + 1 , − 1 } y_i \in \{+1, -1\} yi​∈{+1,−1}。
在这个数据集的基础上，我们会训练 $M$ 个基学习器 $m_1,m_2,...,m_M$，每个基学习器的权重记作 ${\alpha }_1,{\alpha }_2,...,{\alpha }_M$，数据集中第 $n$ 个样本 $x_i$ 在第 $m$ 个基学习器上的权重记作 $w_{m,n}$.

emmm 感觉把这些符号写在一起有点让人头大（）。

okay，现在我们从第一轮，或者说第一个基学习器开始。

在第一轮中，所有的样本拥有相同的权重，即：
$$w_{1,n}=\frac{1}{N},n=1,2,...,N$$

根据目前的数据，我们找到最优基学习器 $G_1(x)$。
最优基学习器怎么找呢？当然是最小化损失函数啦，如下：
$$G_1(x)=\underset{G}{\mathrm{argmin}}\sum _{i=1}^N{w}_{1,i}I(y_i\ne G(x_i))$$

其中 $w_{1,i}$ 为第 $i$ 个样本 $x_i$ 在第 1 个基学习器上的权重，$I$ 是指示函数，当括号内条件成立，即 $y_i\ne G(x_i)$ 时，指示函数值为 1，否则为 0。

也就是说，当基学习器预测的标签和真实标签不同时，损失为它的权重，否则为 0.

注意，因为这里我们使用的是分类损失中的 0-1 损失（这里多了个加权），同时我们默认的基学习器（决策树桩）是一个非参数模型，所以这个损失函数没有办法写成参数的形式，也就是说，我们不能通过数值优化算法来求解这个损失函数。

在实际实现中，adaboost（决策树桩）会尝试所有可能的分裂特征，并选出让损失函数最小的那个，没有显式的数值优化过程。

嗯，在这里补充一下，当问题是回归问题，我们要找的模型是一个可参数化的回归模型（比如线性回归 $y={\beta }^{T}x$）的时候的情况。

这个时候，前面的权重不变，但是后面就不再是指示函数了。如果我们采用平方损失作为损失函数，后面的部分就变成：
$$(y_i-G(x_i){)}^2$$

那么，整个式子就变成：
$$\begin{gathered} G_1^{\ast }(x)=\underset{G}{\mathrm{argmin}}\sum _{i=1}^N{w}_{1,i}(y_i-G(x_i){)}^2 \\ =\underset{\beta }{\mathrm{argmin}}\sum _{i=1}^N{w}_{1,i}(y_i-{\beta }^T{x}_i{)}^2 \end{gathered}$$

这种情况下，我们就可以显式地使用数值优化算法求解啦！

en!! 现在我们可以大致理解这个 “权重” 是怎么起作用的了——对于每个样本，如果它被分类错误了，产生的损失是它的权重。这就迫使模型更关注那些权重大的样本，争取把它们都分类正确，以获得更小的损失。

用一张图来解释：

图中，被第一个基学习器分类错误的样本在第二个基学习器那里获得了更高的权重，第二个基学习器会更注重把它们分类正确，以此类推。

嗯，现在假设我们找到了最优基学习器（决策树桩）$G_1(x)$。接下来，我们要用它对样本进行分类，并计算分类错误率。

错误率的计算和损失的计算是一样的，换句话说，我们找到的损失最小的基学习器也就是错误率最小的基学习器，在这个语境下两者是等价的。

第一个基学习器的错误率 $e_1$ 为：
$$e_1=\sum _{i=1}^N{w}_{1,i}I(y_i\ne G(x_i))$$

然后，根据这个错误率，我们计算第一个模型的权重。
前面说过，adaboost 很聪明，它会给那些错误率低的模型赋予更高的权重。这种量化是通过对数函数定义的，公式如下。
$${\alpha }_1=\frac{1}{2}\log \frac{1-e_1}{e_1}$$

我们直接来看图像吧，这是 $\alpha$ 和 $e$ 的关系图，横轴代表 $e,0<e<1$，纵轴代表 $\alpha$。

可以看到，函数是单调递减的，$e$ 越小，相应的 $\alpha$ 就越大。

嗯不过我们这里要注意一件事。即，在通常情况下，弱学习器的错误率都会小于 0.5，也就是说弱学习器的性能再怎么差也会比随即猜测好。在这个前提下，弱学习器的权重总是大于 0 的，这一点也可以从图上看出来（当 $e>0.5$ 时，$\alpha >0$）。

emm 那么，如果真的出现了某个弱学习器的性能比随即猜测差的情况呢（虽然几乎不会出现）？
well，那这个弱学习器的权重就会变成负值了。也就是说，这个弱学习器在整个模型中的
这也很好理解，如果弱学习器的准确率小于 0.5，那我们只要和它反着来（也就是权重为负数），就可以获得大于 0.5 的准确率了。

举个不恰当的例子，这就像你 “借鉴” 其他同学的作业（咳咳），如果有个同学很不靠谱，错的题总是比对的多，那这个时候，没有被这位同学选择的那些选项反而有可能是正确选项。换言之，这位同学可能不太能告诉你什么是正确答案，但是可以帮助你避开一些错误答案（（（咳咳为什么我会对借鉴作业这么了解（bushi

嗯，现在我们已经获得了第一个模型的权重 ${\alpha }_1$，模型权重这块处理完了，接下来要处理样本权重了。

前面说过，如果某个样本被上一个弱学习器分类错误，adaboost 会加大它在下一个弱学习器中的权重；相反地，如果某个样本被上一个弱学习器分类正确，adaboost 会减小它在下一个弱学习器中的权重。

在实际实现中，样本权重的更新和模型权重是密切相关的，我们还是来看式子，这个式子表示了所有样本在第二个基学习器上的权重。
$$w_{2,i}=\frac{w_{1,i}}{Z(w_1)}\exp (-{\alpha }_1{y}_i{G}_1(x_i))$$

well 乍一看这个式子有点复杂诶，没事我们分开来看，分别看当基学习器预测正确和预测错误的时候，样本权重的变化。

首先是基学习器预测正确的时候，此时 $y_i$ 和 $G_1(x_i)$ 同号，即 $y_i{G}_1(x_i)=1$，那么我们有：
$$w_{2,i}=\frac{w_{1,i}}{Z(w_1)}\exp (-{\alpha }_1{y}_i{G}_1(x_i))=\frac{w_{1,i}}{Z(w_1)}\exp (-\alpha )$$

前面说过，通常而言 $\alpha$ 的值为正，那么 $-\alpha$ 的值为负。此时 $\exp (-\alpha )$ 的值小于 1，即 $w_{2,i}=w_{1,i}\exp (-\alpha )<w_{1,i}$，也就是说这个样本的权重变小了。
（先不用管 $Z(w_1)$ 是什么，后面会说到）

相应的，当基学习器预测错误的时候，此时 $y_i$ 和 $G_1(x_i)$ 异号，即 $y_i{G}_1(x_i)=-1$，我们有：
$$w_{2,i}=\frac{w_{1,i}}{Z(w_1)}\exp (-{\alpha }_1{y}_i{G}_1(x_i))=\frac{w_{1,i}}{Z(w_1)}\exp (\alpha )$$

我们有 $\exp (\alpha )>1$，即 $w_{2,i}=w_{1,i}\exp (\alpha )>w_{1,i}$，样本的权重变大了。

o 对了，这里还有一个点就是，$\alpha$ 越大，或者说，基学习器的性能越好，被它分类错误的样本在下一轮中获得权重（增量）就会越大。这也非常符合直觉——那些被很好的模型分类错误的点通常比那些性能一般的模型分类错误的点需要更多的关注，因为它们更难被分类正确（就像通常而言，学霸错的题是更难的题一样）。所以，在同样是被分类错误的情况下，如果这个点是被一个性能很好的模型分类错误的，它的权重增加量会比它被一个一般的模型分类错误的时候的权重增加量更多。

嗯，现在我们来看一下 $Z(w_1)$。它只是用于归一化的配分函数，对样本权重间的大小关系没有影响，我们在最大熵那一篇中见到过它。在这里 $Z(w_1)$ 的表达式如下：
$$Z(w_1)=\sum _{i=1}^N{w}_{1,i}\exp (-{\alpha }_1{y}_i{G}_1(x_i))$$

nice!! 现在我们得到了样本在第二个基学习器上的权重 $w_{2,i}$，可以按照相同的流程往下做啦！我就不一轮一轮写了，这里给出一个流程概括。

首先，在经过第 $m-1$ 个基学习器后，第 $i$ 个样本 $x_i$ 的权重可以用 $w_{w,i}$ 表示，这代表了 $x_i$ 在第 $m$ 个基学习器上的权重。

根据现有数据及权重，我们最小化如下损失函数，得到最优基学习器 $G_m(x)$：
$$G_m(x)=\underset{G}{\mathrm{argmin}}\sum _{i=1}^N{w}_{m,i}I(y_i\ne G(x_i))$$

计算 $G_m(x)$ 的错误率 $e_m$：
$$e_m=\sum _{i=1}^N{w}_{m,i}I(y_i\ne G(x_i))$$

根据错误率计算 $G_m(x)$ 的权重 ${\alpha }_m$：
$${\alpha }_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$$

得到 ${\alpha }_m$ 后，更新每个样本点的权重：
$$w_{m+1,i}=\frac{w_{m,i}}{Z(w_m)}\exp (-{\alpha }_m{y}_i{G}_m(x_i))$$

最终，我们得到了 $M$ 个基学习器的线性组合，也就是我们最终需要的强学习器 $G(x)$!
$$G(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$

好耶！！

嗯！那么这部分就到这里吧，我觉得你现在应该对 AdaBoost 算法有一个比较全面的了解啦！

接下来，我们来看一些更有趣的东西…

逆向解释：前向分布算法

上一个部分中，我们正向梳理了一遍 adaboost 算法的流程和数学表示。一切看上去都很合理也很简洁。（点头）

诶但是你有没有好奇，这么合理的东西是怎么来的？举个例子，为什么 ${\alpha }_m$ 一定等于 $\frac{1}{2}\log \frac{1-e_m}{e_m}$？因为它单调递增吗？但满足单调递增性质的函数也不止它一个吧。

在上上一篇中，我们最终推出来，逻辑回归算法是最大熵模型的一个特例，当我们选择某个特定的特征函数的时候，最大熵算法等价于逻辑回归算法。

这篇文章和那篇文章，在这个点上，简直太像了!

没错，我们后面马上就会说到，adaboost 算法也是一个算法的特例，这个算法就是——前向分布算法!（emmm 诶其实这部分的小标题是不是已经暴露了这件事情（）

（o对了那篇文章在这里：23. 最大熵模型详解+推导来啦！解决 why sigmoid！

我们先来看看前向分布算法吧。

前向分步算法

前向分步算法，说的更具体一点，前向分步加法算法，可以看作一种分步优化算法。用一句话概括就是，它把一个【需要一次性完成的】复杂优化问题拆解成了很多个【可以分步完成的】简单优化问题；它分步完成这些简单优化问题，并用最终的结果近似原始的复杂优化问题。

emmm 似乎没有什么很好的例子，so 我们直接来看数学表述吧（）不过也并没有很复杂啦。

还是一样的数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$.

考虑如下所示的加法模型，它其实是一个模型，但是由很多个不同的模型（基学习器）构成：
$$f(x)=\sum _{m=1}^M{\beta }_{m}b(x,{\gamma }_m)$$

展开来写就是：
$$f(x)={\beta }_{1}b(x,{\gamma }_1)+{\beta }_{2}b(x,{\gamma }_2)+...+{\beta }_{M}b(x,{\gamma }_M)$$

解释一下参数，${\beta }_m$ 代表第 $m$ 个模型的权重，$x$ 代表输入数据，${\gamma }_m$ 代表第 $m$ 个模型的参数。
注意o，$b$ 不一定是线性模型，${\gamma }_m$ 决定了它是什么模型（实际上，它可以是任何模型，在 adaboost 中，它通常是决策树桩）。

注意我们现在写的是对于某个特定的 $x$ 的 $f(x)$，在真实的数据集中还需要加一个 ${\sum }_{i=1}^N$ 来遍历整个数据集。

嗯，我们现在的任务就是找到最优参数 β = { β 1 , β 2 , . . . , β M } \beta=\{\beta_1, \beta_2, ..., \beta_M\} β={β1​,β2​,...,βM​} 和 γ = { γ 1 , γ 2 , . . . , γ M } \gamma=\{\gamma_1, \gamma_2, ..., \gamma_M\} γ={γ1​,γ2​,...,γM​}，这是一个多元优化问题。它的损失函数长成下面这个样子，

$$\text{Loss}=\sum _{i=1}^N\mathcal{L}(y_i,\sum _{m=1}^M{\beta }_{m}b(x_i,{\gamma }_m))$$

其中 $y_i$ 是 $x_i$ 对应的正确标签，其它参数已经解释过了。

我们的目的就是最小化这个损失函数。

em…这怎么办？或者说，这能怎么办？？？这个问题太复杂了。
我们需要一些让它变简单的方法。

前向分步算法给出了一种思路——既然不能一次求出所有的，那我一次求一个，再把所有次的加起来，总可以了吧？

好耶！我们来试试这种方法。

首先我们需要设置 $f(0)$，显然开始的时候什么都没有，所以 $f(0)=0$。
then 还是从第一次开始，往后推。

第一个模型的权重为 ${\beta }_1$，参数为 ${\gamma }_1$，我们的损失函数是：
$$\text{Loss}=\sum _{i=1}^N\mathcal{L}(y_i,f_0(x_i)+{\beta }_{1}b(x_i,{\gamma }_1))$$

嗯，可以看到，我们在最开始的什么也没有的模型 $f(0)$ 的基础上添加了一个模型 ${\beta }_{1}b(x_i,{\gamma }_1)$。

然后，我们把参数 ${\beta }_1$ 和 ${\gamma }_1$ 解出来，如下。em 因为在这里我们没有规定具体的损失函数，所以没法写具体的求解过程。
（提前剧透一下，改变这个损失函数，我们能够得到前向分步算法不同的特例，本篇的主角 adaboost 就是其一…啊不过这就是下一个话题了（））
$${\beta }_1,{\gamma }_1=\underset{\beta ,\gamma }{\mathrm{argmin}}\sum _{i=1}^N\mathcal{L}(y_i,f_0(x_i)+\beta b(x_i,\gamma ))$$

豪德，现在我们更新 $f(x)$：$f_1(x)=f_0(x)+{\beta }_{1}b(x_i,{\gamma }_1)$。说白了就是，我们把新求解得到的模型加到最开始的什么也没有的模型上。（remember? “加法模型”。

then，我们再往下写一轮，然后你估计就明白啦!

现在我们已经得到 $f_1(x)$ 了，接着我们要求解参数 ${\beta }_2,{\gamma }_2$.
这次，我们的损失函数是：
$$\text{Loss}=\sum _{i=1}^N\mathcal{L}(y_i,f_1(x_i)+{\beta }_{2}b(x_i,{\gamma }_2))$$

和最开始的是一个道理，我们想要把新的模型加到已有的模型上，形成一个新的整体，并且最小化这个整体的损失函数。
eeaaa 加法模型顾名思义就是这样嘛，挨个加起来。
（有点 resnet 那味了，不过还不够 “正宗”，下一篇讲提升树会有更重的 resnet 味哈哈哈哈哈哈）

emm，然后，我们把这个求解得到的参数写一下：
$${\beta }_2,{\gamma }_2=\underset{\beta ,\gamma }{\mathrm{argmin}}\sum _{i=1}^N\mathcal{L}(y_i,f_1(x_i)+\beta b(x_i,\gamma ))$$

嘿，我感觉你应该已经完全明白了!’

那么，对于第 $m$ 个模型，它的参数 ${\beta }_m,{\gamma }_m$ 就可以写成：
$${\beta }_m,{\gamma }_m=\underset{\beta ,\gamma }{\mathrm{argmin}}\sum _{i=1}^N\mathcal{L}(y_i,f_{m-1}(x)+\beta b(x_i,\gamma ))$$

其实本质上就是每次在已有模型的基础上再添加一个模型，形成新的整体，并让这个整体的损失函数最小，以求出新加的模型的参数。

最终，在我们累加完了所有 $M$ 个模型之后，我们就得到了最终的 $f(x)$，这个结果可以用于近似 “一次性优化”，也就是求解 ${\sum }_{i=1}^N\mathcal{L}(y_i,{\sum }_{m=1}^M{\beta }_{m}b(x_i,{\gamma }_m))$ 得到的结果，同时它大大减少了计算量。

在这里放一下我突然冒出来的想法：前向分步算法就像是把一个 $1\ast n$ 的行向量拆了再拼，拼成一个 $n\ast 1$ 的列向量，其中每一行代表一个优化问题，每一列代表一对参数。（eeemmm 这是个很奇怪的说法，如果你感觉很绕，不用管它，希望我过一段时间之后再看这篇文章的时候能够想起来我现在是怎么想的（（（但我又觉得其实这是个非常好的比喻）🤯

好耶！！这些就是前向分步算法的介绍啦！我感觉铺垫已经很充分了其实，接下来我们来看看，为什么说 adaboost 是前向分步算法的特例？从前向分步算法是怎么推出 adaboost 中的各个参数和它们的值的？

AdaBoost 特例

呃嗷嗷嗷（什么奇怪的拟声词/。。），在这一部分里，我们来回答上一部分末尾提出的问题——既然说 adaboost 是前向分步算法的特例，那它是怎么从前向分步算法推导出来的呢？

还是先放结论：当前向分步算法的损失函数为指数损失函数时，就是 adaboost 算法。

下面我们来一步步说明这件事情！

首先先说一下指数损失函数，公式如下：
$$\mathcal{L}=\exp (-y_{i}f(x))$$

其中 $y_i$ 是正确的标签（1 或 -1），$f(x)$ 是模型的输出。

现在我们假设，经过 $m-1$ 轮前向迭代，我们已经得到了 $f_{m-1}(x)$，展开如下：
$$f_{m-1}(x)={\alpha }_1{G}_1(x)+{\alpha }_2{G}_2(x)+...+{\alpha }_{m-1}{G}_{m-1}(x)$$

按照前向分步模型的一般流程，我们现在要添加第 $m$ 个模型了，它可以表示为：
$${\alpha }_m{G}_m(x)$$

注意这里的表示和前向分步算法介绍那块的表述稍有不同，介绍那里我们写的是 ${\beta }_{m}b(x,{\gamma }_m)$，其中 ${\gamma }_m$ 为参数。
但是因为 adaboost 中的基学习器（决策树桩）是个非参数模型，所以我们在这里直接写成 $G_m(x)$，省略了参数部分，后面求解的时候也没有显式的数值优化求解参数的过程。

（emm 其实类似的我在上面已经说过一遍了，在那里我补充了回归问题的情况，在这里也是一样的，就不再展开叙述了。如果你忘记了或者感觉不太明白，可以回到上面看一看~）

那么，把这个新模型（基学习器）加到已有的模型 $f_{m-1}$ 上，按照前向分步算法，我们得到了这一轮的优化问题：
$${\alpha }_m,G_m(x)=\underset{\alpha ,G}{\mathrm{argmin}}\sum _{i=1}^N\mathcal{L}(y_i,f_{m-1}(x)+\alpha G(x))$$

嗯，我们规定函数 $\mathcal{L}$ 为指数损失函数，那么这一轮的优化问题就是：
$${\alpha }_m,G_m(x)=\underset{\alpha ,G}{\mathrm{argmin}}\sum _{i=1}^N\exp [-y_i(f_{m-1}(x)+\alpha G(x)\left)\right]$$

现在我们来对它做一些小小的变形…
a 其实非常简单（），我们按照 $\exp$ 的计算方式把这个式子拆开：
$$\begin{gathered} {\alpha }_m,G_m(x)=\underset{\alpha ,G}{\mathrm{argmin}}\sum _{i=1}^N\exp \left[\right(-y_i{f}_{m-1}(x_i))+(-y_i\alpha G(x_i)\left)\right] \\ =\underset{\alpha ,G}{\mathrm{argmin}}\sum _{i=1}^N\left[\exp \right(-y_i{f}_{m-1}(x_i)\left)\exp \right(-y_i\alpha G(x_i)\left)\right] \end{gathered}$$

很简单的指数的运算法则。
接下来，我们把前面那个很长的 $\exp$ 用 $w_{m,i}$ 表示，即：
$${\overline{w}}_{m,i}=\exp (-y_i{f}_{m-1}(x_i))$$

我们发现，$w_{m,i}$ 和整个优化问题无关，因为它已经是定值了。式子可以重写为：
$$\underset{\alpha ,G}{\mathrm{argmin}}\sum _{i=1}^N{\overline{w}}_{m,i}\exp (-y_i\alpha G(x_i))$$

不错，现在 $\exp$ 里少了很多干扰项，只剩下我们要求的 $\alpha$ 和 $G(x)$ 了。

我们在这里停一下。
首先，我们看看 ${\overline{w}}_{m,i}$ 的表达式，它等于 $\exp (-y_i{\alpha }_{m-1}{G}_{m-1}(x_i))$.
你会发现，诶这怎么感觉和 adaboost 里的 $w_{m,i}$ 没什么关系呀？

先别着急，往后看，样本权重这块的重点是它的更新公式，而不是它自己长什么样子。
（另外，注意，这里的 $\overline{w}$ 上面有个短横线，注意区分o~）

继续继续，我们来最小化这个式子…

最小化这个式子是一件相对容易的事情，因为 $\alpha$ 和 $G(x)$ 之间没有关系，所以我们可以分别求解它们。

我们得到，使得整个式子最小的 $G(x)$ 如下：
$$G_m(x)=\underset{G}{\mathrm{argmin}}\sum _{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i))$$

它就是让加权分类损失最小的模型。注意在求解 $G(x)$ 的时候，我们不用考虑 $\alpha$，它对于求解而言只是一个常数。
其中 $w_{m,i}$ 就是我们之前从 $\exp$ 中提出去的那部分。

还是再强调一下，你可能会对这个结论的得出感觉有点困惑——怎么直接就得出模型了？都没有一个求解的过程吗？

well，这又回到了决策树桩是个非参数化模型这件事了，对于非参数化模型，我们没有一个显式的求解过程。如果你对这块依然感到困惑，我在这简单补充一个用平方损失作为损失函数的例子（此时得到的模型用于回归问题），这个或许会更好理解一点。

【注意，这部分可能有点 distract，可以跳过不看，或者最后再回来看】

当前向分步算法的损失函数为平方损失时，拟合的模型为回归模型的时候，即：
$${\alpha }_m,G_m(x)=\underset{\alpha ,G}{\mathrm{argmin}}\sum _{i=1}^N(y_i-f_{m-1}(x_i)-\alpha G(x_i){)}^2$$

嗯…在这个式子中，我们就可以通过梯度下降等数值优化方法来求最优权重 $\alpha$ 和最优模型 $G$ 了。

关于这个部分更详细的叙述…其实会在下一篇!!! 到时候再说吧！这里就不剧透太多了嘿嘿。

【插入部分结束，回到正题】

嗯，现在我们已经得到了 $G_m(x)$，接下来求解 ${\alpha }_m$。
$$\underset{\alpha ,G}{\mathrm{argmin}}\sum _{i=1}^N{\overline{w}}_{m,i}\exp (-y_i\alpha G(x_i))$$

我们可以把整个式子分成两部分：$y_i=G_m(x_i)$ 的部分和 $y_i\ne G_m(x_i)$ 的部分。
展开写成：
$$\sum _{i=1}^N{\overline{w}}_{m,i}\exp (-y_i\alpha G(x_i))=\sum _{y_i=G_m(x_i)}{\overline{w}}_{m,i}{e}^{-\alpha }+\sum _{y_i\ne G_m(x_i)}{\overline{w}}_{m,i}{e}^{\alpha }$$

上面的变形中，我们把 $\exp$ 写成了 $e$，根据计算结果 1 或 -1 省略掉了 $y_i=G_m(x_i)$，符号被保留在了 $\alpha$ 上。

我们再做一个恒等变形，因为所有的 $e^{\alpha }$ 和 $e^{-\alpha }$ 相对 $\sum$ 而言都是常数（它们都不包含 $i$），我们可以直接把它们提出来；同时，写在 $\sum$ 下面的 $y_i=G_m(x_i),y_i\ne G_m(x_i)$ 也可以变成指示函数的形式，因为指示函数只有在条件成立时为 1，所以两者是等价的。具体公式如下：
$$\begin{gathered} \text{above}=e^{-\alpha }\sum _{y_i=G_m(x_i)}{\overline{w}}_{m,i}+e^{\alpha }\sum _{y_i\ne G_m(x_i)}{\overline{w}}_{m,i} \\ =e^{-\alpha }\sum _{i=1}^N{\overline{w}}_{m,i}I(y_i=G(x_i))+e^{\alpha }\sum _{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i)) \\ =e^{-\alpha }(\sum _{i=1}^N{\overline{w}}_{m,i}-\sum _{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i)))+e^{\alpha }\sum _{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i)) \end{gathered}$$

注意现在 $G_m(x_i)$ 已经是已知的了。接下来对 $\alpha$ 求解偏导，所有 $\sum$ 都可以看作常数（系数）。
emm 是不是感觉这个系数好像有点太长了（）我们不如先用 $A,B$ 代替，即原式变为：
$$e^{-\alpha }A+e^{\alpha }B$$

其中：
$$A=\sum _{i=1}^N{\overline{w}}_{m,i}-\sum _{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i)),B=\sum _{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i))$$

这下看着顺眼多了，求解偏导得到：
$$\frac{\partial (e^{-\alpha }A+e^{\alpha }B)}{\partial \alpha }=-A{e}^{-\alpha }+B{e}^{\alpha }$$

我们让这个偏导等于 0：
$$\begin{gathered} -A{e}^{-\alpha }+B{e}^{\alpha }=0 \\ \to A{e}^{-\alpha }=B{e}^{\alpha } \\ \to \frac{A}{B}=\frac{e^{\alpha }}{e^{-\alpha }}=e^{2\alpha } \end{gathered}$$

我们最终要求的是 $\alpha$ 的值，所以对两边同时以 $e$ 为底取对数：
$$\begin{gathered} \log \frac{A}{B}=2\alpha \\ \to \alpha =\frac{1}{2}\log \frac{A}{B} \end{gathered}$$

嗯!! 这就是令原式偏导数为 0 得到的 $\alpha$ 值！也就是最优的 $\alpha$ 值啦!!（是不是还蛮简单的嘿嘿嘿）

我们把 $A,B$ 带进去，得到：
$$\alpha =\frac{1}{2}\log \frac{{\sum }_{i=1}^N{\overline{w}}_{m,i}-{\sum }_{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i))}{{\sum }_{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i))}$$

eeeenn 快要结束了但还差一点（）
我们把 $\log$ 里的公式上下同除 ${\sum }_{i=1}^N$，相当于做个归一化，很显然这不改变式子最终的值，即：
$$\begin{gathered} \text{above}=\frac{1}{2}\log \frac{\frac{{\sum }_{i=1}^N{\overline{w}}_{m,i}-{\sum }_{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i))}{{\sum }_{i=1}^N{\overline{w}}_{m,i}}}{\frac{{\sum }_{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i))}{{\sum }_{i=1}^N{\overline{w}}_{m,i}}} \\ =\frac{1}{2}\log \frac{1-\frac{{\sum }_{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i))}{{\sum }_{i=1}^N{\overline{w}}_{m,i}}}{\frac{{\sum }_{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G(x_i))}{{\sum }_{i=1}^N{\overline{w}}_{m,i}}} \end{gathered}$$

嗯，，，这个式子有点复杂，我们换个元：
$$\begin{gathered} e_m=\frac{{\sum }_{i=1}^N{\overline{w}}_{m,i}I(y_i\ne G_m(x_i))}{{\sum }_{i=1}^N{\overline{w}}_{m,i}} \\ =\sum _{i=1}^N{w}_{m,i}I(y_i\ne G_m(x_i)) \end{gathered}$$

$e_m$ 就等于原来的分数的分母和分子减号后面的部分。
这样的话，我们的权重 $a_m$ 就可以改写成：
$$a_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$$

嘿！看到了吗？这和我们前面正向叙述那里写的一模一样!

好啊…总算是推出来了!!! 现在 $e_m$ 和 $a_m$ 我们都有啦！还剩下一个 $w_{m,i}$…

不过现在它就很好处理了。

回忆一下，前向分步算法的模型更新公式是什么来着？前面说过，每次都会把新求出来的模型加到前面已经得到的所有模型上，即：
$$f_m(x)=f_{m-1}(x)+{\alpha }_m{G}_m(x)$$

其中 ${\alpha }_m$ 和 $G_m(x)$ 我们已经求出来了，和 adaboost 中是一样的形式。

我们之前，在一个有点远又不太远的地方得到了 ${\overline{w}}_{m,i}=\exp (-y_i{f}_{m-1}(x_i))$，根据指数的运算法则，我们有：
$$\begin{gathered} \exp (f_m(x))=\exp (f_{m-1}(x))\ast \exp ({\alpha }_m{G}_m(x)) \\ \to \exp (-y_i{f}_m(x))=\exp (-y_i{f}_{m-1}(x))\ast \exp (-y_i{\alpha }_m{G}_m(x)) \\ \to {\overline{w}}_{m+1,i}={\overline{w}}_{m,i}\exp (-y_i{\alpha }_m{G}_m(x)) \end{gathered}$$

嘿!!! 这和 adaboost 算法中的样本权重更新公式几乎一样诶！

或者说，这和 adaboost 算法中的样本权重更新公式相差一个归一化，so 只要在两边同时归一化就可以了，两者是等价的!

这样的话，我们已经从前向分步算法推导出了 adaboost 中的 $w_m,a_m,e_m$ 啦！

嗯！！现在我们已经完整地从前向分步算法推导出 adaboost 算法啦！完结撒花!!

总结

最后，我们来总结一下 adaboost 算法吧！

adaboost 算法属于 boosting 家族，通过加权组合多个弱学习器的方式进行决策，注重解决弱学习器高偏差的问题。

adaboost 在寻找新的基学习器时，会提高那些被上一个基学习器分类错误的样本的权重，迫使新的基学习器更关注这些样本。
在组合基学习器时，adaboost 会赋予那些性能较好的基学习器更高的权重。
adaboost 算法可以从前向分步算法推导得出，它是前向分步算法的损失函数为指数损失函数时的特殊情况。

嗯!! 核心内容就这些！！q(≧▽≦q)

放一张蛮不错的图作为结尾吧!

---

嘿嘿，那这一篇就到这里啦~~下一篇再见！下一篇我估计会讲梯度提升树 GBDT!!

这篇文章详解了 AdaBoost 算法，并从前向分步算法的角度给出了推导，希望对你有所帮助！⭐
欢迎三连！！一起加油！🎇
——Geeker_LStar