GBDT - MLLearning

GBDT 的基本原理是什么？

GBDT（Gradient Boosting Decision Tree），即梯度提升决策树，属于 Boosting 算法家族的一部分，是一种在机器学习领域中常用的算法。

Boosting 采用加法模型（基分类器的线性组合）与前向分布算法，将多个弱分类器集成为一个强分类器

在了解 GBDT 之前，我们先来了解一下什么是提升树算法，提升树算法是以分类树或回归树作为基分类器的提升算法，提升树算法就是 AdaBoost 算法中基分类器选取决策树得到的算法。它表示为

\[f_M(x) = \sum_{m=1}^{M} T(x; \Theta_m)\]

其中 $T(x; \Theta_m)$ 表示决策树, $\Theta_m$ 为模型的参数，M 为模型的个数。

提升树采用前向分布算法，先初始化提升树 $f_0(x)=0$，假设第 m-1 步的模型为 $f_{m-1}(x)$，则下一步的模型为

\[f_m(x) = f_{m-1}(x) + T(x; \Theta_m)\]

aaa

极小化损失函数

\[\hat{\Theta}_m = \arg\min_{\Theta_m} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + T(x_i; \Theta_m))\]

可以得到第 m 棵树的参数 $\hat{\Theta}_m$

不同问题对应着不同的损失函数，比如分类问题常用指数损失函数 $L(y, f(x)) = \exp(-yf(x))$，回归问题常用平方损失函数 $L(y, f(x)) = (y - f(x))^2$

以平方损失函数为例，损失函数为 $L(y_i, f_{m-1}(x_i) + T(x_i; \Theta_m)) = [y - f_{m-1}(x) - T(x; \Theta_n)]^2 = [r - T(x; \Theta_n)]^2$ ，其中 $r = y - f_{m-1}(x)$，是当前模型拟合数据的残差。所以，对于回归问题的提升树算法来说，只需简单地拟合当前模型的残差。

GBDT(梯度提升决策树)

GBDT 与提升树类似，模型依旧为加法模型、学习算法为前向分步算法。不同的是，GBDT 没有规定损失函数的类型，设损失函数为 $L(y, f(x))$。

当损失函数是平方误差损失函数和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，Freidman 提出了梯度提升（gradient boosting）算法。Gradient Boosting 是 Boosting 中的一大类算法，它的思想借鉴于梯度下降法，其基本原理是根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有模型中。采用决策树作为弱分类器的 Gradient Boosting 算法被称为 GBDT。

目前 GBDT 有两个不同的描述版本，网上写 GBDT 的大都没有说清楚自己说的是哪个版本，以及不同版本之间的不同是什么，读者看不同的介绍会得到不同的算法描述，实在让人很头痛。

残差版本把 GBDT 说成一个残差迭代树，认为每一棵回归树都在学习前 N-1 棵树的残差。其实残差版本就是损失函数为平方误差的梯度版本。
Gradient 版本把 GBDT 说成一个梯度迭代树，使用梯度下降法求解，认为每一棵回归树在学习前 N-1 棵树的梯度下降值。

GBDT（残差）回归算法

己知一个训练数据集 $T = \{ (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) \}, \quad x_i \in X \subseteq \mathbb{R}^n$，$X$ 为输入空间，$y_i \in Y \subseteq \mathbb{R}$，$Y$为输出空间。在决策树章节中已经讨论了回归树问题。如果将输入空间 $X$ 划分为 $J$ 个互不相交的区域 $R_1, R_2,\ldots, R_J$，并且在每个区域上确定输出的常量 $c_i$，那么树可表示为

\[T(x; \Theta) = \sum_{j=1}^{J} c_j \cdot I(x \in R_j)\]

其中，参数 $ \Theta = { (R_1, c_1), (R_2, c_2), \ldots, (R_J, c_J) } $ 表示树的区域划分和各区域上的常数，$J$ 是回归树的复杂度，即叶节点的个数。

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

\[f_0(x) = 0\]

\[f_m(x) = f_{m-1}(x) + T(x; \Theta_m), \quad m = 1, 2, \ldots, M\]

