前言

自从在香港的检疫隔离十四天期满之后就没有更新过博客了。

今天，阿南他来了！

嘟嘟嘟！ 今天要给大家讲的是现在工业界应用最为广泛、效果最好的机器学习算法之一 提升算法 (Boosting)

这次以代表性的提升算法 AdaBoost 为例给大家介绍提升算法的思路，以及给出提升方法具体的实现实例。

AdaBoost 算法

首先先介绍一下啥子是 提升方法。

提升方法： 通过弱学习算法出发，通过反复训练学习得到一系列基本分类器，然后通过线性组合这些基本分类器，最后得到一个强分类器。

具体怎么理解呢？我试着用一个简单的例子去说明这个问题。

想象高三冲刺季，数学老师发了一张特别难的卷子给全班同学去做，并且允诺，只要卷子总分能打140分以上就给全班同学买一杯 ❤芋泥啵啵奶茶❤ 全班为之沸腾！

然鹅拿到卷子一康，发现好多题都不会做！难道全班都要与 ❤芋泥啵啵奶茶❤ 失之交臂了吗！？

🙅‍♂️ 不可以！ 🙅‍♂️

热爱奶茶（学习）的同学们想出了一个好主意：就是全班轮着做这张卷子。上一个同学做完了之后，下一个同学在之前的结果上去做，不断地修正之前的错误，最后集全班同学的智慧交出一张高分答卷！

上面的这种思想就是 集成学习 的核心思想，集中力量办大事，办好事，办实事！

而提升方法之中的代表性算法 AdaBoost 的全称为 Adaptive Boosting，意为可以通过自适应的的方法进行提升。

其特点是每个训练实例都被赋予一个权值，通过提高前一轮被基本分类器错误分类的样本的权值并降低分类正确样本的权值，使得随后的基本分类器能够更加关注先前被分类错误的样本，并进行针对性训练进一步减小分类误差率。 同时，AdaBoost 采用的是 加权多数表决规则。

假定一个二分类的训练数据集： \(T = \{(x_1, y_1),(x_2,y_2),...,(x_N,y_N)\}\)

其中 $x_i\in \chi \subseteq \boldsymbol{R}^n,\ \ y_i\in \gamma \subseteq {1, -1}$。

接下来我将详细描述 AdaBoost 是如何利用训练数据集学习一系列基本分类器，并将这些基本分类器组合成为一个强分类器的。

输入： 训练集 $T$，弱学习算法。

输出： 最终分类器（强学习器）

1. 初始化各个实例 $x_i$ 的权重分布 $D_1$: \(D_1 = (w_{11}, w_{12, ..., w_{1i}, ..., w_{1N}}), \qquad w_{1i} = \frac{1}{N}, \qquad i=1,2,...,N\)

2. 对第 $m$ 次训练， $m=1,2,…,M$：

   (a) 使用具有权值分布 $D_M$ 的训练数据集学习，得到基本分类器 $G_m(x)$

   (b) 计算 $G_m(x)$ 在训练集上的分类误差率： \(e_m = \sum_{i=1}^N P(G_m(x_i) \ne y_i) = \sum_{i=1}^N w_{mi}I(G_m(x_i) \ne y_i) \tag{1}\) 这里我们可以看出，每个基本分类器 $G_m$ 的分类误差率 $e_m$ 是所有被错误分类实例的权重之和。

   (c) 计算当前基本分类器 $G_m(x)$ 的系数 $\alpha_m$，其表示了基本分类器 $G_m(x)$ 的重要性 \(\alpha_m = \frac{1}{2} \ln \frac{1-e_m}{e_m} \tag{2}\)

   (d) 更新第 $m+1$ 次训练数据集的权值分布 $D_m = (w_{m+1,1},w_{m+1,2},…,w_{m+1, i},…,w_{m+1,N})$:

   \[w_{m+1,i} = \frac{w_{mi}}{Z_m}\exp(-\alpha_m y_i G_m(x_i)), \qquad i=1,2,...,N \tag{3}\]

   上式中的 $Z_m$ 是规范化因子，其作用是让数据集的权值分布 $D_m$ 变成一个 $\sum_{i=1}^N w_{mi}=1$ 的概率分布： \(Z_m = \sum_{i=1}^N w_{mi} \exp(-\alpha_m y_i G_m(x_i)) \tag{4}\)

