从零开始理解AdaBoost算法：前向分布算法（四）【数学推导】

本文主要是介绍从零开始理解AdaBoost算法：前向分布算法（四）【数学推导】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

理解 AdaBoost 算法的原理

在理解 AdaBoost 算法原理的过程中，两个关键问题需要注意：

1. 权重是如何由分类误差决定的。
2. 如何调整前一轮错误和正确的样本的权值。

优化问题

AdaBoost 解决的是二分类问题，数据集表示为：
$$T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$$
其中， y i ∈ { − 1 , + 1 } y_i \in \{-1, +1\} yi​∈{−1,+1}。

模型

AdaBoost 使用的是加法模型：
$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$

化成递推式
$$f_m(x)=f_{m-1}(x)+{\alpha }_m{G}_m(x)$$

最终分类器为：
$$G(x)=\text{sign}[f(x)]$$
sign 函数如下所示：

• 当 $f(x)\ge 0$，$G(x)=1$
• 当 $f(x)<0$，$G(x)=-1$
  

损失函数

使用的是指数损失函数：
$$L(y,f(x))=\exp [-yf(x)]$$

当 $G(x)$ 分类正确时，$f(x)$ 与 $y$ 同号，$-yf(x)<0$ ，$L(y,f(x))\le 1$；
当 $G(x)$ 分类错误时，$f(x)$ 与 $y$ 异号，$-yf(x)>0$，$L(y,f(x))>1$。

因此，指数函数的图像说明了分类正确时损失较小，分类错误时损失较大。

第一个巧思：损失函数视为权值

这个特性适合作为 AdaBoost 算法中调整权值的方法：对于$G_m(x)$如何提高前一轮错误的权值，降低正确的权值
$${\bar{w}}_{mi}=\exp \left[-y_i{f}_{m-1}\left(x_i\right)\right]$$

单个样本的损失函数

$$L(y,f_m(x))=\exp [-y{f}_m(x)]$$
带入加法模型 $f(x)={\sum }_{m=1}^M{\alpha }_m{G}_m(x)$ 得到，
$$L(y,f_m(x))=\exp [-y\sum _{m=1}^M{\alpha }_m{G}_m(x)]$$
展开后得到，
$$L(y,f_m(x))=\exp [-y(f_{m-1}(x)+{\alpha }_m{G}_m(x))]$$

总体损失函数

将所有样本放进去：
$$\sum _{i=1}^N\exp [-y_i(f_{m-1}(x_i)+\alpha G_m(x_i))]$$

前向分布算法

理解损失函数后，需要使用前向分布算法对其进行优化：
$$({\beta }_m,{\gamma }_m)=\arg \underset{\beta ,\gamma }{\min }\sum _{i=1}^{N}L(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma ))$$

在第 m 轮时，
$$({\alpha }_m,{\gamma }_m)=\arg \underset{\alpha ,\gamma }{\min }\sum _{i=1}^N\exp [-y_i(f_{m-1}(x_i)+\alpha G_m(x_i))]$$

式子变换

使用指数运算法则 $e^{a+b}=e^a\ast e^b$ 进行变换，得到：
$$({\alpha }_m,{\gamma }_m)=\arg \underset{\alpha ,\gamma }{\min }\sum _{i=1}^N\exp [-y_i(f_{m-1}(x_i))]\exp [-y_i\alpha G_m(x_i)]$$

将 $\exp [-y_i(f_{m-1}(x_i))]$ 视为权值：
$$({\alpha }_m,{\gamma }_m)=\arg \underset{\alpha ,\gamma }{\min }\sum _{i=1}^N{\bar{w}}_{mi}\exp [-y_i\alpha G_m(x_i)]$$

继续分析式子，$G_m(x_i)$ 有两个取值可能：

• $G_m(x_i)=y_i$
• $G_m(x_i)\ne y_i$

进一步展开，划分为两类：
$$({\alpha }_m,{\gamma }_m)=\arg \underset{\alpha ,\gamma }{\min }(\sum _{y_i=G(x_i)}{\bar{w}}_{mi}\exp (-\alpha )+\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}\exp (\alpha ))$$

化简得到，
$$({\alpha }_m,{\gamma }_m)=\arg \underset{\alpha ,\gamma }{\min }(\exp (-\alpha )\sum _{y_i=G(x_i)}{\bar{w}}_{mi}+\exp (\alpha )\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi})$$

求解

优化 $G_m(x)$

