阿里粗排技术体系与最新进展

分享嘉宾:王哲 阿里巴巴
编辑整理:乐远
语音朗读:蒋志新
出品平台:DataFunTalk

导读: 在搜索、推荐、广告等需要进行大规模排序的场景,级联排序架构得到了非常广泛的应用。以阿里的在线广告系统为例,按顺序一般包含召回、粗排、精排、重排等模块。粗排在召回和精排之间,一般需要从上万个广告集合中选择出几百个符合后链路目标的候选广告,并送给后面的精排模块。粗排有很严格的时间要求,一般需要在 10~20ms 内完成打分。在如此巨大的打分量以及如此严格的 RT 需求下,粗排是如何平衡算力、RT 以及最后的打分效果呢?本文将为大家分享粗排技术体系以及粗排最新进展 COLD,目前 COLD 排序系统已经在阿里定向广告各主要业务落地并取得了巨大的线上效果提升。

本文的分享,主要围绕下面几点展开:

  • 粗排的发展历史
  • 粗排的最新进展 COLD
  • 粗排技术的总结与展望

01 粗排的发展历史

首先和大家分享下粗排的发展历史。

1. 粗排的背景

图片

什么是粗排?一般的话,一个大型的工业级排序系统都会采用多阶段的排序架构,通常会包含四部分:召回、粗排、精排和重排。以阿里巴巴定向广告为例,召回的规模一般是千万左右,而粗排打分规模一般是一万以上,精排和重排的规模一般是上百左右。粗排是处于召回和精排的一个中间阶段,目标是在满足算力 RT 约束的情况下,从上万个广告集合中选择满足后链路需求的候选广告集合。

粗排和精排有两点不同:

  • 算力和 RT 的约束更严格:粗排的打分量远高于精排,同时有更严格的延迟约束,阿里巴巴定向广告的要求是 10-20ms
  • 解空间问题更严重:粗排和精排训练的时候使用的都是展现样本,但是线上打分环节粗排打分候选集更大,打分阶段距离展现环节更远,因此粗排阶段打分集合的分布和展现集合差距相比精排更大,解空间问题也更严重。

2. 粗排的两大技术路线

粗排的技术路线其实就是解决粗排一般该怎么迭代的问题,由于粗排是处于召回和精排之间的一个模块,因此粗排本身的迭代会受到前后链路的制约,因此需要站在整个链路的视角来看待这个问题。纵观整个链路,粗排一般存在两种技术路线:集合选择和精准值预估。

图片

① 集合选择技术

集合选择技术是以集合为建模目标,选出满足后续链路需求的集合的方法,该技术路线在召回非常典型,这其实也非常符合粗排的定位。该方法优点是算力消耗一般比较少,缺点是依赖于对后链路的学习,可控性较弱。

什么叫可控性?也就是说如果希望进行一些调整的话,由于这种方式依赖于通过数据回流对后链路进行学习,而数据回流往往比较慢,同时对数据量也有要求,可能需要后面链路的这些策略调整影响到比较大的流量之后,粗排才可以学习到,因此这种方式可控性比较弱,是偏被动的一种方式。

这种技术路线有以下常见的几种方法:

  • 多通道方法:类似于召回,针对不同的目标构建不同的通道,然后分别选出不同的集合,然后再进行合并选择。
  • Listwise 方法:一般是直接建模集合的损失,典型算法如 LamdaMART。为了更好理解 listwise 算法,这里提一下 pointwise 算法和 pairwise 算法,pointwise 算法一般是点估计的方式,训练过程只考虑单条样本;而 pairwise 算法训练过程中会考虑当前样本和其它样本的相互关系,会构造这样的 pair,并在训练的过程中引入这方面的 pairwise loss,训练目标可能是正 pair 排在负 pair 的前面;Listwise 更近一步,在训练的时候会考虑整个集合,会希望整个集合的指标如 NDCG 等达到最大化,如 LamdaMART 算法。
  • 序列生成方法:直接做集合选择。一般包含集合评估器和集合生成器,算法过程如下:首先,用评估器对所有的 item 进行打分并选择一个得分最高的,作为集合中的第一个商品。接下来,再挑选第二个商品,把第一个商品和所有可能的第二个商品进行组合,并用评估器进行打分。之后,选择得分最高的集合,并持续使用类似于贪心的方式不断的搜索,最终得到一个最优的集合。