3. 构建基本分类器的线性组合： \(f(x) = \sum_{m=1}^M \alpha_m G_m(x) \tag{5}\) 得到最终分类器 $G(x)$： \(\begin{aligned} G(X) & = sign(f(x)) \\ & = sign(\sum_{m=1}^M \alpha_m G_m(x)) \end{aligned} \tag{6}\) 可以看出，$f(x)$ 的符号决定实例 $x$ 的类别，$f(x)$ 的绝对值表示分类的确信度。

接下来给出一个例子来可视化滴讲解吧！假设我们拥有如下数据集：

阔以看到它只有红蓝两个类别，但是叻很难通过一个线性的分类器直接获得很好的效果，于是我们先用一个简单的决策树桩（这就是第一个基本分类器）对其进行第一次切分：

但是这么一刀切下去的结果并不是很理想，我们也能看到，其只能沿着 $x$ 轴或 $y$ 轴方向进行切割，因为这是一个二维的数据，只有两个特征维度。

于是乎，我们以各个实例 $x_i$ 初始权重 $w_{1i}=\frac{1}{N}$ 训练后得到了第一个基本分类器 $G_1(x)$，并计算出 $G_1(x)$ 的系数 $\alpha_1$ 以及下一轮各个实例 $x_i$ 的权值分布 $D_2$。

随后根据权值分布 $D_2$ 我们继续训练下一个基本分类器 $G_2(x)$

发现这一次是选择了 $y$ 轴方向的特征进行切分，类似地，我们得到了第二个基本分类器 $G_2(x)$ 并需要继续计算 $G_2(x)$ 的系数 $\alpha_2$ 以及下一轮各个实例 $x_i$ 的权值分布 $D_3$。

一直根据上述步骤训练下去，直到某个基本分类器 $G_m(x)$ 的训练误差满足要求时停止。

接下来我用动画演示一下吧~

接下来我在李航老师的基础上对 AdaBoost 的 训练误差界 进行推导：

首先给出结论：

\[\frac{1}{N} \sum_{i=1}^N I(G(x_i) \ne y_i) \le \frac{1}{N} \sum_{i} \exp (-y_i f(x_i)) = \prod_m^M Z_m \tag{7}\]

证明： 当 $G_(x_i) \ne y_i$ 时，$y_if(x_i)\le 0$，因此 $e^{-y_if(x_i)} \ge 1$。既证式 $(7)$ 的左半部分等式。

对于后半部分证明首先给出两个等式：

1. 初始样本权重 $w_{1i}=\frac{1}{N}$
2. $w_{m+1,i} = \frac{w_{mi}}{Z_m} \exp (-\alpha_m y_i G_m(x_i))$

接着进行如下证明： \(\begin{aligned} \frac{1}{N} \sum_{i} \exp (-y_i f(x_i)) & = \frac{1}{N} \sum_{i} \exp (-\sum_{m=1}^M \alpha_m y_i G_m(x_i)) \\ & = \sum_i w_{1i} \prod_{m=1}^M \exp (\alpha_m y_i G_m(x_i)) \\ & = \sum_i w_{1i} \exp (\alpha_1 y_i G_1(x_i)) \prod_{m=2}^M \exp (\alpha_m y_i G_m(x_i)) \\ & = Z_1 \sum_i w_{2i} \exp (\alpha_2 y_i G_2(x_i)) \prod_{m=3}^M \exp (\alpha_m y_i G_m(x_i)) \\ & = Z_1 Z_2 \sum_i w_{3i} \exp (\alpha_3 y_i G_3(x_i)) \prod_{m=4}^M \exp (\alpha_m y_i G_m(x_i)) \\ & = \cdots \qquad \cdots \\ & = \prod_{m=1}^M Z_m \end{aligned} \tag{8}\)

从上述推到中可以看出，我们可以通过在每一轮都选取适当的基本分类器 $G_m(x)$ 使得总误差 $\prod_{m=1}^M Z_m$ 最小。

同时对于二分类问题还有如下结果：

\[\begin{aligned} \prod_{m=1}^M Z_m & = \prod_{m=1}^M [2\sqrt{e_m(1-e_m)}] \\ & = \prod_{m=1}^M \sqrt{(1-4\gamma_m^2)} \\ & \le \exp (-2\sum_{m=1}^M \gamma_m^2) \end{aligned} \tag{9}\]