当分类误差率最小时，得到最优的 (G_m(x))：
$$G_m^{\ast }(x)=\arg \underset{G}{\min }\sum _{i=1}^N{\bar{w}}_{mi}I(y_i\ne G(x_i))$$
其中 $I$ 函数在条件 $y_i\ne G(x_i)$ 成立时为 1。

1. $G_m^{\ast }(x)$: 表示在第 (m) 轮迭代中找到的最优分类器。
2. $\arg {\min }_G$: 表示找到使目标函数达到最小值的 $G$。
3. ${\sum }_{i=1}^N{\bar{w}}_{mi}I(y_i\ne G(x_i))$: 表示加权分类误差率的总和。

公式的目标是通过选择合适的分类器 $G(x)$ 来最小化加权分类误差率。其中，加权分类误差率由权重 ${\bar{w}}_{mi}$ 和指标函数 $I(y_i\ne G(x_i))$ 决定。

具体步骤

1. 权重 ${\bar{w}}_{mi}$: 每个样本 $x_i$ 在第 $m$ 轮迭代中的权重，表示该样本的重要性。权重越大，分类器 (G) 对该样本分类错误的代价越高。
2. 指标函数 $I(y_i\ne G(x_i))$: 如果 $y_i$（实际标签）不等于 $G(x_i)$（分类器的预测标签），则 $I$ 函数的值为 1，否则为 0。换句话说，$I(y_i\ne G(x_i))$ 表示分类错误的样本数。
3. 最小化加权分类误差率: 通过调整分类器 $G(x)$，使得加权分类误差率（即权重和分类错误样本数的乘积的总和）最小化。

因此，这个公式表示在所有可能的分类器 $G(x)$ 中，找到一个分类器 $G_m^{\ast }(x)$，使得在加权数据集上的分类错误最少。

示例扩展

为了更好地理解这个公式，可以考虑一个简单的例子：

假设我们有一个包含 5 个样本的数据集，每个样本的初始权重 ${\bar{w}}_{1i}$ 均为 0.2（即每个样本权重相等）。在第一轮迭代中，我们要找到一个分类器 $G_1(x)$，使得加权分类误差率最小。

假设我们有以下数据集：

• 样本 $x_1,x_2,x_3,x_4,x_5$
• 标签 $y_1=1,y_2=-1,y_3=1,y_4=-1,y_5=1$

假设一个分类器 $G(x)$ 预测 $y_i$ 为 ${\hat{y}}_i$。我们需要计算加权分类误差率：
$$\sum _{i=1}^5{\bar{w}}_{1i}I(y_i\ne G(x_i))$$

假设分类器 $G_1(x)$ 的预测结果如下：

• ${\hat{y}}_1=1,{\hat{y}}_2=1,{\hat{y}}_3=-1,{\hat{y}}_4=-1,{\hat{y}}_5=1$

根据公式，分类误差率计算为：
$${\bar{w}}_{11}\cdot 0+{\bar{w}}_{12}\cdot 1+{\bar{w}}_{13}\cdot 1+{\bar{w}}_{14}\cdot 0+{\bar{w}}_{15}\cdot 0$$
即：
$$0.2\cdot 0+0.2\cdot 1+0.2\cdot 1+0.2\cdot 0+0.2\cdot 0=0.4$$

我们通过选择不同的分类器 $G(x)$，使加权分类误差率最小化。例如，如果选择另一个分类器 $G_2(x)$ 的预测结果如下：

• ${\hat{y}}_1=1,{\hat{y}}_2=-1,{\hat{y}}_3=1,{\hat{y}}_4=-1,{\hat{y}}_5=1$

计算误差率：
$${\bar{w}}_{11}\cdot 0+{\bar{w}}_{12}\cdot 0+{\bar{w}}_{13}\cdot 0+{\bar{w}}_{14}\cdot 0+{\bar{w}}_{15}\cdot 0=0$$

在这种情况下，分类器 $G_2(x)$ 使加权分类误差率为 0，因此 $G_2(x)$ 比 $G_1(x)$ 更优。

第二个巧思：优化 ${\alpha }_m$

${\alpha }_m$ 由 $G_m(x)$ 的分类误差率决定：
$$\arg \underset{{\alpha }_m}{\min }(\exp (-\alpha )\sum _{i=1}^N{\bar{w}}_{mi}+(\exp (\alpha )-\exp (-\alpha ))\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi})$$

