之前的博客中讲到了集成学习按照个体学习器之间是否存在依赖关系可以分为两类，第一个是个体学习器之间存在强依赖关系，另一类是个体学习器之间不存在强依赖关系。前者的代表算法就是是boosting系列算法。在boosting系列算法中， Adaboost是最著名的算法之一。Adaboost既可以用作分类，也可以用作回归。本文就对Adaboost算法做一个总结。
Adaboost算法推导：
Adaboost算法有多种推导方式，比较容易理解的是基于“加性模型”，即基学习器的线性组合：
$$ H(x)=\sum_{t=1}^{T}\alpha _{t}h_{t}(x) $$
来最小化指数损失函数：
$$ \iota _{exp}(H|D)=e^{-f(x)h(x)} $$
算法步骤如下：
若$H(x)$能令指数损失函数最小化，则损失函数对$H(x)$的偏导为：
$$ \frac{\alpha \iota _{exp}(H|D)}{\alpha H(x)} = e^{-H(x)}P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x) $$
令其等于零，可解的：
$$ H(x)=\frac{1}{2}ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)} $$
因此，有：
这意味着$sign(H(x))$达到了贝叶斯最优错误率，换言之，若指数损失函数最小化，则分类错误率也将最小化，这说明指数损失函数式分类任务原本0/1损失函数的一致的替代损失函数，而且数学x性能好，我们那他来作为优化目标。
在Adaboost算法中，第一个基分类器$h_1$是通过直接将基学习算法用于初始数据分布而得，此后迭代第生成$h_t$和$\alpha _t$,当基分类器$h_t$基于分布$D_t$产生后，该基学习器的权重$\alpha _t$应使得$\alpha _th_t$最小化指数损失函数:
$$ \frac{\partial \iota _{exp}(\alpha _{t}h_t|D_t)}{\partial \alpha _{t}} = \frac{\partial e^{(-f(x)\alpha _th_{t}(x))}}{\partial \alpha _{t}}\\=e^{-\alpha _{t}}P(f(x)=h_{t}(x)) + e^{\alpha _{t}}P(f(x)\neq h_{t}(x))\\=e^{-\alpha _{t}}(1-\epsilon _{t})+e^{\alpha _{t}}\epsilon _{t} $$
其中，$\epsilon _{t}=P(h_{t}(x)\neq f(x))$。
令其等于零，可解得：
$$ \alpha _{t}=\frac{1}{2}ln\left ( \frac{1-\epsilon _{t}}{\epsilon _{t}} \right ) $$
这就是分类器权重更新公式。
Adboost算法在获得$H_{t-1}$之后样本分布进行调整，使下一轮的基学习器$h_t$能纠正$H_{t-1}$的一些错误，理想的$h_t$能纠正$H_{t-1}$的全部错误，即最小化：
$$ \iota _{exp}(H_{t-1}+h_{t}|D)=e^{-f(x)(H_{t-1}(x)+h_{t}(x))}=e^{-f(x)H_{t-1}(x)h_{t}(x)} $$
注意到$f^2(x)=h^2_t(x)=1$,k可使用$e^{-f(x)h_t(x)}$的泰勒展开式近似为：
于是，理想的基学习器
这就得到了样本分布的更新公式。
在《统计学习方法》中，没有对这部分给出详细说明，《机器学习》一书做出了详细的解释，上面推导将规范化因子替换后，二者就对应起来，规范化因子为：
$$ Z_m=\frac{e^{-f(x)(H_{t-1}(x))}}{e^{-f(x)H_{t1}(x)}}=e^{-\alpha _tf(x)h_t(x)} $$
adaboost在分类中的使用：
这里我们对AdaBoost二元分类问题算法流程做一个总结。
输入为样本集$T=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}$，输出为${-1, +1}$，弱分类器算法, 弱分类器迭代次数K。
输出为最终的强分类器$f(x)$
1) 初始化样本集权重为
$$ D(1) = (w_{11}, w_{12}, ...w_{1m}) ;\;\; w_{1i}=\frac{1}{m};\;\; i =1,2...m $$
2) 对于k=1,2，...K:
- a) 使用具有权重$D_k$的样本集来训练数据，得到弱分类器$G_k(x)$
- b)计算$h_k(x)$的分类误差率
$$ \epsilon _k = P(h_k(x_i) \neq y_i) = \sum\limits_{i=1}^{m}D_{ki}I(h_k(x_i) \neq y_i) $$
- c) 计算弱分类器的系数
$$ \alpha_k = \frac{1}{2}log\frac{1-\epsilon _k}{\epsilon _k} $$
- d) 更新样本集的权重分布
$$ D_{k+1,i} = \frac{D_{ki}}{Z_K}exp(-\alpha_kf_i(x)h_k(x_i)) \;\; i =1,2,...m $$
3) 构建最终分类器为：
$$ f(x) = sign(\sum\limits_{k=1}^{K}\alpha_kh_k(x)) $$
对于Adaboost多元分类算法，其实原理和二元分类类似，最主要区别在弱分类器的系数上。比如Adaboost SAMME算法，它的弱分类器的系数
$$ \alpha_k = \frac{1}{2}log\frac{1-\epsilon _k}{\epsilon _k} + log(R-1) $$
其中R为类别数。从上式可以看出，如果是二元分类，R=2，则上式和我们的二元分类算法中的弱分类器的系数一致。
参考：周志华《机器学习》
李航《统计学习方法》
刘建平：集成学习之Adaboost算法原理小结