\[f_M(x) = \sum_{m=1}^{M} T(x; \Theta_m)\]

在前向分步算法的第 m 步，给定当前模型 $f_{m−1}(x)$，需求解

\[\hat{\Theta}_m = \arg \min_{\Theta_m} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + T(x_i; \Theta_m))\]

得到 $\hat{\Theta}_m $，即第 m 颗决策树的参数。

当采用平方误差损失函数时，

\[L(y, f(x)) = (y - f(x))^2\]

其损失变为：

\[L(y, f_{m-1}(x) + T(x; \Theta_m)) = [y - f_{m-1}(x) - T(x; \Theta_m)]^2 = [r - T(x; \Theta_m)]^2\]

这里，

\[r = y - f_{m-1}(x)\]

是当前模型拟合数据的残差。

为了使损失函数 $L$ 的值最小，对 $L$ 关于其中唯一的未知变量 $T(x; \Theta_m)$ 求偏导,（$f_{m−1}(x)$ 已经是已知的定值了），并令其等于0，即可得使得损失函数 $L$ 最小的回归树 $T(x; \Theta_m)$。具体步骤如下：

\[\frac{\partial L(y, f_{m-1}(x) + T(x; \Theta_m))}{\partial T(x; \Theta)} = \frac{\partial [r - T(x; \Theta_m)]^2}{\partial T(x; \Theta)} = 2[T(x; \Theta_m) - r] = 0\]

可得

\[T(x; \Theta_m) = r\]

所以，对于回归问题的梯度提升算法来说，只需要简单地拟合当前模型的残差。

现将回归问题的梯度提升树叙述如下。

输入：训练数据集 $T = \{ (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) \}, \quad x_i \in X \subseteq \mathbb{R}^n$，$y_i \in Y \subseteq \mathbb{R}$

输出：提升树$f_M(x)$

初始化 $f_0(x)=0$
对 $m=1,2,...,M$
计算残差

$\(r_{mi} = y_i - f_{m-1}(x_i), \quad i = 1, 2, \ldots, N$\)
拟合残差 $r_{mi}$ 学习一个回归树，得到 $T(x; \Theta_m)$
更新

$\(f_m(x) = f_{m-1}(x) + T(x; \Theta_m)$\)
得到回归问题提升树

$f_M(x) = \sum_{m=1}^{M} T(x; \Theta_m)$

aaa

GBDT（梯度）回归算法

输入：训练数据集 $T = \{ (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) \}, \quad x_i \in X \subseteq \mathbb{R}^n$，$y_i \in Y \subseteq \mathbb{R}$

输出：提升树 $\hat{f}_{M}(x)$

初始化

$\(f_0(x) = \arg \min_c \sum_{i=1}^{N} L(y_i, c)$\)

对 $m=1,2,...,M$
对 $i=1,2,...,N$ 计算

$\(r_{mi} = - \left[ \frac{\partial L(y, f(x_i))}{\partial f(x_i)} \right]_{f(x) = f_{m-1}(x)}$\)
对 $r_{mi}$ 拟合一个回归树，得到第 m 棵树的叶子节点区域 $R_{mj}，j=1,2,...,J$
对 $j=1,2,...,J$ 计算

$\(c_{mj} = \arg \min_c \sum_{x_i \in R_{mj}} L(y_i, f_{m-1}(x_i) + c)$\)
更新

$\(f_m = f_{m-1}(x) + \sum_{j=1}^{J} c_{mj} I(x \in R_{mj})$\)
得到回归树

$\(\hat{f}(x) = f_M(x) = \sum_{m=1}^{M} \sum_{j=1}^{J} c_{mj} I(x \in R_{mj})$\)

下面是使用 sklearn 实现 gbdt 的一个案例。

import matplotlib.pyplot as plt
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.metrics import mean_squared_error

# Create a synthetic regression dataset
X, y = make_regression(n_samples=1000, n_features=100, noise=0.1)

