Boost-Adaboost

2020-02-05 本文已影响0人 zhouycoriginal

我们知道boost系列是强依赖关系, 有这个依赖, 各个学习器之间还有这些问题没有解决:

如何计算学习的误差率 $e$
如何得到弱学习器的权重 $\alpha$
如何更新样本权重?
使用何种结合策略?

Adaboost

假定这里给一个二分类的数据集:
$T={(x_1,y_1),(x_2,y_2),...,(x_m,y_m)}$
我们先来看一下Adaboost的步骤

输入数据T
初始化训练数据的权重分布:
$D_1=(w_{11},w_{12},...,w_{1m}), W_{1i}= \frac{1}{m}, i=1,2,...,m$
对 $k=1,2,...,K$ :

使用具有权值分布的 $D_k$ 训练集进行学习, 得到基本的分类器:
$G_k(x):X-> \{-1,1\}$
计算 $G_k(x)$ 在训练数据集上的误差率
$e_k=P(G_k(x_i)\not=y_i)=\sum_{i=1}^{m}w_{ki}I(G_k(x_i)\not=y_i)$
计算 $G_k(x)$ 的系数:
$\alpha_m=\frac{1}{2} \log \frac{1-e_m}{e_m}$
更新训练集的权重分布:
$D_{k+1}=(w_{k+1,1},w_{k+1,2},...,w_{k+1,i})$
$w_{k+1,i}=\frac{w_{ki}}{Z_k} e^{-\alpha_ky_iG_k(x_i)},i=1,2,3..m$
此处 $Z_k$ 是规范化因子:
$Z_k=\sum_{i=1}^{m}w_{ki}e^{(-\alpha_my_iG_k(x_i))}$

构建基本的纤性分类器组合:
$f(x)=\sum_{k=1}^{K}\alpha_kG_k(x)$

Adaboost的损失函数

Adaboost损失函数采用指数损失, 指数损失比较少见
$L(y,f(x))=e^{-yf(x)}$
下面来推导一下其损失函数, 该算法为加法模型, 学习算法为前向分步算法, 前向分步算法其实就是: 通过前一轮学习器的学习, 来更新后一个弱学习器的训练集权重,按照上面的定义, 各轮学习器为:
$f_{k-1}(x)=\sum_{k=1}^{K-1} \alpha_kG_k(x)$
$f_{k}(x)=\sum_{k=1}^{K} \alpha_kG_k(x)$
显然, $f_k(x)=f_{k-1}(x)+\alpha G_k(x)$ 是成立的
利用前向分布, 我们可以得到每个新的子分类器的损失函数为:
$L(\alpha_k, G_k(x))=argmin \sum_{i=1}^{m}e^{-y_i(f_{k-1}(x)+\alpha_{k} G_{k}(x))}$
令 $w_{ki}=e^{-y_if_{k-1}(x)}$ ,它的值不依赖于 $\alpha$ 或者 $G_k$ ,仅依赖于 $f_{k-1}(x)$ ,
将其代入损失函数得到:
$L(\alpha_k, G_k(x))=argmin \sum_{i=1}^{m}w_{ki}e^{-y_i\alpha_k G_k(x)}$
我们知道 $y_iG_k(x)$ 其实是一个输出, 我们可以用一个指示函数 $I$ 代替, 那么我们得到
$L(\alpha_k, G_k(x))=argmin \sum_{i=1}^{m}w_{ki}e^{-y_i\alpha_kI(y_i\not=G_k(x))}$
我们对 $\alpha$ 求偏导:
$\alpha_k=\frac{1}{2}\log \frac{1-e_k}{e_k}$
最终, $e_k$ 求实我们的分类误差率
上面提到的四个问题, 基本上都已经解决了, 那么Adaboost如何处理回归问题?
回归问题, 基本上只用修改误差就可以了

首先我们计算其在训练集上的最大误差
$E_k=max|y_i-G_k(x_i)|$
计算每个样本上的误差:

如果是线性误差:
$e_{ki}=\frac{|y_i-G_k(x_i)|}{E_k}$
平凡误差: 略

计算误差率
$e_k=\sum_{i=1}^{m}w_{ki}e_{ki}$
其他步骤都是一样的

Adaboost正则化

为了防止Adaboost过拟合，我们通常也会加入正则化项:
没有加正则化:
$f_k(x)=f_{k-1}(x)+\alpha G_k(x)$
加了正则化v:
$f_k(x)=f_{k-1}(x)+v\alpha G_k(x)$
$v$ 的取值范围在0~1之间, 更小的 $v$ 代表我们需要更多的迭代次数

总结

理论上任何学习器都可以用于Adaboost.但一般来说，使用最广泛的Adaboost弱学习器是决策树。对于决策树，Adaboost分类用了CART分类树，而Adaboost回归用了CART回归树。
Adaboost的主要优点有：

Adaboost作为分类器时，分类精度很高
在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
作为简单的二元分类器时，构造简单，结果可理解。
不容易发生过拟合
Adaboost的主要缺点有：
对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性

Boost-Adaboost

Adaboost

Adaboost的损失函数

Adaboost正则化

总结

猜你喜欢

热点阅读