3月机器学习在线课程第九课笔记--Boosting

机器学习

---

特别感谢@肖雅夫提供的word版本笔记。此篇笔记是在其word版本笔记基础上修改的。

Boosting的由来

古语云：三个臭皮匠，顶一个诸葛亮。而在机器学习领域，集成算法Boosting就是一个活生生的实例。Boosting和之前介绍过的Bagging相似，都是集成算法之一。Boosting通过整合多个弱分类器，从而形成一个强分类器。具体如何构造，还需要有严谨的理论基础。
在1990年，RobertSchapire最先构造出了一种多项式级的算法，该算法可将若分类器组合成强分类器，即Boosting算法。一年后，Yoav Freund提出了一种效率更高的Boosting算法。但是这两个最初的Boosting算法存在缺陷：都要求实现知道弱学习算法学习正确率的下限。到了1995年，Freund和Schapire改进了Boosting算法，提出了AdaBoost(Adaptive Boosting)算法。该算法的优点：效率和Freund与1991年提出的Boosting算法几乎相同，但不需要任何关于弱学习器的先验知识，因而更加容易应用到实际问题中。
随后，两位创始人更进一步提出了AdaBoost.M1，AdaBoost.M2等算法，在机器学习领域受到了极大关注。Boosting在人脸识别、文本分类中应用较多。

Boosting的思想及流程

Boosting的思想是这样的：给定一份训练数据集（各样本权重是一样的，之后会有变化），然后进行M次迭代，每次迭代后，对分类错误的样本加大权重,对正确分类的样本减少权重，在下一次的迭代中更加关注错分的样本。
可以通过下面的图来了解其中的思想（假设训练集数据有三维特征：X、Y、Z）：

从上图可以看到，每一次迭代过后都会对训练集中的样本给予不同的权重。红色框框部分绿色面积较小的样本表示的是权重较小，表明在此次迭代中它被正确划分了。可以看到弱学习机的弱假设每一次都是针对某一特征进行假设，实际上就像是一个偏科的小孩（如语文好，数学英语较差，总体成绩较差）。但是有3个偏科的小孩，他们每人都有擅长的学科，那么经过分工合作，作为一个整体是有可能达到一个好成绩的。术业有专攻，就是这个道理。

流程如下：

• 给出任意一个弱学习算法和训练集$(x_1,y_1),(x_2,y_2),...,(x_n,y_n),x_i \in X, X$表示某个特征空间，$y_i \in Y = \{+1,-1\}$。
• 初始化时，需要根据特征空间中原始训练集的分布$D$来给每一个样本分配权值。（AdaBoost为训练样本指定分布为1/n，即每个训练样本的权重都相同）。
• 调用弱学习算法进行T次迭代，每次迭代后，按照训练结果更新训练集上的分布，对训练失败的训练样本赋予较大的权重，使得下一次迭代更加关注这些样本，从而得到一个基本分类器序列$k_1,k_2,...,k_t$,每个基本分类器$k_i$也赋予一个权重，预测效果好的，相应的权重越大。
• T次迭代之后，在分类问题中最终的分类器$K$采用带权重的投票法产生。

通过流程可以知道，迭代的过程有两个权重值得注意：一个是每一次都更新的训练样本的权重$w_i^{(m)}$，一个是基本分类器$h_m$的权重$\alpha_{m}$。单个基本分类器的学习准确率并不高，经过运用Boosting算法之后，最终的结果准确率将得到提高。

由于采用的Loss函数不同，Boosting算法也因此有了不同的类型，AdaBoost就是其中一类，更多的还有：

其中的符号稍有差异：

可以看到，L2Boosting、Gradient Boosting、AdaBoost和LogitBoost正是因为分别采用了Squared error、Absolute error、Exponential loss以及Logloss类型的Loss函数，而导致了算法的不一致。

AdaBoost的算法推导--前向算法解释