# Split the data into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Create Gradient Boosting Regressor model
gbdt = GradientBoostingRegressor(n_estimators=100, learning_rate=0.1, max_depth=3, random_state=42)

# Train the model
gbdt.fit(X_train, y_train)

# Make predictions
y_pred = gbdt.predict(X_test)

# Evaluate the model
mse = mean_squared_error(y_test, y_pred)
print(f"Mean Squared Error: {mse}")

# Plot actual vs predicted values
plt.figure(figsize=(10, 6))
plt.scatter(y_test, y_pred, alpha=0.5)
plt.plot([y.min(), y.max()], [y.min(), y.max()], 'k--', lw=4)
plt.xlabel('Actual')
plt.ylabel('Predicted')
plt.title('Actual vs. Predicted Values')
plt.show()

GBDT 需要特征归一化吗？

梯度提升决策树（GBDT）通常不需要特征归一化。GBDT 和其他基于树的算法（如随机森林和传统决策树）主要依赖于数据的排序顺序来进行决策，而不是其具体数值。由于这些算法在构建决策树时，是通过选择最佳切分点来区分数据，因此它们对特征的尺度并不敏感。

GBDT 如何实现正则化？

GBDT的正则化主要有四种方式。

第一种 Shrinkage

这是一种正则化（regularization）方法，为了防止过拟合，在每次对残差估计进行迭代时，不直接加上当前步所拟合的残差，而是乘以一个系数 ν 。系数 ν 也被称为学习率（learning rate），因为它可以对梯度提升的步长进行调整，也就是它可以影响我们设置的回归树个数。对于前面的弱学习器的迭代

$\(f_k(x) = f_{k-1}(x) + h_k(x)$\)

如果我们加上了正则化项，则有

$\(f_k(x) = f_{k-1}(x) + \nu \cdot h_k(x)$\)

v 的取值范围为 0< v ≤1 ，对于同样的训练集学习效果，较小的 v 意味着需要更多的弱学习器的迭代次数。通常用步长和迭代最大次数一起来决定算法的拟合效果。

第二种正则化的方式是通过子采样比例，取值为 (0,1]。

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

使用了子采样的 GBDT 有时也称作随机梯度提升树 (Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做 boosting 的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。

第三种是对于弱学习器即CART回归树进行正则化剪枝。
第四种方式是 Early Stopping，Early Stopping 是机器学习迭代式训练模型中很常见的防止过拟合技巧，具体的做法是选择一部分样本作为验证集，在迭代拟合训练集的过程中，如果模型在验证集里错误率不再下降，就停止训练，也就是说控制迭代的轮数（树的个数）。在sklearn的GBDT中可以设置参数n_iter_no_change实现early stopping。

aaa

GBDT 回归任务常见的损失函数有哪些？

对于 GBDT 回归模型，sklearn 中实现了四种损失函数，有均方差 ls，绝对损失 lad，Huber 损失 huber 和分位数损失 quantile。默认是均方差 ls。一般来说，如果数据的噪音点不多，用默认的均方差 ls 比较好。如果是噪音点较多，则推荐用抗噪音的损失函数 huber。而如果我们需要对训练集进行分段预测的时候，则采用 quantile。

均方差，这个是最常见的回归损失函数了，公式如下

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

对应的负梯度误差为

$\(y_i - f(x_i)$\)

绝对损失，这个损失函数也很常见，公式如下

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

对应的负梯度误差为

$\(\text{sign}(y_i - f(x_i))$\)

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

损失函数如下：

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

对应的负梯度误差为：

$\(r(y_i, f(x_i)) = \begin{cases} y_i - f(x_i) & \text{for } |y_i - f(x_i)| \le \delta, \\ \delta \cdot \text{sign}(y_i - f(x_i)) & \text{for } |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)|$\)

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

$\(r(y_i, f(x_i)) = \begin{cases} \theta & \text{for } y_i \ge f(x_i), \\ \theta - 1 & \text{for } y_i < f(x_i) \end{cases}$\)

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

在 GBDT 中，特征重要性是如何计算的？

树模型相对于神经网络的一个重要优点就是计算每个 input 对 output 的权重比较方便。