② 精准值预估技术

精准值预估技术直接对最终系统目标进行精确值预估,其实也就是 pointwise 的方式。

以广告系统为例,建模的目标一般是 ECPM,即

ECPM=pCTR*bid

利用预估技术预估 pCTR,然后预估 bid,最终根据 ECPM 来进行排序,在粗排的话就是取排序的分最高的 topK 作为最终的集合。这种方式的优点是可控性强,因为是直接对整个目标进行建模,如果建模方式做了调整的话,可以直接调整排序公式,调整预估模型,对整个链路的掌控力更强。缺点就是算力消耗比较大,而且预估越准确,算力消耗也越大。

3. 粗排的技术发展历史

图片

粗排在工业界的发展历程可以分成下面几个阶段:

① 最早期的第一代粗排是静态质量分,一般是统计广告的历史平均 CTR,只使用了广告侧的信息,表达能力有限,但是更新上可以做到很快。

② 第二代粗排是以 LR 为代表的早期机器学习模型,模型结构比较简单,有一定的个性化表达能力,可以在线更新和服务。

其中 ①②可以合称为“粗排的前深度学习时代(2016 年以前)”。

③ 当前应用最广泛的第三代粗排模型,是基于向量内积的深度模型。一般为双塔结构,两侧分别输入用户特征和广告特征,经过深度网络计算后,分别产出用户向量和广告向量,再通过内积等运算计算得到排序分数:
image.png

③ 称为“粗排的深度时代-向量内积模型(2016)”。

图片

向量内积模型相比之前的粗排模型,表达能力有了很显著的提升,其优点:

  • 内积计算简单,节省线上打分算力
  • User 向量和 Ad 向量离线计算产出,因此可以做的非常复杂而不用担心在线 RT 问题
  • 双塔结构的 user 侧网络可以引入 transformer 等复杂结构对用户行为序列进行建模

图片

然而仍然有许多问题:

  • 模型表达能力仍然受限:向量内积虽然极大的提升了运算速度,节省了算力,但是也导致了模型无法使用交叉特征,能力受到极大限制。
  • 模型实时性较差:因为用户向量和广告向量一般需要提前计算好,而这种提前计算的时间会拖慢整个系统的更新速度,导致系统难以对数据分布的快速变化做出及时响应,这个问题在双十一等场景尤为明显。
  • 存在冷启动问题,对新广告、新用户不友好
  • 迭代效率:user 向量和 item 向量的版本同步影响迭代效率。因为每次迭代一个新版本的模型,分别要把相应 user 和 item 向量产出,其本身迭代流程就非常长,尤其是对于一个比较大型的系统来说,如果把 user 和 item 都做到了上亿的这种级别的话,可能需要一天才能把这些产出更新到线上,这种迭代效率很低。

针对向量内积模型的问题,也有很多相关的改进,典型的如下面这个方法。

图片

向量版 Wide&Deep 模型,deep 部分仍然是向量内积结构,wide 部分引入基于人工先验构造的 user 和 ad 的交叉特征,一定程度上克服了向量内积模型无法使用交叉特征的问题。然而该方法仍然有一些问题,wide 部分是线性的,受限于 RT 的约束,不能做的过于复杂,因此表达能力仍然受限。

图片

另外一个典型的改进方法是向量内积模型的实时化, user 向量通过线上打分实时产出,ad 向量仍然离线产出,但是更新频次增加。

通过实时打分,可以引入实时特征,实时性加强。然而实时打分使向量内积模型的 RT 和算力优势减弱,user 模型处于 RT 的约束不能设计的很复杂,而且该方法还引入了新的打分模型和 ad 向量版本不一致的问题。

④第四代 COLD,下一代粗排框架(2019)-算力感知的在线轻量级的深度粗排系统。下面将详细介绍该模型。

02 粗排的最新进展 COLD

图片

