提升方法

提升方法

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

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

提升方法 AdaBoost 算法

  1. 提升方法基于这样一种思想:对于一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比其中任何一个专家单独的判断好。实际上,就是“三个臭皮匠顶个诸葛亮”的道理。

  2. 对于分类问题而言,给定一个训练样本集,求比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)容易得多。提升方法就是从弱学习算法出发,反复学习,得到一系列弱分类器(又称为基本分类器),然后组合这些弱分类器,构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

  3. 这样,对提升方法来说,有两个问题需要回答:一是在每一轮如何改变训练数据的权值或概率分布;二是如何将弱分类器组合成一个强分类器。关于第1个问题,AdaBoost的做法是,提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。这样一来,那些没有得到正确分类的数据,由于其权值的加大而受到后一轮的弱分类器的更大关注。于是,分类问题被一系列的弱分类器“分而治之”。至于第2个问题,即弱分类器的组合,AdaBoost采取加权多数表决的方法。具体地,加大分类误差率小的弱分类器的权值,使其在表决中起较大的作用,减小分类误差率大的弱分类器的权值,使其在表决中起较小的作用。

  4. 现在叙述 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算法的训练误差分析

  1. 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 最小,从而使训练误差下降最快。

  2. 二类分类问题 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) 进而得到。

  3. 二类分类问题,如果存在 \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 的训练误差是以指数速率下降的。

  4. AdaBoost 具有适应性,即它能适应弱分类器各自的训练误差率。这也是它的名称(适应的提升)的由来,Ada 是Adaptive 的简写。

AdaBoost算法的解释

  1. AdaBoost 算法还有另一个解释,即可以认为 AdaBoost 算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法。

  2. 考虑加法模型
    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))

  3. 前向分步算法
    输入:训练数据集 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=1M 所有参数 \beta_m,\gamma_m 的优化问题简化为逐次求解各个 \beta_m,\gamma_m 的优化问题。

  4. AdaBoost 算法是前向分歩加法算法的特例。这时,模型是由基本分类器组成的加法模型,损失函数是指数函数。

提升树

  1. 提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。

  2. 以决策树为基函数的提升方法称为提升树(boosting tree)。对分类问题决策树是二叉分类树,对回归问题决策树是二叉回归树。

  3. 提升树模型可以表示为决策树的加法模型
    F_M(x) = \sum_{m=1}^MT(x;\Theta_m)
    其中,T(x;\Theta_m) 表示决策树;\Theta_m 为决策树的参数;M 为树的个数。

  4. 提升树算法采用前向分步算法。首先确定初始提升树 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))
    由于树的线性组合可以很好地拟合训练数据,即使数据中的输入与输出之间的关系很复杂也是如此,所以提升树是一个高功能的学习算法。

  5. 已知一个训练数据集 T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}x_i \in X \subset R^ny_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)。所以,对回归问题的提升树算法来说,只需简单地拟合当前模型的残差。这样,算法是相当简单的。

  6. 回归问题的提升树算法
    输入:训练数据集 T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}x_i \in X \subset R^ny_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)

  7. 提升树利用加法模型与前向分歩算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时,每一步优化是很简单的。但对一般损失函数而言,往往每一步优化并不那么容易。针对这一问题,Freidman提出了梯度提升(gradient boosting)算法。这是利用最速下降法的近似方法,其关键是利用损失函数的负梯度在当前模型的值
    -[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}
    作为回归问题提升树算法中的残差的近似值,拟合一个回归树。

  8. 梯度提升算法
    输入:训练数据集 T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}x_i \in X \subset R^ny_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阅读 206,602评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,442评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,878评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,306评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,330评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,071评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,382评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,006评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,512评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,965评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,094评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,732评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,283评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,286评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,512评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,536评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,828评论 2 345

推荐阅读更多精彩内容