华为在《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如下进行公式化:

\[L = L_{CE}(Y, \hat{Y}) + L_{KD} (\hat{Y}, Y_{soft}) + R \\ L_{KD}(Y, Y_{soft}) = L_{CE} ( \sigma(\frac{Z}{\tau}), \sigma(\frac{Z_{soft}}{\tau})) \\ L_{CE}(Y, \hat{Y}) = \sum\limits_{y_i \in Y} L_{CE}(y_i, \hat{y}_i)\]

…(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作为离散方法:
\[v \leftarrow floor(log(v)^2)\]

…(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: 效率

参考

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)地对它进行实例化:

\[r_t = \omega^T m_t\]

…(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数可以定义成:

\[m_t^c = \#clicks(f_t)\]

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可以被定义成:

\[m_t^d = \#scans(f_t)\]

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

2.返回时间指标(Return time metric)

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

\[m_t^r = \frac{\beta}{v^r}\]

其中:

  • \(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进行表示:

\[Q^{\pi} (s_t, i_t) = E_{i_k \sim \pi} [\underbrace{r_t}_{\text{current rewards}} + \underbrace{\sum\limits_{k=1}^{T_t} \gamma^k r_{t+k}}_{\text{future rewards}}]\]

…(2)

其中:

  • \(\gamma\)是discount factor,用来对current rewards和future rewards的importance进行balance
  • \(Q^{*}(s_t, i_t)\)具有由optimal policy达到的最大expected reward,应遵循optimal Bellman方程[24]:
\[Q^{*}(s_t, i_t) = E_{s_{t+1}} [r_t + \gamma max_{i'} Q^{*}(s_{t+1}, i') | s_t, i_t\]

…(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进行训练,定义如下:

\[l(\theta_q) = E_{(s_t, i_t, r_t, s_{t+1}) \sim M} [(y_t - Q(s_t, i_t; \theta_q))^2] \\ y_t = r_t + \gamma max_{i_{t+1 \in I}} Q(s_{t+1, i+1; \theta_q}\]

…(4)

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

\[\nabla_{\theta_q} l(\theta_q) = E_{(s_t, i_t, r_t, s_{t+1}) \sim M} [(r+\gamma max_{i_{t+1}} Q(s_{t+1}, i_{t+1}; \theta_q) - Q(s_t, i_t; \theta_q)) \nabla_{\theta_q} Q(s_t, i_t; \theta_q)]\]

…(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进行乘积,如下:

\[i_t^{'} = F_{f_t} i_t\]

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

\[h_{r, t} = Time-LSTM(i_t^{'}, d_t)\]

…(6)

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

\[g_t = \sigma(i_t^{'}, W_{ig} + \sigma(d_t W_{gg}) + b_g) \\ c_t = p_t \odot c_{t-1} + e_t \odot g_t \odot \sigma(i_t^{'} W_{ic} + h_{t-1} W_{hc} + b_c) \\ o_t = \sigma(i_t^{'} W_{io} + h_{t-1} W_{ho} + w_{co} \odot c_t + b_o)\]

其中,\(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进行独立跟踪:

\[h_{k,t} = LSTM-k(h_{r,t})\]

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

\[s_t = concat[h_{r,t}, h_{1,t}, h_{\dot, t}, h_{k,t}, u]\]

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

4.1.3 Q-value layer

Q-value的逼近(approximation)通过具有dense state embedding的input的MLP来完成,item embedding如下:

\[Q(s_t, i_t; \theta_q) = MLP(s_t, i_t)\]

\(\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\)的计算如下:

\[\hat{f}_t = softmax(W_f x_f + b_f) \\ \hat{d}_t = W_d x_f + b_d \\ x_f = tanh(W_{xf} [s_t, i_t] + b_{xf})\]

其中:

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

\[\hat{l}_t = sigmoid(x_f^T w_l + b_l) \\ \hat{v}_r = W_v x_l + b_d \\ x_l = tanh(W_{xl} [s_t, i_t] + b_{xl})\]

4.3 Simulator Learning

5.Simulation研究

6.实验

介绍

4.实验

参考

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

3.方法

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

参考

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”,定义为:

\[log\frac{1}{P(s | m)}\]

其中:

  • 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

更进一步假设:

\[P(w \mid c) \propto exp(\langle\vec{w}, \vec{c}\rangle)\]

其中:\(\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的组合,不管我们赋予它们什么含义,他们总是会落入解决非常相似形式的问题:

\[min_{\theta=\lbrace \theta_1, \cdots, \theta_n\rbrace} \sum\limits_{x \in D} L(x, \theta) \equiv f_1(f_2(\cdots f_n(x, \theta_n), \cdots; \theta_2), \cdots, \theta_1), n \in N\]

…(1)

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

\[\frac{\partial L(x, \theta)}{\partial \theta_i} = \frac{\partial L(x, \theta)}{\partial f_i} \frac{\partial f_i}{\partial \theta_i} = \frac{\partial L(x, \theta)}{\partial f_1} \frac{f_1}{f_2} \cdots \frac{\partial f_{i-1}}{\partial f_i} \frac{\partial f_i}{\partial \theta_i}\]

…(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)\),这可以表示成:

\[D_{KL} (P_{c_1} \| P_{c_2}) \equiv \int_w P(w \mid c_1) \frac{log P(w | c_1)}{log P(w | c_2)} > \delta\]

…(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}>)\))代入到上面的等式,我们可以获得:

\[D_{KL}(P_{c_1} \| P_{c_2} \propto \int_w P(w | c_1) \langle\vec{w}, \vec{c_1} - \vec{c_2}\rangle\]

…(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)可以被简单表示成:

\[D_{KL}(P_{\vec{w}} \| P_c) = \sum\limits_x P_{\vec{w}}(x) log \frac{P_{\vec{x}}(x)}{P(x | c)}\]

…(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)重新改写:

\[D_{KL}(P_{\vec{w}} \| P_c) = - \sum_{x} P_{\vec{w}}\langle\vec{w}, \vec{c}\rangle + log Z(\vec{c}) - H(P_{\vec{w}})\]

…(6)

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

\[\frac{\partial D_{KL}(P_{\vec{w}} \| P_c)}{\partial \vec{c}} \Leftrightarrow - \sum_x P_{\vec{w}}(x) \frac{\partial \langle\vec{w}, \vec{c}\rangle}{\partial \vec{c}} + \frac{\partial log Z(\vec{c})}{\partial \vec{c}} \approx 0 \\ \Leftrightarrow \langle\vec{w}\rangle P_c \approx \langle\vec{w}\rangle P_{\vec{w}}\]

…(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:

\[D_{KL} (P_{\overleftarrow{w}} \| P_{\vec{w}}) = \sum\limits_x P_{\overleftarrow{w}}(x) log \frac{P_{\overleftarrow{w}(x)}(x)}{P(x | w)}\]

…(8)

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

\[\frac{\partial D_{KL}(P_{\overleftarrow{w}} \| P_{\vec{w}})}{\partial \vec{w}} \Leftrightarrow \langle\vec{w}\rangle P_{\vec{w}} \approx \langle\overleftarrow{w}\rangle P_{\overleftarrow{w}}\]

…(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)可以表示成:

\[\overleftarrow{c} \approx (| \langle \overleftarrow{w} \rangle _{ P_{\overleftarrow{w}}} - \langle\overleftarrow{w} \rangle _{P_{\vec{w}}}|^2 + |\langle\vec{w} \rangle _{P_{\vec{w}}} - \langle\vec{w}\rangle_{P_c}|^2) / 2 \geq (\langle \overleftarrow{w} \rangle_{P_{\overleftarrow{w}}} - \langle \overleftarrow{w} \rangle_{P_{\vec{w}}}) \circ (\langle \vec{w} \rangle_{p_{\vec{w}}} - \langle \vec{w} \rangle_{P_c})\]

…(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,我们可以得到:

\[\frac{\partial D_{KL}(P_{\vec{w}} \| P_c)}{\partial \vec{c}} \approx \langle \vec{w} \rangle_{P_{\vec{w}}} - \langle \vec{w} \rangle_{P_c} \approx \frac{\partial{\vec{w}}}{\partial \vec{c}}\]

…(11)

\[\frac{\partial D_{KL}(P_{\overleftarrow{w}} \| P_{\vec{w}})}{\partial \vec{w}} \approx \langle \overleftarrow{w} \rangle_{P_{\overleftarrow{w}}} - \langle \overleftarrow{w} \rangle_{P_{\vec{w}}} \\ \approx \langle L(\vec{w}) \rangle_{P_{\overleftarrow{w}}} - \langle L(\vec{w}) \rangle_{P_{\vec{w}}} \\ \approx \frac{\partial L(\vec{w})}{\partial {\vec{w}}}\]

…(12)

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

\[\overleftarrow{c} \approx \frac{\partial L(\vec{w})}{\partial \vec{w}} \cdot \frac{\partial \vec{w}}{\partial \vec{c}} = \frac{L}{\vec{c}}\]

…(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概率可以被表示为:

\[P(w=a | c) = \frac{exp(\vec{c}^T \vec{w}_a + b_a)}{\sum_{k \in W} exp(\vec{c}^T \vec{w}_k + b_k)} = \frac{exp(\langle \left[ \begin{array}{c} \vec{c} \\ 1 \end{array}\right], \left[ \begin{array}{c} \vec{w}_a \\ b_a \end{array}\right] \rangle)}{\sum_{k \in W} exp(\langle \left[ \begin{array}{c} \vec{c} \\ 1 \end{array}\right], \left[ \begin{array}{c} \vec{w}_k \\ b_k \end{array}\right]\rangle)}\]

…(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.实验

参考

facebook在2019的《Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems》,提出了一种compositional embedding,并且在dlrm中做了实现,我们来看下具体的概念。

1.介绍

DLRMs的设计是为了处理大量categorical (or sparse) features的情况。对于个性化或CTR预估任务,categorical features的示例可以包括:users、posts、pages、以及成百上千的这些features。在每个categorical feature中,categories的集合可能会有许多多样性的含义。例如,社交媒体主页(socal media pages)可能包含的主题范围是:从sports到movies。

为了利用这些categorical信息,DLRMs利用embeddings将每个category映射到在一个embedded空间中的一个唯一的dense representation;见[2,4,5等]。更精确的,给定一个关于categories的集合S以及它的基数 \(\mid S \mid\),每个categorical实例会被映射到一个在一个embedding table \(W \in R^{\mid S \mid \times D}\)的indexed row vector上,如图1所示。我们不用预先决定embedding的weights,对于生成准确的模型,在neural network的其余部分对embeddings进行jointly training更有效。

每个categorical feature,可有具有数千万可能不同的categories(比如:\(\mid S \mid \approx 10^7\)),采用的embedding vector的维度为\(D \approx 100\)。在DLRM的training和inference期,由于存在大量的categories,每个table可能需要多个GBs进行存储,因此embedding vectors的数目构成了主要的内存瓶颈。

一种减小内存需求的天然方法是,通过定义一个hash函数(通常是余项函数:remainder function)来减小embedding tables的size,它可以将每个category映射到一个embedding index上,其中embedding size会比categories的数目要更小。然而,该方法会将许多不同的categories映射到相同的embedding vector上,从而导致在信息的丢失以及在模型质量上变差。理想情况下,我们应减小embedding tables的size,并且仍为每个category生成唯一的representation,从而尊重数据的天然多样性。

在本paper中,我们提出了一种方法,它通过对caegory set使用complementary partitions来生成compositional embeddings,来为每个categorical feature生成唯一的embedding。这些compositional embeddings可以与多个更小的embeddings交互来生成一个final embedding。这些complementary partitions可以从categorical data的天然特性中获取,或者人工强制来减小模型复杂度。我们提出了具体的方法来人工定义这些complementary partitions,并演示了在一个modified DCN以及Facebook DLRM networks在Kaggle Criteo Ad Display Chaalenge dataset上是有用的。这些方法很容易实现,可以在training和inference上同时压缩模型,无需其它额外的pre-或post-training处理,比hashing trick能更好地保留模型质量。

1.1 主要贡献

主要有:

  • quotient-remainder:。。。
  • complementary partitions:
  • 更好的实验效果:

2.商&余数 trick(QUOTIENT-REMAINDER TRICK)

回顾DLRM setup中,每个category会被映射到embedding table中的一个唯一的embedding vector上。数学上,考虑单个categorical feature,假设:\(\epsilon: S \rightarrow \lbrace 0, \cdots, \mid S \mid -1 \rbrace\)表示S的一个枚举(enumeration)(例如:一个categories集合S包括 S={dog, cat, mouse}, 接着S的一个潜在枚举enumeration:\(\ epsilon (dog)=0, \epsilon (cat)=1, \ epsilon (mouse)=2\)。假设\(W \in R^{\mid S \mid \times D}\)是相应的embedding matrix或table,其中D是embeddings的维度。我们可以使用\(\)e_i \in R^{\mid S \mid}\(\)将每个category(或者说:category \(x\in S\)具有index \(i=e(x)\))编码成一个one-hot vector,接着将它映射到一个dense embedding vector \(x_{emb} \in R^D\)上:

\[x_{emb} = W^T e_i\]

…(1)

另外,该embedding可以被解释成embedding table上的一个单行lookup,例如:\(x_{emb} = W_i,:\)。注意,这会产生一个\(O(\mid S \mid D)\)的内存复杂度来存储embeddings,当\(\mid S \mid\)很大时这会变得非常受限。

减小embedding table的naive方法是,使用一个简单的hash function[17],比如:remainder function,这称为hashing trick。特别的,给定一个size为\(m \in N\)(其中, \(m \ll \mid S \mid\))的embedding table,也就是说,\(\sim{W} \in R^{m \times D}\),你可以定义一个hash matrix \(R \in R^{m \times \mid S \mid}\):

\[\]

…(2)

接着,该embedding通过下面执行:

\[x_{emb} = \sim{W}^T Re_i\]

…(3)

该过程可以通过算法1进行归纳:

算法1

尽管该方法可以极大减小embedding matrix的size,由于\(m \ll \mid S \mid\), 从\(O(\mid S \mid D)\)减小到\(O(mD)\),它可以天然地将多个categories映射到相同的embedding vector,从而产生信息丢失以及模型质量上的下降。一个重要的observation是,该方法不会为每个unique category生成一个unique embedding,从而不会遵循categorical data的天然多样性。

为了克服这一点,我们提出了quotient-remainder trick。出于简洁性,m除以\(\mid S \mid\)。假以”"表示整除或商(quotient)操作。使用两个complementary functions(integer quotient function和remainder function),我们可以生成两个独立的embedding tables,对于每个category,两个embeddings组合起来可以生成unique embedding。如算法2所示。

算法2

更严格的,我们定义了两个embedding矩阵:\(W_1 \in R^{m \times D}\)和\(W_2 \in R^{(\mid S \mid/m) \times D}\)。接着定义一个额外的hash矩阵\(Q \in R^{(\mid S \mid /m) \times \mid S \mid}\):

\[\]

…(4)

接着,我们可以通过以下方式获取我们的embedding:

\[x_{emb} = W_1^T R e_i \odot W_2^T Q e_i\]

…(5)

其中,\(\odot\)表示element-wise乘法。该trick会产生一个\(O(\frac{\mid S \mid}{m} D + mD)\)的内存复杂度,它对比起hashing trick在内存上会有微小的增加,但可以生成unique representation。我们在第5节展示了该方法的好处。

3.COMPLEMENTARY PARTITIONS

quotient-remainder trick只是decomposing embeddings的一个更通用框架下的一个示例。注意,在 quotient-remainder trick中,每个操作(quotient或remainder)会将categories集合划分成多个”buckets”,以便在相同”bucket”中的每个index可以被映射到相同的vector上。然而,通过将来自quotient和remainder的两个embeddings组合到一起,可以为每个index生成一个distinct vector。

相似的,我们希望确保在category set中的每个element可以生成它自己的unique representation,即使跨多个partitions。使用基础的set theory,我们可以将该概念公式化成一个称为“complementary partitions”的概念。假设\([x]_p\)表示通过partition P索引的\(x \in S\)的等价类。

定义1: 。。。

作为一个具体示例,考虑集合 \(S=\lbrace 0,1,2,3,4 \rbrace\)。接着,以下三个set partitions是complementary:

1
{ {0}, {1,3,4}, {2} }, { {0,1,3}, {2,4} }, { {0,3}, {1,2,4} }

特别的,根据这些partitions中至少一个,你可以确认每个element与其它element是不同的。

注意,一个给定partition的每个等价类指定了一个“bucket”,它可以映射到一个embedding vector上。因而,每个partition对应到单个embedding table上。在complementary partitions下,在对来自每个partitions的每个embedding会通过一些操作进行组合之后,每个index会被映射到不同的embedding vector上,如第4节所示。

## 3.1 Complementary Partitions示例

使用complementary partitions的定义,我们可以抽象quotient-remainder trick,并考虑其它更通用的complementary partitions。这些示例会在附录中提供。出于简化概念,对于一个给定的\(n \in N\),我们定义了集合:\(\Epsiion(n) = \lbrace 0, 1, \cdots, n-1 \rbrace\)

(1) Naive Complementary Partition:

\[P = \lbrace \lbrace x \rbrace: x \in S \rbrace\]

如果P满足上式,那么P就是一个Complementary Partition。这对应于一个full embedding table,它的维度是:\(\mid S \mid \times D\)。

(2) Quotient-Remainder Complementary Partitions:

给定\(m \in N\),有:

\[P_1 = \lbrace \lbrace x \in S: \epsilon(x)\m=l \rbrace: l \in \epsilon(\lceil |S| /m \rceil) \rbrace && P_2 = \lbrace \lbrace x \in S: \epsilon(x) mod m = l \rbrace: l \in \epsilon(m) \rbrace\]

这些partitions是complementary的。这对应于第2节中的quotient-remainder trick。

(3) Generalized Quotient-Remainder Complementary Partitions:

对于\(i=1, \cdots, k\),给定\(m_i \in N\),以便\(\mid S \mid \leq \prod\limits_{i=1}^{k} m_i\),我们可以递归定义complementary partitions:

\[P_1 = \lbrace \lbrace x \in S: \epsilon(x) mod m = l \rbrace: l \in \epsilon(m_1) \rbrace && P_j = \lbrace \lbrace x \in S: \epsilon(x)\M_j mod m_j = l \rbrace: l \in \epsilon(m_j) \rbrace\]

其中,对于\(j=2, \cdots, k\), 有\(M_j = \prod\limits_{i=1}^{j-1} m_i\)。这会泛化qutient-remainder trick。

(4) Chinese Remainder Partitions:

考虑一个pairwise 互质因子分解(coprime factorization),它大于或等于\(\mid S \mid\),也就是说,对于所有的\(i=1,\cdots,k\) 以及\(m_i \in N\), 有 \(\mid S \mid \leq \prod_{i=1}^{k} m_i\);以及对于所有的\(i \neq j\),有\(gcd(m_i, m_j)=1\)。接着,对于\(j=1,\cdots,k\),我们可以定义该complementary partitions:

\[P_j = \lbrace \lbrace x\inS: \epsilon(x) mod m_j = l \rbrace: l \in \Epsilon(m_j) \rbrace\]

具体取决于application,我们可以定义更专门的 complementary partitions。回到我们的car示例,你可以基于year、make、type等来定义不同的partitions。假设这些属性的unique specificiation会生成一个unique car,这些partitions确实是complementary的。在以下章节,我们会演示如何来利用这些结构减小内存复杂度。

4.使用complementary partitions的compositional embeddings

在第2节对我们的方法进行泛化,我们可以为每个partitions创建一个embedding table,以便每个等价类可以被映射到一个embedding vector上。这些embeddings可以使用一些operation进行组合来生成一个compositional embedding或直接使用一些独立的sparse features(我们称它为feature generation方法)。feature generation方法尽管有效,但可以极大增加参数数目,需要增加额外features,并没有利用其内在结构,即:complementary partitions可以从相同的initial categorical feature中形成。

更严格的,考虑一个关于category set S的complementary partitions的集合:\(P_1,P_2,\cdots,P_k\)。对于每个partition \(P_j\),我们可以创建一个embedding table \(W_j \in R^{\mid P_j \mid \times D_j}\),其中,由\(i_j\)索引的每个等价类\([x]_{P_j}\)被映射到一个embedding vector中,\(D_j \in N\)是embedding table j的embedding维度。假设:\(p_j: S \rightarrow \lbrace 0, \cdots, \mid P_j\mid -1\)函数可以将每个element \(x \in S\)映射到相应的等价类的embedding index上,比如:\(x \rightarrow i_j\)。

为了泛化我们(operation-based)的compositional embedding,对于给定的category,我们会将来自每个embedding table与对应的所有embeddings交叉,来获得final embedding vector:

\[\]

…(6)

其中,\(w: R^{D_1} \times \cdots \times R^{D_k} \rightarrow R^D\)是一个operation function。operation function的示例包括:

  • 1) Concatenation:
  • 2) Addition:
  • 3) Element-wise Multiplication:

你可以看到,这些方法会为在简单假设下的每个category生成一个unique embedding。我们可以看到,在以下理论中。出于简洁性,下文的讨论仅限concatenation操作。

定理1

该方法会将存取整个embedding table \(O(\mid S \mid D)\)的内存复杂度减小到\(O(\mid P_1 \mid D_1 + \mid P_2 \mid D_2 + \cdots + \mid P_k \mid D_k)\)。假设\(D_1 = D_2 = \cdots = D_k = D\)并且\(\mid P_j \mid\)可以被专门选中,该方法会生成一个最优的内存复杂度\(O(k \mid S \mid ^{1/k} D)\),这对于存储和使用full embedding table是一个明显提升。该方法在图2中可视化。

4.1 Path-Based Compositional Embeddings

生成embeddings的另一个可选方法是,为每个partition定义一个不同的transformations集合(除了第一个embedding table外)。特别的,我们可以使用单个partition来定义一个initial embedding table,接着,将initial embedding通过一个函数组合来传递来获取final embedding vector。

更正式的,给定一个category set S的complementary partitions集合:\(P_1, P_2, \cdots, P_k\),我们可以定义一个embedding table \(W \in R^{\mid P_1 \mid} \times D_1\)来进行第一次划分(partition),接着为每一个其它partition定义函数集合\(M_j = \lbrace M_{j,i}: R^{D_{j-1}} \rightarrow R^{D_j}: i \in \lbrace 1, \cdots, \mid P_j \mid \rbrace \rbrace\)。在这之前,假设:\(p_j: S \rightarrow \lbrace 1, \cdots, \mid P_j \mid \rbrace\)是这样的函数:它将每个category映射到embedding index对应的等价类上。

为了为category \(x \in S\)获得embedding,我们可以执行以下transformation:

\[x_{emb} = (M_{k,p_k(x)} \degree \cdots \degree M_{2,p_2(x)}) (W e_{p_1(x)}\]

…(7)

我们

参考