GBDT算法介绍

APSchmidt · 发表于 2021-12-29 22:17

文章主要是阅读论文《GREEDY FUNCTION APPROXIMATION: A GRADIENT BOOSTING MACHINE》的一些记录。
函数估计

函数估计是从函数空间的角度对数值进行优化，而不是参数空间。
假设一个系统是由随机的输入变量 $x= \left\{ x_{1},...x_{n} \right\}$ 和随机输出变量 $y$ 组成，已知的训练样本为，目标获得一个真实目标函数  的函数估计 $\hat{F}(x)$ ，对 $x -> y$ 进行映射。最小化在一些特殊损失函数上面的期望值。
（1） $F^{*} = arg\min_{P} E_{y,x}L(y,F(x)) = arg\min_{P} E_{x}\left[ E_{y}(L(y,F(x)))|x \right].$

通常损失函数有均方误差 $\left( y-F \right)^{2}$ 、绝对值误差 $\left| y-F \right|$ 、分类问题时的负二项对数似然 $log(1+e^{-2yF})，y\in\left\{ -1,1 \right\}$ .
一种常用的处理方式是将限制为参数化函数的成员  , $P = \left\{ P1,P2,P3... \right\}$ 是一组有限的参数，它们共同决定了某个特殊的参数化函数。但是这篇文章总主要讲的是另一种  的表示形式，称为 “additive”expansions 表示形式：
（2） $F(x;\left\{ \beta_{m},h(x;a_{m}) \right\}=\sum_{m=1}^{M}{\beta_{m}h(x;a_{m})}$
公式（2）中的函数  通常是一个参数化函数，它的参数为 $a = \left\{ a_{1}, a_{2} ...\right\}$ 。每一项通过不同的参数  来生成不同基函数，公式（2）展示的这种扩展方法是许多函数逼近方法的核心，如神经网络、径向基函数、MARS、和SVM。在这篇文章中每个  是一颗小的回归树，如CART树，而每一棵树的参数  是是每一个分裂节点的分裂变量，分裂的位置，以及叶子结点的数量。
数值优化

但选择一个参数优化模型  的时候，函数优化问题就变成了参数优化问题，
（3） $P^{*} = arg\min_{P}\Phi(P)$
其中 $\Phi(P)= E_{x,y}L(y,F(x;P)))$ , $F^{*}(x) = F(x;P^{*})$
对于大部分  和损失函数 $L$ 来说，数值优化方法主要用来解决公式(3)的，这通常涉及用以下表达式解决参数优化
（4） $P^{*} = \sum_{m=1}^{M}{p_{m}}$
这里 $p_{0}$ 是默认值，是连续的增量（称为“steps”或“boosts”），每一个值都是在上一步的基础上按序列生成，每一步 $p_{m}$ 的计算逻辑由优化方法定义，如梯度下降方法。
梯度下降

梯度下降是最常用的数值优化方法之一，它把公式(4)中定义的每一次的增量 $\left\{ p_{m} \right\}_{1}^{M}$ 用如下表达式生成。首先生成梯度

$g_{m} = \left\{ g_{jm} \right\} = \left\{ \left[ \frac{\partial\Phi(P)}{\partial P_{j}} \right]_{P=P_{M-1}} \right\}$ ,       其中 $P_{m-1} = \sum_{0}^{m-1}{p_{i}}$
第m次迭代的 $p_{m} = -\rho_{m}g_{m}$ ，其中
(5)     $\rho_{m} = arg\min_{\rho}\Phi(P_{m-1}-\rho{g_{m}})$
负梯度 $-g_{m}$ 代表了梯度下降的方向，公式(5)表示延梯度下降方向上的线性搜索。
函数空间上的数值优化

使用非参数化方法将数值优化应用到函数空间中，这种方法认为在每个  评估的  是一个“参数”，并寻求最小化，并且最小化如下公式：

$\Phi(F) = E_{y,x}L(y,F(x)) = E_{x}[E_{y}(L(y,F(x)))|x]$
或者：

$\phi(F(x)) = E_{y}[L(y,F(x))|x]$
由于这样的参数是无限的，但是数据集是有限的，因此在函数空间解决数值优化问题的方案如下，

$F^{*}(x) = \sum_{m=0}^{M}{f_{m}(x)}$
这里 $f_{0}(x)$ 是初始化， $\left\{ f_{m}(x) \right\}_{1}^{M}$ 是增量函数( “steps” or “boosts” )。
对应梯度下降：
(6)        $f_{m}(x) = -\rho_{m}g_{m}(x)$
其中：

