提升算法总结

对于一个特定机器学习问题，我们可能会建立很多模型，这些单个模型可能表现都不是非常好，由此便会引出一个问题:

问题1: 能否通过一个算法将这些模型组合起来(Ensemble)，产生一个效果更好的组合模型？

这个问题的答案是肯定的，历史上，Kearns 和 Valiant首先提出了“弱可学习”和“强可学习”的概念：

强可学习： 在概率近似正确(PAC)框架下，一个概念(类)，如果存在一个多项式的学习算法能够学习它，并且正确率很高，就称这个概念是强可学习的
弱可学习： 一个概念，如果存在一个多项式的算法能够学习它，但学习的正确率仅仅比随机猜测好，则称该概念是弱可学习

后来Schapire证明了一个重要结论:

一个概念是强可学习的 $\Leftrightarrow$ 一个概念是弱可学习的

这样一来，问题1就转换成了另一个问题:

问题2: 在学习中国，如果已经发现了“弱可学习算法”，那么能否将它提升为强可学习算法？

该部分介绍以下几类提升算法:

• Bagging
• AdaBoost
• 随机森林
• 提升算法解释
• 总结

Bagging

对于一个训练数据集，如果我们将所有的训练集数据拿来训练，那么我们便只能得到一个模型，因此Bagging的思想非常简单：

每次从训练数据集中取一部分数据来训练模型，通过这种方式得到多个模型，最后的决策结果则由这些模型投票表决

算法流程如下:

• Step1: 从包含$n$个样本的数据集中取$m$个样本作为新的训练集
• Step2: 用挑选出的数据集来训练得到一个模型
• Step3: 重复Step1 L次，得到L个模型
• Step4: 最终决策结果由这$L$个模型多数投票得到

AdaBoost

算法流程

Bagging的思想比较简单粗暴，所有样本都一视同仁，而另一种思路则是改变训练数据的概率分布(训练数据的权值分布)，针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。这样，对于提升算法而言，有两个问题需要回答：

• 在每一轮如何改变训练数据的权值或概率分布
• 如何将这些弱分类器组合成一个强分类器

AdaBoost针对这两个问题的的解决方案是:

• 第1个问题: 提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类的样本的权值。这样一来，那些没有得到正确分类的数据由于权值加大而受到后一轮弱分类器的更多关注。
• 第2个问题：AdaBoost采用加权表决的方法,加大分类误差率小的弱分类器的权值。

AdaBoost算法流程如下:

AdaBoost算法
输入： 训练数据集$T = { (x_1,y_1), (x_2,y_2),\dots, (x_N,y_N)}$,其中$x_i \in R^n, y_i \in { -1, +1 }$,弱学习算法
输出： 最终分类器$G(x)$

1. 初始化训练数据的权值分布 $$D_1 = (w_{11}, \dots, w_{1i}, \dots,w_{1N}), w_{1i} = \frac{1}{N}$$
2. 对于$m = 1,2,\dots,M$
   • 使用具有权值分布$D_m$的训练数据集学习，得到基本分类器 $$G_m(x): \mathcal{X} \rightarrow \{ -1, +1 \}$$
   • 计算$G_m(x)$ 在训练数据集上的分类误差率 $$e_m = \sum_{i=1}^N P(G_m(x_i) \neq y_i) = \sum_{i=1}^N w_{mi} I(G_m(x_i) \neq y_i)$$
   • 计算$G_m(x)$的系数: $$\alpha_m = \frac{1}{2} \log \frac{1 - e_m}{e_m}$$
   • 更新训练数据集的权值分布 $$\begin{aligned} D_{m+1} &= (w_{m+1,1},\dots, w_{m+1,i}, \dots,w_{m+1,N}) \\ w_{m+1,i} &= \frac{w_{m+1,i}}{Z_{m}} \exp(- \alpha_m y_i G_m(x_i)) \\ Z_m &= \sum_{i=1}^N w_{mi} \exp(-\alpha_m y_i G_m(x_i)) \end{aligned}$$
   • 构建基本分类器的线性组合: $$f(x) = \sum_{m=1}^M \alpha_m G_m(x)$$ 得到最终分类器： $$G(x) = sign(f(x)) = sign(\sum_{m=1}^M \alpha_m G_m(x))$$

下面对AdaBoost算法说明如下:

• 在最开始假设训练数据具有均匀的权值分布，即每个训练样本在基本分类器中的作用相同，这一假设保证第一步能够在原始数据上学习基本分类器$G_1(x)$
• AdaBoost反复学习基本分类器，在每一轮弱分类器训练中，首先使用当前分布$D_m$加权的训练数据集，学习基本分类器$G_m(x)$,使用加权数据进行训练，最终学得的分类器更加关注权重较高的数据，接下来计算该基本分类器$G_m(x)$在加权训练数据集上的分类误差率,然后通过该误差率计算分类器$G_m(x)$的权重，从权重计算公式可以看出，当$e_m \leq 0.5$(弱分类器前提假设)时，$\alpha_m \geq 0$,且随着$e_m$减小，$\alpha_m$会不断增大。
• 接下来更新训练数据的权值，对于被分类器$G_m(x)$分类正确的样本，增加其权重，反之减少其权重。不改变所给的训练数据，而是不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同作用。
• 最终的组合分类器是一个基本分类器的线性组合形式，$f(x)$的符号决定了实例$x$的类，而$f(x)$的绝对值则显示了分类结果的置信度。

算法理论说明

上一部分从算法思想来对AdaBoost进行理解，这一部分将从理论推导方面证明AdaBoost中的一些关键公式是如何来的，比如：

• 分类器权重$\alpha_m = \frac{1}{2} \log \frac{1-e_m}{e_m}$
• 样本点权重更新公式： $$\begin{aligned} D_{m+1} &= (w_{m+1,1},\dots, w_{m+1,i}, \dots,w_{m+1,N}) \\ w_{m+1,i} &= \frac{w_{m+1,i}}{Z_{m}} \exp(- \alpha_m y_i G_m(x_i)) \\ Z_m &= \sum_{i=1}^N w_{mi} \exp(-\alpha_m y_i G_m(x_i)) \end{aligned}$$

AdaBoost算法训练误差界

首先来推导下AdaBoost的训练误差界，样本$x_i$ 在第$t$轮训练时的权重，由样本点权重递推公式可以得到：

$$w_{t+1i} = w_{ti} \frac{e^{-\alpha_t y_i h_t(i)}}{Z_{t}} = \dots = w_{1i} \frac{e^{-y_i \sum_{j=1}^t \alpha_j h_j(i)}}{\prod_{i=1}^{t} Z_i}$$

其中$w_{1i} = \frac{1}{N}$,若记：

$$\boldsymbol{\alpha} = [\alpha_1,\alpha_2,\dots, \alpha_t], \boldsymbol{h(x)} = [h_1(i),h_2(i),\dots, h_t(i)]$$

$w_{t+1i}$可以写成更加紧凑的形式:

$$w_{t+1i} = \frac{e^{-y_i <\boldsymbol{\alpha}, \boldsymbol{h(x)}>}}{N \prod_{i=1}^t Z_i}$$

又因为有$\sum{i=1}^N w{t+1i} = 1$,对上式求和后可得：

$$\prod_{i=1}^t Z_i = \frac{1}{N} \sum_{i=1}^N e^{-y_i <\boldsymbol{\alpha}, \boldsymbol{h(x)}>}$$

需要注意的是，$<\boldsymbol{\alpha}, \boldsymbol{h(x)}>$刚好是使用AdaBoost最终得到模型的预测结果(未取sign)，下面考虑两种情况：

$$\begin{aligned} &If \quad sign(<\boldsymbol{\alpha}, \boldsymbol{h(x_i)}>) = h(x_i) = y_i \Rightarrow <\boldsymbol{\alpha}, \boldsymbol{h(x)}> \cdot y_i = c \geq 0 , 0 \leq e^{-c} \\ &If \quad sign(<\boldsymbol{\alpha}, \boldsymbol{h(x_i)}>) = h(x_i) \neq y_i \Rightarrow <\boldsymbol{\alpha}, \boldsymbol{h(x)}> \cdot y_i = c \leq 0 , 1 \leq e^{-c} \end{aligned}$$

而AdaBoost最终训练得到的模型的分类误差为:

$$\epsilon = \frac{1}{N}\sum_{i=1}^N \epsilon_i, \epsilon_i = \begin{cases} 1 & h(x_i) \neq y_i \\ 0 & h(x_i) = y_i \end{cases}$$

从前面两种分类讨论可以得到:

$$\epsilon_i \leq e^{-y_i <\boldsymbol{\alpha}, \boldsymbol{h(x_i)}>}$$

由此便可以得到AdaBoost分类器的分类错误率上界：

$$\epsilon = \frac{1}{N}\sum_{i=1}^N \epsilon_i \leq \frac{1}{N} \sum_{i=1}^N e^{-y_i <\boldsymbol{\alpha}, \boldsymbol{h(x_i)}>} = \prod_{i=1}^t Z_i$$

$\alpha_t^\ast$ 推导

需要注意的是，我们上面并未指定权重$\alpha$的表达式，那么现在我们考虑这样一个问题:

$\alpha$取什么值时分类错误率的上界可以尽可能小

因为$Z_i$的大小依赖于$\alpha_i$，而且它们都是迭代过程中的变量，因此可以考虑将上述问题转化为:

如何在每一步迭代中选择合适的$\alpha_t$使得$Z_t$尽可能小

