AdaBoost&GBDT

1、提升方法的基本思路

提升方法的基本思想就是“三个臭皮匠赛过诸葛亮”，更严谨的说，是由“弱学习算法”提升为“强学习算法”。“弱”和“强”的定义由Kearns和Valiant提出：弱可学习指存在一个多项式算法可学习它且学习正确率仅比随机猜测好；强可学习指存在一个多项式算法可学习它且学习正确率很高。非常有趣的是Schapire证明了强可学习与弱可学习是等价的。也就是说在PAC学习的框架下，一个概念是强可学习的充要条件是这个概念弱可学习。这就为我们将“弱学习算法”提升为“强学习算法”提供了理论基础。

理论基础有了，我们再来看一下提升方法的动机，其实这个动机很自然，对一个问题而言，弱学习器的训练比强学习器容易得多。另外，我个人认为提升方法还可以在样本不太大的情形下发挥作用，因为提升方法所做的事就是让各个基学习器关注不同的样本，最后达到兼顾各个样本的效果，可以充分发挥每个样本的作用（这一说法未必准确，但《统计学习方法》中只包含10个样本的例题似乎印证了这一点）。

最后简单说一下提升方法的基本思路。提升方法就是从弱学习算法出发，反复学习得到一系列弱分类器（基分类器），然后组合这些弱分类器构成一个强分类器。不难看出这其中的要点有两个，一是如何得到这一系列弱分类器，二是如何组合这些弱分类器，下面我们看一下AdaBoost是如何处理这两个步骤的。

2、AdaBoost算法

AdaBoost算法的流程如下：

（1）初始化训练数据权值分布（均匀分布）：

$D_1=(w_{11},\dots,w_{1N}),\quad w_{1i}=\frac{1}{N},\quad i=1,2,\dots,N$

（2）对 $m=1,2,\dots,M$

使用具有权值分布 $D_m$ 的数据集进行学习得到基分类器：

$G_m(x):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}ln\frac{1-e_m}{e_m}$

更新训练数据集权值分布：

$D_{m+1}=(w_{m+1,1},\dots,w_{m+1,N})$

$w_{m+1,i}=\frac{w_{mi}e^{-\alpha_m y_i G_m(x_i)}}{Z_m},\quad i=1,2,\dots,N$

这里 $Z_m$ 是规范化因子：

$Z_m=\sum_{i=1}^N w_{mi} e^{-\alpha_m y_i G_m(x_i)}$

（3）构建基本分类器的线性组合：

$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))$

我们看一下算法中的要点：

a） $G_m(x)$ 的系数 $\alpha_m=\frac{1}{2}ln\frac{1-e_m}{e_m}$ ，可以看到 $e_m\leq \frac{1}{2}$ 时 $\alpha_m\geq 0$ ，且 $\alpha_m$ 随 $e_m$ 的减小而增大。这是合理的，前者说明一个基分类器至少要优于随机分类器其权重才大于0，后者说明分类误差率越小的基分类器在最终分类器中的权重越大。

b）更新训练数据权值的式子可以写成：

