提升方法

提升方法 AdaBoost 算法
AdaBoost算法的训练误差分析
AdaBoost算法的解释
提升树

提升（boosting）方法是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。

提升方法 AdaBoost 算法

提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上，就是“三个臭皮匠顶个诸葛亮”的道理。
对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。
这样，对提升方法来说，有两个问题需要回答：一是在每一轮如何改变训练数据的权值或概率分布；二是如何将弱分类器组合成一个强分类器。关于第1个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。至于第2个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。
现在叙述 AdaBoost 算法。假设给定一个二类分类的训练数据集
$T = \{(x_1,y_i),(x_2,y_2),...,(x_N,y_N)\}$
其中，每个样本点由实例与标记组成。实例 $x_i \in X \subset R^n$ ，标记 $y_i \in Y = \{-1, + 1\}$ ， $X$ 是实例空间， $Y$ 是标记集合。
输出：最终分类器 $G(x)$

1>> 初始化训练数据的权值分布
$D_1 = (\omega_{11},..., \omega_{1i},...,\omega_{1N}), \ \ \ \omega_{1i} = \frac{1}{N}, \ \ \ i=1,2,...,N$

2>> 对 $M=1,2,...,m$
a>> 使用具有权值分布 $D_m$ 的训练数据集学习，得到基本分类器
$G_m(x): X \rightarrow \{-1, +1\}$
假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同。
b>> 计算 $G_m(x)$ 在训练数据集上的分类错误率
$e_m = P(G_m(x_i) \neq y_i) = \sum_{i=1}^N\omega_{mi}I(G_m(x_i)\neq y_i)$
$G_m(x)$ 在加权的训练数据集上的分类误差率是被 $G_m(x)$ 误分类样本的权值之和，由此可以看出数据权值分布 $D_m$ 与基本分类器 $G_m(x)$ 的分类误差率的关系。
c>> 计算 $G_m(x)$ 的系数
$\alpha_m = \frac{1}{2}\log\frac{1-e_m}{e_m}$
这里的对数是自然对数。当 $e_m\le \frac{1}{2}$ 时， $\alpha_m\ge0$ ，并且 $\alpha_m$ 随着 $e_m$ 的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。
d>> 更新训练数据集的权值分布
$D_{m+1} = (\omega_{m+1, 1},...,\omega_{m+1,i},...,\omega_{m+1,N})$
$\omega_{m+1,i} = \frac{\omega_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)), \ \ \ i=1,2,...,N$
这里 $Z_m$ 是规范化因子
$Z_m = \sum_{i=1}^N \omega_{mi} exp(-\alpha_my_iG_m(x_i))$
它使 $D_{m+1}$ 成为一个概率分布。
$\omega_{m+1,i}$ 也可以写成
$\omega_{m+1,i} = \begin{cases} \frac{\omega_{mi}}{Z_m} e^{-\alpha_m}, \ \ \ G_m(x_i) = y_i \\ \frac{\omega_{mi}}{Z_m} e^{\alpha_m}, \ \ \ G_m(x_i) \neq y_i \end{cases}$
由此可知，被基本分类器 $G_m(x)$ 误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。两相比较，误分类样本的权值被放大 $e^{2\alpha_m}=\frac{e_m}{1-e_m}$ 倍。因此，误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点。

3>> 构建基本分类器的线性组合
$f(x) = \sum_{m=1}^M\alpha_mG_m(x)$
得到最终分类器
$G(x) = sign(f(x)) = sign(\sum_{m=1}^M\alpha_mG_m(x))$
线性组合 $f(x)$ 实现 M 个基本分类器的加权表决。系数 $\alpha_m$ 表示了基本分类器 $G_m(x)$ 的重要性，这里，所有 $\alpha_m$ 之和并不为1。 $f(x)$ 的符号决定实例 $x$ 的类， $f(x)$ 的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是 AdaBoost 的另一特点。

AdaBoost算法的训练误差分析