$Z_t$的表达式如下:

$$Z_t = \sum_{i=1}^N w_{ti} e^{-\alpha_t y_i h_t(x_i)}$$

这是一个凸函数，因此可以直接求导令导数等于0：

$$\frac{\partial Z_t}{\partial \alpha_t} = -\sum_{i=1}^N w_{ti} y_i h_t(x_i) e^{-\alpha_t y_i h_t(x_i)} = 0$$

下面考虑两个集合：

$$A = y_i h_t(x_i) = 1, \bar{A} = y_i h_t(x_i) = -1$$

据此，上面的偏导可以写成:

$$\frac{\partial Z_t}{\partial \alpha_t} = -\sum_{x_i \in A} w_{ti} e^{-\alpha_t} + \sum_{x_i \in \bar{A}} w_{ti} e^{\alpha} = 0$$

由此可得:

$$e^{2\alpha_t} = \frac{\sum_{x_i \in A} w_{ti}}{\sum_{x_i \in \bar{A}} w_{ti}} = \frac{1 -\epsilon_t}{\epsilon_t}$$

求得$\alpha_t$的最优取值为:

$$\alpha_t^\ast = \frac{1}{2} \log \frac{1 - \epsilon_t}{\epsilon_t}$$

至此我们便理解了每一步迭代$\alpha_t$表达式的来源，该表达式刚好可以保证最终得到的分类器错误率上界尽可能小(局部最小)。

训练误差界(二分类问题)

对于一个二分类问题，则可以将$Z_t$的表达式直接写出:

$$Z_t = 2 \sqrt{e_t(1 - e_t)}$$

令$e_t = \frac{1}{2} - \gamma_t$,则可得：

$$Z_t = \sqrt{1 - 4 \gamma_t^2} \leq e^{-2 \gamma_t^2}$$

由此便可得分类错误率上界为:

$$\prod_{i=1}^t Z_i \leq e^{-2 \sum_{i=1}^t \gamma_t^2}$$

据此可以得到推论:

推论： 如果存在$\gamma >0$,对所有$i$有，$\gamma_i \geq \gamma$,则有：

$$\frac{1}{N} \sum_{i=1}^N I(h(x_i) \neq y_i) \leq \exp(-2N\gamma^2)$$

这说明对于二分类问题，AdaBoost的训练误差是指数速率下降的。

tips:

• 对于无法接受带权样本的基学习算法，可以通过重采样法来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，变相实现带权样本，两种做法没有本质区别。
• Boosting算法在训练的每一轮都需要检查当前生成的基学习器是否满足条件(比随机猜测要好)，若不满足，则抛弃该基学习器，学习过程停止，若采用”重采样法”，则可获得“重启动机会”，避免算法过早停止。

随机森林

随机森林算法其实就是以决策树算法作为基学习算法，选用Bagging策略作为提升策略，最终得到的一个算法，可以这么理解:

$$随机森林 = 决策树 + Bagging$$

随机森林算法简单、容易实现、计算开销小，令人惊奇的是，它在很多现实任务中展现了强大的性能，被誉为“代表集成学习技术水平的方法”。
不过传统的Bagging算法仅仅是在训练样本上引入随机性，而随机森林往往考虑在属性选择上引入随机性，具体做法是:原始的决策树算法是从该节点所有属性中选择一个最优属性进行节点分裂，而作为基学习器，为进一步引入随机性，一般会规定从当前节点所有属性中随机选$k$个，然后从这$k$个属性中选择一个最优的来分裂节点，若该节点有$d$个属性，常见的$k$的取值为$k = \log_2 d$

提升算法解释

学习器结合可能会从三个方面带来好处:

• 从统计的方面来看，由于学习任务的假设空间往往非常大，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器会减少这一风险。
• 从计算角度来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能非常糟糕，而通过多次运行之后进行结合，可降低陷入糟糕极小点的风险。
• 从表示的方面来看，某些学习任务的真实假设可能不在当前学习算法s所考虑的假设空间中，此时若使用单学习器肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似。

总结

该部分主要总结下两个方面的内容，一个是结合策略的选择，另一个则是引入扰动的思路。

结合策略

结合策略主要有以下几种:

• 平均法,包括简单平均法和加权平均法，一般而言，在个体学习器性能相差较大时，加权平均法表现较好，在个体学习器性能接近时采用简单平均法较好。
• 投票法,包括绝对多数投票法(设定得票率阈值)，相对多数投票法，加权投票法
• 学习法，即通过另一个学习器来结合这些基于学习器，该学习器被称为元学习器或者次级学习器，基学习器被称作初级学习器，初级学习器的输出作为次级学习器的输入。

引入扰动

常见的引入扰动的思路有如下几种:

• 数据样本扰动
• 输入属性扰动
• 输出表示扰动
• 算法参数扰动