AdaBoost（Adaptive Boosting，自适应提升）算法由 Yoav Freund 和 Robert Schapire 于 1995 年提出，是一种能自动找出薄弱环节并不断改进的集体学习方法，是机器学习历史上具有里程碑意义的算法。它首次在理论上证明：即使是性能较弱的模型，只要经过合理的组合，也能形成一个强大的分类器。凭借简单而高效的设计，它在图像识别、医学诊断、金融风控等多个领域得到广泛应用。

Paper：https://link.intlpress.com/JDetail/1806634576447516674

1. 算法初识

训练过程：

1. 初始化：给所有训练样本分配相等权重
2. 训练弱学习器：根据当前样本的权重训练弱学习器
3. 调整样本权重：随后根据预测结果调整样本权重，提高错分样本权重、降低正确分类样本权重
4. 分配模型权重：为每个弱学习器赋予模型权重，分类误差越小的学习器，权重越高
5. 重复 2-4 步，直到满足停止条件

预测过程：

1. 每个弱学习器对输入样本的各类别分别打分
2. 将所有弱学习器的类别分数按各自模型权重加权求和
3. 得分最高的类别即为最终预测结果

重要概念：

• 核心思想：通过组合多个弱学习器，逐步提升整体分类性能，训练过程是串行的，每一轮都依赖上一轮的结果
• 样本权重机制：通过动态调整样本权重，让分类错误或难分的样本在下一轮获得更高关注度。
• 模型权重：每个弱学习器都被赋予一个模型权重，表示其重要性，权重越大，对最终预测影响越强
• 学习率：为了防止样本权重变化过大，影响训练稳定性，引入学习率参数，控制每次更新的幅度
• 预测方式：最终预测由所有弱学习器的加权投票得到
• 弱学习器选择：通常使用非常简单的模型，性能略优于随机猜测，能有效避免过拟合
• 算法版本：传统 AdaBoost 用于二分类，scikit-learn 中实现的是其多分类扩展版本 SAMME（Stagewise Additive Modeling using a Multi-class Exponential loss）

2. 损失函数

其中，\(\alpha_{t}\)​ 表示第 t 轮弱分类器的权重，\( h_{t}(x) \) 表示弱分类器输出，是一个 \( K \) 维的标签向量，\( F_{m}(x) \) 也是一个 \( K \) 维的向量，表示每个类别预测得分。

AdaBoost 的目标是最小化加权指数损失，上面的公式表示单个样本 \(x\) 的损失表示函数。这里需要注意的是，\( y^{T} \) 是一个使用对称编码的 \( K \) 维向量来表示的真实标签，使用下面公式表示：

其中 \( l \) 是真实类别，\( K \) 是类别总数。假设有 \( 3 \)个类别，标签 \( y \in {1, 2, \ldots, K} \)，标签 2 可示为 \( (-\frac{1}{2}, 1, -\frac{1}{2}) \) 向量。

上面公式表示弱学习器 \( m \) 的所有样本的总损失。

3. 模型权重

我们的优化目标是降低模型在所有样本上的总体损失，那么，我们得知道如何构建每一个弱学习器才能够降低损失，再具体一点，就是如何构建当前的弱学习器才能进一步降低整体的损失。而对于每个弱学习器而言，最重要的是得到弱学习器的权重表示。

在第 \( m \) 轮，我们已经训练了前 \( m-1 \) 轮的弱分类器，目标是通过选择适当的 \( \alpha_{m} \) 和 \( h_{m}(x) \) 来进一步降低损失。

我们的损失函数可以表示为：

我们设定 \( w_{i}(m) \) 表示在第 \( m \) 轮中样本 \( i \) 的权重。该权重反映了样本在当前弱学习器下的重要程度。权重越大，说明该样本如果在当前弱学习器被分错了，会带来较大的损失。

样本权重是由上一个弱学习器的预测结果来确定的。如果上一轮弱学习器预测错误，则样本的权重在下一轮中会相应增大。反之，若预测正确，权重会减小。这样，新的弱学习器在训练时会更加关注那些此前被错误分类的样本，从而逐步提升整体模型的分类性能。

损失函数是由分类正确的样本的损失、分类错误样本的损失构成，因此目标函数可以写成：

接下来，我们推导一下 \( y_{i}^{T}h_{m}(x_{i}) \) 在预测正确和错误时的结果是什么。假设预测正确，则真实标签和模型预测标签可以表示如下：

那么，如果预测错误的话：

把分类正确、分类错误时得到的公式代入原来损失函数，得到下面的公式：

再次明确：我们希望通过对损失函数的优化得到当前弱学习器的权重 \( \alpha_{m} \)，这是最重要的信息。接下来，对 \( \alpha_{m} \) 进行求导，并令导数为 0，再化简之后，得到下面的公式：

我们看到，分母表示错误样本的权重，这也表示当前弱学习器的加权错误率。我们用 \( err_{t} \) 来表示分母的加权错误率，则分子加权正确率可以表示为 \( 1- err_{t} \)。我们再把前面的系数 \( \frac{(K-1)^2}{K} \) 去掉，则得到模型的权重计算公式：

注意：上面公式中，错误率是未归一化后的样本权重。但在进行模型权重计算时，使用的样本权重必须归一化。

当本轮的弱学习器对样本预测错误时，我们希望根据当前弱学习器的权重提高样本的权重，使得下一个弱学习器训练时，着重关注该样本，给出了下面的样本权重更新公式：

4. 样本权重

可知，下次迭代的损失计算过程中，样本的权重计算应该为：

我们把前面得到的 \( y_{i}^{T}h_{m}(x_{i}) \) 代入到公式中，可得下一轮样本权重的更新公式（注意：这是未归一化的权重）：

我们让两者都乘以相同的常数 \( \exp\left(\frac{K-1}{K}\,\alpha_m\right) \)，则可得：

最后，对所有样本的权重进行归一化，即可得到下一轮训练的样本权重。

5. 决策函数

再回到最开始给的公式：

假设 3 分类情况下：\( h_{t}(x) \) 预测的类别是 \( (-\frac{1}{2}, 1, -\frac{1}{2}) \)，那么第 t 个弱学习器的打分为 \( (-\frac{\alpha}{2}, \alpha, -\frac{\alpha}{2}) \)，将多个弱学习器不同类别的打分加起来，就得到了加法模型+加权投票思想下的 AdaBoost 预测得分，最后选择分数最大的类别作为最终的预测结果。