AdaBoost 最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。AdaBoost 算法最终分类器的训练误差界为
$\frac{1}{N}\sum_{i=1}^NI(G(x_i)\neq y_i) \le \frac{1}{N}\sum_i exp(-y_if(x_i)) = \prod_m Z_m$
证明：
当 $G(x_i) \neq y_i$ 时， $y_i f(x_i) \lt 0$ ，因而 $exp(-y_if(x_i)) \ge 1$ 。因此可直接推导出前半部分。
现推导后半部分如下
$\begin{array} \ \frac{1}{N} \sum_i exp(-y_if(x_i)) & = & \frac{1}{N} \sum_i exp(-\sum_{m=1}^M\alpha_my_iG_m(x_i)) \\ & = & \frac{1}{N} \sum_i \prod_{m=1}^M exp(-\alpha_my_iG_m(x_i))\\ & = & \sum_i \omega_{1i} \prod_{m=1}^M exp(-\alpha_my_iG_m(x_i)) \\ & = & \sum_i \frac{\omega_{2i} Z_m}{exp(-\alpha_1y_iG_1(x_i))}\prod_{m=1}^M exp(-\alpha_my_iG_m(x_i)) \\ & = & Z_1\sum_i \omega_{2i} \prod_{m=2}^M exp(-\alpha_my_iG_m(x_i)) \\ & = & Z_1Z_2 \sum_i \omega_{3i} \prod_{m=3}^M exp(-\alpha_my_iG_m(x_i)) \\ & ... \\ & = & Z_1Z_2\cdot\cdot\cdot Z_{m-1}\sum_i\omega_{Mi}exp(\alpha_My_iG_M(x_i)) \\ & = & \prod_{m=1}^MZ_m \end{array}$
这一定理说明，可以在每一轮选取适当的 $G_m$ 使得 $Z_m$ 最小，从而使训练误差下降最快。
二类分类问题 AdaBoost 的训练误差界
$\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)$
这里 $\gamma_m = \frac{1}{2}-e_m$ 。
证明：
$\begin{array} \ Z_m & = & \sum_{i=1}^N\omega_{mi}exp(-\alpha_my_iG_m(x_i)) \\ & = & \sum_{y_i = G_m(x_i)} \omega_{mi}e^{-\alpha_m} + \sum_{y_i \neq G_m(x_i)} \omega_{mi}e^{\alpha_m} \\ & = & (1-e_m)e^{-\alpha_m} + e_me^{\alpha_m} \\ & = & \sqrt{(1-e_m)^2e^{-\frac{1-e_m}{e_m}} + e_m^2e^{\frac{1-e_m}{e_m}}+2e_m(1-e_m)} \\ & = & 2\sqrt{e_m(1-e_m)} \\ & = & \sqrt{1-4\gamma_m^2} \end{array}$
至于不等式
$\prod_{m=1}^M\sqrt{1-4\gamma_m^2} \le exp(-2\sum_{m=1}^M\gamma_m^2)$
可先由 $e^x$ 和 $\sqrt{1-x}$ 在点 $x=0$ 的泰勒展开式推出 $\sqrt{1-4\gamma_m^2} \le exp(-2\gamma_m^2)$ 进而得到。
二类分类问题,如果存在 $\gamma \gt 0$ ，对所有 $m$ 有 $\gamma_m \gt \gamma$ ，则
$\frac{1}{N}\sum_{i=1}^NI(G(x_i)\neq y_i) \le exp(-2M\gamma^2)$
这表明在此条件下 AdaBoost 的训练误差是以指数速率下降的。
AdaBoost 具有适应性，即它能适应弱分类器各自的训练误差率。这也是它的名称（适应的提升）的由来，Ada 是Adaptive 的简写。

AdaBoost算法的解释

