Press "Enter" to skip to content

一文读懂 CatBoost 算法原理(附代码)

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

 

 

 

一、背景

 

 

 

我们来看看与XGBoost和LightGBM并列为数据挖掘类比赛三大杀器中的CatBoost[1]
。作为“后浪” (2017年代码开源,2018年论文发表),CatBoost解决了
预测偏移 (Prediction Shift)
。那什幺是预测偏移?预测偏移发生在哪里?别急,往下看就知道了。

 

1. 什幺是预测偏移?

 

在GBDT一类模型中,弱学习器模型均在同一完整训练集上训练,然后不断提升成强学习器,但如果训练集和测试集存在分布不一致,模型就会过拟合训练集而在测试集上表现不好 (即预测偏移到训练集上),预测偏移也算是
目标泄露 (Target Leakage)
的一种。

 

2. 预测偏移发生在哪里?

 

预测偏移发生在两个地方:
类别特征编码

梯度提升方法

 

(1) 类别特征编码中的预测偏移

 

1) GBDT
:直接把类别型当作连续型数据对待。

 

2) XGBoost
:建议提前对类别特征One-hot编码后再输入模型。

 

3) LightGBM
:在每步梯度提升下,将类别特征转为
GS
(梯度统计Gradient Statistics)。

 

注:很对不起,

【务实基础】LightGBM

中 “5. 支持类别特征
” 这块存在错误,LGBM不是采用TS编码 (目标统计Target Statistics,即平均值
),而是GS编码,将类别特征转为累积值
(一阶偏导数之和/二阶偏导数之和) 再进行直方图特征排序
[2]。

 

Ai,公众号:宅码【务实基础】LightGBM

 

虽然LGBM用GS编码类别特征看起来挺厉害的,但是存在两个问题:

 

计算时间长
:因为每轮都要为每个类别值进行GS计算。

 

内存消耗大
:对于每次分裂,都存储给定类别特征下,它不同样本划分到不同叶节点的索引信息。

 

为了克服以上问题,LGBM将长尾特征聚集到一类,但也因此丢失了部分信息。对此,CatBoost作者认为,LGBM的GS没有TS好,因为
TS省空间且速度快
,每个类别存一个数就好了。但TS不是完美的,因为它
存在预测偏移
。这很明显,因为TS是依赖训练集的目标标签进行类别特征编码(算是目标泄露),如果训练集和测试集分布过大,那幺类别编码就会偏移向训练集,导致模型的通用性差。

 

如果我们要了解“
预测偏移是怎幺发生在TS类别特征编码 (也称目标编码Target Encoding) 过程当中?
”,我们得先了解下TS的编码机制。

 

一个有效且高效处理类别型特征

的方法是用一个TS编码的数值型变量

来替代第

个训练样本的类别

。通常来说,TS是基于类别的目标变量y的期望来进行估算:

。直白来说,

是TS编码值,

是基于目标变量

估算函数。

 

 

 

图1:Greedy TS编码方式

 

估算函数最直接方式就是
采用训练集中相同类别的

样本的目标变量y的平均值
,如上图所示。这种估算方式在低基类别上有噪声,因此常常会加先验概率p进行平滑:

 

指示类别

指示样本

。而

的意思是判断:当前样本j是否与样本

是同一类别

,如果是则为1,反之则为0。而先验概率

为数据集所有目标值的均值,

是控制先验参与编码的权重。

 

现在,我们举个具体的例子,看下预测偏移是怎幺影响模型通用性。假设特征

为类别型且它的值都是独特的 (unique)。那幺如果TS编码就会发生严重的目标泄露,如下图所示:

 

 

 

图2:Greedy TS编码出现目标泄露的样例

 

有几种方法可以避免条件偏移 (Conditional shift)。其中一个通用的想法是

计算其TS时,用除去

后的样本集

去计算

 

(2) 梯度提升方法中的预测偏移

 

我们已经知道TS因目标泄露带来预测偏移。那接下来,我们来看下GBDT一类模型中,它们梯度提升方法里的预测偏移是在哪发生的。我们先简单回顾下GBDT的梯度提升方法。假设我们上一轮获得强学习器

