2023年8月2日发(作者：)

Adaboost算法流程及⽰例1. Boosting提升⽅法（源⾃统计学习⽅法) 提升⽅法是⼀种常⽤的统计学习⽅法，应⽤⼗分⼴泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进⾏线性组合，提⾼分类的性能。提升算法基于这样⼀种思路：对于⼀个复杂任务来说，将多个专家的判断进⾏适当的综合所得出的判断，要⽐其中任何⼀个专家独断的判断好。实际上，就是“三个臭⽪匠顶个诸葛亮”的道理。 历史上，Kearns和Valiant⾸先提出了“强可学习（Strongly learnable）”和“弱可学习（Weekly learnable）”的概念。⽀出：在概率近似正确（probably approximatelycorrect，PAC）学习框架中，⼀个概念（⼀个分类），如果存在⼀个多项式的学习算法能够学习它，并且正确率很好，那么就称这个概念是强可学习的；⼀个概念（⼀个分类），如果存在⼀个多项式的学习算法能够学习它，但学习的正确率仅⽐随机猜测略好，那么就称这个概念是弱可学习的。⾮常有趣的是Schapire后来证明强可学习与弱可学习是等价的，也就是说，在PAC学习框架下，⼀个概念是强可学习的充要条件是这个概念是弱可学习的。 这样⼀来，问题便成为，在学习中，如果已经发现了“弱学习算法”，那么能否将它提升（boost）为“强学习算法”。⼤家知道，发现弱学习算法通常要⽐发现强学习算法容易得多。那么如何具体实施提升，便成为开发提升⽅法时所要解决的问题。关于提升⽅法的研究很多，有很多算法被提出，最具代表性的是AdaBoost算法（Adaboost algorithm）。 对与分类问题⽽⾔，给定⼀个训练样本集，求⽐较粗糙的分类规则（弱分类器）要⽐求精确的分类规则（强分类器）容易得多。提升⽅法就是从弱学习算法出发，反复学习，得到⼀系列分类器，然后组合这些分类器，构成⼀个强分类器。 这样，对于提升算法来说，有两个问题需要回答：⼀是在每⼀轮如何改变训练数据的权值分布；⼆是如何将弱分类器组合成⼀个强分类器。

Boosting算法要涉及到两个部分，加法模型和前向分步算法。 (1) 加法模型就是说强分类器由⼀系列弱分类器线性相加⽽成。⼀般组合形式如下：F_M(x;P)=sum_{m=1}^nalpha _mh(x;theta_m) 其中h(x;theta_m)是⼀个个的弱分类器，theta_m是弱分类器学习到的最优参数；alpha_m就是若学习在强分类器中所占的⽐重；P是所有alpha_m和theta_m的组合。这些弱分类器线性相加组成强分类器。 (2) 前向分布就是说在训练过程中，下⼀轮迭代产⽣的分类器是在上⼀轮的基础上训练得来的。也就是可以协成这样的形式：F_m (x)=F_{m-1}(x)+alpha _mh(x;theta_m) 由于采⽤的损失函数不同，Boosting算法也因此有了不同的类型，AdaBoost就是损失函数为指数损失的Boosting算法。2. Adaboost算法Adaboost算法思想：1) 提⾼那些被前⼀轮弱分类器错误分类的样本的权值，降低那些被正确分类的样本的权值；2) 采⽤加权多数表决的⽅法。具体的，加⼤分类误差率⼩的弱分类器的权值，使其在表决中起较⼤的作⽤；减⼩分类误差率⼤的弱分类器的权值，使其在表决中起较⼩的作⽤。Adaboost算法流程：输⼊：训练数据集T={(x_1, y_1),(x_2, y_2),(x_3, y_3),...(x_n, y_n)}，其中x_iin Xsubseteq mathbb{R}^{n},y_iin Y={-1,+1},Y={-1, +1}是弱分类算法。输出：最终分类器G_m(x)初始化：假定第⼀次训练时，样本均匀分布权值⼀样。 D_1=(w_{11}, w_{12},w_{13}......w_{1n}) 其中w_{1i}=frac{1}{n},i=1,循环：m=1,M，(a) 使⽤具有权值分布D_m的训练数据集学习，得到基本分类器G_m（选取让误差率最低的阈值来设计基本分类器）：G_m(x):chi rightarrow {-1, +1}

(b) 计算G_m(x)在训练集上的分类误差率e_me_m=P(G_m(x_i)neq y_i)=sum_{i=1}^{n}w_{mi}I(G_m(x_i)neq y_i) I(G_m(x_i)neq y_i)：当G_m(x_i)与y_i相等时，函数取值为0；当G_m(x_i)与y_i不相等时，取值为1;。 由上述式⼦可知，G_m(x)在训练数据集上的误差率e_m就是被G_m(x)误分类样本的权值之和。

