ali在《COLD: Towards the Next Generation of Pre-Ranking System》中讲述了他们的实现。
摘要
长期以来，pre-ranking只是ranking模块的一个简化版本，它要处理待排序的更大集合的候选。这里的努力是为了简化ranking模型，以便在online inerence时处理大量数据。例如，在展示广告系统中，SOTA 的preranking模型会根据vector-product based的深度架构：user-wise和ad-wise vectors会以offline方式进行预计算，online时计算获取preranking score。很明显，这种模型限制会导致次优的performance。
本paper中，我们从算法系统co-design的角度来重新思考pre-ranking系统。除了解记模型架构的计算能力（computing power）限制外（会造成模型效果的loss），这里我们设计了一个新的pre-ranking系统，会对pre-ranking模型和computing power做joint optimization。我们将之命名为COLD（Computing power cost-aware Online and Lightweight Deep pre-ranking system），COLD在三方面是SOTA的：
- 1) 在COLD中会使用一个带有交叉特征的专属deep model
- 2) 通过在inference加速上进行optimization tricks，计算开销明显下降。这为COLD使用更复杂深度模型来达到更好performance带来空间
- 3) COLD模型以online learning和servering方式运行，可以很好地处理数据分布偏移（data distribution shift）的挑战
同时，COLD的fully online pre-ranking系统会使用一个灵活的基础设施来支持高效的新模型开发和online A/B testing。自2019以来，COLD已经被部署到ALibaba展示广告系统的所有产品上，并带来了极大提升。
1.介绍
有许多papers介绍如何构建一个高效的ranking系统。然而，非常少的工作关注于pre-ranking系统。本文将讨论在展示广告系统中设计pre-ranking系统。该技术也能应用到推荐、搜索引擎中。
传统上，pre-ranking系统的候选集的size可以扩展到上万。它是ranking系统的百倍。另一方面，ranking和pre-ranking系统有严格的latency限制，例如：10-20ms。这种情况下，pre-ranking系统通常被设计成一个lightweight ranking系统，它可以简化ranking模型以解决online inference时的计算爆炸。
1.1 pre-ranking系统的开发历史简介
回看pre-ranking在工作界的开发历史，我们可以将模型视图分为4代，如图2所示。
图2
第1代是非个性化的ad-wise statistical score。它会通过将每个ad的最近CTR做平均来计算pre-ranking score。该score会以很高频率更新。LR模型是第二代系统，它是一个关于大规模ranking模型的lightweight版本。它可以以online learning和serving的方式更新。Vector-product based的deep模型是第三代，也是当前SOTA的pre-ranking模型。在这种方法中，user-wise和ad-wise embedding vectors是以offline方式单独预先计算好，它没有user-ad交叉特征，接着两个vectors的内积会通过在线计算来获得pre-ranking score。尽管vector-product-based DNN可以极大增加前两代的模型效果，它仍然有两个地方有提升空间：
- 1) 模型表征能力（Model expression ability）：如[17]所示，模型的表征能力被限制在vector-product的形式上
- 2) 模型更新频率：vector-product based DNN的embedding vectors需要offline进行预计算，然后加载到server的内存中进行online计算。这意味着vector-product based DNN模型只能以一种low-frequency的方式更新，使得它很难适配最新的data distribution shift，特别是当数据变化很大时（比如：双十一前后）
上述提到的三代pre-ranking系统会具有相同的范式：计算能力（computing power）被看成是一个常数限制，在此之下开发pre-ranking模型。也就是说，模型的设计和计算能力的optimization是解耦的（decoupled），这通常会导致模型的简化版可以满足计算能力的需求。这也会导致次优的效果。
2. CLOD：新一代pre-ranking系统
在本paper中，我们从算法系统co-design的角度重新思考了pre-ranking系统的挑战。作为替代，这里重新设计了一个新的pre-ranking系统，它会对pre-ranking模型和计算能力开销一起进行jointly optimizaing。我们将它命名为COLD，如图2所示。我们将COLD看成是第4代pre-ranking系统。COLD会同时考虑模型设计和系统设计。COLD中的计算能力开销（computing power cost）是个变量，它可以与模型效果一起进行jointly优化。换句话说，COLD是一个灵活的pre-ranking系统，在模型效果和计算能力开销间进行trade-off。
COLD的关键特征是：
- 1) 在COLD中会使用带交叉特征的Arbitrary deep model。在真实系统中，COLD模型是一个7-layer fully connected DNN，它使用SE（Squeeze-and-Excitation）blocks。SE block可以将feature进行group selection来从复杂的ranking模型中得到一个lightweight版本。该selection会同时考虑模型效果和计算能力开销。也就是说，COLD的计算能力开销是可控的。
- 2) 通过使用optimization tricks（比如：在inference加速中进行并行计算和semiprecision计算），计算能力开销可以显式地减小。这可以让COLD使用更复杂的deep模型来达到更好的效果
- 3) COLD模型可以以online learning和serving的方式工作，可以为系统带来良好的能力来解决data distribution shift的问题。COLD的fully online pre-ranking系统可以提供给我们一个良好的基础设施来支持新的模型开发和快速在线A/B testing，它也是当前ranking系统所具有的最好的系统实践。
图3给出了4代ranking系统在模型表征能力和更新频率上的一个比较。COLD可以达到最好的tradeoff。自2019以来，COLD在展示广告系统的所有产品上进行部署，每天服务数亿用户。对比vector-product based DNN，COLD的online version会带来6%的RPM提升，它在商业上是一个极大的提升。
图3
2.pre-ranking系统总览
如图1所示，pre-ranking可以被看成是一个matching和ranking 模块间的connecting link。它接收matching的结果，并执行一个粗糙的选择(rough selection)，来减小后续ranking模块的候选集的size。以Alibaba的展示广告系统为例，候选集的size M会被feed到pre-ranking系统中，通常规模为一万。接着pre-ranking模型会根据特征metrics（比如：eCPM）来选择top-N的候选集合。N的幅度通常为数百。这些胜出的N个candidates会进一步通过一个复杂的ranking模型来进行排序得到最终结果，最后展示给用户。
总的说来，pre-ranking会共享与ranking相似的功能。最大的不同之处在于问题规模。很明显，对于pre-ranking系统中待排序的candidates的size会是ranking系统中的10倍或更大。在pre-ranking系统中直接使用ranking模型是不可能的，因为它会面对大量的计算开销。然而，对computing power和模型效果进行balance是设计pre-ranking系统的一个关键考虑。
2.1 Vector-Product based DNN模型
受deep learning的驱动，vector-product based DNN模型被广告用于pre-ranking系统中，并达到state-of-the-art的效果。如图2所示，vector-product based DNN模型被认为是由两个并行的sub enural networks组成。user features被feed到left sub network中，ad features则到right sub network中。对于每个sub network，features被feed给embedding layer中，接着concatenated一起，后接FC layers。这种方式下，我们可以获得两个fix-size的vectors：\(v_u\)和\(v_a\)，它分别表示user和ad信息。最终，pre-ranking score p会以如下方式进行计算：
\[p = \sigma(v_u^T v_a), where \ \sigma(x)=\frac{1}{1+e^{-x}}\]…(1)
vector-product based DNN的训练与传统ranking model的方式相类似。
2.2 缺点
vector-product based DNN模型在latency和计算资源上很高效。\(v_u\)和\(v_a\)的vectors可以以offline的方式单独预计算好，score p可以online计算。这使得它在计算开销上很友好。图4展示了经典的实现。对于前两代pre-ranking模型，vector-product based DNN可以获得极大的性能提升。
图4
然而，vector-product based DNN模型会更关注于计算开销的减小，将模型限制在vector-product形式下，这会导致次优的效果。我们将缺点总结如下：
- 1) 模型表征能力被限制在vector-product形式下，不能使用user-ad cross features。之前的工作【17】展示了在vector-product based的复杂深度模型的优越性。
- 2) 通过枚举所有的users和ads，user和ad vectors需要离线进行预计算，来减小计算资源并进行latency优化。为数亿用户和数千万ads计算会花费几小时，使得它很难适应data distribution shift。当数据变化很剧烈时，会对模型效果带来伤害。
- 3) 模型更新频率会受系统实现的影响。对于vector-product based DNN模型，在user/ad vectors indexes间的每日切换必须同时进行。
vector-product based DNN的pre-rankin系统的这些缺点源自于追剧计算能力开销，很难完全解决。
3.COLD
COLD的核心思想是，同时考虑模型设计与系统设计。在COLD中的计算开销是个变量（variable），它可以和模型performance一起进行jointly optimzied。换句话说，COLD是一个灵活的pre-ranking系统，在模型效果和计算开销间的tradeoff是可控的。
3.1 COLD中的Deep pre-ranking模型
不同于vector-product based DNN模型，它会通过限制模型结构来减小计算开销，这会造成模型效果的loss，COLD允许使用arbittrary deep models的复杂结构来确保最佳的模型效果。换句话说，SOTA deep ranking模型可以用在COLD中。例如，在我们的实际系统中，我们采用GwEN（group-wise embedding network）作为我们的初始模型结构，它是我们的ranking系统的online模型的一个早期版本。图2展示了GwEN，它是一个fully connected layer，使用feature group-wise embedding的concatenation作为inputs。注意，在GwEN network中也包括交叉特征（cross features）。
当然，直接使用复杂结构的deep rank模型的online inference的计算能力开销是不可接受的，在pre-ranking系统中待排序的candidate set的size更大。为了解决该问题，我们采用两种方式的优化策略：
- 一种是设置一个灵活的网络结构，它可以在模型performance和计算开销间做出一个trade-off；
- 另一种方式是，通过在inference加速上使用optimization tricks，来显式减小计算开销。
3.2 灵活的网络结构设计
总的来说，我们需要引入关于网络结构的合理设计来获得关于deep model（初始GwEN模型的一个full版本）的一个lightweight版本。可以使用以下技术（network pruning、feature selection、neural architecture search等）到该任务上。在我们的实践中，我们选择feature selection方法，它对于模型效果和计算开销间的trade-off控制来说来说方便些。也可以使用其它技术，这个读者可以进一步尝试。
特别的，我们使用SE（squeeze-and-excitation）bloack作为feature selection。SE block首先被用到CV中来显式地建模channels间的inner-dependencies。这里，我们使用SE block来获得group-wise features的重要性权重（importance weights），通过对模型效果和计算开销两者进行measure，在COLD中选择最合适的。
importance weight计算。假设\(e_i\)表示第i个input feature group的embedding。feature groups的总数是M。SE block会对input \(e_i\)压缩到一个关于weight \(s_i\)的scalar value，它的计算如下：
\[s = \sigma( W [e_1, \cdots, e_m ] + b)\]…(2)
其中，\(s \in R^M\)是一个vector，\(W \in R^{k \times M}, b \in R^M\)。W和b是可学习的参数。接着，新的weighted embedding \(v_i\)通过在embedding \(e_i\)和importance weight \(s_i\)间的field-wise乘法计算得到。
feature group selection。weight vector s表示每个feature group的重要性。我们使用该weight来对所有feature groups进行排序（rank），并选择具有top weights的K个feature groups。接着，会进行一个offline test，来评估选择K个feature groups的lightweight版本的模型的模型效果和系统效果。metrics包括：GAUC、QPS以及RT（return time，表示模型的时延）。对于数目k有许多启发tricks，例如：features的groups，我们最终选择在给定系统效果限制下最好的GAUC版本作为我们最终的模型。这种方式下，模型效果和计算开销间的trade-off可以以灵活方式开展。
3.3 工程optimization tricks
除了通过灵活的网络架构设计来减小计算开销外，很难避免模型效果在一定程度上的损失；我们也会在工程上使用许多optimzation tricks，进一步看COLD使用复杂deep models能带来更大的收益。
这里，我们引入了一些在展示广告系统中的经验。不同的系统间可能差异比较大，大家可以根据业务实际做选择。在我们的展示广告系统中，pre-ranking模块的online inference engine主要包括两个部分：feature计算和dense network计算。在feature计算上，eigine会从indexing系统拉取user和ad features，接着计算cross-features。在dense network computation中，eigine会首先将features转换成embedding vectors，并将它们做concatenate作为network的input。
所有level的Parallelism。为了在计算开销上达到low latency和high throughput inference，增大并行计算很重要。因此，当可能时，我们的系统使用parallelism。幸运的是，不同ads的pre-rank score相互之间完全独立。这意味着他们可以并行计算，代价是：相关的user features会有些重复计算。
在high level上，一个前端（front-end）user query可以被split成许多inference queries。每个query会处理部分ads，结果会在所有queries返回之后进行merge。因此，当决定要进行split的queries数时需要进行trade-offs。更多queries意味着每个query会有更少ads，因此对于每个uqery具有更低的lantency。queries过多可能会导至大量重复计算和系统额外开销。另外，我们的系统使用RPC来实现queries，越多的queries意味着越多的network traffic，更有可能会导致delay或failure。
当处理每个query时，多线程处理可以用于feature计算。每个thread会处理部分ads来减小latency。最终，当执行dense network inference时，我们使用GPU来加速计算。
column based computation。传统上，feature计算的完成会以row-based的方式进行：ads被一条一条处理。然而，这些row-based的方法并不是cache-friendly。作为替代，我们使用一个column-based方式来将一个feature column放一起进行计算。图5展示了两种类型的计算模式。通过这样做，我们可以使用像SIMD（多数据单指令Single Instruction Multiple Data）的技术来加速feature computation。
图5
low precision GPU计算。对于COLD模型，大多数计算是dense matrix乘法，这留给我们优化的空间。在NVIDIA的Turing架构中，T4 GPU为Float16和Int8 matrix乘法提供了extreme效果，很适合我们的case。Float16的FLOPS理论峰值是Float32的8倍以上。然而，Float16会丢失一些precision。实际上，我们发现对于一些场景，随着我们对一些feature groups使用sum-pooling，dense network的input可以非常大，超过Float16的表示。为了解决该问题，一种解决方案是使用normlization layers比如：batch-norm layer。然而，BN layer本身包含了移动变量参数（moving-variance parameters），它的规模可能会更大。这意味着计算图需要是mix-precision的，fully-connected layer会使用Float16和batch-norm layers会使用Float32.另一种方法是使用parameter-free normalization layer。例如，log函数可以将大数转换成一个合理的区间。然而，log()函数可能不能处理负数，当输入接近0时，会生成一个很大的数。因此，我们设计了一个piece-wised smooth function，称为linear-log oprator来处理unwanted行为，如等式(3)所示：
\[linear_log(x)=\\]…(3)
linear_log()函数可以看成图6的样式。它将Float32的数字转换成一个合适的区间。如果在第一个layer上放置一个linear_log operator，它会保证network的input可以会小些。另外，linear_log()函数是\(C^1\)连续的，因此，它不会让网络训练更难。实际上，我们发现，在添加了这个layer后，network仍能达到对比原始COLD模型相近的accuracy。
图6 linear_log function
在使用Float16进行inference之后，我们发现，CUDA kernel的running time会急剧下降，kernel launching时间会成为瓶颈。为了增强实际QPS，当开加kernels时，我们进一步使用MPS（multi-process service）来减小overhead。通过组合Float16和MPS，engne throughput是之前的两倍。
3.4 Fully Online infrastructure
受益于不受限的模型结构，COLD可以在一个fully online infrastructure上实现：training和serving都以online方式进行，如图7所示。从工业界角度，当前的最好系统实践是ranking系统自身。该infrastcture的好处有两块：
图7
- 1) COLD模型的online learning可以处理data distribution shift。根据我们的体验，在下一实验环节我们会展示COLD模型对比vector-product based DNN模型的提升，尤其是当数据剧烈变化时。另外，COLD模型使用online learning对于new ads是友好的。
- 2) COLD的fully online pre-ranking系统提供给我们一个灵活的infrastructure来支持高效的新模型开发以及online A/B testing。记住，对于vector-product based DNN模型，user和ad的vectors需要离线预计算好，并通过index加载到inference engine中。因此，它涉及到许多系统的开发，以便进行两个版本vector-product based DNN模型的A/B testing。根据我们的经验，获得一个solid A/B testing结果的常见时间开销是多天，而对于COLD来说则是几小时。另外，fully online serving也会帮助COLD避免vector-product DNN模型的delayed switch。
4.实验
我们仔细对比评估了COLD的pre-ranking系统的效果。并做了模型效果和系统效果的对比。据我们所知，以下实验在online展示广告系统中执行。
4.1 实验设置
COLD模型的最强baseline是SOTA vector-product based DNN模型，它是在展示广告系统中的online pre-ranking模型的最近版本。
COLD模型和vector-product based DNN模型会使用超过900亿的样本进行训练，它们从真实系统中的log进行收集得到。注意，vector-product based DNN模型会共享与COLD模型的相同的user和ad features。vector-product based DNN模型不能引入任何user-ad交叉特征，而COLD则会使用user-ad交叉特征。作为公平对比，我们也会评估使用不同cross features的groups时的COLD模型的表现。对于COLD模型，feature embedding vectors会被concatenated在一起，接着feed到一个fully connected network（FCN）上。FCN的结构是：\(D_{in} \times 1024 \times 512 \times 256 \times 128 \times 64 \times 2\)，其中\(D_{in}\)意味着被选中features的concatenated embedding vectors的维度。对于vetor-product based DNN模型，FC layers被设置成200 x 200 x 10. 对于两种模型，input feature embedding的维度被设置成16. 我们使用Adam solver来更新模型参数。GAUC被用来评估模型的offline表现。另外，人们引入一个新的top-k recall指标，以便measure在pre-ranking模型和后续ranking模型间的alignment degree。top-k的recall rate被定义如下：
\[recall = \frac{| \lbrace top\ k\ ad\ candidates \rbrace } \union \lbrace top \ m \ ad \ candidates \rbrace } {top \ m \ ad \ candidates} |\]…(4)
其中，top k的candidates和top m的candidates会从相同的candidate set中生成，它是pre-ranking模块的input。top k ad candidates会通过pre-ranking模型进行排序，top m ad candidates则通过ranking模型进行排序。ranking metric是eCPM（expedted Cost Per Mile, eCPM = pCTR * bid）。在我们的实验中，ranking模型使用DIEN，online ranking系统的一个之前版本。
对于系统效果的评估， 我们使用包括QPS、RT的指标。这些metrics会影响在要进行pre-ranked的相同size候选集合下的计算能力开销。粗略的说，对于一个给定模型，在越低的RT下，更大的QPS意味着更低的计算开销。
4.2 模型效果的评估
表1展示了不同模型的offline评估结构。我们可以看到，对比起DIEN，COLD维持着一个相当的GAUC，并在GAUC和Recall上对比vector-product based模型同时达到了重大的提升。
我们在online A/B testing上做了细致的实验。表2展示了COLD模型的lift，胜过vector-product based DNN模型。在正常日子里，COLD模型可以达到6.1%的CTR和6.5%的RPM提升，它在商业上是一个巨大的提升。另外，在双11节，该提升会是9.1%的CTR和10.8%的RPM。这证明了COLD的fully online infrasturcture的价值，它使得模型可以适应最新的数据分布，即使当数据变化剧烈时。
4.3 系统效果的评估
我们在pre-ranking系统上使用不同模型评估了 QPS和RT。表3给出了结果。Vector-product based模型会运行在一个CPU机器上，它使用2 Intel(R) Xeon(R)Platinum 8163 CPU @ 2.50GHz (96 cores) and 512GB RAM上。COLD模型和DIEN都运行在一个使用NVIDIA T4的GPU机器上。此时，vector-product based DNN模型可以达到最佳的系统效果，它是预期结果。DIEN的计算能力开销最大。COLD则达到balance。
4.4 COLD的Ablation研究
为了进一步理解COLD的效果，我们在模型设计角度和工程优化角度同时做了实验。对于后者，它很难从系统集成上解耦所有的优化技术，并对他们进行对比。这里我们给出了在最重要因子上的评估。
略。