,那幺,当前第

轮下的强学习器为:

为第

轮的弱学习器,

为学习率。

目标是使损失函数最小化:

 

最小化问题可通过牛顿法或梯度下降求解。在梯度下降中,GBDT是用损失函数的负梯度去帮助拟合,负梯度如下:

 

还记得我在之前文章里说过,GBDT当前轮的弱学习器是拟合上一轮的负梯度值,因此,

可以为:

 

如果
训练集和测试集分布不一致
,那幺用训练集得到的梯度值分布就跟测试集的
梯度值分布不一致
,那幺便会有预测偏移,最终影响了模型的通用性。

 

二、原理优化

 

 

 

CatB
oost针对
类别特征TS编码
时发生的预测偏移采用了
Ordered TS
方法,针对
梯度提升方法
中的偏移采用
Ordered Boosting
方法。

 

1. Ordered TS

 

之前在背景里有讲Greedy TS的编码思路,但其实还有其它TS编码方式。这里,我根据论文整理了下Greedy TS、Holdout TS和Leave-one-out TS的编码思路对比图如下:

 

 

 

图3:其它常见TS编码方式对比图

 

我们发现,常见的TS的编码方式没有平衡好”
充分利用数据集
“和”
避免目标泄露
“。CatB
oost作者受到在线学习算法 (即随时间变化不断获取训练集) 的启发,提出了Ordered TS。Ordered TS是基于排序原则,对于每个样本的TS编码计算是依赖于可观测的样本。为了使这个想法符合标准线下设定,作者人为构造了”时间“。具体步骤如下:

 

(1)
随机
打乱训练集
,获取一个随机排列顺序

 

(2)
在训练集中,

的”历史“样本去计算样本

的TS
,即训练集用

 

(3)
在测试集中,用全测试集数据去计算

的TS。

 

该方法既充分利用了数据集,又避免了目标泄露。注意如果只用一个随机排列顺序,那幺最早进行TS编码的样本会比后面才TS编码的样本具有更高方差 (即
先编码比后编码更欠拟合
),因此,CatB
oost
在不同梯度提升轮数中采用不同的排列顺序去计算TS,这样模型的方差会变低,利于拟合

 

便于理解,我画了Ordered TS的计算样例图:

 

 

 

图4:Ordered TS示意图

 

如图4所示,如果我们对打乱顺序后ID为6的样本进行TS编码,会先将样本4、3、7、2作为历史样本,然后使用它们去计算样本6的TS编码,由于只有样本4和样本6为同类特征,二样本6不参与自身的TS计算,所以最后样本6的TS为

。注意:图4展示的是训练集的TS编码过程,而
测试集TS编码是用全测试集进行计算
的。

 

2. Ordered Boosting

 

假设我们有无限的训练数据,我们可以轻松构建一个算法。每步提升中,我们独立采样一个新数据

,然后对新采样的数据集应用现有模型,便可获得无偏残差 (Unshifted Residuals)。但现实中,带标注的数据是有限的。如果我们用I颗树学习一个模型,为了使残差

不偏移,我们需要训练模型

时不用样本

。因为我们需要计算所有样本各自的无偏残差,所以训练模型

不用任何样本才行。第一样看上去,不可能吧,怎幺可能模型训练不使用样本?但是,我们可以搞一堆模型,然后每个模型用不同的样本去训练。听起来有点迷糊,我们先看一张图:

 

 

 

图5:传统提升和排序提升的残差计算对比

 

图5展示了传统提升和排序提升中残差计算的对比:

 

传统残差计算法:第t轮的输入残差可通过上一轮

的模型预测值与样本真实值做差得到。而因为残差计算中的模型

是用全部数据集训练的,所以容易预测偏移。

 

排序提升残差计算法
:CatB
oost基于排序提升原则去计算残差,例如样本4的残差计算是用前3个样本训练得到的模型预测值与样本真实值做差,这样的话,样本4的残差计算没有让样本4自身参与进去,这样可以避免了预测偏移,因为得到的是无偏残差。

 

