Catboost

2025年9月30日

14:21

1.类别特征的处理

1)one-hot，但是当类别数量过多时，如user_id，会出现维度灾难。

2）target encodeing

3）在Lightgbm中：

核心思想：用“数据”代替“类别名”

在梯度提升树中，分裂节点时需要找到一个特征和一个阈值，使得分裂后的数据集的损失函数降低最多。对于数值特征，这很直接：对特征值排序，然后找到一个切分点（例如：年龄 <= 30）。

但对于类别特征（例如：城市 = {北京， 上海， 广州， 深圳}），你不能直接对类别名进行排序（“北京”和“上海”没有大小关系）。因此，必须找到一种方法将类别特征“转换”成某种可以排序的数值。

LightGBM的方法：基于梯度的统计量

LightGBM采用的是一种非常流行且有效的方法，叫做 “梯度统计” 或 “均值编码” 的在线变体。

具体是什么意思？

  1. 什么是梯度？
  • 在梯度提升的每一步，我们都在拟合一个新的弱学习器（一棵树）来纠正之前模型的错误。
  • 对于每一个样本，我们都可以计算其损失函数关于当前模型预测值的梯度（对于回归问题，梯度大致就是残差；对于二分类，有特定的形式）。这个梯度表示了“为了降低这个样本的损失，我们的新模型应该往哪个方向预测”。
  1. 如何用于类别特征？
  • 假设我们有一个类别特征“城市”，现在要考虑根据“城市”来分裂节点。
  • 传统的均值编码是：用整个训练集上，目标变量的均值来代表一个类别（例如，北京的用户平均购买金额是1.2万元）。
  • LightGBM的梯度统计方法是：在当前模型下，用该节点内（注意：是当前要分裂的节点，不是全局）样本梯度的均值（或某种统计量）来代表一个类别。
  • 简单来说：它不是用“目标变量的平均值”，而是用“当前模型残差（梯度）的平均值”来给每个类别打分。
  1. 分裂过程：
  • 对于节点上的所有样本，遍历每个类别特征。
  • 对于某个类别特征（如“城市”），计算每个城市类别（北京、上海...）对应的梯度统计量（比如，梯度均值）。
  • 然后，按照这个梯度统计量的大小对类别进行排序。比如，计算出来：
  • 北京： 梯度均值 = 0.1
  • 上海： 梯度均值 = 0.5
  • 广州： 梯度均值 = -0.2
  • 深圳： 梯度均值 = 0.3
  • 排序后，类别顺序可能是：广州(-0.2) -> 北京(0.1) -> 深圳(0.3) -> 上海(0.5)。
  • 现在，类别特征被转化成了一个可以排序的“伪数值特征”。分裂时，就可以像数值特征一样，寻找最佳的分割点。例如，分裂规则可能是：城市 in {广州， 北京} vs 城市 in {深圳， 上海}。

CatBoost论文指出的问题

现在再回头看CatBoost论文中指出的两个问题就非常清晰了：

  1. 计算时间长：
    “计算每个类别在每一步的统计量”
  • 因为每构建一棵树，在每个节点分裂时，对于每一个类别特征，都需要重新计算所有出现类别的梯度统计量。对于高基数（类别非常多）的特征，这个排序和统计的计算成本非常高。
  1. 内存消耗大：
    “存储哪个类别属于哪个节点”
  • 一旦按照梯度统计量排序并完成了分裂，树的结构就记录了“哪些类别被分到了左子树，哪些被分到了右子树”。例如，上面的例子中，规则就是 城市 in {广州， 北京}。LightGBM需要存储这个类别集合，对于高基数特征，存储这些集合会消耗大量内存。

LightGBM的解决方案及其新问题

  • 解决方案：为了缓解上述问题，LightGBM会将那些出现频率很低的尾部类别 合并成一个集群。
  • 新问题：丢失信息。把“乌鲁木齐”、“拉萨”这样罕见的类别和“太原”合并成一个“其他”类别，无疑会损失这些类别本身特有的信息。
  • LightGBM论文中作者也提到最好将高基数类别转换为数值特征。所以Target encoding似乎是最有效的处理高基数类别特征的方法。

对比CatBoost的TS方法

论文最后一句是关键：

