GBDT

Posted on

GBDT

1. 提升树

提升树是以分类树或回归树为基本分类器的提升方法。

1.1. 提升树模型

提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法，以决策树为基函数的提升方法成为提升树（Boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。
提升树模型可以表示为决策树的加法模型： \[f_M(\pmb{x}) = \sum_{m=1}^M T(\pmb{x};\Theta_m)\] 其中，\(T(\pmb{x};\Theta_m)\)表示决策树；\(\Theta_m\)为决策树的参数，\(M\)为树的个数。

1.2. 提升树算法

提升树算法采用前向分步算法。首先确定初始提升树\(f_0(\pmb{x}) = 0\)，第\(m\)步的模型是 \[f_m(\pmb{x}) = f_{m-1}(\pmb{x}) + T(\pmb{x};\Theta_m)\] 其中，\(f_{m-1}(\pmb{x})\)为当前模型，通过经验风险最小化确定下一棵决策树的参数\(\Theta_m\)： \[\hat{\Theta}_m = \arg \min_{\Theta_m} \sum_{i=1}^N L(y_i,f_{m-1}(\pmb{x}_i)+T(\pmb{x}_i;\Theta_m))\] 由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。
针对不同问题的提升树学习算法，主要区别在于使用的损失函数不同：

  • 回归问题：平方误差损失函数；
  • 分类问题：指数损失函数；
  • 一般决策问题：一般损失函数。

（1）二类分类问题
对于二类分类问题，提升树算法只需将AdaBoost算法中的基本分类器限制为二类分类树即可，可以说这时的提升树算法是AdaBoost算法的特殊情况。

（2）回归问题
已知一个训练数据集\[T = \{(\pmb{x}_1,y_1),(\pmb{x}_2,y_2),\cdots,(\pmb{x}_N,y_N)\},\quad \pmb{x}_i \in \mathbf{R}^n, \quad y_i \in \mathbf{R}\]。如果将输入空间划分为\(J\)个互不相交的区域\(R_1,R_2,\cdots,R_J\)，并且在每个区域上确定输出的常量\(c_j\)，那么树可表示为 \[T(\pmb{x};\Theta) = \sum_{j=1}^J c_j I(\pmb{x} \in R_j)\] 其中，参数\(\Theta = \{(R_1,c_1),(R_2,c_2),\cdots,(R_J,c_J)\}\)表示树的区域划分和各区域上的常数，\(J\)是回归树的复杂度即叶节点个数。
回归问题提升树使用以下前向分步算法：
\[\begin{align} f_0(\pmb{x}) &= 0 \nonumber \\ f_m(\pmb{x}) &= f_{m-1}(\pmb{x}) + T(\pmb{x};\Theta_m), \quad m=1,2,\cdots,M \nonumber \\ f_M(\pmb{x}) &= \sum_{m=1}^M T(\pmb{x};\Theta_m) \nonumber \end{align}\] 在前向分步算法的第\(m\)步，给定当前模型\(f_{m-1}(\pmb{x})\)，需求解 \[\hat{\Theta}_m = \arg \min_{\Theta_m} \sum_{i=1}^N L(y_i,f_{m-1}(\pmb{x}_i)+T(\pmb{x}_i;\Theta_m))\] 得到\(\hat{\Theta}_m\)，即第\(m\)棵树的参数。
当采用平方误差损失函数时， \[L(y,f(\pmb{x})) = (y-f(\pmb{x}))^2\] 其损失变为 \[\begin{align} L(y,f_{m-1}(\pmb{x}) + T(\pmb{x};\Theta_m)) &= [y - f_{m-1}(\pmb{x}) - T(\pmb{x};\Theta_m)]^2 \nonumber \\ &= [r - T(\pmb{x};\Theta_m)]^2 \nonumber \end{align}\] 这里 \[r = y - f_{m-1}(\pmb{x})\] \(r\)是当前模型拟合数据的残差（residual）。所以，对于回归问题的提升树算法来说，只需要简单地拟合当前模型的残差。

2. GBDT

GBDT是Boosting家族中另一个重要的算法梯度提升树（Gradient Boosting Decision Tree，GBDT），又叫MART（Multiple Additive Regression Tree, MART），是一种迭代的决策树算法。在传统的AdaBoost算法中，我们利用弱学习器的误差率来更新训练集的权重，这样一步步迭代下去。GBDT也是迭代，使用了前向分步算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和AdaBoost也有所不同。

