AdaBoost与前向分步算法

1. 加性模型的定义

在AdaBoost算法中，我们可以将其视为一种加性模型。加性模型是指由多个基模型的线性组合构成的模型。图中的公式 (10-9) 描述了加性模型的形式：
$$f(x)=\sum _{t=1}^T{\alpha }_{t}b(x;{\gamma }_t)$$

其中：

• $b(x;{\gamma }_t)$ 表示第 $t$ 个基模型，参数 ${\gamma }_t$ 是模型的参数。
• ${\alpha }_t$ 是基模型的系数，表示每个基模型的权重。
• $T$ 是基模型的数量。

加性模型的目标是最小化损失函数 $L(y,f(x))$，通过逐步优化每个基模型的参数和权重，逐渐逼近目标值。

2. 加性模型的目标函数

对于给定的训练集 $D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$，其中 $x_i\in {\mathbb{R}}^n$， y i ∈ { − 1 , + 1 } y_i \in \{-1, +1\} yi​∈{−1,+1}，我们可以定义加性模型的目标函数为：
$$\underset{{\alpha }_t,{\gamma }_t}{\min }\sum _{i=1}^{N}L\left(y_i,\sum _{t=1}^T{\alpha }_{t}b(x_i;{\gamma }_t)\right)$$

即在所有基模型的权重 ${\alpha }_t$ 和参数 ${\gamma }_t$ 上最小化损失函数。

由于这个优化问题非常复杂，难以一次性求解所有参数，所以可以采用前向分步算法来进行逐步优化。

3. 前向分步算法的思想

前向分步算法的核心思想是：逐步优化。每一步仅优化一个基模型的参数和权重，将其加入到模型中，逐渐逼近目标值。

每一步的优化目标可以用公式 (10-11) 表示为：
$$\underset{{\alpha }_t,{\gamma }_t}{\min }\sum _{i=1}^{N}L(y_i,f_{t-1}(x_i)+{\alpha }_{t}b(x_i;{\gamma }_t))$$

其中：

• $f_{t-1}(x)$ 表示前 $t-1$ 步构建的模型。
• ${\alpha }_t$ 和 ${\gamma }_t$ 是第 $t$ 个基模型的参数，需要通过最小化损失函数来确定。

4. 前向分步算法在AdaBoost中的应用

在AdaBoost中，前向分步算法的思想体现在逐步增加弱分类器，并为每个弱分类器分配权重，以最小化整个模型的损失函数。

具体步骤如下：

(1) 初始化模型

首先，将模型初始化为常数值 $f_0(x)=0$，即模型初始时没有任何分类能力。

(2) 迭代构建模型

对于每一轮 $t=1,2,\dots ,T$：

• 选择基模型：选择一个基模型 $b(x;{\gamma }_t)$ 和对应的参数 ${\gamma }_t$ 以及权重 ${\alpha }_t$，使得当前损失函数最小化。这一步可以通过公式 (10-12) 来表示：
  $$({\alpha }_t,{\gamma }_t)=\arg \underset{\alpha ,\gamma }{\min }\sum _{i=1}^{N}L(y_i,f_{t-1}(x_i)+\alpha b(x_i;\gamma ))$$
• 更新模型：将新的基模型加入到当前模型中，更新后的模型为：
  $$f_t(x)=f_{t-1}(x)+{\alpha }_{t}b(x;{\gamma }_t)$$

(3) 最终加性模型

经过 $T$ 轮迭代后，最终的加性模型表示为：
$$f(x)=\sum _{t=1}^T{\alpha }_{t}b(x;{\gamma }_t)$$

5. 将前向分步算法应用于AdaBoost

对于AdaBoost而言，基模型是二分类器 $G_t(x)$，加性模型构建过程如下：

• 假设在第 $t-1$ 步，我们已经获得了一个模型 $f_{t-1}(x)$。
• 第 $t$ 步添加新的弱分类器 $G_t(x)$ 时，我们会选择一个权重系数 ${\alpha }_t$，使得损失函数最小化。

即公式 (10-16) 表示了这一过程：
$$({\alpha }_t,G_t(x))=\arg \underset{\alpha ,G}{\min }\sum _{i=1}^N\exp (-y_i(f_{t-1}(x_i)+\alpha G(x_i)))$$

通过这个优化，我们可以得到每一轮中需要添加的弱分类器 $G_t(x)$ 及其权重 ${\alpha }_t$，从而逐步逼近最优解。

6. 总结

综上所述，AdaBoost可以看作是前向分步算法的具体应用。在每一轮中，AdaBoost通过选择一个新的弱分类器及其权重，逐步逼近整体目标函数的最小化。

本文部分公式详细解析：
公式 (10-16)