$g_{m} = \left[ \frac{\partial\phi(F(x))}{\partial F(x)} \right]_{F(x)=F_{m-1}(x)} = \left[ \frac{\partial E_{y}\left[ L(y,F(x))|x \right]}{\partial F(x)} \right]_{F(x)=F_{m-1}(x)}$

$F_{m-1}(x) = \sum_{i=1}^{m-1}{f_{i}(x)}$
交换积分和微分
(7)   $g_{m}(x) = E_{y}\left[ \frac{\partial L(y,F(x))}{\partial F(x)}|x\right]_{F(x) = F_{m-1}(x)}$
公式(6)中的  通过下面公式得到
(8) $\rho_{m} = arg \min_{\rho}E_{y,x}L(y, F_{m-1}(x) - \rho g_{m}(x))$
有限的数据集

在有限的数据集  上面无法准确预估每个 $x_{i}$ 附近的 $E_{y}[.|x]$ ，即使能够预估，我们需要的也是在  附近的  而不是训练集上面的。可以通过借用附近点来平滑实现。一种实现方法是像1.1表述的参数优化方法那样，参考等式(2)，然后在数据集上面最小化期望损失

$\left\{ \beta_{m},\alpha_{m} \right\}_{1}^{M} = arg\min_{\left\{ \beta_{m}^{'},\alpha_{m}^{'} \right\}}\sum_{i=1}^{N}{L(y_{i},\sum_{m=1}^{M}{\beta_{m}^{'}h(x_{i},a_{m}^{'})})}$
直接优化上面公式中的参数是不可取的，因此采用贪婪的方式优化
(9)   $(\beta_{m},\alpha_{m}) = arg\min_{\beta,\alpha}\sum_{i=1}^{N}{L(y_{i},F_{m-1}(x_{i})+\beta h(x_{i};\alpha)})$
这时
(10)   $F_{m}(x) = F_{m-1}(x) + \beta_{m}h(x;\alpha)$
假设一个特定的损失函数 $L(y,F(x))$ 和特定的基学习器  ,公式(9)也是比较难优化的，给定任意一个估计  ,（9）（10）中的 $\beta_{m}h(x;a_{m})$ 项的计算可以被看成基于数据集去预估目标函数  最佳贪婪方案，每一步的方向是由参数限制的  内的成员函数  ,整个流程可以看成公式(6)在参数约束下的梯度下降。
公式(7)在特定数据集上面的非约束负梯度为

$-g_{m}(x_{i}) = -\left[ \frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})} \right]_{F(x) = F_{m-1}(x)}$
因此，通过参数化方法训练一个基分类器  ,使其在训练集上面高度拟合负梯度 $-g_{m}(x)$
（11） $a_{m} = arg\min_{\alpha,\beta}\sum_{i=1}^{N}[{-g_{m}(x_i)}-\beta h(x_i;a)]^2$
梯度方向上的步长
(12) $\rho_{m} = arg\min_\beta \sum_{i=1}^{N}{L(y_{i},F_{m-1(x_{i})}+\rho h(x_{i};a_{m}))}$
模型更新方法如下

$F_{m}(x) = F_{m-1}(x) + \rho_{m}h(x;a_{m})$
从根本上来说，上述过程将参数化解题方案应用到非参数梯度下降优化方案中去拟合“伪响应” $\left\{ \tilde{y}_{i} = - g_{m}(x_{i})\right\}_{1}^{N}$ (7),而不是直接在公式(9)上面进行拟合优化，这样做的好处是，(9)的优化问题是比较难解的，但是改成公式(11)中的均方误差就比较容易计算，然后再通过(12)解出 $\rho$ ，仅仅只需要解决单个参数的优化问题。因此，对于任何能用最小二乘算法来求解 (11)的  函数来说，可以使用任意复杂的损失函数 $L(y,F)$ 结合 stage-wise additive modeling 。
以上算法的通用伪代码如下，算法1：

GBDT框架应用

这里讲述了将GBDT算法框架应用到几个主流的损失函数上，主要包括 least-squares (LS), least absolute deviation (LAD), Huber (M), 和 logistic binomial log-likelihood (L).
1. Least-squares regression