(c) 计算G_m(x)的系数alpha_m，alpha_m表⽰G_m(x)在最终分类器中的重要程度：alpha_m = frac{1}{2}lnfrac{1-e_m}{e_m} 【注】显然e_m <= 1/2时，alpha_mam >= 0，且alpha_m随着e_m的减⼩⽽增⼤，意味着分类误差率越⼩的基本分类器在最终分类器中的作⽤越⼤ 此时分类器为：f_m(x)=alpha_mG_m(x)

(d) 更新训练数据集的权值分布，⽤于下⼀轮迭代。D_{m+1}=(w_{m+1,1},w_{m+1,2},w_{m+1,3},...w_{m+1,n})w_{m+1,i}=frac{w_{mi}}{Z_m}exp(-y_ialpha_mG_m(x_i))，i=1,2,3,...n其中Z_m是规范化因⼦，使得D_{m+1}成为⼀个概率分布。Z_m=sum_{i=1}^{n}w_{mi}exp(-y_ialpha_mG_m(x_i))

循环结束条件：e_m⼩于某个阈值（⼀般是0.5），或是达到最⼤迭代次数。AdaBoost ⽅法中使⽤的分类器可能很弱（⽐如出现很⼤错误率），但只要它的分类效果⽐随机好⼀点（⽐如两类问题分类错误率略⼩于0.5），就能够改善最终得到的模型。组合分类器：f(x)=sum_{m=1}^{M}alpha_mG_m(x)最终分类器： G_m(x)=sign(f(x))=sign(sum_{i=1}^{M}alpha_mG_m(x))

3. Adaboost⽰例假定给出下列训练样本。序号数据类别标签ixy1-154-165-09-1初始化：w_{1i}=frac{1}{n}=0.1，n=10（样本个数)序号

数据类别标签初始权值ixyw_{1i}1010.12110.13210.143-10.154-10.165-10.17610.18710.19810.1109-10.1阈值猜测：观察数据，可以发现数据分为两类：-1和1，其中数据“0,1,2”对应“1”类，数据“3,4,5”对应“-1”类，数据“6,7,8”对应“1”类，数据“9”对应“"1”类。抛开单个的数据“9”，可以找到对应的数据分界点（即可能的阈值），⽐如：2.5、5.5、8.5（⼀般0.5的往上加，也可以是其他数）。然后计算每个点的误差率，选最⼩的那个作为阈值。 但在实际操作中，可以每个数据点都做为阈值，然后就算误差率，保留误差率最⼩的那个值。若误差率有⼤于0.5的就取反（分类换⼀下，若⼤于取1，取反后就⼩于取1），再计算误差率。迭代过程1：m=11> 确定阈值的取值及误差率当阈值取2.5时，误差率为0.3。即 x<2.5 时取 1，x>2.5 时取 -1，则数据6、7、8分错，误差率为0.3（简单理解：10个⾥⾯3个错的，真正误差率计算看下⾯的表格）当阈值取5.5时，误差率最低为0.4。即 x<5.5 时取1，x>5.5 时取 -1，则数据3、4、5、6、7、8分错，错误率为0.6>0.5，故反过来，令 x>5.5 取 1，x<5.5 时取 -1，则数据0、1、2、9分错，误差率为0.4当阈值取8.5时，误差率为0.3。即 x<8.5 时取1，x>8.5 时取 -1，则数据3、4、5分错，错误率为0.3由上⾯可知，阈值取2.5 或8.5时，误差率⼀样，所以可以任选⼀个作为基本分类器。这⾥选2.5为例。G_1(x)=begin{cases}1, &x<2.5 -1, & x>2.5 end{cases}计算误差率：序号数据类别标签分类器结果分类结果ixyG_1(x)1011对2111对3211对43-1-1对54-1-1对65-1-1对761-1错871-1错981-1错109-1-1对

从上可得G_1(x)在训练数据集上的误差率（被分错类的样本的权值之和）:e_1=P(G_1(x_i)neq y_i)=sum_{G_1(x_i)neq y_i}w_{1i}=0.1+0.1+0.1=0.32> 计算G_1(x)的系数：alpha_1=frac{1}{2}lnfrac{1-e_1}{e_1}=frac{1}{2}lnfrac{1-0.3}{0.3}approx 0.42365这个alpha_1代表G_1(x)在最终的分类函数中所占的⽐重约为0.423653> 分类函数f_1(x)=alpha_1G_1(x)=0.42365G_1(x)4> 更新权值分布：序号

数据类别标签初始权值1更新权值2ixyw_{1i}w_{2i}1010.10.071432110.10.071433210.10.0714343-10.10.0714354-10.10.0714365-10.10.071437610.10.166668710.10.166669810.10.16666 由上⾯可以看出，因为数据“6,7,8”被G_1(x)分错了，所以它们的权值由初始的0.1增⼤到了0.16666；其他的数据由于被分对了，所以权值由0.1减⼩到0.07143。

