Gradient Boosting

也来讲讲 Gradient Boosting，传说中天池移动推荐算法比赛中应用最多的算法。

基本思想：把分类问题看作回归问题，弱分类器看作一个决策函数 F(x)；每次迭代过程，对上一次分类的残差进行分类训练，即训练 $h(x) = y - F_m(x)$ ，作为前一次分类结果的补偿。对于平方损失函数 $\frac{1}{2} (\hat{y} - y)^2$ 而言，上述 $h(x)$ 则是其导数，因此，该方法作为一个梯度提升方法得名，可以根据需要推广到不同的损失函数。

算法：

1. 初始化基础模型 $F_0(x) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L(y_i, \gamma)$
2. 迭代 $m \in (1, M)$
   1. 计算伪梯度 $r_{im} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]{F(x)=F{m-1}(x)} \quad \mbox{for } i=1,\ldots,n$
   2. 以伪梯度为类标，训练基础模型 $h_m(x)$
   3. 计算模型权重 $\gamma_m = \underset{\gamma}{\operatorname{arg,min}} \sum_{i=1}^n L\left(y_i, F_{m-1}(x_i) + \gamma h_m(x_i)\right)$
   4. 更新模型： $F_m(x) = F_{m-1}(x) + \gamma_m h_m(x)$
3. 得到最终模型 $F_m(x)$

其中 2.4 中计算模型权重采用的是一维模型，更恰当地，应该采用区域模型（决策树对特征向量的预测实际上是就是对特征空间进行划分）：
$$F_m(x) = F_{m-1}(x) + \sum_{j=1}^J \gamma_{jm} I(x \in R_{jm}), \quad
\gamma_{jm} = \underset{\gamma}{\operatorname{arg,min}} \sum_{x_i \in R_{jm}} L(y_i, F_{m-1}(x_i) + \gamma h_m(x_i))$$
但这样做无疑增加了计算量。

为了简化操作，在 Spark MLlib 中的 GradientBoostTree 中，模型参数 $\gamma_m$ 被规定为 1 ，不要与学习率（learning rate）混淆。

---

参数调优：

1. 学习率（Learning Rate） $F_m(x) = F_{m-1}(x) + \nu \cdot \gamma_m h_m(x), \quad 0 < \nu \leq 1$ ，实践中越小的学习率分类预测效果越好
2. 随机梯度提升（Stochastic Gradient Boosting），受 Bagging 思想启发，每次训练时不直接用全局数据，而是对数据进行抽样，每次只选择一部分数据进行训练
3. 限制叶子节点的实例个数，减小预测的方差
4. 模型复杂度的惩罚，树越复杂越可能过拟合

具体可以参考 <a href="https://en.wikipedia.org/wiki/Gradient_boosting">https://en.wikipedia.org/wiki/Gradient_boosting</a>