梯度提升算法基础

1. 概述

梯度提升（Gradient Boosting）是一种加法模型（Additive Model）的学习方法，其核心思想是：将弱学习器（如决策树）逐步累加，每次都去拟合前一轮的残差（或负梯度），从而逐步减少损失。

1.1 发展历史

年份	算法	关键贡献
2001	AdaBoost	自适应提升，指数损失
2001	GBM	梯度提升框架
2016	XGBoost	正则化目标、并行化
2017	LightGBM	基于梯度的采样、直方图
2018	CatBoost	类别特征、Ordered Target

1.2 核心思想

梯度提升将机器学习问题重新解释为函数空间中的优化问题：

F^*(x) = \arg\min}_{F} \mathbb{E}_{x,y}[L(y, F(x))]

其中 $L (y, F (x))$ 是损失函数， $F (x)$ 是预测函数。

2. 前向分步加法模型

2.1 加法模型形式

梯度提升使用加法模型：

F_{m} (x) = m = 1 \sum M η \cdot h_{m} (x)

其中：

$h_{m} (x)$ 是第 $m$ 个弱学习器（通常是决策树）
$η$ 是学习率（收缩因子）
$M$ 是弱学习器的数量

2.2 前向分步算法

前向分步算法（Forward Stagewise Algorithm）通过逐步优化来训练加法模型：

F_{m} (x) = F_{m - 1} (x) + η \cdot h_{m} (x)

其中 $h_{m} (x)$ 是对残差的拟合：

h_m(x) = \arg\min}_h \sum_{i=1}^{N} L(y_i, F_{m-1}(x_i) + h(x_i))

2.3 为什么用前向分步？

直接优化加法模型是困难的，因为每个 $h_{m}$ 都需要同时优化。前向分步算法通过贪心策略逐步构建模型，每次只优化一个基学习器。

3. 梯度下降视角

3.1 函数空间中的梯度下降

梯度提升可以被理解为函数空间中的梯度下降：

考虑在函数空间 $F$ 中优化泛函：

L (F) = i = 1 \sum N L (y_{i}, F (x_{i}))

梯度下降更新：

F_{m} = F_{m - 1} - η \cdot \nabla L (F_{m - 1})

3.2 负梯度作为残差

梯度 $\nabla L (F)$ 在每个数据点上的值为：

g_{i} = [\frac{\partial L ( y _{i} , F ( x _{i} ))}{\partial F ( x _{i} )}]

负梯度 $- \nabla L (F)$ 可以看作是残差的广义扩展。

3.3 常见损失函数的梯度

损失函数	残差形式
平方损失 $L = \frac{1}{2} (y - F)^{2}$	$r_{i} = y_{i} - F_{m - 1} (x_{i})$
绝对损失 $L =	y-F
指数损失 $L = exp (- y F)$	$r_{i} = y_{i} \cdot exp (- y_{i} F_{m - 1} (x_{i}))$
Huber损失	$r_{i} = clip (y_{i} - F_{m - 1} (x_{i}), - δ, δ)$

3.4 梯度提升算法流程

输入: 训练数据集 D = {(x_1, y_1), ..., (x_N, y_N)}
      损失函数 L(y, F(x))
      基学习器数量 M
      学习率 η

1. 初始化 F_0(x) = argmin_c Σ L(y_i, c)
   (例如: 平方损失下 F_0(x) = ȳ)

2. For m = 1 to M:
   
   a. 计算负梯度(伪残差):
      r_im = -[∂L(y_i, F(x_i))/∂F(x_i)]_{F=F_{m-1}}
   
   b. 用训练集 {(x_i, r_im)} 拟合基学习器 h_m(x)
   
   c. 计算最优步长:
      γ_m = argmin}_γ Σ L(y_i, F_{m-1}(x_i) + γ·h_m(x_i))
   
   d. 更新模型:
      F_m(x) = F_{m-1}(x) + η·γ_m·h_m(x)

3. 输出最终模型 F_M(x)

4. 收缩（Shrinkage）

4.1 收缩的作用

收缩因子 $η$ （也叫学习率）控制每棵树的贡献：

F_{m} (x) = F_{m - 1} (x) + η \cdot h_{m} (x)

4.2 收缩的效果

较小的 $η$ ：需要更多棵树，但通常泛化性能更好
典型的 $η$ 值：0.01 到 0.1
$η$ 与 $M$ 的关系： $η ↓\Rightarrow M ↑$ ，但计算量增加

4.3 经验法则

如果 η = 0.1 需要 M = 100 棵树
那么 η = 0.01 可能需要 M ≈ 1000 棵树
但泛化性能可能更好

5. 子采样（Stochastic Boosting）

5.1 行采样

与Random Forest类似，梯度提升也可以使用行采样：

F_{m} (x) = F_{m - 1} (x) + η \cdot h_{m} (x; I_{m})

其中 $I_{m}$ 是从 ${1, 2, \dots, N}$ 中有放回或无放回采样的子集。

5.2 子采样的好处

减少过拟合：引入随机性，增加模型的泛化能力
加速训练：每次只训练部分数据
典型采样率：0.5 到 0.8

5.3 与AdaBoost的联系

当使用指数损失和子采样时，梯度提升与AdaBoost有密切联系。实际上，AdaBoost可以看作梯度提升的一个特例。

6. 正则化策略

6.1 树数量 M

树数量 $M$ 是最重要的正则化参数：

过少的树：欠拟合
过多的树：过拟合

