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会以如下方式进行计算：

…(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，它的计算如下：

…(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)所示：

…(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被定义如下：

…(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的效果，我们在模型设计角度和工程优化角度同时做了实验。对于后者，它很难从系统集成上解耦所有的优化技术，并对他们进行对比。这里我们给出了在最重要因子上的评估。

略。

参考

• 1.https://arxiv.org/pdf/2007.16122.pdf

华为在《A Practical Incremental Method to Train Deep CTR Models》对许多大厂在用的增量训练方式做了些总结。

介绍

互联网用户会训练大量在线产品和服务，因此很难区分什么对它们更有兴趣。为了减小信息过载，并满足用户的多样性需求，个性化推荐系统扮演着重要的角色。精准的个性化推荐系统有利于包括publisher和platform在内的需求侧和供给侧。

CTR预测是为了估计一个用户在特定context上、在某个推荐item上的概率。它在个性化推荐系统中扮演着重要角色，特别是在app store的商业化以及在线广告上。现在deep learning方法获得了越来越多的吸引力，因为它在预测性能和自动化特征探索上的优越性。因此，许多工业界公司都会在它们的推荐系统上部署deep ctr模型，比如：google play的Wide&Deep、Huawei AppGallery的DeepFM/PIN，Taobao的DIN和DIEN等。

然而，每件事都有两面。为了达到良好的性能，Deep CTR模型具有复杂的结构，需要在大量训练数据上进行训练许多epochs，因此它们都会具有较低的训练效率。当模型不能及时生成时，这样低效的训练（很长训练时间）会导致效果下降。我们在Huawei AppGallery上进行app推荐时观察到，当模型停止更新时，这样的效果如图1所示。举个例子：如果模型停止更新5天，模型效果在AUC上会下降0.66%，这会导致收益和用户体验的极大损失。因此，如何提升Deep CTR模型的训练效率并且不伤害它的效果是在推荐系统中的一个必要问题。分布式学习(Distributed learning)和增量学习( incremental learning )是两种常见范式来解决该问题。分布式学习需要额外的计算资源，需要将训练数据和模型分布到多个节点上来加速训练。在另一方面，增量学习会更改训练过程：从batch mode到increment mode，它会利用最近的数据来更新当前模型。然而，工业界推荐系统的大多数deep models是以batch模式进行训练的，它会使用一个fixed-size window的训练数据来迭代训练模型。在本工作中，我们主要关注incremental方法来训练deep CTR模型，它的目标是极大提升训练效率，并且不降低模型表现。

图1 当模型停止更新不同天时，模型效果下降的表现。x轴表示training set和test set间的不同gaps

然而，大多数incremental learning方法主要关注于图片识别领域，其中：新的任务或classes会随时间被学习。而incremental learning方法在图片识别上面临着不同的状况，比如：刚来的new features等，因此，没有必要研究该话题。在本paper中，我们提出一个实用的incremental方法：IncCTR。如图2所示，三种解耦的模块被集成到我们的模型中：Data Module、Feature Module以及Model Module。

• Data Module：会模拟一个水库（reservoir）的功能，从历史数据和incoming数据中构建训练数据。
• Feature module：被设计成处理来自incoming data的新features，并初始化已经存在的features和new features。
• Model模块：会部署知识蒸馏（knowledge distillation）来对模型参数进行fine-tune，并对来自之前模型的知识与来自incoming data的知识的学习进行balance。更特别的，对于teacher model我们会观察两种不同的选择。

图2 IncCTR架构总览，其中t表示incremental step

主要贡献如下：

• 强调了在推荐系统中通过离线模拟进行incremental learning的必要性。我们提出了一种实用的incremental方法：IncCTR来训练deep CTR模型。
• IncCTR包括了：data模块、feature模块、以及model模块，它们分别具有构建训练数据、处理new features以及fine-tuning模型参数的功能
• 我们会在公开数据集以及Huawei APP工业界私有数据集上进行大量实验。结果表明：对比batch模式的训练，IncCTR在训练效率上具有很大提升，可以达到较好的效果。另外，在IncCTR上每个模块的ablation study可以被执行。

paper的其余部分组织如下。在第2节，我们引入先决条件来更好理解方法和应用。我们会详述我们的增量学习框架IncCTR以及其三种单独模块。在第4节中，对比实验和消融学习的结果会用来验证框架的效果。最后，第5节下个结论。

2.先决条件

在该节中，我们引入了关于deep ctr模型的一些概念、基础知识。

2.1 Deep CTR模型

。。。

2.2 Batch模式 vs. Increment模式

在本节中，我们会表述和比较两种不同的训练模式：batch mode与increment mode。

2.2.1 使用Batch Mode进行训练

在batch mode下进行训练的模型会基于一个fixed-size time window的数据进行迭代式学习。当新数据到来时，time window会向前滑动。如图3所示，“model 0”会基于day 1到day 10的数据进行训练。接着，当新数据（”day 11”）到来时，一个新模型（称为“model 1”）会基于day 2到day 11的数据进行训练。相似的，“model 2”会基于day 3到day 12进行训练。

图3 使用Batch Mode进行训练 vs. 使用Incremental Mode进行训练。每个block表示一天的训练数据

2.2.2 使用Incremental Mode进行训练

在incremental模式下，会基于已经存在的模型和新数据进行训练。如图3所示，“Model 1”会基于已经存在的模型“Model 0”（它会基于在day 1到day 10上的数据进行训练），以及day 11的数据进行训练。接着，”Model 1”转向已经存在的模型。接着，当day 12的数据到来时，”Model 2”会基于”Model 1”和第day 12的数据进行训练。

可以看到，当使用batch mode进行训练时，两个连续的time window的训练数据会在大部分有重合。例如，day 1到day 10的数据、day 2到day 11的数据的重合部分是day 2到day 10，其中：80%的部分是共享的。在这样的环境下，使用incremental mode来替代batch mode会极大提升效率，而这样的替换又能维持效果表现。

3.方法论

我们的incremental learning框架IncCTR如图2所示。设计了三个模块：feature、model、data，会对历史数据（historical data）和新进来数据（incoming data）进行较好的trade-off。特别的：

• Data module：会被看成是一个蓄水池（reservoir），它可以基于历史数据和新进来数据进行构建训练数据。
• Feature module：会处理来自incoming data的new features，并会对已经存在的features和new features进行初始化。
• Model module：会使用knowledge distillation来对模型参数进行fine-tune。

3.1 Feature Module

在推荐和信息检索场景下，feature维度通常非常高，例如：数百万 or 数十亿。这样大数目的features的出现频次符合长尾分布，其中只有少量比例的features会出现很频繁，其余很少出现。如[10]观察到的，在模型中的一半features在整个训练数据中只出现一次。很少出现的features很难被学好。

因此，当使用batch模式训练时，features必须被归类成“frequent”或”infrequent”，通过统计每个feature的出现次数来完成。更正式的，对于一个feature x，它的出现次数S[x]大于一个预定义的阈值THR（例如：\(S[x] > THR\)）即被认为是”frequent”，并且作为单个feature进行学习。其余”infrequent” features被当成是一个特殊的dummy feature：Others。在经过这样的处理后，每个feature通过某些策略（比如：auto-increment、hash-coding）会被映射到一个唯一id上等。出于简洁性，我们会采用一个auto-increment policy F。在batch模式下，policy F从头开始构建，它会给fixed size window的训练数据中的每个features分配唯一ids，其中unique ids会1-by-1的方式自增。

然而，使用incremental模式训练会带来额外问题，因为当新数据进来时，新features会出现。如图4所示，new data的每个块都会带来一个特定比例的new features。例如，从criteo数据集上观察到，对比起在该块前存在的features集合，new data的第一块会带来12%的new features，而第14个块仍会带来4%的new features。因此，当新数据进来时，policy F需要自增更新。可能会出现：一个feature x之前被认为是Others；在new data进来后，如果该feature x的出现次数S[x]大于THR阈值，会被认为是一个唯一的feature。

图4 来自criteo dataset观察到的，随着new data的blocks进来，new features对比起已存在features集合的比例

在分配合适的ids给所有features后，IncCTR中的feature module会对已存在featurs和new features进行初始化。当我们以batch模式训练时，feature embedding \(\epsilon\)的所有值都会被随机初始化。然而，在incremental模式下，我们会对已存在的features \(\epsilon_{exist}\)的embedding和new features \(\epsilon_{new}\)的embeddings独立进行初始化。

feature模块（称为：new feature分配和feature embedding初始化）的功能如算法1所示。当new data进来时，我们首先更新每个feature（第3行）的出现次数，并继承已存在的feature分配策略（第4行）。如果来自new data的一个new feature大于该阈值（第6行），它会被添加到该policy中，id会自增1（第7行）。feature embeddings会根据一个feature是否为新来独立初始化。对于一个已经存在的feature，它会继承来自已存在模型的embedding作为它的初始化（行11）。这样的继承会将历史数据的知识转移到将自增训练的模型上。对于一个new feature，它的embedding会随机初始化，因为没有先验知识提供（行12）。

算法1

3.2 Model模块

在本节中，我们引入在IncCTR中的model模块，它会对模型进行合适训练，这样：模型仍会“记住（remember）”来自历史数据的知识，同时也会从new data上做出一些“升级（progress）”。

Fine-tune

除了已存在features的embedding外，network参数也从已存在模型继承，作为warm-start。为了使用incremental模式对模型参数进行fine-tune，我们会使用一些auxiliary tricks来达到较好表现。例如，对于\(\epsilon_{exist}\)我们会使用一个比\(\epsilon_{new}\)更低的learning rate。fine-tune的训练细节在算法2的第19-第25行进行表示。该模型会通过在prediction和ground truth间以最小化cross entropy的方式来进行最优化。我们会对该模型训练一定数目的epochs，其中：经验上我们设置数目epoch为1（第25行）。

算法2

知识蒸馏（Knowledge distillation）

除了以上的”fine-tune”外，我们引入了knowledge distillation（KD）方法来增强来自历史数据学到的知识（名义上，为了避免灾难性忘却（catastrophic forgetting））。Hinton[6] 出于高效部署，使用KD来将一个模型ensemble将knowledge转移到单个模型上，其中KD loss会被用来保留来自较重模型（cumbersome model）的知识，通过鼓励distilled model的outputs来逼近cumbersome model。相似的，LwF[7]的作者执行KD来学习新任务，并且能保持在老任务上的知识。借用相似的思想，KD可以被用在incremental learning场景中来学习来自incoming data的新知识，并保留在historical data上的记忆。

当我们在IncCTR上使用KD时，我们提供了一些关于设计teacher model的参考。有两种选项。

• KD-batch：使用batch模式训练的过期模型（outdated model），可以做为teacher model的一个天然选择来对incremental model进行distill，它会保持在一个fixed-size window上的历史数据的效果。我们使用batch模式并使用这样的teacher进行训练的KD方法称为“KD-batch”。
• KD-self：由于batch模式训练一个模型作为teacher model，需要额外的计算资源，执行之前的incremental model作为teacher要更方便。在这种情况下，后继的incremental model会在之前incremental model的监督下进行训练。我们将这样的设计称为“KD-self”。相似的思想，在BANs中有使用，其中一个后继的student model会随机初始化，通过前一teacher model进行教导，多个student后代的ensemble是为了达到可期的表现。在图片识别领域上，所有模型会以batch模式进行训练，这与我们的框架非常不同。

当执行KD时，我们会利用soft targets \(Y_{soft}\)，它由teacher model在incoming data上生成。objective function如下进行公式化：

…(2) (3) (4)

新的objective function会对标准的二元cross-entropy \(L_{CE}(\cdot)\)（其中：\(Y\)和\(\hat{Y}\)分别表示groundtruth和outputs）、KD loss \(L_{KD}(\cdot)\)进行组合。

• KD loss \(L_{KD}(\cdot)\)：是在\(\hat{Y}\)和\(Y_{soft}\)间的cross entropy（其中：\(Y_{soft}\)是teacher model的prediction），它基于logits Z和\(Z_{soft}\)。
• 变量\(\tau\)被用来获得soft targets
• R是正则项。

等式(2)中的loss function的目的是：distilled model的知识应对于new data来说是精准的（第一项），而它与teacher model的知识不应该有大的不同（第二项）。

KD-batch和KD-self的训练细节在算法2中的第3行到第5行，第11行到第17行有描述。KD-batch和KD-self间的差异是：teacher模型\(Teacher_t\)如何被训练。记住：在KD-batch中的teacher model是一个使用过期模型，而在KD-self中的teacher model是前一个incremental model。我们会在实验部分对它们的效果进行对比。给定input data的features，incremental模型\(M_t\)和teacher模型\(Teacher_t\)会做出预测，如第4和第13行。接着，incremental模型\(M_t\)通过最小化等式(2)的loss function进行最优化，如第14行。当模型训练至少一个epoch时训练过程会终止，KD loss会停止减少，第17行。

3.3 Data模块

从数据的视角看，对于灾难性忘却问题（catastrophic forgetting）一种简单的解决方法是：不只基于new data来训练incremental模型，同时也基于一些选中的historical data。我们计划实现一个data reservoir来提供合适的训练数据给incremental training。在existing reservoir中的一些比例的数据，和new data会互相交错构成new reservoir。在该模型中，一些问题需要进行确认，比如：在已存在的reservoir中需要保留多少比例的数据。data模块的实现目前还没完成，它是要完成框架的将来工作的一部分。

4.实验

在这部分，我们会在一个公开bechmark和私有数据集上进行实验，目标是回答以下问题：

• RQ1: IncCTR的效果 vs. batch模式的效果？
• RQ2: 在IncCTR框架中不同模块的贡献？
• RQ3: IncCTR的效率 vs. batch模式？

4.1 Dataset

为了评估在IncCTR框加中提出的效果和效率，我们在公开benchmark和私有数据集上做了实验。

• Criteo。该数据集用于CTR预估的benchmark算法。它包含了24天的连续流量日志，包括26个类别型features以及13个numerical features，第一行作为label，表示该ad是否被点击
• HuaweiAPP。为了演示提出方法的效果，我们在商业数据集上做了离线实验。HuaweiAPP包含60个连续天的点击日志，包含了app features、匿名的user features和context features。

为了减小复制实验结果的目的，我们在criteo数据集上做了数据处理的细节。根据kaggle比赛，涉及datasampling、discretization以及feature filtering。出于商业原因，我们没有给出huaweiAPP的处理细节，但过程基本相似。

• Data sampling：考虑数据的imbalance（只有3%的样本是正），与[12]相似，我们将负样本做down sampling，将正样本比例接近50%
• 离散化：类别型和数值形features都存在在Criteo数据集中。然而，两种类型的features的分布本质是相当不同的[11]。在大多数推荐模型中，numerical features通过buckeing或logarithm被转换成categorical features。根据上述方式，我们使用logarithm作为离散方法：

…(5)

• Featrue filtering：不频繁的features通常带的信息少，可能是噪声，因此模型很难学到这样的features。因此，根据[11]，在一个特定field中的features出现次数少于20次会被设置成一个dummy feature：others。

4.2 评估

Evaluation指标：AUC和logloss（cross-entropy）. AUC和logloss的提升在0.1%才被认为是一个ctr预估模型显著提升[1, 4, 15]。

baseline。使用batch模式训练的模型被用于baseline，来验证IncCTR的效果和效率。为了进一步评估模型的更新延迟（delay updating）上的影响，我们考虑使用不同的delay days的baseline。更特别的，\(Batch_i(i=0,1,2,3,4,5)\)表示baseline model具有i天的延迟。

实验细节：为了专注于deep ctr的效果和效率，当使用batch模式和IncCTR增量方式训练时，我们选择流行的deep CTR模型DCN来进行对比。

为了模似在工业界场景的训练过程，实验会在连续几天上做出。当使用batch模式进行训练时，所有数据都会使用在fixed size window内（例如：在size-w window中的数据[s, s+w), 其中\(s \in [0, T-w]\)）。当使用增量模式训练时，只有具有新来天的（coming day）数据（例如：在window [s, s+1)中的size-1，其中\(s \in [w, T-1]\)）提供。对于增强模型，在第一个incremental step之前，会使用batch模式训练的模型进行warm-start。也就是说，我们首先训练一个使用batch模式在[0,w)上的warm-started模型，接着会在第w天的数据上训练首个增量模型。对于criteo数据集，我们设置w=7，T=23；对于HuaweiAPP我们设置w=30，T=59作为HuaweiAPP dataset。

4.3 RQ1: 整体表现

4.4 RQ2: Ablation Studies

4.5 RQ3: 效率

…

参考

• 1.https://arxiv.org/pdf/2009.02147.pdf

jd在《Reinforcement Learning to Optimize Long-term User Engagement in Recommender Systems》对long-term engagement做了建模。

摘要

Feed流机制在推荐系统中广泛被采用，特别是移动Apps。Feed streaming setting提供用户无限feeds的交互形式。这种形式下，一个好的推荐系统会更关注用户的粘性，通常以long-term user engagement的方式进行measure。这与经典的instant metrics相差较大。直接对long-term engagement直行优化是一个non-trivial问题，因为learning target通常不能由传统的supervised learning方法提供。尽管RL天然适合于对long term rewards最大化的最优化问题，应用RL来最优化long-term user engagement仍然面临着以下挑战：

• 用户行为是多变的，它通常包含两者：instant feedback（比如：clicks）以及delayed feedback（比如：停留时长（dwell time）,再次访问（revisit））；
• 另外，执行有效的off-policy learning仍然不成熟，特别是当结合上bootstrapping和function approximation时。

为了解决该问题，在该工作中，我们引入了一个RL framework——FeedRec来最优化long-term user engagement。FeedRec引入了两个部分：

• 1) 一个Q-Network，它以hierarchical LSTM的方式设计，会建模复杂的用户行为
• 2) 一个S-Network，它会模拟enviroment，协助Q-Network并避免在policy learning上的收敛不稳定。

实验表明，FeedRec在优化long-term user engagement上要胜于SOTA的方法。

介绍

推荐系统通过建议最匹配用户需求和喜好的商品，在信息搜索任务中帮助用户进行发现。最近，用户可以浏览由无限刷的feeds流生成的items，比如：Yahoo News的新闻流，Facebook的social流，Amazon的商品流。特别的，当与商品流交互时，用户会点击items并浏览items的详情。同时，用户可能也会跳过不够吸引人的items，并继续下刷，并有可能由于过多冗余的、不感兴趣的items的出现而离开系统。在这样的环境下，优化点击（clicks）不再是黄金法则。最大化用户的交互满意度，有两部分：

• instant engagement（比如：click）
• long-term engagement（比如：粘性 stickiness）：通常表示用户会继续更长时间停留在streams上，并在后续重复打开streams

然而，大多数传统的推荐系统只关注于优化instant metrics（比如：CTR：点击率、CVR：转化率 conversion rate）。随着更深的交互，一个商品feed流推荐系统应不仅带来更高的CTR，同时也能保持用户与系统的活跃度。Delayed metrics通常更复杂，包括：在Apps上的dwell time，page-view的深度，在两个visits间的internal time等。不幸的是，由于建模delayed metrics的难度，直接优化delayed metrics非常具有挑战性。而一些前置工作[28]开始研究一些long-term/delayed metrics的最优化，希望找到一种系统解决方案来最优化overall engagement metrics。

直觉上，RL天生是最大化long-term rewards的，可以是一个unified framework来最优化instant和long-term user engagement。使用RL来最优化long-term user engagement本身并不是一个non-trivial问题。正如提到的，long-term user engagement是非常复杂的（例如：在多变行为上的measure，比如：dwell time, revisit），需要大量的enviroment interactions来建模这样的long term行为，并有效构建一个推荐agent。作为结果，通过在线系统从头构建一个recommender agent的代价很高，因为许多与不成熟的推荐agent的交互会伤害用户体验，甚至惹恼用户。另一种可选的方法是利用logged data构建一个离线的recommender agent，其中，off-policy learning方法会缓和trial-and-error search的开销。不幸的是，在实际推荐系统中，包括Monte Carlo(MC)和temporal difference(TD)在内的当前方法，对于offline policy learning具有缺陷：MC-based方法会有high variance的问题，尤其是在实际应用中当面对大量action space（例如：数十亿candidate items）；TD-based方法可以通过使用bootstrapping技术在估计时提升效率，然而，会遇到另一个大问题：Deadly Triad（致命的三）：例如：当将function approximation、bootstrapping、offline training给合在一起时，会引起不稳定（instability）和分歧（divergence）问题。不幸的是，推荐系统中的SOTA方法，使用neural结构设计，在offline policy learning中会不可避免地遇到Deadly Triad问题。

为了克服复杂行为和offline policy learning的问题，我们这里提出了一个RL-based framework，称为FeedRec，来提升推荐系统中的long-term user engagement。特别的，我们将feed streaming推荐看成是一个Markov decision process(MDP)，并设计了一个Q-Network来直接最优化user engagement的metrics。为了避免在offline Q-learning中收敛不稳定的问题，我们会进一步引入S-Network，它会模拟environments，来协助policy learning。在Q-Network中，为了捕获多变的用户long-term行为的信息，会通过LSTM来建模用户行为链（user behavior chain），它包括所有的rough behaviors，比如：click、skip、browser、ordering、dwell、revisit等。当建模这样的细粒度用户行为时，会有两个问题：特定用户actions的数目是十分不平衡的（例如：click要比skips少很多）；long-term user behavior的表示更复杂。我们会进一步使用temporal cell集成hierarchical LSTM到Q-Network来对fine-grained用户行为进行characterize。

另一方面，为了充分利用历史logged data，并避免在offline Q-Learning中的Deadly Triad问题，我们引入了一个environment模型，称为S-network，来模拟environment并生成仿真的用户体验，协助offline policy learning。我们会在模拟数据集和真实电商数据集上进行实验。

主要贡献如下：

• 1) 提出了一个RL模型FeedRec，它会直接对user engagement进行最优化（同时对instant和long-term user engagement）
• 2) 为了建模多变的用户行为，它通常同时包括：instant engagement（比如：click和order）以及long-term engagement（例如：dwell time、revisit等），提出了hiearchical LSTM的结构的Q-Network
• 3) 为了确保在off-policy learning的收敛，设计了一个有效、安全的训练框架
• 4) 实验结果表明，提出的算法要胜过SOTA baseline

