1 简介

Boosting,也称为增强学习或提升法,是一种重要的集成学习技术,能够将预测精度仅比随机猜度略高的弱学习器增强为预测精度高的强学习器,这在直接构造强学习器非常困难的情况下,为学习算法的设计提供了一种有效的新思路和新方法。作为一种元算法框架,Boosting 几乎可以应用于所有目前流行的机器学习算法以进一步加强原算法的预测精度,应用十分广泛,产生了极大的影响。

Boosting 方法训练基分类器时采用串行的方式,各个基分类器之间有依赖。它的基本思路是将基分类器层层叠加,每一层在训练的时候,对前一层基分类器分错的样本,给予更高的权重。测试时,根据各层分类器的结果的加权得到最终结果。Bagging 与 Boosting 的串行训练方式不同,Bagging 方法在训练过程中,各基分类器之间无强依赖,可以进行并行训练。

而 AdaBoost 正是 Boosting 方法中最成功的代表,被评为数据挖掘十大算法之一。在 AdaBoost 提出至今的十几年间,机器学习领域的诸多知名学者不断投入到算法相关理论的研究中去,扎实的理论为 AdaBoost 算法的成功应用打下了坚实的基础。

2 加法模型

多元线性回归模型的构造实质上是将输入特征 $X$ 进行加权运算,即
$$
\begin{aligned}
y &= \beta_0+\beta_1x_1+\beta_2x_2+\cdots+\beta_px_p \\
&= \beta_0+\sum_{i=1}^p\beta_ix_i
\end{aligned}
$$
而 Boosting 算法与线性回归模型的思想类似,所不同的是该算法实现了多棵基础决策树 $f(x)$ 的加权运算。作为 Boosting 中最有代表性的算法,Adaboost 算法的整体数学公式为:
$$
F(x) = \sum_{i=1}^M\alpha_mf_m(x) = F_{m-1}(x)+\alpha_mf_m(x)
$$
其中,$F(x)$ 是由 $M$ 颗基础决策树构成的最终提升树,$F_{m-1}(x)$ 表示经过 $m-1$ 轮迭代后的提升树,$\alpha_m$ 为第 $m$ 棵基础决策树所对应的权重,$f_m(x)$ 为第 $m$ 棵基础决策树。除此之外,每一棵基础决策树的生成并不像随机森林那样,而是基于前一棵基础决策树的分类结果对样本点设置不同的权重,如果在前一棵基础决策树中将某样本点预测错误,就会增大该样本点的权重,否则会相应降低样本点的权重,进而再构建下一棵基础决策树,更加关注权重大的样本点。

按照这个思想,AdaBoost 算法需要解决三大难题,即样本点的权重 $w_{mi}$ 如何确定、基础决策树 $f(x)$ 如何选择以及每一棵基础决策树所对应的权重 $\alpha_m$ 如何计算。

3 损失函数

对于分类问题而言,通常提升树的损失函数会选择使用指数损失函数;对于预测性问题,通常会选择平方损失函数。这里不妨以二分类问题为例(正负例分别用 +1 和 -1 表示),详细解说关于提升树损失函数的推导和延申。
$$
\begin{aligned}
L(y,\hat y) &= L(y,F(x))\\
&= \exp\big(-yF(x)\big)\\
&= \exp\big(-y\sum_{m=1}^M\alpha_mf_m(x)\big)\\
&= \exp\big(-y(F_{m-1}(x)+\alpha_mf_{m}(x))\big)
\end{aligned}
$$

指数损失函数(exponential loss):
$$
L(Y|f(x)) = \exp[-yf(x)]
$$
对离群点、噪声非常敏感。经常用在 AdaBoost 算法中。

如上损失函数所示,未知信息为权重系数 $\alpha_m$ 和基础树 $f_m(x)$。

3.1 基学习器的选择——最优 $f_m(x)$