以AdaBoost为例，让我们来推导具体的算法过程及原理。观察上表，发现AdaBoost采用的是Exponential loss--$L(\tilde y,f) = exp(-\tilde y f)$，其中$\tilde y \in \{-1,+1\}$。也就是说，当错分的时候，cost为$e^{f}$；而正确分类时，cost为$e^{-f}$。我们现在还无法确定预测函数$f$的具体表达形式，但是可以知道潜在的要求是$f>0$,因为我们必须令错分时候的cost大一些，即满足$e^f > e^{-f}$。

假设在第m次迭代中，我们已经选出了m-1个基本分类器，这些分类器的线性组合表达形式如下：
$C_{m-1}(x_i) = \alpha_1k_1(x_i) + \alpha_2k_2(x_i)+...+\alpha_{m-1}k_{m-1}(x_i)$.
假设各参数具体表达形式已知，其中$\alpha_i$表示基本分类器的权重，基本分类器$k_i(x_i) \in \{-1,+1\}$。现在我们想要选择第m个基本分类器，将线性组合形式拓展为：
$C_{m}(x_i) =C_{(m-1)}(x_i) +\alpha_m k_m (x_i)$
但此时的$\alpha_m，k_m$并没有确定，需要通过最优算法求解得到。这个线性组合（强分类器）的Loss函数为：

$$E = \sum_{i=1}^n e^{-\tilde y_i (C_{(m-1)}(x_i) +\alpha_m k_m (x_i))}$$
可以重写上式为另一种形式：
$$E = \sum_{i=1}^n w_i^{(m)} e^{-\tilde y_i \alpha_m k_m (x_i)}$$
其中$w_i^{(m)} = e^{-\tilde y_i C_{(m-1)}(x_i)}$。

将上式拆分为两个表达式的和：

$$E = e^{-\alpha_m}\sum_{\tilde y_i = k_m(x_i)}w_i^{(m)} + e^{\alpha_m}\sum_{\tilde y_i \neq k_m(x_i)}w_i^{(m)}$$
这意味着总的Loss函数是正确分类的Loss加上错误分类的Loss。进一步转化为：
$$E = (e^{\alpha_m} - e^{-\alpha_m})\sum_{i=1}^N w_i^{(m)} \mathbb{1}(\tilde y_i \neq k_m(x_i)) + e^{-\alpha_m}\sum_{i=1}^N w_i^{(m)}$$
现在需要求出$\alpha_m，k_m$的表达形式。对上式加以分析，可以知道，$e^{-\alpha_m}\sum_{i=1}^Nw_i^{(m)}$项与$k_m$没有关系，那么此时取能够令Loss函数最小的$k_m$为：
$$k_m = \operatorname*{argmin}_{k_m} \sum_{i=1}^N w_i^{(m)} \mathbb{1}(\tilde y_i \neq k_m(x_i))$$
也就是第m个基本分类器选择的标准是使得第m次分类中错分的Loss最小的那个基本分类器。

关于$\alpha_m$的确定，我们对表达式$E$求解关于$\alpha_m$的导数，并且令导数为0，可以得到最优的$\alpha_m$为：

$$\alpha_m = \frac{1}{2} log \frac{1- err_m}{err_m},其中err_m = \frac{\sum_{i=1}^N w_i^{(m)} \mathbb{1}(\tilde y_i \neq k_m(x_i))} {\sum_{i=1}^N w_i^{(m)}}$$

由此，关于AdaBoost的具体过程可以写成如下：

• 对于第m个分类器，m=1,...,M:
• • a) 选择使得第m次分类中错分的Loss最小的基本分类器$k_m$；
    b) 计算$err_m = \frac{\sum_{i=1}^N w_i^{(m)} \mathbb{1}(\tilde y_i \neq k_m(x_i))} {\sum_{i=1}^N w_i^{(m)}}$;
    c) 计算此时的第m个基本分类器权重$\alpha_m =\frac{1}{2} log \frac{1- err_m}{err_m}$;
    d) 更新此时的样本权重，$w_i := w_i ·exp(2\alpha_m \mathbb{1}(\tilde y_i \neq k_m(x_i))-\alpha_m)$。
