在 CatBoost 中，预测偏移（Prediction Shift） 和 排序提升（Ordered Boosting） 是其关键概念和创新点。CatBoost 通过引入 排序提升 解决了梯度提升决策树（GBDT）算法中常见的 预测偏移问题，从而提高了模型的稳定性和性能。以下是对这两个概念的详细解释：

---

1. 预测偏移（Prediction Shift）

概念

预测偏移是指在梯度提升决策树（GBDT）训练过程中，由于在模型训练阶段同时使用特征和目标变量可能会导致未来信息泄漏，从而影响模型性能和稳定性。

• 原因：
  在标准 GBDT 算法中，训练样本的目标变量会被用来更新模型，而同时目标变量也会被用于特征变换（如目标统计编码）。这种特征变换过程中可能会使用目标变量的全局信息，从而导致未来样本的信息被泄漏到当前训练样本中。

• 结果：

  • 训练误差较低，但在测试集上表现较差（过拟合）。
  • 对目标变量统计不准确，尤其是分类特征的目标统计编码可能引入偏差。

---

示例

假设有一个分类特征 $x$ 和目标变量 $y$：

样本 $i$	分类特征 $x_i$	目标变量 $y_i$
1	A	1
2	A	0
3	A	1

如果在第 3 个样本训练过程中使用整个数据集的目标统计均值（包括第 3 个样本本身的 $y_3=1$），则会导致信息泄漏。例如：

目标统计编码：
$$\text{编码值}=\frac{\text{总目标值}}{\text{总样本数}}=\frac{1+0+1}{3}=0.67$$

这会将第 3 个样本的目标变量泄漏到其特征变换中。

---

2. 排序提升（Ordered Boosting）

概念

排序提升是 CatBoost 提出的用于解决 预测偏移问题 的方法。其核心思想是在每一轮训练中，严格按照样本的时间或排列顺序，只使用当前样本之前的数据计算特征变换（如目标统计编码），避免了未来信息泄漏。

---

Ordered Boosting 的实现原理

CatBoost 的 排序提升 使用了一种特殊的数据划分和特征计算方式：

1. 样本顺序化：

   • 假设样本被排列为 $(x_{{\sigma }_1},y_{{\sigma }_1}),(x_{{\sigma }_2},y_{{\sigma }_2}),\dots ,(x_{{\sigma }_n},y_{{\sigma }_n})$，其中 $\sigma$ 表示样本的排列顺序。
   • 在训练第 $i$ 个样本时，仅使用前 $i-1$ 个样本的数据来计算特征值。

2. 目标统计的顺序计算：

   • 对于分类特征，目标统计值的计算严格遵循样本顺序。例如，计算第 $i$ 个样本的目标统计值 $TS(x_i)$ 时，仅基于样本 $(x_1,y_1),(x_2,y_2),\dots ,(x_{i-1},y_{i-1})$ 的目标变量 $y_j$。
   • 避免了将当前样本 $y_i$ 或未来样本的目标值泄漏到统计值中。

3. 模型更新的顺序化：

   • CatBoost 使用排序提升算法训练决策树时，每棵树的分裂决策仅基于当前模型状态和之前的数据更新。

---

排序提升算法的伪代码

如下图 14-2 中描述的伪代码：

1. 对训练样本 $(x,y)$ 按顺序排列为 $(x_{{\sigma }_1},y_{{\sigma }_1}),(x_{{\sigma }_2},y_{{\sigma }_2}),\dots ,(x_{{\sigma }_n},y_{{\sigma }_n})$。
2. 初始化模型 $M_0$。
3. 对于每个样本 $i$：
   • 根据模型状态 $M_{i-1}$ 和前 $i-1$ 个样本的目标变量 $y_{{\sigma }_j}$ 计算目标统计值。
   • 更新模型状态 $M_i=M_{i-1}+\Delta M$，其中 $\Delta M$ 是模型的增量更新（如一棵树的增量效果）。
4. 输出最终模型 $M_n$。

---

排序提升的优点

1. 避免信息泄漏：

   • 通过按顺序计算特征值和模型更新，确保每个样本的特征计算只依赖于之前的样本信息。
   • 解决了传统梯度提升算法中的预测偏移问题。

2. 提高模型鲁棒性：

   • 排序提升能够更好地适应分类特征中高基数、稀疏类别的情况。
   • 即使样本数量有限，也能生成稳定的特征统计值。

3. 改进模型性能：

   • 避免了模型过拟合，提升了测试集上的性能。

---

排序提升的一个例子

假设训练样本如下：

样本 $i$	分类特征 $x_i$	目标变量 $y_i$
1	A	1
2	B	0
3	A	1
4	B	1

目标统计值的计算：

对于分类特征 $x$，计算目标统计值 $TS(x_i)$ 时：

1. 第 1 行：

   • $TS(x_1)$：没有之前的样本，所以使用全局均值 $p$。

2. 第 2 行：

   • $TS(x_2)$：类别 $B$ 的目标统计值基于之前样本：
     $$TS(x_2)=p$$

3. 第 3 行：

   • $TS(x_3)$：类别 $A$ 的目标统计值基于第 1 行：
     $$TS(x_3)=\frac{y_1}{1}=1$$

4. 第 4 行：

   • $TS(x_4)$：类别 $B$ 的目标统计值基于第 2 行：
     $$TS(x_4)=\frac{y_2}{1}=0$$

---

总结

1. 预测偏移（Prediction Shift）：

   • 是由于目标变量泄漏到特征变换中引起的模型训练问题，导致过拟合和不稳定性。

2. 排序提升（Ordered Boosting）：

   • 是 CatBoost 的核心创新，通过严格按照时间或排列顺序训练模型，避免了预测偏移问题。
   • 在分类特征处理、目标统计值计算和模型更新中都有应用。