证明如下：

首先根据式 $(4)$ ：$Z_m = \sum_{i=1}^N w_{mi} \exp(-\alpha_m y_i G_m(x_i))$ 易知：

• 当 $y_i= G_m(x)$ 时，$y_iG_m(x_i)=1$
• 当 $y_i\ne G_m(x)$ 时，$y_iG_m(x_i)=-1$

改写式 $(4)$ ： \(Z_m = \sum_{y_i=G_m(x_i)} w_{mi} e^{-\alpha_m} + \sum_{y_i\ne G_m(x_i)} w_{mi} e^{\alpha_m} \tag{10}\)

又因为分类误差率 $e_m = \sum_{i=1}^N w_{mi}I(G_m(x_i) \ne y_i)$，再次改写式 $(10)$： \(Z_m = (1-e_m)e^{-\alpha_m} + e_m e^{\alpha_m} \tag{11}\)

又因为 $\alpha_m = \frac{1}{2} \log \frac{1-e_m}{e_m}$，可得 $e^{-\alpha_m} = e^{-\frac{1}{2}\log \frac{1-e_m}{e_m}} = \sqrt{\frac{e_m}{1-e_m}}$。

同理 $e^{\alpha_m} = e^{\frac{1}{2}\log \frac{1-e_m}{e_m}} = \sqrt{\frac{1-e_m}{e_m}}$

再次改写式 $(11)$： \(\begin{aligned} Z_m & = (1-e_m) \sqrt{\frac{e_m}{1-e_m}} + e_m \sqrt{\frac{1-e_m}{e_m}} \\[2ex] & = 2\sqrt{e_m(1-e_m)} \\[2ex] & = \sqrt{(1-4\gamma_m^2)} \end{aligned} \tag{12}\)

此处 $\gamma_m = \frac{1}{2} - e_m$

同时由 $e^x$ 和 $\sqrt{1-x}$ 在 $x=0$ 处的泰勒展开式可以得到不等式： \(\sqrt{(1-4\gamma_m^2)} \le e^{-2\gamma_m^2} \tag{13}\)

即证明式 $(9)$ 最后一步的结论： \(\prod_{m=1}^M \sqrt{(1-4\gamma_m^2)} \le \exp (-2\sum_{m=1}^M \gamma_m^2)\)

该结论也表明了 AdaBoost 的训练误差式以指数的速度下降的，这个极其吸引人的性质也是 AdaBoost 在业界广泛使用的原因之一。

同时，我们还可以认为 AdaBoost 是前向分布算法的一个特例实现。在这个算法中，模型是 加法模型，损失函数是 指数损失，算法是 前向分布算法。

即：

加法模型： \(f(x) = \sum_{m=1}^M \alpha_m G_m(x;\gamma_m) \tag{14}\)

其中 $G_m(x;\gamma_m)$ 为基函数， $\gamma_m$ 为第 $m$ 个基函数的参数，$\alpha_m$ 为第 $m$ 个基函数的系数。

其损失函数是 指数损失函数： \(L(y,f(x)) = e^{-yf(x)} \tag{15}\)

对模型的 优化方法 采用的是 经验风险最小化，即最小化损失函数：

\[\min_{\alpha_{m},G_{m}(x)} L(y,f(x)) = \min_{\alpha_{m},G_{m}(x)} e^{-yf(x)} \tag{16}\]

具体应用 $AdaBoost$ 框架时通常以 分类树 或 回归树 作为基本分类器。

以决策树为基函数的提升方法称之为 提升树 (Boosting Tree)。对分类问题决策树选用的是 二叉分类树，对回归问题决策树选用的是 二叉回归树。

提升数模型可以表示为决策树的加法模型：

\[f_M (x) = \sum_{m=1}^M T(x;\Theta_m) \tag{17}\]

其中，$T(x;\Theta_m)$ 表示第 $m$ 棵基本决策树，$\Theta_m$ 为其对应的决策树参数（分类特征，分裂点，叶子节点的取值等），$M$ 表示最终的强分类器 $f_M(x)$ 中树的数量。

提升书算法采用前向分布算法，首先确定初始的提升书 $f_0(x)=0$，第 $m$ 步的模型是：

