梯度提升分类树原理推导（超级详细！）

作者: 人生茫茫好似荒野 | 来源:发表于2020-03-26 22:28 被阅读0次

GBDT (Gradient Boosting Decision Tree) ，梯度提升树，是属于集成算法中boosting类的一种算法。GBDT中又分梯度提升回归树和梯度提升分类树。本文就讨论一下梯度提升分类树（只讨论二分类）的原理以及公式推导。

梯度提升分类树的原理及公式推导

梯度提升分类树的原理和思想和梯度提升回归树本质上是没有区别的。他们的模型都是决策回归树(DecisionTreeRegressor),可能有人有疑问，为什么梯度提升分类树的模型也是决策回归树，那是怎么实现分类的呢？其实梯度提升分类树和逻辑斯蒂回归类似。

逻辑斯蒂回归的预测模型：sigmoid函数 + 线性回归

梯度提升分类树的预测模型： sigmoid函数 + 决策回归树

梯度提升分类树的预测概率为 $p = \frac{1}{1 + exp(-F(x))}$ ，其中 $F(x)$ 表示决策回归树。

但是由于梯度提升分类树的样本输出不是连续的而是离散的，因此无法直接拟合类别输出的误差。这时候需要构建交叉熵损失函数(也叫对数损失函数)。那么什么是交叉熵损失函数呢？

关于交叉熵，大家看看这篇文章，相信对交叉熵一定有一个深刻的理解。总之，交叉熵就是用来衡量在给定的真实分布下，使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小。

交叉熵的公式为： $\sum\limits_{k=1}^{N}p_klog_2\frac{1}{q_k}$ ，其中 $p_k$ 表示真实分布， $q_k$ 表示非真实分布。

一个样本的交叉熵损失函数可以表示成： $\psi(y,F(x)) = -ylog_2(p) - (1-y)log_2(1-p)$ ，其中 $p = \frac{1}{1 + exp(-F(x))}$

其中 $y$ 就是真实概率，相当于真实分布 $p_k$ ， $p$ 是算法预测的概率，相当于非真实分布 $q_k$ 。

将 $p = \frac{1}{1 + exp(-F(x))}$ 代入到函数中化简：

