机器学习13 GBDT

这一篇开始讲GBDT(梯度提升决策树)，根据上一篇可知，该模型每次学习的是损失函数的负梯度。所以基模型是回归树（因为每次都在拟合一个确定的值，这和提升树不一样了，提升树中分类问题的基模型是二叉分类树）。正如提升树中所讲， GBDT可以用于回归问题，也可以用于分类问题。学习的流程和提升树是一致的，在确定损失函数后，只是基模型学习的目标不一样。最后的模型就是基模型的线性组合。

F表示组合的模型， f表示每次学习的模型，首先我们定义一下损失函数 $L(y,F_m(x)) = L(y, F_{m-1}(x) + \alpha_m f_m(x))$

泰勒展开，保留第一项，得到 $L(y, F_m(x)) = L(y,F_{m-1}(x)) +f_m(x)\frac{\partial L(y,X)}{\partial X}_{|X=F_{m-1}(x)}$

所以当 $f_m(x) = -\alpha\frac{\partial L(y,X)}{\partial X}_{|X=F_{m-1}(x)}$ 时，损失函数会变小。

对于回归问题:

损失函数可以是MSE， $L(y,F_m(x)) = \frac{1}{2}(y-F_m(x))^2$ , 梯度是 $\frac{\partial L}{\partial X}_{|X=F_{m-1}(x)} = F_{m-1}(x) - y$

