上手机器学习系列-第7篇（下）-CatBoost论文阅读笔记

前言

在第7篇（上），我们介绍了CatBoost的代码实践，本篇来一起读一下算法原创论文《CatBoost: unbiased boosting with categorical features》，以期加深对于CatBoost的理解。

 

论文中心思想

笔者提炼了一下论文的核心逻辑如下图所示：

所以最核心的是要理解论文提出的排序原则到底是咋回事。

 

内容导读

CatBoost方法给笔者的第一印象是它可以直接处理类别型变量，但读论文时才发现它其实初心的目标是解决boosting集成算法中出现的“预测偏移”问题，只是说在类别型变量的处理过程中使用的方法也恰好同样会出现类似的问题，就使用同一种方法解决了。所以笔者觉得论文其实应该把第4部分的内容（讲预测偏移）与第3部分（讲类别变量的处理）换一下顺序。所以本文解读时换个顺序来聊。

预测偏移

作者在这一部分论证说，boosting集成学习算法都会遇到“prediction shift”（笔者本文姑且翻译为预测偏移）的问题，且在以往未得到识别，甚至就是否存在非零的偏移问题都未在理论上得到过证实。但作者自己在论证时只是在一个平方和损失函数的回归问题场景下进行了讨论，且设定了预测函数为一个多项式函数。

作者得到了下面这样一个表达式结论，其中对偏移的量还进行了量化表达。

坦白讲，这一段论证，笔者没有太get到这里的逻辑，大家后续看的过程中如有心得，欢迎评论留言讨论。

那怎么通俗地理解prediction shift？
用作者的语言是：

The distribution F(x_k) | x_k for a training example shifts from the distribution of F(x) | x for a test example x.

作者提到的其它有讨论prediction shift的论文《Using Iterated Bagging to Debias Regressions》，扒一下里面的内容，可以找到一段这样的描述：

到这里，笔者定性地理解是，我们每一轮训练新的弱学习器时，本来是想拟合前一轮所得模型对于真实函数的逼近程度，但因为所有样本都参与了梯度（或者说残差）的计算，然后又去最小化损失函数，而每个训练数据的目标值本身也有系统偏差，那就把这个系统偏差也加到了拟合的过程中去。有点类似于我们在普通的有监督学习中，直接让测试集也参与了损失函数的最优化计算，那就可能导致过拟合了。解决的方法也就比较直观了，留出一个类似的“测试集”，在计算每一个样本的梯度时，不要让它自身参与计算。这个思路与讨论类型变量处理时的“Holdout TS”是相似的。

为了解决prediction shift的问题，作者提出了基于排序的boosting方法。过程原理论述的还是比较清楚的，整理逻辑如下：

这里训练的模型要比通常的GBDT多很多。回忆一下，GBDT中，在第t-1轮训练提到的回归树，在第t轮被用于所有样本上的负梯度（平方和损失函数场景下也就是残差）计算；而这种ordered boosting的方法，在每个新的弱学习器训练过程中，都要训练n个模型，每次用前i-1个样本训练得到的模型来计算第i个样本的残差。

类别变量

对于类别型变量而言，如果直接进行one-hot-encoding处理，在类别值特别多的情况下，就会衍生了大量的新变量，使得数据变得很稀疏。一种常用的方法是先将类别值进行分组（或聚类），然后再进行one-hot-encoding。但类别值本身无法对比大小与计算距离，因此需要进行数值化表达。Target Statistics就是这样一种将类别值转化为数值的方法。计算方法如下式：

别看这个公式长得麻烦，其实想法挺朴实的。就是用每个类别所在样本的目标值来近似表达类别值本身，直接用对应目标变量的均值的话，如果少数类别的样本量较少，可能就会受到极值的影响（还记得吗，平均值这种统计值本身就容易受到异常点的干扰），所以加了一个平滑的处理。

作者又提到说单纯的TS计算会导致target leakage。所以又提出了变种的方法，包括Holdout TS、Leave-one-out TS、Ordered TS。最终采用的是Ordered TS这种方法，其原理在论文中是这样描述的：

结语

事实上，仅读一篇论文肯定是不足以充分get到一个算法的精髓的，我们读了本篇论文也只能算入门。对于Catboost，下面这个网站https://www.kaggle.com/abhinand05/catboost-a-deeper-dive给了一些相关的学习材料，读者可以自行去找来读读，也欢迎大家就学习心得在留言区讨论交流~