前面粗排的相关工作仅仅把算力看做系统的一个常量,模型和算力的优化是分离的。我们重新思考了模型和算力的关系,从两者联合设计优化的视角出发,提出了新一代的粗排架构 COLD ( Computing power cost-aware Online and Lightweight Deep pre-ranking system )。它可以灵活地对模型效果和算力进行平衡。COLD 没有对模型结构进行限制,可以支持任意复杂的深度模型。这里我们把 GwEN ( group-wise embedding network ) 作为我们的初始模型结构。它以拼接好的特征 embedding 作为输入,后面是多层全连接网络,支持交叉特征。当然,如果特征和模型过于复杂,算力和延时都会难以接受。因此我们一方面设计了一个灵活的网络架构可以进行效果和算力的平衡。另一方面进行了很多工程上的优化以节省算力。

总结为以下几点:

  • 基于算法-系统 Co-Design 视角设计,算力作为一个变量与模型进行联合优化
  • 模型结构没有限制,可以任意使用交叉特征
  • 工程优化解决算力瓶颈
  • 在线实时系统,实时训练,实时打分,以应对线上分布快速变化

1. 模型结构

① 特征筛选

图片

精简网络的方法有很多,例如网络剪枝 ( network pruning)、特征筛选 ( feature selection)、网络结构搜索 ( neural architecture search)等。我们选择了特征筛选以实现效果和算力的平衡,当然其他技术也可以进行尝试。具体来说,我们把 SE (Squeeze-and-Excitation) block 引入到了特征筛选过程中,它最初被用于计算机视觉领域以便对不同通道间的内部关系进行建模。这里我们用 SE block 来得到特征重要性分数。假设一共有 M 个特征,e_i表示第 i 个特征的 embedding 向量,SE block 把e_i压缩成一个实数s_i。具体来说先将 M 个特征的 embedding 拼接在一起,经过全连接层并用 sigmoid 函数激活以后,得到 M 维的向量 s:
image.png

这里向量 s 的第 i 维对应第 i 个特征的重要得分,然后再将s_i乘回到e_i,得到新的加权后的特征向量用于后续计算。

在得到特征的重要性得分之后,我们把所有特征按重要性选择最高的 top K 个特征作为候选特征,并基于 GAUC、QPS 和 RT 指标等离线指标,对效果和算力进行平衡,最终在满足 QPS 和 RT 要求情况下,选择 GAUC 最高的一组特征组合,作为 COLD 最终使用的特征。后续的训练和线上打分都基于选择出来的特征组合。通过这种方式,可以灵活的进行效果和算力的平衡。



注意 Se Block 仅用于特征筛选阶段,线上模型不包含该结构。

② 基于 scaling factor 的结构化剪枝

此外 COLD 还会进行剪枝,做法是在每个神经元的输出后面乘上一个 gamma,然后在训练的 loss 上对 gamma 进行稀疏惩罚,当某一神经元的 gamma 为 0 时,此时该神经元的输出为 0,对此后的模型结构不再有任何影响,即视为该神经元被剪枝。

在训练时,会选用循环剪枝的方式,每隔 t 轮训练会对 gamma 为 0 的神经元进行 mask,这样可以保证整个剪枝过程中模型的稀疏率是单调递减的。

图片

这种剪枝方法在效果基本不变的情况下,粗排 GPU 的 QPS 提升 20%。

最终模型是 7 层全连接网络。

2. 工程优化

为了给 COLD 使用更复杂的特征模型打开空间,工程上也进行了很多优化。在阿里定向广告系统中,粗排的线上打分主要包含两部分:特征计算和网络计算。特征计算部分主要负责从索引中拉取用户和广告的特征并且进行交叉特征的相关计算。而网络计算部分,会将特征转成 embedding 向量,并将它们拼接进行网络计算。

图片

① 并行化

为了实现低时延高吞吐的目标,并行计算是非常重要的。而粗排对于不同的广告的计算是相互独立的,因此可以将计算分成并行的多个请求以同时进行计算,并在最后进行结果合并。特征计算部分使用了多线程方式进一步加速,网络计算部分使用了 GPU。

② 行列转换

特征计算的过程可以抽象看做两个稀疏矩阵的计算,一个是用户矩阵,另一个是广告矩阵。矩阵的行是 batch_size,对于用户矩阵来说 batch_size 为 1,对于广告矩阵来说 batch_size 为广告数,矩阵的列是 featue group 的数目。常规计算广告矩阵的方法是逐个广告计算在不同 feature group 下特征的结果,这个方法符合通常的计算习惯,组合特征实现也比较简单,但是这种计算方式是访存不连续的,有冗余遍历、查找的问题。事实上,因为同一个 feature group 的计算方法相同,因此可以利用这个特性,将行计算重构成列计算,对同一列上的稀疏数据进行连续存储,之后利用 MKL 优化单特征计算,使用 SIMD (Single Instruction Multiple Data)优化组合特征算子,以达到加速的目的。