\[f_m(x) = f_{m-1}(x) + T(x;\Theta_m) \tag{18}\]

其中，$f_{m-1}(x)$ 是当前模型，通过经验风险最小化确定下一棵决策树的参数 $\Theta_m$（分类特征，分裂点，叶子节点的取值等）:

\[\hat \Theta_m = \arg \min_{\Theta{m}} \sum_{i=1}^N L(y_i,f_{m-1}(x_i) + T(x_i;\Theta_m)) \tag{19}\]

观察上式可知，我们所期望的是找到这么一颗新的基本决策树能够使得所有实例 $x_i$ 在其的累加损失值最小。

对于 二分类问题，我们只需在之前所提到的 $AdaBoost$ 中的基本分类器替换成 二类分类树 即可，此时的提升树算法只是 $AdaBoost$ 的一种特殊情况，大家可自行体会。

接下来讲一讲对于 回归问题的提升树算法：

假设我们拥有一个训练数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)},\ x_i\in \chi \subseteq R^n$ 现在如果我们将输入空间 $\chi$ 划分为 $J$ 个互不相交的区域 $R_1, R_2,…,R_J$，划分区域的方法就是遍历所有特征 $m$ 与切分点 $s$，求解：

\[\min_{m,s} \left[\min_{c_1} \sum_{x_i\in R_1(m,s)}(y_1-c_1)^2 + \min_{c_2} \sum_{x_i\in R_2(m,s)}(y_i-c_2)^2 \right] \tag{20}\]

并且每个区域的输出为 $c_j$ （这里的输出 $c_j$ 之前已经讲过了，就是把对应区域 $R_i$ 上的样本子集的输出求平均即可），那么这棵树可以写为：

\[T(x;\Theta) = \sum_{j=1}^J c_j I(x\in R_j) \tag{21}\]

这里的参数 $\Theta = {(R_1,c_1),(R_2,c_2),…,(R_J,c_J)}$，分别表示每棵树的区域划分和各个区域上的输出。$J$ 表示回归树的复杂度（叶节点个数）。

同样地，我们还是需要根据损失函数最小化的原则计算决策树的参数 $\hat \Theta_m$，即：

\[\hat \Theta_m = \arg \min_{\Theta{m}} \sum_{i=1}^N L(y_i,f_{m-1}(x_i) + T(x_i;\Theta_m)) \tag{22}\]

如果使用平方误差作为损失函数的话：

\[L(y,f(x)) = (y - f(x))^2 \tag{23}\]

将式 $(18)$ 带入上式得：

\[\begin{aligned} L(y, f_{m-1}(x) + T(x; \Theta_m)) & = [y - f_{m-1}(x) - T(x; \Theta_m)]^2 \\[2ex] & = [r - T(x; \Theta_m)]^2 \end{aligned} \tag{24}\]

上式中的 $r$ 代表上一个模型 $f_{m-1}(x)$ 拟合数据的残差值，即 $r = (y - f_{m-1}(x))$，所以对于回归问题的提升树算法只需简单地拟合上一个模型的残差即可。

更普适地讲，提升回归树 (Boosting Tree) 是通过拟合上一个模型的残差的方式，使得全局强学习器达到最优的这么一个过程，不论采用的是什么损失函数。

同时提升回归树对于所有的样本权重都是 $1$，并且隐式地将每个基本分类器（回归树）前的系数给包含在每棵树 $J$ 个互不相交的区域 $R_1, R_2,…,R_J$ 的输出为 $c_j$ 里面了，使得需要计算的参数数量大大减少。

现将回归问题的提升树算法归纳如下：

输入： 训练数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)},\ x_i\in \chi \subseteq R^n, \ y_i\in \gamma \subseteq R$

输出： 提升树 $f_M(x)$

1. 初始化 $f_o(x) = 0$

2. 对所有基本分类器 $m=1,2,…,M$

   (a) 计算残差： \(r_{mi} = y_i - f_{m-1}(x_i), \qquad i=1,2,...,N \tag{25}\)

   (b) 拟合残差 $r_{mi}$ 学习一个回归树，得到 $T(x;\Theta_m)$

   (c) 更新 $f_m(x) = f_{m-1}(x) + T(x;\Theta_m)$

3. 得到针对回归问题的提升树

   \[f_M(x) = \sum_{m=1}^M T(x;\Theta_m) \tag{26}\]

