机器学习11 AdaBoost 与前向分步算法

这一篇开始介绍Boosting，我们先介绍Boosting中的第一个模型， AdaBoost, 二分类学习模型

AdaBoost的基本原理，是每次改变样本的权重，增大本次学习之前分类错误的样本的权重，减小已经分类正确的样本的权重，每次学习一个基分类器，加到现有的模型里。然后根据新的分类结果，更新样本权重，学习新的基分类器，并将这些分类器线性组合成为一个强分类器。

$f(x) = \sum_{m=1}^M\alpha _mG_m(x)$

$G(x) = sign(f(x))$

为了方便理解，我们从拿到数据集开始一步步考虑这个模型。

数据集 $D = \{{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}\}$

我们在一开始给每一个数据同样的权重， $D_1 = w_{1i} = \frac{1}{N}$

然后我们用一个基模型(例如cart分类树)去训练数据集，得到一个基分类器。 $G_1(x): x\rightarrow \{-1,1\}$

我们可以得到这个基分类器的分类误差: $e_1 = \sum_{i=1}^N p(G_1(x_i) \neq y_i) = \sum_{n=1}^Nw_{1i}1(G_1(x_i) \neq y_i)$

然后我们就可以得到这个基分类器的权重 $\alpha _1 = \frac{1}{2} log\frac{1-e_1}{e_1}$ ，所以分类正确率越高，模型权重越大

接下来要更新数据集的权重了， $w_{2,i} = \frac{w_{1,i}}{z_1}exp(-\alpha_1y_iG_1(x_i))$ , 其中 $z_1 = \sum_{i=1}^Nw_{1,i}exp(-\alpha_1y_iG_1(x_i))$

然后构建第二个基分类器，得到第二个基分类器的分类误差，基分类器权重，更新样本权重，再构建第三个基分类器。如此这般依次构建一个个基分类器，最后根据基分类器权重线性组合成一个大的分类器即可。

到现在只是说了一下模型的基本概念，现在开始我们来仔细的解释模型。

AdaBoost算法，是模型为加法模型，损失函数为指数函数，学习算法为前向分步算法的二分类学习方法。我们一步步看这句话

加法模型比较好理解，最终的模型是基模型的线性组合。

现在我们来介绍一下什么是前向分步算法。

在加法模型下， $f(x) = \sum_{m=1}^M\beta _mb(x;\gamma_m)$

在给定数据集即损失函数的情况下，只需要最小化 $L(y, f(x))$ , 即 $\mathop{argmin}_{\beta _m,\gamma_m} \sum_{i=1}^NL(y_i, \sum_ {m=1}^M \beta_mb(x_i;\gamma_m)$

直接优化这个是很难的，前向分步算法的想法，就是每次只学习一个基模型及其系数，慢慢逼近最优化的模型，起到了简化这个优化模型的复杂度。

现在我们根据前向分步算法来推出AdaBoost,首先定义损失函数为指数损失。

$L(y,f(x)) = exp(-yf(x))$

在第m-1步学习后，得到 $f_{m-1}(x) = f_{m-2}(x) +\alpha_ {m-1} G_{m-1}(x)$

所以我们第m步的目标是， $\mathop{argmin}_{\alpha _m,G_m} \sum_{i=1}^Nexp[-y_i(f_{m-1}(x_i) +\alpha _mG_m(x_i)]$

定义 $\bar w_{m,i} = exp[-y_if_{m-1}(x_i)]$ ,这是没有归一化过的 $w_{m,i}$

因为 $w_{m,i} = \frac{w_{m-1,i}}{z_{m-1}}exp(-\alpha_{m-1}y_iG_{m-1}(x_i)) = \frac{w_{m-2,i}}{z_{m-1}*z_{m-2}}exp(-\alpha_{m-1}y_iG_{m-1}(x_i)-\alpha_{m-2}y_iG_{m-2}(x_i)) = .....$

$=\frac{w_{1,i}}{\prod_{j=1}^{m-1}z_j } exp(-y_if_{m-1}(x)) = \frac{w_{1,i}}{\prod_{j=1}^{m-1}z_j } \bar w_{m,,1}$ , $w_{1,i} = \frac{1}{N}$ ，

所以 $\bar w_{m,i}$ 是没有归一化过的 $w_{m,i}$ 。为方便理解，下面就用 $w_{m,i}$ 代替 $\bar w_{m,i}$ 了，因为差一个归一化因子，不会影响优化问题

当前的目标函数为 $\mathop{argmin}_{\alpha _m,G_m} \sum_{i=1}^Nw_{m,i}exp[-y_i\alpha _mG_m(x_i)]$

我们先求 $G_m$ ， $\alpha _m$ 是个大于0的数，当 $y_i \neq G_m(x_i)$ 的时候，是 $w_{m,i}e^{2\alpha}$ , 当 $y_i = G_m(x_i)$ ，是 $w_{m,i}e^{-2\alpha}$

所以只需要在 $w_{m,i}$ 权重下，误分类的点越少越好。

$G_m^* = \mathop{argmin}_{G_m} \sum_{i=1}^Nw_{m,i}I(y_i \neq G_{m}(x_i))$ , 这就是AdaBoost每一步学习到的模型。

将 $G_m^*$ 带入目标函数，求 $\alpha _m$ ,

$\sum_{i=1}^n w_{m,i}exp[-y_i\alpha G(x_i)] = \sum_{y_i = G_m(x_i)} w_{m,i}e^{-\alpha} + \sum_{y_i \neq G_m(x_i)}w_{m,i}e^{\alpha}$

$=(e^\alpha - e^{-\alpha})\sum_{i=1}^N w_{m,i}1(y_i \neq G_m(x_i)) + e^{-\alpha}\sum_{i=1}^Nw_{m,i}$ ( $\Delta$ )

$\frac{\partial \Delta}{\partial \alpha} = (e^\alpha + e^{-\alpha})\sum_{i=1}^Nw_{m,i}1(y_i \neq G_m(x_i)) - e^{-\alpha}\sum_{i=1}^N w_{m,i}$

$\Rightarrow (e^{2\alpha} +1)e_m = 1\Rightarrow e^{2\alpha} = \frac {1 - e_m}{e_m}$

推出 $\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$

其中 $e_m = \sum_{i=1}^Nw_{m,i}1(y_i \neq G_m(x_i))$ ,

这就是AdaBoost里第m个基模型的误差，现在我们已经求出了AdaBoost里的基模型和基模型权重，现在我们来看样本权重的更新。

由 $f_m(x) = f_{m-1}(x) +\alpha_mG_m(x)$ 和 $\bar w_{m,i} = exp[-y_if_{m-1}(x_i)]$

$\bar w_{m+1,i} = exp[-y_if_m(x_i)] = exp[-y_i(f_{m-1}(x) +\alpha_mG_m(x))] = \bar w_{m,i}exp[-y_i\alpha_mG_m]$

正如上面所讲，只要一个归一化因子，就可以得到和AdaBoost里一样的权重更新了。

至此，我们从加法模型和前向分步算法，在损失函数为指数函数的情况下，推出了AdaBoost算法，由此也证明了AdaBoost算法，是模型为加法模型，损失函数为指数函数，学习算法为前向分步算法的二分类学习方法。

下一篇会介绍另一种boosting模型，梯度树

转载请注明，谢谢

机器学习11 AdaBoost 与 前向分步算法

机器学习11 AdaBoost 与前向分步算法