2.1. 梯度提升

提升树利用加法模型与前向分步算法实现学习的优化过程，当损失函数是平方损失和指数损失函数时，每一步的优化是很简单的。但对一般损失函数而言，如绝对值和Huber损失函数，往往每一步的优化并不那么容易，针对这一问题，Freidman提出了梯度提升（gradient boosting）算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值： \[-[\frac{\partial L(y,f(\pmb{x}_i))}{\partial f(\pmb{x}_i)}]_{f(\pmb{x}) = f_{m-1}(\pmb{x})}\] 用这个值作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

2.2. GBDT回归算法

算法第一步初始化，估计使损失函数极小化的常数值，它是只有一个根节点的树。第2（a）步计算损失函数的负梯度在当前模型的值，将它作为残差的估计。对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。第2（b）步估计回归树叶节点区域，以拟合残差的近似值。第2（c）步利用线性搜索估计叶节点区域的值，使损失函数极小化。第2（d）步更新回归树。第3步得到输出的最终模型\(\hat{f}(\pmb{x})\)。

2.3. GBDT分类算法

GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续值，而是离散的类别，导致无法直接从输出类别去拟合类别输出的误差。
为了解决这个问题，主要有两种方法：

  1. 用指数损失函数，此时GBDT退化为AdaBoost算法；
  2. 用类似于逻辑回归的对数似然损失函数的方法，用类别的预测概率值和真实概率值的差来拟合损失。

下面主要讨论用对数似然损失函数的GBDT分类，而对于对数似然损失函数，又有二元分类和多元分类的区别。

2.3.1. 二元GBDT分类算法

对于二元GBDT，如果用二元Logistic回归损失函数，则损失函数为 \[L(y,F) = \log (1 + \exp(-2 y F))\] 其中\(y \in \{-1,+1\}\)，并且 \[F(\pmb{x}) = \frac{1}{2} \log [\frac{P(y=1|\pmb{x})}{P(y=-1|\pmb{x})}]\] 此时的负梯度误差为 \[\tilde{y}_i = -[\frac{\partial L(y_i,F(\pmb{x}_i))}{\partial F(\pmb{x}_i)}]_{F(\pmb{x}) = F_{m-1}(\pmb{x})} = \frac{2y_i}{1+\exp(2 y_i F_{m-1}(\pmb{x}_i))}\] 对于生成的决策树，各个子节点的最佳残差拟合值为 \[\gamma_{lm} = \arg \min_{\gamma} \sum_{\pmb{x}_i \in R_{lm}} \log(1+\exp(-2y_i (F_{m-1}(\pmb{x})+\gamma)))\] 由于上式无法求得闭式解，所以根据Newton-Raphson方法求其近似解，得到 \[\gamma_{lm} = \frac{\sum_{\pmb{x}_i \in R_{lm}} \tilde{y}_i}{\sum_{\pmb{x}_i \in R_{lm}} |\tilde{y}_i| (2 - |\tilde{y}_i|)}\] 更新公式为 \[F_m(\pmb{x}) = F_{m-1}(\pmb{x}) + \gamma_{lm} 1(\pmb{x} \in R_{lm})\]

算法如下：

得到最终的强学习器\(F_M(\pmb{x})\)的预测值与对数几率相关，可转化为概率预测值： \[\begin{align} p_+(\pmb{x}) &= \hat{P}(y=1|\pmb{x}) = \frac{1}{1+\exp(-2 F_M(\pmb{x}))} \nonumber \\ p_-(\pmb{x}) &= \hat{P}(y=-1|\pmb{x}) = \frac{1}{1+\exp(2 F_M(\pmb{x}))} \nonumber \end{align}\]

可用如下公式进行分类： \[\hat{y}(\pmb{x}) = 2· 1[c(-1,1)p_+(\pmb{x}) > c(1,-1)p_-(\pmb{x})] - 1\] 其中\(c(\hat{y},y)\)是将真实标记\(y\)预测为\(\hat{y}\)的损失代价。

2.3.2. 多元GBDT分类算法

