GBDT (Gradient Boosting Decision Tree) ，梯度提升树，是属于集成算法中boosting类的一种算法。GBDT中又分梯度提升回归树和梯度提升分类树。本文就讨论一下梯度提升分类树（只讨论二分类）的原理以及公式推导。
梯度提升分类树的原理和思想和梯度提升回归树本质上是没有区别的。他们的模型都是决策回归树(DecisionTreeRegressor),可能有人有疑问，为什么梯度提升分类树的模型也是决策回归树，那是怎么实现分类的呢？其实梯度提升分类树和逻辑斯蒂回归类似。
逻辑斯蒂回归的预测模型：sigmoid函数 + 线性回归
梯度提升分类树的预测模型： sigmoid函数 + 决策回归树
梯度提升分类树的预测概率为 ，其中 表示决策回归树。
但是由于梯度提升分类树的样本输出不是连续的而是离散的，因此无法直接拟合类别输出的误差。这时候需要构建交叉熵损失函数(也叫对数损失函数)。那么什么是交叉熵损失函数呢？
关于 交叉熵 ，大家看看这篇文章，相信对交叉熵一定有一个深刻的理解。总之，交叉熵就是 用来衡量在给定的真实分布下，使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小 。
交叉熵的公式为： ，其中 表示真实分布， 表示非真实分布。
一个样本的交叉熵损失函数可以表示成： ，其中
其中 就是真实概率，相当于真实分布 ， 是算法预测的概率，相当于非真实分布 。
将 代入到函数中化简：
化简的最后结果为
求 对于 的一阶导数：
令 ，有
利用sigmoid函数求导公式，求 对于 的二阶导数：
以上就是单个样本的损失函数推导，那么整体的损失函数也就容易了，就是单个样本的累加。
损失函数推导出来了，接下来我们看看梯度和损失函数的更新方式是怎样的。
上文中提到 是决策回归树，当算法还没有第一轮学习时，算法会给 一个初始值，我们记为 ，此时 是最小的。因为 的更新规则是 ， 表示相对 上一次的值， 表示第m轮学习的预测结果（稍后我们会进行推导）。 表示学习率，学习率是我们给定算法的参数。
因此有式
其中， 表示整体的损失函数，现在令其导数为0，求解出 即为最小值。
上式右边可以看做一个常数，因此有
两边求倒数，
这样，算法的初始值就求出来了。上文说到 表示第m轮学习的预测结果，那我们把第m轮的学习中，树的第j个叶子节点的结果记为 ，其推导过程如下：
注：这里 可写可不写，因为是个常数，不管它给多少，最后都会消掉。 表示第m轮样本数据。
要求解的
利用 泰勒展开公式 ，就可以将上式展开两级，得到：
要求最小，求导，令导数为零，即
上文我们对 的一阶导数和二阶导数已经做了推导，
其中， ，我们令 ， 把它叫做负梯度，因此有
进行变换，解出
接下来我们就通过一个算例来看看由算法计算的结果和我们推导的公式计算的结果是不是一样的（基于sklearn）。同时，加深一下对算法原理的理解。
_ = tree.plot_tree(clf[0,0],filled=True) # 第1棵树
_ = tree.plot_tree(clf[1,0],filled=True) # 第2棵树
_ = tree.plot_tree(clf[2,0],filled=True) # 第3棵树
_ = tree.plot_tree(clf[99,0],filled=True) # 第100棵树
上面是算法计算的结果，接下来我们调用上面推导的公式计算一下。
我们也可以写一个for循环，计算出1~100棵树的预测结果。
运行得到一下结果：
第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