③ Float16 加速

图片

对于 COLD 来说,绝大部分网络计算都是矩阵乘法,而 NVIDIA 的 Turning 架构对 Float16 和 Int8 的矩阵乘法有额外的加速,因此引入 Float16 计算对提升性能非常必要 。但是 Float16 会损失计算精度,特别是在 sum-pooling 的情况下,数值有可能超出 Float16 的范围。为了解决这个问题,一种方式是使用 BN。但是 BN 本身的参数范围也有可能超过 Float16。因此只能使用混合精度的方式,对于 BN 层使用 Float32,而后面的层使用 Float16。另一种方式是使用参数无关的归一化方式,例如 log 函数。但是 log 函数不能处理负数,并且输入值接近 0 的时候会输出绝对值较大的数字。因此我们设计了一种分段平滑函数,我们叫做 linear_log 来解决这个问题。

从函数图像可以看出,linear_log 函数可以将 Float32 的数值处理到一个比较合适的范围。所以如果我们将 linear_log 函数放到第一层,那么就可以保证网络的输入参数在一个比较小的范围内。具体实践上,linear_log 函数对 COLD 模型的效果基本没有影响。使用 Float16 以后,CUDA kernel 的运行性能有显著提升,同时 kernel 的启动时间成为了瓶颈。为了解决这个问题,我们使用了 MPS (Multi-Process Service)来解决 kernel 启动的开销。Float16 和 MPS 技术,可以带来接近 2 倍的 QPS 提升。另外,使用阿里自研的含光 800NPU 专有硬件,替代原来的 GPU,QPS 进一步提升约 1 倍。

3. 在线服务架构

图片

COLD 没有限制模型的结构,训练和在线打分都是实时化的,可以带来以下两个优点:

  • 在线学习的引入使 COLD 与向量内积模型相比,可以更及时的响应数据分布的变化,对新广告冷启动也更为友好。
  • 实时架构对于模型迭代和在线 A/B 测试都更有利。向量内积模型由于用户向量和广告向量需要提前计算好,在线 A/B 测试也更为困难。实时架构也使 COLD 模型可以更快的更新,避免了向量内积模型的更新延迟问题。

4. 实验结果

这里 COLD 模型使用了 7 层全连接的网络结构。离线评估指标除了 GAUC 之外,还包含了 top-k recall,用于评估粗排和精排的对齐程度。

image.png

其中 top k 候选集合和 top m 候选集合均为粗排的输入打分集合。top k 集合是粗排选出的,而 top m 集合是精排选出的,排序指标是 eCPM(eCPM = pCTR*bid)。这里的精排模型是 DIEN。我们使用 QPS (Queries Per Seconds, which measures the throughput of themodel) 和 RT (return time, which measures the latency of model)来评估系统性能的影响。

① 模型效果评估

图片

离线效果评估可以看到 COLD 在 GAUC 和 Recall 上都优于向量内积模型。在线效果上,COLD 与向量内积模型相比在日常 CTR +6.1%,RPM + 6.5%。双十一 CTR+9.1%,RPM+10.8%,提升显著。

② 系统性能评估

图片

从上面表格可以看到,向量内积模型的系统性能最好,而精排的 DIEN 的系统性能最差,COLD 则在两者之间取得了平衡。

COLD 在得到特征重要性分数以后,会选出不同的候选特征,并基于离线指标进行特征选择。第二个表列了几组供选择的特征,可以看到 COLD 是考虑效果和系统性能以后的折中。

图片

Table 5 表明,工程优化上引入 Float16 和 MPS 优化以后,QPS 提升了 1 倍,效果显著。

5. COLD 的进一步发展

图片

那么 COLD 的后面进一步怎么发展?答案是与精排进行更加深度的整合。目前粗排和精排都是各自独立迭代的,这样会造成一个前后不一致的问题,会带来一个链路的内耗。而且粗排和精排维护两套流程的话,本身维护成本也很高,尤其是像阿里巴巴定向广告这边,业务多而且复杂。另外,COLD 和精排一样都是非常实时化的架构,这使得粗排和精排进行更深度的联动成为可能。

