AdaBoost小结

发表于 2020-06-28 更新于 2020-12-23 分类于计算机科学阅读次数： Valine：

本文字数： 6k 阅读时长 ≈ 5 分钟

AdaBoost

总结一下AdaBoost

参考文献：西瓜书，南瓜书，"ADDITIVE LOGISTIC REGRESSION: A STATISTICAL VIEW OF BOOSTING"

集成学习

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

集成学习的两个关键要素就是个体学习器（基学习器）和结合策略。

假设个体学习器错误率相互独立的前提下，可以证明随着集成数量的增加，集成错误率将以指数级下降并趋于0.

根据结合策略的不同，目前集成学习的方法可大体分为Boosting和Bagging两大类。

Boosting

Boosting（提升学习）是一族将弱学习器提升为强学习器的算法，个体学习器之间存在强依赖关系，必须串行生成。

通常的工作机制是：先训练出一个基学习器，根据基学习器的表现对训练样本的分布进行调整，使先前分类错误的样本在后续得到更多关注，然后基于调整后的分布进行训练下一个基学习器。最后将基学习器进行结合。

AdaBoost

AdaBoost是Boosting算法里著名的代表，标准的AdaBoost只适用于二分类任务。

假设训练集为$D = \{(\boldsymbol{x}_1, y_1),...,(\boldsymbol{x}_m, y_m)\}$，其中$\boldsymbol{x}_i \in \mathbb{R}^n$，$y_i \in \{-1, +1\}$为样本的类标记。假设训练集$D$里的样本服从某个分布$\mathcal{D}$，即$\boldsymbol{x} \sim \mathcal{D}$。

第$t$轮训练的基分类器记为$h_t(\boldsymbol{x})$，基分类器的加权和记为$H(\boldsymbol{x})$，最终的集成分类器记为$F(\boldsymbol{x})$

AdaBoost算法需要详细解释的地方有两处：①基分类器$h_t$的权重为何采用第6行的公式来计算②样本分布为何采用第7行的公式来更新

AdaBoost的损失函数——指数损失

根据西瓜书的推导方法，AdaBoost采用的损失函数为指数损失函数：

\[ l_{exp}(H|\mathcal{D}) = \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}[e^{-yH(\boldsymbol{x})}] \]

其中$H(\boldsymbol{x})$是基分类器的加权和，$y$是样本的类标记。

\[ H(\boldsymbol{x}) = \sum_{t=1}^T \alpha_t h_t(\boldsymbol{x}) \]

贝叶斯最优错误率

最小化指数损失将使最终的集成分类器$F(\boldsymbol{x})$满足贝叶斯最优错误率：

\[ F(\boldsymbol{x}) = \arg\max_y P(f(\boldsymbol{x})=y|\boldsymbol{x}) \]

当指数损失得到最小化时，对应的条件期望 $\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}[e^{-yH(\boldsymbol{x})}|\boldsymbol{x}]$ 也一定得到最小化。

\[ \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}[e^{-yH(\boldsymbol{x})}|\boldsymbol{x}] = e^{-H(\boldsymbol{x})} P(y=1|\boldsymbol{x}) + e^{H(\boldsymbol{x})} P(y=-1|\boldsymbol{x}) \]

此时条件期望对$H(\boldsymbol{x})$的偏导数为0：

\[ \frac{\partial \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}[e^{-yH(\boldsymbol{x})}|\boldsymbol{x}]}{\partial H(\boldsymbol{x})} = -e^{-H(\boldsymbol{x})} P(y=1|\boldsymbol{x}) + e^{H(\boldsymbol{x})}P(y=-1|\boldsymbol{x}) = 0 \]

解得

\[ H(\boldsymbol{x}) = \frac{1}{2} ln\frac{P(y=1|\boldsymbol{x})}{P(y=-1|\boldsymbol{x})} \]

因此有

\[ F(\boldsymbol{x}) = sign(H(\boldsymbol{x})) = sign(ln\frac{P(y=1|\boldsymbol{x})}{P(y=-1|\boldsymbol{x})}) = \begin{cases} 1, & P(y=1|\boldsymbol{x}) > P(y=-1|\boldsymbol{x}) \\ -1, & P(y=1|\boldsymbol{x}) < P(y=-1|\boldsymbol{x}) \end{cases} \\ = \arg\max_y P(f(\boldsymbol{x})=y|\boldsymbol{x}) \]

基分类器权重公式

权重$\alpha_t$应最小化带权基分类器$\alpha_t h_t$ 在 $_t $ 上的指数损失

\[ \alpha_t = \arg\min_\alpha l_{exp}(\alpha h_t|\mathcal{D}_t) \]

注意到$yh_t(\boldsymbol{x})\in \{-1, +1\}$

\[ l_{exp}(\alpha_th_t|\mathcal{D}_t) = \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_t} [e^{-y\alpha_th_t(\boldsymbol{x})}] \\ \]

指数损失$l_{exp}(\alpha_th_t|\mathcal{D}_t)$最小化时，$l_{exp}(\alpha_th_t|\mathcal{D}_t)$对基分类器的权重$\alpha_t$的偏导数为0：

