GBDT算法梳理

前向分步算法

加法模型

$$f(x) = \sum_{m=-1}^M\beta_mb(x;\gamma_m)$$

上述公式其实就是基函数的一种线性组合，其中：

• $b(x;\gamma_m)$ 为基函数
• $\gamma_m$ 为基函数的参数
• $\beta_m​$ 为基函数的系数

不同问题的提升树学习算法，其主要区别在于损失函数不同。平方损失函数常用于回归问题，用指数损失函数用于分类问题，以及绝对损失函数用于决策问题。

在给定训练数据以及损失函数 $L(y,f(x))$ 的条件下，上述模型学习问题转化为求损失函数极小值得优化问题：

$$min_{\beta_m,\gamma_m}\sum_{m=1}^ML(y_i, \sum_{m=1}^M\beta_mb(x_i;y_m))$$

若直接求解上述问题是非常困难的，因为需要同时求解 $m=1,\dots,M$ 个参数。

前向分步算法的求解思路：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，所以，前向分布算法每一步的优化目标为：

$$min_{β,γ}\sum_{i=1}^NL(y_i,\beta b(x;y))$$

每次仅仅只学习一个基函数及其系数。

　前向分步算法

输入：

• 训练数据集：$D=((x_1,y_1),(x_2,y_2),\dots,(x_N,y_N))$
• 损失函数：$L(y,f(x))$
• 基函数集：$b(x;\gamma)$

输出：

• 加法模型：$f(x)$

具体流程如下：

1. 初始化 $f_o(x) = 0$
2. 对 $m=1,2,\dots,M$

• 极小化损失函数：

  $$(\beta_m,\gamma_m) = argmin_{\beta,\gamma}\sum_{i=1}^NL(y_i,f_{m-1}(x_i) + \beta b(x_i;\gamma))$$

  ​ 得到参数 $\beta_m,\gamma_m$。

• 更新：

  $$f_m(x)=f_{m-1}(x) + \beta_mb(x;\gamma_m)$$

1. 得到加法模型： $$f(x) = f_M(x)=\sum_{m=1}^M \beta_m b(x;\gamma_m)$$

这样，前向分步算法将同时求解从 $m=1$ 到 $m=M$ 所有参数 $\beta_m,\gamma_m$ 的优化问题简化为逐次求解 $\beta_m,\gamma_m$ 的优化问题。

负梯度拟合

提升树算法

提升方法实际采用加法模型与前向分步算法，以决策树作为基函数的提升方法称为提升树。注意，这里的决策树为CART回归树，不是分类树。当问题是分类问题时，采用的决策树模型为分类回归树。

提升树模型可表示为：

$$f_M(x) = \sum_{m=1}^MT(x;\theta_m)$$

其中，

• $T(x,\theta_m)$ 表示决策树
• $\theta_m$ 为决策树参数
• $M$ 为树的个数

不同的问题下，提升树算法的具体形式也不尽相同，主要区别在于损失函数不同。损失函数决定了决策树要拟合的值。一般情况，对于回归问题的提升树算法来说，损失函数为平方损失函数。

下面以平方损失函数为例，阐述算法流程：

输入：

• 训练数据集 $T=\{ (x_1,y_1),(x_2,y_2),…,(x_N,y_N) \}$
• $x_i\in \chi \subseteq\mathcal{R}^n,y_i\in\gamma\subseteq\mathcal{R}$

输出：

• 提升树 $f_M(x)​$

具体流程如下：

1. 初始化 $f_o(x) = 0$
2. 对 $m=1,2,\dots,M$

• 计算残差 $$r_{mi} = y_i - f_{m-1}(x_i), \\ i = 1,2,...,N$$
• 拟合残差 $r_{mi}$，学习一个回归树 $T(x;\theta_m)$
• 更新 $ f_m(x) = f_{m-1}(x) + T(x;\theta_m)$

1. 得到回归问题提升树 $$f(x) = f_M(x)=\sum_{m=1}^MT(x;\theta_m)$$

梯度提升

提升树用加法模型与前向分布算法实现学习的优化过程，当损失函数为平方损失函数和指数损失函数时，优化问题较简单。而对于一般的损失函数并不容易，这时候一般利用梯度下降来进行优化，一般用负梯度拟合：

$$-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)}=f_{m-1}(x)$$

回归

梯度提升算法在回归问题上的流程：

输入：

• 训练数据集：$D=((x_1,y_1),(x_2,y_2),\dots,(x_N,y_N))$
• $x_i\in \chi \subseteq\mathcal{R}^n,y_i\in\gamma\subseteq\mathcal{R}$
• 损失函数：$L(y,f(x))$

输出：

• 回归树：$\widetilde{f}(x)$

具体流程如下：

1. 初始化 $f_o=argmin_c\sum_{i=1}^NL(y_i,c)$

• 对 $i=1,2,\dots,N$ 计算 $$r_{mi} =-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)}=f_{m-1}(x)$$
• 对 $r_{mi}$ 拟合一个回归树，得到第m颗树的叶结点区域 $R_{mj},j=1,2,\dots,J$
• 对于 $j=1,2,\dots,J$ 计算： $$c_{mj}=argmin_c\sum_{x_j\in \mathcal{R}_{mj}}L(y_i, f_{m-1}(x_i)+c)$$
• 更新 $$f_m(x) = f_{m-1}(x) + \sum_{j=1}^Jc_{mj}I(x\in \mathcal{R}_{mj})$$

1. 得到回归树 $$\widetilde{f}(x) = f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in \mathcal{R}_{mj})$$

分类

GBDT的分类算法从思想上和GBDT的回归算法没有本质区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。

为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为AdaBoost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。

二分类

对于二分类GBDT，如果用类似逻辑回归的对数似然损失函数，则损失函数为：