2.相关工作

略

3.问题公式化

3.1 Feed Streaming推荐

在feed流推荐中，推荐系统会在离散的time steps上与一个user \(u \in U\)进行交互：

在每个time step t上，agent会feeds一个item \(i_t\)，并从该user上接收一个feedback \(f_t\)，其中\(i_t \in I\)会来自推荐的item set，\(f_t \in F\)是用户在\(i_t\)上的feedback/behavior，包括：点击、购买、跳过、离开等。交互过程形成一个序列：\(X_t = \lbrace u, (i_1, f_1, d_1), \cdots, (i_t, f_t, d_t) \rbrace\)，其中：\(d_t\)是在推荐上的dwell time，它表示用户在推荐上的体验偏好。

给定\(X_t\)，agent需要为下一个item step生成\(i_{i+1}\)，它的目标是：最大化long term user engagement，例如：总点击数（total clicks） 或 浏览深度（browsing depth）。在本工作中，我们关注于在feed streaming场景如何提升所有items的期望质量（expected quality）。

3.2 Feed Streams的MDP公式

一个MDP可以通过\(M=<S, A, P, R, \gamma>\)进行定义，其中：

• S是state space
• A是action space
• \(P: S \times A \times S \rightarrow R\)是转移函数（transition function）
• \(R: S \times A \rightarrow R\)是mean reward function ，其中：r(s, a)是immediate goodness
• \(\gamma \in [0,1]\)是discount factor。

