从一个demo学习AdaBoost

从一个demo学习AdaBoost

前言

提升算法(boost算法)是组合多个仅比随机猜测好一些的弱学习器,形成一个性能很好的强学习器。听起来很不可思议,但已经有学者证明,一个问题可由单个强学习器学习的充分必要条件是,这个问题可由多个弱学习器组合的学习器学习。这也是提升算法可行的根本依据。

提升算法直观上也很好理解,如果多个弱学习器各自擅长解决问题的某一些互相不同的场景,那么多个弱学习器有可能比单个擅长任何场景的学习性能好,三个臭皮匠胜过一个诸葛亮。

具体怎么学习和组合这一系列的弱学习器,各个boost算法着重点不同,常用的是三大boost算法,AdaBoost、GBDT和XGBoost。

提升算法的性能取决于各个弱分类器的多样性,AdaBoost通过改变训练数据的权重,来增强各个基本分类器的多样性。

本文以一个demo为例,庖丁解牛式的学习AdaBoost。

例子

给定下表所示二分类问题的训练数据,总共10个样本,x的取值0~9,y是类别,取值1或-1,代表两种类别。假设弱分类器由$x>v$或$x<v$产生,其阈值v使该分类器在训练数据集上分类误差率最低,试用AdaBoost算法学习一个强分类器。

// 训练数据表
num | 1 | 2 | 3 |  4 |  5 |  6 | 7 | 8 | 9 | 10  |
 x  | 0 | 1 | 2 |  3 |  4 |  5 | 6 | 7 | 8 |  9  |
 y  | 1 | 1 | 1 | -1 | -1 | -1 | 1 | 1 | 1 | -1  |

弱分类器的形式是决策树桩:

g(x) = x > v ? 1 : -1;
或者
g(x) = x < v ? 1 : -1;

由于大括号的公式MathJax不支持,这里以代码代替。

AdaBoost算法

