梯度提升决策树（GBDT）

概述

梯度提升决策树（Gradient Boosting Decision Tree，GBDT）是一种基于加法模型（Additive Model）和前向分步算法（Forward Stagewise Algorithm）的集成学习方法。通过迭代地训练决策树来逐步减少残差，GBDT在各种机器学习任务中取得了优异的表现。¹

---

1. 从加法模型到梯度提升

1.1 加法模型

给定输入特征 $\mathbf{x}\in {\mathbb{R}}^d$，GBDT使用 $M$ 个基学习器的加权和进行预测：

$$F_M(\mathbf{x})=\sum _{m=1}^M{\alpha }_m{h}_m(\mathbf{x})$$

其中：

• $h_m(\mathbf{x})$ 是第 $m$ 个基学习器（决策树）
• ${\alpha }_m$ 是对应的权重系数

1.2 前向分步算法

训练加法模型的目标是最小化经验风险：

$$\underset{F}{\min }\sum _{i=1}^{N}L(y_i,F({\mathbf{x}}_i))$$

前向分步算法通过逐步添加基学习器来近似求解：

$$F_m(\mathbf{x})=F_{m-1}(\mathbf{x})+{\alpha }_m{h}_m(\mathbf{x})$$

每一步只优化当前基学习器的参数：

$$({\alpha }_m,{\theta }_m)=\arg \underset{\alpha ,\theta }{\min }\sum _{i=1}^{N}L(y_i,F_{m-1}({\mathbf{x}}_i)+\alpha h_m({\mathbf{x}}_i;\theta ))$$

---

2. 梯度提升的核心思想

2.1 残差与负梯度

当使用平方损失 $L(y,F(\mathbf{x}))=\frac{1}{2}(y-F(\mathbf{x}){)}^2$ 时，目标函数对 $F(\mathbf{x})$ 的负梯度为：

$$-\frac{\partial L}{\partial F}=y-F(\mathbf{x})$$

这恰好是当前预测的残差。因此，GBDT在每一步拟合残差。

2.2 通用梯度下降视角

对于任意可微损失函数 $L(y,F(\mathbf{x}))$，梯度提升将函数空间中的优化问题转化为梯度下降：

$$F_m(\mathbf{x})=F_{m-1}(\mathbf{x})-{\rho }_m\cdot g_m(\mathbf{x})$$

其中：

• $g_m(\mathbf{x})={\left[\frac{\partial L(y_i,F({\mathbf{x}}_i))}{\partial F({\mathbf{x}}_i)}\right]}_{i=1}^N$ 是梯度向量
• ${\rho }_m$ 是步长

2.3 梯度提升算法框架

def gradient_boosting(X, y, n_estimators, loss_fn, lr=0.1):
    """
    梯度提升算法框架
    
    参数:
        X: 输入特征 (N, d)
        y: 目标值 (N,)
        n_estimators: 基学习器数量
        loss_fn: 损失函数
        lr: 学习率（收缩因子）
    
    返回:
        F: 最终模型
        trees: 基学习器列表
    """
    N = len(y)
    
    # 初始化：使用训练集的均值
    F_0 = np.mean(y)
    F = F_0
    trees = []
    
    for m in range(n_estimators):
        # Step 1: 计算负梯度（伪残差）
        residuals = -gradient(loss_fn, y, F)
        
        # Step 2: 训练基学习器拟合伪残差
        tree = train_decision_tree(X, residuals)
        
        # Step 3: 求解最优步长
        rho = find_optimal_step(F, tree, X, y, loss_fn)
        
        # Step 4: 更新模型
        F = F - lr * rho * tree.predict(X)
        trees.append((tree, rho))
    
    return EnsembleModel(F_0, trees, lr)

---

3. CART决策树基础

3.1 CART回归树

GBDT通常使用CART（Classification and Regression Tree）作为基学习器。对于回归任务，使用平方误差作为分裂准则：

对于节点 $m$ 的数据集合 $R_m$，分裂后左右子节点的平方误差为：

$$\sum _{i\in R_m}(y_i-{\bar{y}}_m{)}^2\to \underset{j,s}{\min }\left[\sum _{i\in R_m^L}(y_i-{\bar{y}}_m^L{)}^2+\sum _{i\in R_m^R}(y_i-{\bar{y}}_m^R{)}^2\right]$$

其中：

• $(j,s)$ 表示在特征 $j$ 上使用阈值 $s$ 进行分裂
• ${\bar{y}}_m$ 是节点 $m$ 的均值预测

