提升树
提升树（Boosting Tree）本质上是一类加法模型。它不是只训练一棵树，而是按轮次训练很多棵弱学习器，并把它们逐步叠加起来。
如果把第 $m$ 轮训练得到的树记作 $h_m(x)$，那么最终模型可以写成：
$$
F_M(x) = \sum_{m=1}^{M} \alpha_m h_m(x)
$$
其中：
- $h_m(x)$ 表示第 $m$ 棵树
- $\alpha_m$ 表示该树的权重
- $F_M(x)$ 表示最终集成后的预测函数
提升方法的核心不是“一次把问题学完”，而是：
- 先训练一个较弱的模型
- 观察当前模型还没学好的部分
- 再让下一轮模型去修正前一轮的误差
如果是平方损失回归问题，当前模型 $F_{m-1}(x)$ 在样本 $x_i$ 上的残差为：
$$
r_{im} = y_i - F_{m-1}(x_i)
$$
于是第 $m$ 轮训练的树，就是去逼近这些残差：
$$
h_m(x) \approx r_{im}
$$
模型更新为：
$$
F_m(x) = F_{m-1}(x) + \alpha_m h_m(x)
$$
所以提升树可以理解成一种“逐轮纠错”的方法。前面的树先把大体结构学出来，后面的树不断补充前面没拟合好的部分。
梯度提升树
GBDT（Gradient Boosting Decision Tree）是在提升树上的进一步推广。它最关键的地方在于：
- 不再局限于直接拟合残差
- 而是统一地去拟合损失函数对当前模型输出的负梯度
这样一来，GBDT 就不只适用于平方损失回归，也能自然用于分类、排序等任务。
1. 加法模型
GBDT 仍然采用加法模型。设第 $m$ 轮新增的树为 $h_m(x)$，则：
$$
F_M(x) = F_0(x) + \sum_{m=1}^{M} \nu \gamma_m h_m(x)
$$
其中：
- $F_0(x)$ 是初始模型
- $h_m(x)$ 是第 $m$ 轮训练得到的回归树
- $\gamma_m$ 是该轮步长
- $\nu \in (0,1]$ 是学习率，也叫 shrinkage
2. 优化目标
给定训练集 ${(x_i, y_i)}_{i=1}^{N}$，GBDT 希望最小化经验风险：
$$
\mathcal{L} = \sum_{i=1}^{N} L(y_i, F(x_i))
$$
这里 $L(y_i, F(x_i))$ 是单样本损失。
由于模型是逐步加出来的，所以第 $m$ 轮就是在已有模型 $F_{m-1}(x)$ 的基础上，再增加一个新函数，使总损失下降：
$$
F_m(x) = F_{m-1}(x) + \nu \gamma_m h_m(x)
$$
3. 负梯度思想
在函数空间里做梯度下降时，当前样本的负梯度定义为：
$$
g_{im} = - \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}, \quad \text{其中 } F(x)=F_{m-1}(x)
$$
GBDT 每一轮的关键动作就是：
- 先计算所有样本在当前模型下的负梯度 $g_{im}$
- 再用一棵回归树去拟合这些负梯度
也就是说，第 $m$ 轮不是直接去拟合标签 $y_i$，而是拟合：
$$
h_m(x) \approx g_{im}
$$
这就是“梯度提升”的本质。
4. 为什么平方损失下等价于拟合残差
如果损失函数使用平方误差：
$$
L(y_i, F(x_i)) = \frac{1}{2}(y_i - F(x_i))^2
$$
那么对 $F(x_i)$ 求导可得：
$$
\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} = F(x_i) - y_i
$$
于是负梯度就是：
$$
g_{im} = y_i - F_{m-1}(x_i)
$$
这正好就是残差。所以普通的“拟合残差的提升树”，其实可以看成是 GBDT 在平方损失下的一个特例。
5. 每轮训练流程
GBDT 一轮训练可以拆成下面几步：
- 给定当前模型 $F_{m-1}(x)$
- 计算每个样本的伪残差，也就是负梯度
$$
g_{im} = - \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}, \quad \text{其中 } F(x)=F_{m-1}(x)
$$
- 用样本对 $(x_i, g_{im})$，$i=1,2,\ldots,N$ 拟合一棵回归树，得到若干叶子区域 $R_{jm}, j=1,\dots,J$
- 对每个叶子区域求最优输出值
$$
\gamma_{jm} = \arg\min_{\gamma} \sum_{x_i \in R_{jm}} L\big(y_i, F_{m-1}(x_i) + \gamma\big)
$$
- 更新模型
$$
F_m(x) = F_{m-1}(x) + \nu \sum_{j=1}^{J} \gamma_{jm} I(x \in R_{jm})
$$
其中 $I(\cdot)$ 是示性函数，表示样本是否落在第 $j$ 个叶子区域。
6. 初始模型
GBDT 通常先用一个常数作为初始模型：
$$
F_0(x) = \arg\min_{\gamma} \sum_{i=1}^{N} L(y_i, \gamma)
$$
它的含义是：在还没有任何树之前，先找一个能让整体损失最小的常数起点。
常见情况下：
- 平方损失回归时，$F_0$ 一般是样本均值
- 二分类对数损失时，$F_0$ 一般对应正样本比例的 logit
7. 二分类中的 GBDT
在二分类中，常见损失是 logistic loss。若标签 $y_i \in {0,1}$，设：
$$
p_i = \sigma(F(x_i)) = \frac{1}{1 + e^{-F(x_i)}}
$$
则交叉熵损失可写为：
$$
L(y_i, F(x_i)) = -\big[y_i \log p_i + (1-y_i)\log(1-p_i)\big]
$$
其对模型输出的导数为：
$$
\frac{\partial L}{\partial F(x_i)} = p_i - y_i
$$
所以负梯度为：
$$
g_{im} = y_i - p_i
$$
这里的形式仍然很像残差，但它表示的是“真实标签与当前预测概率之间的差距”。
8. GBDT 的特点
GBDT 在表格数据上长期非常强，原因主要有：
- 能处理非线性关系
- 能自动学习特征组合
- 对特征尺度不太敏感
- 对数值特征和离散特征都比较友好
它的缺点也很明显：
- Boosting 是串行训练，训练速度通常不如 bagging 系模型容易并行
- 参数较多，比如树深、树数、叶子数、学习率
- 树太深或迭代轮数太多时容易过拟合
一个常见经验是：
- 学习率调小一些
- 树的数量加多一些
- 再配合样本采样和特征采样
通常会比“大步快跑”的配置更稳。
用GBDT+LR进行粗排
GBDT + LR 是推荐和广告系统里非常经典的一种粗排方案。它的核心思路是：
- 用 GBDT 自动挖掘非线性特征组合
- 再把这些组合特征交给 LR 做最终打分
1. 为什么要结合 LR
逻辑回归的形式很简单：
$$
\hat y = \sigma(w^\top x + b)
$$
它非常擅长处理高维稀疏特征，但天然是线性的。如果要让 LR 学到复杂交叉，通常只能依赖人工做特征工程。
而 GBDT 很擅长把特征空间切成很多局部区域。一条从根节点到叶子节点的路径，本质上就是一组规则的组合，例如：
年龄 < 25近7天点击次数 > 3品类 = 数码
当样本落入某个叶子节点时，就说明它满足了一组非线性条件。所以“叶子节点”本身就可以看成自动学习得到的组合特征。
2. 特征转换方式
假设训练好的 GBDT 一共有 $M$ 棵树，第 $m$ 棵树有 $J_m$ 个叶子节点。对于一个样本 $x$，它在第 $m$ 棵树中只会落入一个叶子。
于是可以把第 $m$ 棵树的输出编码成 one-hot 向量：
$$
\phi_m(x) \in {0,1}^{J_m}
$$
并且满足：
$$
\sum_{j=1}^{J_m} \phi_{mj}(x) = 1
$$
把所有树的叶子 one-hot 拼接起来，得到新的稀疏特征：
$$
\phi(x) = [\phi_1(x), \phi_2(x), \ldots, \phi_M(x)]
$$
然后再把它送给 LR：
$$
\hat y = \sigma(w^\top \phi(x) + b)
$$
3. 它为什么有效
因为每一个叶子节点都代表了一种局部模式，所以 GBDT + LR 相当于：
- 先用 GBDT 做自动分桶和高阶交叉
- 再用 LR 对这些交叉模式做线性组合
这比人工枚举交叉特征要省很多工作量，而且在工业场景里通常更稳定。
4. 训练流程
工程上常见的流程如下：
- 用原始特征训练一个 GBDT
- 对每个样本，取它在每棵树上的叶子编号
- 把所有叶子编号展开成 one-hot 稀疏向量
- 用这个新的稀疏向量训练 LR
如果总叶子数为 $\sum_{m=1}^{M} J_m$，那么 LR 的参数维度就是：
$$
w \in \mathbb{R}^{\sum_{m=1}^{M} J_m}
$$
5. 为什么适合粗排
粗排阶段通常希望：
- 比纯 LR 有更强的非线性能力
- 在线推断又不能太重
GBDT + LR 很符合这个诉求。因为：
- GBDT 可以离线完成复杂模式学习
- 在线阶段只需要走树拿叶子，再做一次稀疏 LR 打分
虽然现在很多系统会进一步升级到 FM / DeepFM / DCN 这类模型，但 GBDT + LR 依然是理解工业排序模型演化路径时非常重要的一环。
用 LightGBM 的 LambdaRank 方法进行粗排
如果任务目标不是点估计 CTR，而是对一个候选列表做排序，那么普通的 pointwise 分类目标往往不够。因为排序任务真正关心的是：
- 哪些样本应该排在前面
- 把两个样本交换位置之后，排序指标会变化多少
LambdaRank 就是为这种目标设计的一类排序方法，而 LightGBM 提供了非常成熟的 lambdarank 实现。
1. 排序问题的本质
对于同一个 query 或同一个用户请求下的一组候选样本，设模型对第 $i$ 个样本输出分数 $s_i$。最终排序就是按这些分数从大到小排列。
排序指标如 NDCG@K 更关心前几位是否排对，因此它和普通分类损失的关注点并不一致。
LambdaRank 的核心思想是：
- 不直接只看单个样本
- 而是看样本对 $(i, j)$ 的相对顺序
- 如果样本 $i$ 应该排在 $j$ 前面，就推动 $s_i > s_j$
- 并且这种推动力度要和排序指标收益相关
2. pairwise 概率形式
若在同一个 group 中，样本 $i$ 的相关性高于样本 $j$，则希望：
$$
s_i > s_j
$$
RankNet 中常见的 pairwise 概率写法为：
$$
P_{ij} = \sigma(s_i - s_j) = \frac{1}{1 + e^{-(s_i - s_j)}}
$$
对应的 pairwise loss 可以写成：
$$
L_{ij} = \log\big(1 + e^{-(s_i - s_j)}\big)
$$
如果只优化这个损失，本质上只是做成对排序，还没有显式考虑 NDCG。
3. Lambda 的核心思想
LambdaRank 的关键是：如果交换样本 $i$ 和 $j$ 的位置会带来更大的指标变化，那么这对样本在训练时就应该被赋予更大的梯度权重。
设交换它们后带来的指标变化为：
$$
\Delta \mathrm{NDCG}_{ij}
$$
那么常见的 lambda 形式可以写成：
$$
\lambda_{ij} = - \frac{\partial L_{ij}}{\partial s_i} \cdot |\Delta \mathrm{NDCG}_{ij}|
$$
先看导数本身：
$$
\frac{\partial L_{ij}}{\partial s_i} = -\frac{1}{1 + e^{s_i - s_j}}
$$
因此负导数为：
$$
-\frac{\partial L_{ij}}{\partial s_i} = \frac{1}{1 + e^{s_i - s_j}}
$$
所以可以写成：
$$
\lambda_{ij} = \frac{|\Delta \mathrm{NDCG}_{ij}|}{1 + e^{s_i - s_j}}
$$
对于样本 $i$，它最终接收到的梯度信号可以理解成相关样本对贡献的加总：
$$
\lambda_i = \sum_{j:(i,j)} \lambda_{ij} - \sum_{j:(j,i)} \lambda_{ji}
$$
LightGBM 在 lambdarank 训练时，本质上就是利用这些 lambda 值来构造树的分裂和更新方向。
4. 为什么适合粗排
推荐和搜索里的粗排，常常更关心：
- top-k 的结果是否尽量靠前
- 强相关内容有没有被压到后面
lambdarank 的优势就在于：
- 它优化目标更接近实际线上排序指标
- 它关注列表内部的相对顺序，而不是单点分类误差
- 它会更重视那些影响前排结果的样本对
5. LightGBM 中的数据组织
使用 LightGBM 的 lambdarank 时，训练数据一般按 group 组织：
- 每个 group 对应一个 query、一次搜索请求，或一次推荐曝光集合
- group 内部样本一起参与排序损失计算
如果共有 $Q$ 个 group，第 $q$ 个 group 的样本集合为 $\mathcal{G}_q$，那么整体目标可以理解为：
$$
\mathcal{L} = \sum_{q=1}^{Q} \mathcal{L}_{rank}(\mathcal{G}_q)
$$
其中每个 group 内部再基于样本对和 NDCG 增益计算 lambda。