AdaBoost,是Adaptive Boosting(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于:前一个基本分类器分错的样本会得到加强,加权后的全体样本再次被用来训练下一个基本分类器。同时,在每一轮中加入一个新的弱分类器,直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

算法1: AdaBoost
输入:训练数据集$T=\left\{ (x_{1}, y_{1}),(x_{2}, y_{2}),…,(x_{N}, y_{N}) \right\}$,其中$x_{i}\in X\subseteq R^{n}$,$y_{i}\in Y=\{1,-1\}$;
输入:弱学习算法;
输出:最终的分类器$G(x)$.
步骤:
(1)初始化训练数据的权值分布,$D_{1}=(w_{11},w_{12},…,w_{1N}),w_{1i}=\frac{1}{N},i=1,2,…,N$
(2)对$m=1,2,…,M$
(a)使用具有权值分布$D_{m}$的训练数据集学习,得到基本分类器

(b)计算基本分类器$G_{m}$在训练数据集上的分类误差率

(c)计算$G_{m}$的系数

这里的对数是自然对数.
(d)更新训练数据集的权值分布

这里,$Z_{m}$是归一因子

它使$D_{m+1}$成为一个概率分布.
(3)构建基本分类器的线性组合

得到最终分类器

用AdaBoost解上述例子

我们把训练数据表挪过来,方便对照。

// 训练数据表
num | 1 | 2 | 3 |  4 |  5 |  6 | 7 | 8 | 9 | 10  |
 x  | 0 | 1 | 2 |  3 |  4 |  5 | 6 | 7 | 8 |  9  |
 y  | 1 | 1 | 1 | -1 | -1 | -1 | 1 | 1 | 1 | -1  |

(1)第一轮迭代m=1

(a)初始化数据权值分布

(b)在权值分布为$D_{1}$的训练数据集上,训练弱分类器。
可以发现当阈值$v=2.5$时,分类误差率最低,故基本分类器为:

G1(x)= x < 2.5 ? 1 : -1

(c)计算$G_{1}(x)$在训练数据集上的误差率
对每一个样本计算$G_{1}(x_{i}),i=1,2,…,10$,发现共有7、8、9等三个样本分类错误。将这三个错误分类样本的权值相加,得到分类误差率:

(d)计算$G_{1}(x)$的权重系数:$\alpha_{1}=\frac{1}{2}log\frac{1-e_{1}}{e_{1}}$=0.4236
(e)此阶段得到的分类器为

分类器$sign[f_{1}(x)]$在训练数据集上有3个误分类点。

(2)第二轮迭代m=2

(a)更新数据集权值分布

归一化上述$w_{2i}$成一个概率分布:

这里不一一计算各个权值,最终得到的新的权值分布为:

标红的是$G_{1}$错误分类的三个样本7、8、9,更新后的权重,明显的,$G_{1}$正确分类的减小,错误分类的加大。
(b)在权值分布为$D_{2}$的训练数据集上,训练弱分类器。
可以发现当阈值$v=8.5$时,分类误差率最低,故基本分类器为:

G2(x)= x < 8.5 ? 1 : -1

(c)计算$G_{2}(x)$在训练数据集上的误差率
对每一个样本计算$G_{2}(x_{i}),i=1,2,…,10$,发现共有4、5、6等三个样本分类错误。将这三个错误分类样本的权值相加,得到分类误差率:

(d)计算$\alpha_{2}=\frac{1}{2}log\frac{1-e_{2}}{e_{2}}$=0.6496
(e)此阶段得到的分类器为

分类器$sign[f_{2}(x)]$在训练数据集上有3个误分类点。

(3)第三轮迭代m=3

(a)更新数据集权值分布

归一化上述$w_{3i}$成一个概率分布:

这里不一一计算各个权值,最终得到的新的权值分布为:

标红的是$G_{2}$错误分类的三个样本4、5、6,更新后的权重,明显的,$G_{2}$正确分类的减小,错误分类的加大。
(b)在权值分布为$D_{3}$的训练数据集上,训练弱分类器。
可以发现当阈值$v=5.5$时,分类误差率最低,故基本分类器为:

G3(x)= x > 5.5 ? 1 : -1

(c)计算$G_{3}(x)$在训练数据集上的误差率
对每一个样本计算$G_{3}(x_{i}),i=1,2,…,10$,发现共有1、2、3、10等四个样本分类错误。将这四个错误分类样本的权值相加,得到分类误差率:

(d)计算$\alpha_{3}=\frac{1}{2}log\frac{1-e_{3}}{e_{3}}$=0.7514
(e)此阶段得到的分类器为

分类器$sign[f_{3}(x)]$在训练数据集上有0个误分类点,停止迭代。

于是最终分类器为:

观察可知,$G_{1}、G_{2}、G_{3}$的误差率分别为0.3、0.2143、0.1820,对应的权重分别为0.4236、0.6496、0.7514,明显的误差越低,在最终分类器中所占的比重越大,表决权越大。还可以看出,AdaBoost的收敛速度是很快的,上述例子仅需三步训练误差就降为0,事实上对AdaBoost做误差分析可知,AdaBoost的误差是以指数速率下降的。

AdaBoost算法推导

经过前文的demo,相信大家对AdaBoost已经有个较为全面的认知。本文尝试推导AdaBoost

AdaBoost算法实际上是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二分类学习方法。

加法模型与前向分步算法

加法模型(additive model)是模型由若干个基函数线性组合而成:

其中,$b(x;\gamma_{m})$为基函数,$\gamma_{m}$为基函数的参数,$\beta_{m}$为基函数的系数,显然的AdaBoost算法的最终分类器是一个加法模型。

在给定训练数据及损失函数$L(y,f(x))$的条件下,学习加法模型$f(x)$成为经验风险极小化即损失函数极小化的问题:

通常这是一个非常复杂的优化问题,前向分步算法(forward stagewise algorithm)求解这一优化问题的想法是:因为学习的是加法模型,如果能够从前向后,每一步只学习一个基函数及其系数,逐步逼近上述优化目标函数,那么就可以简化优化的复杂度,具体地,每一步只需要优化如下损失函数:

算法2:前向分布算法
输入:训练数据集$T=\left\{ (x_{1}, y_{1}),(x_{2}, y_{2}),…,(x_{N}, y_{N}) \right\}$,其中$x_{i}\in X\subseteq R^{n}$,$y_{i}\in Y=\{1,-1\}$;
输入:基函数集${b(x;\gamma)}$
输出:加法模型$f(x)$
(1)初始化$f_{0}(x)=0$
(2)对$m=1,2,…,M$
(a)极小化损失函数

得到参数$\beta_{m},\gamma_{m}$
(b)更新

(3)得到加法模型

这样,前向分步算法将同时求解从$m=1$到$M$所有参数$\beta_{m},\gamma_{m}$的优化问题,简化为逐次求解各个$\beta_{m},\gamma_{m}$的优化问题。

AdaBoost推导

AdaBoost只是一个前向分步加法算法的特例,这时,模型是由基本分类器组成的加法模型,损失函数是指数函数。
指数损失函数的形式是:

假定经过$m-1$轮迭代,前向分步算法已经得到$f_{m-1}(x)$:

在第$m$轮迭代得到$\alpha_{m}$,$G_{m}(x)$和$f_{m}(x)$.

目标是使前向分步算法得到的$\alpha_{m}$和$G_{m}(x)$使$f_{m}(x)$在训练数据集$T$上的指数损失最小,即

记$\bar{w}_{mi}=exp[-y_{i}f_{m-1}(x_{i})]$,则

求解上式,可分为两步:
首先,求$G_{m}(x)$. 对任意$\alpha>0$,使得上式最小的$G(x)$由下式得到:

之后,求$\alpha_{m}$

上式是$\alpha$的单变量函数,记为$h(\alpha)$,对$\alpha$求导,并令其等于0

记,归一化的权重$\bar{w}_{mi}$为$w_{mi}$,则

记,$e_{m}=\sum_{i=1}^{N}w_{mi}I(y_{i}\neq G_{m}(x_{i}))$,则

最终得到$\alpha_{m}$:

最后来看每一轮样本权值的更新. 由

以及$\bar{w}_{mi}=exp[-y_{i}f_{m-1}(x_{i})]$,可得

归一化后得,

这与AdaBoost的权值更新公式完全相同。

上述的$G_{m}(x)、\alpha_{m}、{w}_{m+1,i}$的迭代公式与AdaBoost的$G_{m}(x)、\alpha_{m}、{w}_{m+1,i}$的迭代公式完全相同,推导完毕。

需要说明的是,权重的归一化是$\alpha_{m}$中$e_{m}$的计算所要求的,$G_{m}(x)$的迭代并不需要权值归一化。

文献

  1. 李航老师《统计学习方法》第八章 提升方法
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×