现在对 提升树 (Boosting Decision Tree, BDT) 做一个小结：

首先 提升树 (Boosting Decision Tree, BDT) 分为 分类提升树 和 回归提升树。

对于 分类提升树，其基本步骤与原理与之前对于 $AdaBoost$ 基本一致，只需把 $AdaBoost$ 框架中的基本分类器 $G_m(x)$ 换成分类决策树即可，其余关于样本权重的计算以及每个基本分类器的系数 $\alpha_m$ 的计算与 $AdaBoost$ 所描述的一致。

对于 回归提升树，与传统 $AdaBoost$ 不一样的就是，回归提升树的训练模式是每轮训练都是针对上一个分类器拟合数据后的残差 $r_{mi}$ 进行拟合，同时在回归提升树中 **每个样本实例 $x_i$ 的权重都为 $1$，并且每个基本分类器的系数也都为 $1$。这是因为在计算的时候已经将样本权重及分类器系数给隐式地整合至计算回归树每个区域 $R_j$ 中的输出中去了。

关于权重我们可以这样理解，每一步的残差计算其实变相地增大了被分错实例的权重，而已经正确划分的实例其误差都趋向于 $0$。经过这样的操作，后面的树就能越来越专注那些前面被分错的实例。

同时注意，提升树 (Boosting Decision Tree, BDT) 并不等价于时下最流行的 梯度提升树 (Gradient Boosting Decision Tree, GBDT)，关于 GBDT 我会单独再开一个博客来写！敬请期待！

总结

到这里相信大家对 AdaBoost 已经有一个详细的了解啦！ 接下来我们对其进行一个课后小总结！

优点：

1. $AdaBoost$ 算法通过给已有模型预测错误的样本更高的权重，使得先前的学习器做错的训练样本在后续受到更多的关注的方式来弥补已有模型的不足。

2. 可以采用多种不同的方法构建不同的基本分类器，可以充分利用各种算法之间的优点，不用对特征进行筛选。

3. $Adaboost$ 不需要基本分类器 $G_m(x)$ 的先验知识，最后得到的强分类器 $G(x)$ 的分类精度依赖于所有基本分类器 $G_m(x)$ 。因此无论是应用于人造数据还是真实数据，$Adaboost$ 都能显著的提高学习精度。

4. $Adaboost$ 算法不需要预先知道基本分类器的错误率上限，且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，可以深挖分类器的能力。

缺点：

1. 经典的 $AdaBoost$ 算法只能处理采用指数损失函数的二分类学习任务

2. 在 $Adaboost$ 训练过程中，其会使得错误分类次数高的样本的权值呈指数增长。这将导致之后的训练会过于偏向这类困难的样本，意味着 $Adaboost$ 算法易受噪声干扰。

3. $Adaboost$ 每个基本分类器之间存在前后依赖关系，而基本分类器的训练时间往往很长。这导致生成强分类器的时间会变得很漫长。

如果损失函数是平方差损失函数，就在残差上做平方差拟合构造弱分类器; 如果是指数形式的损失函数，就在带权重的样本上构造弱分类器。

但损失函数如果不是这两种，问题就没那么简单，比如绝对差值 函数，虽然构造弱分类器也可以表示成在残差上做绝对差值拟合，但这个子问题本身也不容 易解，因为我们是要构造多个弱分类器的，所以我们当然希望构造弱分类器这个子问题比较 好解。因此，像 $AdaBoost$ 这种采用前向自适应建模 (Forward Stagewise Adaptive Modeling, FSAM) 思路无法推广到其他一些实用的损失函数上。因此接下来我们就会提出一种更加普适的方法——梯度提升法 (Gradient Boosting)。

接下来比较一下 支持向量机、AdaBoost， 逻辑回归 这三者之间的学习策略与算法：

	学习策略	算法
支持向量机	极小化加入正则项的合页损失函数	SMO序列最小优化算法
AdaBoost	极小化加法模型指数损失函数	前向分布加法算法
逻辑回归	极大化对数似然函数或正则化的对数似然函数	改进的迭代尺度算法，梯度下降法，拟牛顿法

好滴，阿南机器学习小课堂今天就到这里啦！

下次再见~

:)

---

• Previous
  阿南带你理解主成分分析法
• Next
  阿南带你理解隐马尔可夫模型