$\begin{equation} w_{m+1,i}=\left\{ \begin{array}{rcl} \frac{w_{mi}e^{-\alpha_m}}{Z_m}& & {G_m(x_i)=y_i}\\ \frac{w_{mi}e^{\alpha_m}}{Z_m}& & {G_m(x_i)\neq y_i} \end{array} \right. \end{equation}$

在a）中我们已经说明了 $\alpha_m\geq 0$ ，因此这里的 $e^{\alpha_m}\leq 1$ ， $e^{-\alpha_m}\geq 1$ ，这意味着被基分类器 $G_m(x)$ 误分类样本的权值被扩大，而被正确分类样本的权值则被缩小。也就是说训练下一个分类器的时候我们重点关注当前分类器误分的样本，这样下一个分类器将与当前分类器“互补”，从而最后组合起来将达到在全体数据上较好的效果。

c）需要注意的是，我们训练各个基学习器是序列化进行的，而不是同时进行的，这也意味着AdaBoost算法不能并行计算。也就是说，我们训练当前学习器时用的样本权重是由前一个学习器用的样本权重及其分类结果决定的，因此要按次序进行。

3、AdaBoost算法误差分析

定理1

AdaBoost算法最终分类器的训练误差界为：

$\frac{1}{N}\sum_{i=1}^N I(G(x_i)\neq y_i)\leq \frac{1}{N}\sum_i e^{-y_i f(x_i)}=\prod_m Z_m$

证明：

当 $G_m(x_i)\neq y_i$ 时， $y_i f(x_i)<0$ ，因此 $e^{-y_i f(x_i)}\geq 1$
当 $G_m(x_i)\neq y_i$ 时， $I(G_m(x_i)\neq y_i)=1$

从而前半部分得证。

后半部分推导要用到 $Z_m$ 和权重的关系：

$w_{m+1,i}=\frac{w_{mi}e^{-\alpha_m y_i G_m(x_i)}}{Z_m},\quad i=1,2,\dots,N$

$\Rightarrow w_{mi}e^{-\alpha_m y_i G_m(x_i)}=Z_m w_{m+1,i} \quad \quad \quad(*)$

由上式可得：

$\begin{equation*} \begin{aligned} \frac{1}{N}\sum_i e^{-y_i f(x_i)}&=\frac{1}{N}\sum_i e^{-\sum_{m=1}^M \alpha_m y_i G_m(x_i)}\\ &=\sum_i w_{1i}\prod_{m=1}^M e^{-\alpha_m y_i G_m(x_i)}(w_{1i}=\frac{1}{N})\\ &=Z_1\sum_i w_{2i}\prod_{m=2}^M e^{-\alpha_m y_i G_m(x_i)}(由式(*)可得)\\ &=Z_1 Z_2\sum_i w_{3i}\prod_{m=3}^M e^{-\alpha_m y_i G_m(x_i)}\\ &=\dots\\ &=\prod_{m=1}^M Z_m \end{aligned} \end{equation*}$

从而后半部分得证。

定理1为我们提供了AdaBoost的训练误差界，所以我们每一轮选取的 $G_m$ 应该使得 $Z_m$ 最小，从而使训练误差下降最快。

定理2

二分类问题AdaBoost的训练误差界满足：

$\begin{equation*} \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}(\gamma_m=\frac{1}{2}-e_m)\\ &\leq e^{-2\sum_{m=1}^{M}\gamma_m^2} \end{aligned} \end{equation*}$

证明：

$\begin{equation*} \begin{aligned} Z_m&=\sum_{i=1}^N w_{mi} e^{-\alpha_m y_i G_m(x_i)}\\ &=\sum_{y_i=G_m(x_i)}w_{mi}e^{-\alpha_m}+\sum_{y_i\neq G_m(x_i)}w_{mi}e^{\alpha_m}\\ &=(1-e_m)e^{-\alpha_m}+e_m e^{\alpha_m}\\ &=2\sqrt{e_m(1-e_m)}(因为\alpha_m=\frac{1}{2}ln\frac{1-e_m}{e_m})\\ &=\sqrt{1-4\gamma_m^2} \end{aligned} \end{equation*}$

这就完成了定理2中等号部分的证明，至于不等号的证明，我们把项拆开并用 $x$ 代替 $\gamma_m^2$ ，于是现在需要证明的结论为：

$\sqrt{1-4x}\leq e^{-2x}$

即：

$1-4x\leq e^{-4x}$

即：

$1-u\leq e^u$

这在 $u=4\gamma_m^2\geq 0$ 时是显然的。从而定理2得证。

不难看出，定理2是在定理1的基础上推出的一个更宽泛的上界，这个上界与各个基分类器的错误率有关， $\gamma_m=1-e_m$ 衡量的其实是分类器 $G_m$ 由于随机分类器的程度，若这个程度有一个下界： $\gamma_m\geq \gamma\quad\forall m$ ，即各个基分类器都与随机分类器的误差率之间有一个“间隙”，则：

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

这表明随基学习器数目的增加，AdaBoost的训练误差以指数速率下降。这是非常好的性质。

4、AdaBoost算法解释

AdaBoost的另一个解释是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二分类学习方法。

以上解释中有几个关键词：加法模型，前向分步，指数函数。

所谓加法模型，就是最终学习器是由各个基学习器带权加和而成的：

$f(x)=\sum_{m=1}^M \beta b(x;\gamma_m)$

这里 $\gamma_m$ 表示基函数的参数， $\beta_m$ 表示基函数的系数。

所谓前向分布，就是对于使得上述 $f(x)$ 经验风险极小化的问题：

$\min_{\beta_m,\gamma_m}\sum_{i=1}^N L(y_i,\sum_{m=1}^M \beta_m b(x_i;\gamma_m))$

直接优化 $M$ 组参数 $(\beta_m,\gamma_m)$ 是非常复杂的。前向分布算法的思路是每一步只学习一个基学习器及参数，即一次只学习一组系数 $(\beta_m,\gamma_m)$ 。具体来说，每步只需优化：

$\min_{\beta,\gamma}\sum_{i=1}^N L(y_i,\beta b(x_i;\gamma))$

