AdaBoost与前向分步算法

1. 加性模型的定义

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

其中：

• b ( x ; γ t ) b(x; \gamma_t) b(x;γt​) 表示第 t t t 个基模型，参数 γ t \gamma_t γt​ 是模型的参数。
• α t \alpha_t αt​ 是基模型的系数，表示每个基模型的权重。
• T T T 是基模型的数量。

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

2. 加性模型的目标函数

对于给定的训练集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } D = \{(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)\} D={(x1​,y1​),(x2​,y2​),…,(xN​,yN​)}，其中 x i ∈ R n x_i \in \mathbb{R}^n xi​∈Rn， y i ∈ { − 1 , + 1 } y_i \in \{-1, +1\} yi​∈{−1,+1}，我们可以定义加性模型的目标函数为：
min ⁡ α t , γ t ∑ i = 1 N L ( y i , ∑ t = 1 T α t b ( x i ; γ t ) ) \min_{\alpha_t, \gamma_t} \sum_{i=1}^N L\left(y_i, \sum_{t=1}^T \alpha_t b(x_i; \gamma_t)\right) αt​,γt​min​i=1∑N​L(yi​,t=1∑T​αt​b(xi​;γt​))

即在所有基模型的权重 α t \alpha_t αt​ 和参数 γ t \gamma_t γt​ 上最小化损失函数。

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

3. 前向分步算法的思想

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

每一步的优化目标可以用公式 (10-11) 表示为：
min ⁡ α t , γ t ∑ i = 1 N L ( y i , f t − 1 ( x i ) + α t b ( x i ; γ t ) ) \min_{\alpha_t, \gamma_t} \sum_{i=1}^N L(y_i, f_{t-1}(x_i) + \alpha_t b(x_i; \gamma_t)) αt​,γt​min​i=1∑N​L(yi​,ft−1​(xi​)+αt​b(xi​;γt​))

其中：

• f t − 1 ( x ) f_{t-1}(x) ft−1​(x) 表示前 t − 1 t-1 t−1 步构建的模型。
• α t \alpha_t αt​ 和 γ t \gamma_t γt​ 是第 t t t 个基模型的参数，需要通过最小化损失函数来确定。

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

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

具体步骤如下：

(1) 初始化模型

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

(2) 迭代构建模型

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

• 选择基模型：选择一个基模型 b ( x ; γ t ) b(x; \gamma_t) b(x;γt​) 和对应的参数 γ t \gamma_t γt​ 以及权重 α t \alpha_t αt​，使得当前损失函数最小化。这一步可以通过公式 (10-12) 来表示：
  ( α t , γ t ) = arg ⁡ min ⁡ α , γ ∑ i = 1 N L ( y i , f t − 1 ( x i ) + α b ( x i ; γ ) ) (\alpha_t, \gamma_t) = \arg \min_{\alpha, \gamma} \sum_{i=1}^N L(y_i, f_{t-1}(x_i) + \alpha b(x_i; \gamma)) (αt​,γt​)=argα,γmin​i=1∑N​L(yi​,ft−1​(xi​)+αb(xi​;γ))
• 更新模型：将新的基模型加入到当前模型中，更新后的模型为：
  f t ( x ) = f t − 1 ( x ) + α t b ( x ; γ t ) f_t(x) = f_{t-1}(x) + \alpha_t b(x; \gamma_t) ft​(x)=ft−1​(x)+αt​b(x;γt​)

(3) 最终加性模型

经过 T T T 轮迭代后，最终的加性模型表示为：
f ( x ) = ∑ t = 1 T α t b ( x ; γ t ) f(x) = \sum_{t=1}^T \alpha_t b(x; \gamma_t) f(x)=t=1∑T​αt​b(x;γt​)

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

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

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

即公式 (10-16) 表示了这一过程：
( α t , G t ( x ) ) = arg ⁡ min ⁡ α , G ∑ i = 1 N exp ⁡ ( − y i ( f t − 1 ( x i ) + α G ( x i ) ) ) (\alpha_t, G_t(x)) = \arg \min_{\alpha, G} \sum_{i=1}^N \exp(-y_i (f_{t-1}(x_i) + \alpha G(x_i))) (αt​,Gt​(x))=argα,Gmin​i=1∑N​exp(−yi​(ft−1​(xi​)+αG(xi​)))

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

6. 总结

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