Adaboost

作者: GQRstar | 来源:发表于2019-08-04 21:17 被阅读1次

1.Boosting提升算法

Adaboost是典型的Boosting提升算法。Boosting算法是将弱学习算法提升为强学习算法的过程。Boosting算法主要涉及两个部分：加法模型和前向分布算法。加法模型是指强学习器是由一系列的弱学习器线性相加而成。一般的组合形式如下所示：
$F_M(x;P)=\sum_{m=1}^{n}{\beta_mh(x;a_m)}$
其中， $h(x;a_m)$ 就是一个个弱分类器， $a_m$ 是弱学习器的最优参数， $\beta_m$ 是弱学习器所占比重, $P$ 是 $\beta_m$ , $a_m$ 的组合。这些弱学习器线性相加组成最终的强学习器。
前向分步算法是指在训练过程中，下一轮迭代产生的分类器是在上一轮的基础上训练得到的。可以用下式表达迭代过程：
$F_m(x)=F_{m-1}(x)+\beta_mh_m(x;a_m)$
在训练过程中使用的损失函数的不同，也就有了不同类型的Boosting算法，AdaBoost的损失函数是指数损失函数。
boosting算法的基本思想如下图所示：

boosting算法基本思想
从图中可以看出，Boosting算法首先从训练集中用初始权重训练一个弱学习器，根据弱学习器的表现更新样本的权重，使得分错的样本权重加大，在下轮迭代中受到更大的重视。如此往复进行，知道弱学习器的数量达到指定数目。

2.AdaBoost算法

在AdaBoost算法中主要存在4个问题：
（1）如何计算弱学习器的误差率 $e$ ?
（2）如何计算弱学习器的权重 $\alpha$ ?
（3）如何更新样本的权重？
（4）如何将弱学习器组合为强学习器？
假设我们的训练集样本是
$T=\{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\}$
第 $k$ 个弱学习器的训练集的样本权重为
$D(k)=(w_{k1},w_{k2},...,w_{km});w_{1i}=\frac{1}{m};i=1,2,3,...,m$

2.1分类问题

假设处理的是二分类问题，输出是{-1,1}，则第 $k$ 个弱分类器 $G_k(x)$ 在训练集上的加权误差率为:
$e_k=P(G_k(x_i){\neq}y_i)=\sum_{i=1}^mw_{ki}I(G_k(xi)\neq{y_i})$
第 $k$ 个弱学习器 $G_k(x)$ 的权重系数为 $\alpha_k=\frac{1}{2}log\frac{1-e_k}{e_k}$ ，从上面两个公式可以看出，弱学习器的权重与误差率成反比。
第三步需要更新样本的权重D，假设第 $k$ 个弱分类器的样本权重系数为 $D(k)=(w_{k1},w_{k2},...,w_{km})$ ，则第 $k+1$ 个弱分类器的样本权重系数为 $w_{k+1,i}=\frac{w_{ki}}{Z_k}exp(-\alpha_{k}y_{i}G_k(x_i))$ ,其中 $Z_k=\sum_{i=1}^mw_{ki}exp(-\alpha_{k}y_{i}G_k(x_i))$ 为规范因子。从权重计算公式中可以看出，若样本分对，系数会减小，否则系数会增大。
对弱分类器组合一般采用线性加权的方法：
$f(x)=sign(\sum_{k-1}^K\alpha_kG_k(x))$

2.2回归问题

在回归问题中，同样要解决上面提到的四个问题，首先是弱学习器误差率的计算，对于第 $k$ 个弱学习器，计算其在训练集上的最大误差 $E_k=max|y_i-G_k(x_i)|,i=1,2,...,m$ ,然后计算每个样本的相对误差： $e_{ki}=\frac{|y_i-G_k(x_i)|}{E_k}$ ,上式计算的是线性误差，若采用平方误差，计算公式为： $e_{ki}=\frac{(y_i-G_k(x_i))^2}{E_k^2}$ ，若要计算指数误差，其计算公式为： $e_{ki}=1-exp(\frac{-y_i+G_k(x_i)}{E_k})$ 。
计算完单个样本的误差后，需要计算弱学习器在整个训练集上的表现性能。最后得到第 $k$ 个弱学习器的误差率为: $e_k=\sum_{i=1}^{m}w_{ki}e_{ki}$ 。
第 $k$ 个弱学习器的权重系数 $\alpha_k$ 的计算公式为: $\alpha_k=\frac{e_k}{1-e_k}$ ，下一步需要更新训练集样本的权重D，对于第 $k+1$ 个弱学习器的样本权重系数为： $w_{w+1,i}=\frac{w_{ki}}{Z_k}\alpha_k^{1-e_{ki}}$ ，其中的 $Z_k$ 为规范化因子 $Z_k=\sum_{i=1}^{m}w_{ki}\alpha_{ki}^{1-e_{ki}}$ 。
最后一步是将一得到的若干弱学习器组合，与分类问题不同，最终的强学习器为 $f(x)=G_{k^*}(x)$ ，其中的 $G_{k^*}$ 是所有的 $ln\frac{1}{\alpha_k},k=1,2,...,K$ 中位数对应的弱学习器。

3.损失函数优化

Adaboost模型是加法模型，学习算法是前向分步算法，分类问题的损失函数是指数函数。在迭代学习过程中，利用前一弱学习器的结果更新训练集的权重，进行下一轮的学习，第 $k-1$ 轮的强学习器为: $f_{k- 1}(x)=\sum_{i-1}^{k-1}\alpha_iG_i(x)$ ，而第 $k$ 轮的强学习器为 $f_k(x)=\sum_{i=1}^{k}\alpha_iG_i(x)$ ，比较上面两个公式可以得出 $f_k(x)=f_{k-1}(x)+\alpha_kG_k(x)$ ，损失函数为 $argmin_{\alpha,G}\sum_{i=1}^mexp(-y_if_k(x_i))$

4.正则化

为防止模型过拟合，通常会加入正则项，通常称之为步长（learning rate）。定义为 $v$ ，加入正则项之后的模型迭代公式为: $f_k(x)=f_{k-1}(x)+v\alpha_kG_k(x)$ ， $v$ 的取值范围为(0,1]。对于同样的模型效果，较小的 $v$ 意味着更多的迭代次数。通常使用步长和迭代最大次数一起决定模型的拟合效果。

5.总结

在AdaBoost算法中的弱学习器使用最广泛的是决策树和神经网络。对于决策树，AdaBoost使用的是CART分类树，回归使用的是CART回归树。
AdaBoost也有其优缺点，优点是：精度高，不易过拟合；缺点是：对异常点较敏感，异常样本容易获得较高的权重，影响最终强学习器的预测准确性。

参考链接

（如有不同见解，望不吝指教！）

Adaboost

1.Boosting提升算法

2.AdaBoost算法

2.1分类问题

2.2回归问题

3.损失函数优化

4.正则化

5.总结

参考链接

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

工作