DanielLaah

《统计学习方法》笔记 (十) - 提升方法


本篇博客为《统计学习方法》笔记系列第10篇, 对应《统计学习方法》中第8章中的最大熵模型.
说明: 目前来讲, 本系列博客内容基本完全摘抄自李航博士的《统计学习方法》, 所以阅读本系列博客极有可能造成您的不适, 如发生, 请尽快关闭浏览器. 写此系列博客目的一是学习的时候加深印象二是为了方便自己随时复习. 后面如果在其他书籍或课程中学习了相关的知识, 可能会对文章内容进行适量增删. 谢谢你!
PPT下载


提升方法是一种常用的统计学习方法, 应用广泛且有效. 在分类问题中, 它通过改变训练样本的权重, 学习多个分类器, 并将和谐分类器进行线性组合, 提高分类性能.

一. 提升方法AdaBoost算法

对提升方法来说, 有两个问题需要回答:
一是在每一轮如何改变训练数据的权值或概率分布;
二是如何将弱分类器组合成一个强分类器.
关于第1个问题, AdaBoost的做法是, 提高那些被前一轮弱分类器错误分类样本的权值, 而降低那些被正确分类样本的权值. 这样一来, 那些没有得到正确分类的数据, 由于其权值的加大而受到后一轮的弱分类器的更大关注. 于是, 分类问题被一系列的弱分类器分而治之. 至于第2个问题, 即弱分类器的组合, AdaBoost采取加权多数表决的方法. 具体地, 加大分类误差率小的弱分类器的权值, 使其在表决中起较大的作用, 减小分类误差率大的弱分类器的权值, 使其在表决中起较小的作用.
下面给出AdaBoost算法
假设给定一个二类分类的训练数据集
$$T={(x_1, y_1), (x_2, y_2),…,(x_N, y_N)}$$
其中, 每个样本点由实例与标记组成. 实例$x_i\in \mathcal{X}\subseteq R^n$, 标记$y_i\in=\{-1,+1\}$, $\mathcal{X}$是实例空间, $\mathcal{Y}$是标记集合. AdaBoost利用以下算法, 从训练数据中学习一系列弱分类器或基本分类器, 并将这些弱分类器线性组合成为一个强分类器.
输入:训练数据集$T={(x_1, y_1),(x_2, y_2),…,(x_N,y_N)}$, 其中$x_i\in \mathcal{X}\subseteq R^n$, $y_i\in=\{-1,+1\}$;弱学习算法;
输出:最终分类器$G(x)$.
(1)初始化训练数据的权值分布
$$D_1=(w_{11},…,w_{1i},…,w_{1N}), w_{1i}=\frac1N, i=1,2,…,N$$
(2)对$m=1,2,…,M$
(a)使用具有权值分布$D_m$的训练数据集学习, 得到基本分类器
$$G_m(x)=\mathcal{X}\rightarrow \{-1,+1\}$$
(b)计算$G_m(x)$在训练数据集上的分类误差率
$$e_m=P(G_m(x_i)\ne y_i)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\ne y_i)$$
(c)计算Gm(x)的系数
$$\alpha_m=\frac12\ln\frac{1-e_m}{e_m}\tag{8.2}$$
(d)更新训练数据集的权值分布
$$D_{m+1}=(w_{m+1,1},…,w_{m+1,i},…,w_{m+1,N})$$
$$w_{m+1,i}=\frac{w_{mi}}{z_m}\exp{(-\alpha_my_iG_m(x_i))}, i=1,2,…,N \tag{8.4}$$
这里, Zm是规范化因子
$$Z_m=\sum_{i=1}^Nw_{mi}\exp{(-\alpha_my_iG_m(x_i))}\tag{8.5}$$
它使Dm+1成为一个概率分布.
(3)构建基本分类器的线性组合
$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$
得到最终分类器
$$G(x)=\text{sign}(f(x))=\text{sign}\left(\sum_{m=1}^M\alpha_mG_m(x)\right)$$
对AdaBoost算法作如下说明:
步骤(1) 假设训练数据集具有均匀的权值分布, 即每个训练样本在基本分类器的学习中作用相同, 这一假设保证第1步能够在原始数据上学习基本分类器$G_1(x)$.
步骤(2) AdaBoost反复学习基本分类器, 在每一轮$m=1,2,…,M$顺次地执行下列操作:
(a)使用当前分布$D_m$加权的训练数据集, 学习基本分类器$G_m(x)$.
(b)计算基本分类器$G_m(x)$在加权训练数据集上的分类误差率:
$$e_m=P(G_m(x_i)\ne y_i)=\sum_{G_m(x_i)\ne y_i}w_{mi}$$
这里, $w_{mi}$表示第$m$轮中第$i$个实例的权值, . 这表明, $G_m(x)$在加权的训练数据集上的分类误差率是被$G_m(x)$误分类样本的权值之和, 由此可以看出数据权值分布$D_m$与基本分类器$G_m(x)$的分类误差率的关系.
(c)计算基本分类器$G_m(x)$的系数$\alpha_m$. $\alpha_m$表示$G_m(x)$在最终分类器中的重要性. 由式(8.2)可知, 当$e_m≤\frac12$时, $\alpha_m≥0$, 并且$\alpha_m$随着$e_m$的减小而增大, 所以分类误差率越小的基本分类器在最终分类器中的作用越大.
(d)更新训练数据的权值分布为下一轮作准备. 式(8.4)可以写成:
$$
\begin{cases}
w_{m+1,i} = \frac{w_{mi}}{Z_m}e^{-\alpha_m}, & G_m(x_i)=y_i \\
\\
w_{m+1,i} = \frac{w_{mi}}{Z_m}e^{\alpha_m}, & G_m(x_i)\ne y_i
\end{cases}
$$
由此可知, 被基本分类器$G_m(x)$误分类样本的权值得以扩大, 而被正确分类样本的权值却得以缩小. 两相比较, 误分类样本的权值被放大倍. 因此, 误分类样本在下一轮学习中起更大的作用. 不改变所给的训练数据, 而不断改变训练数据权值的分布, 使得训练数据在基本分类器的学习中起不同的作用, 这是AdaBoost的一个特点.
步骤(3) 线性组合$f(x)$实现$M$个基本分类器的加权表决. 系数$\alpha_m$表示了基本分类器$G_m(x)$的重要性, 这里, 所有$\alpha_m$之和并不为1. $f(x)$的符号决定实例$x$的类, $f(x)$的绝对值表示分类的确信度. 利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点.