$$L(y,f(x)) = log(1 + e^{-yf(x)})；y\in \{-1,1\}$$

此时的负梯度误差为：

$$r_{ti} = \frac{y_i}{1 + e^{y_if(x_i)}}$$

多分类

多分类GBDT比二分类GBDT复杂些，对应的是多元逻辑回归和二元逻辑回归的复杂度差别。假设类别数为 $K$，则此时我们的对数似然损失函数为：

$$L(y,f(x)) = -\sum_{k=1}^Ky_klog(p_k(x))$$

若输出类别为 $k$，则 $y_k=1，第 $k$ 类的概率 $P_k(x)$ 的表达式为：

$$P_k(x) = \frac{e^{f_k(x)}}{\sum_{l=1}^Ke^{f_i(x)}}$$

集合上两式，我们可以计算出第t轮的第i个样本对应类别l的负梯度误差为：

$$t_{til} = [\frac{\partial L(y_if(x_i))}{\partial f(x_i)}]_{f_k(x) = f_{l,t-1}(x)} = y_{il} - p_{l,t-1}(x_i)$$

常用损失函数

分类算法

其损失函数一般有对数损失函数和指数损失函数两种:

• 如果是指数损失函数，则损失函数表达式为 $$L(y,f(x))=e^{−yf(x)}$$ 其负梯度计算和叶子节点的最佳负梯度拟合和AdaBoost原理相同。
• 如果是对数损失函数，分为二元分类和多元分类两种，见上文。

回归算法

常用损失函数有如下4种:

均方差损失函数

$$L(y,f(x)) = (y-f(x))^2$$

绝对损失函数

$$L(y,f(x)) = |y-f(x)|$$

对应负梯度误差为：

$$sign(y_i−f(x_i))$$

Huber损失函数

均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。损失函数如下：

$$L(y,f(x)) = \begin{cases} \frac{1}{2}(y-f(x))^2, & |y-f(x)|\le \delta \\[5ex] \delta(|y-f(x)|-\frac{\delta}{2}), & |y-f(x)|> \delta \end{cases}$$

对应的负梯度误差为：

$$r(y_i,f(x_i)) = \begin{cases} y_i - f(x_i), & |y_i-f(x_i)|\le \delta \\[5ex] \delta sign(y_i-f(x_i)), & |y_i-f(x_i)| > \delta \end{cases}$$

分位数损失函数

$$L(y,f(x)) = \sum_{y\ge f(x)}\theta|y-f(x)| + \sum_{y<f(x)}(1-\theta)|y-f(x)|$$

其中θ为分位数，需要在回归前指定。对应的负梯度误差为：

$$r(y_i,f(x_i)) = \begin{cases} \theta, & y_i \ge f(x_i) \\[5ex] \theta -1, & y_i<f(x_i) \end{cases}$$

对于Huber损失和分位数损失，主要用于健壮回归，也就是减少异常点对损失函数的影响。

正则化

三种方法：

• 第一种是和AdaBoost类似的正则化项，即步长(learning rate)。

  定义为 $\eta$，对于前面的弱学习器的迭代：$f_k(x)=f_{k-1}(x)+h_k(x)$。如果我们加上正则化项，则有 $f_k(x)=f_{k-1}(x)+\eta h_k(x)$，$\eta$ 的取值范围为 $0<\eta\le1$。对于同样的训练集学习效果，较小的 $\eta$ 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

• 第二种正则化的方式是通过子采样比例（subsample）。取值为 $(0,1]​$。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在 $[0.5, 0.8]​$ 之间。

• 第三种是对于弱学习器即CART回归树进行正则化剪枝。

优缺点

优点：

• 可以处理连续值和离散值
• 较小调参的情况下效果也比较好
• 对异常值有较好的鲁棒性

缺点：

• 弱学习器之间有较强依耐性，难以并行训练。

sklearn参数

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’, validation_fraction=0.1, n_iter_no_change=None, tol=0.0001)[source]

参数说明：

• n_estimators：弱学习器的最大迭代次数，也就是最大弱学习器的个数。
• learning_rate：步长，即每个学习器的权重缩减系数a，属于GBDT正则化方化手段之一。
• subsample：子采样，取值(0,1]。决定是否对原始数据集进行采样以及采样的比例，也是GBDT正则化手段之一。
• init：我们初始化的时候的弱学习器。若不设置，则使用默认的。
• loss：损失函数，可选{‘ls’-平方损失函数，‘lad’绝对损失函数-,‘huber’-huber损失函数,‘quantile’-分位数损失函数}，默认’ls’。
• alpha：当我们在使用Huber损失”Huber”和分位数损失”quantile”时，需要指定相应的值。默认是0.9，若噪声点比较多，可适当降低这个分位数值。
• criterion：决策树节搜索最优分割点的准则，默认是”friedman_mse”，可选”mse”-均方误差与’mae”-绝对误差。
• max_features：划分时考虑的最大特征数，就是特征抽样的意思，默认考虑全部特征。
• max_depth：树的最大深度。
• min_samples_split：内部节点再划分所需最小样本数。
• min_samples_leaf：叶子节点最少样本数。
• max_leaf_nodes：最大叶子节点数。
• min_impurity_split：节点划分最小不纯度。
• presort：是否预先对数据进行排序以加快最优分割点搜索的速度。默认是预先排序，若是稀疏数据，则不会预先排序，另外，稀疏数据不能设置为True。
• validationfraction：为提前停止而预留的验证数据比例。当n_iter_no_change设置时才能用。
• n_iter_no_change：当验证分数没有提高时，用于决定是否使用早期停止来终止训练。

应用场景

可用于所有回归问题（线性/非线性），相对LR仅能用于线性回归，GBDT的适用面非常广。亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。