得到最优参数 $(\beta_m,\gamma_m)$ ，然后更新 $f(x)$ ：

$f_m(x)=f_{m-1}(x)+\beta_m b(x;\gamma_m)$

最后，我们以定理的形式说明AdaBoost的损失函数是指数函数。

定理3

AdaBoost算法是前向分步加法算法的特例，模型是由基分类器组成的加法模型，损失函数是指数函数。即损失函数为：

$L(y,f(x))=e^{-yf(x)}$

证明：

假设经过 $m-1$ 轮迭代前向分步算法已经得到 $f_{m-1}(x)$ ：

$f_{m-1}(x)=\alpha_1 G_1(x)+\dots+\alpha_{m-1}G_{m-1}(x)$

第 $m$ 轮迭代得到 $\alpha_m,G_m(x)$ ，则 $f_m(x)$ 为：

$f_m(x)=f_{m-1}(x)+\alpha_m G_m(x)$

目标是使前向分步算法得到的 $\alpha_m,G_m(x)$ 使 $f_m(x)$ 的指数损失最小：

$(\alpha_m,G_m(x))=arg\min_{\alpha,G}\sum_{i=1}^N e^{-y_i(f_{m-1}(x_i)+\alpha G(x_i))}$

上式可表示为：

$(\alpha_m,G_m(x))=arg\min_{\alpha,G}\sum_{i=1}^N \hat{w}_{mi}e^{-y_i \alpha G(x_i)}\quad(\hat{w}_{mi}=e^{-y_i f_{m-1}(x_i)})$

可以看到 $\hat{w}_{mi}$ 不依赖 $\alpha$ 和 $G$ ，与最小化无关。

下面我们先求最优的 $G_m^*(x)$ ，对任意 $\alpha>0$ ：

$G_m^*(x)=arg\min_G (e^\alpha\sum_{y_i\neq G(x_i)} \hat{w}_{mi}+e^{-\alpha} \sum_{y_i=G(x_i)} \hat{w}_{mi})$

当 $\alpha>0$ 时， $e^\alpha>1>e^{-\alpha}$ ，又 $\sum_{y_i\neq G(x_i)} \hat{w}_{mi}+\sum_{y_i= G(x_i)} \hat{w}_{mi}=\sum_{i=1}^N \hat{w}_{mi}$ 为定值，所以我们希望 $\sum_{y_i\neq G(x_i)} \hat{w}_{mi}$ 尽可能小，即：

$G_m^*(x)=arg\min_G \sum_{i=1}^N \hat{w}_{mi} I(y_i\neq G(x_i))$

这正是AdaBoost算法的基本分类器 $G_m(x)$ ，接下来我们求 $\alpha_m^*$ ：

$\begin{equation*} \begin{aligned} \sum_{i=1}^N \hat{w}_{mi}e^{-y_i \alpha G(x_i)}&=e^\alpha\sum_{y_i\neq G(x_i)} \hat{w}_{mi}+e^{-\alpha} \sum_{y_i=G(x_i)} \hat{w}_{mi}\\ &=(e^\alpha-e^{-\alpha}) \sum_{i=1}^N \hat{w}_{mi} I(y_i\neq G(x_i))+e^{-\alpha} \sum_{i=1}^N \hat{w}_{mi} \end{aligned} \end{equation*}$

将 $G_m^*(x)=arg\min_G \sum_{i=1}^N \hat{w}_{mi} I(y_i\neq G(x_i))$ 带入上式，则有：

$\sum_{i=1}^N \hat{w}_{mi} I(y_i\neq G(x_i))=e_m$

又因为权重之和为1：

$\sum_{i=1}^N \hat{w}_{mi}=1$

从而原式变成：

$(e^\alpha-e^{-\alpha})e_m+e^{-\alpha}$

对 $\alpha$ 求导并令其为0：

$(e^\alpha+e^{-\alpha})e_m-e^{-\alpha}=0$

$\Rightarrow \alpha_m^*=\frac{1}{2}ln\frac{1-e_m}{e_m}$

这也与AdaBoost算法的 $\alpha_m$ 完全一致。

最后我们看每一轮样本权值的更新。由：

$f_m(x)=f_{m-1}(x)+\alpha_m G_m(x)$

$\hat{w}_{mi}=e^{-y_i f_{m-1}(x_i)}$

可知：
$\hat{w}_{m+1,i}=e^{-y_i[f_{m-1}(x)+\alpha_m G_m(x)]}=\hat{w}_{mi}e^{-y_i \alpha_m G_m(x)}$

可以看到，除了规范化因子，这与AdaBoost算法的权值更新过程也完全一致。