一个(stationary) policy \(\pi: S \times A \rightarrow [0, 1]\)会在actions上分配每个state \(s \in S\)一个distribution，其中：\(a \in A\)具有概率\(\pi (a \mid s)\)。

在feed流推荐中，\(<S, A, P>\)设置如下：

• State S：是一个states的集合。我们会在time step t上的 state设计成浏览序列\(s_t = X_{t-1}\)。在开始时，\(s_1 = \lbrace u \rbrace\)只会包含用户信息。在time step t上，\(s_t = s_{t-1} \oplus \lbrace (i_{t-1}, f_{t-1}, d_{t-1})\rbrace\)会使用old state \(s_{t-1}\)进行更新，
• Action A：是一个关于actions的有限集合。可提供的actions依赖于state s，表示为A(s)。\(A(s_1)\)会使用所有recalled items进行初始化。\(A(s_t)\)会通过从\(A(s_{t-1})\)中移除推荐items进行更新，action \(a_t\)是正在推荐的item \(i_t\)
• Transition P：是transition function，其中\(p(s_{t+1} \mid s_t, i_t)\)指的是，在\(s_t\)上采取action \(i_t\)之后看到state \(s_{t+1}\)的概率。在我们的case中，来自用户的feedback \(f_t\)的不确定性会根据\(t_t\)和\(s_t\)进行。

