从零开始理解AdaBoost算法：加法模型与优化方法（三）【理论解析】

从零开始理解AdaBoost算法：加法模型与优化方法（三）【理论解析】

在前面我们已经明白了如何进行AdaBoost算法的基本操作，但我们还不清楚这些公式是如何得来的，以及为什么要这样做。接下来，我们将详细讲解这些公式的推导过程及其背后的原因。

AdaBoost算法属于Boosting类型的算法，其基本思路是通过组合多个弱分类器来构建一个强分类器。由于它是一个加法模型，我们可以通过训练来优化模型中的参数。

预测函数——加法模型的定义

在机器学习中，加法模型的预测函数如下所示：
$$f(x)=\sum _{m=1}^M{\beta }_{m}b(x;{\gamma }_m)$$
这里：

• ${\beta }_m$ 是基函数的系数
• $b(x;{\gamma }_m)$ 是基分类器
• ${\gamma }_m$ 是基分类器的参数

损失函数

损失函数的选择取决于具体问题：

• 回归问题：均方误差（MSE）
• 分类问题：指数函数或交叉熵损失

优化方法

常用的优化方法是梯度下降，但是对于加法模型，梯度下降并不总是适用。

梯度下降的缺点

目标函数是要极小化损失函数：
$$\underset{{\beta }_m,{\gamma }_m}{\min }\sum _{i=1}^{N}L(y_i,\sum _{m=1}^M{\beta }_{m}b(x_i;{\gamma }_m))$$
假设 $M=2$，且损失函数为均方误差（MSE），则目标函数为：
$$\sum _{i=1}^N(y_i-({\beta }_{1}b(x_i;{\gamma }_1)+{\beta }_{2}b(x_i;{\gamma }_2)){)}^2$$

如果使用梯度下降法进行优化，每次迭代需要同时更新 ${\beta }_1$、${\beta }_2$、${\gamma }_1$、${\gamma }_2$。当 $M$ 较大时，需要同时更新 $2M$ 个参数，复杂度较高。而且，这里假设了 $\gamma$ 只有一个参数，但在实际中，如逻辑回归，$\gamma$ 可能是一个向量。

前向分布算法

由于当前的基函数会受到前面所有基函数的影响，前后关系非常紧密，因此我们可以使用具有递推关系的前向分布算法。

输入：

• 训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$
• 损失函数 $L(y,f(x))$
• 基函数集 $b(x;\gamma )$

输出：加法模型 $f(x)$

过程：

1. 初始化 $f_0(x)=0$

2. 对 $m=1,2,\dots ,M$：

   • （a）极小化损失函数：
     $$({\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 ))$$
     得到参数 ${\beta }_m$ 和 ${\gamma }_m$
   • （b）更新模型：
     $$f_m(x)=f_{m-1}(x)+{\beta }_{m}b(x;{\gamma }_m)$$

3. 得到最终的加法模型：
   $$f(x)=f_M(x)=\sum _{m=1}^M{\beta }_{m}b(x;{\gamma }_m)$$

优势

1. 递推性质：当前参数只受到前面所有参数的影响，前后关系紧密。前向分布算法每次只计算一个新的基函数参数，使得每步计算更为简洁。

2. 计算效率：由于每次迭代只更新一个基函数的参数，前向分布算法显著降低了计算复杂度，特别是当模型包含大量基函数时。

3. 串行优化：前一个参数 $f_{m-1}(x)$ 在当前计算中是一个定值，不再变化，因此每次只需集中精力优化新的参数 ${\beta }_m$ 和 ${\gamma }_m$。这体现了逐步优化的思想，使得参数优化更加明确和直观。

前向分布算法 VS 梯度下降方法

在优化加法模型时，我们可以采用前向分布算法（Forward Stagewise Additive Modeling）来替代传统的梯度下降方法。这两种方法的主要区别在于参数更新的方式和计算复杂度。

1. 梯度下降方法：

   • 目标：同时极小化所有参数。
   • 计算复杂度：高，每次迭代需要更新所有参数。
   • 参数更新：每次迭代更新 $2M$ 个参数（假设 $\gamma$ 是标量）。
   • 适用场景：适用于参数数量较少的情况。

2. 前向分布算法：

   • 目标：逐步极小化一个基函数的参数。
   • 计算复杂度：低，每次迭代只更新一个基函数的参数。
   • 参数更新：每次迭代更新 2 个参数（${\beta }_m$ 和 ${\gamma }_m$）。
   • 适用场景：适用于参数数量较多，或每个基函数参数复杂的情况。

参考链接：5.加法模型_哔哩哔哩_bilibili