AdaBoost 算法还有另一个解释，即可以认为 AdaBoost 算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法。
考虑加法模型
$f(x) = \sum_{m=1}^M\beta_mb(x;\gamma_m)$
其中， $b(x;\gamma_m)$ 为基函数， $\gamma_m$ 为基函数的参数， $\beta_m$ 为基函数的系数。
在给定训练数据及损失函数 $L(Y,f(X))$ 的条件下，学习加法模型 $f(x)$ 成为经验风险极小化即损失函数极小化问题：
$min_{\beta_m,\gamma_m} \ \ \ \ \ \sum_{i=1}^NL(y_i, \sum_{m=1}^M\beta_mb(x_i;\gamma_m))$
通常这是一个复杂的优化问题。前向分步算法（forward stagewise algorithm）求解这一优化问题的想法是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：
$min_{\beta,\gamma} \ \ \ \ \ \sum_{i=1}^NL(y_i, \beta b(x_i;\gamma))$
前向分步算法
输入：训练数据集 $T=\{(x_1，y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，损失函数 $L(Y, f(x))$ ；基函数集 $\{b(x;\gamma)\}$ ；
输出：加法模型 $f(x)$ 。
1>> 初始化 $f_0(x) = 0$
2>> 对 $m=1,2,...,M$
a>> 极小化损失函数
$(\beta_m,\gamma_m) = arg \ min_{\beta,\gamma}\ \ \sum_{i=1}^NL(y_i, f_{m-1}(x_i) + \beta b(x_i;\gamma))$
得到参数 $\beta_m, \gamma_m$
b>> 更新
$f_m(x) = f_{m-1}(x) + \beta_mb(x;\gamma_m)$
3>> 得到加法模型
$f(x) = f_M(x) = \sum_{m=1}^M\beta_mb(x;\gamma_m)$
这样，前向分步算法将同时求解从 $m＝1$ 到 $M$ 所有参数 $\beta_m，\gamma_m$ 的优化问题简化为逐次求解各个 $\beta_m，\gamma_m$ 的优化问题。
AdaBoost 算法是前向分歩加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。

提升树

提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。
以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。
提升树模型可以表示为决策树的加法模型
$F_M(x) = \sum_{m=1}^MT(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}_m = arg \ min_{\Theta_m} \sum_{i=1}^NL(y_i,f_{m-1}(x_i) + T(x_i;\Theta_m))$
由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。
已知一个训练数据集 $T=\{(x_1，y_1),(x_2,y_2),...,(x_N,y_N)\}$ ， $x_i \in X \subset R^n$ ， $y_i \in Y \subset R$ 。在决策树部分已经讨论了回归树问题。如果将输入空间 $X$ 划分为 $J$ 个互不相交的区域 $R_1,R_2,...,R_J$ ，并且在每个区域上确定输出的常量 $c_j$ ，那么树可以表示为
$T(x;\Theta) = \sum_{j=1}^Jc_jI(x \in R_j)$
其中，参数 $\Theta = \{(R_1,c_1),(R_2,c_2),...,(R_J,c_J)\}$ 表示树的区域划分和各区域上的常数。 $J$ 是回归树的复杂度即叶结点个数。
回归问题提升树使用以下前向分步算法：
$\begin{array} \ f_0(x) = 0 \\ f_m(x) = f_{m-1}(x) + T(x;\Theta_m),\ \ \ m=1,2,...,M \\ f_M(x) = \sum_{m=1}^MT(x;\Theta_m) \end{array}$
在前向分步算法的第 m 步，给定当前模型 $f_{m-1(x)}$ ，需求解
$\hat{\Theta}_m = arg \ min_{\Theta_m} \sum_{i=1}^NL(y_i,f_{m-1}(x_i) + T(x_i;\Theta_m))$
得到 $\hat{\Theta}_m$ ，即第 m 棵树的参数。
当采用平方误差损失函数时，
$L(y,f(x)) = (y-f(x))^2$
其损失变为
$L(y_i,f_{m-1}(x_i) + T(x_i;\Theta_m)) = [y-f_{m-1}(x)-T(x;\Theta_m)]^2=[r-T(x;\Theta_m)]^2$
这里， $r = y-f_{m-1}(x)$ 是当前模型拟合数据的残差（residual）。所以，对回归问题的提升树算法来说，只需简单地拟合当前模型的残差。这样，算法是相当简单的。
回归问题的提升树算法
输入：训练数据集 $T=\{(x_1，y_1),(x_2,y_2),...,(x_N,y_N)\}$ ， $x_i \in X \subset R^n$ ， $y_i \in Y \subset R$ ；
输出：提升树 $f_M(x)$ 。
1>> 初始化 $f_0(x)=0$
2>> 对 $m=1,2,...,M$
a>> 计算残差 $r_{mi} = y_i-f_{m-1}(x_i),\ \ \ i=1,2,...,N$
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}^MT(x;\Theta_m)$
提升树利用加法模型与前向分歩算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，Freidman提出了梯度提升（gradient boosting）算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值
$-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$
作为回归问题提升树算法中的残差的近似值，拟合一个回归树。
梯度提升算法
输入：训练数据集 $T=\{(x_1，y_1),(x_2,y_2),...,(x_N,y_N)\}$ ， $x_i \in X \subset R^n$ ， $y_i \in Y \subset R$ ；损失函数 $L(Y,f(x))$ ；
输出：回归树 $\hat{f}(x)$ 。
1>> 初始化
$f_0(x) = arg \ min_c \ \sum_{i=1}^NL(y_i, c)$
估计使损失函数极小化的常数值，它是只有一个根结点的树。
2>> 对 $m=1,2,...,M$
a>> 对 $i=1,2,...,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,…,J$
估计回归树叶结点区域，以拟合残差的近似值。
c>> 对 $j=1,2,...,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}^Jc_{mj}I(x\in R_{mj})$
3>> 得到回归树
$\hat{f}(x) = f_M(x)= \sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$

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

提升方法

提升方法 AdaBoost 算法

AdaBoost算法的训练误差分析

AdaBoost算法的解释

提升树

推荐阅读更多精彩内容