3.3 User Engagement和Reward function

之前提到，像传统推荐中，即时指标（instant metrics，比如：点击、购买等）不是用户engagement/satisfactory的唯一衡量，long term engagement更重要，它通常会以delayed metrics进行衡量，例如：浏览深度（browsing depth）、用户重复访问（user revisits）、在系统上的停留时长（dwell time）。RL learning会通过对reward functions进行设计，提供一种方式来直接对instant和delayed metrics进行直接最优化。

reward function \(R: S \times A \rightarrow R\)可以以不同的形式进行设计。我们这里会假设：在每一step t上的user engagement reward \(r_t(m_t)\)会以不同metrics进行加权求和的形式（weighted sum），来线性（linearly）地对它进行实例化：

…(1)

其中：

• \(m_t\)由不同metrics的column vector组成
• \(\omega\)是weight vector

接着，我们根据instant metrics和delayed metrics给出一些reward function的实例。

3.3.1 Instant metrics

在instant user engagement中，我们会具有clicks、purchase（商业上）等。instant metrics的公共特性是：这些metrics由current action即时触发。此处我们以click为例，第t次feedback的click数可以定义成：

3.3.2 Delayed metrics

delayed metrics包括：browsing depth、dwell time、user revisit等。这些metrics通常会被用于衡量long-term user engagement。delayed metrics会由之前的行为触发，其中一些会具有long-term dependency。这里提供会提供delayed metrics的两个示例reward functions：

1.深度指标（Depth metrics）

由于无限下刷机制，浏览的深度是在feed流场景下的一个特殊指标器（special indicator），它会与其它类型的推荐相区别。在观看了第t个feed之后，如果用户仍然在系统中并且继续下刷，系统会对该feed进行reward。直觉上，depth \(m_t^d\)的metric可以被定义成：