\[ \frac{\partial l_{exp}(\alpha_th_t|\mathcal{D}_t)}{\partial \alpha_t} = -e^{-\alpha_t}(1-\epsilon_t) + e^{\alpha_t} \epsilon_t = 0 \]

解得

\[ \alpha_t = \frac{1}{2} ln(\frac{1 - \epsilon_t}{\epsilon_t}) \]

从这里还可以看出，当$\epsilon_t > 0.5$时有$\alpha_t < 0$。

这说明如果某一个基分类器比随机猜测的效果还差的时候，这个基分类器的权重应当取负数。与其留下效果不好的基分类器，倒不如直接舍弃，所以算法第5行要求基分类器的错误率要小于0.5才继续训练。

样本分布更新公式

下一轮训练的基分类器$h_t$应最小化基分类器加权和$H_{t-1}+\alpha_th_t$在原始数据分布$\mathcal{D}$上的指数损失$l_{exp}(H_{t-1}+\alpha_th_t|\mathcal{D})$

\[ h_t(\boldsymbol{x}) = \arg\min_h l_{exp}(H_{t-1}+\alpha_th|\mathcal{D}) \]

$l_{exp}(H_{t-1}+\alpha_th_t|\mathcal{D})$展开可以写成： \[ l_{exp}(H_{t-1}+\alpha_th_t|\mathcal{D}) = \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t-1}(\boldsymbol{x})}(e^{-yh_{t-1}(\boldsymbol{x})})^{\alpha_t}] \]

根据算法第5行，$0 < \epsilon_t \le 0.5$，所以$\alpha_t \ge 0$。最小化$l_{exp}(H_{t-1}+\alpha_th_t|\mathcal{D})$等价于最小化$l_{exp}(H_{t-1}+h_t|\mathcal{D})$

\[ l_{exp}(H_{t-1}+h_t|\mathcal{D}) = \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-y(H_{t-1}(\boldsymbol{x})+h_t(\boldsymbol{x}))}] = \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t-1}(\boldsymbol{x})} e^{-yh_t(\boldsymbol{x})}] \]

将$e^{-yh_t(\boldsymbol{x})}$用泰勒公式展开到二阶近似代替，并注意到$y^2 = h_t(\boldsymbol{x})^2=1$

\[ l_{exp}(H_{t-1}+h_t|\mathcal{D}) \approx \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t-1}(\boldsymbol{x})} (1-yh_t({\boldsymbol{x})+\frac{y^2h_t(\boldsymbol{x})^2}{2}})] \\ = \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t-1}(\boldsymbol{x})} (1-yh_t({\boldsymbol{x})+\frac{1}{2}})] \]

所以

\[ h_t(\boldsymbol{x}) = \arg\min_h \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t-1}(\boldsymbol{x})} (1-yh({\boldsymbol{x})+\frac{1}{2}})] \\ = \arg \max_h \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}[e^{-yH_{t-1}(\boldsymbol{x})}yh(\boldsymbol{x})] \]

配上一个归一化用的常数因子

\[ \frac{1}{Z_t} = \frac{1}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t-1}(\boldsymbol{x})}]} \]

原式可以改写成

\[ h_t(\boldsymbol{x}) = \arg \max_h \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}[\frac{e^{-yH_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t-1}(\boldsymbol{x})}]}yh(\boldsymbol{x})] \]

再令

\[ \mathcal{D}_t(\boldsymbol{x}) = \frac{\mathcal{D}(\boldsymbol{x})e^{-yH_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t-1}(\boldsymbol{x})}]} \]

不难证明$\mathcal{D}_t$表示一个新的分布，考虑$\mathcal{D}_{t+1}$和$\mathcal{D}_t$的关系

\[ \mathcal{D}_{t+1}(\boldsymbol{x}) = \frac{\mathcal{D}(\boldsymbol{x})e^{-yH_{t}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t}(\boldsymbol{x})}]} \\ = \frac{\mathcal{D}(\boldsymbol{x}) e^{-yH_{t-1}(\boldsymbol{x})}e^{-y\alpha_th_t(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t}(\boldsymbol{x})}]} \\ =\mathcal{D}_t(\boldsymbol{x})e^{-y\alpha_th_t(\boldsymbol{x})} ·\frac{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t-1}(\boldsymbol{x})}]}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}} [e^{-yH_{t}(\boldsymbol{x})}]} \]

这就得到了算法第7行的样本分布更新公式。

在新的分布下最小化分类误差

原式又可以改写成

\[ h_t(\boldsymbol{x}) = \arg \max_h \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_t} [yh(\boldsymbol{x})] \]

这表明理想的$h_t$是在新的分布$\mathcal{D_t}$下最小化指数损失。由$y,h(\boldsymbol{x})\in \{-1, +1\}$，有

\[ yh(\boldsymbol{x}) = 1 - 2 \mathbb{I}(y \ne h(\boldsymbol{x})) \]

于是原式等价于

\[ h_t(\boldsymbol{x}) = \arg \min_h \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_t} \mathbb{I} (y \ne h(\boldsymbol{x})) = \arg \min_h P(y \ne h(\boldsymbol{x})) \]

这说明$h_t$不仅在分布$\mathcal{D}_t$下最小化指数损失，同时也在最小化分类误差