最小二乘法损失函数的形式为 $L(y,F) = (y-F)^{2}/2$ ,因此，负梯度为

$-g_{m}(x_{i}) = -\left[ \frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})} \right]_{F(x) = F_{m-1}(x)} = -\left[ \frac{\partial (y_{i}-F(x_{i}))^{2})}{\partial F(x_{i})} \right]_{F(x) = F_{m-1}(x)} = y_{i} - F_{m-1}(x_{i})$
因此，替换通用算法伪代码第三行 $\tilde{y} = y-F_{m-1}(x_{i})$ ,同时合并第4，5行让 $\rho_{m} = \beta_{m}$ ,得到算法2

因此，在均方误差损失函数下，GBDT算法拟合的是上一步的残差。
2. Least absolute deviation (LAD) regression.

绝对值损失函数的形式为： $L(y,F) = |y-F|$ ,其梯度计算：
(13)   $\tilde{y}_{i} = -g_{m}(x_{i}) = -\left[ \frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})} \right]_{F(x) = F_{m-1}(x)} = sign(y_{i} - F_{m-1}(x_{i}))$
这里  拟合上一步残差的sign值(算法1第四行)，第5行的更新如下：
(14)   $\rho_{m} = arg\min_\rho\sum_{i=1}^{N}{|y_{i} - F_{m-1}(x_{i})-\rho h(x_{i};a_{m})|}$

$= arg\min_\rho\sum_{i=1}^{N}|{h(x_{i};a_{m})|.|\frac{y_{i} - F_{m-1}(x_{i})}{h(x_{i};a_{m})} -\rho|}$

$= median_{W}\left\{ \frac{y_{i} - F_{m-1}(x_{i})}{h(x_{i};a_{m})} \right\}_{1}^{N}, w_{i} = |h(x_{i};a_{m})|$
其中 $median_{W}\left\{ . \right\}$ 表示在权重为 $w_{i}$ 下面的加权中位数。将公式(13)(14)插入到算法1的第4，5行，得到损失函数为绝对值误差的求解方法，基学习器  可取任何模型。
3. Regression trees.

这里考虑，基分类器使用包含k个叶子结点的回归树。每棵回归树的形式如下：
(15)   $h(x;\left\{ b_{j},R_{j} \right\}_{1}^{J}) = \sum_{j=1}^{J}{b_{j}1(x∈ R_{j})}$
这里 $\left\{R_{j} \right\}_{1}^{J}$ 是不相交的区域，是所有输入变量  的分段函数映射值。通过决策树的路径映射到最终叶子节点。指示函数 $1(.)$ 表示当参数为true的时候，值为1，否则，为0。决策树(公式15)的参数是系数 $\left\{ b_{j} \right\}_{1}^{J}$ 以及叶子结点的 $\left\{ R_{j} \right\}_{1}^{J}$ 以及用来用来分裂的非叶子结点上的变量集分裂位置。
对于回归树来说，算法1中第六行，模型的迭代如下：
(16)   $F_{m}(x) = F_{m-1}(x) + \rho_{m}\sum_{j=1}^{J}{b_{jm}1(x∈R_{jm})}$
在均方误差损失函数下， $b_{jm}$ 的值

$b_{jm} = avg_{x∈R_{jm}}\tilde{y}_{i}$
算法1第5行的缩放因为  ，将公式(16)重写为
(17)   $F_{m}(x) = F_{m-1}(x) + \sum_{j=1}^{J}{\gamma_{jm}1(x∈R_{jm})}$
其中 $\gamma_{jm} = \rho_{m}b_{jm}$ 。可以将公式(17)看成J个基础函数的相加，而不是像公式(16)那样加上一个单独的函数。这样做的好处是可以通过优化公式(17)中每个单独函数的系数进一步优化拟合效果。系数的优化如下：

$\left\{ r_{jm} \right\}_{1}^{J} = arg\min_{\left\{ r_{j} \right\}_{1}^{J}}\sum_{i=1}^{N}{L(y_{i},F_{m-1}(x)+\sum_{j=1}^{J}{\gamma_{j}1(x_{i}∈R_{jm})})}$
因为回归树的叶子结点是不相交的，上述公式可以优化为：
(18)   $r_{jm} = arg\min_\gamma \sum_{x∈R_{jm}}{L(y_{i},F_{m-1}(x_i)+\gamma)}$
给定上一步的累计值  ,基于绝对值损失函数 $L=|y-F|$ 优化每一个叶子结点上面的值