二. AdaBoost算法的训练误差分析

AdaBoost最基本的性质是它能在学习过程中不断减少训练误差, 即在训练数据集上的分类误差率, 关于这个问题有如下定理:
AdaBoost算法最终分类器的训练误差下界为
$$\frac{1}{N}\sum_{i=1}^NI(G(x_I)\ne y_i)\le\frac1N\sum_{i}\exp(-y_f(x_i))=\prod_mZ_m$$
证明, 当$G(x_i)\ne y_i$时, $y_if(x_i)\lt 0$, 因而$\exp(-y_if(x_i))\ge 1$. 由此直接推导出前半部分. 后半部分的推导要用到$Z_m$的定义式(8.5)以及(8.4)的变形:
$$w_{mi}\exp(-\alpha_my_iG_m(x_i))=Z_mw_{m+1,i}$$
推导如下:
$$
\begin{align}
\frac1N & \sum_i\exp(-y_if(x_i)) \\
\\
& = w_{1,i}\sum_{i}\exp\left(-\sum_{m=1}^M\alpha_my_iG_m(x_i)\right) \tag{利用定义} \\
\\
& = \sum_{i}w_{1,i}\exp\left(-\sum_{m=1}^M\alpha_my_iG_m(x_i)\right) \tag{分配律} \\
\\
& = \sum_{i}w_{1,i}\prod_{m=1}^M\exp\left(-\alpha_my_iG_m(x_i)\right) \tag{指数性质}\\
\\
& = \sum_{i}w_{1,i}\exp\left(-\alpha_1y_iG_1(x_i)\right)\prod_{m=2}^M\exp\left(-\alpha_my_iG_m(x_i)\right) \tag{提取连乘第一项}\\
\\
& = Z_1Z_2\sum_{i}w_{2,i}\prod_{m=3}^M\exp\left(-\alpha_my_iG_m(x_i)\right) \tag{Z的推倒式}\\
\\
& = …\\
\\
& = Z_1Z_2…Z_{M-1}\sum_{i}\exp\left(-\alpha_My_iG_M(x_i)\right) \\
\end{align}
$$
这一定理说明, 可以在每一轮选取适当的$G_m$使得$Z_m$最小, 从而使得训练误差下降最快. 对二分类问题, 有如下结果:

三. AdaBoost算法的解释