提升方法

Boosting

如果发现了"弱学习算法", 将它提升(boost)为"强学习算法". 最具代表性的是AdaBoost算法.

对于分类问题, 提升方法:

• 从若学习算法出发, 反复学习, 得到一系列弱分类器(又称基本分类器)
• 然后组合这些弱分类器, 构成一个强分类器

Boosting的两个问题

1. 每一轮如何改变训练数据的权值或概率分布?
2. 如何将弱分类器组合成一个强分类器?

AdaBoost

AdaBoost做法

1. 目的: 使错误分类样本的权值加大, 在后一轮的弱分类器中, 得到更多关注

   • 提高 前一轮弱分类器 错误分类样本 的权值,
   • 降低 被 正确分类样本 的权值.

2. 弱分类的组合: AdaBoost采用加权多数表决的方法.

   • 加大 分类误差率小的弱分类器的权值, 使其在表决中起较大的作用,
   • 减小 分类误差率大的弱分类器的权值, 使其在表决中起较小的作用,

AdaBoost算法

输入: 二分类的训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$, 其中 $x_i\in{\scr{X}}\subseteq R^n, y_i\in{\scr{Y}}=\{-1,+1\}, {\scr{X}}是实例空间, {\scr{Y}}是标记集合$

输出: 最终分类器 $G(x)$

1. 初始化训练数据的权值分布: 假设训练数据集有均匀的权值分布, 即每个训练样本在基本分类器的学习中作用相同 $D_1=(w_{11},\cdots,w_{1i},\cdots,w_{1N}),\quad w_{1i}={1 \over N},\quad i=1,2,\cdots,N$

2. AdaBoost反复学习基本分类器, 在每一轮 $m=1,2,\cdots,M$ 顺次执行下列操作:

   • 使用当前权值分布 $D_m$ 的训练数据集学习(e.g.让分类误差率 最小), 得到基本分类器: $G_m(x): {\scr{X}}\rightarrow\{-1,+1\}$

   • 计算基本分类器 $G_m(x)$ 在训练数据集上的分类误差率: $e_m=P(G_m(x_i)\neq y_i)=\sum_{G_m(x_i)\neq y_i}w_{mi}=\sum_{i=1}^N w_{mi}I(G_m(x_i)\neq y_i)$

     其中, $w_{mi}$ 表示第m轮中第i个样本实例的权值, $\sum_{i=1}^N w_{mi}=1$

   • 计算基本分类器 $G_m(x)$ 的系数: $\alpha_m={1\over2}log{1-e_m\over e_m}$ 其中, $\alpha_m$ 表示 $G_m(x)$ 在最终分类器中的重要性. 分类误差率越小的的基本分类器在最终分类器中的作用越大.

     (a) $e_m\leq{1\over2}\longrightarrow\alpha\geq0$,

     (b) $e_m\downarrow\longrightarrow\alpha_m\uparrow$,

     (c) $e_m={1\over2}\longrightarrow\alpha_m=0$, (bad g(t) --> zero weight)

     (d) $e_m=0 \longrightarrow\alpha_m=+\infty$, (good g(t) --> superior weight)

• 更新训练数据集的权值分布: $D_{m+1}=(w_{m1},\cdots,w_{mi},\cdots,w_{mN}),\quad i=1,2,\cdots,N$ $w_{m+1,i}={w_{mi}\over Z_m}{\rm{exp}}(-\alpha_my_iG_m(x_i))= \begin{cases} {w_{mi}\over Z_m}e^{-\alpha_m}, &{G_m(x_i)=y_i}\\[2ex] {w_{mi}\over Z_m}e^{\alpha_m}, &{G_m(x_i)\neq y_i} \end{cases}$

  因此, 被基本分类器 $G_m(x)$ 误分类样本的权值, 在下一轮 $G_{m+1}(x)$ 中得以扩大, 起更大的作用.

• 构建基本分类器的线性组合: $f(x)=\sum_{m=1}^M\alpha_mG_m(x)$

  得到最终分类器: $G(x)=sign(f(x))=sign\big(\sum_{m=1}^M\alpha_mG_m(x)\big)$

  • 系数 $\alpha_m$ 表示了基本分类器的重要性, 所有 $\alpha_m$ 之和并不为 $1$.
  • $f(x)$ 的符号决定实例 $x$ 的类, $f(x)$ 的绝对值表示分类的确信度.

AdaBoost的训练误差分析

如果存在 $\gamma>0$ , 对于所有 $m$ 有 $\gamma_m>\gamma$, 则: ${1\over N}\sum_{i=1}^N I(G(x_i)\neq y_i)\leq{\rm{exp}}(-2M\gamma^2)$

因此, AdaBoost的训练误差是以指数速率下降的.

Adaboost的本质

Adaboost 是 前向分步加法 算法的特例:

• 加法模型: 由基本分类器组成
• 损失函数: 指数函数

AdaBoost的思想

GBDT

• 步骤:
  • 求出损失函数的负梯度, 当做残差的近似值
  • 然后让一棵树去拟合每个样本的残差
    • 回归树和决策树很类似，只是回归树把落入叶子节点的样本，对于他们的标签求了个平均值输出，注意，这里的标签，对于GBDT来说，是每一个样本的残差
  • 然后再去求这棵树的占的比重.
    • 线性搜索求系数, 也就是每棵树的系数
    • 最后的模型用这些树融合

反馈与建议

• 微博：@Girl_AI

参考文献

• 统计学习方法
• 机器学习技法