Boosting 算法

1. AdaBoost 简介

AdaBoost (Adaptive Boosting) 是一种用于分类或回归的集成方法。它具有如下的特点：

它通过不断关注之前被错分的样本来提升模型的拟合能力，从而降低偏差。这一点与随机森林等主要减少方差的集成方法不同。
与 Bagging 类似，它也对训练样本进行加权，但权重在每次迭代中都会动态调整。
每个弱学习器训练时样本的权重都是不同的。
增加被错误分类的训练点的权重：这是 AdaBoost 的核心机制。如果一个样本被当前的学习器搞错了，那么在训练下一个学习器时，这个样本的权重就会变大，让下一个学习器更加关注这个难点。
在最终做决策时，表现好的（错误率低的）学习器有更大的发言权。

它的核心流程如下：

训练 $T$ 个分类器：AdaBoost 依次训练出一系列的弱分类器 $G_1, G_2, ..., G_T$ 。（这里的 $T$ 通常代表 "Trees"，因为决策树是 AdaBoost 最常用的弱学习器）。
动态调整样本权重：训练第 $t$ 个分类器 $G_t$ 时，训练样本 $X_i$ 的权重取决于它被前面 $t-1$ 个分类器 $G_1, ..., G_{t-1}$ 错分了多少次。如果一个样本 $X_i$ 被一个非常准确的弱学习器错分了，它的权重会增加得更多；反之则会减少。
训练弱学习器 $G_t$ ： $G_t$ 的训练目标是，在当前样本权重分布下，尽可能地把样本（尤其是权重大的样本）分类正确。

最终我们获得强分类器 $M(z)$ 是所有弱学习器的加权线性组合。对于一个测试点 $z$ ，最终的预测结果由 $M(z) = \sum \beta _t G_t(z)$ 的符号决定，其中 $G_t(z)$ 的输出是 +1 或 -1， $β_t$ 是第 $t$ 个弱学习器的权重（投票权）。 $M(z)$ 是一个连续值，最终的分类结果是 $\text{sign}(M(z))$ 。

我们经常使用决策树来作为弱分类器的理由如下：

可靠地减少偏差：Boosting 能稳定地降低偏差。使用“不纯”的短决策树（即只有一层分裂的决策树，或深度很浅的树）可以防止过拟合，从而控制方差。同时短决策树的训练和预测都非常快。
无需超参数搜索：与 SVM、神经网络等需要精细调参的模型相比，AdaBoost+决策树几乎是“开箱即用”的，效果通常都很好。UC Berkeley 的 Leo Breiman 称之为“世界上最好的现成（off-the-shelf）分类器”。
隐式特征选择：AdaBoost+短决策树是一种特征选择的形式。如果一个特征对提升整体预测能力贡献不大，它可能根本不会被任何一个短决策树选中。
非线性边界更有效：对于线性分类器，Boosting 效果不佳，因为需要很多次迭代才能拟合复杂的非线性边界。而决策树本身就是非线性的，Boosting 可以更快地减少其偏差。

2. 损失函数与公式推导

AdaBoost 使用了一个特殊的指数损失函数：

L(\lambda,\hat{\lambda}) \;=\; e^{-\lambda\hat{\lambda}} \;=\; \begin{cases} e^{-\hat{\lambda}}, & \lambda=+1,\\[6pt] e^{\hat{\lambda}}, & \lambda=-1. \end{cases}

其中： $\lambda$ 是真实标签 (+1 或 -1)， $\hat{\lambda}$ 是元学习器的连续输出值 $M(X_i)$ 。

于是总风险可以表示为：

\text{Risk} = \frac{1}{n} \sum_{i=1}^{n} L(M(X_i), y_i) = \frac{1}{n} \sum_{i=1}^{n} e^{-y_i M(X_i)}

将模型展开并分离第 $T$ 轮，有：

\begin{aligned} \text{Risk} &= \frac{1}{n} \sum_{i=1}^{n} e^{-y_i \sum_{t=1}^{T} \beta_t G_t(X_i)} \\ &= \frac{1}{n} \sum_{i=1}^{n} \prod_{t=1}^{T} e^{-\beta_t y_i G_t(X_i)} \\ &= \frac{1}{n} \sum_{i=1}^{n} \left( \prod_{t=1}^{T-1} e^{-\beta_t y_i G_t(X_i)} \right) e^{-\beta_T y_i G_T(X_i)} \end{aligned}

我们定义第 $T$ 轮开始时的样本权重 $w_i^{(T)}$ ：

w_i^{(T)} = \prod_{t=1}^{T-1} e^{-\beta_t y_i G_t(X_i)}

于是总风险可以写成关于第T轮的形式：

