集成学习与Adaboost

??集成学习在上一节已经介绍过了，集成算法-随机森林，一般来说集成算法可以分为两类：Boosting和Bagging，而上次我们详细介绍了Bagging中的代表算法随机森林。但是Boosting中的算法却一个也没有提，于是这篇文章，就主要介绍Boosting的最常见的一个集成算法：Adaboost。
??Adaboost算法的核心思想就将多个弱学习器进行组合成一个强学习器，就是三个臭皮匠顶个诸葛亮地道理。但是并没有这么简单，说组合就能组合，多个弱学习器如何组合得到的效果才能最好，这是一个非常重要的重点。在前面随机森林中我们学习到了要想组合多个弱学习器得到很好的效果需要满足弱学习器具有好而不同的特点，在随机森林中，我们使用自助采样法使得多个弱学习器学习的数据集不同，从而使得弱学习器不同，这是一种可行得学习方法。在今天要学习的Boosting中，（也就是Adaboost中），我们是对一个数据集不断进行学习，只不过每次学习的数据集其权重不同，而这个权重就是我们说的“不同”。后面我们再详细介绍，在这里只需要直到Adaboost算法的思想就行，至于为什么我们可以不改变样本点 $x_i,y_i)$ ，而只需要改变样本点的权重占比 $w_i$ 即可。这里就是Adaboost算法独特的地方，首先明确一点，我们这里介绍的算法只针对分类问题，也即预测值是离散的学习问题（Adaboost可以解决回归问题，只不过在本节不介绍）。在之前学习决策树的时候，我们说学习一个决策树依靠的是决策树的损失函数 $C_\alpha(T)$ ，标准可以选取最小二乘（回归问题）或者基尼指数（分类问题）。但是在Adaboost算法中，我们计算弱分类树的误差使用的是特别的函数，这个函数和样本的权值分布有关。
??下面会详细介绍Adaboost算法从0实现的细节

细说Adaboost分类算法

??这里叙述的Adaboost算法主要是针对分类问题。
??假设给定一个二分类问题的训练数据集：
$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$
??其中，每个样本点由实例与标记组成。实例是 $x_i$ ，标记是 $y_i$ 。AdaBoost算法可以利用上述的训练数据集学习一系列的基本分类器，也叫弱学习器，并将这些弱分类器线性组合成一个强分类器，注意是线性组合，说明每个弱分类器肯定就会有一个系数。
??算法训练开始前，我们需要给训练集样本赋予初权值。此时训练数据集具有均匀的权值分布，设权值分布为 $D_1=(w_{11},w_{12},\cdots,w_{1N}),\,\,\,\,\,\,\,\,w_{1i}=\frac{1}{N},\,\,\,\,\,\,\,\,\,\,i=1,2\cdots,N$ 。在学习第一个分类器时，其实就是根据现有的训练数据集学习一个分类树，只不过此时的分类树具有最小的误差。所有分类器的误差 $e$ 的计算方式如下：
$e_m=\sum\limits_{i=1}^N{P(G_m(x_i)\ne y_i)}=\sum\limits_{i=1}^N{w_{mi}I(G_m(x_i)\ne y_i)}$
??这个误差其实就是用来评价我们分类模型学习的好坏的，而从公式中也可以看出，误差就是分类错误样本的权值的累加。
??在得到第一个弱分类器 $G_1(x)$ 的误差 $e_1$ 后，我们可以用这个误差来计算第一个弱分类器的权重，这个权重在最后线性组合多个弱分类器时会用到。计算 $G_1(x)$ 的系数为：
$\alpha_1=\frac{1}{2}\log\frac{1-e_1}{e_1}$
??这样就得到了第一个弱分类器的权重系数 $\alpha_1$ 。对于第二个第三个分类器计算方式都是一样的。这里的对数就是自然对数。
??上面我们已经学习了第一个弱分类器 $G_1(x)$ 和第一个弱分类器的权重 $\alpha_1$ 。那么后面就可以对训练数据集的权重分布进行一个更新，这个更新是Adaboost算法的重点，我们只有对样本权重进行一个更新，提高在第一个弱分类器中误分类的点的权重，才能使得在第一个弱分类器中分类错误的点在第二个弱分类器中被更加注意，这样在第二个弱分类器中就会对第一个若分类器分类错误的点进行照顾，从而不断优化。计算权重分布 $D_2$ 的公式如下：
$D_2=(w_{21},w_{22},\cdots,w_{2N})\\ w_{2i}=w_{1i}\frac{\exp(-\alpha_1y_iG_1(x_i))}{\sum\limits_{i=1}^N{w_{1i}}\exp(-\alpha_1y_iG_1(x_i))}\,\,\,\,\,\,\,i=1,2,\cdots,N$
经过上述式子的更新，得到的第二代权值分布情况 $D_2$ 。
??注意不管是第一代还是第二代，我们的权值分布 $D$ 的总和应该为1。
??Adaboost算法就训练往后迭代，使用第二代的数据训练第二个弱分类器。
??算法中还有几个点或者说是规律可以看出，第 $i$ 个弱分类器的线性系数为 $\alpha_i$ ，这个系数的值可以说是由误差决定的，因为计算系数的式子中只有误差一个参量，而误差的范围是从0到1，我们遍历误差绘制加法系数的大小如图：
在这里插入图片描述
??从图上可以看到，当误差小于0.5时，弱分类器的系数才是大于0的，这一点其实和真实情况一样，毕竟没人会要一个分类错误率都超过一半的分类器，那还不如瞎猜。所以我们在遇到的绝大多数Adaboost算法中，系数都是正的，所有基学习器的误差不会超过0.5。
??另一个需要注意的点就是在计算下一轮训练数据的权值分布 $D_{m+1}$ 时，因为所有的 $\sum\limits_{i=1}^N{w_{1i}}\exp(-\alpha_1y_iG_1(x_i))$ 都是一样的，所以最后只与 $\exp(-\alpha_1y_iG_1(x_i))$ 有关，而 $y_i$ 与 $G_1(x_i)$ 的输出值都是离散值，假设我们取二分类结果为1和-1，则 $y_iG_1(x_i)$ 的值也取-1和1，如果基分类器预测正确取1，预测错误取-1，所以原函数就变成了 $\exp(\alpha)$ 或 $\exp(-\alpha)$ ，即假设我们的样本点 $x_i$ 在基分类器中分类错误，那么他下一轮的样本权重就会增大，如果样本点 $x_i$ 分类正确，那么他下一轮的样本权重就会减小。这样做不会导致训练样本 $x_i$ 发生改变，但是会让训练样本点的权重 $w_i$ 发生改变，不改变样本点数值大小而使得样本点在不同基学习器中发挥不同作用，这应该就是Adaboost算法的核心。

