机器学习 | 提升方法（一）

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

AdaBoost算法

基本思路

对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独判断效果好。在这里要先了解两个概念：“强可学习（strongly learnable）”和“弱可学习（weakly learnable）”的概念。概念指出，在概率近似正确（probably approximately correct，PAC）学习的框架中，一个概念（类），如果存在一个多项式的学习算法能够学习它并且正确率很高，则这个概念是强可学习的；如果正确率仅仅比随机猜测略好，则是弱可学习的。

这样一来，问题变成了如何将弱可学习算法提升为强可学习算法，这便是提升方法所需解决的问题，其中最具代表性的是AdaBoost算法。

提升方法就是从弱学习算法出发，反复学习，得到一系列的弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

对提升方法来说，有两个问题需要回答：一是在每一轮如何改变训练数据的权值或概率分布；而是如何将弱分类器组合成一个强分类器。关于第一个问题，AdaBoost的做法是提高那些被前一轮弱分类器错误分类样本的权值，降低被正确分类的样本的权值。对第二个问题，AdaBoost采取加权多数表决的方法，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值。

Adaboost算法

AdaBoost算法如下：

输入：训练数据集\(T = \lbrace(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\rbrace\)，其中\(x_i\in\chi\subseteq R^n\)，\(y_i\in Y=\lbrace -1, 1\rbrace\)；弱学习算法。

输出：最终分类器G(x)。

（1）初始化训练数据的权值分布 \[ D_1 = (w_{11},...,w_{1i},...,w_{1N}),w_{1i} = \frac{1}{N},i = 1,2,...,N \] （2）对m = 1, 2, ..., M

（a）使用具有权值分布\(D_m\)的训练数据集学习，得到基本分类器 \[ G_m(x):\chi\longrightarrow\lbrace-1,1\rbrace \] （b）计算\(G_m(x)\)在训练数据集上的分类误差率 \[ e_m = \sum^N_{i = 1}P(G_m(x_i)\ne y_i) = \sum^N_{i=1}w_{mi}I(G_m(x_i)\ne y_i) \] （c）计算\(G_m(x)\)的系数 \[ \alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m} \] 这里的对数是自然对数。

（d）更新训练数据集的权重分布 \[ D_{m+1} = (w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N}) \\ w_{m+1,i}=\frac{w_{mi} }{Z_m}exp(-\alpha_my_iG_m(x_i)),i=1,2,...,N \] 这里，\(Z_m\)是规范化因子 \[ Z_m = \sum^N_{i=1}w_{mi}exp(\alpha_my_iG_m(x_i)) \] 它使\(D_{m+1}\)成为一个概率分布。

（3）构建基本分类器的线性组合 \[ f(x) = \sum^M_{m=1}\alpha_mG_m(x) \] 得到最终分类器 \[ G(x) = sign(f(x)) = sign(\sum^M_{m=1}\alpha_mG_m(x)) \] 步骤说明如下：

步骤（1）假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第一步能够在原始数据上学习基本分类器\(G_1(x)\)。

步骤（2）AdaBoost反复学习基本分类器，在每一轮m = 1, 2, ..., M顺次地执行下列操作：

（a）使用当前分布\(D_m\)加权的训练数据集，学习基本分类器\(G_m(x)\)。

（b）计算基本分类器\(G_m(x)\)在加权训练数据集上的分类误差率： \[ e_m = \sum^N_{i=1}P(G_m(x_i)\ne y_i)=\sum_{G_m(x_i)\ne y_i}w_{mi} \] 这里，\(w_{wi}\)表示第m轮中第i个实例的权值，\(\sum^N_{i=1}w_{mi}=1\)。这表明，\(G_m(x)\)在加权的训练数据集上的分类误差率是被\(G_m(x)\)误分类样本的权值之和，由此可以看出数据权值分布与基本分类器的分类误差率的关系。

（c）计算基本分类器的系数\(\alpha_m\)，其表示\(G_m(x)\)在最终分类器中的重要性，其随\(e_m\)的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。

（d）更新训练数据的权值分布，为下一轮做准备。误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这就是AdaBoost的一个特点。

步骤（3）线性组合\(f(x)\)实现M个基本分类器的加权表决。系数\(\alpha_m\)表示了基本分类器\(G_m(x)\)的重要性，这里，所有\(\alpha_m\)之和不为1.\(f(x)\)的符号决定实例x的类，\(f(x)\)的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点。

以上就是今天的内容，谢谢大家的观看！