Adaboost算法

基本思想

Adaboost是adaptive boosting的缩写，是一种基于Boosting的融合算法，其核心思想是将多个弱分类器通过添加相应的权值组合成一个强分类器。对于分类效果好的弱分类器给更大的权值，反之则给更小的权值。同时它还是一种迭代算法，后一个弱分类器通过增加前一个弱分类器分错的样本的权重来达到更好的分类效果。最后将所有的弱分类器结合成一个强分类器，作为最终的算法模型。
通过Adaboost算法的定义可以看出，算法核心由两部分组成：

第m个弱分类器的权重 $a_m = \frac{1}{2}ln\frac{1-\varepsilon_m}{\varepsilon_m}$ , $\varepsilon_m$ 为第m次迭代的错误率 ;
第m+1次样本迭代的权重 $W_{m+1} = \frac{W_m}{Z_m}e^{a_my_iG_m(x_i)}$
$Z_m$ 为归一化因子， $G_m$ 为弱分类器解析函数

$F(x) = \alpha_1f_1(x)+\alpha_2f_2(x)...+\alpha_nf_n(x)$

$F_2(x) = \alpha_1f_1(x)+\alpha_2f_2(x)=F_1(x)+\alpha_2f_2(x)$
第一次迭代所有的样本权重:
$D_1 = (W_{11}+W_{12}+W_{13}+W_{14}+...W_{1n})$
由此看出，Adaboost算法的每次迭代的权重需要通过前一次的权重得出，所以不能并行计算。

算法推导

弱学习器： $G(x) =\begin{cases}1 \\-1\end{cases}$ 只有两种结果，关注特征也比较少，分类能力较弱。
强学习器： $f(x) = \sum_{m=1}^m a_mG_m(x)$ , $a_m$ 每个弱分类器的权重。
将每个强分类器通过计算的权值进行线性组合得到强分类器。
损失函数： $loss = \frac{1}{n}\sum_{i=1}^nI(G(x) \neq y_i)\le \frac{1}{n}\sum_{i=1}^n e^{(-y_isign(f(x_i)))}$
n 为样本个数； $I()$ 函数满足条件返回1，不满足则返回1； $f(x)$ 为强分类器预测值，套一个sign函数使其返回1或-1，大于0返回1，小于0返回-1。

其中：函数 $I(G(x) \neq y_i)$ 判断分类器 $G(x)$ 与实际标签值 $y_i$ 是否相等，即是否预测正确，正确则相等，返回值为0；不正确则不想等，返回值为1。那么求和之后的值即为该分类器分错了多少个样本，即损失。
但是该函数并不单调，所以无法进行优化。那么通过优化后面的式子来达到优化损失函数的效果。

那么损失函数的优化即转化为对 $\frac{1}{n}\sum_{i=1}^n e^{(-y_i(f(x_i)))}$ 的优化问题。
损失函数优化的最终目的是让函数可以和分类器同趋势反映模型分类的准确率，那么该函数如何正确反映模型分类的准确率，通过下面推导得出。

分析该函数， $y_i$ 及 $(f(x_i))$ 的取值分别有两种：
$y_i =\begin{cases}1 \\-1\end{cases}$ $f(x) =\begin{cases}>0 \\<0\end{cases}$
可通过表格更直观感受：

-yf(x)	y = 1	y = -1
f(x)>0	<0 分对了（1）	>0 分错了（1）
f(x)<0	>0 分错了（2）	<0 分对了（2）

通过图像观察优化方向（a = 2.1和e差不多，趋势也一样了，不要在意这些细节）

指数函数图像

所谓优化损失函数，就是以为了让损失函数尽可能小为核心思想，对函数进行优化。不论分对还是分错，都要通过变化f(x)使损失函数尽可能小：
所以：x轴

-y_if(x_i)

，y轴

e^{(-y_if(x_i))}

有下面四种情况

在分对了（1）情况下，f(x)>0， f(x)↑
在分对了（2）情况下，f(x)<0， f(x)↓
在分错了（1）情况下，f(x)>0， f(x)↓
在分错了（2）情况下，f(x)<0， f(x)↑
按以上趋势变化
$-y_if(x_i)$ 绝对值越大，损失函数越往左优化，损失函数 $e^{(-y_if(x_i))}$ 值也就越小。就可以达到优化的目的。

该损失函数的优化是基于函数空间的优化，也就是说优化的并不是像梯度下降那样的函数的参数的值，可以通过回代算出的值。这里的f(x)是优化的对象，而f(x)是不能通过带入带回算出来的值。

结果： $loss = \frac{1}{n}\sum_{i=1}^n e^{(-y_i(f(x_i)))}$

$f_{k-1}(x) = \sum_{i=1}^{k-1}a_iG_i(x)$ 前k-1个弱分类器组成的分类器
$f_k(x) = \sum_{i=1}^ka_iG_i(x)$ 前k个弱分类器组成的分类器
$f(x) = f_{k-1}(x) + a_kG_k(x)$
强分类器，就是前k-1个弱分类器组成的分类器加上最后一个弱分类器。有迭代关系
损失函数优化：
$loss(a_m, G_m(x)) = \frac{1}{n}\sum_{i=1}^ne^{-y_i(f_{m-1}(x_i)+a_mG_m(x_i))}$
$a_m$ 为第m个学习器的权重； $G_m(x)$ 为第m个弱分类器，n为样本个数。
优化损失函数：
$= \frac{1}{n}\sum_{i=1}^ne^{-y_if_{m-1}(x_i)}e^{-y_ia_mG_m(x_i)}$ 把e的指数项拆开
$e^{-y_if_{m-1}(x_i)}$ 样本权重从上一次迭代中获得的已知当作常数 $\overline W_{mi}$
$=\frac{1}{n}\sum_{i=1}^n W_{mi}e^{-y_ia_mG_m(x_i)}$
$a_m$ 即为所求的学习器权重
$y_i$ 为样本的真实标签，结果两种1， -1
$G_m(x_i)$ 为样本预测标签，结果两种1，-1
分对→ $y_i= G_m(x_i)$ ; 分错 → $y_i\neq G_m(x_i)$
则函数可变为：
$= \sum_{y_i= G_m(x_i)}\overline W_{mi}e^{-a_m} + \sum_{y_i\neq G_m(x_i)}\overline W_{mi}e^{a_m}$ 第一项分对的个数，第二项分错的个数

两项同时除以所有样本的权重 $\sum_{i=1}^n\overline W_{im}$ ，进行归一化，得：

$\frac{ \sum_{y_i= G_m(x_i)}\overline W_{mi}}{\sum_{i=1}^n\overline W_{mi}}e^{-a_m}+ \frac{ \sum_{y_i\neq G_m(x_i)}\overline W_{mi}}{\sum_{i=1}^n\overline W_{mi}}e^{a_m}$
那么上式的第二项 $e^{a_m}$ 的系数即为分错的概率即错误率，
那前一项的系数即为正确率（1-错误率）
为表达方便，令它为 $\varepsilon_m$ ，则上式可写作：
$(1-\varepsilon_m)e^{-a_m}+\varepsilon_me^{a_m}$
通过上式求出样本权重 $a_m$ 即对 $a_m$ 求导，令导数为0即可。