你可能不知道的对称树和GBM模型的快速预测

想必大家都已经很熟悉gradient boosting machine（GBM）和它的各种实现软件包——比如R中的gbm包，和已经在各种机器学习竞赛中成绩斐然的xgboost。GBM本质上是ensemble模型，也就是利用不同的weak learner组合起来得到一个效果更好的模型。

和deep learning一样，GBM也有overfit甚至perfect fit的能力，这一点在实际应用中很重要。overfit能力强，也就是可塑性强，然后我们要解决的问题就是如何把模型训练的“恰好”。GBM的软件包通常都有early stopping的功能，early stopping让我们可以尽量的去训练一个“恰好”的模型。有时候我会想GBM和增强学习中的explore & exploit思想有相通之处。具体来说，每一次我们训练一个新的weak learner的时候，我们会选一个新的随机样本（random sample），在这个随机样本上面我们先用已经训练好的模型进行预测，这其实就是exploit的过程，然后我们根据这个随机样本上的真实值和预测值计算residual（残差）来训练新的树，这像是explore的过程。线性回归模型就缺乏很强的overfit能力。如果实际数据恰好符合线性模型的关系，那我们可以得到很好的结果，可是如果实际数据不符合线性模型的关系呢？我们可能就需要做特征工程（feature engineering）了。可是特征工程又是一个比较主观的过程。关于特征工程，这里我们就不多讨论了。

我们回到文章的标题——对称树。关于GBM的理论我们不用多说，各种文章书籍都说的很清楚，这里我们就来讲一讲大家可能不知道的吧，symmetric or oblivious trees（暂且翻译成对称树）。大多数的GBM中使用的都是普通的决策树，比如下面的这个树。

上面这棵树中，第二层中左右两个节点的判断条件不同。如果一个样本进入了左面的节点，下一个问题是是否关注了“机器会学习”，如果进入了右面的节点，下一个问题则是“喜欢tensorflow”还是“pytorch”。

那么对称树呢？和普通决策树有什么区别？

对称树中，每一层的每一个节点判断条件都是一样的。假如如果我们只训练一棵树，那么显然对称树的overfit能力会比普通的决策树弱；但是在GBM中，我们通常训练很多的树，所以overfit的能力不必担心。那么对称树在GBM中有什么优势呢？下面列出三点：

拟合模式相对简单，因为每一层都是一个判断条件

可以提高预测速度

对称树的结构本身比普通决策树自由度小，可以看作是加入了penalty，或者看作regularization

我认为最大的优势就是第二点——预测速度会提升。为什么会更快呢？

上面这棵树最底层有四个节点，我们可以把这四个节点从0到3编号（index），每一个节点有一个对应值（value）。比如一个样本最终进入了第一个节点，那么这棵树对这个样本的预测值就是1.6。我们可以把value存放在一个数组里面，这样给定index就可以立刻得到value。那么对一个样本用一棵树进行预测时，我们只需要找到这个样本对应的index，因为在对称树中每一层的判断条件都是一样的，所以每一层都可以用0或者1来表示，比如是学生，用1表示，不是用0；有关注机器会学习用1表示，没有用0，那么每一个样本进入这棵树，都可以用两个bits来表示，也就是四种可能结果：00，01，10，和11。这两个bits代表的数字就是index。这意味着什么呢？我们在做预测的时候，只要对每一层的条件进行判断，然后就可以找到index。因为每一个树的结构（判断条件）是已知的，我们甚至可以对这个过程进行并行计算。

目前对称树在catboost中已经实现，xgboost和lightgbm都依然使用传统的决策树结构。传统的决策树对每一个样本进行预测时都要从根节点遍历这棵树，但是应用catboost中的对称树我们只要进行数组的操作。下面的模型预测速度对比结果来自catboost的官方网站[3]（40万样本，2000个特征），可见对称树在预测速度上的优异表现。

参考文献

[1]http://learningsys.org/nips17/assets/papers/paper_11.pdf

[2]https://devblogs.nvidia.com/catboost-fast-gradient-boosting-decision-trees/

[3]https://catboost.ai/news/best-in-class-inference-and-a-ton-of-speedups

希望大家点赞或者转发支持，你们的支持就是我们创作的最大动力！