总结Adaboost算法的步骤如下：
输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ，弱学习算法
输出：最终的分类器 $G (x)$

初始化训练数据的权重分布 $D_1=(w_{11},w_{12},\cdots,w_{1N}),\,\,\,\,\,\,\,\,w_{1i}=\frac{1}{N},\,\,\,\,\,\,\,\,\,\,i=1,2\cdots,N$
对 $m=1,2,\cdots,M$ (1)使用具有权值分布 $D_m$ 的训练数据集学习，得到基本分类器G_m(x)。 (2)计算 $G_m(x)$ 在训练数据集上的分类误差率 $e_m=\sum\limits_{i=1}^N{P(G_m(x_i)\ne y_i)}=\sum\limits_{i=1}^N{w_{mi}I(G_m(x_i)\ne y_i)}$ (3)计算 $G_m(x)$ 的系数
$\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}$ 这里的对数是自然对数。
(4)更新训练数据集的分布
$D_{m+1}=(w_{m+1,1},\cdots,w_{m+1,i},\cdots,w_{m+1,N})\\ w_{m+1,i}=\frac{w_{mi}}{Z_m}\exp(-\alpha_my_iG_m(x_i))$
其中， $Z_m$ 是规范化因子。
$Z_m=\sum\limits_{i=1}^N{w_{mi}\exp(-\alpha_my_iG_m(x_i))}$
$Z_m$ 的作用就是使 $D_{m+1}$ 成为一个概率分布。
构建基本分类器的线性组合 $f(x)=\sum\limits_{m=1}^M{\alpha_mG_m(x)}$ 得到最终的分类器为： $G (x) = s i g n (f (x))$

??上面是Adaboost算法的核心。最后我们会得到一个线性加和的模型，可以利用这个模型来对未知的数据进行预测，经实验，Adaboost的效果相比于常规的决策树要提升很多。

Adaboost算法与加法模型

??其实在学习Adaboost算法过程中，我们应该还需要掌握一个算法，叫做前向分布算法，而Adaboost算法也可以理解为前向分布算法的一个特例，即可以认为Adaboost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法的二分类学习方法。
加法模型指的是对于：
$f(x)=\sum\limits_{m=1}^M{\beta_mb(x;\gamma_m)}$
其中 $b(x;\gamma_m)$ 为基函数， $\gamma_m$ 为基函数的参数， $\beta_m$ 为基函数的系数。显然式子中是对很多个基函数进行一个累加过程，我们称这种模型为加法模型。
在给定训练数据集以及损失函数 $L (y, f (x))$ 的条件下，学习加法模型 $f (x)$ 成为损失函数最小化问题：
$\min\limits_{\beta_m,\gamma_m}\sum\limits_{i=1}^N{L(y_i,\sum\limits_{m=1}^N{\beta_mb(x_i;\gamma_m)})}$
??其实这种学习方法在前面已经出现很多次了，例如在支持向量机中最大化间隔，后来也转化为学习参数 $\alpha$ 的问题。在这里通常是有一个很复杂的优化问题，因为如果想要一次性学习找到全局最优的参数将会非常复杂，而前向分布算法就是将找到所有参数的优化问题分解成一个个小的子问题，即我们学习的是加法模型，前向分布算法就是从前往后，每一步只学习一个基函数及其系数，然后学习一步再学下一步，逐渐逼近目标，那么就可以将复杂的问题简单化。然而Adaboost就是前向分布算法最经典的一个例子。而前向分布算法有着其独特的学习方式：
对于一个集成模型 $f (x)$ 来说，因为是加法模型，所以我们可以把 $f (x)$ 拆成:
$f_m(x)=f_{m-1}(x)+\beta_mb(x;\gamma_m)$
此时我们只需要学习函数 $b(x;\gamma_m)$ 即可，这种思想和贪心思想很像。
关于Adaboost是前向分布算法的一个特例是有相关证明的。
而且Adaboost模型是可以解决回归问题的，是在分类算法的基础上加以改进。