通常使用早停（Early Stopping）来确定最优的 $M$ 。

6.2 树的复杂度

通过限制树的复杂度来正则化：

参数	作用
最大深度	限制树的深度
最小叶节点样本数	防止创建小叶节点
最大叶节点数	限制树的复杂度
分裂所需最小增益	防止无意义的分裂

6.3 L1/L2 正则化

对于树模型，L1正则化促进稀疏性（部分特征权重为0），L2正则化收缩权重：

Ω (h) = γ T + \frac{1}{2} λ j = 1 \sum T w_{j}^{2}

其中 $T$ 是叶节点数， $w_{j}$ 是叶节点权重。

7. 二阶梯度近似

7.1 Newton法 vs 梯度下降

梯度提升使用一阶导数（梯度），但也可以使用二阶近似（Newton法）：

对于损失函数的二阶Taylor展开：

L (y, F + h) \approx L (y, F) + g \cdot h + \frac{1}{2} h \cdot H \cdot h

其中 $g = \partial L / \partial F$ 是一阶梯度， $H = \partial^{2} L / \partial F^{2}$ 是二阶梯度（Hessian）。

7.2 二阶梯度提升

F_{m} = F_{m - 1} - η \cdot H^{- 1} \cdot g

当 $L = \frac{1}{2} (y - F)^{2}$ 时， $g = F - y$ ， $H = 1$ ，这退化为标准的残差拟合。

7.3 XGBoost的实现

XGBoost使用二阶近似来构建树：

L = i = 1 \sum N [g_{i} \cdot w_{q (x_{i})} + \frac{1}{2} h_{i} \cdot w_{q (x_{i})}^{2}] + Ω (h)

其中 $g_{i}$ 和 $h_{i}$ 分别是一阶和二阶梯度。

8. 特征重要性

8.1 基于增益的重要性

Importance (j) = m = 1 \sum M 1 [特征 j 在树 m 中被使用] \cdot gain_{m} (j)

8.2 基于分裂次数的重要性

统计每个特征被用于分裂的次数。

8.3 基于覆盖的重要性

使用经过分裂的样本数作为权重。

9. 优缺点分析

优点

优点	说明
高精度	在表格数据上通常表现最好
鲁棒性	对异常值和噪声相对鲁棒
可解释性	可以计算特征重要性
灵活性	支持各种损失函数
稀疏数据	能处理缺失值

缺点

缺点	说明
训练时间	串行训练，无法充分利用GPU
内存消耗	需要存储所有树
调参复杂	有多个超参数需要调整
不适合高维稀疏	如文本、图像数据

10. 代码实现

10.1 基础梯度提升框架

import numpy as np
from sklearn.tree import DecisionTreeRegressor
 
class GradientBoosting:
    def __init__(self, n_estimators=100, learning_rate=0.1, max_depth=3):
        self.n_estimators = n_estimators
        self.learning_rate = learning_rate
        self.max_depth = max_depth
        self.trees = []
        self.initial_prediction = None
    
    def fit(self, X, y):
        N = len(y)
        
        # 初始化：使用常数预测（最小化MSE）
        self.initial_prediction = np.mean(y)
        F = np.full(N, self.initial_prediction)
        
        for m in range(self.n_estimators):
            # 计算负梯度（伪残差）
            residuals = y - F
            
            # 拟合残差
            tree = DecisionTreeRegressor(
                max_depth=self.max_depth,
                random_state=m
            )
            tree.fit(X, residuals)
            self.trees.append(tree)
            
            # 更新预测
            F += self.learning_rate * tree.predict(X)
        
        return self
    
    def predict(self, X):
        F = np.full(len(X), self.initial_prediction)
        for tree in self.trees:
            F += self.learning_rate * tree.predict(X)
        return F
 
# 示例
X = np.random.randn(1000, 10)
y = X[:, 0] ** 2 + 0.5 * X[:, 1] + np.random.randn(1000) * 0.1
 
gbm = GradientBoosting(n_estimators=100, learning_rate=0.1, max_depth=4)
gbm.fit(X, y)
predictions = gbm.predict(X)
print(f"MSE: {np.mean((predictions - y) ** 2):.4f}")

10.2 使用scikit-learn

from sklearn.ensemble import GradientBoostingRegressor
from sklearn.model_selection import cross_val_score
 
# 训练
gbm = GradientBoostingRegressor(
    n_estimators=100,
    learning_rate=0.1,
    max_depth=4,
    min_samples_split=5,
    min_samples_leaf=2,
    subsample=0.8,
    random_state=42
)
gbm.fit(X_train, y_train)
 
# 预测
predictions = gbm.predict(X_test)
 
# 评估
score = gbm.score(X_test, y_test)
print(f"R² Score: {score:.4f}")
 
# 特征重要性
importances = gbm.feature_importances_
print(f"Top 3 features: {np.argsort(importances)[-3:][::-1]}")

11. 与其他集成方法的对比

11.1 Bagging vs Boosting

特性	Bagging (RF)	Boosting (GBM)
训练方式	并行	串行
基学习器权重	相等	加权累积
减少的误差	方差	偏差+方差
对噪声的敏感性	较不敏感	较敏感
典型算法	Random Forest	AdaBoost, GBM

11.2 AdaBoost vs Gradient Boosting

特性	AdaBoost	Gradient Boosting
损失函数	指数损失	任意可微损失
权重更新	显式调整样本权重	隐式通过梯度
正则化	通过early stopping	多种正则化策略

Metaphor

探索