西瓜书-AdaBoost

集成学习（ensemble learning）通过构建多个个体学习器并结合起来完成学习任务。

做一个简单分析，考虑二分类问题 ，假定基本分类器的错误率为 ,有

由基分类器相互独立，设X为T个基分类器分类正确的次数，因此

根据Hoeffding不等式 令 得

由上面的式子可以得到，个体分类器的数目越大。错误率将指数级下降，最终变为0。

要获得好的集成，个体学习器应该“好而不同”，要有一定的“准确性”，即学习器不能太坏，并且要有多样性，之间具有差异。互为补充，才可提升效果。而集成学习的难点就是如何获得“好而不同”的学习器。

根据个体学习器的生成方式，集成学习大致分为两类：

1. 个体学习器间有强依赖，必须串行生成的序列化方法。代表：AdaBoost
2. 个体学习器不存在强依赖，可并行生成方法。代表：Bagging和RandomForest

AdaBoost

直观解释层面

boosting 方法背后的直观想法是：

1. 我们需要串行训练模型，而不是并行训练。
2. 每个模型需要重点关注之前的分类器表现不佳的地方。

上述想法可以诠释为：

• 在整个数据集上训练模型 h1
• 对 h1 表现较差的区域的数据加权，并在这些数据上训练模型 h2
• 对 h1 ≠ h2 的区域的数据加权重，并在这些数据上训练模型 h3
• ...

加权误差

我们如何才能实现这样的分类器呢？实际上，我们是通过在整个迭代过程中加权误差做到的。这样，我们将为之前分类器表现较差的区域赋予更大的权重。

不妨想想二维图像上的数据点。有些点会被很好地分类，有些则不会。通常，在计算误差率时，每个误差的权重为 1/n，其中 n 是待分类的数据点个数。

现在让我们对误差进行加权！

现在，你可能注意到了，我们对没有被很好地分类的数据点赋予了更高的权重。加权的过程如下图所示：

最终，我们希望构建如下图所示的强分类器：

在每一轮迭代 t 中，我们将选择能够最好地划分数据的弱分类器 ht，该分类器能够最大限度地降低整体误差率。回想一下，这里的误差率是一个经过加权修正之后的误差率版本，它考虑到了前面介绍的内容。

寻找最佳划分

如上所述，通过在每轮迭代 t 中识别最佳弱分类器 ht（通常为具有 1 个节点和 2 片叶子的决策树（决策树桩））来找到最佳划分。假设我们试图预测一个想借钱的人是否会是一个好的还款人：

在这种情况下，t 时刻的最佳划分是将「支付历史」作为树桩，因为这种划分的加权误差是最小的。

只需注意，实际上，像这样的决策树分类器可能具备比简单的树桩更深的结构。这将会是一个超参数。

融合分类器

自然而然地，下一步就应该是将这些分类器融合成一个符号分类器。根据某个数据点处于分割线的哪一侧，将其分类为 0 或 1。该过程可以通过如下方式实现：

你发现了可能提升分类器性能的方法吗？

通过为每个分类器加权，可以避免赋予不同的分类器相同的重要性。

西瓜书理论推导

为什么使用指数损失函数

1. 先考虑指数损失函数 的含义,f为真实函数，对于样本x来说， 只能取和两个值，而 是一个实数； 当 的符号与 一致时, ，因此 ，且 大指数损失函数

（这很合理：此时 越大意味着分类器本身对预测结果的信心越大，损失应该越小；若 零附近，虽然预测正确，但表示分类器本身对预测结果信心很小，损失应该较大） 越小。

当 的符号与 不一致时， ，因此 ，且| H(\boldsymbol{x}) |∣H(x)∣越大指数损失函数越大（这很合理：此时 大意味着分类器本身对预测结果的信心越大，但预测结果是错的，因此损失应该越大；

若 在零附近，虽然预测错误，但表示分类器本身对预测结果信心很小，虽然错了，损失应该较小）

2. 符号 的含义： 为概率分布，可简单理解为在数据集 中进行一次随机抽样，每个样本被取到的概率, 为经典的期望，则综合起来 表示在概率分布 上的期望

显然sign(H(x))达到了贝叶斯最优错误率，换言之，若指数损失函数最小化，分类错误率也将最小化。这说明指数损失函数是原本0/1损失函数的一致性替代损失函数。它的优势是它是连续可微函数，因此我们替换它作为优化目标。

类似地，在AdaBoost算法中，第一个基分类器 是通过直接将基学习算法用于初始数据分布而得；此后迭代地生成 和

的一些错误，理想情况下h(t)能纠正所有错误。

所以下一轮的学习是看谁能最小化上一轮的调整后的权重分布，谁就是最合适的。

实例演示

最后还是看实例把内容串起来的，哎

参考自： zhuanlan.zhihu.com/p/27126737

例 给定如下表所示训练数据。假设个体学习器由x（输入）和y（输出）产生，其阈值v（判定正反例的分界线）使该分类器在训练数据集上分类误差率最低。（y=1为正例，y=-1为反例）