上文的损失函数即假设已经得知 $m-1$ 轮迭代后的提升树 $F_{m-1}(x)$ 之后,如何基于该提升树进一步求解第 $m$ 棵基础决策树和相应的系数。如果提升树 $F_{m-1}(x)$ 还能够继续提升,就说明损失函数还能够继续降低,换句话说,将所有训练样本点代入损失函数后,一定存在一个最佳的 $\alpha_m$ 和 $f_m(x)$,使得损失函数尽可能地小:
$$
(\alpha_m,f_m(x)) = \arg\min_{\alpha,f(x)}\sum_{i=1}^N\exp\Big(-y_i\big(F_{m-1}(x_i)+\alpha_mf_m(x_i)\big)\Big)
$$
上面的式子还可以改写为:
$$
(\alpha_m,f_m(x)) = \arg\min_{\alpha,f(x)}\sum_{i=1}^Np_{mi}\exp\big(-y_i\alpha_mf_m(x_i)\big)
$$
其中,$p_{mi} = \exp[-y_iF_{m-1}(x_i)]$,由于 $p_{mi}$ 与损失函数中的 $\alpha$ 和 $f_m(x)$ 无关,因此在求解最小化问题时只需重点关注 $\sum_{i=1}^N\exp\big(-y_i\alpha_mf_m(x_i)\big)$ 部分。