$\gamma_{jm} = median_{x_{i}∈R_{jm}}\left\{ y_{i} - F_{m-1}(x_i)\right\}$
仅需要取每个叶子结点的残差值的中位数作为叶子节点的值即可。在绝对值损失函数下，每次迭代，基函数拟合的是当前残差的sign值，最后，将每个叶子结点的值修正为到达该叶子结点的每个样本的残差值的中位数，得到如下算法，算法三：

该算法具有高度鲁棒性的优点。因为回归树算法仅用到每个输入变量 $x_{j}$ 的顺序信息，目标值  也仅仅只有两个值 $\tilde{y}_i ∈ \left\{ +1,-1 \right\}$ ,以及叶子结点是通过残差中位数更新的。
另一种方法是构建一棵树来直接最小化损失标准，

$tree_m = arg\min_{J-node\ tree}\sum_{i=1}^{N}{|y_{i}-F_{m-1}(x_i)-tree(x_i)|}$

$F_m(x) = F_{m-1}(x) + tree_m(x)$
然而，算法3更快，因为他使用均方误差损失函数来建树。在建树过程中，均方误差损失函数搜索分裂点的速度远大于绝对值损失函数。
4. M-Regression.

M回归的设计是针对长尾和异常点有高度鲁棒性，同时保持对正态分布误差的高敏感性。该算法使用Huber损失函数
（19） $L(y,F) = \begin{cases} \frac{1}{2}(y-F)^{2}, \ \ |y-F|\leq\delta, \\ \delta(|y-F|-\delta/2), \ \ |y-F|>\delta. \end{cases}$
因此，伪响应 $\tilde{y}_{i}$ 为：

$\tilde{y}_{i} = \begin{cases} y_{i}-F_{m-1}(x_i), \ \ |y_{i}-F_{m-1}(x_i)|\leq\delta, \\ \delta * sign(y_{i}-F_{m-1}(x_i)), \ \ |y_{i}-F_{m-1}(x_i)|>\delta, \end{cases}$
这时  为：
（20） $\rho_{m} = arg\min_\rho \sum_{i=1}^{N}{L(y_i,F_{m-1}(x_i)+\rho h(x_i;a_m))}$
其中L是公式(19)中的损失函数。
在这个损失函数中，阈值  将残差的某些值定义为异常值，并且用绝对值损失函数而不是均方误差去定义其造成的损失。一个好的  是需要根据 $y-F^*(x)$ 的分布定义，  是目标函数。一个常用的做法是选择 $|y-F^*(x)|$ 的 $\alpha$ 分位点作为  的值，这样 $1-\alpha$ 决定了异常值的数量。但由于目标函数  是未知的，因此在每一步迭代的时候，使用上一步的结果  作为第m次迭代的的估计值，进行计算，因此 $\delta_m$ 为：

$\delta_m = quantile_\alpha\left\{ |y_i - F_{m-1}(x_i)| \right\}_{1}^{N}$
当基函数为回归树的时候，并且按照公式(18)进行每个叶子结点 $R_{jm}$ 节点值  的计算，带入公式(19)的Huber损失函数形式得到节点值的计算逻辑如下：

$\tilde{\gamma}_{jm} = median_{x_i ∈ R_{jm}}\left\{ y_i - F_{m-1}(x_i) \right\}$

$\gamma_{jm} = \tilde{\gamma}_{jm}\frac{1}{N_{jm}}\sum_{x_i∈R_{jm}}{sign(y_i-F_{m-1}(x_i)-\tilde{\gamma}_{jm}).min(\delta_m,abs(y_i-F_{m-1}(x_i)-\tilde{\gamma}_{jm}))}$
$N_{jm}$ 是第j个叶子节点上面的样本数，因此，基于Huber损失函数的GBDT算法伪代码如下：

基于模型鲁棒性提出的算法四，在正态分布误差上面的表现接近于算法2(损失函数为均方误差)，在长尾误差分布上面的表现接近于算法3(绝对值误差)，对于只有中长尾误差的分布，它的性能可以优于两者。
5. Two-class logistic regression and classification.

这里，损失函数为 negative binomial log-likelihood (FHT00)

