CatBoost算法理论

概述

CatBoost是俄罗斯的搜索巨头Yandex在2017年开源的机器学习库，是Boosting族算法的一种。CatBoost和XGBoost、LightGBM并称为GBDT的三大主流神器，都是在GBDT算法框架下的一种改进实现。XGBoost被广泛的应用于工业界，LightGBM有效的提升了GBDT的计算效率，而Yandex的CatBoost号称是比XGBoost和LightGBM在算法准确率等方面表现更为优秀的算法。

CatBoost是一种基于对称决策树（oblivious trees）为基学习器实现的参数较少、支持类别型变量和高准确性的GBDT框架，主要解决的痛点是高效合理地处理类别型特征，CatBoost是由Categorical和Boosting组成。此外，CatBoost还解决了梯度偏差（Gradient Bias）及预测偏移（Prediction shift）的问题，从而减少过拟合的发生，进而提高算法的准确性和泛化能力。

算法特点

Catboost自动采用特殊的方式处理类别型特征（categorical features）。首先对categorical features做一些统计，计算某个类别特征（category）出现的频率，之后加上超参数，生成新的数值型特征（numerical features）。Catboost通过该方法提供了自动处理类别特征的能力，解决了算法工程需要对类别特征进行特殊处理的痛点问题。
Catboost使用组合类别特征，可以利用到特征之间的联系，从而极大的丰富了特征维度。
Catboost采用ordered boost的方法避免梯度估计的偏差，进而解决预测偏移的问题。
Catboost的基模型采用的是对称树，同时计算leaf-value方式和传统的boosting算法也不一样，传统的boosting算法计算的是平均数，而catboost在这方面做了优化采用了其他的算法，这些改进都能防止模型过拟合。

Catboost优缺点

Catboost优点

性能卓越：在性能方面可以匹敌任何先进的机器学习算法；
鲁棒性/健壮性：它减少了对很多超参调优的需求，并且降低了过拟合的概率，增强了模型的泛化能力；
易于使用：提供与scikit集成的Python接口，以及R和命令行界面；
实用：可以处理类别型、数值型特征；
可拓展：支持自定义损失函数；
支持类别型变量，无需对非数值型特征进行预处理；
快速、可拓展的GPU版本，可以使用基于GPU的梯度提升算法训练模型，支持多卡并行；
快速预测，对延时非常苛刻的任务也能快速高效的部署模型。

Catboost缺点

对于类别型特征的处理需要大量的内存和时间；
不同随机数的设定对于模型预测结果有一定的影响；

与XGBoost、LightGBM相比，CatBoost的创新点有：

CatBoost创新点

嵌入了自动将类别特征处理为数值型特征的创新算法。首先对categorical features进行统计，计算某个类别特征（category）出现的频率，之后加上超参数，生成新的数值型特征（numerical features）；
Catboost使用组合类别特征，可以利用到特征之间的联系，极大丰富了特征维度；
采用排序提升的方法对抗训练集中的噪声点，从而避免梯度估计的偏差，进而解决预测偏移的问题；
采用完全对称树作为基模型；
采用一种新的算法计算leaf-values。

算法原理

Ordered Target Statistics

对于类别特征，如果类别数目不多，可以使用onehot编码。否则，很容易造成维度爆炸。CatBoost不提倡使用one-hot编码，它设计了一种基于预测目标统计值的方法可以将类别特征转化为数值特征。颇有均值编码的思想。

CatBoost算法的设计初衷是为了更好的处理GBDT特征中的categorical features。在处理GBDT特征中的categorical features的时候，最简单的方法是用 categorical feature对应的标签的平均值来替换。在决策树中，标签平均值将作为节点分裂的标准。这种方法被称为 Greedy Target-based Statistics , 简称 Greedy TS，用公式来表达就是：

然而，这种方法有一个显而易见的缺陷，即通常特征比标签包含更多的信息，如果强行使用标签的平均值来表示特征的话，当训练数据集和测试数据集数据结构和分布不一样的时候会出条件偏移问题。

CatBoost 使用一个更有效的策略，一方面可以减少过拟合，另一方面使用全部数据来训练。对数据集先随机排序，对于每个样本的该类别特征中的某个取值，转换为数值型时都是基于该样本之前的类别label value取均值，同时加入了优先级（先验值）的权重系数。

假设 $/sigma=(/sigma_1,/sigma_2,...,/sigma_n)$ 是随机排列序列，则有：

[·]代表指示函数，P就代表先验，对应回归任务，计算标签的平均值为先验值；对于二分任务，将正类的出现概率作为先验值。 $/alpha$ 就代表优先级的权重系数，用来防止低频次特征带来的影响所有的平滑操作，如果不使用这个操作的话，当对于某一个特征只有一个样本的时候，其特征编码就是1，会有过拟合的风险。
这种类别标签处理方法就是Ordered Target Statistics数值编码方法，可以有效解决预测漂移的问题。

基于贪心策略的特征交叉方法

