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

摘要

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

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

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

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

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

介绍

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

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

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

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

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

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

主要贡献如下：

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

2.相关工作

略

3.问题公式化

3.1 Feed Streaming推荐

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

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

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

3.2 Feed Streams的MDP公式

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

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

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

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

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

3.3 User Engagement和Reward function

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

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

…(1)

其中：

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

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

3.3.1 Instant metrics

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

3.3.2 Delayed metrics

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

1.深度指标（Depth metrics）

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

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

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

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

其中：

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

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

4. 推荐系统的Policy learning

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

…(2)

其中：

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

…(3)

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

…(4)

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

…(5)

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

4.1 Q-Network

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

4.1.1 Raw Behavior Embedding Layer

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

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

…(6)

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

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

4.1.2 Hierarchical Behavior Layer

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

图1

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

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

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

4.1.3 Q-value layer

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

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

4.2 off-policy learning任务

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

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

图2

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

其中：

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

4.3 Simulator Learning

略

5.Simulation研究

略

6.实验

介绍

4.实验

略

参考

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

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

3.方法

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

参考

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

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

摘要

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

1.1 Motivation

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

1.2 核心

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

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

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

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

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

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

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

系统总览：

图1

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

2.数学公式

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

其中：

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

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

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

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

更进一步假设：

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

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

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

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

…(1)

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

…(2)

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

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

2.2 增长需要

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

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

…(3)

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

…(4)

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

2.3 新的neuron model: DynamicCell

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

2.3.1 free energy principle的动机

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

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

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

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

2.3.2 Formulation

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

Internal state homeostasis稳态

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

…(5)

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

…(6)

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

…(7)

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

Upsteam state homeostasis稳态

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

…(8)

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

…(9)

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

Reaction

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

…(10)

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

与gradient descent update相联系

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

…(11)

…(12)

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

…(13)

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

3.系统设计

3.1 tensorflow API设计

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

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

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

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

3.1.1 Sparse Input

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

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

其中：

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

3.1.2 Sparse Output

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

…(14)

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

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

Candidate negatie sampling

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

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

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

TopK retrieval

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

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

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

3.1.3 Saving/restoring模型

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

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

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

3.1.4 使用DynamicEmbedding的Word2Vec模型

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

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

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

3.2 DynamicEmbedding serving设计

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

3.2.1 Embedding存储

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

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

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

3.2.2 embedding update

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

long-short term memory

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

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

3.2.3 top-k sampling

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

3.2.4 Candidate sampling

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

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

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

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

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

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

3.2.5 分布式计算

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

3.2.6 扩展Serving

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

Sandbox mode

Remote storage lookup with local cache

4.实验

略

参考

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

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\)上：

…(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通过下面执行：

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

…(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满足上式，那么P就是一个Complementary Partition。这对应于一个full embedding table，它的维度是：\(\mid S \mid \times D\)。

(2) Quotient-Remainder Complementary Partitions:

给定\(m \in N\)，有：

这些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：

其中，对于\(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：

具体取决于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：

…(7)

我们

参考

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

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来定义：

…(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}\)给出，有：

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。

参考

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