求导
$$\frac{\partial (e^{-{\alpha }_m}{\sum }_{i=1}^N{\bar{w}}_{mi}+(e^{{\alpha }_m}-e^{-{\alpha }_m}){\sum }_{y_i\ne G(x_i)}{\bar{w}}_{mi})}{\partial {\alpha }_m}=-e^{-{\alpha }_m}\sum _{i=1}^N{\bar{w}}_{mi}+e^{{\alpha }_m}\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}+e^{-{\alpha }_m}\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi})$$

合并同类项得到，
$$=-e^{-{\alpha }_m}(\sum _{i=1}^N{\bar{w}}_{mi}-\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi})+e^{{\alpha }_m}\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}$$
第一个式子中的${\sum }_{i=1}^N{\bar{w}}_{mi}-{\sum }_{y_i\ne G(x_i)}{\bar{w}}_{mi}$意味着，全样本减去错误分类的样本，最后得到的就是分类正确的样本，因此。
$$=-e^{-{\alpha }_m}\sum _{y_i=G(x_i)}{\bar{w}}_{mi}+e^{{\alpha }_m}\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}$$

导数为0
令求导结果为0，得到，
$$e^{{\alpha }_m}\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}=e^{-{\alpha }_m}\sum _{y_i=G(x_i)}{\bar{w}}_{mi}$$

化简并求解，得到：
$${\alpha }_m=\frac{1}{2}\ln \frac{{\sum }_{y_i=G(x_i)}{\bar{w}}_{mi}}{{\sum }_{y_i\ne G(x_i)}{\bar{w}}_{mi}}$$

进一步，分子分母同除 所有样本的权值之和 ${\sum }_{i=1}^N{\bar{w}}_{mi}$ ，得到；
$${\alpha }_m=\frac{1}{2}\ln \frac{\frac{{\sum }_{i=1}^N{\bar{w}}_{mi}}{{\sum }_{i=1}^N{\bar{w}}_{mi}}-\frac{{\sum }_{y_i\ne G(x_i)}{\bar{w}}_{mi}}{{\sum }_{i=1}^N{\bar{w}}_{mi}}}{\frac{{\sum }_{y_i\ne G(x_i)}{\bar{w}}_{mi}}{{\sum }_{i=1}^N{\bar{w}}_{mi}}}$$

其中$\frac{{\sum }_{y_i\ne G(x_i)}{\bar{w}}_{mi}}{{\sum }_{i=1}^N{\bar{w}}_{mi}}$为分类错误的点的权值之和 除以 所有样本的权值——分类误差率 $e_m$，最终得到
$$\frac{1}{2}ln\frac{1-e_m}{e_m}$$

因此，
$${\alpha }_m=\frac{1}{2}ln\frac{1-e_m}{e_m}$$

满足我们的要求：分类误差率越大，${\alpha }_m$越小；

前向更新 $f_m(x)$

$$f_m(x)=f_{m-1}(x)+{\alpha }_m{G}_m(x)$$
在前一步的基础上，加上当前的训练的权重

更新训练数据权值 ${\bar{w}}_{m+1,i}$

前面我们说过，我们是使用指数损失函数来替代权值的，所以我们直接带入即可求得；

根据原始公式
$${\bar{w}}_{mi}=\exp \left[-y_i{f}_{m-1}\left(x_i\right)\right]$$

我们有，
$${\bar{w}}_{m+1,i}=\exp \left[-y_i{f}_m\left(x_i\right)\right]$$

带入 $f_m(x)=f_{m-1}(x)+{\alpha }_m{G}_m(x)$，得到

$${\bar{w}}_{m+1,i}=\exp -y_i(f_{m-1}(x_i)+{\alpha }_m{G}_m(x_i))$$

展开得到，
$${\bar{w}}_{m+1,i}=\exp [-y_i{f}_{m-1}(x_i)]\ast \exp -y_i{\alpha }_m{G}_m(x_i)$$

带入原始式子${\bar{w}}_{mi}=\exp \left[-y_i{f}_{m-1}\left(x_i\right)\right]$ ，我们得到
$${\bar{w}}_{m+1,i}={\bar{w}}_{mi}\ast [\exp -y_i{\alpha }_m{G}_m(x_i)]$$

参考链接：6.【Adaboost】算法原理解析_哔哩哔哩_bilibili

这篇关于从零开始理解AdaBoost算法：前向分布算法（四）【数学推导】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---