8.1 概述与核心创新
CatBoost(Categorical Boosting)是由俄罗斯搜索引擎巨头 Yandex 于 2017 年开源的梯度提升决策树实现。核心论文有两篇:Prokhorenkova 等人的 CatBoost: unbiased boosting with categorical features(NeurIPS 2018,arXiv 2017)提出有序提升与有序目标统计;Dorogush、Ershov、Gulin 的 CatBoost: gradient boosting with categorical features support(arXiv 2018)介绍了库的整体设计、特征组合与 GPU 实现。其名称直接体现了核心定位——为包含大量类别特征的数据集提供无偏、高效的梯度提升。与 XGBoost 和 LightGBM 相比,CatBoost 的独特之处在于它从理论层面系统性地解决了梯度提升中的预测偏移(Prediction Shift)问题,并提出了有序提升(Ordered Boosting)和有序目标统计(Ordered Target Statistics);同时以遗忘树(Oblivious Trees)作为基学习器。
CatBoost 的三大核心技术:
- Ordered Boosting(有序提升):使用随机排列来避免梯度估计中的目标泄漏(Target Leakage),从根本上解决了梯度提升中的预测偏移问题。
- Oblivious Trees(对称树/遗忘树):同一层所有节点使用相同的特征和分裂条件,生成对称平衡树,减少过拟合并加速预测。遗忘树本身并非 CatBoost 首创(早在 1990 年代就有相关研究),但 CatBoost 把它作为默认基学习器并做了专门的快速预测实现。
- Ordered Target Statistics(有序目标统计):为类别特征提供无偏的目标编码方案,避免了传统目标编码中的目标泄漏。
8.2 三大核心问题:预测偏移、梯度估计偏差、类别特征处理
CatBoost 论文指出,传统梯度提升(包括 XGBoost 和 LightGBM)存在由目标泄漏(target leakage)引起的偏移问题,它在两个地方出现:梯度估计和类别特征的目标统计。下面分三点说明:
问题一:预测偏移(Prediction Shift)
预测偏移是指:对训练样本 $x_k$,当前模型输出 $F^{t-1}(x_k)$ 在给定 $x_k$ 下的条件分布,与对一个新的测试样本 $x$ 的输出 $F^{t-1}(x)$ 的条件分布不同。原因在于,在标准梯度提升中,第 $t$ 棵树使用第 $t-1$ 轮模型对所有训练样本的预测来计算梯度,而这个模型正是用这些样本(包括它们的标签)训练出来的。这意味着每个样本的梯度计算都隐含了该样本自身标签的信息,导致梯度估计存在偏差,进而使最终模型产生偏移。论文定理 1 在一个简化设定下严格证明了这种偏移的存在:平方损失,两个独立的伯努利特征 $x^{(1)}, x^{(2)}$($p = \frac{1}{2}$),真实函数 $y = f^*(x) = c_1 x^{(1)} + c_2 x^{(2)}$,做两步提升、每步一个树桩(深度为 1 的树)、步长为 1。
- 若两步各用一份独立的、大小为 $n$ 的样本,则 $\mathbb{E}\, F^2(x) = f^*(x) + O(2^{-n})$,几乎无偏;
- 若两步用同一份数据,则 $\mathbb{E}\, F^2(x) = f^*(x) - \frac{1}{n-1} c_2 \left(x^{(2)} - \frac{1}{2}\right) + O(2^{-n})$,即存在与样本量 $n$ 成反比的偏差。
直观理解:模型在训练时"偷看"了当前样本的标签来计算梯度更新,这类似于在验证集上调参会导致验证集上的性能被高估。
问题二:梯度估计偏差(Gradient Estimation Bias)
预测偏移的直接后果是梯度估计有偏。在标准梯度提升中,对于样本 $i$,梯度 $g_i$ 是基于模型 $F_{t-1}$ 计算的,而 $F_{t-1}$ 已经使用了样本 $i$ 的信息进行训练。这种依赖关系使得梯度估计不再是对真实损失函数梯度的无偏估计。
CatBoost 通过 Ordered Boosting 引入随机排列,确保每个样本的梯度仅由“没见过该样本”的模型计算,从而消除这种目标泄漏。
问题三:类别特征处理的目标泄漏
传统的类别特征目标编码(如将类别替换为该类别的平均标签值)存在严重的目标泄漏问题:
- 对于训练样本 $i$,用其自身标签计算该类别的统计量时,该样本的标签信息泄漏到特征中。
- 这导致模型在训练集上表现极好,但在测试集上严重过拟合。论文举了一个极端例子:若某个类别特征的每个取值都只出现一次,且 $P(y=1 \mid \text{类别}) = 0.5$,那么用全量数据算出的目标统计只取决于样本自身的标签,一个阈值就能把训练集完美分开;但在测试集上这个特征的编码对所有样本都相同(等于先验),准确率只有 0.5。
- 常见的补救办法各有缺陷:留出法(holdout TS,一部分数据算统计量、另一部分训练)浪费数据;留一法(leave-one-out TS)看似排除了自身,却仍会泄漏。例如对一个所有样本取值都相同的类别特征,留一法编码的大小只取决于样本自身的标签(正样本的编码比负样本略低),一个阈值就能完美分开训练集。
CatBoost 的 Ordered Target Statistics 通过有序统计的方式,仅使用样本之前的数据计算目标统计量,从根本上解决了这一问题。
8.3 Ordered Boosting(有序提升)
8.3.1 核心思想:使用随机排列避免目标泄漏
Ordered Boosting 的核心思想来源于一个关键观察:在标准梯度提升中,计算第 $t$ 棵树的梯度时,当前模型 $F_{t-1}$ 已经使用了所有训练样本(包括当前样本)进行了 $t-1$ 轮更新。这导致每个样本的梯度计算都隐含了该样本自身的信息,形成目标泄漏。
CatBoost 的解决方案:为训练数据引入一个随机排列(random permutation)。对于每个样本,只使用排列中排在它之前的样本构建模型,然后用该模型计算当前样本的梯度。
更具体地说(论文算法 1 的理想版本):取一个随机排列 $\sigma$,同时维护 $n$ 个支持模型(supporting models)$M_1, \dots, M_n$,其中 $M_i$ 只用排列中前 $i$ 个样本训练。每一步提升时,排在第 $j$ 位的样本的残差(负梯度)用 $M_{j-1}$ 计算,所以这个残差不依赖该样本自身的标签。这个理想版本需要训练 $n$ 个模型,计算量和内存都增加 $n$ 倍,实际不可行,8.3.3 介绍 CatBoost 的近似实现。
flowchart TD
A["生成随机排列 sigma"] --> B["对于每个样本 i 按 sigma 顺序"]
B --> C["只用当前样本之前的数据构建模型"]
C --> D["用前缀模型计算当前样本预测"]
D --> E["计算样本 i 的梯度 g_i"]
E --> F{"还有未处理样本?"}
F -->|是| B
F -->|否| G["在所有样本上拟合第 t 棵树"]
G --> H{"满足停止条件?"}
H -->|否| A
H -->|是| I["输出最终模型"]
8.3.2 与传统梯度提升的对比
| 维度 | 传统梯度提升(GBDT/XGBoost/LightGBM) | Ordered Boosting(CatBoost) |
|---|---|---|
| 梯度计算 | 使用全部样本训练得到的模型计算梯度 | 每个样本仅使用排在它前面的样本训练的模型计算梯度 |
| 目标泄漏 | 存在(每个样本的梯度隐含自身信息) | 消除(样本的梯度不依赖自身标签) |
| 预测偏移 | 存在 | 消除 |
| 训练效率 | 每轮只需训练一棵树 | 每轮仍只学一棵树的结构,但要维护多组支持模型的叶子值,计算更慢(论文实验中 Ordered 模式约比 Plain 模式慢 1.7 倍) |
| 近似方案 | 无 | 多个随机排列 + 只维护 $2^j$ 长度前缀的支持模型 |
| 理论分析 | 论文证明存在与样本量成反比的预测偏移(定理 1) | 残差由未见过该样本的模型计算,从构造上避免了这种偏移 |
8.3.3 近似实现:多组随机排列
如果严格按照 Ordered Boosting 的定义,每轮迭代需要为每个样本训练一个不同的模型,计算量不可接受。CatBoost 以遗忘树为基学习器,按如下方式实现(论文第 5 节):
- 生成 $s+1$ 个随机排列 $\sigma_0, \sigma_1, \dots, \sigma_s$。$\sigma_1, \dots, \sigma_s$ 用于评估分裂、确定树结构;$\sigma_0$ 用于计算最终模型的叶子值。用多个排列是因为在单个排列里,排在前面的样本“历史”很短,其目标统计和残差的方差都很大,多个排列可以降低最终模型的方差。
- 每轮随机选一个排列:第 $t$ 轮从 $\{\sigma_1, \dots, \sigma_s\}$ 中随机抽取 $\sigma_r$,类别特征的有序目标统计(8.5 节)和梯度都按这个排列计算。
- 共享树结构:维护支持模型 $M_{r,j}$,$M_{r,j}(i)$ 表示只用排列 $\sigma_r$ 中前 $j$ 个样本得到的、对样本 $i$ 的当前预测。建树时,样本 $i$ 使用梯度 $\mathrm{grad}_{r,\sigma_r(i)-1}(i)$,即只基于排在它前面的样本。评估候选分裂时,样本 $i$ 的叶子值由同一叶子中排在它前面的样本的梯度平均得到,再用余弦相似度衡量这些叶子值与梯度的吻合程度(对应参数
score_function,默认Cosine)。树结构确定后,同一个结构被加到所有支持模型上,只是各模型的叶子值不同。 - 最终模型的叶子值:所有树建好后,最终模型 $F$ 的叶子值按标准梯度提升的方式计算,样本按 $\sigma_0$ 下计算的目标统计落入叶子。对测试样本,目标统计使用全部训练数据计算。
- 降低复杂度:不保存全部 $O(s n^2)$ 个 $M_{r,j}(i)$,只保存和更新 $M'_{r,j}(i) := M_{r,2^j}(i)$($j = 1, \dots, \lceil \log_2 n \rceil$,且只对 $\sigma_r(i) \le 2^{j+1}$ 的样本),把需要维护的预测值降到 $O(s n)$。论文表 1 给出每轮的复杂度:计算梯度和更新支持模型都是 $O(s \cdot n)$,建树为 $O(\lvert C \rvert \cdot n)$($C$ 为候选分裂集合),因此与使用有序目标统计的标准 GBDT 渐近复杂度相同。
8.3.4 Ordered 与 Plain 两种模式
CatBoost 有两种提升模式,由参数 boosting_type 选择:
- Plain:标准的梯度提升流程;有类别特征时,仍按 $\sigma_1, \dots, \sigma_s$ 计算有序目标统计。
- Ordered:上面介绍的有序提升。
论文实验显示,Ordered 模式在小数据集上优势最明显,样本越少,Plain 模式的相对误差越大,这与定理 1“偏差与 $n$ 成反比”的结论一致。
默认值并不总是 Ordered 按当前官方文档,
boosting_type的默认值在 CPU 上是Plain;在 GPU 上,样本数不超过 5 万且不是多分类任务时默认Ordered,否则为Plain。需要有序提升时应显式设置boosting_type='Ordered'。无论哪种模式,类别特征都用有序目标统计处理。
8.4 Oblivious Trees(对称树/遗忘树)
8.4.1 结构特点:同层同特征同分裂条件
Oblivious Trees(又称对称树或遗忘树)是 CatBoost 使用的基础树结构。与传统决策树(如 CART、XGBoost、LightGBM 使用的树)不同,Oblivious Trees 具有严格的对称结构:
- 同一层所有节点使用相同的分裂特征。
- 同一层所有节点使用相同的分裂条件(分裂阈值相同)。
- 树的每个叶子对应一条从根到叶子的二进制路径(左/右选择序列),树总是完全平衡的满二叉树。深度为 $d$ 的遗忘树等价于一张有 $2^d$ 个格子的决策表(decision table):$d$ 个二元条件的取值组合决定落在哪个叶子。
graph TD
subgraph ObliviousTree["Oblivious Tree: 同层同特征同分裂条件"]
A["根节点
feature_A > 0.5"] --> B["Level 1
feature_B > 1.2"]
A --> C["Level 1
feature_B > 1.2"]
B --> D["Level 2
feature_C > 3.0"]
B --> E["Level 2
feature_C > 3.0"]
C --> F["Level 2
feature_C > 3.0"]
C --> G["Level 2
feature_C > 3.0"]
end
subgraph TraditionalTree["传统决策树: 不同节点不同分裂"]
H["根节点
feature_A > 0.5"] --> I["feature_B > 0.3"]
H --> J["feature_D > 2.1"]
I --> K["feature_C > 1.0"]
I --> L["feature_E > 0.8"]
J --> M["feature_F > 5.0"]
J --> N["leaf"]
end
8.4.2 优点:减少过拟合、加速预测
减少过拟合:
- 传统决策树在每个节点独立选择分裂特征,容易对训练数据的局部噪声过度拟合。
- Oblivious Trees 的强制对称结构限制了模型的灵活性,相当于一种强正则化,减少了过拟合风险(论文:“Such trees are balanced, less prone to overfitting”)。代价是单棵树的表达能力较弱,通常需要更多棵树。
- 对称结构意味着每个特征的影响在树的同一层被一致应用,避免了对特定数据子集的过度优化。
加速预测:
- 在传统决策树中,预测时需要从根节点开始,根据每个节点的分裂条件进行条件判断,路径长度等于树的深度。
- 在 Oblivious Trees 中,每一层的判断条件与样本走过的路径无关,所以 $d$ 个条件可以互相独立地同时计算,不需要逐层分支跳转。
- 更关键的是,Oblivious Trees 的叶子数固定为 $2^{d}$,每个叶子对应唯一的二进制编码。Dorogush 等人(2018)描述的预测器先把用到的特征、统计量都二值化,再把第 $t$ 棵树的叶子索引计算为
其中 $B(x, f) \in \{0, 1\}$ 是样本 $x$ 在二值特征 $f$ 上的取值,$f(t, i)$ 是第 $t$ 棵树第 $i$ 层使用的二值特征。叶子值存成长度为 $2^d$ 的数组,按索引直接读取,预测速度显著提升。
- 该论文在 Epsilon 数据集上、树的数量相近(限制为 8000 棵)的情况下测得:单线程时 CatBoost 预测耗时 2.4 s,XGBoost 为 78 s(约 32.5 倍),LightGBM 为 122 s(约 50.8 倍);32 线程时分别约为 19.5 倍和 74 倍,总结为“约比 XGBoost 快 25 倍、比 LightGBM 快 60 倍”。这一差距来自遗忘树结构与专门优化的预测器两方面,作者也说明这只是粗略的比较。
分裂查找的简化:
- 由于同层所有节点使用相同的分裂,每一层只需选出一个对整层所有节点综合最优的分裂(候选分裂的得分按该层所有叶子汇总计算),而非每个节点独立选择。
- 这进一步加速了建树过程。
- 除默认的
grow_policy='SymmetricTree'外,CatBoost 也支持Depthwise(逐层生长,但每个节点可以选不同的分裂)和Lossguide(按损失下降最大的叶子生长,配合max_leaves,默认 31)。按官方文档,depth的默认值为 6,使用Lossguide时为 16。
8.5 类别特征处理(Ordered Target Statistics)
8.5.1 公式推导
类别特征处理是 CatBoost 的核心优势之一。传统方法(如 one-hot 编码)在高基数类别场景下会产生高维稀疏特征;而目标编码(将类别替换为该类别的平均标签)虽然维度低,但存在严重的目标泄漏。
CatBoost 提出 Ordered Target Statistics(有序目标统计),为每个类别值计算目标统计量时,仅使用排列中排在当前样本之前的样本:
对于类别特征 $k$ 和类别值 $x_{ik}$,记 $\mathcal{D}_i = \{ j : \sigma(j) < \sigma(i) \}$ 为随机排列 $\sigma$ 中排在样本 $i$ 之前的样本集合,样本 $i$ 的有序目标统计量定义为:
$$ \hat{x}_{ik} = \frac{\sum_{j \in \mathcal{D}_i} \mathbb{1}_{[x_{jk} = x_{ik}]} \cdot y_j + a \cdot P}{\sum_{j \in \mathcal{D}_i} \mathbb{1}_{[x_{jk} = x_{ik}]} + a} $$如果事先把样本按 $\sigma$ 重新排好序,求和范围就是 $j = 1, \dots, i-1$(Dorogush 等人论文中的写法)。
符号表:
| 符号 | 含义 |
|---|---|
| $x_{ik}$ | 样本 $i$ 在类别特征 $k$ 上的原始类别值 |
| $\hat{x}_{ik}$ | 样本 $i$ 经过有序目标统计编码后的数值特征 |
| $y_j$ | 样本 $j$ 的目标标签 |
| $\mathbb{1}_{[x_{jk} = x_{ik}]}$ | 指示函数,当样本 $j$ 的类别值等于样本 $i$ 的类别值时为 1,否则为 0 |
| $a$ | 先验的权重($a > 0$),控制先验强度 |
| $P$ | 先验值:回归任务通常取标签的全局均值,二分类通常取正类的先验概率 |
| $\sigma$ | 训练样本的随机排列,充当人为的“时间顺序” |
8.5.2 避免目标泄漏的机制
为什么有序目标统计能避免目标泄漏?
关键在于分子和分母的求和范围是 $\mathcal{D}_i$,即只使用排在当前样本之前的样本计算统计量,这借鉴了在线学习中“只能看到历史数据”的思想。这意味着:
- 样本 $i$ 的目标标签 $y_i$ 不会被用于计算样本 $i$ 自身的类别编码。
- 因此,类别编码中不包含样本 $i$ 的目标信息,消除了目标泄漏。
- 在预测阶段,对于新样本,使用全部训练数据的统计量(因为新样本不存在于训练排列中)。
- 论文用两条性质概括好的目标统计:P1,训练样本与测试样本的编码在给定标签下分布一致(无条件偏移);P2,所有训练数据都能同时用于计算统计量和训练模型。贪心 TS 违反 P1,留出法违反 P2,有序 TS 同时满足两者。
先验平滑的作用:
- 当某个类别值在排列中首次出现时(即分母为 0),编码值会退化为全局先验 $P$。
- 参数 $a$ 控制先验的强度:$a$ 越大,编码值越接近全局先验,正则化效果越强。
- 这在处理低频次类别(训练集中出现次数很少的类别)时尤为重要,防止对这些类别过拟合。
多排列增强:
- 只用一个排列时,排在前面的样本“历史”很短,其编码的方差远大于排在后面的样本。因此 CatBoost 在不同的提升轮次使用不同的排列:每轮从 $\sigma_1, \dots, \sigma_s$ 中随机选一个,按它计算这一轮建树用的目标统计(见 8.3.3)。
- 注意这不是把多个排列的编码取平均:Dorogush 等人指出,直接使用多个排列算出的统计量会导致过拟合,CatBoost 是靠 8.3.3 的叶子值计算方式来避免这个问题的。
- 有序 TS 与有序提升必须使用同一个排列($\sigma_{\text{cat}} = \sigma_{\text{boost}}$),这样才能保证样本 $i$ 的标签既不参与它自身的编码,也不参与计算它梯度的模型。
8.5.3 特征组合(Feature Combinations)
把类别特征逐个转换成目标统计会丢失特征之间的交互信息。例如在音乐推荐中,“用户 ID”和“音乐类型”分别编码后,就无法表达“某个用户偏好摇滚”这一信息,而两者的组合作为一个新类别特征却能直接表达。组合的数量随类别特征数指数增长,无法全部枚举,CatBoost 采用贪心策略(Dorogush et al., 2018;Prokhorenkova et al., 2018):
- 树的第一次分裂不考虑组合。
- 之后每次分裂时,把当前树中已经用过的所有类别特征(及其组合)与数据集中的所有类别特征逐一拼接,生成新的组合特征作为候选。
- 树中已选用的数值特征分裂(形如“数值特征 > 阈值”)也被视为取两个值的类别特征,可以参与组合。
- 组合特征在训练过程中实时转换为目标统计。
一个组合中最多包含的特征数由参数 max_ctr_complexity 控制(默认 4;GPU 上的多分类任务中类别特征默认为 1)。
8.5.4 其他实现细节:CTR 类型、多先验与 one-hot
- 计数统计:除目标统计外,CatBoost 还可以用类别在数据集中出现的次数作为数值特征(CTR 类型
Counter),这对特征组合同样适用。 - 多个先验:为了在每一步找到合适的先验,CatBoost 会同时尝试多个先验,并为每个先验各构造一个特征。
- CTR 类型:CPU 上可用
Borders、Buckets、BinarizedTargetMeanValue、Counter等,通过simple_ctr、combinations_ctr参数配置(官方文档 Categorical features 参数页)。 - 低基数类别直接 one-hot:类别数不超过
one_hot_max_size的特征直接做 one-hot,不计算 CTR。按官方文档,一般情况下默认值为 2(只有两个取值的类别特征直接 one-hot),Ranking 模式下为 10,GPU 上某些情况下为 255。 - 时间顺序数据:设置
has_time=True时,CatBoost 不再随机打乱,而是直接使用输入数据的顺序作为“时间”来计算有序统计与有序提升,适用于样本本身有时间先后的场景。
8.6 Python API与关键参数
CatBoost 提供功能丰富的 Python API,原生支持类别特征(字符串或整数均可,但不能是浮点数,类别列中的缺失值需先填成字符串等取值)。
原生接口(CatBoostClassifier / CatBoostRegressor)
| |
关键参数详解
| 参数 | 含义 | 默认值 | 调参建议 |
|---|---|---|---|
iterations | 迭代次数(树的数量) | 1000 | 配合 learning_rate 调整,通常 500-2000。 |
depth | 树深度(Oblivious Tree层数) | 6(Lossguide 时为 16) | 控制模型复杂度。增大可捕获更复杂模式,但易过拟合。典型值 4-10。 |
learning_rate | 学习率 | 自动确定 / 0.03 | 对 Logloss、MultiClass、RMSE 损失,若未设置 leaf_estimation_iterations、leaf_estimation_method、l2_leaf_reg,会根据数据和迭代次数自动选择学习率(并打印出来);其他情况默认 0.03。典型值 0.01-0.3。 |
boosting_type | 提升模式 | CPU:Plain | Ordered(有序提升)或 Plain。GPU 上样本数不超过 5 万且非多分类时默认 Ordered。小数据集可尝试 Ordered。 |
l2_leaf_reg | 叶子L2正则化 | 3.0 | 惩罚大叶子权重,防止过拟合。典型值 1-10。 |
random_strength | 分数随机强度 | 1.0 | 选择分裂时给每个候选分裂的得分加上均值为 0 的正态噪声,噪声方差随训练进行逐渐减小,该参数是方差的乘数。增大增加正则化。 |
bootstrap_type | 样本采样方式 | CPU(非多分类):MVS(subsample=0.8);否则多为 Bayesian | 可选 Bayesian、Bernoulli、MVS、Poisson(仅 GPU)、No。 |
bagging_temperature | 贝叶斯bootstrap温度 | 1 | 仅在 bootstrap_type='Bayesian' 时生效。为样本随机赋权:0 表示所有权重都为 1(不采样),1 表示权重服从指数分布,值越大采样越激进。 |
border_count | 数值特征切分点数 | CPU:254;GPU:128 | 数值特征量化的边界数(别名 max_bin)。增大可提升精度,增加计算量。 |
one_hot_max_size | one-hot 阈值 | 一般为 2 | 类别数不超过此值的类别特征直接 one-hot,不计算目标统计。 |
max_ctr_complexity | 特征组合的最大特征数 | 4 | 控制类别特征组合的阶数(8.5.3)。 |
grow_policy | 生长策略 | SymmetricTree | SymmetricTree(Oblivious Tree)、Depthwise(Level-wise)、Lossguide(Leaf-wise)。 |
cat_features | 类别特征索引 | None | 指定类别特征列索引,CatBoost自动处理。 |
8.7 详细注释的Python代码示例
| |
第三部分总结:本部分详细阐述了 XGBoost、LightGBM 和 CatBoost 三大现代梯度提升实现的数学原理、核心算法与工程优化。XGBoost 以二阶泰勒展开和显式正则化奠定了现代树提升的理论基础;LightGBM 通过直方图、Leaf-wise、GOSS 和 EFB 实现了大规模数据上的高效训练;CatBoost 则通过 Ordered Boosting 和有序目标统计系统性地解决了预测偏移和类别特征处理问题,并以 Oblivious Trees 兼顾正则化与预测速度。三者各有侧重,在实际应用中应根据数据规模、特征类型和性能需求选择最合适的工具。