损失函数还可以是绝对误差MAE， $L(y,F_m(x)) = |(y-F(x)|$ ， $\frac{\partial L}{\partial X}_{|X=F_{m-1}(x)} = sign(y-F_{m-1}(x))$

新的模型去拟合负梯度即可(对于MSE，拟合负梯度和拟合残差是一样的),和提升树一样的学习即可。

对于二分类问题：

损失函数 $L (y,F_m(x)) = log(1+e^{-yF_m(x)})$

$\frac{\partial L(y, F(x))}{\partial F(x)}_{|F(x) = F_{m-1}(x)}= \frac{-y}{1 + exp(yF_{m-1}(x))}$

第m步的基模型拟合了m-1步之后的负梯度，

因此首先需要有第0个基模型，

$F_0(x) = \mathop{argmin}_{F}\sum_{x_i} log(1+e^{-y_iF(x_i)})$

对F求偏导， $\frac{\partial \sum_{x_i} log(1+e^{-y_iF(x_i)})}{\partial F} = \frac{-y_ie^{-y_iF(x_i)}}{1+e^{-y_iF(x_i)}} = 0$

$\Rightarrow \sum_{y_i=1}\frac{-e^{-F}}{1+e^{-F}} +\sum_{y_i=-1}\frac{e^F}{1+e^{F}} = 0$

$\Rightarrow \sum_{y_i=1}\frac{-1}{1+e^{F}} +\sum_{y_i=-1}\frac{e^F}{1+e^{F}} = 0$

$-m + ne^F = 0 \Rightarrow e^F=m/n = \frac{1 +\frac{m-n}{m+n}}{1-\frac{m-n}{m+n}} = \frac{1+\bar y}{1 - \bar y}$

$F_0 = log\frac{1+\bar y}{1 - \bar y}$

m步拟合了负梯度之后，模型变成了 $F_m(x) = F_{m-1}(x) + \alpha _mf_m(x) = F_{m-1}(x) + \alpha _m *(-\frac{\partial L(y, F_{m-1}(x)}{\partial F_{m-1}(x)})$

$= F_{m-1}(x) + \alpha _m *\frac{y}{1 + exp(yF_{m-1}(x))}$

负梯度就是参数变化的方向，现在我们需要找到 $\alpha_{m}$ ，使得损失函数最小，即

$\alpha_{m} = \mathop{argmin}_{\alpha}\sum_{x_i}L(y_i,F_{m-1}(x_i) + \alpha f_m(x_i)) = \mathop{argmin}_{\alpha}\sum_{x_i} log(1+e^{(-y_i(F_{m-1}(x_i)+\alpha f_m(x_i))})$

我们不妨把 $\alpha _mf_m(x)$ 定义成 $\sum_{j=1}^Jc_{m,j}1(x \in R_{m,j})$ , 即第m个基模型的第j个划分空间值为 $c_{m,j}$ 。

所以第m个基模型求解变成了， $c_{mj} = \mathop{argmin}_{c}\sum_{x_i \in R_{mj}}L(y_i,F_{m-1}(x_i) +c) = \mathop{argmin}_{c}\sum_{x_i \in R_{mj}} log(1+e^{(-y_i(F_{m-1}(x_i)+c)})$

这个优化问题非常难求，这里用牛顿法做一个近似

$f(c) = \sum_{x_i \in R_{mj}} log(1+e^{(-y_i(F_{m-1}(x_i)+c)})$

$f’(c) = \sum_{x_i\in R_{mj}} \frac{-y_i}{1 + exp(y_iF_{m-1}(x_i) +c)}$

$f’’(c) = \sum_{x_i\in R_{mj}} \frac{y_iexp(y_i(F_{m-1}(x_i) +c))}{(1 + exp(y_i(F_{m-1}(x_i) +c))^2}$

$c_{m,j} = c_0 - \frac{f’(c)}{f’’(c)}$ , $c_0 = 0$

所以 $c_{mj} = \frac{\sum_{x_i\in R_{mj}}r_{m-1,i}}{\sum_{x_i\in R_{mj}}|r_{m-1,i}|(1-|r_{m-1,i}|)}$ , 其中 $r_{m-1,i}$ 是m-1步之后第i个样本的负梯度值，即 $r_{m-1,i} = \frac{y_i}{1 + exp(y_iF_{m-1}(x))}$

即解出了 $\alpha _mf_m(x)$ 。

多分类问题:

损失函数使用交叉熵损失函数， $L(y,F_m(x)) = -\sum_{k=1}^Ky_klog(p_k(x))$ , 其中， $p_k(x) = \frac{exp(f_k(x))}{\sum_{l=1}^K(f_l(x))}$ , 一共有K个二分类，所以每一步都有k个基模型，一共有m*K个基模型。

$\frac{\partial L(y,X)}{\partial X}_{|X=F_{l,m-1}(x)} = -y_{i,l} + p_{m-1,l}(x)$ , 如果 $y_i$ 是类别l的类，则 $y_{i,l}$ = 1，不然为0

每一步都是k个二分类， $F_k(x)$ ,

$F_{m,l}(x) = F_{m-1,l}(x) + \alpha _{m,l}f_{m,l}(x) = F_{m-1,l}(x) + \alpha _{m,l} *(-\frac{\partial L(y, F_{m-1,l}(x)}{\partial F_{m-1,l}(x)})$

同理，现在我们需要找到 $\alpha_{m,l}$ ，使得

$\alpha_{m,l} = \mathop{argmin}_{\alpha}\sum_{x_i}L(y_i,F_{m-1,l}(x_i) + \alpha f_{m,l}(x_i))$

同样把 $\alpha _{m,l}f_{m,l}(x)$ 定义成 $\sum_{j=1}^Jc_{m,j,l}1(x \in R_{m,j,l})$

$c_{m,j,l} = \frac{K-1}{K} \frac{\sum_{x_i\in R_{m,j,l}}r_{m-1,i,l}}{\sum_{x_i\in R_{m,j,l}}|r_{m-1,i,l}|(1-|r_{m-1,i,l}|)}$ , 其中 $r_{m-1,i,l} = y_{i,l} - p_{l,m-1}(x_i)$ , 即m-1步学习后， $l$ 类中第i个点的负梯度。

第m步学习就结束了

GBDT的介绍就到这里了，和提升树的不同就在于GBDT学习的是损失函数的负梯度，参数每次沿着负梯度前进一小步

在CTR预估中，会结合使用GBDT+LR， GBDT用来生成特征，增强LR模型的非线性能力。这一块读者可以查询相关的文章。

下一篇会介绍下一个Boosting模型，它在GBDT上又改进了一些内容，是一个大杀器。