GBDT、Xgboost和LightGBM

1. 什么是GBDT

GBDT又叫梯度提升树，使用CART决策树作为基学习器，利用Boosting的集成思想训练模型。与AdaBoost不同，每轮学习GBDT不会根据训练结果调整样本权重，而是希望求得一个学习器$h_m$使得目标函数达到最小，即：

$$h_m=arg\min_{h_m}\sum_i L(y_i,F_{m-1}(x_i)+h_m(x_i))$$

已知$F_{m-1}$，则损失函数对$F_{m-1}$在各个样本的一阶梯度等于：

$$\frac{\partial L(y_i,F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}$$

我们知道一个函数关于一个变量的梯度，代表变量可以使得函数有最大上升的方向。而梯度的反方向则代表变量可以使得函数有最大下降的方向。所以要找到一个最佳$h_m$，可以使$h_m(x_i)$尽量接近$-\frac{\partial L(y_i,F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}$，即$h_m$尽量拟合损失函数的负梯度。这就是GBDT的算法思想。在其他博客经常能看到说GBDT的每棵决策树是拟合损失函数的残差，这是不准确的，拟合残差是因为损失函数是均方误差函数，均方误差的一阶梯度几乎等于残差。而实际上GBDT是使每棵决策树去拟合损失函数的负梯度使得损失函数每次都能往降低的方向发展。

当GBDT用于分类任务时，使用交叉熵损失函数，每个叶子节点输出一个向量。叶子节点输出向量等于在该叶子节点样本的向量的平均值。每个样本的输出向量经过softmax函数得到样本的输出分布，表示样本属于各个类别的概率，损失函数使用交叉熵损失函数。使用GBDT求解时，利用损失函数对各个样本求出向量的负梯度，使用这个负梯度作为下一棵树对该样本的学习目标。初始时，每个样本的向量可以设置为零向量。

2. 如何求解GBDT

(1) 使用CART决策树训练数据，得到第一个基学习器$h_1$
(2) 在训练样本上计算损失函数与预测结果的负梯度，使用负梯度更新样本的学习目标
(3) 继续使用CART决策树训练数据，得到第二个基学习器$h_2$
(4) 在训练样本上计算损失函数与两个学习器求和后的预测结果的负梯度，使用负梯度更新样本的学习目标
(5) 重复(3)(4)步骤，直到达到训练结束条件
(6) 将各个学习器的预测结果求和，有时可以将各个学习器的预测结果乘上一个系数，这个系数表示学习率

3. 什么是Xgboost

Xgboost使用下式作为目标函数：

$$Obj = \sum_iL(y_i,F_{m-1}(x_i)+f_m(x_i))+\Omega(F_{m-1})+\Omega(f_m)$$

其中$\Omega$表示正则项，一般而言有下式：

$$\Omega(f)=\gamma T + \frac{1}{2}\lambda\lVert\omega\rVert^2$$

其中$T$表示决策树集合$f$的叶子节点数，而$\omega$表示叶子节点的输出。将目标函数进行泰勒展开并近似到二阶项有：

$$Obj\approx\sum_i\{L(y_i,F_{m-1}(x_i))+\frac{\partial L(y_i,F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}f_m(x_i)+\frac{1}{2}\frac{\partial^2L(y_i,F_{m-1}(x_i))}{\partial F_{m-1}(x_i)^2}f_m(x_i)^2\} \\ +\Omega(F_{m-1})+\Omega(f_m)$$

用$g_i$表示一阶导数，$h_i$表示二阶导数，将常数项$L(y_i,F_{m-1}(x_i))$与$\Omega(F_{m-1})$并入$C$，展开$\Omega(f_m)$，则有：

$$Obj\approx\sum_i\{g_if_m(x_i)+\frac{1}{2}(h_i+\lambda)f_m(x_i)^2\}+C+\gamma T$$

已知$f_m$是一棵决策树，且有$T$个叶子节点，第$t$个叶子节点的权重为$w_t$，则上式可以变为：

$$Obj\approx\sum_t\{w_t\sum_ig_iI(x_i\in S_t)+\frac{1}{2}w_t^2\sum_i(h_i+\lambda)I(x_i\in S_t)+\gamma\}+C$$

其中$S_t$表示样本进入决策树第$t$号节点的集合。使用目标函数对$w_t$求导并令导数为0，可以得到：

$$w_t=-\frac{\sum_{x_i\in S_t}g_i}{\sum_{x_i\in S_t}(h_i+\lambda)}$$

也就是说对于一个叶节点，这个叶节点的权值$w_t$是由到达该节点的样本的$g_i$和$h_i$决定的。以前的决策树一般都会使用样本目标的平均数或众数来决定叶节点的权值，这是Xgboost和这些决策树不同的一个地方。将上式结果代入目标函数最终可以得到：

$$Obj\approx-\frac{1}{2}\sum_t\frac{(\sum_{x_i\in S_t}g_i)^2}{\sum_{x_i\in S_t}(h_i+\lambda)}+\gamma T+C$$

以前的决策树会使用信息增益，信息增益率和基尼系数来决定选择一个特征和特征值展开决策树，Xgboost直接使用目标函数，每次会选择一个使目标函数达到最小的特征和特征值展开决策树，具体步骤如下：
(1) 选择一个特征和特征值
(2) 计算以该特征值展开决策树后新的叶子节点的权重$w_t$
(3) 将$w_t$代入目标函数，计算目标函数值
(4) 选择使目标函数最小的特征和特征值展开决策树

4. 如何求解Xgboost

(1) 使用训练样本学习第一棵决策树$f_1$
(2) 计算损失函数关于$f_1$的输出的一阶导数和二阶导数
(3) 根据一阶导数和二阶导数，使用训练样本学习第二棵决策树$f_2$
(4) 计算损失函数关于$f_1+f_2$的输出的一阶导数和二阶导数
(5) 根据一阶导数和二阶导数，使用训练样本学习第三棵决策树$f_3$
(6) 重复上面的步骤，直到到达训练结束条件，对于第$i$棵决策树，可以给其乘上一个系数$\alpha_i$调整其输出影响

5. 其他

(1) Xgboost可以实现并行运算，提升效率。这里的并行运算是指在特征选择时的并行运算，可以加快算出最佳分割点。
(2) Xgboost可以处理特征缺失值，对于缺失值，将其放置可以使得目标函数最小的一边。
(3) Xgboost在计算特征重要性时，有几种方法，一般是计算使用这种特征分割的平均增益，增益可以是损失函数的降低程度，也可以是基尼系数，也可以是信息熵增益，还可以是多种指标的组合。有一种简单的方法是统计使用这种特征进行分割的次数。

6. LightGBM

LightGBM在Xgboost之上添加了许多新的特性，可以减少资源占用与增加运算效率。主要可总结为三点：直方图离散化特征统计，按叶子扩展策略，直接处理类别特征。