对于 $\sum_{i=1}^N\exp(-y_i\alpha_mf_m(x))$ 而言,当第 $m$ 棵基础决策树能够准确预测时,$y_i$ 与 $f_m(x_i)$ 的乘积为 1,否则为 -1,于是 $\exp(-y_i\alpha_mf_m(x_i))$ 的结果为 $\exp(-\alpha_m)$ 或 $\exp(\alpha_m)$,对于某个固定的 $\alpha_m$ 而言,损失函数中的和式仅仅是关于 $\alpha_m$ 的式子。所以,要想求得损失函数的最小值,首先得找到最佳的 $f_m(x)$ ,使得所有训练样本点 $x_i$ 代入 $f_m(x)$ 后,误判结果越少越好,即最佳的 $f_m(x)$ 可以表示为:
$$
f_m(x)^* = \arg\min_f\sum_{i=1}^Np_{mi}I(y_i\ne f_m(x))
$$
其中,$f$ 表示所有可用的基础决策树空间,$f_m(x)^*$ 就是从 $f$ 空间中寻找到的第 $m$ 轮基础决策树,它能够使加权训练样本点的分类错误率最小,$I(y_i\ne f_m(x)$ 表示当第 $m$ 棵基础决策树预测结果与实际值不相等时返回 1。

3.2 基学习器的权重——最优 $\alpha_m$

下一步需要求解损失函数中的参数 $\alpha_m$ ,为了求解的方便,首先将损失函数改写为下面的式子:
$$
\begin{aligned}
L(y,\hat y) &= L(y,F(x))\\
&= \exp(-y(F_{m-1}(x)+\alpha_mf_m(x)))\\
&= \sum_{i=1}^Np_{mi}\exp(-y_i\alpha_mf_m(x_i))\\
&= \sum_{y_i=f_m(x_i)}p_{mi}\exp(-\alpha_m) + \sum_{y_i\ne f_m(x_i)}p_{mi}\exp(\alpha_m)\\
&= \exp(-\alpha_m)\sum_{y_i=f_m(x_i)}p_{mi}+\exp(\alpha_m)\sum_{y_i\ne f_m(x_i)}p_{mi}\\
&= \exp(\alpha_m)\sum_{y_i\ne f_m(x_i)}p_{mi} -\exp(-\alpha_m)\sum_{y_i\ne f_m(x_i)}p_{mi}\\
&\quad + \exp(-\alpha_m)\sum_{y_i\ne f_m(x_i)}p_{mi} + \exp(-\alpha_m)\sum_{y_i=f_m(x_i)}p_{mi}\\
&= (\exp(\alpha_m)-\exp(-\alpha_m))\sum_{i=1}^Np_{mi}I(y_i\ne f_m(x))+\exp(-\alpha_m)\sum_{i=1}^Np_{mi}
\end{aligned}
$$
其中,$\sum_{i=1}^Np_{mi}$ 可以被拆分为两部分,一部分是预测正确的样本点,另一部分是预测错误的样本点,即:
$$
\begin{aligned}
\sum_{i=1}^Np_{mi} &= \sum_{i=1}^Np_{mi}I(y_i \ne f_m(x)) + \sum_{i=1}^Np_{mi}I(y_i = f_m(x))\\
&= \sum_{y_i\ne f_m(x_i)}p_{mi} + \sum_{y_i = f_m(x_i)}p_{mi}
\end{aligned}
$$
然后基于上文中改写后的损失函数求解最佳的参数 $\alpha_m$ ,能够使得损失函数取得最小值。对损失函数中的 $\alpha_m$ 求导,并令导函数为 0:
$$
\begin{aligned}
\frac{\partial L(y,F(x))}{\partial\alpha_m} &= (\exp(\alpha_m)+\exp(-\alpha_m))\sum_{i=1}^Np_{mi}I(y_i\ne f_m(x))-\exp(-\alpha_m)\sum_{i=1}^Np_{mi}\\
&= \exp(\alpha_m)\sum_{i=1}^Np_{mi}I(y_i\ne f_m(x)) - \exp(-\alpha_m)\sum_{i=1}^Np_{mi}I(y_i = f_m(x))
\end{aligned}
$$
导函数为 0 ,有:
$$
\exp(\alpha_m)\sum_{i=1}^Np_{mi}I(y_i\ne f_m(x)) = \exp(-\alpha_m)\sum_{i=1}^Np_{mi}I(y_i = f_m(x))
$$
等式两边同乘 $\exp(\alpha_m)$ ,两边同除 $\sum_{i=1}^Np_{mi}I(y_i\ne f_m(x))$,得:
$$
\exp(2\alpha_m) = \frac{\sum_{i=1}^Np_{mi}I(y_i = f_m(x))}{\sum_{i=1}^Np_{mi}I(y_i\ne f_m(x))}
$$
两边取对数,得:
$$
2\alpha_m = \ln\frac{\sum_{i=1}^Np_{mi}I(y_i = f_m(x))}{\sum_{i=1}^Np_{mi}I(y_i\ne f_m(x))}
$$
令 $e_m = \frac{\sum_{i=1}^Np_{mi}I(y_i\ne f_m(x))}{\sum_{i=1}^Np_{mi}}$,则得基础决策树的权重 $\alpha_m^*$ :
$$
\alpha_m^* = \frac12\ln\frac{1-e_m}{e_m}
$$
此时 $e_m$ 表示错误率。

3.3 基学习器的训练样本——最优 $w_{mi}$

在求得第 $m$ 轮基础决策树 $f_m(x)$ 以及对应的权重 $\alpha_m$ 后,便可得到经 $m$ 次迭代后的提升树 $F_m(x) = F_{m-1}(x) + \alpha_m^*f_m(x)^*$ ,再根据 $p_{mi} = \exp[-y_iF_{m-1}(x_i)]$ ,进而可计算第 $m+1$ 轮基础决策树中样本点的权重 $w_{mi}$:
$$
w_{m+1,i} = w_{mi}\exp[-y_i\alpha_m^*f_m(x_i)^*]
$$
为了使样本权重单位化,需要将每个 $w_{m+1,i}$ 与所有样本点的权重和做商处理,即:
$$
w_{m+1,i}^* = \frac{w_{mi}\exp(-y_i\alpha_m^*f_m(x_i)^*)}{\sum_{i=1}^Nw_{mi}\exp(-y_i\alpha_m^*f_m(x_i)^*)}
$$
实际上,$\sum_{i=1}^Nw_{mi}\exp(-y_i\alpha_m^*f_m(x_i)^*)$ 就是第 $m$ 轮基础决策树的总损失值,然后将每一个样本点对应的损失值与总损失的比值用作样本点的权重。

前向分布算法在优化加法模型的问题中有奇效:因为学习的是加法模型,如果能够从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标函数式,那么就可以简化优化的复杂度。

可以认为 AdaBoost 算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二类分类学习方法。——李航 《统计学习方法》 8.3 节

4 操作步骤

4.1 分类问题步骤

AdaBoost 算法在解决分类问题中,它的核心就是不停地改变样本点的权重,并将每一轮的基础决策树通过权重的方式进行线性组合。该算法在迭代过程中需要进行如下四个步骤:

(1)在第一轮基础决策树 $f_1(x)$ 的构建中,会设置每一个样本点的权重 $w_{1i}$ 均为 $\frac1N$。

(2)计算基础决策树 $f_m(x)$ 在训练数据集上的误判率 $e_m=\sum_{i=1}^Nw_{mi}^*I(y_i\ne f_m(x_i))$。

(3)计算基础决策树 $f_m(x)$ 所对应的权重 $\alpha_m^*=\frac12\ln\frac{1-e_m}{e_m}$。

(4)根据基础决策树 $f_m(x)$ 的预测结果,计算下一轮用于构建基础决策树的样本点权重 $w_{m+1,i}^*$ ,该权重可以写成:
$$
w_{m+1,i}^* = \begin{cases}
\frac{w_{mi}\exp(-\alpha_m^*)}{\sum_{i=1}^Nw_{mi}\exp(-\alpha_m^*)}, f_m(x_i)^*=y_i\\
\frac{w_{mi}\exp(\alpha_m^*)}{\sum_{i=1}^Nw_{mi}\exp(\alpha_m^*)}, f_m(x_i)^*\ne y_i
\end{cases}
$$
在如上的几个步骤中,需要说明三点:

  • 第一是关于基础决策树误判率 $e_m$ 与样本点权重之间的关系,通过公式可知,实际上误判率 $e_m$ 就是错分样本点权重之和;
  • 第二是关于权重 $\alpha_m^*$ 与基础决策树误判率 $e_m$ 之间的关系,只有当第 $m$ 轮决策树的误判率小于等于 0.5 时,该基础决策树才有意义,即误判率 $e_m$ 越小于 0.5,对应的权重 $\alpha_m^*$ 越大,进而说明误判率越小的基础树越重要;
  • 第三是关于样本点权重的计算,很显然,根据公式可知,在第 $m$ 轮决策树中样本点预测错误时对应的权重是预测正确样本点权重的 $\exp(2\alpha_m^*)$ 倍,进而可以使下一轮的基础决策树更加关注错分类的样本点。

4.2 回归问题步骤

AdaBoost 算法也可以处理回归问题,对于回归提升树来说,它的核心就是利用第 $m$ 轮基础树的残差值拟合第 $m+1$ 轮基础树。算法在迭代过程中需要进行如下四个步骤:

(1)初始化一棵仅包含根节点的树,并寻找到一个常数能够使损失函数达到极小值。

(2)计算第 $m$ 轮基础树的残差值 $r_{mi}=y_i-f_m(x_i)$。

(3)将残差值 $r_{mi}$ 视为因变量,再利用自变量的值对其构造第 $m+1$ 轮基础树 $f_{m+1}(x)$。

(4)重复步骤(2)和(3),得到多棵基础树,最终将这些基础树相加得到回归提升树 $F(x) = \sum_{m=1}^Mf_m(x)$。

sklearn.ensemble.AdaBoostRegressor 或 sklearn.ensemble.AdaBoostClassifier 可以使用 AdaBoost 进行分类或回归任务。

最后修改:2023 年 01 月 18 日
如果觉得我的文章对你有用,请随意赞赏