排序提升（Ordered Boosting）是 CatBoost 的核心创新之一，用于解决梯度提升决策树（GBDT）在训练过程中可能产生的信息泄漏（Information Leakage）和预测偏移（Prediction Shift） 问题。

传统的 GBDT 在计算目标统计（Target Statistics）或特征值时，可能会使用目标变量的全局信息，从而导致未来数据（即测试集或当前样本的真实值）对模型的训练产生影响。排序提升通过一种特殊的数据划分和训练方法，严格按照样本顺序计算目标统计，避免了这种信息泄漏问题。

---

1. 排序提升的背景：解决预测偏移问题

什么是预测偏移？

在传统的 GBDT 中，目标变量可能会泄漏到训练特征中，主要体现在：

1. 目标统计计算时的信息泄漏：

   • 比如计算分类特征的目标统计值（如目标均值编码）时，通常会使用整个数据集的信息，这导致模型的训练阶段可以看到未来样本的目标变量。

2. 结果：

   • 训练集表现良好（低误差），但测试集表现较差（高误差）。
   • 这是因为模型的训练数据中包含了未来的目标变量，导致过拟合。

解决方案：排序提升

CatBoost 提出的排序提升方法通过严格限制每个样本只能使用之前样本的信息，避免了目标变量的信息泄漏问题，从而解决预测偏移。

---

2. 排序提升的核心思想

排序提升的核心思想是：

1. 对训练样本按照时间或索引顺序排列。
2. 在训练过程中，每个样本的目标统计值（如目标均值编码）只能使用其之前样本的数据计算，而不能使用当前样本及之后的样本信息。

---

3. 排序提升的具体实现

排序提升在 CatBoost 的训练过程中体现在以下几个方面：

1. 数据顺序化

假设训练数据集为 $(x,y)$，排序提升首先将数据按照某种固定顺序排列（如时间顺序、自然顺序或随机顺序）。排列后的数据为：
$$(x_{{\sigma }_1},y_{{\sigma }_1}),(x_{{\sigma }_2},y_{{\sigma }_2}),\dots ,(x_{{\sigma }_n},y_{{\sigma }_n})$$
其中，$\sigma$ 是样本的排列顺序。

2. 按顺序计算目标统计（Target Statistics）

对于每个分类特征 $x_k$，目标统计值（如目标均值编码）是基于该样本之前的数据计算的。公式如下：
$${\hat{x}}_k^i=\frac{{\sum }_{j=1}^{i-1}[x_{{\sigma }_j,k}=x_{{\sigma }_i,k}]y_{{\sigma }_j}+a\cdot p}{{\sum }_{j=1}^{i-1}[x_{{\sigma }_j,k}=x_{{\sigma }_i,k}]+a}$$
其中：

• $i$：当前样本的索引。
• $j$：历史样本的索引（$j<i$）。
• $a$：平滑因子，避免数据稀疏时统计值不稳定。
• $p$：目标变量的全局均值。

这个公式确保：

• 当前样本 $i$ 的目标统计值只使用历史样本（$j<i$）的数据。
• 避免了信息泄漏问题。

3. 模型的增量更新

CatBoost 的模型更新过程是逐步迭代的：

1. 每一轮迭代中，模型预测值 $M_{t-1}(x)$ 被更新为：
   $$M_t(x)=M_{t-1}(x)+h_t(x)$$
   其中 $h_t(x)$ 是本轮迭代的增量函数。
2. 在训练增量函数 $h_t(x)$ 时，严格按照样本顺序对每个样本进行训练，只使用之前样本的信息。

---

4. 排序提升的算法伪代码

如下是排序提升算法的伪代码：

输入：

• 训练样本 $(x,y)$
• 样本排列顺序 $\sigma$
• 模型初始化状态 $M_0$

过程：

1. 初始化模型 $M_0=0$。
2. 对每一轮迭代 $t=1,2,\dots ,T$：
   • 对每个样本 $i=1,2,\dots ,n$：
     1. 根据前 $i-1$ 个样本 $(x_{{\sigma }_1},y_{{\sigma }_1}),\dots ,(x_{{\sigma }_{i-1}},y_{{\sigma }_{i-1}})$ 计算目标统计值。
     2. 更新模型的残差：
        $$g_t(y_{{\sigma }_i},M_{t-1}(x_{{\sigma }_i}))$$
     3. 使用残差拟合一棵决策树 $h_t(x)$。
   • 更新模型：
     $$M_t(x)=M_{t-1}(x)+\eta h_t(x)$$

---

5. 排序提升的一个例子

假设有以下训练数据：

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

目标统计计算：

1. 第 1 行：

   • 没有之前的样本，目标统计值使用全局均值 $p=0.75$。

2. 第 2 行：

   • 当前特征值为 $x_2=B$，计算目标统计：
     $$TS(x_2)=p=0.75$$

3. 第 3 行：

   • 当前特征值为 $x_3=A$，基于第 1 行计算目标统计：
     $$TS(x_3)=\frac{y_1}{1}=1.0$$

4. 第 4 行：

   • 当前特征值为 $x_4=B$，基于第 2 行计算目标统计：
     $$TS(x_4)=\frac{y_2}{1}=0.0$$

---

6. 排序提升的优点

1. 避免信息泄漏：

   • 通过严格按照样本顺序计算目标统计值和更新模型，避免了未来数据对当前样本的影响。

2. 提高模型的鲁棒性：

   • 排序提升能够更稳定地处理高基数分类特征，尤其是稀疏类别。

3. 解决预测偏移问题：

   • 训练误差和测试误差更接近，模型的泛化性能更好。

4. 支持并行计算：

   • CatBoost 结合排序提升和对称树结构（Symmetric Trees），实现了高效的 GPU 加速训练。

---

7. 总结

• 排序提升 是 CatBoost 的核心创新，通过严格限制样本使用顺序，解决了传统 GBDT 模型中常见的预测偏移问题。
• 它在目标统计计算和模型训练中都严格遵循样本顺序，避免了信息泄漏。
• 排序提升特别适合高基数分类特征的数据集，能显著提升模型的稳定性和泛化性能。