其中，\(\#scans(f_t)\)是第t个feedback的scans的数目。

2.返回时间指标（Return time metric）

当用户对推荐items很满意时，通常他会更经常性地使用该系统。因此，在两个visits间的间隔时间（interval time）可以影响系统的用户满意度。return time \(m_t^r\)可以被设计成时间的倒数（reciprocal of time）:

其中：

• \(v^r\)表示在两次visits间的time
• \(\beta\)是超参数

从以上示例（click metric、depth metric以及return time metrics），我们可以清楚看到：\(m_t = [m_t^c, m_t^d, m_t^r]^T\)。注意，在MDP setting中，累积收益（cumulative rewards）是可以被最大化的，也就是说，我们实际上对总浏览深度（total browsing depth）、未来访问频次进行最优化，它们通常是long term user engagement。

4. 推荐系统的Policy learning

为了估计future reward（例如：未来用户粘性），对于推荐项\(I_T\)的expected long-term user engagement会使用Q-value进行表示：

…(2)

其中：

• \(\gamma\)是discount factor，用来对current rewards和future rewards的importance进行balance
• \(Q^{*}(s_t, i_t)\)具有由optimal policy达到的最大expected reward，应遵循optimal Bellman方程[24]：

…(3)

给定\(Q^{*}\)，推荐项\(i_t\)会使用最大的\(Q^{*}(s_t, i_t)\)选中。在真实推荐系统中，由于大量的users和items，为每个state-action pairs估计action-value function \(Q^{*}(s_t, i_t)\)是可行的。因而，使用函数逼近（例如，neural networks）来估计action-value function很灵活和实际，例如：\(Q^{*}(s_t, i_t) \approx Q(s_t, i_t; \theta_q)\)。实际上，neural networks对于跟踪用户在推荐中的兴趣表现很好。在本paper中，我们提到，使用参数\(\theta_q\)的nural network function approximator作为一个Q-network。Q-network可以通过最小化mean-squared loss function进行训练，定义如下：

…(4)

其中，\(M = \lbrace (s_t, i+t, r_t, s_{t+1}) \rbrace\)是一个大的replay buffer，它会存储过去的feeds，我们从中以mini-batch training的方式进行抽样。通过对loss function进行微分，我们可以达到以下的gradient：

…(5)

实例上，通过SGD来最优化loss function通常计算效果，而非计算以上gradient的full expectations。

4.1 Q-Network

Q-network的设计对于性能很重要。在long-term user engagement最优化中，用户的交互行为反复无常（例如：除了click外，还有dwell time、revisit、skip等），这使得建模变得non-trivial。为了有效对这些engagement进行最优化，我们会首先从这样的行为收到信息传给Q-Network

4.1.1 Raw Behavior Embedding Layer

该layer的目的是，采用所有raw behavior信息，它们与long term engagement有关，来distill用户的state以便进一步最优化。给定observation \(s_t= \lbrace u, (i_1, f_1, d_1) \cdots, (i_{t-1}, f_{t-1}, d_{t-1}) \rbrace\)，我们让\(f_t\)是在\(i_t\)上所有用户行为的可能类型，包括：点击、购买、跳过、离开等，其中\(d_t\)是该行为的dwell time。\(\lbrace i_t \rbrace\)的整个集合首先被转成embedding vectors \(\lbrace i_t \rbrace\)。为了表示将信息feedback给item embedding，我们将\(\lbrace i_t \rbrace\)投影到一个feedback-dependent空间中，通过使用一个projection matrix来对embedding进行乘积，如下：

其中，\(F_{f_t} \in R^{H \times H}\)是对于一个特定feedback \(f_t\)的投影矩阵，为了进一步建模时间信息，会使用一个time-LSTM来跟踪user state随时间的变化：

…(6)

其中，Time-LSTM会建模dwell time，通过引入一个由\(d_t\)控制的time gate：

其中，\(c_t\)是memory cell。 。。。

4.1.2 Hierarchical Behavior Layer

为了捕获我变的用户行为信息，所有rough behaviors会顺序feed到raw Behavior Embedding layer中。在实际中，特定user actions的数目是极其不均的（例如：点击数要少于skips数）。因此，直接利用raw Behavior Embedding Layer的output会造成Q-Network从sparse user behaviors中丢失信息，例如：购买信息会被skips信息会淹没。另外，每种类型的用户行为具有它自己的特性：在一个item上的点击，通常能表示用户当前的偏好，在一个item上的购买会暗示着用户兴趣的转移（shifting），而skip的因果关系更复杂，可能是：随意浏览（casual browsing）、中立（neutral）、或者觉得不喜欢（annoyed）等。

图1

为了更好表示user state，如图1所示，我们提供一种hierarchical behavior layer来加到raw beahiors embedding layers中，主要的用户行为，比如：click、skip、purchase会使用不同的LSTM pipelines进行独立跟踪：

f_t是第k个行为，其中，不同的用户行为（例如：第k个行为）会通过相应的LSTM layer来进行捕获，以避免被大量行为支配（intensive behavior dominance）、并捕获指定的特性。最后，state-action embedding会通过将不同用户的behavior layer和user profile进行concate起来：

其中，u是对于一个指定用户的embedding vector。

4.1.3 Q-value layer

Q-value的逼近（approximation）通过具有dense state embedding的input的MLP来完成，item embedding如下：

\(\theta_q\)的值会通过SGD进行更新，梯度计算如等式(5)所示。

4.2 off-policy learning任务

有了Q-learning based framework，在学习一个稳定的推荐policy之前，我们在模型中通过trial&error search来训练参数。然而，由于部署不满意policies的开销以及风险，对于在线训练policy几乎是不可能的。一个可选的方式是，在部署前使用logged data D训练一个合适的policy，它通过一个logging policy \(\pi_b\)收集到。不幸的是，等式(4)的Q-Learning framework会到到Deadly Trial问题，当对函数近似（function approximation）、bootstrapping以及offline training进行组合时，会出现这种不稳定和差异问题。

为了避免在offline Q-Learning中的不稳定和差异问题，我们进一步引入一个user simulator（指的是S-Network），它会对environment进行仿真，并帮助policy learning。特别的，在每轮推荐中，会使用真实user feedback进行对齐（aligning），S-Network需要生成用户的响应\(f_t\)、dwell time \(d_t\)、revisited time \(v^r\)，以及一个二元变量\(L_T\)，它表示用户是否会离开平台。

图2

如图2所示，simulated user feedback的生成使用S-Network \(S(\theta_s)\)，它是一个multi-head neural network。State-action embedding被设计在与Q-Network中相同的结构中，但具有独立的参数。layer \((s_t, i_t)\)会跨所有任务进行共享，其它layer （图2中的\((s_t, i_t)\)）是task-specific的。因为dwell time和用户的feedback是inner-session的行为，\(\hat{f}_t\)和\(\hat{d}_t\)的计算如下：

其中：

\(X_*\)和\(b_*\)是weight项和bias项。\([s_t, i_t]\)是state action feature的核心。revisiting time的生成、以及离开平台（inter-session 行为）的完成如下：

4.3 Simulator Learning

略

5.Simulation研究

略

6.实验

介绍

4.实验

略

参考

• 1.https://arxiv.org/pdf/1902.05570.pdf

<Returning is Believing: Optimizing Long-term User Engagement in Recommender Systems>

3.方法

我们提出了从顺序决策最优化的角度，在推荐中改进long-term user engagement。

参考

• 1.https://arxiv.org/pdf/2001.03025.pdf

google有一篇关于dynamic embedding的paper介绍。我们来看下。注：本paper的前面几部分感觉很凑数。最好直接从3节开始即可。

摘要

深度学习模型的一个限制是：input的sparse features，需要在训练之前定义好一个字典。本文提出了一个理论和实践系统设计来解决该限制，并展示了模型结果在一个更大规模上要更好、更高效。特别的，我们通过将内容从形式上解耦，来分别解决架构演进和内存增长。为了高效处理模型增长，我们提出了一个新的neuron model，称为DynamicCell，它受free energy principle的启发，引入了reaction的概念来排出non-digestive energy，它将gradient descent-based方法看成是它的特例。我们在tensorflow中通过引入一个新的server来实现了DynamicCell，它会接管涉及模型增长的大部分工作。相应的，它允许任意已经存在的deep learning模型来有效处理任意数目的distinct sparse features（例如：search queries），可以不停增长，无需重新定义模型。最显著的是，在生产环境中运行超过一年它仍是可靠的，为google smart campaingns的广告主提供高质量的keywords，并达到极大的accuracy增益。

1.1 Motivation

为了理解一些已存在的深度学习库的限制，我们考虑一个简单示例：对每天的来自在线新闻上的新闻文章上训练一个skip-gram模型。这里模型的训练实例是相互挨着的一些words，期望的实现是将每个word映射到一个vector space上，它们在语义空间中也相接近。为了实验word2vec算法，我们需要定义一个字典变量，它包含了待学习embeddings的所有的words。由于在训练前需要一个字典（dictionary），这限制了模型的增长，很难处理从未见过的words或者增加embedding的维度。

1.2 核心

为了更好适应模型增长，我们尝试搜寻一个框架，它可以将一个neural network layer的input/output看成是满足特定分布的充分统计(sufficient statistics)（即：embeddings），我们提出了一个与free energy principle的概念有关的新neuron model称为DynamicCell。直觉上，通过对interal state进行调节(regulating)及行动(take actions)，可以最小化它的自由能（free energy）。另外，当input包含了non-digestive energy时，它也会通过reaction将它们排出(discharge)，以维持一个稳定的internal state。我们可以看到对free-energy priciple做小修改，可以让它与传统的gradient descent-based算法来关联。因此，对一个layer的一个input signal可以被连续（continuously）或组合（combinatorially）的方式处理。例如，当在input端上看到一个新的input feature时，该layer可以为它动态分配一个embedding，并将它发送到upstream layers上以便进一步处理。

为了实现上述思想，会对tensorflow做出一些修改。特别的，会在tensorflow python API中添加一些新的op集合，来直接将symbolic strings作为input，同时当运行一个模型时，”intercept” forward和backward信号。这些op接着会访问一个称为“DynaimicEmbeddding Service(DES)”的新的server，来处理模型的content part。在模型的forward execution期间，这些op会为来自DES的layer input抽取底层的float values（embeddings），并将这们传递给layer output。与backward execution相似，计算的gradients或其它信息，会被传给DES，并基于用户定制的算法来更新interal states。

实际上，DES扮演着扩展Tensorflow的角色，主要有以下几方面影响：

• embedding data的虚拟无限容量（Virtually unlimited capacity）：通过与外部存储系统（比如：Bigtable或Spanner）合作，可以将模型能力逼近存储的上限。实际上，我们的系统可以与任意支持kv数据的lookup/update的存储系统相适应
• 灵活的梯度下降更新：DES可以保持关于一个layer的全局信息，比如：词频或平均梯度变化，来帮助它决定何时更新一个embedding。Gradient descent update对于每个变量来说不再是均齐过程 (homogeneous process)，每个layer通过采用合适的actions可以维护它自己的“homeostasis”。同时，它也保证了我们的系统与任意gradient descent optimizers（SGD、AdaGrad、Momentum）是后向兼容的。
• 高效：在DES上的计算/内存加载会自动分布到云平台的worker机上。训练速度与tensorflow workers成正比，模型容量（capacity）由DynamicEmbedding workers的数目决定。
• 可靠性：有了DES，tensorflow模型可以变得非常小，因为大多数数据都被保存到像Bigtable的额外存储中。因此，当训练一个大模型时对于机器失败（由于超过资源限制）变得很有弹性。
• 对迁移学习或多任务学习的支持：通过采用tensorflow的embedding data，多个模型可以共享相同的layer，只需要简单使用相同的op name以及DES配置即可。因此，模型会共享一个norm，而非一个option。

我们的DynamicEmbedding系统被证明是在大规模深度学习系统中非常重要的，并且它在多个应用中稳定运行超过一年。带DynamicEmbedding的tensorflow模型可以和不带该功能的tensorflow运行一样快，新增的优点是：更大的capacity，更少的编码，更少的数据预处理工作。工程师切换到DynamicEmbedding的主要工作是：学习新的APIs和配置额外的存储（比如：Bigtable或Spanner），这可以尽可能的简化。

在过去两年，由于我们的系统上线，我们移植了许多流行的模型，特别是涉及到在训练前需要sparse features的模型，它们可以满足来自input的持续增长。例如，image annotation中使用upgraded Google Inception模型，它可以从来自海量搜索queries的lables中进行学习；用于机器翻译的GNMT的模型，它可以被用于将句子翻译成多数语言描述；我们升级版的Word2vec可以以任意语言快速发现与任意root query相似的的queies。

通过采用DynamicEmbedding, 我们发现，单个不需要任意预处理的模型足够达到令人满意的效果。特别的，对比其它rule-based系统，我们的sparse feature models之一（从网站内容中给出关键词suggesting）可以达到相当高的accurate结果。通过允许系统由数据自我演化来驱动，它可以快速胜过其它需要人工调整的系统。

系统总览：

图1

图1展示了我们添加到tensorflow的扩展组件的总览。整体目标是：让存在的tensorflow APIs只处理模型的static part：定义nodes，connections，将数据相互间进行传递，并将trainable variable的lookup/update/sample操作传到DynamicEmbedding Service(DES)上来允许它们构建和动态增长。另外，我们也需要定义一个新的python APIs集合，它可以直接将string Tensors作为input，将它们的embeddings作为output。这些tensorflow APIs可以直接访问一个称为DynamicEmbedding Master(DEM)的组件，它们会将实际job轮流分发给DynamicEmbedding Workers(DEWs)。DEWs负责embedding lookup/update/sample，并与外部云存储（比如：Bigtable或Spanner）进行通信，并基于多种gradient descent算法来更新embedding values。

2.数学公式

free energy principle的一个基本思想是，规定：一个生态系统趋向于最小化“surprise”，定义为：

其中：

• s是一个系统的当前internal和external state；
• m是解释s的一个internal model

我们可以将这样的思想与neural networks相关联，通过将”surprise”重定义为一个具有contextual inputs与不具体congextual input的state分布间的差异（通过KL-divergence衡量），分别表示成：\(P(w \mid c)\)和\(P(w)\)。对于上述原始的公式，我们的新方式可以在一个cell level上实现，不再需要使用一个内部预测模型m来解释state s（它本身可以是一个非常复杂的process）。我们展示了BP算法在embedding space的free-energy最小化的一个通用过程，它会给人工神经网络（artificial neural network：ANN)带来一个新的思路：一个ANN是关于inter-connected neurons的一个group，它会最小化自己的free energy。在其余部分，我们会详细解释neural networks的新方法，以及它带来的实际影响，比如：现实中的一个系统设计和提升。