3.2 叶子节点预测值

对于回归树，叶子节点的预测值是落在该叶子中样本的目标均值：

$$c_m=\frac{1}{|R_m|}\sum _{i\in R_m}{y}_i$$

3.3 手写回归树实现

import numpy as np
from sklearn.tree import DecisionTreeRegressor
 
class SimpleRegressionTree:
    """简化的CART回归树实现"""
    
    def __init__(self, max_depth=3, min_samples_leaf=5):
        self.max_depth = max_depth
        self.min_samples_leaf = min_samples_leaf
        self.tree = None
    
    def fit(self, X, y):
        self.tree = self._build_tree(X, y, depth=0)
        return self
    
    def _best_split(self, X, y):
        """寻找最优分裂"""
        best_mse = float('inf')
        best_j, best_s = None, None
        
        m, n = X.shape
        for j in range(n):
            # 对特征j的所有可能阈值进行遍历
            thresholds = np.unique(X[:, j])
            for s in thresholds:
                left_mask = X[:, j] <= s
                right_mask = ~left_mask
                
                if left_mask.sum() < self.min_samples_leaf or \
                   right_mask.sum() < self.min_samples_leaf:
                    continue
                
                # 计算分裂后的MSE
                mse_left = np.var(y[left_mask]) * left_mask.sum()
                mse_right = np.var(y[right_mask]) * right_mask.sum()
                mse = (mse_left + mse_right) / m
                
                if mse < best_mse:
                    best_mse = mse
                    best_j, best_s = j, s
        
        return best_j, best_s, best_mse
    
    def _build_tree(self, X, y, depth):
        """递归构建决策树"""
        # 停止条件
        if depth >= self.max_depth or len(y) < 2 * self.min_samples_leaf:
            return {'leaf': True, 'value': np.mean(y)}
        
        # 寻找最优分裂
        j, s, _ = self._best_split(X, y)
        
        if j is None:
            return {'leaf': True, 'value': np.mean(y)}
        
        # 分裂数据
        left_mask = X[:, j] <= s
        right_mask = ~left_mask
        
        return {
            'leaf': False,
            'feature': j,
            'threshold': s,
            'left': self._build_tree(X[left_mask], y[left_mask], depth + 1),
            'right': self._build_tree(X[right_mask], y[right_mask], depth + 1)
        }
    
    def predict(self, X):
        """预测"""
        return np.array([self._predict_single(x, self.tree) for x in X])
    
    def _predict_single(self, x, node):
        if node['leaf']:
            return node['value']
        if x[node['feature']] <= node['threshold']:
            return self._predict_single(x, node['left'])
        return self._predict_single(x, node['right'])

---

4. 分类任务的梯度提升

4.1 指数损失与AdaBoost

对于二分类问题，AdaBoost使用指数损失函数：

$$L(y,F(\mathbf{x}))=\exp (-yF(\mathbf{x})),y\in \{-1,+1\}$$

AdaBoost的梯度为：

$$-\frac{\partial L}{\partial F}=y\cdot \exp (-yF(\mathbf{x}))$$

4.2 Logistic损失

更常用的分类损失是Logistic损失：

$$L(y,F(\mathbf{x}))=-[y\log \sigma (F(\mathbf{x}))+(1-y)\log (1-\sigma (F(\mathbf{x})))]$$

其中 $\sigma$ 是sigmoid函数。负梯度为：

$$-g_m({\mathbf{x}}_i)=y_i-\sigma (F_{m-1}({\mathbf{x}}_i))$$

这与回归残差的形式相同，但$y$是0/1编码。

4.3 类别概率预测

使用sigmoid或softmax将GBDT输出转换为概率：

$$P(y=1|\mathbf{x})=\sigma (F(\mathbf{x}))=\frac{1}{1+e^{-F(\mathbf{x})}}$$

---

5. 收缩与子采样

5.1 收缩（Shrinkage）

收缩因子 $\nu$ 降低了每棵树对整体的贡献，提高泛化能力：

$$F_m(\mathbf{x})=F_{m-1}(\mathbf{x})+\nu \cdot {\alpha }_m{h}_m(\mathbf{x}),0<\nu \le 1$$

典型值为 $\nu \in [0.01,0.1]$。配合更多的树 $M$ 使用。

5.2 子采样（Subsampling）

借鉴Bagging的思想，对训练样本进行有放回抽样：

• 行采样：每次迭代使用部分样本训练
• 列采样：每次迭代使用部分特征