5、提升树（Boosting Tree）

以决策树为基函数的提升方法称为提升树。提升树被认为是统计学习中性能最好的方法之一。

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

$f_M(x)=\sum_{m=1}^M T(x;\Theta_m)$

其中 $T(x;\Theta_m)$ 表示决策树， $\Theta_m$ 表示决策树参数， $M$ 为树的个数。

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

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

其中 $f_{m-1}(x)$ 为当前模型，通过经验风险极小化确定下一棵决策树参数 $\Theta_m$ ：

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

针对不同问题的提升树学习算法主要区别在于损失函数 $L$ 不同。平方误差对应回归问题，指数损失函数对应分类问题，一般损失函数对应一般决策问题。

5.1、分类问题的提升树方法

上面提到，当损失函数为指数函数的时候，提升树算法可以解决分类问题。我们之前证明了AdaBoost算法是前向分步加法算法的特例，模型是由基分类器组成的加法模型，损失函数是指数函数。

因此针对而分类问题，提升树算法只需将AdaBoost算法中的基分类器限制为二分类决策树即可，也就是说此时提升树算法是AdaBoost算法的特殊情况。

5.2、回归问题的提升树算法

将输入空间 $X$ 划分为 $J$ 个互不相交的区域 $R_1,R_2,\dots,R_J$ ，并在每个区域上输出常量 $c_j$ ，则树可以表示为：

$T(x;\Theta)=\sum_{j=1}^J I(x\in R_j)$

其中参数 $\Theta=\{ (R_1,c_1),\dots,(R_J,c_J) \}$ 表示树的区域划分和各区域上的常数。 $J$ 是回归树的复杂度即叶子结点个数。

当采用平方误差损失函数时：

$L(y,f(x))=(y-f(x))^2$

其损失为：

$\begin{equation*} \begin{aligned} L(y_i,f_{m-1}(x)+T(x_i;\Theta_m)&=[y-f_{m-1}(x)-T(x;\Theta_m)]^2\\ &=[r-T(x;\Theta_m)]^2\\ \end{aligned} \end{equation*}$

这里 $r=y-f_{m-1}(x)$ 是当前模型拟合数据的残差。

因此对回归问题的提升树算法来说，只需要简单地拟合当前模型的残差即可。算法流程如下：

（1）初始化 $f_0(x)=0$
（2）对 $m=1,2,\dots,M$

计算残差： $r_{mi}=y_i-f_{m-1}(x_i),\quad i=1,2,\dots,N$
拟合残差 $r_{mi}$ 学习一个回归树，得到 $T(x;\Theta_m)$
更新 $f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$
（3）得到回归问题的提升树：

$f_M(x)=\sum_{m=1}^M T(x;\Theta_m)$

5.3、梯度提升

当损失函数是均方误差或者指数函数的时候，优化是很简单的，但对一般形式的损失函数来说，往往每一步的优化并不那么容易。梯度提升（Gradient Boosting）算法可以解决这个问题。其关键是利用损失函数的负梯度在当前模型的值：

$-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$

作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

梯度提升算法流程如下：

（1）初始化：

$f_0(x)=arg\min_c \sum_{i=1}^N L(y_i,c)$

（2）对 $m=1,2,\dots,M$ ：

a) 对 $i=1,2,\dots,N$ ，计算：

$r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$

b) 对 $r_{mi}$ 拟合一个回归树，得到第 $m$ 棵树的叶结点区域 $R_{mj},j=1,2,\dots,J$
c) 对 $j=1,2,\dots,J$ ，计算：

$c_{mj}=arg\min_c \sum_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$

d) 更新 $f_m(x)=f_{m-1}(x)+\sum_{j=1}^J c_{mj}I(x\in R_{mj})$

（3）得到回归树：

$\hat{f}(x)=f_M(x)=\sum_{m=1}^M \sum_{j=1}^J c_{mj}I(x\in R_{mj})$

上述算法流程要点如下：第一步初始化只有一个根结点的树。第2(a)步计算损失函数的负梯度在当前模型的值，将其作为残差的估计（对于平方损失函数这就是残差，对于一般损失函数这就是残差的近似值）。第2(b)步估计回归树叶结点区域，以拟合残差近似值。第2(c)步利用线性搜索估计叶结点区域的值，使损失函数极小化。第2(d)步更新回归树。第3步输出最终模型。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,179评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,229评论 2赞 380
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,032评论 0赞 336
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,533评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,531评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,539评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,916评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,574评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,813评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,568评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,654评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,354评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,937评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,918评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,152评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,852评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,378评论 2赞 342