GBDT

提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树。提升树模型可以表示为决策树的加法模型：

其中，表示决策树；为决策树的参数；为树的个数。

提升树算法采用前向分步算法。首先确定初始提升树，第步的模型是

其中，为当前模型，通过经验风险极小化确定下一棵决策树的参数，

下面讨论针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括平方误差损失函数的回归问题，用指数函数的分类问题，以及用一般损失函数的一般决策问题。

分类问题

将GBDT应用于回归问题，相对来说比较容易理解。因为回归问题的损失函数一般为平方差损失函数，这时的残差，恰好等于预测值与实际值之间的差值。每次拿一棵决策树去拟合这个差值，使得残差越来越小，这个过程还是比较intuitive的。而将GBDT用于分类问题，则显得不那么显而易见。

在说明分类之前，我们先介绍一种损失函数。与常见的直接求预测与真实值的偏差不同，这种损失函数的目的是最大化预测值为真实值的概率。这种损失函数叫做对数损失函数（Log-Likehood Loss），定义如下

对于二项分布，，我们定义预测概率为，即二项分布的概率，可得

即，可以合并写成

即

对于与的关系，我们定义为

二分类

类似于逻辑回归、FM模型用于分类问题，其实是在用一个线性模型或者包含交叉项的非线性模型，去拟合所谓的对数几率。而GBDT也是一样，只是用一系列的梯度提升树去拟合这个对数几率，实际上最终得到的是一系列CART回归树。其分类模型可以表达为：

其中，就是学习到的决策树。

清楚了这一点之后，我们便可以参考逻辑回归，单样本的损失函数可以表达为交叉熵：

假设第步迭代之后当前学习器为，将的表达式带入之后，损失函数写为：

可以求得损失函数相对于当前学习器的负梯度为：

可以看到，同回归问题很类似，下一棵决策树的训练样本为：，其所需要拟合的残差为真实标签与预测概率之差。于是便有下面GBDT应用于二分类的算法：

• ，其中是训练样本中的比例，利用先验信息来初始化学习器
• ：
  • 计算，并使用训练集训练一棵回归树，其中
  • 通过最小化损失函数找树的最优权重：
  • 考虑shrinkage，可得这一轮迭代之后的学习器，为学习率
• 得到最终学习器：

多分类

模仿上面两类分类的损失函数，我们能够将类分类的损失函数定义为

其中，，且将与关系定义为

或者，换一种表达方式

即，对于多分类问题，则需要考虑以下softmax模型：

其中是个不同的tree ensemble。每一轮的训练实际上是训练了棵树去拟合softmax的每一个分支模型的负梯度。可见，这棵树同样是拟合了样本的真实标签与预测概率之差，与二分类的过程非常类似。

回归问题

已知一个训练数据集，为输入空间，，为输出空间。如果将输入空间划分为个互不相交的区域，并且在每个区域上确定输出的常量，那么树可表示为

其中，参数表示树的区域划分和各区域上的常数。是回归树的复杂度即叶结点个数。

回归问题提升树使用以下前向分布算法：

在前向分步算法的第步，给定当前模型，需求解

得到，即第颗树的参数。当采用平方误差损失函数时，

其损失变为

这里，即当前模型拟合数据的残差。所以，对回归问题的提升树算法来说，只需简单地拟合当前模型的残差。

回归问题的提升树算法

输入：训练数据集

输出：提升树

（1）初始化

（2）对

• （a）按计算残差
• （b）拟合残差学习一个回归树，得到
• （c）更新

（3）得到回归提升树：

举例如下

对于：

求即回归树，首先通过以下优化问题：

求解训练数据的切分点：

容易求得在，内部使平方损失误差达到最小值的，为

这里，是，的样本点数

求训练数据的切分点。根据所给数据，考虑如下切分点：1.5，2.5，3.5，4.5，6.5，7.5，8.5，9.5

对各切分点，求相应的及

例如，当时，，，，，

现将及的计算结果列表如下

由上表可知，当时达到最小值，此时，，，，所以回归树为

用拟合训练数据的残差

用拟合训练数据的平均损失误差：

对于：

求，方法与求一样，只是拟合的数据为上一步的残差。可以得到

用拟合训练数据的平方损失误差是：

对于：

继续按上述方法计算，直至求得拟合训练数据的平方误差到可接受范围。

梯度提升

提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，梯度提升算法利用最速下降法的近似方法，其核心是利用损失函数的负梯度在当前模型的值

作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

输入：训练数据集，损失函数

输出：回归树

（1）初始化：

（2）对

• （a）对，计算
• 
• （b）对拟合一个回归树，得到第棵树的叶结点区域
• （c）对，计算
• 
• （d）更新

（3）得到回归树：

算法第（1）步初始化，估计使损失函数极小化的常数值，它是只有一个根节点的数。

第（2a）步计算损失函数的负梯度在当前模型的值，将它作为残差的估计。对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。

第（2b）步估计回归树叶结点区域，以拟合残差的近似值。

第（2c）步利用线性搜索估计叶结点区域的值，是损失函数极小化。

第（2d）步更新回归树

第（3）步得到输出的最终模型。

Source

https://zhuanlan.zhihu.com/p/46445201
https://zhuanlan.zhihu.com/p/25257856