“Note that TS features require calculating and storing only one number per one category.”

  • TS 是 Target Statistics（目标统计）的缩写，是CatBoost的核心技术之一。
  • 它的意思是：在数据预处理阶段，对每个类别，计算一个唯一的、全局的数值来代替它（例如，基于目标变量的期望值）。
  • 优势：
  • 计算：这个数值只需要在训练开始前计算一次，之后这个特征就被当作数值特征来处理。避免了LGB在每棵树每个节点都要重新计算的开销。
  • 内存：不需要存储复杂的类别集合分裂规则，只需要存储一个转换后的数值，内存占用小。
  • 挑战：TS方法本身最大的挑战是目标泄漏 和过拟合，因为你在用目标y的信息来构造特征。这正是CatBoost论文重点解决的问题，它通过一种“有序”的编码方式巧妙地避免了这个问题。

 

2.Target statistics

 Target encoding是很容易产生目标泄漏的，比如某个类别只有一个取值，那么此时用目标进行编码的话，其实几乎相当于直接用目标列作为特征列。

1)greedy

2)hold-out

3)leave one out

4)ordered

这是CatBoost的创新核心，它巧妙地借鉴了时间序列验证的思想，并将其应用于任意数据集，完美地解决了上述所有问题。

核心洞察：将数据集想象成一个时间序列。在预测  t 时刻的值时，你只能使用 t−1 时刻及之前的信息。

具体实现 - 引入“虚拟时间”（Artificial Time）：

随机排列：对整个训练数据集进行一次随机排序（Permutation），生成一个“虚拟时间”顺序。假设排序后的样本索引是 σ(1),σ(2),...,σ(n) 。

有序编码：对于每个样本 i（在虚拟时间顺序中），计算其类别特征编码时，只使用“过去”的样本（即排在它前面的样本）。

为什么 Ordered TS 是完美的？

  • 解决目标泄漏：在计算样本 ii 的编码时，完全没有使用样本 i 本身及其“未来”的信息。
  • 解决条件偏移：

训练时：对于第 i 个样本，我们使用前 i−1个样本来计算其编码。

推理时：对于一个新样本，我们使用整个训练集来计算其编码。

  • 这看起来又产生了分布不一致？但CatBoost在训练模型本身时，也采用了同样的“有序”原则，这被称为 “Ordered Boosting”。

Ordered Boosting 简介：

在梯度提升的每一步，当计算第 i 个样本的梯度时，只使用前 i−1  个样本训练的模型来计算。这样就保证了训练过程和编码过程处于完全相同的条件下，彻底消除了条件偏移。

 

 

3.Prediction shift

当计算样本1的梯度时：

  • 模型 F_{t-1} 是用 {样本1,2,3,4} 训练的
  • 但 F_{t-1} 已经见过样本1本身
  • 因此计算出的梯度是有偏的，不能反映模型在未见过的样本上的真实表现

 

Prediction Shift的本质：

  • 根本原因：用相同的数据既训练模型又计算梯度
  • 表现形式：训练时的梯度分布不能代表测试时的真实梯度分布
  • 后果：基学习器过度拟合有偏信号，最终模型泛化能力下降
  • 解决方案：Ordered Boosting确保每个样本的梯度都用没看过该样本的模型计算

 

  1. Ordered Boosting

上图是catboost如何构建每一棵树的算法，在每轮构建新树之前，先选择一种样本排序方式σr​，然后用当前的支持模型M和真实标签y，计算出每个样本的梯度/残差，即上图中的G和下图中的Residuals，然后开始构建新树。

 

具体的确定树结构（寻找最优特征分裂点）的流程，详见：https://www.youtube.com/watch?v=3Bg2XRFOTzg&t=317s

这张图中的predictions列就是支持模型M_(r,j)，对每一个样本排序r（上图相当于是一种排序），每一个样本j，都有一个prediction，表示的是在样本排序r下，用样本0到样本j训练出的模型的预测值，即支持模型M_(r,j)的预测值。

有了支持模型M_(r,j)的预测值predictions列，和真实标签heigth列，就可以计算出每个样本的梯度/残差，即residuals列。

 

下面来看如何构建一棵新树。首先是树结构的确定，即特征分裂点的寻找。

catboost是对称树，从算法中看出，是一层一层的构建 ，从树桩开始。在每一层，对所有的特征候选分裂点，按照排好序后的样本顺序，进行如下操作：将样本i根据当前树结构分到叶子节点leaf_x中，并记下样本i的梯度和leaf_x当前的输出值（leaf output），记下后，再用加入样本i后的梯度更新叶子节点leaf_x的输出值，leaf_x新的输出值 = 加上样本i后叶子节点leaf_x中所有样本的梯度的平均值。leaf_output列是按样本顺序一个一个生成的，即算法图中的Δ。

有了Δ列（leaf_output列）之后 ，计算Δ和梯度G（residuals列）的余弦相似度，选择余弦相似度最大的作为最优分裂点。这样一层一层，就确定了树结构 。

 