$L(y,F) = log(1+e^{-2yF}),\ \ \ \ y∈\left\{ -1,1 \right\},$
其中 $F(x)$ 拟合的是对数几率
(21) $F(x) = \frac{1}{2}log\left[ \frac{Pr(y=1|x)}{Pr(y=-1|x)} \right]$
伪响应
(22)   $\tilde{y}_i = -\left[ \frac{\partial L(y_i,F(x_i))}{\partial F(x_i)} \right]_{F_m(x) = F_{m-1}(x)} = 2y_i/(1+exp(2y_iF_{m-1}(x_i)))$

的更新如下：

$\rho_m = arg\min_\rho\sum_{i=1}^{N}{log(1+exp(-2y_i(F_{m-1}(x_i)+\rho h(x_i;a_m))))}$
当使用回归树作为基函数时，每个叶子结点 $J_{jm}$ 的值  如下：
(23) $\gamma_{jm} = arg\min_\gamma\sum_{x_i∈R_{jm}}{log(1+exp(-2y_i(F_{m-1}(x_i)+\gamma)))}$
公式(23)没有闭式解，根据算法FHT00，得到  的解如下：

$\gamma_{jm} = \sum_{x∈R_{jm}}{\tilde{y}_i/ \sum_{x∈R_{jm}}|\tilde{y}_i|(2-|\tilde{y}_i|)}$
因此，二分类问题下的GBDT算法如下：

最终的拟合函数 $F_M(x)$ 就与公式(21)中的对数几率相关。通过如下方式将它转换成概率：

$p_+(x) = \hat{Pr}(y=1|x) = 1/(1+e^{-2F_M(x)}),$

$p_-(x) = \hat{Pr}(y=-1|x) = 1/(1+e^{2F_M(x)}).$
最终的类别可用如下公式确定：

$\hat{y}(x) = 2*1\left[ c(-1,1)p_+(x)>c(1,-1)p_-(x) \right]-1$
其中 $c(\hat{y},y)$ 是预测错误的代价。
5.1 Influence trimming
对于2分类分体来说，在第  次迭代时的经验损失为：
(24) $\phi_m(\rho,a) = \sum_{i=1}^{N}{log(1+e^{-2y_i(F_{m-1}(x_i)+\rho h(x_i;a))})} = \sum_{i=1}^{N}{log\left[ 1+ exp(-2y_iF_{m-1}(x_i))exp(-2y_i\rho h(x_i;a)) \right]}$
当很大的时候，公式(24)几乎不依赖于  ，且接近于0，这意味着该样本  对损失函数几乎没有贡献，因此在求解 $(\rho_m,a_m)$

$(\rho_m,a_m) = arg\min_{\rho,a}\phi_m(\rho,a)$
在求解上述公式的时候，可以将  值很大的样本对  从第  迭代的计算中删除也不会对结果有显著的影响。因此，
(25)   $\omega_i = exp(-2y_iF_{m-1}(x_i))$
可以被看成第 $i$ 个样本对训练  的影响或者说是权重。
此外，在第二章所讲述的函数空间视角下，观察值 $\left\{ F(x_i) \right\}_1^N$ 就是参数，参数 $F(x_i)$ 对函数估计的影响(保持其他值固定)，可以用损失函数对该参数的二阶导来衡量。第  次迭代的二阶导为 $|\tilde{y}_i|(2-|\tilde{y}_i|)$ ，因此，另外一个衡量样本  在第  次迭代对训练函数 $\rho_m h(x_i;a_m)$ 的贡献值指标为：
(26)   $\omega_i = |\tilde{y}_i|(2-|\tilde{y}_i|)$
在  次迭代中，删除所有 $\omega_i<\omega_{l(a)}$ 的样本， $l(a)$ 通过如下公式计算：
(27) $\sum_{i=1}^{l(a)}{w_{(l)}} = \alpha \sum_{i=1}^{N}{w_i}$
这里， $\left\{ \omega_{(i)} \right\}_1^N$ 是 $\left\{ \omega_i \right\}_1^N$ 的增序序列，通常 $\alpha ∈ [0.05,0.2]$ 。算法Real AdaBoost中使用的迭代方案是公式(25),(27)，而FHT00 中 LogitBoost算法使用的迭代方案是公式(26),(27)。大概有90%~95%的样本在每次迭代中被删除而不会影响算法的整体精度，使计算量相应减少 10 到 20 倍。

		自动登录	找回密码
密码			立即注册

GBDT算法介绍

本帖子中包含更多资源