提升方法 （Boosting）

Boosting基本思想: 通过改变训练数据的概率分布（训练数据的权值分布），学习多个弱分类器，并将它们线性组合，构成强分类器。

Boosting 方法需要解决两个问题

1. 如何改变训练数据的权值
2. 如何将弱分类器组合成强分类器。

AdaBoost 思想

1.提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。
未被正确分类的样本受到后一轮弱分类器更大的关注。
2. AdaBoost 采用加权多数表决，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用。

AdaBoost 算法

考虑二分类问题
数据集 $T{(x_1,y_1),(x_2,y_2),...(x_n,y_n)}$T(x1​,y1​),(x2​,y2​),...(xn​,yn​) , $y_i \in \{0,1\}$yi​∈{0,1}
有M个弱分类器$G_m(x) , m=1,2,..M$Gm​(x),m=1,2,..M。
（1）初始化训练数据 的权值分布
$D_1=(w_{11},..w_{i1},...,w_{1N}) , w_{1i}=\frac{1}{N}, i=1,2,..,N$D1​=(w11​,..wi1​,...,w1N​),w1i​=N1​,i=1,2,..,N
（2）for m = 1 to M
（a） 使用具有权值分布$D_m$Dm​的数据训练数据集学习，得到基本分类器$G_m(x)$Gm​(x)。
这个分类器是使得第m轮加权训练数据分类误差率最小的基本分类器
（b）计算分类误差率
$e_m = P(G_m(x) \not= y_i) = \sum_ {i=1}^Nw_{mi}I(G_m(x) \not= y_i)$em​=P(Gm​(x)̸​=yi​)=i=1∑N​wmi​I(Gm​(x)̸​=yi​)
（c）计算$G_m(x)$Gm​(x)的系数
$a_m = \frac{1}{2}ln\frac{1-e_m}{e_m}$am​=21​lnem​1−em​​
（d）更新训练数据的权值分布
$D_{m+1} = (w_{m+1,1},...w_{m+1,i},...w_{m+1,N})$Dm+1​=(wm+1,1​,...wm+1,i​,...wm+1,N​)
$w_{m+1,i}= \frac{w_{mi}}{Z_m}exp(- \alpha_my_iG_m(x_i)),i=1,2,..N$wm+1,i​=Zm​wmi​​exp(−αm​yi​Gm​(xi​)),i=1,2,..N
$Z_m$Zm​是规范化因子
$Z_m=\sum_{i=1}^Nw_{mi}exp(- \alpha_my_iG_m(x_i))$Zm​=i=1∑N​wmi​exp(−αm​yi​Gm​(xi​))
（3）构建基本分类器的线性组合
$f(x)= \sum_{m=1}^M\alpha_mG_m(x)$f(x)=m=1∑M​αm​Gm​(x)
得到最终的分类器
$G(x) = sign(f(x)) = sign(\sum_{m=1}^M\alpha_mG_m(x))$G(x)=sign(f(x))=sign(m=1∑M​αm​Gm​(x))

AdaBoost 算法的理解

1. （2）（b）权值的分布影响体现在损失函数上？基学习器是朝着最小化损失函数去学习的，被误分的样本具有更大的权值，因此受到了“更大的关注”。
2. （2）（c）基学习器的系数，它是由最小化指数损失函数得到的,（后面会提到的前向分步算法）
   先直观理解
   
   $e_m\le\frac{1}{2}$em​≤21​时，$\alpha_m\ge0$αm​≥0,并且$\alpha_m$αm​随着分类误差率的减小而增大。
   误分类率小的系数大，即在最后加权表决时起到较大的作用。
   系数的另一个作用，改变权值分布（2）（d）,扩大误分样本权值，缩小被正确分类的样本。
3. （3）基分类器线性组合的系数$\alpha_m$αm​之和不为1；
   二分类的输出为{-1，+1}，1多时，多数表决为1，求和大于0，因此用符号函数。
4. AdaBoost 最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率

AdaBoost 的另一种解释

模型：加法模型
策略：最小化损失函数（指数函数）
算法：前向分步算法

前向分步算法

加法模型
$f(x) = \sum_{m=1}^N\beta_mb(x;\gamma_m)$f(x)=m=1∑N​βm​b(x;γm​)
其中，$b(x;\gamma_m)$b(x;γm​)为基函数，$\gamma_m$γm​为基函数的参数，$\beta_m$βm​为基函数的系数。
给定训练数据及损失函数$L(y,f(x))$L(y,f(x))的条件下，学习加法模型$f(x)$f(x)成为经验风险最小化问题
$\mathop {min}_{\beta_m,\gamma_m}\sum_{i=1}^{N}L(y_i,\sum_{m=1}^M\beta_mb(x_i;\gamma_m))$minβm​,γm​​i=1∑N​L(yi​,m=1∑M​βm​b(xi​;γm​))

前向分步算法思想：从前向后，每一步只学习一个基函数及其系数，逐步逼近优化上式目标函数。
每一步只需要优化如下损失函数
$\mathop {min}_{\beta,\gamma}\sum_{i=1}^{N}L(y_i,\beta b(x_i;\gamma))$minβ,γ​i=1∑N​L(yi​,βb(xi​;γ))

Adaboost 是前向分步算法的特例，模型是由基本分类器组成的加法模型,损失函数是指数函数
$L(y,f(x)) = exp[-yf(x)]$L(y,f(x))=exp[−yf(x)]

根据前向分步算法，可以把 $\alpha_m$αm​和$G_m(x)$Gm​(x)推导出来对应到开头的AdaBoost
证明 蓝皮书

这个博客的例子讲解很详细
http://blog.****.net/mousever/article/details/52038198