Boosting
在另一篇博客中(boosting与指数损失)介绍了关于Boosting的一些简单内容。
- boosting的过程是不断地修改数据集，在此之上应用弱学习器，由此产生一个弱学习器序列$b(x;\gamma_m), m = 1, 2, ..., M$。最后通过加权的多数表决来合并每个弱学习器的预测结果。
- Boosting是一种建立在弱学习器集合上的加法模型。
- 通过前向分步拟合的方法来拟合Boosting，相继添加新的弱学习器到Boosting“委员会”里，而不调整已添加的弱学习器的模型参数及其在委员会中的权重系数，这是一种贪心的方法，一次只拟合一个最优的弱学习器。
前向分步拟合方法使用指数损失拟合Boosting分类模型，等价于Adaboost
前向分步拟合算法
- 初始化$f_0(x)=0$
- 对于m=1到M:
(a)计算$$(\beta_m, \gamma_m)=\arg\min_{\beta, \gamma}\sum_{i=1}^NL\bigg(y_i, f_{m-1}(x_i)+\beta b(x_i;\gamma)\bigg)$$ (b)更新$f_m(x)=f_{m-1}(x)+\beta_m b(x; \gamma_m)$
平方损失+前向分步拟合=梯度提升(Gradient boosting)
平方经验损失的梯度
令f为所求的boosting模型
{% raw %}$$f(x) = \sum_{m=1}^M \beta_m b(x; \gamma_m) \tag 1$${% endraw %}
面对回归问题，通常使用平方损失：
$$L(y, f(x))=(y-f(x))^2\tag 2$$
令$y=(y_1,...,y_N)^T, f(x)=(f(x_1),...,f(x_N))^T$为boosting模型的预测值，那么最小化平方经验损失的过程可以等价于
$$
\min_fL(y, f(x))=\min_f(y-f(x))^T(y-f(x))=\min_f\frac{1}{2}(y-f(x))^T(y-f(x))
\tag 3$$
显然这是凸优化，其负梯度方向为
$$\begin{aligned}
- \frac{\partial}{\partial f(x)} \bigg(\frac{1}{2}(y-f(x))^T(y-f(x))\bigg)
&= - \frac{1}{2} \cdot 2 \cdot \Big(\frac{\partial}{\partial f(x)} (y-f(x))^T\Big) \cdot (y-f(x)) \\
&= - \Big(\frac{\partial y^T}{\partial f(x)} - \frac{\partial f^T(x)}{\partial f(x)}\Big) \cdot (y-f(x)) \\
&= -(0-I)\cdot (y-f(x)) \\
&= y-f(x)
\end{aligned} \tag4$$
我们发现，模型残差就是平方经验损失相对于模型预测值的负梯度方向。不过在模型$f$没有求出来之前，我们没法计算梯度。
注意： 这和我们平时所见的梯度不同，一般梯度下降法里的梯度是经验损失相对于模型参数的梯度，而这里的梯度是经验损失相对于模型预测值的梯度。
前向分步拟合最小化平方经验损失
在前向分步拟合算法中，第m次迭代的模型为
{% raw %}$$f_m(x) = \sum_{i=1}^m \beta_i b(x; \gamma_i)=f_{m-1}+\beta_m b(x;\gamma_m)\tag 5$${% endraw %}
每次迭代，最小化平方经验损失的过程为
$$\begin{aligned}
\min_{f_m}L(y, f_m(x))
&= \min_{f_m}(y-f_m(x))^T(y-f_m(x)) \\
&= \min_{f_m}\|y-f_m(x)\|^2\\
&= \min_{\beta, \gamma}\|y-f_{m-1}(x)-\beta_mb(x;\gamma_m)\|^2\\
&= \min_{\beta, \gamma}\|r_{m-1} - \beta_m b(x;\gamma)\|^2
\end{aligned}
\tag{6}$$
令$r_{m}=(r_{m1},...,r_{mN})^T, r_{mi}=y_i - f_m(x_i)$，当然$r_{m-1}$就是是当前模型(第m-1次迭代所产生的模型)的残差。这样，对于平方损失，每一次迭代都是把对当前模型残差拟合的最好的弱分类器及其系数$\beta_mb(x;\gamma_m)$加到新模型$f_m(x)$里。将这个目标函数带入到前向分布拟合算法中来
平方损失的前向分步拟合算法
- 初始化$f_0(x)=0$
- 对于m=1到M:
(a)计算残差
$$r_{m-1}=y - f_{m-1}(x)$$ (b)估计模型参数，拟合残差$$(\beta_m, \gamma_m)=\min_{\beta, \gamma}\|r_{m-1} - \beta b(x;\gamma)\|^2 \tag 7$$ (c)更新$f_m(x)=f_{m-1}(x)+\beta_m b(x; \gamma_m)$
式(7)中$\beta, \gamma$的优化不存在相互依赖，可以分开优化，式(7)等价于
$$\bigg\{ \begin{matrix}
\gamma_m = \arg\min_{\gamma}\|r_{m-1} - b(x;\gamma)\|^2 \\
\beta_m = \arg\min_{\beta}\|r_{m-1} - \beta b(x;\gamma)\|^2
\end{matrix}
\tag{8}$$
平方损失下的梯度提升
由上一小节我们知道$r_{m-1}$就是平方经验损失相对于当前模型预测值的负梯度方向，那么这里的$b(x;\gamma_m)$就是对当前模型预测值的负梯度方向最优的拟合。而一维实数$\beta_m$可以看做是梯度下降时的步长。上述算法等价于
平方损失下的梯度提升
- 初始化$f_0(x)=0$
- 对于m=1到M:
(a)计算残差
$$r_{m-1}=y - f_{m-1}(x)$$ 则梯度为$-r_{m-1}$, 若梯度非常接近0可提前结束迭代
(b)估计模型参数，拟合残差$$\gamma_m = \arg\min_{\gamma}\|r_{m-1} - b(x;\gamma)\|^2 \tag 9$$(c)估计最优步长 $$\beta_m = \arg\min_{\beta}\|r_{m-1} - \beta b(x;\gamma_m)\|^2 \tag{10}$$ (d)更新模型，梯度下降
$$f_m(x)=f_{m-1}(x)+\beta_m b(x; \gamma_m)=f_{m-1}(x)-\beta_m (-b(x; \gamma_m))$$
上述算法是梯度提升算法在平方损失情形下的特例。每次迭代，梯度提升算法拟合经验损失在预测函数（值）上的梯度，然后在拟合的预测函数梯度减小最快的方向boost（我觉得翻译成“推进”更好），是对梯度下降的一种近似。
考虑实际的梯度下降算法
在梯度下降算法中，每次迭代需要求当前搜索位置的梯度，然后沿着负梯度方向搜索，直到找到0梯度位置为止。
与梯度下降算法比较，平方损失下的梯度提升算法，相当于以模型预测值$f(x)$为参数做梯度下降。这里的残差为真实的负梯度，我们以弱学习器去拟合真实的负梯度，再沿着拟合的负梯度方向搜索。实际上并不是在真实的梯度方向下降，而是在拟合的梯度方向下降。