• 得到最终预测结果$f_(x) =sign( \sum_{m=1}^M \alpha_m k_m(x))$。

实际上根据Adaboost的构造过程，权值调整公式为：

$$\left( w_{m+1,i} \right) = \left\{ \begin{array}{l} \frac{w_{m,i}}{Z_m}e^{-\alpha_m}, {\kern 1pt} k_m(x_i) = y_i\\ \frac{w_{m,i}}{Z_m}e^{\alpha_m},,{\kern 1pt} k_m(x_i) \neq y_i \end{array} \right.$$
其中的$Z_m$是正则化因子，它的目的仅仅是使$D_{m+1}$成为一个概率分布，具体表达式为：
$$Z_m = \sum_{i=1}^N w_{m,i}· exp(-\alpha_m y_i k_m(x_i))$$

最终的结果是多个基本分类器加权之后再通过sign函数将结果判断出来，因为强分类器最终也是要区分两类结果$\{-1,1\}$，用sign函数很符合常理。

AdaBoost实例演示

给定训练样本：

求解步骤：
(1) 初始化权值分布

$${D_1} = \left( {{w_{11}},{w_{12}},...,{w_{1i}},...,{w_{1n}}} \right)$$
其中，${w_{1i}} = \frac{1}{N},i = 1,2,...N$
由于$N=10$，所以 $w_{1i} = 0.1，i = 1,2,...N$
（2）训练第一个基本分类器
a) 观察数据，发现'0,1,2'、'3,4,5'、'6,7,8'是三类不同的数据，而'9'则是单身汉；直观上推测可知，需要找到对应的数据分界点，比如2.5、5.5、8.5等，将这十个数分为两类。我们能够发现当阈值$v = 2.5$时，即分类器认为小于2.5的为正样本，大于2.5的为负样本。观察得知此时的误差率最低（0.3），表格中阴影部分表示分错的记录：

此时的基本分类器为：
$${k_1}\left( x \right) = \left\{ \begin{array}{l} 1,{\kern 1pt} x < 2.5\\ - 1, {\kern 1pt} x \ge 2.5 \end{array} \right.$$
b) 通过表格可以看出，训练样本有10个数据，分类器$k_1(x)$分错了3个，因此$k_1(x)$在训练样本上的分类误差率为：
$${e_1} = P\left( {{k_1}\left( {{x_i}} \right) \ne {y_i}} \right) = 0.1 + 0.1 + 0.1 = 0.3$$
c) 根据分类误差率来计算$k_1(x)$的系数，有：
$${\alpha _1} = \frac{1}{2}\log \left( {\frac{{1 - {e_1}}}{{{e_1}}}} \right) = 0.4236$$
d) 更新训练样本的权值分布（错分的样本6,7,8的权值增大），得到${D_2}$:
$${D_2} = \left( {0.0715,{\rm{ }}0.0715,{\rm{ }}0.0715,{\rm{ }}0.0715,{\rm{ }}0.0715,{\rm{ }}0.0715,{\rm{ }}0.1666,{\rm{ }}0.1666,{\rm{ }}0.1666,{\rm{ }}0.0715} \right)$$
e) 得到当前的强分类器，由于目前只有一个基本分类器，所以当前的强分类器只有一项：
$$\begin{array}{l} f_1\left( x \right) = \sum\limits_{m = 1}^M {{\alpha _m}{k_m}\left( x \right)} {\kern 1pt} = 0.4236·{k_1}\left( x \right) \end{array}$$
可以看出：错分样本的加权之和影响误差率，误差率影响基本分类器在最终分类器中所占的权重。
(3) 训练第二个分类器
a) 观察数据，此时取$v = 8.5$时误差率最低，表格中阴影部分表示分错的记录：

