讲到Ensemble Learning的boosting,肯定会讲Adaboost,它是boosting思想最重要的算法之一,另外一个是GBDT。本文主要内容是参考《李书》和一篇博客(见参考资料1,2).
1. Adaboost算法
二分类问题,训练数据集{$(x_1,y_1), (x_2,y_2),\dots,(x_N,y_N)$},样本的label为$y_i=1$或者-1.
Adaboost
输入:训练数据集{$T = (x_1,y_1), (x_2,y_2),\dots,(x_N,y_N)$};和某个弱学习算法(又称学习器、分类器)
输出:最终分类器$G(x)$
- 初始化训练样本的权重分布:
- 对每个学习器$m=1,2,\dots,M$:
- 将训练数据集$T$和训练数据的权重$D_m$,带入分类器学习,得到$G_m(x)$
- 计算在训练集上的误分类比率:
- 计算分类器$G_m(x)$的系数:
- 更新训练数据集的权重分布:其中
- 构建基本分类器的线性组合并得到最终的分类器:
2. 算法的解释
- 第1步,初始化样本的权重为均匀分布,对于第一个学习器,样本的权重相同。即第一个学习器是对原始数据集合上训练。
第2.1步,分类器训练的目标就是最小化误分类率$e_m$,
所以,第2.1步和第2.2步是同时进行的。Adaboost算法的最基本性质是它能在学习过程中不断减小训练误差,即误分类比率。(参考资料1-P142-定理8.1,8.2)
- 第2.2步,误分类比率是被误分类的样本的权重之和。在第$m$个学习器上的误分类比率:。(用概率表示是因为第2.4步,每一轮的样本权重之和均为1:. )
- 第2.2步,默认的弱学习器叫做Decision stump,即只有一层的决策树,只考虑一个特征(一个维度)。选择$e_m$的方式:遍历每个特征的每个分割方式,得到的误分类样本权重和最小的为$e_m$。
- 第2.3步,学习器的系数代表这个学习器的重要性。当$e_m\leq\frac{1}{2}$(即误分类比率低)的时候,有$\alpha_m\geq 0$,并且$e_m$越小$\alpha_m$越大。所以误分类比率越小的分类器,在最终分类器中作用越大。
- 第2.3步,在《西瓜书》里这一步之前,会加一个判断:如果得到$e_m>0.5$,即遍历了每个特征的每种分割方式都找不到合适的弱学习器,跳出迭代,算法终止。
- 第2.4步,权重更新的时候除以,这样权重分布之和为1,称为一个概率分布。
- 第2.4步,权重的更新可以写成下面的式子如果$\alpha_m>0$是一个正面作用的分类器,先忽略$Z_m$,对那些分类正确的样本,权重值减小;分类错误的样本呢,权重值变大。这样误分类样本点在下一轮学习器会更加重要。
不改变所给的训练数据,只不断改变训练数据的权重分布,使得训练数据在基本分类器的训练中起不同作用,这是Adaboost的特点
3. Adaboost算法的数学解释
Adaboost算法是模型为加法模型的、损失函数为指数函数的、学习方法为前向分布算法的二分类问题。
- 加法模型:$f(x) = \sum\limits_{m=1}^M \alpha_m g_m(x,\gamma_m)$. 其中$g_m$是基函数,$\gamma_m$是基函数的参数,$\alpha_m$是基函数的系数
- 指数损失函数:$L(y, f(x)) = e^{-yf(x)}$
(回忆SVM中的hinge损失函数$L(y,f(x)) = \max(0, 1-yf(x))$) - 前向分布算法的思想:对于加法模型,从前往后,每一轮只学习一个基函数及其系数,逐步逼近优化损失函数。
即每一轮$m$的目标就是极小化损失函数
应用到Adaboost:
(加法模型)第$m$轮迭代得到的,和,有
(指数损失)又因为损失函数为$L(y,f(x)) = e^{-yf(x)}$,
(前向分布)所以第$m$轮迭代的目标是:要找到能够使损失函数最小化的$\alpha_m$和$G_m(x)$,
上式可写成
其中.可以看出,只与有关,与无关,所以暂时无视这些系数。先求使得\eqref{eq1}式得到最小的,就是$\alpha_m$和$G_m(x)$。
- 分两步,首先求$G_m(x)$:对任意$\alpha>0$,使\eqref{eq1}式达到最小的$G(x)$由下式得到:其中。比较容易理解,对于$\alpha>0$,系数$\bar{w}>0$,越小,说明满足的$i$越少,$\bar{w}$增大(乘以一个大于1的数)的样本数越少。
所以,$G_m$就是第$m$轮迭代,加权训练数据集,误分类比率最小的分类器。 - 然后求$\alpha_m$:这里如果令,恰好就是误分类率;对\eqref{eq3}式关于$\alpha$求导并使导数为0,得到因为损失函数\eqref{eq3}的二次导数>0,所以极值点是极小值点。
最后再看权重的更新:由以及可得,
注意:
- 一般而言$\alpha>0$,因为我们总是找一个弱分类器,即误分类率略小于0.5即可。
- $w$是样本的权重>0,不是分类器的参数。前向分布算法的每一次迭代,\eqref{eq1}要找使得损失函数最小的分类器参数(也就是确定分类器),这里完全不是求样本的权重。
- 每一轮迭代$m$,通过极小化指数损失函数\eqref{eq1}而得到的分类器\eqref{eq2},是使第$m$轮加权的样本数据误分类之和最小的分类器。
- 在第$m-1$轮就已经确定了样本的权重,在第$m$轮时作为常数来考虑,权重只与前一轮的参数有关系,然后在第$m$轮再确定的$G_m$和$\alpha_m$
4. Adaboost的优缺点
来自参考资料3:
- 优点:
- 快, 简单
- 需要调参的参数很少,除了弱学习器数量$M$
- Adaboost不容易过拟合
- 缺点:
- 对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性;
5. 参考资料
- 《统计学习方法》李航,P137-146.
- AdaBoost原理详解
- BOOSTING(Adaboost algorithm)