前向分布算法 (Forward Stagewise Algorithm) 是求解加法模型优化问题的一种常见的方式。前向分布算法可以看成是在加法模型的基础上,从前往后逐渐建立基学习器来逼近目标函数的过程:
\[\begin{aligned} f_0(x)&=0 \\ f_m(x)&=f_{m-1}(x)+T(x; \Theta_m), ~~ m=1,2,\dots,M \\ f_M(x)&=\sum_{m=1}^M T(x; \Theta_m) \end{aligned}\]考虑如下的加法模型
\[f(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)\]其中 $b\left(x ; \gamma_{m}\right)$ 为基函数,$\gamma_{m}$ 为基函数参数,$\beta_{m}$ 为基函数系数。
在给定了训练数据和损失函数 $L(y, f(x))$ 的条件下,学习加法模型 $f(x)$ 就成为经验风险极小化即如下损失函数极小化的问题。
\[\min _{\beta_{m}, \gamma_{m}} \sum_{i=1}^{N} L\left(y_{i}, \sum_{m=1}^{M} \beta_{m} b\left(x_{i} ; \gamma_{m}\right)\right)\]通常来说这是一个复杂的优化问题,前向分布算法求解的思路是:因为是加法模型,那么从前往后,每一步只学习一个基学习器及其系数,逐步逼近优化目标函数,那么就能简化优化的复杂度了。
那么我们就只要每步优化如下的损失函数:
\[\min _{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, \beta b\left(x_{i} ; \gamma\right)\right)\]前向分布算法流程
- 输入:
- 训练数据集:$T=\{\left(x_{1}, y_{1}\right),\left\langle x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\}$
- 损失函数:$L(y, f(x))$
- 基函数集:$\{b(x ; \gamma)\}$
- 输出:加法模型 $f(x)$
- 初始化 $f_{0}(x)=0$
- 对 $m=1,2, \cdots, M$
a) 极小化损失函数
\[\left(\beta_{m}, \gamma_{m}\right)=\arg \min _{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+\beta b\left(x_{i} ; \gamma\right)\right)\]得到基函数系数 $\beta_{m}$,基函数参数 $\gamma_{m}$。
b) 更新当前的强学习器
\[f_{m}(x)=f_{m-1}(x)+\beta_{m} b\left(x ; \gamma_{m}\right)\]- 求解到加法模型