提升方法

一、什么是提升(boosting)方法

​ 提升方法是一种常用的统计学习方法。在分类问题中，通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性整合，提高分类的性能。

二、 提升方法的基本思路

• 提升方法的思想是，“三个臭皮匠顶个诸葛亮”，多个弱分类器能够组合成一个强分类器。

• kearns和Valiant提出强可学习和弱可学习的概念。

• 在概率近似正确（probably approximately correct，PAC）学习框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习，而且正确率高，则称这个概念是强可学习的。如果正确率仅仅比随机猜想的略好，称这个概念是弱可学习的。

• Schapire证明，强可学习和弱可学习是等价的。

• 实践中常常发现弱可学习算法，将弱可学习算法提升为强可学习算法成为研究的重点。

三、AdaBoost算法

​ AdaBoost采取加权多数表决的方法。加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用；减小分类误差大的弱分类器的权值，使其在表决中起较小的作用。

​ 现在叙述AdaBoost算法。假设给定一个二分类的训练数据集 \( T=\left \{ (x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\right \} \) 其中，每个样本点由实例和标记组成。示例 \(x_i \in X \subseteq R^n\) ，标记 \(y_i \in \ Y =\left \{ -1,+1\right \}\) ，\(X\) 是实例空间，\(Y\) 是标记集合。AdaBoost利用以下算法，从训练数据中学习一系列弱分类器或基本分类器。并将这些弱分类器线性组合成一个强分类器。

输入：

• 训练数据集 \(T=\left \{ (x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\right \}\) ，其中 \(x_i \in X \subseteq R^n\) ，\(y_i \in \ Y =\left \{ -1,+1\right \}\)

• 弱学习算法

输出：

• 最终分类器 \( G(x)\)

步骤：

• (1) 初始化训练数据的权值分布

  • \(D_1=(\omega _{11},\cdots,\omega_{1i},\cdots,\omega_{1N}), \omega_{1i}=\frac{1}{N},i=1,2,\cdots,N \)

• (2) 对于 \(m=1,2,\cdots,M\)

  • (a) 使用具有权值分布 \(D_m\) 的训练数据集学习，得到基本分类器公式 \( G_m(x):X\to \left \{ -1,+1\right \}\)

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

  • (c) 计算 \(G_M(x)\) 的系数 \(\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}\)

  • (d) 更新训练数据集的权值分布 \(D_1=(\omega _{m+1,1},\cdots,\omega_{m+1,i},\cdots,\omega_{m+1,N}), \omega_{m+1,i}=\frac{\omega_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)),i=1,2,\cdots,N \)

  这里，\(Z_m\) 是规范化因子 \(Z_m=\sum_{i=1}^{N}\omega_{mi}exp(-\alpha_my_iG_m(x_i))\) ，它使得 \(D_{m+1}\) 成为一个概率分布。

• (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))\)