Boosting是一种用来提高弱分类器准确度的算法，是将“弱学习算法“提升为“强学习算法”的过程，主要思想是“三个臭皮匠顶个诸葛亮”。一般来说，找到弱学习算法要相对容易一些，然后通过反复学习得到一系列弱分类器，组合这些弱分类器得到一个强分类器。
Boosting算法要涉及到两个部分，加法模型和前向分步算法。
加法模型就是说强分类器由一系列弱分类器线性相加而成。一般组合形式如下：
$$F_M(x;P)=\sum_{m=1}^n\beta_mh(x;a_m)$$
其中，$h(x;a_m)$就是一个个的弱分类器，$a_m$是弱分类器学习到的最优参数，$\beta_m$就是弱学习在强分类器中所占比重，$P$是所有$\alpha_m$和$\beta_m$的组合。这些弱分类器线性相加组成强分类器。
前向分步就是说在训练过程中，下一轮迭代产生的分类器是在上一轮的基础上训练得来的。也就是可以写成这样的形式：
$$F_m (x)=F_{m-1}(x)+ \beta_mh_m (x;a_m)$$
用下面的GIF看起来会更加生动
AdaBoost是典型的Boosting算法，属于Boosting家族的一员。
对于AdaBoost，我们要搞清楚两点：
1、每一次迭代的弱学习$h(x;a_m)$有何不一样，如何学习？
2、弱分类器权值$\beta_m$如何确定？
第一个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。
第二个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。
输入：训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$，其中，$x_i∈X?R^n$，$y_i∈Y={-1,1}$，迭代次数$M$
1.初始化训练样本的权值分布:
$$
\begin{aligned}
D_1=(w_{1,1},w_{1,2},…,w_{1,i}),\w_{1,i}=\frac{1}{N},i=1,2,…,N
\end{aligned}
$$
2.对于$m=1,2,…,M$
(a) 使用具有权值分布$D_m$的训练数据集进行学习，得到弱分类器$G_m (x)$
(b) 计算$G_m(x)$在训练数据集上的分类误差率：$$e_m=\sum_{i=1}^Nw_{m,i} I(G_m (x_i )≠y_i )$$
(c) 计算$G_m (x)$在强分类器中所占的权重：$$\alpha_m=\frac{1}{2}log \frac{1-e_m}{e_m} $$
(d) 更新训练数据集的权值分布（这里，(z_m)是归一化因子，为了使样本的概率分布和为1）：
$$w_{m+1,i}=\frac{w_{m,i}}{z_m}exp?(-\alpha_m y_i G_m (x_i ))，i=1,2,…,10$$
$$z_m=\sum_{i=1}^Nw_{m,i}exp?(-\alpha_m y_i G_m (x_i ))$$
3.得到最终分类器:
$$F(x)=sign(\sum_{i=1}^N\alpha_m G_m (x))$$
假设已经经过$m-1$轮迭代，得到$F_{m-1} (x)$，根据前向分步，我们可以得到：
$$F_m (x)=F_{m-1} (x)+\alpha_m G_m (x)$$
我们已经知道AdaBoost是采用指数损失，由此可以得到损失函数：
$$
\begin{aligned}
Loss=&\sum_{i=1}^Nexp?(-y_i F_m (x_i ))\
=&\sum_{i=1}^Nexp?(-y_i (F_{m-1} (x_i )+\alpha_m G_m (x_i )))
\end{aligned}
$$
这时候,$F_{m-1}(x)$是已知的，可以作为常量移到前面去:
$$Loss=\sum_{i=1}^N\widetilde{w_{m,i}} exp?(-y_i \alpha_m G_m (x_i ))$$
其中，$\widetilde{w_{m,i}}=exp?(-y_i (F_{m-1} (x)))$ 就是每轮迭代的样本权重！依赖于前一轮的迭代重分配。
再化简一下：
$$
\begin{aligned}
\widetilde{w_{m,i}}=&exp?(-y_i (F_{m-1} (x_i )+\alpha_{m-1} G_{m-1} (x_i )))\=&\widetilde{w_{m-1,i}} exp?(-y_i \alpha_{m-1} G_{m-1} (x_i ))
\end{aligned}
$$
继续化简Loss：
$$
\begin{aligned}
Loss=\sum_{y_i=G_m(x_i)}\widetilde{w_{m,i}} exp(-\alpha_m)+\sum_{y_i≠G_m(x_i)}\widetilde{w_{m,i}} exp?(\alpha_m)\=\sum_{i=1}^N\widetilde{w_{m,i}}(\frac{\sum_{y_i=G_m(x_i)}\widetilde{w_{m,i}}}{\sum_{i=1}^N\widetilde{w_{m,i}}}exp(-\alpha_m)+\frac{\sum_{y_i≠G_m(x_i)}\widetilde{w_{m,i}}}{\sum_{i=1}^N\widetilde{w_{m,i}}}exp(\alpha_m))
\end{aligned}
$$
其中
$\frac{\sum_{y_i≠G_m(x_i)}\widetilde{w_{m,i}}}{\sum_{i=1}^N\widetilde{w_{m,i}}}$就是分类误差率$e_m$
所以
$Loss=\sum_{i=1}^N\widetilde{w_{m,i}}exp?(-\alpha_m)+e_m exp?(\alpha_m))$
这样我们就得到了化简之后的损失函数
对$\alpha_m$求偏导令$\frac{?Loss}{?\alpha_m }=0$得到：
$$\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}$$
《统计学习方法》上面有个小例子，可以用来加深印象
有如下的训练样本，我们需要构建强分类器对其进行分类。x是特征，y是标签。