2.1 Exponential family, embedding和人工神经网络

使用neural networks来表示sparse features的represent已经在自然语言模型中广泛探索。本质上，在neural network中的layer仅仅只是它的variables对于特定分布\(P(w_1, \cdots, w_n \mid c_1, \cdots, c_m)\)的充分统计。[47]更进一步将这样的思想泛化到许多已经存在的DNN模型中，并派生了embedding space的一个新等式，来解释contextual input到output的相关度。例如，在NN中的一个layer可以被看成是在embedding空间中\(P(w \mid c)\)分布的一个表示，其中：c是layer的contextual input，w是output。

更进一步假设：

其中：\(\vec{w}\)和\(\vec{c}\)分别表示w和c的embeddings

接着一个layer可以基于\(\vec{c}\)来简单计算\(\vec{w}\)。

这与传统观念：neurons相互间基于单个动作电位进行通信（action potentials：表示成1D function（二元binary or 连续continuous））来说是个挑战。另外，它偏向于一个更现实的观点：neurons实际上会与它们的firing patterns【9】相通信，以便单个neuron不会只与单个bit相通信。【47】采用了probability作为一种描述firing patterns分布的通用语言，并使用embeddings(sufficient statistics)来表示它们的近似形式。

DNN的另一个视角的一个明显优化是：建模能力。如果我们限制AI来定义activation function的组合，不管我们赋予它们什么含义，他们总是会落入解决非常相似形式的问题：

…(1)

其中，D表示一整个training data或一个mini-batch。等式(1)的gradients可以通过使用chain rule来对可学习参数集合\(\theta_i\)进行计算，对于每个\(f_i, i=1, \cdots, n\)：

…(2)

从\(f_1\)到\(f_n\)递归计算\(\frac{\partial L(x,\theta)}{\partial f_i}\)和\(\frac{\partial L(x,\theta)}{\partial \theta_i}\)的算法，称为“back-propagation”。定义一个loss function，接着通过back-propagation算法来求解它是人工神经网络的标准做法。

从上面的过程，如果back-propagation算法一次只运行一个batch，可以看到我们可以更改x或\(\theta_i, i\in \lbrace 1,2,\cdots,n \rbrace\)的维度。然而，已存在的deep learning库的设计不会将它考虑成一个必要特性。在本节其余部分，我们提出了一个新框架来解释模型增长。

2.2 增长需要

一个智能系统的一个基本需要是：能够处理来自感知输入（sensory input）的新信息。当我们在一个neural network中处理一个新的input时，必须将它转化成一个representation，可以由像等式（1）（其中\(x \in R^m\)）的loss function处理。特别的，如果该input涉及到离散对象（比如：words）时，它必须将它们映射到一个embedding space中。对于该需求的一个naive解释可以从neural network的视角看：一个discrete input c可以被表示成一个特征向量（one-hot）：\(\vec{c}_{0/1} = [0, \cdots, 1, \cdots, 0]^T\)，接着通过一个linear activation layer，它可以变成\(W \vec{c}_{0/1}=W_i\)，其中\(W_i\)表示real matrix W中的第i列，或等价的，c就是embedding。这样的解释可以说明：这对于使用sparse input values的DNN实现来说是个限制，以及为什么总是需要一个字典（比如：一个字典定义为W）。

实际上，特征向量\(\vec{c}_{0/1}\)的维度（比如：W中的列数）可以增长到任意大，embedding维度（比如：W中的行数）也会相应增长。为了观察embedding dimension为什么增长，我们对neural network layers采用sufficient statistics的视角，一个基本事实是一个embedding的每个dimension都应该被限定。也就是说，假设neural network的一个layer表示了\(P(w \mid c) \propto exp(\langle \vec{w}, \vec{c} \rangle)\)。那么，两个inputs \(c_1\)和\(c_2\)它们相应的分布相互完全分离，它们可以被认为是不同的。假设：\(P_{c_1}(w) \equiv P(w \mid c_1)\)并且\(P_{c_2}(w) \equiv P(w \mid c_2)\)，这可以表示成：

…(3)

其中，\(D_{KL}(P \mid Q)\)表示两个分布P和Q间的KL散度，\(\delta > 0\)是一个threshold。通过将embedding的形式\(P(w \mid c)\)（例如：\(P(w \mid c) \propto exp(<\vec{w}, \vec{c}>)\)）代入到上面的等式，我们可以获得：

…(4)

几何上，它会沿着方向\(\vec{c_1} - \vec{c_2}\)来计算vector \(\vec{w}\)的平均长度。由于\(\vec{c}\)的长度是限定的，当distinct c的数目增长时，让等式(3)的不等式总是成立的唯一方法是：增加\(\vec{c}\)和\(\vec{w}\)的维度。直觉上可以简单地说：为了在一个限定空间中填充更多objects，以便它们相互间隔得足够远，我们必须扩展到更高维度上。

2.3 新的neuron model: DynamicCell

现在，我们已经解决了为什么（why）一个AI系统会增长，另一个问题是how：一组neurons只通过input/output signals相互连接，在一起工作来达到整体的稳态？一个理想的neuron model不应解释单个cell是如何工作的，而是要泛化到groups of cells，甚至groups of organisms。更好的是，它也能解释在deep learning中广泛使用的已经存在方法（比如：BP算法）的成功。

2.3.1 free energy principle的动机