迭代过程2：m=21> 确定阈值的取值及误差率当阈值取2.5时，误差率为0.49998。即 x<2.5 时取 1，x>2.5 时取 -1，则数据6、7、8分错，误差率为0.16666*3（取过，不列⼊考虑范围）当阈值取5.5时，误差率最低为0.28572。即 x<5.5 时取1，x>5.5 时取 -1，则数据3、4、5、6、7、8分错，错误率为0.07143*3+0.16666*3=0.71427>0.5，故反过来，令 x>5.5 取 1，x<5.5 时取 -1，则数据0、1、2、9分错，误差率为0.07143*4=0.28572当阈值取8.5时，误差率为0.21429。即 x<8.5 时取1，x>8.5 时取 -1，则数据3、4、5分错，错误率为0.07143*3=0.21429由上⾯可知，阈值取8.5时，误差率最⼩，所以：G_2(x)=begin{cases}1, &x<8.5 -1, & x>8.5 end{cases}计算误差率：序号数据类别标签权值分布　分类器结果分类结果ixyw_{2i}G_2(x)1010.071431对2110.071431对3210.071431对43-10.071431错54-10.071431错65-10.071431错7610.166661对8710.166661对9810.166661对

从上可得G_2(x)在训练数据集上的误差率（被分错类的样本的权值之和）:e_2=P(G_2(x_i)neq y_i)=sum_{G_2(x_i)neq y_i}w_{2i}=0.07143+0.07143+0.07143=0.214292> 计算G_2(x)的系数：alpha_2=frac{1}{2}lnfrac{1-e_2}{e_2}=frac{1}{2}lnfrac{1-0.21429}{0.21429}approx 0.64963这个alpha_2代表G_2(x)在最终的分类函数中所占的⽐重约为0.6492633> 分类函数f_2(x)=alpha_2G_2(x)=0.64963G_2(x)4> 更新权值分布：序号

数据类别标签初始权值1权值2更新权值3ixyw_{1i}w_{2i}$w_{3i}1010.10.071430.045462110.10.071430.045463210.10.071430.0454643-10.10.071430.1666754-10.10.071430.1666765-10.10.071430.166677610.10.166660.106068710.10.166660.106069810.10.166660.10606

迭代过程3：m=31> 确定阈值的取值及误差率当阈值取2.5时，误差率为0.31818。即 x<2.5 时取 1，x>2.5 时取 -1，则数据6、7、8分错，误差率为0.10606*3=0.31818（取过，不列⼊考虑范围）当阈值取5.5时，误差率最低为0.18184。即 x<5.5 时取1，x>5.5 时取 -1，则数据3、4、5、6、7、8分错，错误率为0.16667*3+0.10606*3=0.81819>0.5，故反过来，令 x>5.5 取 1，x<5.5 时取 -1，则数据0、1、2、9分错，误差率为0.04546*4=0.18184当阈值取8.5时，误差率为0.13638。即 x<8.5 时取1，x>8.5 时取 -1，则数据3、4、5分错，错误率为0.04546*3=0.13638（取过，不列⼊考虑范围）由上⾯可知，阈值取8.5时，误差率最⼩，但8.5取过了，所以取5.5：G_3(x)=begin{cases}-1, &x<5.5 1, & x>5.5 end{cases}计算误差率：序号数据类别标签权值分布　分类器结果分类结果ixyw_{3i}G_3(x)1010.04546-1错2110.04546-1错3210.04546-1错43-10.16667-1对54-10.16667-1对65-10.16667-1对7610.106061对8710.106061对9810.106061对 从上可得G_3(x)在训练数据集上的误差率（被分错类的样本的权值之和）:e_3=P(G_3(x_i)neq y_i)=sum_{G_3(x_i)neq y_i}w_{3i}=0.04546+0.04546+0.04546+04546=0.181842> 计算G_3(x)的系数：alpha_3=frac{1}{2}lnfrac{1-e_3}{e_3}=frac{1}{2}lnfrac{1-0.18188}{0.18184}approx 0.75197这个alpha_3代表G_3(x)在最终的分类函数中所占的⽐重约为0.751973> 分类函数f_3(x)=alpha_3G_3(x)=0.75197G_3(x)4> 更新权值分布：序号

数据类别标签初始权值1权值2权值3更新权值4ixyw_{1i}w_{2i}$w_{3i}$w_{4i}1010.10.071430.045460.125002110.10.071430.045460.125003210.10.071430.045460.1250043-10.10.071430.166670.1018554-10.10.071430.166670.1018565-10.10.071430.166670.101857610.10.166660.106060.064818710.10.166660.106060.064819810.10.166660.106060.06481迭代过程4：m=4此时观察数据，每次迭代被分错的数据都已经重新分配过权值，按其他参考资料来说，此时的误差率为0，所以迭代可以到此结束。最终分类器：G_m(x)=sign(0.42365G_1(x)+0.64963G_2(x)0.75197G_3(x))

---------------------

参考⽂献：

原⽂：Processing math: 0%