def gradient_boosting_with_sampling(X, y, subsample_ratio=0.8):
    # 行采样
    n_samples = int(len(y) * subsample_ratio)
    indices = np.random.choice(len(y), n_samples, replace=True)
    X_sub, y_sub = X[indices], y[indices]
    
    # 使用子样本训练
    tree = train_decision_tree(X_sub, y_sub)
    # ...

5.3 正则化效果

技术	作用
收缩 $\nu$	减少单棵树的影响，增加$M$的贡献
最大深度	限制树的复杂度
最小叶节点样本数	防止过拟合
子采样	降低方差，增加随机性

---

6. 完整GBDT实现

import numpy as np
from sklearn.tree import DecisionTreeRegressor
 
class GradientBoostingRegressor:
    """GBDT回归模型"""
    
    def __init__(self, n_estimators=100, max_depth=3, 
                 learning_rate=0.1, min_samples_leaf=5):
        self.n_estimators = n_estimators
        self.max_depth = max_depth
        self.learning_rate = learning_rate
        self.min_samples_leaf = min_samples_leaf
        self.trees = []
        self.F_0 = None
    
    def fit(self, X, y):
        """训练GBDT模型"""
        self.F_0 = np.mean(y)
        F = self.F_0 * np.ones(len(y))
        
        for m in range(self.n_estimators):
            # 计算残差
            residuals = y - F
            
            # 训练决策树拟合残差
            tree = DecisionTreeRegressor(
                max_depth=self.max_depth,
                min_samples_leaf=self.min_samples_leaf
            )
            tree.fit(X, residuals)
            
            # 求解最优步长
            predictions = tree.predict(X)
            rho = np.dot(residuals, predictions) / (np.dot(predictions, predictions) + 1e-8)
            
            # 更新预测
            F = F + self.learning_rate * rho * predictions
            
            # 保存树和步长
            self.trees.append((tree, rho))
        
        return self
    
    def predict(self, X):
        """预测"""
        F = self.F_0 * np.ones(len(X))
        
        for tree, rho in self.trees:
            F = F + self.learning_rate * rho * tree.predict(X)
        
        return F
 
# 使用示例
X_train = np.random.randn(1000, 10)
y_train = X_train[:, 0] ** 2 + np.sin(X_train[:, 1]) + np.random.randn(1000) * 0.1
 
model = GradientBoostingRegressor(n_estimators=100, max_depth=4, learning_rate=0.1)
model.fit(X_train, y_train)
 
y_pred = model.predict(X_train)
mse = np.mean((y_train - y_pred) ** 2)
print(f"训练MSE: {mse:.4f}")

---

7. 与其他Boosting方法的关系

7.1 AdaBoost与GBDT对比

方面	AdaBoost	GBDT
损失函数	指数损失	任意可微损失
基学习器	决策树桩（单分裂）	CART（任意深度）
权重更新	样本权重重新分配	负梯度（伪残差）
正则化	权重收缩	收缩、子采样、树结构

7.2 GBDT vs 随机森林

方面	GBDT	随机森林
训练方式	串行（依赖前一轮）	并行（独立树）
残差	拟合残差	无残差概念
树结构	回归树	分类/回归树
过拟合风险	较高（串行累积错误）	较低（独立树投票）
预测速度	较快	较慢

---

8. GBDT的优缺点

优点

1. 预测精度高：在各种结构化数据上表现优异
2. 灵活性强：支持多种损失函数
3. 特征选择：自然地处理特征重要性
4. 鲁棒性：对异常值相对不敏感
5. 可解释性：特征重要性分析直观

缺点

1. 训练时间长：串行训练，难以并行化
2. 内存消耗：需要存储中间结果
3. 高维稀疏数据：表现不如线性模型
4. 过拟合风险：需要仔细调参

---

9. 应用场景

GBDT及其变体（XGBoost、LightGBM、CatBoost）在以下场景表现优异：

场景	特点
Kaggle竞赛	结构化数据的首选模型
搜索排序	LambdaMART等排序学习
推荐系统	特征交叉与点击率预估
金融风控	信用评分、欺诈检测
医疗诊断	疾病预测、风险评估

---

参考

---

相关主题

• 决策树与随机森林
• XGBoost深入解析
• LightGBM高效实现
• 集成学习统一理论

Footnotes

1. Friedman, J. H. (2001). “Greedy Function Approximation: A Gradient Boosting Machine.” Annals of Statistics, 29(5), 1189-1232. ↩