Facebook提升数十亿用户体验的秘密武器：梯度提升决策树

机器之心报道

Facebook 使用机器学习和排序模型给所有用户带来最佳体验，例如发送什么通知，在你的消息推送中放入什么文章，以及对于你想关注的人提些什么建议。高质量的机器学习模型对于找出最相关的内容来说很重要。我们观察了大量实时信号以制定最佳排序；例如，在过滤通知的使用情况中，我们观察某人是否已点击相似的通知，或者对应通知的文章获得了多少赞。由于每执行一次就会生成一个新通知推送，所以我们想要尽快返回发送通知的决策。

更复杂的模型有助于提高预测的精度，提供更相关的内容。但更复杂的模型需要更长的 CPU 周期（CPU cycles），返回结果的时间也更长。考虑到这些限制，我们做不到对所有可能的候选模型进行评估。然而，通过提升模型效率，我们可以做到在相同的时间帧运用相同的计算资源评价更多的候选模型（inventory）。

在本文中，我们比较了梯度提升决策树（gradient-boosted decision tree ，简称GBDT）这一类预测模型的不同实现，并描述了能产生更高效评估的 C++ 多方面改进。

决策树模型

决策树被普遍用作预测模型，该算法将关于对象的特征观察值映射到对象类的目标值。由于其非线性和快速求值的特点，它成为了机器学习、数据分析和统计学之中最常见的预测模型方法之一。在这些树状结构中，叶结点表征分类标签，而有向边表征产生这些分类标签的特征连接。

决策树非常强大，但是训练数据中的小变动可以演化为决策树中的大变化。这可通过使用一项被称为梯度提升（gradient boosting）的技术来补救。即，为错误分类的训练实例提升权重，从而形成一个新的决策树。接着对这一步骤进行连续重复以获得新的决策树。最后的分值（scores）是决策树上每个叶节点分值的加权总和。

模型通常很少更新，且训练复杂模型需要花费数小时。然而，在 Facebook 的大规模数据上，我们想要更频繁地更新模型，即按照毫秒间隔依次运行它们。Facebook 的很多后端服务是用 C++ 写的，因此我们利用这一语言的一些属性做了些改善，以产生只需要更短 CPU 周期进行求值的高效模型。

下图是一个简单的决策树，它包含以下特征：

• 今天某人 A 点击通知的数量（特征 F[0]）

• 对应通知的文章点赞数量（特征 F[1]）

• 某人 A 点击通知的总数量（特征 F[2]）

在不同的结点，我们查看了上述特征的值，并遍历整棵决策树以获取通知点击的概率。

平面树（Flat tree）的实现

决策树模型的朴素实现是通过一个带有指针的简单二叉树而完成的。然而，结点并不需要连续地存储于内存之中，因为这样二叉树并非很有效。另一方面，决策树通常是完整的二叉树（即二叉树的每个结点一定存在零值或两棵子树），它通过使用向量而压缩存储。指针并不需要空间，而每一结点的父结点和子结点可通过数组索引算法查看。我们将用这一实现对比这一章节的实验。

编译树（Compiled tree）的实现

每一个二叉树都能由一个复杂的三元表达式表征，而这个表达式能进行编译并链接到可直接在服务中使用的动态库（DLL）。需要注意的是，我们可以实时添加或更新决策树模型，而不需要重启服务。

我们也可以利用 C++ 中的 LIKELY/UNLIKELY 注释（annotations）。它们是编译器发出指令的方向，并且能将分支预测更加偏向于跳转指令（jump instruction）「可能」出现的一侧。如果预测是对的，那么就意味着跳转指令将占有 0 个 CPU 周期。我们可以根据在批量中排序的或离线分析中的真实样本计算分支预测，这是因为训练和评估集的分布不应该改变太多。

下列代码表征上述的简单决策树的一个实现：

模型范围求值

在典型的排序设置中，我们需要在多个特征向量的实例上评估相同的已训练模型。例如，我们需要为了一个给定的人排序 1000 个潜在候选项，并选择最相关的候选项。

一种方法是迭代所有候选项并逐一排序。而通常情况下，模型和所有候选者都不能组合到 CPU 指令缓存中。而受到提升训练（boosted training）的驱动，实际上我们可以将模型分解到树的范围内（第一批 N 子棵树，第二批 N 棵子树等等）。这样每个范围就能足够小以适应缓存。随后我们可以调转评估顺序：我们将评估每个范围上的所有样本，而不是评估一个样本上的所有树。采用这种方法，我们可以在 CPU 缓存中将整棵树的集合与所有的特征向量进行合并，并在下一次迭代中仅仅只是替代子树集。这种方法不仅减少了缓存未命中（cache misses）数量，同时还使用区块读/写而不是 RAM。

此外，经常还出现多个模型需要评估相同特征向量的情况。例如，用户在文章中点击、点赞或评论的概率。这种方法有助于将所有特征向量储存在 CPU 缓存中，并逐个评估模型。

另外一个折衷方法可以考虑为前 N 棵树排序所有的候选项，并由于提升算法的自然属性，我们可以丢弃排名最低的候选项。这样虽然可以提高延迟，但精度也会略微地下降。

普遍特征

有时特征在所有的特征向量中很普遍。在上述对于某个特定个人的实例中，我们需要排序所有的候选通知。上文描述的特征向量 [F[0]、F[1]、F[2]] 可为：

[0、2、100]

[0、0、100]

[0、1、100]

[0、1、100]

我们很容易发现特征 F[0] 和 F[2] 对于候选项是相同的。我们可以通过聚焦 F[1] 的值显著缩小决策树，从而改善求值的时间。

类属（Categorical features）特征

绝大多数机器学习算法使用二叉树，并且二叉树可被延伸成 k-ary 树。另一方面，特征中的一些实际上并不能被比较，因而被称为类属特征。例如，如果国家是一个特征，一个人不可能说这个国家的值是否少于或者等于美国（或者一个对应的枚举值）。如果树足够深，那么这个比较可通过使用多个层级实现。但是这里我们已经实现了检查当前特征是否属于一组值的可能性。

这个学习方法并没有改变太多，我们依然在尝试找到可被分割的最优子集，并且其求值也非常快。基于集的大小，我们使用 in_set C++ 实现，或者仅仅把 if 条件连接起来。这减小了模型，对于收敛也有所帮助。

计算结果

我们训练了一个提升决策树（boosted decision tree）模型以预测一个使用了 256 个决策树、每个树包含 32 个叶结点的通知点击概率。接着，我们比较了特征向量求值的 CPU 使用率，其中每个批量平均排序 1000 个候选项。批量大小值 N 基于机器 L1/L2 缓存大小进行调整和优化。下面让我们看一下在平面树（flat tree）实现期间的性能提升：

• 普通编译模型：2 倍提升。

• 带注释的编译模型：2.5 倍提升。

• 带注释、范围和普遍／特殊特征的编译模型：5 倍提升。

性能提升对于不同的算法参数（128 或 512 个树，16 或 64 个叶结点）是相似的。

结论

CPU 使用率的提升和附带的加速允许我们增加排序实例的数量，或者在使用相同数量资源的情况下增加模型的大小。这一方法已被应用于 Facebook 的几个排序模型之中，比如通知过滤、推送排序、建议和用户关注。我们的机器学习平台在持续进化，更精确模型与更高效的模型求值方法的结合将允许我们持续提升排序系统的性能，并为数十亿人带来最佳的个人化体验。