前言
上一次介绍完集成学习算法中的 $AdaBoost$ 以及 $提升树$ 之后，一直在筹划这篇梯度提升树的博客。
今天，就让阿南带你走进面试中最热门的机器学习算法之一，梯度提升树！
梯度提升树
梯度提升树 (Gradient Boosting Decision Tree, GBDT)，
听到这个名字有没有觉得很熟悉？
没错，在上节课介绍 提升方法 的时候（阿南带你理解 AdaBoost）我们就提到了 提升树 (Boosting Decision Tree, DBT)，这两个方法的名字看起来非常的相似，名字都只相差一个字，那它们到底有什么区别呢？
机智的你们应该可以看出来，区别就是 $GBDT$ 跟梯度 Gradient 相关，而之前所提到的 提升回归树 只是与上一个基本分类器的残差有关，与梯度无关。
梯度提升算法，利用了最速下降梯度的近似算法，关键就在于利用损失函数关于当前模型的负梯度值作为回归问题提升树算法中残差的近似值，进而用来拟合一个回归树。
\[-\left[\frac{\partial L(y,f(x_i))}{\partial f(x_i)} \right]_{f(x) = f_{m-1}(x)} \tag{1}\]实际上，$GBDT$ 只是 梯度提升方法学习器 (Gradient Boost Machine, GBM) 的一个特例。
并且我们接下来要介绍的 梯度提升树 的基本分类器只能由 回归树 组成，原因也很简单：分类树无法处理连续值，而梯度一般都是连续值，故只能采用回归树。
当时在学习 梯度提升树 这一块的时候我有许多疑惑。比如说
-
除了回归树以外，还可以选择其它的方法作为基本分类器吗？
-
已经有了提升回归树和提升分类树了，为什么还需要梯度提升树？
-
梯度提升树与 $AdaBoost$ 之间有什么联系与区别？
-
梯度提升树的优缺点是什么？为什么会应用这么广泛？
现在我分别详细地解答上述问题，也是一个温习的过程！
-
可以选择别的方法作为基本分类器！ 只需满足每个基本分类器具有 低方差，高偏差 的特性即可。因为我们的目的就是通过提升方法组合多个基本分类器，训练的过程是通过降低偏差来不断提高最终分类器的精度。
上述思想正是梯度提升方法不容易过拟合的主要原因之一！因为如果选择强学习方法（如SVM）就非常容易导致寥寥几个基本学习器就达到预先设定的误差阈值，这恰与集成学习的思想相悖且往往会导致过拟合。
因此在实际工业应用中，时常采用 回归决策树 作为基本分类器。原因也与决策树自身的优点有关。
-
可解释性强、预测速度快
-
不需要做特征标准化
-
能够很好地处理字段缺失的数据，因为决策树的每个节点只依赖一个 feature，如果某个 feature 不存在，这颗树依然可以拿来做决策，只是少一些路径。像逻辑回归，SVM 就没这个好处。
-
不用关心特征之间是否相互依赖
-
对离群值 (outlier) 拥有很好的鲁棒性，因为每个节点都是 $x < 𝑇$ 的形式，至于具体大多少或小多少对结果来说没有区别，outlier 不会有什么大的影响。然而逻辑回归和 SVM 并没有这样的天然特性。
单独使用决策树进行拟合往往会造成过拟合的现象。幸运的是，我们可以通过抑制树的深度及叶子节点个数等多种方法降低单棵树的复杂程度，使其满足提升算法对于基本分类器的要求 ——“低方差，高偏差”，随后结合提升算法实现满意的 分类 or 回归 效果。
-
-
对于第二个问题，当损失函数为均方误差作为损失函数时残差比较好求解，但如果损失函数选用的是绝对差值函数，虽然构造弱分类器也可以表示成在残差上做绝对差值拟合，但这个子问题本身也不容易求解，因为我们是要构造多个弱分类器的，所以我们当然希望构造弱分类器这个子问题比较 好解。因此 $AdaBoost$ 的基于残差的思路无法推广到其他一些实用的损失函数上。
相比较而言，$GBDT$ 只需要计算当前模型的负梯度，并将这个负梯度用作为上一个基本分类器残差的近似值，随后用这个近似值训练下一棵回归树。只要损失函数是连续可微的，梯度就可以计算。
-
联系： 都是基于加法模型，属于提升方法的一种。每个基本分类器之间都存在前后依赖关系。
区别：
-
与AdaBoost算法不同，梯度提升方法在迭代的每一步构建一个能够沿着梯度最陡的方向降低损失（steepest-descent）的学习器来弥补已有模型的不足。
-
经典的AdaBoost算法只能处理采用指数损失函数的二分类学习任务，而梯度提升方法通过设置不同的可微损失函数可以处理各类学习任务（多分类、回归、Ranking等），应用范围大大扩展。
-
-
优点：
- 预测精度高
- 可以处理各种类型的数据，包括连续值和离散值
- 适合低维数据
- 能够处理非线性数据
- 可以在相对较少的调参时间下取得相对较好的预测准确率
- 若使用相对健壮的损失函数，那么对异常值的鲁棒性将会非常强。如 **Huber 损失函数。**
缺点：
- 基本分类器之间存在依赖关系，难以并行训练。
- 数据维度较高时，算法的时间复杂度会大大提升。
好的，接下来我们就正式叙述 梯度提升树 的算法流程吧！
GBDT 回归
输入： 训练数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)},\ x_i\in \chi \subseteq R^n, \ y_i\in \gamma \subseteq R$
输出： 回归树 $\hat f(x)$
-
通过寻找一个能够使得损失函数 $L(y_i,c)$ 最小的常数 $c$ 作为第一个基本分类器 $f_0(x)$
\[f_0(x) = \arg \min_c \sum_{i=1}^N L(y_i,c) \tag{2}\] -
依次计算之后的基本分类器，对 $m=1,2,…,M$
(a) 对所有样本 $i=1,2,…,N$，计算其在当前实例 $x_i$ 的负梯度，并将其作为残差 $r_{mi}$ 的估计值：
\[r_{mi} = -\left[\frac{\partial L(y,f(x_i))}{\partial f(x_i)} \right]_{f(x) = f_{m-1}(x)} \tag{3}\](b) 对残差 $r_{mi}$ 拟合一个回归树，得到第 $m$ 棵树的叶节点区域 $R_{mj}, j=1,2,…,J$
(c) 对 $j=1,2,…,J$ 搜索其对应叶节点区域能使得损失函数最小的输出值 $c_{mj}$
\[c_{mj} = \arg \min_c \sum_{x_i\in R_{mj}} L(y_i, f_{m-1}(x_i) +c) \tag{4}\](d) 更新模型 $f_m = f_{m-1}(x) + \sum_{j=1}^J c_{mj} I(x\in R_{mj})$
-
得到最终的回归树：
\[F(x) = f_M (x) = \sum_{m=1}^M \sum_{j=1}^J c_{mj} I(x\in R_{mj}) \tag{5}\]
为了防止过拟合的出现，我们可以引入 收缩因子 (Shrinkage)。
核心思想就是，新的回归树只拟合上一颗树的部分 “近似残差”（负梯度）
\[r_{mi}^{*} = \gamma \times r_{mi} \tag{6}\]这里的 $\gamma$ 就是 收缩因子 (Shrinkage)，值域为 $(0,1]$。取 $1$ 时表示不对其进行缩放。然后用下一个回归树去拟合 $r_{mi}^{*}$
这样做的好处就是防止下一个基本分类器一次性吃成一个胖子。长辈们不也常说：“鸡蛋不能全放在一个篮子里。”
所以我们不能寄希望于只相信寥寥几个模型，应当转而相信 “群众的眼睛时雪亮的！”
GBDT 分类
GBDT 用于解决回归问题时比较直观易懂，因为其基本分类器的组成天然的就是回归树，然鹅这是不是就意味着 GBDT 不能用来解决回归问题了呢？
放心！万能且好用的 GBDT 当然可以用来解决分类问题，甚至是多分类问题对于 GBDT 也时手到擒来~
接下来让阿南详细地讲一讲 GBDT 用于分类的步骤，大家搬起小板凳做好了！首先是二分类问题：
二分类问题
首先，在上述回归问题中，最终回归树 $F(x)$ 是直接地预测实例 $x_i$ 的输出值 $\hat y_i$。
但是在分类问题中，每个实例的真实值是 $0$ 或 $1$ 的标签，那么我们所训练最终回归树 $F(x)$ 的输出应该是什么呢？
大家想想之前在逻辑回归中提到过的对数几率：$\log \frac{p}{1-p}$，其描述了类别 $y=1$ 发生的可能性。
因此我们可以借鉴逻辑回归的思想，期望得到一颗最终回归树能够准确的输出对数几率 $\log \frac{p}{1-p}$，随后我们只需要将得到的对数几率带入至逻辑函数中即可得到实例 $x_i$ 属于类别 $y=1$ 的概率了。
\[P(y_i=1|x_i) = \frac{1}{1+e^{-F(x_i)}} \tag{7}\]确定我们的训练目标是对数几率之后，我们接下来就要选择一个适当的损失函数用来衡量训练效果。在此处我们用分类问题中常用的 逻辑损失函数 (Log Loss)：
\[\begin{aligned} L(y,f_m(x)) & = -\{y_i \log p_i + (1-y_i)\log (1-p_i)\} \\[2ex] & = -\left\{y_i \log \frac{1}{1+e^{-f_m(x_i)}} + (1-y_i)\log \left[\frac{e^{-f_m(x_i)}}{1+e^{-f_m(x_i)}}\right]\right\} \\[2ex] & = -\left\{-y_i \log {[1+e^{-f_m(x_i)}]} + (1-y_i) \left\{ \log e^{-f_m(x_i)} - \log[{1+e^{-f_m(x_i)}]} \right\} \right\} \\[2ex] & = -\left\{-y_i \log {[1+e^{-f_m(x_i)}]} + \log e^{-f_m(x_i)} - \log[{1+e^{-f_m(x_i)}]} -y_i \log e^{-f_m(x_i)} + y_i \log[{1+e^{-f_m(x_i)}]} \right\} \\[2ex] & = -\left\{ -y_i \log e^{-f_m(x_i)} + \log e^{-f_m(x_i)} - \log[{1+e^{-f_m(x_i)}]}\right\} \\[2ex] & = -\left\{y_i f_m(x_i) + \log \left[\frac{e^{-f_m(x_i)}}{1+e^{-f_m(x_i)}}\right] \right \} \\[2ex] & = -\left\{y_i f_m(x_i) + \log \left[{1+e^{f_m(x_i)}} \right] \right \} \end{aligned} \tag{8}\]其中 $p_i$ 是第 $i$ 个实例 $x_i$ 属于类别 $y=1$ 的概率，即 $(7)$ 式。
随后求出损失函数关于模型的负梯度 $-\left[\frac{\partial L(y,f_m(x))}{\partial f_m(x)}\right]$
\[r_{mi}=-\left[\frac{\partial L(y_i,f_m(x_i))}{\partial f_m(x_i)}\right] = y_i - \frac{1}{1+e^{-f_m(x_i)}} \tag{9}\]计算得到负梯度值之后，在下一个回归树 $f_{m+1}(x)$ 中拟合上述负梯度值 $r_{mi}$。此处我们可以对负梯度乘上收缩因子 (Shrinkage) $\eta \in(0,1]$,即将残差分散开让尽可能多的基本分类器进行学习，防止一次性学习步伐过大造成过拟合。
拟合的方式就是遍历所有特征 $k$ 以及可能的分裂点 $s$，找出一个分裂点 $s_i$ 能够使得下述均方误差最小，记录下对应的特征 $A_k$ 和 分裂值 $s_i$。
\[\min_{k,s} \left[\min_{c_1} \sum_{x_i\in R_1(k,s)}(y_1-c_1)^2 + \min_{c_2} \sum_{x_i\in R_2(k,s)}(y_i-c_2)^2 \right] \tag{10}\]按照预先设定的最大深度和最大子节点数量，通过上式我们能够得到 $J$ 个不相交的区域 $R_1, R_2, …,R_J$，接下来我们计算每个区域上的输出值 $\gamma_{jm}$：
\[\gamma_{jm} = \frac{\sum_{x_i\in R_{jm}}\hat y_i}{\sum_{x_i\in R_{jm}}\left[(y_i - \hat y_i) * (1-(y_i-\hat y_i))\right]} \tag{11}\]重复上述步骤，当误差低于设定阈值时停止计算，得到最终回归树 $F(x)$
\[F(x) = f_{m-1} + \sum_{j=1}^J \gamma_{jm}I(x\in R_{jm}) \tag{12}\]得到最终的强回归树之后，当出现一个新实例 $x^{new}$ 时我们只需把它输入至 $F(x)$，然后计算其属于类别 $1$ 的概率：
\[P(y_i=1|x_i) = \frac{1}{1+e^{-F(x^{new})}} \tag{13}\]至于阈值则可以自行设定，比如说设定为大于 $0.5$ 则为 $1$ 类，否则则为 $0$ 类。
总结一下 GBDT 用于分类的步骤：
-
用对数几率 $\log \frac{p}{1-p}$ 初始化第一个基本分类器 $f_0(x)$，其中 $p$ 是训练样本中类别为 $1$ 的概率。
\[f_0(x) = h_0(x) = \log \frac{p}{1-p}\] -
对于随后的回归树 $f_m(x),\ m=1,2,…,M$ 有
- 首先根据式 $(9)$ 计算负梯度值 $r_{mi}$。(如果此处设置了 Shrinkage 则对负梯度进行放缩，$r^{*}{mi} = \eta \cdot r{mi}$)
- 使用负梯度值 $r_{mi}$ 或 $r^{*}{mi}$ 去训练下一棵回归树 $f{m+1}(x)$，每个叶子节点的输出值 $\gamma_{jm}$ 由式 $(11)$ 决定：
- 得到最终的学习器 $F(x)$
好啦!
今天的 GBDT 小课堂就到这里了！
希望找工作能够万事顺意！ 😊
