<Returning is Believing: Optimizing Long-term User Engagement in Recommender Systems>
3.方法
我们提出了从顺序决策最优化的角度，在推荐中改进long-term user engagement。
dynamic embedding介绍
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.实验
略
参考
QR embedding介绍
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)
我们
参考
md embedding介绍
facebook在2019的《Mixed Dimension Embedding with Application to Memory-Efficient Recommendation Systems》，提出了一种mixed dimension embedding，并且在dlrm中做了实现，我们来看下具体的概念。
2.背景
我们主要关注explicit CF和CTR预估这两块。在explicit CF中，特定items的user ratings会被直接观测到，因此，它可以被看成是一个矩阵补全问题（matrix complition problem）。在解决矩阵补全问题时，embedding-based的方法（比如：MF、NCF）是流行的高效解法。它的核心是，使用一个convex relaxation来发现最小的nuclear norm solution。它需要求解一个半正定的program，时耗是\(O(n^4)\)，因而不能扩展到real-world应用中。作为替代，embedding/factorization方法具有明显缺点：显式需要一个embedding dimension，但实际上，这可以使用cross-validation或其它超参数tuning技术求解。在CTR预测任务中，我们会预测一个click的概率，它可以被看成是只有二元rating的context-based CF。最近该领域开发了许多模型。这些state-of-the-art的模型会具有许多相似的特征，他们无一例外都使用内存密集型(memory-intensive) embedding layers来简化模型其余部分。
在现代ML中，embeddings通常会用来表示categorical features。embeddings vectors会从数据中进行挖掘，由vectors表示的categorical概念间的特定语义关系可以通过spatial或geometric关系、以及vectors的属性来编码。因而，large embeddings是推荐系统的天然选择，它需要模型来理解users和items间的关系。
目前开发了许多技术来减小由embedding layers消耗的内存量。他们可以被划分成两类：
- (i) 压缩算法（compression algorithms）
- (ii) 压缩结构 （compressed architectures）
在标准训练之前，压缩算法通常会涉及到对模型进行一些额外处理。它们可以离线（只涉及到post-training处理）或在线执行（压缩处理会交太、或者部分变更训练处理）。简单的offline压缩算法包括：post-training quantization、pruning或low-rank SVD。模型蒸馏技术（比如：compositional coding）和neural binarization也是一种复杂的离线压缩方法，其中：autoencoders会被训练成mimic uncompressed、pre-trained embedding layers。在线压缩算法包括：quantization-aware training、gradual pruning、以及periodic regularization。我们注意到，许多这些压缩算法对于embedding layers是不唯一的，在模型压缩文献中被广泛使用。
另一方面，我们也可以压缩结构，它尝试使用更少的参数来构建关于可比静态质量(comparable statistical quality)的embedding representations。压缩结构的优点是，inference时不只可以减小内存需要，在training时也可以。该方法遵循hashing-based和tensor factorization方法，它们可以以多种方式通过re-using参数来减小在一个embedding layer上使用的参数数目。我们的方法与这些技术不同，我们基于embedding popularity来对embedding vectors的维度进行非统一（non-uniform）reduction。原则上，我们提出的技术与大多数其它压缩算法或压缩结构的方法可以混合使用。这是未来的一个方向。
最终，我们注意到，non-uniform和deterministic sampling在矩阵补全文献中有提出【37】，同时也包括：纠正popularity来提升statistical recovery performance，或者在non-uniform sampling下为completion提供理论保证。据我们所知，我们是第一个利用popularity来在大规模embedding layers中实际减小参数数的。
4.Mixed Dimension Embedding Layer
我们开始定义MD embedding layer，并讨论如何将它应用于CF和CTR预测任务上。
假设一个mixed dimension embedding layer $\bar{E}$ 包含了k+1个blocks，它可以通过2k+1个matrices来定义：
\[\bar{E} = (\bar{E}^{(0)},\bar{E}^{(1)}, \cdots, \bar{E}^{(k)}, P^{(1)}, \cdots, P^{(k)})\]…(4)
其中，
- $\bar{E}^{(i)} \in R^{n_i \times d_i}$
- $P^{(i)} \in R^{d_i \times d_0}$，其中$P^{(0)} \in R^{d_0 \times d_0}$是显式定义
假设这些blocks的维度是固定的。接着，对于一个MD embedding layer的forward propagation，会采用一个范围在(1, \(n=\sum_{i=0}^k n_i\))的index x，并产生一个如算法1所定义的embedding vector \(e_x\)。在该算法中涉及到的steps是可微的，因此我们会通过该layer执行backward propagation，并在训练期间更新matrices \(\bar{E}^{(i)}\)和 \(P^{(i)}\)。我们注意到算法1可以被泛化成支持multi-hot lookups，其中对应于一些z query indices的embedding vectors会被取到（fetched），并通过一个可微操作符（比如：add, multiply, concatenation）进行recude。
算法一
注意，我们会为除了第一个embedding matrix之外的所有embeddings返回投影embeddings（projected embeddings），所有的embedding vectors \(e_j\)会具有相同的base dimension \(d:= d_0\)。因此，基于一个mixed dimension embedding layer的模型应根据\(\bar{d}\)来确定size。我们在图2中展示了mixed dimension embedding layer的矩阵结构，它具有两个blocks，其中，由uniform或mixed dimension matrices的参数预算（parameter budget（总区域））是相同的，但内存分配不同。
图2 Uniform和Mixed Dimension Embedding layers的matrics结构
接着，我们看下如何来在mixed dimension结构中寻找block结构。这包括了：在mixed dimension embedding layer中分配给每个block的行数（row count）\(n_i\)、以及维度（dimension）\(d_i\)。我们使用流行度信息（popularity information）来界定（sizing）mixed dimension embedding layer的大小（例如：访问一个特定feature的频率f；假设这里在training和test样本间大部分一致）。我们注意到，你可以使用一个与importance相关但不同的概念：它指的是一个特定的feature通常是如何统计信息给target variable的inference的。Importance可以通过domain experts或在训练时通过data-driven的方式来决定。
4.1 Mixed Dimensions的Blocking Scheme
从一个uniform dimension embedding layer转成一个mixed dimension layer，存在一些延续性。通过使用合理的re-indexing，多个embedding matrics可以被stack成单个block matrix，或者单个embedding matrix可以通过row-wise的形式划分(partitioned)成多个block matrices。partitioned blocking scheme的关键是，将n个total embedding rows映射成blocks，其中，block-level row counts通过\((n_0, \cdots, n_k)\)和offset vector \(t \in N^{k+1}\)给出，有：
\[t_i := \sum_{j=0}^{i-1} n_j\]Blocking for CF
在CF任务中，我们只有两类features——分别对应于users和items，对应的embedding matrices分别为：
- \[W \in R^{n \times d}\]
- \[V \in R^{m \times d}\]
为了对mixed dimension embedding layer定大小，我们会使用mixed dimensions，它使用单独的embedding matrices来对它们进行划分。
- 首先，我们基于row-wise frequency来对rows进行排序（sort）和re-index：满足\(i < i' \rightarrow f_i \geq f_{i'}\)（即：索引i越小，频率越大）。
- 接着，我们将每个embedding matrix划分成k+1个blocks，以便每个block内的total popularity（AUC）是常数，如算法2所示。
对于一个给定的frequency f，k等分（k-equipartition）是唯一的，并且很容易计算。在我们的实验中可以看到，对于观察到由mixed dimensions带来的效果，以及这之外的递减效应（diminishing effect），在(8,16)范围内的任意地方设置k是足够的。
算法2
Blocking for CTR prediction
在CTR预测任务中，我们有一些categorical features，以及k+1个相对应的embedding matrics： \(E^{(i)} \in R^{n_i \times d}\)。对于ctr prediction应用，为了界定MD embedding layer的size大小，我们会跨不同的embedding matrices上使用mixed dimensions来对它们进行stacking。因此，该问题结构定义了blocks数；在每个original embedding中的vectors数目定义了在md embedding layer中相应block的行数（row counts）\(n_i\)。
4.2 popularity-based mixed dimensions
假设在md embedding layer \(\bar{E}\)的每个block中的vectors数目\(n_i\)是已经固定的。因此，它只分配了维度\(d:=(d_0, \cdots, d_k)\)来完全指定它。
我们提出了一个popularity-based scheme来在block-level上操作，它基于这样一个heuristic：每个embedding应分配一个与它的popularity的一些分数幂（fractional power）成比例的维度。
注意，这里我们会将block-level probability p与row-wise frequency f进行区别。给定f，我们将\(a_i = \sum\limits_{j=t_i}^{t_{i+1}} f_j\)定义成：在区间\([t_i, t_{i+1}]\)间的frequency curve的面积，其中总的\(\tau = \sum\limits_{j=0}^n f_j\)。
接着，我们假设：block-level probability vector \(p \in R^{k+1}\)通过它的elements \(p_i=a_i/\tau\)来定义。我们将算法3中的popularity-based scheme进行公式化，使用一个额外的超参数temperature \(a > 0\)。
算法3
提出的技术需要知道probability vector p，它管理着feature popularity。当这样的分布是未知的，我们会很容易使用来自数据样本的经验分布来替代它。
可选的，我们可以将\(\lambda \leftarrow B(\sum_i p_i^{a-1})^{-1}\)设置成：将 embedding layer sizeing的大小限制到一个total budget B上。更进一步，为了获得crisp sizing，可以使用round d，可能是2的最近幂，在应用算法3后。
注意，我们最终会具有所有的tools来对MD embedding layers进行size，同时使用算法1-3对它们进行forward和backward propagation。
参考
yahoo soft fequency capping
yahoo在2019年《Soft Frequency Capping for Improved Ad Click Prediction in Yahoo Gemini Native》提出了Soft Frequency Capping的技术。我们来看下：
1.介绍
yahoo的本地广告市场(native ad marketplace)（称为“Gemini native”）会提供给用户相应的广告：通过周围的本地内容进行重组后进行渲染（如图1所示）。对比搜索广告市场，用户意图通常是未知的。5年前启动，现在操控着每天数十亿美金的运行率，Gemini native是Yahoo的主要业务之一。每天超过20亿次曝光，数十万的active ads的库存，该市场会执行实时GSP（generalized second price）竞拍，会考虑：广告定向（ad targeting），预算考虑，频控规则（frequency）和近因原则(recency rule)，以及服务等级协议SLA（或latency）小于80ms的超过99%。
为了对在CPC价格类型特定context下的一个用户对本地广告进行排序，会为每个广告计算一个score（或expected revenue）：通过将广告主竞价 乘以 pCTR来得到。尽管Gemini native会处理其它价格类型，比如：oCPC，本文主要关注CPC价格类型。
pCTR会通过使用周期更新的模型“OFFSET”来计算：它是一个A feature enhanced collaborative-filtering (CF) based event-prediction algorithm。OFFSET是一个one-pass算法，它会为每个新的mini-batch的logged data使用SGD-based的学习方法来更新它的latent factor model。OFFSET的实现使用map-reduce架构，其中每个新的mini-batch的logged data会被预处理，通过许多mappers进行并行解析，模型实例的持续训练会通过多个reducers并行完成。
OFFSET通过他们的特征（age、gender、geo等）来表示它的用户，其中每个feature value（对于性别有：female、male或者unknown）通过一个latent factor vector（LFV）进行表示。一个用户的LFV通通应用一个non-linear function，它允许pairwise feature的依赖。由于OFFSET是一个user-less模型，一个特定用户观看一个特定广告（或frequency feature）的次数不能仅仅通过记录下来的曝光进行捕获。另外，frequency即不是一个user feature，也不是一个ad feature。因此，为了阻止用户重复观看同一个广告，基于硬频率捕获（HFC：hard frequency capping）的规则会在ad ranking过程被用于serving系统中。总之，用户在预定义的周期内观看一个ads超过预定义次数，会从ranked list中移除，不允许参与竞价。
从观测看，展示CTR会随着重复ad观看次数下降（15、17），在本工作中，我们会考虑一种新方法：通过模型将它看成是一种user-ad feature来处理频次。根据该方法，称为（SFC：soft frequency capping），对于每种曝光，frequency feature会通过user-ad pair进行计算，并用于训练一个frequency weight vector作为OFFSET SGD的一部分。在serving时，会根据incoming impression的frequency feature挑选合适的weight，并叠加到OFFSET score上。正如我们所见，frequency weight vector，产生的pCTR会随着frequency递减，表示用户对于重复观察相同的ads会厌倦。提出的方法在离线和在线评估上，对比SFC和HFC，表现出一个令人吃惊的效果提升。特别的，我们在在线实验服务真实用户时，获得一个7.3%的收益提升。SFC会增强OFFSET model，传到真实生产中，它会服务所有的Gemini native流量。我们也提供了关于frequency feature的统计，展示了不同人群在点击趋势。总之，在许多setting中会观察到“user fatigue（用户厌倦）”，因为CTR会随着频率特征的增加而递减。在许多特定的observation reveal中，男性和妇性用户体验相似的ad fatigue patterns，在观察5次广告后，在age group 50-60的群体上比group 20-30的群体的fatigue的两倍。
。。。 略
2.背景
2.1 Gemini Native
Gemini native是Yahoo主业务之一，。。。。
2.2 OFFSET Click-Prediction算法
Gemini native模型的算法是OFFSET：a feature enhanced collaborative-filtering (CF)-based ad click-prediction algorithm[2]。对于一个给定用户u的pCTR和一个ad a，会有：
\[pCTR(u, a) = \sigma(s_{u,a}) \in [0, 1]\]…(1)
其中：\(\sigma(x) = (1+e^{(-x)})^{-1}\)是sigmoid function，
4.FREQUENCY FEATURE
Yahoo users的日志活动会包括native ad impressions，从中我们可以抽取和计算frequency，例如：一个指定用户在一个预定义周期内看到一个特定ad的次数。我们可以计算每个ad featrure的frequency（例如：创意广告、campaign、或advertiser）。因此，在设置后，ad feature \(A_f\)、时间周期\(T_f\)，我们可以提供每个user u以及每个ad a相应的frequency featrue \(f_{u,a}(A_f, T_f)\)（或者简单些：\(f_{u,a}\)）。注意，通过定义，frequency feature是一个非负整数\(f_{u,a} \in N^{+}\)。
示例：假设user u看了三个广告\(a_1, a_2, a_3\)，每个ad \(a_i\)具有ad features：advertiser \(Ad_i\)、campaign \(C_{a_i}\)，creative \(Cr_i\)，另外，假设这是在星期六晚上，刚好在午夜后，user u的Gemini native在最近一周的天活动日期如表1所示（从左到右）。下面给出了不同settings下的frequency feature的一些值：
\[f_{u,a_1} (camp., last day) = 2; f_{u, a_1} (adver., last day) = 3 \\ f_{u,a_2} (camp., last week) = 5; f_{u, a_2} (adver., last day) = 5 \\ f_{u,a_3} (camp., last 4 days) = 2; f_{u, a_3} (adver., last week) = 5\]5.统计与观察
在该节，我们提出一些关于frequencey的统计和观察。最重要的，我们展示了，frequency feature是很重要的，它对CTR具有重要影响。我们聚合了30天内的统计。它包括数十亿impression和clicks。我们注意到，当SFC方法包含在OFFSET中时，这里所使用的data会被收集，用于服务所有流量。
Global view（全局视角）
在图3中，平均归一化CTR，曝光数 CDF（cumulative density function），一个特定用户关于一个特定广告的观看数v（或frequency）会绘制成关于曲线。注意：v=0意味着，在这些曝光中，用户从未观看过在这之前的广告。 对于v次views的测算，normalized CTR可以通过除以average CTR来计算；对于v=0 （之前无views），可以通过平均CTR进行测算：
\[CTR_n(v) = \frac{CTR(v)}{CTR(0)}; v=0,1, \cdots, 50\]注意，在两个曲线上，最后一点包括了对于v>=50以上所有聚合的measurements。
从图上检查，可以做出许多observations。我们抛开异常点v=25，CTR会随着观看次数（频次）进行单调递减。特别的，在只有单一past view之后，平均CTR会以20%下跌，在7次views之后几乎有50%。这是个很清晰的证据表明：用户被展示相同广告多次后的快速厌倦。然而，CTR下降率会随着views次数递减，并且曝光数会随着frequency递减（忽略最后一个点，它包含了v>=50以上的所有曝光）。特别的，47%的曝光是之前从未看过的广告（v=0），对于见过一次的广告（v=1）只有10%，见过两次的广告（v=2）只有6%。
性别视角（Gender view）
在图4中，normalized CTR和曝光CDF会为男性、女生、未知性别的frequency函数进行给制。Gemini native流量对于表2中的每种性别都是共享的。令人吃惊的是，男性用户要比妇性用户多。性别不确定是因为注册用户未标注性别。曝光CDF曲线会提供后续支持，70%的未知用户曝光是之前从未见过的广告（v=0），而男性、女性只有40%这样的曝光。
如图所示，我们注意到frequency在男性、女性用户上具有相同的效应，具有几乎相同的厌倦模式。然而，未知用户行为却很不同，对于广告重复次数具有更高的容忍度。对于这些用户的这样行为的一个合理解释是，这些用户很可能是未注册用户，到达Yahoo时，来自外部搜索或社交媒体网站，比起注册用户来说具有一个相当不同的体验。
图4
年龄组视角（Age group view）
类似。
Yahoo vertical view
6.我们的目标
采用一种soft frequency capping方法，通过将frequency fearure包含到OFFSET模型中。提出的解决方案，对比起HFD可以被优化来提供最佳的offline和online效果。
7.SOFT FREQUENCY CAPPING
总览， frequency feature可以是一个特定用户在某个预定义时间周期\(T_f\)（例如：last day、last week、last month）内对某个特定ad feature \(A_f\)（创意creative、广告campaign、广告主advertiser）的。
总之，我们将frequency feature看成是一个user-ad feature，其中我们会学习一个frequency weight vector(s)，对应于一个预定义的weights category参数\(W_c\)，它决定了我们是否具有单个全局的vector 或对于每个campaign or 每个advertiser具有一个独立的vector。
特别的，对于每个incoming train事件 {(u, a, y, t)}，feature value \(f_{a,u}(A_f, T_f)\)会进行分箱操作（binned），乘以合适的frequency weight vector的对应entry，并加上OFFSET score。frequency weight vectors会通过SGD使用user和ad features进行学习，label 为y（click或skip）。在serving time中，frequency weight vectors被用作OFFSET model的一部分来计算pCTR，并用于竞价。
公式描述
SFC方法如算法1描述。
为什么要binning？作为binning based方法的另一种选择，我们会使用一个线性回归来进行additive frequency weight：
\[s_{u,a}^' = s_{um,a} + c_a \cdot g(f_{u,a})\]其中，\(c_a\)是一个weight，它可以被全局学到，每个campaign、或每个advertiser均有，\(g(\cdot)\)是一个arbitrary function。使用一个weight vector（每个bin具有一个weight entry）的优点是，我们不必假设：一个特定依赖（例如：\(g(\cdot)\)）会提供最好的效果，我们让模型来决定最好的拟合（fit）。在我们的case中，不存在缺点，因为frequency fearture可以具有非负整数值，可以避免量化错误（ quantizatio errors）。
期望的影响（Expected impac）
直觉上，这种方法的影响可以限制分数：对于相同用户对同一个ad出现重复观看。然而，理论上的考虑表明，这样的影响实际会强加给一个广告的首次views。
当我们使用HFC时，predictive model的得分会忽略：frequency会趋向于首次曝光和重复曝光的一个平均CTR。由于重复曝光会具有更低的CTR，这些得分会比首次view具有更低的CTR。添加SFC可以使得pCTR在首次view时具有更高的CTR，之后的views会随着SFC weights进行递减。因此，会接收许多次views的广告（ads）得分不再随这些views减小，从而它们的首次views的点击预测会更准确，之后的views也更准确。
8.效果评估
本节我们会进行在线、离线评估。
注意，由于记录的数据会被用于评估模型，很明显地，通过其它方式来产生结果是不可能的。该 警告在papers中很常见。
8.1 离线评估
为了评估离线效果，我们训练了两个offset models，一个使用SFC，如第7节所描述，其它没有frequency capping，作为baseline。我们会从头运行这些模型，其中，所有模型参数会被随机初始化，它会在一个月的Gemini native 数据上进行训练，包括了数十亿次曝光。
由于技术限制，我们使和以下的binning vector，它具有26个bins:
\[B_{26} = [0:1), [1:2), \cdots, [25, \infity)\]另外，我们会测试SFC算法参数的多个组合，并找到最好的setup来使用campaign作为ad feature（\(A_f = campaign\)），并在last week（\(T_f=week\)上聚合views），并使用一个global weight vector（\(W_c=global\)），它会消除一些稀疏性。我们使用sAUC和LogLoss metrics来评估离线效果，在应用效果metrics之前，每次曝光会被用来训练系统。OFFSET hyper parameters，比如SGD step size和正则系数，会通过adaptive online tuning机制进行自动决定。
效果指标
Area-under ROC curve(AUC)：AUC指定了概率，给出两个随机事件（一正一负，点击或跳过），以及预测的pairwise ranking是正确的。
Stratified AUC (sAUC)：每个Yahoo section的AUC的平均加权（通过postive event，例如：点击数），该metric的使用是因为：不同Yahoo sections会具有不同的prior click bias，因此，单独使用section feature对于达到更高AUC values来说被证明是充分的。
LogLoss
\[\sum\limits_{(u,a,y,t) \in T} -y log pCTR(u,a) - (1-y) log(1 - pCTR(u,a))\]其中，\(T\)是一个training set，\(y \in \lbrace 0, 1\rbrace\)是postive event indicator（例如：click或skip）。我们注意到，LogLoss metric会用于优化OFFSET model参数以及它的算法超参数。
结果：LogLoss和sAUC的提升会随时间进行绘制，在图7上，对于一个使用binning vector \(B_{26}\)训练的OFFSET model，最好的SFC算法参数是：\(A_f=campaign, T_f=week, W_c=global\)，其中每个点表示了数据3小时价值。从图中看出，SFC model的优点是，所有提升都是正向。特别的，在last week训练上我们在LogLoss上有平均1.02%的提升，在sAUC上有0.83的提升。我们注意到，对于一个成熟算法来说，要达到这样的高accuracy提升，需要持续优化数年，这相当令人印象深刻。
为了达到这部分，我们将产生的全局campaign frequency weight vector如图8所示。weights 会随着frequency单调递减，其中，最后一点会包含所有大于v=25的frequency，它在曲线最下会掉落。后者会造成pCTR在该区域不准确，例如：\(f_{u,a}=25\)的under-prediction以及对\(f_{u,a} >> 25\)的over-prediction。由于我们具有较少的events，并具有更高的frequencies（如图3所示），这表明整体平均效果是under-prediction的。
统计异常解释
异常包含了在nCTR的小“jump”，它会“破坏”nCTR随frequency的单调递减性，这会发生在v=24和v=25间。如上所述，当SFC集成到offset中时，会使用binning vector \(B_{26}\)中的\([25, \infity)\)作为最后一个bin，进行收集统计信息。在之前的paragraph中，这会造成一个整体under-prediction effect在该区域的下降。由于statistics会被收集来进行auction wining events，我们会获得in-spite。
际