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

翻译自:https://code.facebook.com/posts/975025089299409/evaluating-boosted-decision-trees-for-billions-of-users/

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机器学习平台不断发展,通过更精确的算法结合更高效的工程实现,不断改进排名系统,为数十亿人提供最佳的个性化体验。

Written on March 29, 2017