机器学习算法系列（11）Adaboost 算法及其参数解释

在 Adaboost 中会有很多次的迭代计算，每一次的迭代计算得到一个基本分类器，根据已有的基本分类器，Adaboost 算法会提高那些在前一轮被弱分类器误分类的样本的权值，并降低那些被正确分类的样本的权值，对于“差生”重点关注。提升方法通过重复修改训练数据的权重分布，构建一系列的弱分类器，然后依据特定的组合算法对这些弱分类器进行线性组合，从而得到最终的强分类器。

Adaboost 是一个“笨蛋”，一开始它也许不怎么聪明，但是它非常乐于改进并接受他人的意见，所以最后它会变得很强大。

偏差指的是模型的期望预测值与真实结果的偏离程度，Boosting 方法在训练的过程中非常关注自己在每次的训练中所犯下的错误，所以“从偏差-方差分解的角度看，Boosting 主要关注降低偏差，因此 Boosting 能给予泛化性能相对弱的学习器构建很强的集成”。

一、背景

在机器学习中，集成学习（Ensemble learning）目标是构建并组合多个学习器（Weak learner）来完成学习任务，组合学习器中的单个学习器“单兵作战”的效果可能并不理想，然而多个这样的学习器组合起来效果就很可观了。有一句俗话，“三个臭皮匠顶个诸葛亮”，意思是说几个资质平庸的人联合起来也有能有大智慧，集成学习的道理也是如此：能力不够，人头来凑。

学习一个简单粗糙的弱学习器比学习一个准确率很高的学习器要简单得多，比如预测股市的涨或者跌，没有任何知识背景的外行瞎蒙也有50%的准确率。然而通过特定组合算法的学习，这样几个弱学习器最终学习器整体的性能却能够得到显著提高，这个提高的过程也被称为提升（boosting）。提升是集成学习的一类，可以理解为“集思广益”，即团结力量大。这篇文章要介绍的便是集成学习中一个非常著名的算法—— Adaboost 算法。

二、Adaboost 算法

Adaboost 算法的原理比较简单，在 Adaboost 算法中，有两个难点问题需要弄明白：

• 如何在每一轮训练中更新数据的权值$D_m$？
• 如何将弱学习器组合成一个强学习器？

Adaboost 算法的基本思路大致有3个步骤，首先 Adaboost 给予训练集中的每个样本均匀的权重$w{1i}=\frac{1}{N}$，即每个训练样本在$h{1}(x)$分类器中所起得作用均一样；然后 Adaboost 反复学习$h{1}(x)$分类器，分别更新数据集权重和$h{m}(x)$分类器的系数；最后组合$m$个弱学习器得到最终分类器。

1. 初始化训练数据$T$的权重分布$D_m$； $$D_1 = (w_{11}, w_{12},...,w_{1N}), w_{1i}=\frac{1}{N}$$
2. 基于初始化训练数据集进行学习，得到弱学习器$h_{1}(x)$；

3. 对$m=1,2,..M$，计算弱学习器$h{m}(x)$在训练数据集上的误差率$e_m$和弱学习器$h{m}(x)$的系数$\alpha$；

   $$e_m = P(h_{m}(x) \neq y_i)$$

   \begin{equation}\begin{split}
   \alpha_m = \frac{1}{2}ln(\frac{1-e_m}{e_m})
   \end{split}\end{equation}

4. 更新训练数据集的权值分布，迭代到第m次时；

   $$D_{m+1} = (w_{m+1,1}, w_{m+1,2},...,w_{m+1,N})$$

   \begin{equation}\begin{split}
   w{m+1,i} = \frac{w{m,i}}{Zm}exp(-\alpha{m}yih{m}(x_i))\
   \label{dataweightupdate}
   \end{split}\end{equation}

   $$Z_m = \sum_{i=1}^{N}exp(-\alpha_{m}y_ih_{m}(x_i)）$$

5. 构建弱学习器的线性组合，得到最终分类器$G(x)$

   $$f(x) = \sum_{i=1}^{N}\alpha_{m}h_{m}(x_i)$$ $$H(x) = sign(f(x))$$

三、Adaboost 算法参数的解释

不打算继续深究的读者可以就此打住了，毕竟大多数人只是用用模型，背后复杂的数学推导根本没有必要。然而，本着知其然更要知其所以然的精神，我们还是有必要对 Adaboost 算法中涉及到的两个点——弱学习器系数和数据集权值分布，做一个简单的梳理，亦呼应了上一节开头提的两个问题。

1. 分类器权重$\alpha_m$更新原理

Adaboost 算法的优化目标是最小化指数损失函数

\begin{equation}\begin{split}
E &= exp^{-f(x)H(x)} \
&=exp^{-f(x)\alpha_mh_m(x)},f(x)h_m(x)只有1和-1两种情形,同时对应两种概率 \
&=exp^{-\alpha_m}(1-e_m)+exp^{\alpha_m}e_m\
\label{weightupdate}
\end{split}\end{equation}

令$\eqref{weightupdate}$式为零可得分类器权重更新公式

$$\alpha_m = \frac{1}{2}ln(\frac{1-e_m}{e_m})$$

2. 数据集权重$\bar{w}_{m+1,i}$更新原理

求解在每一轮样本的权值更新，由下面两个式子

$$f_m(x) = f_{m-1}(x) + \alpha H_m(x)$$ $$\bar{w}_{m,i} = exp(-y_if_{m-1}(x_i))$$

得

$$\frac{ln(\bar{w}_{m+1,i})}{-y_i} = \frac{ln(\bar{w}_{m,i})}{-y_i} - \alpha_m H_m(x)$$

经过化简可得样本权值的更新公式，对应算法中的$\ref{dataweightupdate}$，唯一的区别在与少了一个规范化因子，但是这并不妨碍与$\ref{dataweightupdate1}$等价

\begin{equation}\begin{split}
\bar{w}{m+1,i} = \bar{w}{m,i}·exp(-y_i \alpha_m H_m(x)) \
\label{dataweightupdate1}
\end{split}\end{equation}

3. 分类误差率$e_m$

$$e_m = \sum_{i=1}^{N} w_{m,i} I(h_{m}(x_i) \neq y_i)$$

Adaboost 算法的笔记暂时告一段落了，如果读者还有不太明白的地方，可以参照《统计学习方法》第140页的“Adaboost 例子”来辅助理解，文末提供的参考5给出了该例更为详细的讲解，相信对理解 Adaboost 算法的原理会有一定的帮助。

笔者是头一次接触集成学习（Ensemble learning），在这之前对集成学习的概念很是模糊，因为先前接触到的都是依据单个算法做成的分类器，所以一直弄不明白的是多个弱分类器是如何组成称为一个新的并且性能更强大的分类器。知其然还要知其所以然，笔者一直认为不管是直接调用各种强大的库，还是调一调参数以期提高机器学习的应用水平，背后的数学原理还是有必要去理解一下的，不然总有一种不踏实的感觉。

参考

1. 统计学习方法.李航
2. 机器学习.周志华
3. Explaining AdaBoost
4. Adaboost - 新的角度理解权值更新策略
5. Adaboost 算法的原理与推导（读书笔记）