ESL 10.1 Boosting Methods

2021-09-13 本文已影响0人找不到工作

Boosting 最初是为解决分类问题设计的，后来又被扩展到了回归问题。Boosting 的原理是将很多弱分类器组合起来产生一个强分类器。

一个弱分类器是某种比随机猜测结果略好的简单分类器。Boosting 每次将输入特征赋予不同的权重，并应用弱分类器进行分类，最后将所有结果通过投票的形式产生最终结果。

AdaBoost

我们从最基本的 AdaBoost 开始介绍。
假设某个分类问题结果为 -1 或者 +1。一共有 $N$ 个样本，并且我们已有 $M$ 个弱分类器。AdaBoost算法表述为：

初始化权重 $w_i = 1/N, i = 1,2,...,N$
For $m = 1$ to $M$ :
a. 对每个样本 $x_i$ 附加权重 $w_i$ 并送入分类器 $G_m(x)$
b. 计算错误率：
$\text{err}_m = \sum_{i=1}^N w_i I(y_i \neq G_m(x_i))$
c. 根据错误率计算该分类器权重（错误率越低权重越高）
$\alpha_m = \ln((1- \text{err}_m)/\text{err}_m)$
d. 更新分类错误的样本权重，并归一化处理（判断错误的样本权重提高，交由下一个分类器分类）
$w_i = \text{normalize} [ w_i e^{\alpha_m I(y_i \neq G_m(x_i))} ]$
最终生成的强分类器为：
$G(x) = \sign [ \sum_{m=1}^M \alpha_m G_m(x)]$

其中， $I(x)$ 是条件判断。false = 0, true = 1。

2.d 比较难理解。调整样本权重的意义在于，如果某个分类器已经正确分类 i 样本，后续的分类器的责任在于“补全” A 分类器的功能，即，不要重复正确的结论，应该把重点放在 A 分类错误的样本上。

如果后续某个分类器与 A 分类器的结论重复，那由 2.c 得到的分类器权重会很低。在最终的强分类器中，几乎不产生影响。反之，如果与 A 互补，那可能会得到一个很高的权重。

AdaBoost 简单例子

假设有如下训练数据。

待分类样本数据

我们有如下分类器（都比随机猜测略好）：

$G_1(x) = \begin{cases} +1 & x_1 \leq 2 \\ -1 & x_1 > 2 \end{cases}$

$G_2(x) = \begin{cases} -1 & x_2 \leq 1 \\ +1 & x_2 > 1 \\ \end{cases}$

$G_3(x) = \begin{cases} +1 & x_1 \leq 1 \\ -1 & x_1 > 1 \end{cases}$

首先，我们将样本权重设置为 $w_i = 0.2$ ，应用 $G_1$ 分类器，发现位于 (1.5, 0.5) 的点（假设为 5 号点）分类错误：

$\text{err}_1 = 0.2$

计算 $G_1$ 分类器权重：

$\alpha_1 = \ln ((1-0.2) / 0.2) = \ln 4$

调整分类错误的样本权重并归一化：

$w_i = \text{normalize} [ 0.2, 0.2, 0.2, 0.2, 0.8] = [\frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{4}{8}]$

此后再将新的权重用于 $G_2$ 的分类：

$\text{err}_2 = \frac{1 }{8} *1 + \frac{1}{8} *1 = \frac{1}{4}$

$\alpha_2 = \ln ((1-0.25) / 0.25) = \ln 3$

$w_i = \text{normalize} [ 0.6, 0.2, 0.2, 0.6, 0.8] = [\frac{3}{12}, \frac{1}{12}, \frac{1}{12}, \frac{3}{12}, \frac{4}{12}]$

再用 $G_3$ 分类：

$\text{err}_3 = \frac{1 }{12}$

$\alpha_3 = \ln 11$

最终得出：

$G(x) = \sign [\ln4 G_1(x) + \ln3 G_2(x) + \ln11 G_3(x)]$

各区域实际值

得到的边界为：

边界

参考资料

Lectures on Machine Learning

上一篇下一篇

猜你喜欢

热点阅读