使用Ordered Target Statistics方法将类别特征转化成为数值特征以后，会影响到特征交叉，因为数值特征无法有效地进行交叉。为了有效地利用特征交叉，CatBoost在将类别特征转换为数值编码的同时，会自动生成交叉特征。但如果让全部的类别特征之间都进行交叉，两两交叉，三三交叉，四四交叉，这个复杂度是指数级的，特征维度一定会爆炸。

CatBoost使用一种贪心的策略来进行特征交叉。生成tree的第一次分裂，CatBoost不使用任何交叉特征。在后面的分裂中，CatBoost会使用生成tree所用到的全部原始特征和交叉特征跟数据集中的全部类别特征进行交叉。

参数max_ctr_complexity用于控制特征交叉的最大个数。

避免预测偏移的Ordered Boosting方法

使用XGBoost或者LightGBM做模型时，可能会出现模型在训练集上拟合的很好，train_auc甚至达到了1.0；但是在验证集上变差的问题, val_auc 可能只有0.7。这当然有可能是因为tree的数量太多了，或者是每棵tree的leaves太多了，即模型太复杂了造成了过拟合。

此外，这也可能是由于XGBoost和LightGBM自身算法的缺陷因素导致。LightGBM在训练下一棵tree的时候，需要计算前面这些tree构成的加法模型在所有样本上的一阶梯度和二阶梯度(Loss对模型预测结果的导数)，然后用这些梯度来决定下一棵树的结构和叶子节点取值。

然而，计算一阶梯度和二阶梯度值是有问题的。前面的这些tree都是在这些样本上训练的，现在又在这些样本上估计模型预测结果的一阶和二阶梯度。显然，应该换一些新的样本才更合理。

在CatBoost中，先将样本随机打乱，然后每个样本只使用排序在它前面的样本来训练模型。用这样的模型来估计这个样本预测结果的一阶和二阶梯度。然后用这些梯度构建一棵tree的结构，最终tree的每个叶子节点的取值，是使用全体样本进行计算的。

这就是Ordered Boosting的主要思想。可以有效地减少梯度估计的误差，缓解预测偏移。但是会增加较多的计算量，影响训练速度。

在定义CatBoost模型时，可以用boosting_type这个参数来设置是使用Ordered Boosting还是LightGBM那样的Plain Boosting。如果不显式设置，CatBoost会根据样本和特征数量自行决定。

详细步骤

构建一棵树有两个阶段：第一，选择树结构；第二，在树结构固定后计算叶节点的值。CatBoost在第二阶段采用传统GBDT方法执行，在第一阶段则采用修正的方法——梯度步长的无偏估计。

令 $F^i$ 为前 $i$ 棵树的模型结构，为了使 $g^i(X_k,Y_k)$ 是关于模型 $F^i$ 的无偏梯度，需要在训练的时候不使用样本k。
样本集为 $\lbrace(X_k, Y_k)\rbrace^{n}_{k=1}$ 按随机排序 $\sigma$ 排序，树的棵树为 $I$ 。

首先，对于样本 $X_k$ ,初始化模型 $M_k$ ；
对于每一棵树，遍历一次样本，对于前 $k-1$ 个样本，一依次计算Loss的梯度 $g^i$ ;
再次将前 $k-1$ 个样本的 $g^i$ 和 $X^j(j=1,\dots,k-1)$ 来构建模型 $M$ ；
最后，对于每一个样本 $X_k$ ，用 $M$ 来修正初始化的 $M_k$ ，这样就可以得到一个分隔的模型 $M_k$ （并且这个模型不需要这个样本用梯度估计来更新）。重复上述操作，就可以得到每个样本 $X$ 的分隔模型 $M$ 。由此可见，每一个 $M_k$ 都共享相同的树结构。

使用对称二叉树作为基模型

XGBoost和LightGBM采用的基模型是普通的二叉树，但是CatBoost采用的是对称二叉树。

这种对树结构上的约束有一定的正则作用。更为重要的是，它可以让CatBoost模型的推断过程极快。

对于CatBoost的tree的预测过程来说，每个特征的分裂都是独立的，不分先后顺序，多个样本可以一起预测。

基于GPU的加速训练

密集的数值特征：对于任何GBDT算法而言，最大的难点之一就是搜索最佳分割。尤其是对于密集的数值特征数据集来说，该步骤是建立决策树时的主要计算负担。CatBoost使用oblivious决策树作为基模型，并将特征离散化到固定数量的箱子中以减少内存使用。就GPU内存使用而言，CatBoost至少与LightGBM一样有效。主要改进之处就是利用了一种不依赖于原子操作的直方图计算方法。
类别型特征：CatBoost实现多种处理类别型特征的方法，并使用完美哈希来存储类别型特征的值，以减少内存使用。由于GPU内存的限制，在CPU RAM中存储按位压缩的完美哈希，以及要求的数据流、重叠计算和内存等操作。通过哈希来分组观察。在每个组中，我们需要计算一些统计量的前缀和。该统计量的计算使用分段扫描GPU图元实现。
多GPU支持：CatBoost中的GPU实现可支持多个GPU。分布式树学习可以通过数据或特征进行并行化。CatBoost采用多个学习数据集排列的计算方案，在训练期间计算类别型特征的统计数据。