特征 j 的全局重要度通过特征 j 在单颗树中的重要度的平均值来衡量：

\[\hat{J}^2_j = \frac{1}{M} \sum_{m=1}^M \hat{J}^2_j(T_m)\]

其中，M 是树的数量。特征 j 在单颗树中的重要度的如下

\[\hat{J}^2_j(T) = \sum_{t=1}^{L-1} \hat{i}^2_t \mathbb{1}(v_t = j)\]

其中，L 为树的叶子节点数量，L−1 即为树的非叶子节点数量（构建的树都是具有左右孩子的二叉树），$v_t$ 是和节点 t 相关联的特征，$\hat{i}^2_t \(是节点 t 分裂之后平方损失的减少值。比如分裂之前该节点里有 100 个数据点，MSE为1；分裂后分成两个节点，一个里面有 30 个数据点，MSE为 0.9，另一个里面有 70 个数据点，MSE为 0.8，那么考虑上加权，$\hat{i}^2_t\) 就等于 (100∗1−30∗0.9−70∗0.8)/100 = 0.17；这个数值越大，说明这个节点降低 loss 的能力越大。

为更好理解，给出sklearn中的代码。

def feature_importances_(self):
    total_sum = np.zeros((self.n_features, ), dtype=np.float64)
    for tree in self.estimators_:
        total_sum += tree.feature_importances_ 
    importances = total_sum / len(self.estimators_)
    return importances

其中，self.estimators_ 是算法构建出的决策树的棵树，tree.feature_importances_ 是单棵树的特征重要度向量，其计算方法如下：

def compute_feature_importances(self, normalize=True):
    """Computes the importance of each feature (aka variable)."""

    while node != end_node:
        if node.left_child != _TREE_LEAF:
            # ... and node.right_child != _TREE_LEAF:
            left = &nodes[node.left_child]
            right = &nodes[node.right_child]

            importance_data[node.feature] += (
                node.weighted_n_node_samples * node.impurity -
                left.weighted_n_node_samples * left.impurity -
                right.weighted_n_node_samples * right.impurity)
        node += 1

    importances /= nodes[0].weighted_n_node_samples

    return importances

上面的代码经过了简化，保留了核心思想。计算所有的非叶子节点在分裂时加权不纯度的减少，减少得越多说明特征越重要。

不纯度的分类有很多，对于回归问题，impurity(不纯度) 可以是类似 MSE 这样的损失函数；对于分类问题，impurity(不纯度)可以是gini值。weighted_n_node_samples 就是各个节点的加权样本数，最后除以根节点 nodes[0].weighted_n_node_samples 的总样本数。

AdaBoost 与 GBDT 对比有什么不同？

AdaBoost（Adaptive Boosting）和 GBDT（Gradient Boosting Decision Tree）都是集成学习算法中的 boosting 方法。不同的是，AdaBoost 是通过调整错分数据点的权重来改进模型，GBDT是通过计算负梯度来改进模型。因此，相比AdaBoost, GBDT 可以使用更多种类的目标函数，而当目标函数是均方误差时，计算损失函数的负梯度值就是前一个模型的残差。

GBDT 算法优缺点？

GBDT 主要的优点有：

GBDT 是拿 Decision Tree 作为 GBM 里的弱分类器，GBDT 的优势首先得益于 Decision Tree 本身的一些良好特性，具体可以列举如下：
Decision Tree 可以很好的处理缺失值
Decision Tree 可以很好的处理各种类型的特征
数据规模影响不大，因为我们对弱分类器的要求不高，作为弱分类器的决策树的深度一般设的比较小，即使是大数据量，也可以方便处理。
可以灵活处理各种类型的数据，包括连续值和离散值
在相对少的调参时间情况下，预测的准确率也可以比较高。
GBM 在损失函数的选择上有更大的灵活性
使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和 Quantile损失函数

GBDT的主要缺点有

由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的 SGBT 来达到部分并行。

aaa

Keys	Action
`?`	Open this help
`n`	Next page
`p`	Previous page
`s`	Search