前向分布算法(Forward Stagewise Algorithm)

考虑加法模型

$f(x) = \sum_{k=1}^K\beta_ib(x;\gamma_i)$

其中 $b(x;\gamma_i)$ 为基函数，$\gamma_i$ 为基函数的参数，$\beta_i$ 为基函数的系数。

给定训练数据以及损失函数 $L(y,f(x))$，加法模型的代价函数最小化问题为

$\min_{\beta_i,\gamma_i}\sum_{i=1}^mL\left( y^{(i)},\sum_{k=1}^K\beta_ib(x^{(i)} ;\gamma_i) \right)$

可以类比动态规划的求解方法，从前向后，每次只优化一项损失函数，求解出一个基函数的参数，就可以简化算法的复杂度。令 $f_0(x)=0$，可以得出第 $k$ 步迭代式

$(\beta_k,\gamma_k)=\arg\min_{\beta,\gamma}\sum_{i=1}^mL\left( y^{(i)},f_{k-1}(x^{(i)})+\beta b(x^{(i)};\gamma) \right)$

更新加法模型

$f_k(x) = f_{k-1}(x)+\beta_kb(x;\gamma_k)$

因为 $f_{k-1}(x^{(i)})$ 中不存在需要优化的变量，那么每步就只需优化

$\min_{\beta,\gamma}\sum_{i=1}^mL\left(y^{(i)},\beta b(x^{(i)};\gamma)\right)$

通过迭代，减少算法的复杂度，逐次学习 $\beta_k,\gamma_k$ 而不是一次性全部求解。通过证明可以得知 AdaBoost 也属于加法模型。

提升树(Boosting Tree)

提升树模型以前向分布算法为理论基础，将加法模型中的基函数替换为二叉树：

$f_K(x)=\sum_{k=1}^KT(x;\Theta_k)$

其中 $T(x;\Theta_k)$ 表示决策树；$\Theta$ 表示决策树的参数。

首先确定初始提升树 $f_0(x)=0$，第 $k$ 步的模型为

$f_k(x) = f_{k-1}(x)+T(x;\Theta_k)$

针对不同的问题，损失函数也有所不同，比如 AdaBoost 的代价函数就为指数函数，回归问题的的代价函数就为最小二乘。下面说一下回归问题的提升树。

如果需要解决的问题是回归问题，则假发模型中的基函数就是回归二叉树，在算法的第 $m$ 步，已知 $f_{k-1}(x)$ 的前提下，需要求解第 $m$ 棵回归树的参数 $\Theta_k$：

$\begin{align} \hat \Theta_k &= \arg\min_{\Theta_k} \sum_{i=1}^m L\left(y^{(i)},f_{k-1}(x^{(i)})+T(x^{(i)};\Theta_k)\right)\\ &=\arg\min_{\Theta_k}\sum_{i=1}^m\left[ y^{(i)}-\left(f_{k-1}(x^{(i)})+T(x^{(i)};\Theta_k)\right) \right ]^2\\ &=\arg\min_{\Theta_k}\sum_{i=1}^m\left( y^{(i)}-f_{k-1}(x^{(i)})-T(x^{(i)};\Theta_k) \right)^2 \end{align}$

令 $r^{(i)}{k} = y^{(i)}-f{k-1}(x^{(i)})$，那么有

$\hat \Theta_k = \arg\min_{\Theta_k} \sum_{i=1}^m \left( r^{(i)}_{k} -T(x^{(i)};\Theta_k) \right)^2$

这里可以理解为第 $m$ 棵回归树只需要对 $f_{k-1}(x)$ 模型的残差进行拟合即可，这样就会大大减少计算量。所以这种模型也被称为残差树。

梯度提升(Gradient Boosting)

梯度提升算法主要针对那些损失函数不是常见的最小二乘或者指数函数，最优化的过程需要梯度下降法来帮忙。做法就是残差来用负梯度方法来拟合：

$r^{(i)}_m=\left[ \frac{\partial L(y^{(i)},f(x^{(i)}))}{\partial f(x^{(i)})} \right]_{f(x)=f_{k-1}(x)}$

👇

残差树可以说是梯度提升树的特例。就如同在一个二次曲线上你可以看到最优点，然后你用数学模型去模拟他。可能模拟的八九不离十。你越模拟，学习器的精度就会越高。但是如果用梯度来模拟残差，那么就相当于向最小方向迈出一步，也不知道结果如何，有可能加法模型中的若模拟器不是越多越好。这里或许可以解释为何牛顿法（二阶导数）比梯度下降法（一阶导数）迭代的更为精准，快速。

👆

还有挺多没写，到时候再说

https://www.cnblogs.com/zengzhen94/p/8744970.html