Facebook 在数十亿用户规模场景下 GBDT 算法性能优化

原文： https://code.facebook.com/posts/975025089299409/evaluating-boosted-decision-trees-for-billions-of-users/

下面由 Google 翻译，看不懂别问我。

Facebook 应用中的诸多功能都是通过机器学习和排序模型来优化用户体验，例如预测哪些通知应该发给用户，用户更喜欢哪些 story ，哪些兴趣 page 是你可能会关注。为了能够挖掘出用户感兴趣的内容，高质量的机器学习模型是至关重要的。 Facebook 的机器学习排序模型会根据非常多的实时反馈信号，动态决定最佳的排序结果。例如在通知预测这个场景中， Facebook 的模型会感知用户是否点击过相似的通知内容，以及通知中的 story 已经获得了多少 like 。由于每一条新产生的通知都需要根据这些实时数据进行预测预测，所以对于预测算法性能要求非常高。

越复杂的模型，预测的精准度会越高，但同时越消耗 CPU 的计算能力，预测所需要的时间也会越长。这些条件会限制系统的吞吐能力，也就无法对所有的候选集进行预测。如果能够优化算法模型的性能，使用同样的计算资源就可以预测更多的候选集，预测的精准度也就相应提高。

下面内容会对比多种 GBDT 算法实现的性能差异，已经在 C++算法实现上的一些优化经验。

决策树模型

决策树通常被用作预测模型，原理上是建立对象的观测结果与属性的映射关系。因为决策树具有非线性，速度快等特点，所以在机器学习、数据分析、数据统计等领域决策树是最常见的预测实现算法。在决策树的结构中，叶子节点表示分类标签，中间节点表示这些特征之间的关联性。

虽然决策树模型非常有效，但是训练数据轻微的一个变动就会生成一颗完全不同的决策树，结构差别非常大。这个问题可以通过梯度提升技术来解决。也就是说每次分类都将上一次分错的数据权重提高一点再进行分类，生成一个新的树，如此反复，最终得分就是所有叶子节点得分权重的加权。

一般来说训练复杂的模型需要的数个小时，所以模型不会频繁更新。但在 Facebook 的规模下，模型需要经常更新，并且预测耗时要求是毫秒级。 Facebook 的很多后端服务是 C++实现的，因此我们利用 C++的一些特性，并作出了改进，实现更有效的模型，使用较少的 CPU 计算资源

下图中是一个简单的决策树模型，其中特征包括：

A 用户一天点击通知的次数
通知中 story 的 like 数
A 点击通知的总数

通过遍历树中不同节点的特征值，得到用户点击这个通知的概率。

扁平化实现

决策树的初始实现方式是通过简单的二叉树指针实现。这种实现方案不是很高效，主要原因是节点的数据在内存中不是连续存储的，所以执行时 CPU Cache Miss 会比较严重。另一方面，决策树的结构通常是完全二叉树（每个节点要么有两个孩子要么没有），这种结构可以通过数组形式实现，以便让节点数据分布在一片连续的内存空间里，同时省去了指针的开销。 Facebook 对比了两种实现方式的性能差异。

编译实现

每个二叉树可以表示为一个复杂的三元表达式，它可以被编译并链接到可以直接用于服务的动态库（ DLL ）。请注意，我们可以实时添加或更新决策树模型，而无需重新启动服务。

Facebook 还利用了 C++中的LIKELY / UNLIKELY注释。这些注释是编译器发出指令的方向，这些指令将导致分支预测有利于跳转指令的“可能”侧。如果预测是正确的，跳转指令只占用零个 CPU 周期。因为训练数据和实际评估数据的分布不会有太大变化，所以可以根据实际样本或离线分析计算每个分支的概率。下面是上图中决策树的实现样例代码：

int tree(double* F) {
  return LIKELY(F[0] < 1)
    : (UNLIKELY(F[1] > 10) ? (F[2] > 50 ? 0.1 : 0.05) : 0.01)
    ? (F[2] > 100 ? 0.5 : 0.2);

分片预测

在典型的排名预测中，需要逐一对每个实例的特征向量进行预测。例如，为一个用户预测 1000 个不同的潜在候选人的排名，并选择最相关的候选人。

简单的实现可以迭代所有候选，每次对一个候选计算一次完整的预测。但是通常情况下，模型和所有候选特征数据不能完整的加载到 CPU 高速缓存中。参考 GBDT 的思路，实际上可以将模型分解成树的范围（前 N 个树，然后是 N 个树等），使得每个范围都足够小以适应 CPU 缓存。预测的实现可以按树的范围进行拆分：所有样本对一个小范围内的数据进行预测，而不是每个样本预测所有的树。这样就能够将小范围的树和所有候选的特征向量全部加载到 CPU 缓存中，并在下一次迭代中只是替换树集。这减少了高速缓存未命中的数量，并且使用块读 /写而不是 RAM 。

此外，有多个模型时，例如，用户点击，喜欢，评论的模型，这种方式有助于将所有特征向量保存在 CPU 缓存中并逐个评估模型。

另一个折衷方案通过前 N 个树的排名后，基于增强算法的性质，直接丢弃排名最低的候选人。这样进入下 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]特征进行预测即可，以此缩短预测时间

分类特征

大多数 ML 算法都使用二叉树，这可以扩展到k-ary 树。另一方面，有些特征是不可比的分类数据。例如，国家作为一维特征，并不能说某一个值小于等于"US"（或者小于等于 US 对应的枚举值）。如果树的深度足够深，这种比较可以通过逐层二值比较来实现。 Facebook 的做法是通过检查当前要素是否属于一组值的可能性，来实现分类特征的比较。

学习方法并没有太大变化，仍然尝试找到最好的子集来分解

算法上并没有太大变化 - 尝试找到最好的子集拆分边界，而且计算的速度非常快。基于集合的大小，我们使用 C ++集合的in_set操作或者直接使用if判断逐一比较。这种实现方式可以减少模型尺寸，并有助于收敛。

对比结果

Facebook 训练了一个含有 256 颗树的预测通知点击率的 GBDT 模型，每棵树含有 32 个叶子节点。对平均 1000 候选特征预测对比 CPU 使用率。批量计算因子 N ，根据 CPU 的 L1/L2 缓存大小做了特殊的调优。可以看到性能提升的效果：

简单编译实现模型： 2x
Likely/Unlikely 优化编译实现模型： 2.5x
Likely/Unlikely 优化编译，分片，分类特征优化： 5x

在不同的模型参数下，性能提升数据基本一致（ 128 或者 512 颗树， 16 或者 64 叶子节点）

总结

CPU 使用率的改善和性能的优化，使 Facebook 能够使用相同的资源量的情况下，可以同时预测更多的候选以及增加模型复杂度。这种方法已经应用于 Facebook 上的几个排名模型，包括通知过滤， Feed 排名以及关系推荐和 Page 推荐。 Facebook 机器学习平台不断发展，通过更精确的算法结合更高效的工程实现，不断改进排名系统，为数十亿人提供最佳的个性化体验。