确定了树结构之后 ，对所有排序方式下的支持模型进行更新，

从算法中也可以看出，是两层for循环，对每种排序σ，每个样本i，都更新支持模型对排序σ下样本i的预测值。

CatBoost通过支持模型来构建每棵树，其核心过程如下：

  • 支持模型的作用：在Ordered Boosting模式下，CatBoost会维护一组支持模型 Mr,j，其中 r 代表排列的索引，j 代表在这个排列中前 jj个样本。支持模型 Mr,j的含义是基于排列 σr 中前 j 个样本训练得到的模型状态。它的核心任务是提供无偏的梯度估计。
  • 如何构建树结构：在每次迭代 t 要构建新树 Tt时，算法会随机选择一个排列 σr​，然后利用对应的支持模型来计算梯度。具体来说，对于排列中的样本 i，使用支持模型 Mr,σr(i)−1（即用排在 i 之前的样本训练的模型）来计算其梯度 gradr,σr(i)−1(i)，
    这确保了在计算样本     ii 的梯度时，模型没有见过样本 ii 本身，从而得到无偏的梯度估计。这棵树的结构（即分裂规则） 就是依据这些无偏梯度学习到的。
  • 更新支持模型：一旦新的树结构 Tt​ 确定，CatBoost并不会只更新一个最终模型，而是会用这棵树的树结构去更新所有的支持模型。这就是图中“用树结构 TtTt​ 更新所有支持模型”这一步。对于每一个支持模型 Mr′,jMr′,j​，都会根据其对应的排列 σr′σr′​ 和前 jj 个样本，计算出 TtTt​ 在这组特定数据上对应的叶子节点值，然后更新 Mr′,jMr′,j​ 。这样，所有支持模型都共享同一棵树结构 TtTt​，但各自拥有基于自身数据计算的叶子节点值。

 

训练期间——树结构与支持模型的更新

这段话描述的是在训练过程中，当一棵树的结构 T_t 被确定后，如何用它来更新所有支持模型。

核心要点：

  • 统一的树结构： 在每次迭代 t，算法只构建一个树结构 T_t。这个结构定义了从根节点到叶子节点的所有分裂规则（例如，第一层按“年龄<30”分裂，第二层按“收入>50k”分裂）。
  • 个性化的叶子值： 这个统一的树结构 T_t 被添加到每一个支持模型 M_{r', j} 中。但是，对于不同的 (r', j) 组合，这棵树的叶子节点的值是不同的。
  • 原因： 每个支持模型 M_{r', j} 是基于不同数据子集（排列 σ_{r'} 的前 j 个样本）的模型状态。因此，对于同一个叶子节点（例如，“年龄<30 & 收入>50k”），不同的支持模型 M_{r', j} 会根据各自所见的数据子集计算出的梯度统计量，来赋予该节点不同的输出值。

总结： 在训练时，树结构是全局共享的，但叶子值是针对每个支持模型局部计算的。这是一种高效的工程近似，用一套“骨架”适配了多个模型状态。

 

 

 

 

训练结束后——最终模型的确定与预测

这段话描述的是在所有树都构建完成后，如何确定最终用于预测的模型 F 的叶子值，以及如何进行推理。

核心要点：

1）最终模型的叶子值： 最终模型 F 是由所有树 T_1, T_2, ..., T_T 叠加而成的。对于 F 中的每一棵树，其叶子节点的值是通过标准的梯度提升程序计算的(也就是直接计算损失函数最小值对应的叶子节点取值？)。这与之前支持模型的更新是两回事。

  • 这里使用的是另一个独立的排列 σ_0 来计算TS，以确保评估最终模型叶子值时使用的是无偏统计量。
  • 训练样本 i 根据其在 σ_0 下的TS值，被分配到叶子节点 leaf_0(i)。
  • 然后，基于落入每个叶子节点的样本的梯度和二阶导数（对于平方损失就是样本数量），按照GBDT的标准公式（如 -sum_gradients / (sum_hessians + lambda)）计算该叶子节点的最终输出值。

2）推理时的TS处理： 当使用训练好的最终模型 F 对新样本进行预测时，对于新样本中的类别特征，我们使用整个训练数据集来计算其TS值。这与训练最终模型时使用排列 σ_0 是不同的。

  • 这是因为在推理时，我们没有“未来”数据的概念。为了获得最稳定的估计，我们使用全部可用的训练数据来计算每个类别对应的TS值。
  • 这个在全部训练集上计算得到的TS映射关系，是在模型序列化（保存）时就已经计算好并存储的。

 

 

 

已使用 OneNote 创建。