此时的基本分类器$k_2$为：
$${k_2}\left( x \right) = \left\{ \begin{array}{l} 1, {\kern 1pt} x < 8.5\\ - 1,{\kern 1pt} x \ge 8.5 \end{array} \right.$$
b) 计算分类误差率，有：
$${e_2} = P\left( {{k_2}\left( {{x_i}} \right) \ne {y_i}} \right) = 0.0715 + 0.0715 + 0.0715 = 0.2143$$
c) 根据分类误差率来计算$k_2(x)$的系数，有：
$${\alpha _2} = \frac{1}{2}\log \left( {\frac{{1 - {e_2}}}{{{e_2}}}} \right) = 0.6496$$
d) 更新训练样本的权值分布，得到${D_3}$:
$${D_3} = \left( {0.0455,{\rm{ }}0.0455,{\rm{ }}0.0455,{\rm{ }}0.1667,{\rm{ }}0.1667,{\rm{ }}0.1667,{\rm{ }}0.106,{\rm{ }}0.106,{\rm{ }}0.106,{\rm{ }}0.0455} \right)$$
对应的强分类器为：
$$f_2(x) = \sum\limits_{m = 1}^M {{\alpha _m}{k_m}\left( x \right)} = 0.4236·{k_1}\left( x \right) + 0.6496·k_2(x)$$
此时，将所有样本都代入到$sign(f_2(x))$，可以知道此时强分类器的错误率为30%。与$sign(f_1(x))$的错误率一致。
(4) 训练第三个分类器
a) 类似的步骤，在分布$D_3$中，当取$v = 8.5$时误差率最低，此时的基本分类器$k_3$为：
$${k_3}\left( x \right) = \left\{ \begin{array}{l} 1, {\kern 1pt} x < 5.5\\ - 1,{\kern 1pt} x \ge 5.5 \end{array} \right.$$
b) 计算分类误差率，有：
$${e_3}=0.182$$
c) 根据分类误差率来计算$k_3(x)$的系数，有：
$${\alpha _3} = \frac{1}{2}\log \left( {\frac{{1 - {e_3}}}{{{e_3}}}} \right) = 0.7514$$
d) 更新训练样本的权值分布，得到${D_4}$:
$${D_4} = \left( {0.125,{\rm{ }}0.125,{\rm{ }}0.125,{\rm{ }}0.102,{\rm{ }}0.102,{\rm{ }}0.102,{\rm{ }}0.065,{\rm{ }}0.065,{\rm{ }}0.065,{\rm{ }}0.125} \right)$$
对应的强分类器为：
$$f_3(x) = \sum\limits_{m = 1}^M {{\alpha _m}{k_m}\left( x \right)} = 0.4236·{k_1}\left( x \right) + 0.6496·k_2(x)+0.7514·k_3(x)$$
这个时候，我们将所有训练样本都代入到强分类器$f_3(x)$中，可以发现，在这个强分类器里面，所有的样本都被正确分类了，错误率为0！！！果然，三个臭皮匠顶上了一个诸葛亮！我们可以停止迭代了。通常迭代停止的条件有两种：一是判断强分类器的错误率是否已经达到预期设定的标准；二是判断总的迭代次数是否达到了预期设定的次数。

AdaBoost的误差界

通过上面的例子可知，Adaboost在学习的过程中不断减少训练误差，直到各个弱分类器组合成最终分类器，那这个最终分类器的误差界到底是多少呢？

相关专家已经证明，Adaboost 最终分类器的训练误差的上界为：