假设类别数为\(K\)，对应的损失函数为 \[L(\{y_k, F_k(\pmb{x})\}_1^K) = - \sum_{k=1}^K y_k \log p_k(\pmb{x})\] 其中，当类别为\(k\)时，\(y_k = 1 \in \{0,1\}\)，\(p_k(\pmb{x}) = P(y_k=1|\pmb{x})\)。
使用对称多元logistic转换，即 \[F_k(\pmb{x}) = \log p_k(\pmb{x}) - \frac{1}{K} \sum_{l=1}^K \log p_l (\pmb{x})\] 或者，等价于 \[p_k(\pmb{x}) = \frac{\exp(F_k(\pmb{x}))}{\sum_{l=1}^K \exp(F_l(\pmb{x}))}\] 此时负梯度误差为 \[\tilde{y}_{ik} = - [\frac{\partial L(\{y_{ij}, F_{ij}(\pmb{x}_i)\}_{j=1}^K)}{\partial F_k(\pmb{x}_i)}]_{\{F_j(\pmb{x}) = F_{j,m-1}(\pmb{x})\}_1^K} = y_{ik} - p_k(\pmb{x}_i)\] 根据对应的残差生成\(K\)棵决策树，每一棵决策树都是为了拟合对应的残差\(\{y_{ik} - p_k(\pmb{x}_i)\}_{i=1}^N\)。其中第\(k\)棵树的第\(l\)个子节点在第\(m\)轮对应划分的训练集区域为\(R_{klm}\)，最佳残差拟合值为 \[\gamma_{klm} = \arg \min_{\gamma} \sum_{\pmb{x}_i \in R_{klm}} \phi_k (y_{ik}, F_{k,m-1}(\pmb{x}_i)+ \gamma)\] 其中\(\phi_k = - y_k \log p_k(\pmb{x})\)，式中\(p_k(\pmb{x}) = \frac{\exp(F_k(\pmb{x}))}{\sum_{l=1}^K \exp(F_l(\pmb{x}))}\)。
由于上式无法求得闭式解，所以根据Newton-Raphson方法求其近似解，得到 \[\gamma_{klm} = \frac{K-1}{K} \frac{\sum_{\pmb{x}_i \in R_{klm}}\tilde{y}_{ik}}{\sum_{\pmb{x}_i \in R_{klm}} |\tilde{y}_{ik}|(1- |\tilde{y}_{ik}|)}\] 更新公式为 \[F_{km}(\pmb{x}) = F_{k,m-1}(\pmb{x}) + \gamma_{klm} 1(\pmb{x} \in R_{klm})\]

算法如下：

最终得到的强分类器\(\{F_{kM}(\pmb{x})\}_1^K\)可以通过公式\(p_k(\pmb{x}) = \frac{\exp(F_k(\pmb{x}))}{\sum_{l=1}^K \exp(F_l(\pmb{x}))}\)计算对应的概率\(\{p_{kM}(\pmb{x})\}_1^K\)，并可以用来进行分类 \[\hat{k}(\pmb{x}) = \arg \min_{1 \leq k \leq K} \sum_{k'=1}^K c(k,k')p_{k'M}(\pmb{x})\] 其中\(c(k,k')\)是将真实标记\(k'\)预测为\(k\)的损失代价，当\(K=2\)时，多元GBDT分类算法与二类GBDT分类算法相同。

3. sklearn使用

在sklearn中，有GradientBoostingClassifier和GradientBoostingRegressor分别用来分类和回归。

GradientBoostingClassifier：

1
class sklearn.ensemble.GradientBoostingClassifier(loss=’deviance’, learning_rate=0.1, n_estimators=100, subsample=1.0, criterion=’friedman_mse’, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_depth=3, min_impurity_decrease=0.0, min_impurity_split=None, init=None, random_state=None, max_features=None, verbose=0, max_leaf_nodes=None, warm_start=False, presort=’auto’)

GradientBoostingRegressor：

1
class sklearn.ensemble.GradientBoostingRegressor(loss=’ls’, learning_rate=0.1, n_estimators=100, subsample=1.0, criterion=’friedman_mse’, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_depth=3, min_impurity_decrease=0.0, min_impurity_split=None, init=None, random_state=None, max_features=None, alpha=0.9, verbose=0, max_leaf_nodes=None, warm_start=False, presort=’auto’)[source]

框架参数

弱分类器参数：即决策树参数

函数

属性