看起来排序提升残差计算法更好,但它需要留意以下几点:

 

(1)
计算残差需要

个不同模型
。所以Catboost中,作者在CatB
oost的梯度提升算法中做了些修改,详见后续伪代码部分。

 

(2)
TS计算与残差计算所用样本顺序是一样的,即

,才能保证预测不偏移。

 

(3)
同理Ordered TS,单用一个顺序

会增加最终模型的方差,所以
每次提升都采用不同的

,以避免模型欠拟合。

 

Catboost有两种提升模式:Ordered
和Plain
,后者是标准GBDT算法搭配Ordered TS,前者是Ordered TS + Ordered Boosting。前面讲了Ordered Boosting下的残差计算方式,现在我们正式来看下
CatB
oost是怎幺建树
的。CatB
oost是用
对称树 (Oblivious Decision Tree)
作为弱学习器,对称意味着树同一层都使用相同分裂标准。对称树是平衡的,不易过拟合,且能显着加速测试执行时间。具体伪代码如下所示:

 

 

 

图6:CatB
oost建树伪代码

 

首先,Cat
B
oost对训练集生成

个独立随机排列序列。
序列

用于评估树分裂情况,以帮助定义树结构。

用于为给定树选择叶子节点值


在Orderd Boosting模式中,我们维持一个模型

,它
是学习序列

里前

个样本的模型,然后对第

个样本预测。在算法迭代

轮下,我们从

中随机选一个序列

,并基于此构建一棵树

。首先,对于类别型数据,TS编码在序列

下完成。然后,该序列继续影响树的学习。即,基于

,我们计算对应得梯度

。之后,当构建树时,我们使用余弦相似度

估计梯度

,其中,对每个样本

,我们取梯度

(该梯度只基于序列

的历史样本计算)。在每轮评估候选分裂点时,第

个样本的叶子节点值

是与样本

同属相同叶子节点

的历史样本

的梯度值

求均值所得。注意:

是依赖于序列

,因为

会影响样本

的Ordered TS值。当树结构

(即分类特征顺序)确定了,我们会用它提升所有模型

。作者强调:
所有模型

都是共用一个相同树结构

,但是根据

设置不同叶子节点值应用在不同

的。具体过程如图6所示。

 

Plain Boosting模式跟标准GBDT流程类似,但如果出现类别特征,他会对应

个序列,维持

个模型

 

3. 特征组合

 

Catboost捕捉高阶依赖的类别特征组合成额外的类别特征,例如广告点击预测中的用户ID和广告话题。特征组合随数据集的类别特征数量增加呈指数型增长,这不太好。所以Catboost使用贪婪策略构建特征组合,即,对一个树的每个分裂点,Catboost会组合所有现有树中已被历史分裂使用过的类别特征 (和它们的组合)。

 

三、对比LightGBM

 

 

 

图7:CatBoost与LGBM的对比

 

四、代码参考

 

CatB
oost的样例代码参考如下,受限于篇幅,这里不做过多详细展开,详见官方文档[3]

 

from catboost import CatBoostClassifier, Pool, cv
from sklearn.metrics import accuracy_score


model = CatBoostClassifier(
    custom_loss=['Accuracy'],
    random_seed=42,
    logging_level='Silent'
)


model.fit(
    X_train, y_train,
    cat_features=categorical_features_indices,
    eval_set=(X_validation, y_validation),
    plot=True
)


predictions = model.predict(X_test)

 

参考资料:

 

[1] Prokhorenkova, L., Gusev, G., Vorobev, A., Dorogush, A. V., & Gulin, A. (2018). CatBoost: unbiased boosting with categorical features. In Advances in neural information processing systems (pp. 6638-6648).

 

[2] https://lightgbm.readthedocs.io/en/latest/Features.html#optimal-split-for-categorical-features

 

[3] CatBoost官方文档:[https://catboost.ai/docs](https://catboost.ai/docs)

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。