free energy principle是为了理解大脑的内部运作而发展起来的，它提供给我们一些线索：关于如何在neural network learning上构建一个更统一的模型。必要的，它假设一个生物系统通过一个马尔可夫毯(Markov blanket：它会将internal state与外部环境相隔离）闭环，通信只通过sensory input和actions发生。生物系统的整体目标是：不论内部和外部，维持一个稳态(homeostasis)，从而减小内部和外部的free energy(surprises)。

然而，如果一个组织（organism），通过Markov blanket闭环，可以通过变更internal states来最小化free energy，并且/或者 与环境（environment）交互，如果两者都失败怎么办？例如，当一个人听到关于一个不幸新闻时，他不会有任何反映发生，变更internal state可能只会破坏身体的体内平衡（homeostasis）。从物理角度，如果信息和energy是内部可变的，那么总的energy是守恒的，non-digestive energy也是维持稳态的一个必要方式。

图2 在DynamicCell模型中，我们通过引入reaction到free energy priciple中，构建了生命的基本单元（basic unit of life）(cell)。一个basic activity of life仍会维持它的稳态。另外，它通过变更internal states或actions，会将unexpected input “react”成一种排出过多不能被处理energy的方式。例如：笑与器都意味着分别排出good和bad surprises，它们不会对生存（survival）有贡献。换句话说：life reacts。

因此，我们可以将reaction包含到图2中，来简单改进free energy principle的思想，它会遵循物理中的能量转化定律。在我们的新模型中，每个cell或一个group（称为：organism）可以遵循相似原则：通过变更internal states和/或 actions，来最小化free energy（来自input \(\vec{c}\)的surprise），不能被最小化的过多non-digestive energy会通过reaction排出。这里的action signal \(\vec{w}\)被在位于相同Markov blanket中的其它upstream cells接收，只会影响upstream feedback \(\overleftarrow{w}\)。注意，action singal \(\vec{w}\)不同于一个organism采取的与环境交互的物理动作。在我们的模型下，物理动作可以通过upstream singal \(\vec{w}\)进行激活来做有用工作、或者通过downstream singal \(\ overleftarrow {c}\)来排出extra surprises（例如：通过笑或哭）。

2.3.2 Formulation

对了对上述思想进行数学上的公式化，我们将[47]重新resort来构建一个新的neuron model。总体上，一个neuron表示分布\(P(w \mid c)\)并且遵循[47]，它的input和output singals可以通过它们的embeddings近似表示，比如：\(P(w \mid c) = \frac{1}{Z(\vec{c})} exp(\langle\vec{w}, \vec{c}\rangle)\)，其中\(\vec{w}\)可能依赖于\(\vec{c}\)，并且\(Z(\vec{c})=\sum_{\vec{w}} exp(\langle\vec{w}, \vec{c}\rangle)\)。给定这样的假设，我们可以将free energy（或surprise）的最小化表示成两部分：internal和external。

Internal state homeostasis稳态

一个cell的internal state的稳定性在图2中反应在action state \(\vec{w}\)上。一个cell的长期行为（long-term behavior）可以与它的context c相互独立，因此可以表示成分布\(P_{\vec{w}} = P(w)\)。这里，在来自一个给定input c的一个cell的internal state上的free energy（或surprise）可以被简单表示成：

…(5)

并且，surprise最小化（minimization）意味着调整\(P(w \mid c)\)的internal参数，以便\(P(w \mid c) \approx P(w)\)。为了观察surprise最小化（minimization）是如何在embedding space中实现的，假设我们使用sufficient statistics representation \(P(w \mid c)\)，并将等式(5)重新改写：

…(6)

其中，\(H(\cdot)\)表示给定分布的entropy，它应该是相对稳定的。为了最小化等式(6)，一个cell需要达到一个这样的state：其中对应到input c的\(D_{KL} (P_{\vec{w}} \mid P_c)\)梯度是0:

…(7)

其中，我们假设：\(\frac{\partial \langle\vec{w}, \vec{c}\rangle} {\partial {\vec{c}} }\approx \vec{w}\)。注意，这与contrastive divergence算法在形式上相似，尽管他们基于完全不同的假设。

Upsteam state homeostasis稳态

upstream和downstream的不同之处是，前者的state预期是隐定的。为了对upstream states的稳定性进行measure，你可以将在upstream中信息处理的整个复杂过程看成是一个黑盒，并简单地对来自usual distribution的偏差（deviation）进行measure：

…(8)

其中，\(P_{\overleftarrow{w}}\)表示upstream feedback singal \(\overleftarrow{w}\)的分布（如图2所示）。这与等式(7)相似，我们可以获得该稳定upstream state的condition：

…(9)

通过变更\(P(w \mid c)\)的internal state，一个cell可以通过等式(6)和等式(8)进行optimize来最小化整体的surprise。均衡是在internal state和actions间的一个平衡。

Reaction

从上面的分析可知，free energy可以通过在满足等式(7)和等式(9)时达到最小化。然而，一个系统的overall state的entropy的天然趋势是增加的，因此，一个封闭的organic系统应期望来自input的一个常量的upcoming surprises。当这些surprises不能通过变更internal states（等式7）或taking actions（等式(9)）最小化时，他们必须排出到系统外（例如：通过reaction \(\overleftarrow{c}\)）。例如，其中一种总和energy（total additional energy）可以表示成：

…(10)

其中，\(\mid \cdot \mid^2\)表示element-wise square，\(\circ\)也是一个element-wise product。以下，我们会观察到该形式的选择可以天然地与loss function的梯度下降更新相联系。在定义reaction时存在许多其它可能，本paper不考虑。

与gradient descent update相联系

最终，我们来看下，上述过程是如何将常规的使用gradient descent的loss minimization做为它的一个特例的。为了观察到它，我们可以简单将action singal \(\vec{w}\)与一个loss function \(L({\vec{w}})\)相联系，假设\(\vec{w}\)返回loss的评估(evaluation)（例如：\(\vec{w} = L(\vec{w})\)）。从上述关系，在梯度近似时可以将有限差 step设置为1，我们可以得到：

…(11)

…(12)

最终，从等式(10)，我们可以达到熟悉的梯度形式：

…(13)

这与认识场景的过程相一致，大脑实际上会做某些形式的back-propagations操作。

3.系统设计

3.1 tensorflow API设计

回顾上面，在neural network中的每个layer/neuron被认为是在embedding space中的特定分布\(p(w\mid c)\)（c为input，w为output）。对于在input和output间的中间层（intermediate layers），c已经被表示成一个embedding \(\vec{c}\)，我们只需要定义一个函数来计算\(\vec{w}\)。在这样的情况下，我们可以只使用在tensorflow中相同的计算图来进行forward计算（图2中的input和action）和backward执行（在图2中的feedback和reaction），非基于梯度的更新（non-gradients based update）可以通过对tf.gradients做很微小的变化来达到。例如，一个典型的DynamicCell node可以被定义成：

def my_cell_forward(c):
    """returns action w"""

@ops.RegiestorGradient("MyCellForward")
def my_cell_backward(op, w_feedback):
    """returns reaction c_feecback"""

然而，需要特别注意：当w和c其中之一涉及到sparse features(比如：words)时，由于它可能发生在input或output layer（例如：一个softmax output layer来预测一个word）。已经存在的tensorflow实现总是需要一个字典和string-to-index转换（例如：通过tf.nn.embedding_lookup或tf.math.top_k），它们与我们的哲学（philosophy：用户只需要定义\(P(w \mid c)\)的形式，无需关注它的内容）不兼容。实际上，这些input/output操作是让tensorflow处理日益增长（ever-growing）的关键，它与input/output values是有区别的，通过将content processing的job转移给Dynamic Embedding service (DES)。另外，为了让tensorflow与DES无缝工作，我们使用单个protocol buffer来编码所有的配置，它在我们的tensorflow APIs中可以表示成input参数de_config。

3.1.1 Sparse Input

如上所述，允许tensorflow直接采用任意string作为input，这非常有用。这里我们调用该process来将任意string input转换成它的embedding dynamic embedding，使用tensorflow API定义成：

def dynamic_embedding_lookup(keys, de_config, name):
    """returns the embeddings of given keys.""""

其中：

• key：是任意shape的string tensor
• de_config：包含了关于embedding的必要信息，包含：希望的embedding维度、初始化方法（当key是首次见到时）、embedding的存储等。
• name：和config也可以唯一的区分embedding来进行数据共享（data sharing）

3.1.2 Sparse Output

当一个neural network的输出为sparse features时，它通常被用在inference问题中：\(argmax_w P(w \mid c)\)，其中c是来自之前layer的input，表示在neural network中的\(\vec{c}\)。根据第2.1节，如果我们假设\(P(W \mid C) \propto exp(\langle \bar{w}, \bar{c} \rangle )\)，其中，\(\vec{w}\)是w的embedding，接着\(argmax_w P(w \mid c) = argmax_w \langle \vec{w}, \vec{c} \rangle\)，它可以简化为：在w的所有值中，离input query \(\vec{c}\)的最近点。实际上，softmax function通常被用在neural network中，它与我们的formulation最相关。为了观察到这一点，假设w的所有可能值集合为W，\(\forall a \in W\)，softmax概率可以被表示为：

…(14)

如果\(dim(\vec{w})=dim(\vec{c}) +1\)，其中\(dim(\cdot)\)表示一个vector的维度，即落到我们的特例上。

然而，需要计算等式(14)，对于softmax output来说，当在W中的elements的数目非常大时，对于w的所有值计算cross entropy loss非常低效。幸运的是，efficient negative sampling方法已经被很好地研究[21]。在DES中必须支持它。

Candidate negatie sampling

为了允许output values具有无限数目，我们根据tf.nn.sampled_softmax_loss来定义一个内部函数实现，它需要返回logit values（）。

_compute_sampled_logits(pos_keys, c, num_samled, de_config, name):
    """returns sampled logits and keys from given positive labels."""

这里，num_sampled是一个正数，sampling strategy在de_config中定义。

TopK retrieval

这里，在训练期间需要candidate negative sampling，在inference期间，我们希望如上计算\(argmax_w P(w \mid c) = argmax_w \langle \vec{w},\vec{c} \rangle\)，在实际上，它通常来检索到给定input的top-k最近点（例如：在语言inference中beam search）。topK retrieval的interface定义如下：

def top_k(c, k, de_config, name):
    """returns top k closet labels to given activation c."""

在该场景背后，该函数会调用DynamicEmbedding server来来寻找那些接近\([\vec{c}, 1]\)的keys。

3.1.3 Saving/restoring模型

最终，在model training期间，一个模型需要被周期性保存。由于我们会将大多数数据移出tensorflow的graph外，对于维持在tensorflow与DynamicEmbedding两者保存的checkpoints间的一致性很重要。在API这一侧，每次调用DynamicEmbedding相关API时，相应的embedding data信息，会在一个global variable中保存唯一的(name, de_config)。寻于DynamicEmbedding的checkpoint saving/loading会与tensorflow非常相似：

save_path = save(path, ckpt)
restore(save_path)

如果用户使用在tensorflow中的automatic training framework，比如：tf.estimator，通过我们的high-level APIs自动处理saving/load模型。但如果他们希望在一个low level的方式，他们需要调用以上的函数和tensorflow相应的I/O函数。

3.1.4 使用DynamicEmbedding的Word2Vec模型

总之，对tensorflow API变更以支持DynamicEmbedding非常简单，对于模型构建的job也简单。做为示例，word2vec模型可以使用以下代码行来进行定义：

tokens = tf.placeholder(tf.string, [None, 1])
labels = tf.placeholder(tf.string, [None, 1])
emb_in = dynamic_embedding_lookup(tokens, de_config, 'emb_in')
logits, labels = _compute_sampled_logits(labels, emb_in, 10000, de_config, 'emb_out')
cross_ent = tf.nn.softmax_cross_entropy_with_logits_v2(labels, logits)
loss = tf.reduce_sum(cross_ent)

注意，字典的需求被完全移除。

3.2 DynamicEmbedding serving设计

如图1所示，我们的DynamicEmbedding Service(DES)涉及到两部分：DynamicEmbedding Master(DEM)和DynamicEmbedding Workers(DEWs)。前面定义的tensorflow API只会与DEM通信，它涉及到将real work分布到不同的DEWs上。为了同时达到效率和ever-growing模型，在DEWs中的每个worker会对local caching和remote storage进行balance。在该部分，我们会讨论在当前形式下DES的不同方面。

3.2.1 Embedding存储

在第2节中讨论的，neurons间的通信会被表示成firing patterns(embedding)的充分统计，它们是floating values的vectors。这些firing patterns本质上是离散的（discrete），可以被表示成string ids。这里，这些embedding data的存储只涉及到(key, value) pairs，并且不吃惊的是，我们会使用protocol buffer来处理data transfer、以及为每个embedding保存像string id, frequency这类额外信息。

当特定数据被传递到由tensorflow API定义的node中时，它会与DES通信来处理实际job。例如，在运行dynamic_embedding_look op的forward pass期间，一个batch的strings会被传递给tensorflow computation graph的一个node，它接着会询问DEM来处理实际的lookup job。在backward pass期间，feedback信号（例如：对应output的gradients）会被传递给注册的backward node中，它也需要与DEM通信来进行数据更新。

为了允许可扩展的embedding lookup/update，我们设计了一个称为EmbeddingStore的组件，它会专门与google内部的多个storage systems进行通信。每个支持的storage system实现了与基础操作（比如：Lookup(), Update(), Sample(), Import(), Export()）相似的接口，例如，一个InProtoEmbedding实现了EmbeddingStore接口，它通过将整个数据保存到一个protocol buffer格式中，它可以被用来进行local test以及训练小的data set。一个SSTableEmbedding会在training期间将数据加载进DEWs的内存中，并在GFS中将它们保存成immutable且非常大的文件。一个BigtableEmbedding允许数据同时存成local cache和remote、mutable及高度可扩展的Bigtables。因此，从worker failure中快速恢复，使得不必等待，直到所有之前的数据在接受到新请求前被加载。

3.2.2 embedding update

在我们的框架中，embedding updates会在forward和backward passes期间同时发生。对于backpropagation算法，updates只发生在当backward feedback过程中信息\(\frac{\partial{L}}{\partial{w}}\)到达时。为了保证我们的系统与已经存在的gradient descent算法（例如：tf.train.GradientDescentOptimizer或tf.train.AdagradOptimizer）完全兼容，我们需要在DEWs中实现每个算法。幸运的是，我们可以复用tensorflow相似的代码来保证一致性。注意，许多gradient descent算法（比如：Adagrad）会保存关于每个值的全局信息，它们应在gradient updates间一致。在我们的情况中，这意味着我们需要额外信息来存储到embedding中。

long-short term memory

当一个学习系统可以处理一段长期的数据时（比如：数月和数年），解决long-short term memory的主题很重要*。因为如果特定features只是短暂出现，或者在一段较长时间内没有被更新，它对inference accuracy不会有帮助。在另一方面，一些短期输入（momentary input）可能包含需要特殊处理的有价值信息，一个无偏的学习系统（unbiased learning system）应该处理这些低频数据。接着，我们提出了两个基本技术来管理embedding data的生命周期(lifetime)。

• Frequency cutoff: 每当一个embedding被更新时，使用一个定时器进行递增来记录它的更新频次（update frequency）。因此，我们可以根据它的频次基于一个cutoff value来决定该embedding是否应该被保存成一个永久存储（比如：Bigtable）。对于涉及到多个epoches的训练，tensorflow的job会告诉你：一个example是否是首次见到。
• Bloom filter: 另一个达到相似效果的流行的方法是：使用bloom filter来对低频数据进行剪枝，会更有存储效率。我们实现该特性是为了兼容已经存在的linear systems（它们已经处理了大量数据），但它们的模型比deep networks复杂度要低。

3.2.3 top-k sampling

在模型inference期间，对于高效检索离给定input activation最近的topk个embeddings很重要，其中距离通过点乘（dot product）来测量，如第3.1.2节所示。对于非常大数目的input（例如：[45]），可以很高效和近似地处理。我们会采用在google内部的实现来让在DEWs中的每个worker返回它自己的top k个embeddings给DEM。假设它们有n个DEWs，那么DEM会在\(n \times k\)个candidate vectors间选择top-k个最近点。这样，当\(k << m\)时（其中，m是keys的总数）， accuracy和efficiency会被保障。

3.2.4 Candidate sampling

当它们被储存到像Bigtable的远程存储中时，Sampling可以是很tricky的。这也是为什么需要metadata，它可以存储必要信息来进行高效采样候选。在很早时，我们支持由两个已存在的tensorflow ops：tf.nn.sampled_softmax_loss和tf.contrib.text.skip_gram_sample（基于frequency）所使用的sampling strategies。如果我们希望达到更好的word embedding，则相应地需要计算更高阶的信息比如PMI（互信息概率）或共现次数。因此，这些bookkeeping信息需要在高效采样进行embedding lookup期间被处理。

这里，我们决定重新设计在DES中的candidate sampling，因上以下原因：

• i) 复用tensorflow code很简单，因为每个embedding在一个interger array中都具有一个唯一的索引
• ii) 原始实现不会考虑多个label output，因为实际上它会区别true labels和sampled labels（为了满足限制：所有variables必须在training前被定义，它需要从input中的true labels数目，比如：每个input必须具有明确相同的true labels）。。。

