本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.
一、背景
我们来看看与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, cvfrom sklearn.metrics import accuracy_scoremodel = 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