\begin{aligned} \text{Risk}_T &= \sum_{i=1}^{n} w_i^{(T)} e^{-\beta_T y_i G_T(X_i)} \\ &= \sum_{y_i = G_T(X_i)} w_i^{(T)} e^{-\beta_T} + \sum_{y_i \neq G_T(X_i)} w_i^{(T)} e^{\beta_T} \\ &= e^{-\beta_T} \sum_{i=1}^{n} w_i^{(T)} + (e^{\beta_T} - e^{-\beta_T}) \sum_{y_i \neq G_T(X_i)} w_i^{(T)} \end{aligned}

由这个式子，我们讨论两个问题：

$G_T$ 的选择：可以看出最优的弱分类器 $G_T$ 的选择依据如下：

G_T = \underset{G}{\arg\min} \sum_{i=1}^{n} w_i^{(T)} \mathbb{I}(y_i \neq G(X_i))

这正是我们训练弱分类器的目标：我们希望让被错分的点的权重之和最小。

权重的递归定义：可以得到如下的样本权重更新规则：

w_i^{(T+1)} = w_i^{(T)} e^{-\beta_T y_i G_T(X_i)} = \begin{cases} w_i^{(T)} e^{-\beta_T}, & \text{if } y_i = G_T(X_i) \quad (\text{correct}) \\ w_i^{(T)} e^{\beta_T}, & \text{if } y_i \neq G_T(X_i) \quad (\text{incorrect}) \end{cases}

然后我们推导分类器权重 $\beta_T$ 的选择。令风险函数为 $J(\beta_T)$ ：

J(\beta_T) = \sum_{y_i = G_T(X_i)} w_i^{(T)} e^{-\beta_T} + \sum_{y_i \neq G_T(X_i)} w_i^{(T)} e^{\beta_T}

对 $\beta_T$ 求偏导并令其为零：

\begin{aligned} \frac{\partial J(\beta_T)}{\partial \beta_T} &= -\sum_{y_i = G_T(X_i)} w_i^{(T)} e^{-\beta_T} + \sum_{y_i \neq G_T(X_i)} w_i^{(T)} e^{\beta_T} = 0 \\ e^{\beta_T} \sum_{y_i \neq G_T(X_i)} w_i^{(T)} &= e^{-\beta_T} \sum_{y_i = G_T(X_i)} w_i^{(T)} \\ e^{2\beta_T} &= \frac{\sum_{y_i = G_T(X_i)} w_i^{(T)}}{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}} \\ e^{2\beta_T} &= \frac{\sum_{i=1}^n w_i^{(T)} - \sum_{y_i \neq G_T(X_i)} w_i^{(T)}}{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}} \\ e^{2\beta_T} &= \frac{1 - \frac{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}}{\sum_{i=1}^n w_i^{(T)}}}{\frac{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}}{\sum_{i=1}^n w_i^{(T)}}} \\ \end{aligned}

我们定义加权错误率 $\text{err}_T$ ：

\text{err}_T = \frac{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}}{\sum_{i=1}^{n} w_i^{(T)}}

则：

\begin{aligned} e^{2\beta_T} &= \frac{1 - \text{err}_T}{\text{err}_T} \\ 2\beta_T &= \ln\left(\frac{1 - \text{err}_T}{\text{err}_T}\right) \\ \beta_T &= \frac{1}{2} \ln\left(\frac{1 - \text{err}_T}{\text{err}_T}\right) \end{aligned}

如果 $err_T = 0$ (完美分类)， $\beta_T = \infty$ (获得无限大的投票权)。
如果 $err_T = 0.5$ (相当于随机猜测)， $\beta_T = 0$ (没有投票权)。
如果 $err_T > 0.5$ (比随机猜还差)， $\beta_T$ 会是负数。这意味着这个学习器“坏到恰到好处”，我们可以把它预测的结果反过来用，它就变成了一个好的学习器。

于是，AdaBoost 经过整理后的完整流程如下：

初始化权重：所有训练样本的权重 $w_i$ 初始化为 $\frac{1}{n}$ 。
循环 $T$ $T$ 次，对于第 $t$ $t$ 次：
1. 使用当前的权重 $w_i$ 训练一个弱学习器 $G_t$ 。
2. 计算 $G_t$ 的加权错误率 $err_t$ ，并根据 $err_t$ 计算该学习器的投票权重 $\beta_t$ 。
3. 更新所有样本的权重 $w_i$ ：错分的样本权重乘以 $e^{(\beta_t)}$ ，正确的样本权重乘以 $e^{(-\beta _t)}$ 。（然后通常会进行归一化，使所有权重之和为1）。
返回最终模型：元学习器 $h(z) = \text{sign}(\sum _{t=1} ^T β_t G_t(z))$ 。

需要说明：指数损失函数对噪声和异常值非常敏感，一个离群点可能会获得极大的权重，从而影响后续学习器的训练。如果数据质量不高，可以考虑使用其他更鲁棒的损失函数。

Boosting 算法

1. AdaBoost 简介

2. 损失函数与公式推导

Comments