$\begin{align} \psi(y,F(x)) &= -ylog_2(\frac{1}{1 + exp(-F(x))}) - (1 - y)log_2(1 - \frac{1}{1 + exp(-F(x))})\\ &= ylog(1 + exp(-F(x))) - (1-y)log(\frac{exp(-F(x))}{1 + exp(-F(x))})\\ &= ylog(1 + exp(-F(x))) - (1 - y)(-F(x) - log(1 + exp(-F(x))))\\ &= (1 -y)F(x) + ylog(1 + exp(-F(x))) + (1 - y)log(1 + exp(-F(x)))\\ &= (1 - y)F(x) + log(1 + exp(-F(x)))\\ &= -yF(x) + F(x) + log(1 + exp(-F(x)))\\ &= -yF(x) + log(exp(F(x))) + log(1 + exp(-F(x)))\\ &= -yF(x) + log(exp(F(x))*(1 + exp(-F(x)))\\ &= -yF(x) + log(1 + exp(F(x))) \end{align}$
化简的最后结果为 $\psi(y,F(x)) = -yF(x) + log(1 + exp(F(x)))$

求 $\psi(y,F(x))$ 对于 $F(x)$ 的一阶导数：
$\begin{align} \psi'(y,F(x)) &= -y + \frac{exp(F(x))}{1 + exp(F(x))}\\ &= -y + \frac{1}{1 + exp(-F(x))} \end{align}$
令 $\sigma(F(x)) = \frac{1}{1 + exp(-F(x))}$ ，有 $\psi'(y,F(x)) = -y + \sigma(F(x))$

利用sigmoid函数求导公式，求 $\psi(y,F(x))$ 对于 $F(x)$ 的二阶导数：
$\begin{align} \psi''(y,F(x)) &= -\frac{1}{(1 + exp(-F(x)))^2}*exp(-F(x))*(-1)\\ &= \frac{1}{1 + exp(-F(x))}*\frac{exp(-F(x))}{1 + exp(-F(x))}\\ &= \frac{1}{1 + exp(-F(x))}*\frac{exp(-F(x))+1-1}{1 + exp(-F(x))}\\ &= \frac{1}{1 + exp(-F(x))}*(1-\frac{1}{1 + exp(-F(x))})\\ &= \sigma(F(x))(1 - \sigma(F(x))) \end{align}$
以上就是单个样本的损失函数推导，那么整体的损失函数也就容易了，就是单个样本的累加。

损失函数推导出来了，接下来我们看看梯度和损失函数的更新方式是怎样的。

上文中提到 $F(x)$ 是决策回归树，当算法还没有第一轮学习时，算法会给 $F(x)$ 一个初始值，我们记为 $F_0(x) = \rho$ ，此时 $\rho$ 是最小的。因为 $F(x)$ 的更新规则是 $F_m(x) = F_{m-1}(x) + \gamma_m*learnin\_rate$ ， $F_{m-1}(x)$ 表示相对 $F_m(x)$ 上一次的值， $\gamma_m$ 表示第m轮学习的预测结果（稍后我们会进行推导）。 $learning\_rate$ 表示学习率，学习率是我们给定算法的参数。

因此有式
$\begin{align} F_0(x) &= {argmin}_{\rho}\sum\limits_{i = 1}^N\psi(y_i,\rho)\\ &= =argmin_{\rho}H(\rho)\\ &= -\sum\limits_{i=1}^N(y_i\rho -log(1 + exp(\rho))) \end{align}$
其中， $H(\rho)$ 表示整体的损失函数，现在令其导数为0，求解出 $\rho$ 即为最小值。

$H'(\rho) = -\sum\limits_{i = 1}^N(y_i - \frac{1}{1 + exp(-\rho)})$

$0 = -\sum\limits_{i = 1}^N(y_i -\frac{1}{1 + exp(-\rho)})$

$\sum\limits_{i=1}^Ny_i = \sum\limits_{i=1}^N\frac{1}{1+exp(-\rho)}$

上式右边可以看做一个常数，因此有

$\sum\limits_{i=1}^Ny_i = \frac{\sum\limits_{i=1}^N1}{1+exp(-\rho)}$

两边求倒数，

$\frac{1}{\sum\limits_{i=1}^Ny_i} = \frac{(1 + exp(-\rho))}{\sum\limits_{i=1}^N1}$

$1 + exp(-\rho) = \frac{\sum\limits_{i=1}^N1}{\sum\limits_{i=1}^Ny_i}$

$exp(-\rho) = \frac{\sum\limits_{i=1}^N1}{\sum\limits_{i=1}^Ny_i} - 1$

$exp(-\rho) = \frac{\sum\limits_{i=1}^N(1 -y_i)}{\sum\limits_{i=1}^Ny_i}$

$-\rho = log\frac{\sum\limits_{i=1}^N(1 -y_i)}{\sum\limits_{i=1}^Ny_i}$

$\rho = log\frac{\sum\limits_{i=1}^Ny_i}{\sum\limits_{i=1}^N(1 -y_i)}$

这样，算法的初始值就求出来了。上文说到 $\gamma_m$ 表示第m轮学习的预测结果，那我们把第m轮的学习中，树的第j个叶子节点的结果记为 $\gamma_{mj}$ ，其推导过程如下：

$F_m(x) = F_{m-1}(x) + \gamma_m*learnin\_rate$

$L(\gamma_{mj},R_{mj}) = \sum_{x_i \in R_{mj}}\psi(y,F_{m-1}(x) + \gamma_{mj})$

注：这里 $learning\_rate$ 可写可不写，因为是个常数，不管它给多少，最后都会消掉。 $R_{mj}$ 表示第m轮样本数据。

要求解的 $\gamma_{mj} = argmin_{\gamma_{mj}}L(\gamma_{mj},R_{mj})$

利用泰勒展开公式，就可以将上式展开两级，得到：

$\gamma_{mj} = argmin_{\gamma_{mj}}L(\gamma_{mj},R_{mj}) \approx \sum_{x_i \in R_{mj}}\{\psi(y,F_{m-1}(x)) + \psi'(y,F_{m-1}(x))\gamma_{mj} + \frac{1}{2}\psi''(y,F_{m-1}(x))\gamma_{mj}^2 \}$

要求最小，求导，令导数为零，即

$\sum_{x_i \in R_{mj}}\{\psi'(y_i,F_{m-1}(x_i)) + \psi''(y_i,F_{m-1}(x_i))*\gamma_{mj}\} = 0$

上文我们对 $\psi(y,F(x))$ 的一阶导数和二阶导数已经做了推导，

$\psi'(y,F(x)) = -y + \sigma(F(x))$

$\psi'(y,F(x)) = \sigma(F(x))(1 - \sigma(F(x)))$

其中， $\sigma(F(x)) = \frac{1}{1 + exp(-F(x))}$ ，我们令 $\widetilde{y} = y - \sigma(F(x))$ ， $\widetilde{y}$ 把它叫做负梯度，因此有

$\sum_{x_i \in R_{mj}}\{-\widetilde{y_i} + (y_i - \widetilde{y_i})(1 - y_i + \widetilde{y_i}) *\gamma_{mj}\} = 0$

进行变换，解出 $\gamma_{m j}$

$\sum_{x_i \in R_{mj}}\widetilde{y_i} = \sum_{x_i \in R_{mj}}(y_i - \widetilde{y_i})(1 - y_i + \widetilde{y_i}) *\gamma_{mj}$

$\gamma_{mj} = \frac{\sum_{x_i \in R_{mj}}\widetilde{y_i}}{\sum_{x_i \in R_{mj}}(y_i - \widetilde{y_i})(1 - y_i + \widetilde{y_i})}$

梯度提升分类树的算例

接下来我们就通过一个算例来看看由算法计算的结果和我们推导的公式计算的结果是不是一样的（基于sklearn）。同时，加深一下对算法原理的理解。

导包、准备数据

$x_i$ 1 2 3 4 5 6 7 8 9 10

$y_i$ 0 0 0 1 1 0 0 0 1 1

$x_i$	1	2	3	4	5	6	7	8	9	10
$y_i$	0	0	0	1	1	0	0	0	1	1

# 导包
import numpy as np
from sklearn.ensemble import GradientBoostingClassifier
from sklearn import tree

# 准备数据
X = np.arange(1,11).reshape(-1,1)
y = np.array([0,0,0,1,1]*2)

声明算法，进行训练和预测

# 声明函数  默认损失函数是log-loss  ==  交叉熵损失函数
# n_estimators=100 - 100棵树 ， learning_rate=0.1 - 学习率0.1 ， max_depth=1 - 树深度1
clf = GradientBoostingClassifier(n_estimators=100, learning_rate=0.1, max_depth=1)
clf.fit(X,y)    # 训练
clf.predict(X)  # 预测

绘制第1,2,3,100棵树的图形

_ = tree.plot_tree(clf[0,0],filled=True) # 第1棵树

first_tree.png

_ = tree.plot_tree(clf[1,0],filled=True) # 第2棵树

second_tree.png

_ = tree.plot_tree(clf[2,0],filled=True) # 第3棵树

third_tree.png

_ = tree.plot_tree(clf[99,0],filled=True) # 第100棵树

hundred_tree.png

上面是算法计算的结果，接下来我们调用上面推导的公式计算一下。

初始化算法，计算初始值，根据公式 $\rho = log\frac{\sum\limits_{i=1}^Ny_i}{\sum\limits_{i=1}^N(1 -y_i)}$ ，分子上是类别1，分母上是类别0；1有4个，0有6个；
```
F_0 = np.log(4/6)
F_0
```
计算出初始值为-0.40546510810816444
计算负梯度 $\widetilde{y}$ ，根据公式 $\widetilde{y} = y - \frac{1}{1 + exp(-F(x))}$
```
y_d0 = y - 1/(1 + np.exp(-F_0))
y_d0
```
得到结果为 array([-0.4, -0.4, -0.4, 0.6, 0.6, -0.4, -0.4, -0.4, 0.6, 0.6])
拟合第一棵树
```
# 分裂标准 mse - 均方误差
for i in range(1,11):
    if i ==10:
        mse = ((y_d0 - y_d0.mean())**2).mean()
    else:
        left_mse = ((y_d0[:i] - y_d0[:i].mean())**2).mean()
        right_mse = ((y_d0[i:] - y_d0[i:].mean())**2).mean()
        mse = left_mse*i/10 + right_mse*(10-i)/10
    print('从第%d个进行切分'%(i),mse)
```
结果为：

从第1个进行切分 0.22222222222222224
从第2个进行切分 0.2
从第3个进行切分 0.17142857142857143
从第4个进行切分 0.22499999999999998
从第5个进行切分 0.23999999999999994
从第6个进行切分 0.23333333333333336
从第7个进行切分 0.20952380952380956
从第8个进行切分 0.15
从第9个进行切分 0.2
从第10个进行切分 0.24

因此从第8棵树开始切分。

计算左右两侧叶子的预测值，根据公式 $\gamma_{mj} = \frac{\sum_{x_i \in R_{mj}}\widetilde{y_i}}{\sum_{x_i \in R_{mj}}(y_i - \widetilde{y_i})(1 - y_i + \widetilde{y_i})}$

# 分子
f1 = y_d0[:8].sum()
# print(f1)
# 分母
f2 = ((y[:8] - y_d0[:8])*(1 - y[:8] + y_d0[:8])).sum()

gamma1 = np.round(f1/f2,3)
print('左边决策树分支，预测值：',gamma1)

# 右边分支
gamma2 =np.round(y_d0[8:].sum()/((y[8:] - y_d0[8:])*(1 - y[8:] + y_d0[8:])).sum(),3)
print('右边决策树分支，预测值：',gamma2)

运行结果为：

左边决策树分支，预测值： -0.625
右边决策树分支，预测值： 2.5

预测结果和算法计算的结果完全一样！

拟合第二棵树

# 第一棵树的预测结果，计做gamma
gamma = np.array([-0.625]*8 + [2.5]*2)
gamma

# F(x)随着梯度提升树提升
F_1 =np.round( F_0 + gamma*0.1,4)
F_1

# 计算F1(x)的负梯度
y_d1 = np.round(y - 1/(1 + np.exp(-F_1)), 4)
y_d1

# 第二棵树分裂标准 mse
for i in range(1,11):
    if i ==10:
        mse = ((y_d1 - y_d1.mean())**2).mean()
    else:
        left_mse = ((y_d1[:i] - y_d1[:i].mean())**2).mean()
        right_mse = ((y_d1[i:] - y_d1[i:].mean())**2).mean()
        mse = left_mse*i/10 + right_mse*(10-i)/10
    print('从第%d个进行切分'%(i),mse)

# 第二棵树也是从第八个样本进行切分 

# 分子
f1 = y_d1[:8].sum()
# print(f1)
# 分母
f2 = ((y[:8] - y_d1[:8])*(1 - y[:8] + y_d1[:8])).sum()

gamma1 = np.round(f1/f2,3)
print('左边决策树分支，预测值：',gamma1)

# 右边分支
gamma2 =np.round(y_d1[8:].sum()/((y[8:] - y_d1[8:])*(1 - y[8:] + y_d1[8:])).sum(),3)
print('右边决策树分支，预测值：',gamma2)

运行结果为：

左边决策树分支，预测值： -0.571
右边决策树分支，预测值： 2.168

和算法预测的结果也是一样！以此类推，我们可以计算到第100棵树，会发现每棵树的预测结果和算法计算的都一样，因此我们的公式推导是正确的！

我们也可以写一个for循环，计算出1~100棵树的预测结果。

# 初始值
F_ = np.log(4/6)

for m in range(0, 100):
    # 函数F(x)初始值的负梯度
    y_di = np.round(y - 1/(1 + np.exp(-F_)), 4)
    
    # 分裂标准 mse
    total_mse = []
    for i in range(1,11):
        if i ==10:
            mse = ((y_di - y_di.mean())**2).mean()
        else:
            left_mse = ((y_di[:i] - y_di[:i].mean())**2).mean()
            right_mse = ((y_di[i:] - y_di[i:].mean())**2).mean()
            mse = left_mse*i/10 + right_mse*(10-i)/10
        total_mse.append(mse)
    index = total_mse.index(min(total_mse))+1
    
    # 分子
    f1 = y_di[:index].sum()
    # 分母
    f2 = ((y[:index] - y_di[:index])*(1 - y[:index] + y_di[:index])).sum()

    gamma1 = np.round(f1/f2,3)
    print('第%d棵树左边决策树分支，预测值：'%(m+1),gamma1)

    gamma2 =np.round(y_di[index:].sum()/((y[index:] - y_di[index:])*(1 - y[index:] + y_di[index:])).sum(),3)
    print('第%d棵树右边决策树分支，预测值：'%(m+1),gamma2)
    
    gamma = np.array([gamma1]*index + [gamma2]*(10 - index))
    F_ = np.round( F_ + gamma*0.1, 4)

运行得到一下结果：

第1棵树左边决策树分支，预测值： -0.625
第1棵树右边决策树分支，预测值： 2.5
第2棵树左边决策树分支，预测值： -0.571
第2棵树右边决策树分支，预测值： 2.168
第3棵树左边决策树分支，预测值： -1.592
第3棵树右边决策树分支，预测值： 0.666
......
第99棵树左边决策树分支，预测值： -1.057
第99棵树右边决策树分支，预测值： 0.245
第100棵树左边决策树分支，预测值： 0.411
第100棵树右边决策树分支，预测值： -0.424

梯度提升分类树原理推导（超级详细！）

梯度提升分类树的原理及公式推导

梯度提升分类树的算例

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读