具体如何进行更加深度的整合呢?这里我们直接将粗排和精排的生产流程合二为一,联合训练,共享部分参数。另外也会借助特征蒸馏的方式,使用精排训练过程中的得分来指导粗排。在这个基础上,尝试引入精排参竞日志,对于未展现样本借助精排得分进行辅助学习。为什么引入精排参竞日志?其实前面提到过,因为粗排除了 RT 还有一个就是解空间的问题,粗排本身见到的集合比精排更多,但是它本身模型的能力却比精排更弱。所以为了缓解这个问题,引入精排参竞日志,这部分日志本身是没有 label 的,可以利用精排在这些 label 上进行打分,通过蒸馏的方式来引导粗排进行学习。为什么说这种方式在一定程度上能缓解解空间的问题?其实是建立在精排的模型能力比粗排更强,这个强很大程度体现在精排对交叉特征的利用上,在这种情况下,对于很多没有展现的 user 和 item 的 pair 对,精排相比于粗排其实是可以给出更精确的预估的,在这个前提下,借助精排更精确的预估分数,然后对粗排进行指导,在一定程度上是可以缓解解空间问题的。

这种方案的好处是将粗排和精排的流程合二为一,粗排精排模型一起训练,一起产出,这样可以提升粗排和精排的对齐程度,解决前面提到的因为前后链路不一致造成的链路损耗问题。另外引入精排参竞日志,在一定程度上也能缓解解空间问题。而且还有一个好处就是降低运维成本,减少了训练资源,提升我们的迭代效率。

03 粗排技术的总结与展望

图片

最后做一下总结,目前整个粗排基本已经全面迈向深度学习时代,而且深度学习时代的粗排主要存在向量内积和 COLD 两种主流技术路线。没有最好的算法,只有最合适的算法。不管是 COLD 还是向量内积,其实都有它适合的场景。有的团队在向量内积这条路线上持续迭代,其实也是受到本身算力 RT 的一些限制,包括本身工程团队等各方面因素的影响。而且很多团队的精排也还是向量内积结构,粗排就没有必要升级到 COLD 了。

图片

最后,展望一下粗排会怎么发展。粗排未来会存在两种可能的路线。

一个是粗排精排化,也就是说精排技术持续向粗排迁移,粗排和精排的界限逐渐模糊,走向更深层次的整合和一体化。其实可以看到,粗排的迭代历程本身其实就是一个粗排精排化的过程,一般很多技术如向量内积,都是先在精排落地拿到效果后,再逐渐向粗排迁移。而且算力也会更深度的参与到整个模型的迭代过程中,未来可能的话甚至不会再分粗排和精排,精排本身可能会在引入算力作为一个约束的情况下,通过 AutoML 等方式,产出多个不同算力版本的子模型,粗排只是其中一个,跟随精排自动升级和迭代,从而实现全链路算力和效果的平衡。甚至算力足够大的话,可以不需要粗排了,直接用精排打分就可以了。

另外其实还存在另外一条路,就是回归集合选择的本质,以产出符合后链路需要的集合为目标,真正以集合为对象进行建模。这里需要清楚粗排的目标是什么?粗排的目标是选出后链路需要的集合。而目前粗排精排化的迭代思路其实是在做 ranking,但是粗排其实只需要一个 top k 的集合,集合内部无序就可以了。而粗排精排化这种方式消耗了很大一部分算力在 TopK 的内部排序上,很多算力消耗在 Top1 和 Top2 怎么排好,从计算角度来看是一种资源浪费。当然这条技术路线还比较新,目前还在探索中。但是这个方向是一个很有希望的方向,因为它回归了粗排的本质,直接面向粗排的最终目标,因此在算力的利用率和最终的天花板上是更高的。

参考资料:

【1】Covington P, Adams J, Sargin E. Deep Neural Networks for YouTube Recommendations. RecSys. 2016.

【2】Zhe Wang, Liqin Zhao, Biye Jiang. COLD: Towards the Next Generation of Pre-Ranking System


本文地址:https://www.6aiq.com/article/1613987373768
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出