集成算法(AdaBoost基本原理)

1. 引言

提升算法大多都是基于这样的一个思想；对于一个复杂的任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独判断的好。实际上就是 三个臭皮匠，顶个诸葛亮的道理。
AdaBoost算法是提升算法中具有代表性的一种，它通过改变样本的权重，学习多个分类器，并将这些分类器线性组合，提高分类器的性能。

2. 算法

输入：训练数据集 $T=\left\{\right(x_1,y_1),(x_2,y_2\left)...\right(x_3,y_3\left)\right\}$T={(x1​,y1​),(x2​,y2​)...(x3​,y3​)},其中 $x_1ϵXϵR_n$x1​ϵXϵRn​, $y_iϵY=\{-1,+1\}$yi​ϵY={−1,+1}，弱学习方法；
输出：最终分类器 $G\left(x\right)$G(x)
(1)初始化训练数据的权值分布 $D_1=(w_{ll},...,w_{l}i,...,w_{lN}),w_{li}=\frac{1}{n},i=1,2,...,N$D1​=(wll​,...,wl​i,...,wlN​),wli​=n1​,i=1,2,...,N
(2)对 $m=1,2,...,M$m=1,2,...,M
(a)使用具有权值分布 $D_m$Dm​的训练数据集学习，得到基分类器 $G_m\left(x\right):x\stackrel{}{\to }\{-1,+1\}$Gm​(x):x {−1,+1}
(b)计算 $G_m\left(x\right)$Gm​(x)在训练集数据上的分类误差率 $e_m=P\left(G_m\right(x_i\left)\ne y_i\right)=\sum _{i=1}^n{w}_{mi}I\left(G_m\right(x_i\left)\ne y_i\right)$em​=P(Gm​(xi​)̸​=yi​)=i=1∑n​wmi​I(Gm​(xi​)̸​=yi​)
©计算 $G_m\left(x\right)$Gm​(x)的系数 $a_m=\frac{1}{2}log\frac{(1-e_m)}{e_m},这里的对数是自然对数$am​=21​logem​(1−em​)​,这里的对数是自然对数
(d)更新训练数据集权值分布 $D_{m+1}=(w_{m+l,l},...,w_{m+l,i}...,w_{m+l,N})$Dm+1​=(wm+l,l​,...,wm+l,i​...,wm+l,N​)
$w_{m+l,i}=\frac{w_{m}i}{Z_m}exp(-a_m{y}_i{G}_m(x_i\left)\right),i=1,\mathrm{2...}N$wm+l,i​=Zm​wm​i​exp(−am​yi​Gm​(xi​)),i=1,2...N这里 $Z_m$Zm​是规范化因子
$Z_m=\sum _{i=1}^N{w}_{mi}exp(-a_m{y}_i{G}_m(x_i\left)\right)$Zm​=i=1∑N​wmi​exp(−am​yi​Gm​(xi​))
他使 $D_{m+1}$Dm+1​成为一个概率分布
(3)构建基本分类器线性组合
$f\left(x\right)=\sum _{m=1}^M{a}_m{G}_m\left(x\right)$f(x)=m=1∑M​am​Gm​(x)
得到最终分类器 $G\left(x\right)=sign\left(f\right(x\left)\right)=sign\left(\sum _{m=1}^M{a}_m{G}_m\right(x\left)\right)$G(x)=sign(f(x))=sign(m=1∑M​am​Gm​(x))

3. 算法描述

步骤（1）：假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中的作用相同，这一假设保证第一步能够在原始数据上学习基本分类器 $G_1\left(x\right)$G1​(x).
步骤（2）：AdaBoost反复学习基本分类器，在每一轮 $m=1,2,\mathrm{3..},M$m=1,2,3..,M顺次的执行下列操作：
(a)使用当前分布 $D_m$Dm​加权的训练数据集，学习基本分类器 $G_m\left(x\right)$Gm​(x)
(b)计算基本分类器 $G_m\left(x\right)$Gm​(x)在加权训练数据集上的分类误差率： $e_m=P\left(G_m\right(x_i\left)\ne y_i\right)=\sum _{G_m\left(x_i\right)\ne y_i}{w}_{mi}$em​=P(Gm​(xi​)̸​=yi​)=Gm​(xi​)̸​=yi​∑​wmi​
这里， $w_{mi}$wmi​表示第m轮中第i个实例的权值， ${\sum }_{i=1}^N{w}_{mi}=1$∑i=1N​wmi​=1.这表明， $G_m\left(x\right)$Gm​(x)在加权的训练数据集上的分类误差率是被 $G_m\left(x\right)$Gm​(x)误分类样本的权值之和，由此可以看出数据权值分布 $D_m$Dm​与基本分类器 $G_{(}x)$G(​x)的分类误差率的关系。
©计算基本分类器 $G_m\left(x\right)$Gm​(x)的系数 $a_m$am​. $a_m$am​表示 $G_m\left(x\right)$Gm​(x)在最终分类器中的重要性。
(d)更新训练数据的权值分布为下一轮做准备
步骤（3）：线性组合 $f\left(x\right)$f(x)实现M个基本分类器的加权表决。系数 $a_m$am​表示了基本分类器 $G_m\left(x\right)$Gm​(x)的重要性，这里，所有的 $a_m$am​之和并不唯一。 $f\left(x\right)$f(x)的符号决定实例x的类， $f\left(x\right)$f(x)的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点。

4. 小结

Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。

参考文献：统计学习-李航