在我们的新设计中，为了满足graph的需求：即graph是固定的，每个input中的true_labels数目会不同，我们会简单地将positive 和negative examples进行合并，并由用户来决定num_samples的值。我们的接着变为：

class CandidateSampler {
  public:
    struct SampledResult {
      string id;
      bool is_positive;
      float prob;
    }
    
  std::vector<SampledResult> Sample (
      const std::vector<string>& positive_ids, const int num_sampled, const int range) const;
  )
}

因此，我们的新candidate sampling会解决在tensorflow实现中的限制，从而能更好地处理multi-label learning。

3.2.5 分布式计算

分布式很简单，给定每个embedding data，需要一个唯一的string id作为它的lookup key。每当DEM接收到来自tensorflow API的请求时，它会基于它们的ids将数据划分，并将work分布到不同的DEWs（lookup, update, sample，etc）中。这里，每个worker会负责处理总的keys中的一个唯一子集，并进行失败恢复，它还可以标识它负责的keys子集。有了Google’s Borg system，在server中的每个worker可以唯一标识它自己的shard number。例如，当存在n个workers时，第i个worker会负责这些embeddings，满足：\(mod(hash(key),n) = i\)。对于高效dandidate sampling来说，DEM应记帐关于每个worker的metadata，并决定每个worker的samples数目。

3.2.6 扩展Serving

使用DynamicEmbedding的tensorflow模型，需要一些特例，因为embedding数据需要对大size（>100G）进行高效检索。在本机(local)中很难满足。因此，除了由DynamicEmbedding service提出的最简单serving，我们需要支持更多健壮的设计来处理大的embedding data。为了更健壮的model serving，以下两个optimization需要考虑下。

Sandbox mode

Remote storage lookup with local cache

4.实验

略

参考

• 1.https://arxiv.org/pdf/2004.08366.pdf