$$\frac{1}{N} \sum_{i=1}^N\mathbf{1}(sign(f_M(x_i)) \neq y_i) \leq \frac{1}{N} \sum_{i=1}^Nexp(-y_if_M(x_i)) = \prod_{m=1}^M Z_m$$
也就是说，随着证明过程如下：
当强分类器$sign(f_m(x_i)) \neq y_i$时，有$y_if_m(x_i) \leq 0$，因而$exp(-y_if_m(x_i)) \geq 1$，因此前半部分得证。
关于后半部分,由之前的知识可知：
$$w_{m+1,i}= \frac{w_{m,i}}{Z_m}exp(-\alpha_my_ik_m(x_i)) \\ Z_mw_{m+1,i}= w_{m,i}exp(-\alpha_my_ik_m(x_i))$$
整个推导过程如下：
$$\frac{1}{N} \sum_{i=1}^Nexp(-y_if_M(x_i)) = \frac{1}{N} \sum_{i=1}^Nexp(-y_i\sum_{m=1}^M \alpha_m k_m(x_i))\\ =\sum_{i=1}^N \frac{1}{N} exp(-y_i\sum_{m=1}^M \alpha_m k_m(x_i)) = \sum_{i=1}^N w_{1i} ·exp(-y_i\sum_{m=1}^M \alpha_m k_m(x_i))\\ =\sum_{i=1}^N w_{1i} \prod_{m=1}^M exp(-y_i \alpha_m k_m(x_i)) = \sum_{i=1}^N w_{1,i}·exp(-y_i \alpha_1 k_1(x_i))\prod_{m=2}^M exp(-y_i \alpha_m k_m(x_i))$$
将之前的$Z_mw_{m+1,i}= w_{m,i}·exp(-\alpha_my_ik_m(x_i))$代入可知：
$$=\sum_{i=1}^N Z_1·w_{2,i}\prod_{m=2}^M exp(-y_i \alpha_m k_m(x_i)) =Z_1\sum_{i=1}^N w_{2,i}\prod_{m=2}^M exp(-y_i \alpha_m k_m(x_i)) \\ =Z_1Z_2\sum_{i=1}^N w_{3,i}\prod_{m=3}^M exp(-y_i \alpha_m k_m(x_i)) =Z_1Z_2···Z_{M-1}\sum_{i=1}^N w_{M,i} exp(-y_i \alpha_M k_M(x_i))\\ =\prod_{m=1}^M Z_m$$
这个结果表明：在每一轮选择适当的$k_m(x)$使得$Z_m$最小，从而使得训练误差下降最快。这和之前的推导是一致的。接下来，我们来看看上述结果的上界。
对于二分类而言，有如下结论：
$$\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} \leq exp(-2\sum_{m=1}^M \gamma_m^2)$$
其中，$\gamma_m = \frac{1}{2} - e_m$。证明如下：
根据$Z_m$以及分类误差$e_m$的定义式：
$$Z_m = \sum_{i=1}^N w_{m,i}· exp(-\alpha_m y_i k_m(x_i)) = \sum_{y_i = k_m(x_i)}w_{m,i}·e^{-\alpha_m}+\sum_{y_i = k_m(x_i)}w_{m,i}·e^{\alpha_m}\\ =(1-e_m)e^{-\alpha_m}+e_me^{\alpha_m} = 2\sqrt{e_m(1-e_m)} = \sqrt{1-4\gamma_m^2}$$
而最后的不等式$\prod_{m=1}^M \sqrt{1-4\gamma_m^2} \leq exp(-2\sum_{m=1}^M \gamma_m^2)$可先由$e^x$和$\sqrt{1-x}$在点$x=0$处的泰勒展开式推出不等式$\sqrt{(1-4\gamma^2)}\leq exp(-2 \gamma_m^2)$，进而得到。
推论：如果存在$\gamma >0$,对所有$m$有$\gamma_m > \gamma$，则
$$\frac{1}{N}\sum_{i=1}^N \mathbf{1}(sign(f_M(x_i) \neq y_i))) \leq exp(-2M \gamma^2)$$
这表明在此条件下AdaBoost算法的训练误差是以指数速率下降的。这一性质是很有吸引力的。注意，AdaBoost算法不需要知道下界$\gamma$，这真是Freund与Schapire设计AdaBoost时所考虑的，也就是说它具有适应性，即它能够适应弱分类器各自的训练误差率，这也就是它的名称的由来。