ali在《ATNN: Adversarial Two-Tower Neural Network for New Item’s Popularity Prediction in E-commerce》中提出了ATNN。

3.ADVERSARIAL TWO-TOWER NEURAL NETWORK

本节中，首先描述了new arrivals预估问题。CTR被认为是该问题的最重要的indicator。接着我们描述了ATNN，它会根据它们的流行度（popularity）对所有new arrivals进行排序。

A.问题描述

我们的目标是解决在电商平台上预估关于new arrivals的流行度的冷启问题。由于对于new arivals的流行度（popularity）没有公共评估，我们会使用CTR预估作为一个关键任务来解决该cold-start问题。在平台上有新items发出时，我们会利用模型根据CTR预估来做出个性化推荐。精准的CTR预估可以让购买者（buyers）看到它们更偏好的items，这会满足buyers对于new arrivals的消费期望，增强用户体验。同时，卖家（sellers）也愿意在该平台上提供更新的items，因为增加new arrivals的交易数可以获得利润。

另外，我们的主要目标是，在new arrivals间发现潜在的流行items。然而，对于一个模型来说，评估item流行性是很难的。我们会采用：如果一个item对于大多数购买者（buyers）具有较高CTR，那么它会具有一个高可能性是吸引人的。因此，我们会基于大规模工业界数据，将模型进行扩展，以获得new arrivals在所有用户上的流行度。在new items放到平台上前，该模型能获得关于new items的流行度。

特别的，我们会使用item被释放到平台上的前30天信息作为训练数据。我们接着收集这些items的静态数据，包括：Page Views（PV）、UV（Unique Visotors）、用户行为序列（比如：点击、加购物车、加收藏、购买）。我们也会获得item profiles和user profiles作为训练数据的features。Item profiles包含了买家信息、产品名、产品图片、类别。User profiles包含了私人数据，经如：用户名、性别、位置信息、购买偏好、购买力等级等。New arrivals只有item profiles没有item统计信息。我们的目标是对所有new arrivals对在所有用户上的流行度进行排序。

B.普通pairwise user-item CTR预估的双塔模型

DNNs被广泛用来进行普通CTR预估，自动学习feature表示和高阶特征交叉。由DNNs获得的Item vectors可以被用于多个任务，包括new arrivals的流行度估计。

图2展示了一个标准的DNN model，用于pairwise user-item CTR预估。这是一个经典的方法，会首先将一个item embedding和一个user embedding进行concatenate在一起。通过该模型我们不能获得item vector和user vector。

图2

为了显式捕获对new item流行度预估的item vectors，我们会构建一个two-tower网络，如图3所示。左塔会从item profiles和item统计信息中抽取信息，来达到item vectors；右塔会利用user profiles来获得user vectors。我们可以显式捕获item vector和user vector，可以用来训练其它模型，并求解与pairwise CTR预估相关的其它任务。我们使用ATNN获得的item vectors来训练一个generator，它会在后描述。

我们会训练模型，通过将每个item,user pair给到network中，包括它们的交叉。一条input样本如下：

\[[itemID, x_{i1}, x_{i2}, x_{i3}, \cdots, userID, x_{u1}, x_{u2}, x_{u3}, \cdots, y]\]

其中:

• itemID和user ID是唯一标识符
• \(x_i\)和\(x_u\)表示一个item和一个user的features
• \(y\)是label

图3

C.对new arrivals进行ATNN预估

New arrivals CTR预估与普通CTR预估不同，因为缺少user-item交叉。对于平台新上的items，对比起普通item，通常在它们之上具有少量的用户行为。用户行为非常稀疏，很难训练。另外，对于还没有上的new arrivals，还不存在item统计数据。所有经典方法面临着item统计信息（包括：PV、UV、用户行为预行）的缺失。

受GANs思想的启发，我们设计了一个item generator以及一个discriminator，它可以更好学习只有item profiles的item vectors。如上所述，一个原始的two-tower DNN模型能达到item vectors和user vectors，因为在item encoder和user encoder间存在一个显式层（explicit layer）。我们会利用由双塔网络生成的item vectors来增强generator的feature extraction能力。生成的item vector和user vector的quality会影响CTR预估的精准度。

我们提出在双塔结构中引入一个对抗网络（adversarial network）来进行CTR预估，称为：Adversarial Two-tower Neural Network (ATNN)。ATNN结论如图4所示。左部分是对抗组件，它使用没有任何item统计信息的item profiles来学习更好抽取item vectors。

图4

generator设计的目的是：用来从item profiles生成item vectors，以便生成的item vectors与由item encoder生成的item vectors很相似，其中：item encoder从item profile和item统计数据中学习得到。discriminator被设计用来区分：由item generator生成的item vectors、由item encoder生成的item vectors。该generator和discriminator会做一个极大极小博弈（minimax game）来提升效果。discriminator的loss function会基于两类item vectors间的相似度，被定义为\(L_s\)。

另外，我们会使用由generator和encoder两者生成的所有item vectors来训练CTR预估模型。原始two-tower模型的loss function被定义为：\(L_i\)。generated item vectors和user vectors间的CTR预估的loss function被定义为\(L_g\)：

\[L_i = - \frac{1}{N} (y_i log\hat{y}_i + (1-y_i) log(1-\hat{y}_i)) \\ L_g = - \frac{1}{N} (y_i log\hat{y}_i^{(g)} + (1-y_i) log(1-\hat{y}_i^{(g)}))\]

其中：

• \(y_i \in \lbrace 0, 1\rbrace\)是label indicator，表示用户是否对该item有点击
• \(\hat{y} \in (0,1)\)：是基于item vector和user vector的预估label
• \(\hat{y}^{(g)} \in (0,1)\)：是基于generated item vector和user vector的预估label
• N表示训练样本数

我们会feed每对item\user pair、以及每个user-item pair的交互信息给网络来训练该模型。我们会迭代式最小化loss的方式来最优化ATNN。生成能力以及CTR的预估质量可以被增强。

在gnerators和encoders中会使用DCN。略

另外受transfer learning和multi-task learning的启发，我们让两个item embedding layers共享它们的embeddings。embedding layers会将large-scale sparse features映射到low-rank vectors中，需要大量input样本来训练一个更好模型。在embedding layers间共享features会改善generator组件的能力，以便将item profiles映射到vectors中。

我们在算法1中将ATNN的训练过程进行总结。

算法1

在每轮迭代，我们会首先通过以下的loss function来最优化ATNN：

\[L_i(H(f_i(X_i), f_u(X_u)), y)\]

其中，

• \(X_i\)和\(X_u\)分别表示一个item和一个user的features
• \(f_i(X_i)\)和\(f_u(X_u)\)表示由item encoder和user encoder获得的item vector和user vector
• \(H(\cdot)\)函数表示在一个item和一个user间的CTR预估得分

\(L_i\)会使用LR从item profiles和item统计信息，根据给定labels来进行CTR预估。在该步，我们会通过使用item tower和user tower来最优化CTR prediction。

接着，我们会通过以下的loss function来最优化ATNN:

\[L_g(H(g(X_{ip}), f_u(X_u)), y) + \lambda L_s(S(g(X_{ip}), f_i(X_i)))\]

其中：

• \(X_{ip}\)是一个item profiles的features
• \(g(X_{ip})\)是generated item vector
• \(\lambda\)是一个weighting参数，用来对两个loss进行balance
• \(S(\cdot)\)函数表示在一个generated item vector和一个普通item vector间的相似度

根据给定labels，\(L_g\)使用logistic regression从只有item profiles信息中来评估CTR预估，\(L_s\)会使用mean squared error，如下：

\[L_s(X) = mean((1 - x_i)^2)\]

其中，\(L_s\)会评估在generated item vectors和normal item vectors间的平均相似度。在该step中，我们会最小化在来自generator的generated item vector与item encoder的item vector间的差异。

D.基于ATNN进行大规模new arrivals的流行度预估

我们的目标是：通过对所有items进行流行度排序，来发现潜在的流行new arrivals。然而，对于items流行度的打分没有通用评估。基于合理假设：如果一个item对于大量买家来说具有一个较高CTR，我们认为该商品很可能更吸引人，我们可以利用ATNN来估计new arrivals的流行度。

然而，使用一个pairwise user-item CTR预估模型来完成new arrivals流行度，面临着高时间复杂度的挑战。实际上，对于new arrivals的排序，我们需要获得所有new arrivals流行度。在预估阶段，我们需要构建一个关于所有new arrivals和所有users的笛卡尔积 （ Cartesian product）。因此，预估阶段的时间复杂度是\(O(N_u * N_{NA})\)，其中：\(N_{NA}\)表示new arrivals的数目。在电商平台上，每天会来数百万已存在用户和数百万新items。在实际系统中\(O(N_u * N_{NA})\)复杂度的算法是不用运转的。

为了对new arrivals进行排序，没必要获得所有user-item pairs。作为替代，我们选择top 2000w偏好new arrivals的活跃用户，将他们看成一个用户组。我们在训练阶段学习和存储它们的mean user vector。当预估一个item的流行度时，我们只需要使用存储好的mean user vector来做出预估，它可以减少时间复杂度：每个item从\(O(N_u)\)到\(O(1)\)。图5展示了ATNN模型对于new arrivals流行度预估的效率。

图5

参考

• 1.https://personal.ntu.edu.sg/c.long/paper/21-ICDE-arrivalPrediction.pdf

microsoft在《Predictive Model Performance: Offline and Online Evaluations》中提出在线评估与离线评估中 AUC的特性：

1.介绍

对于一个常见的机器学习问题，训练和评估（or test）样本会从模型所需要的population中随机选出，预估模型会基于训练样本构建。接着，学到的模型会被应用到evaluation data上，模型的qualities会使用选中的evaluation metrics进行measure。这被称为“offline evaluation”。

另外，高度复杂的现代应用，比如：google/bing的搜索引擎，经常会在一个controlled AB testing平台上对最好的离线模型进行开展在线评估（称为online evaluation）。

现实中模型评估的一个问题是：在离线评估中模型效果的提升有时不会收到实际效果，或者有时在在线评估时获得相反结果。不同于静态offline evaluation，在controlled环境下的online Testing是高度动态的，当然，在离线建模期间都没有考虑的许多因素会对结果有重要影响。然而，这些observations会抛出一个问题：是否存在会导致这样差异在离线评估指标上的基础biases或限制。

另一个问题是：使用不同类型的数据构建的模型所进行的效果对比，特别是那些带有稀有事件（rare events）数据。稀有事件（rare events）会比其它事件以更低频率出现，从而导致在classes间的倾斜样本分布。在真实世界问题中，这是个相当常见的现象。（rare events）的样本包含了在web search结果链接上的点击、展示广告的点击、在产品广告上的购买。之前的研究已经表明，一些metrics可能会过度估计对于倾斜样本的模型效果。该observations会导致以下的问题：

• 有了该bias，我们如何解释和对比应用不同类型数据的模型效果？
• 例如，当我们构建对于文本广告和展示广告的预估模型时，我们可以使用离线指标作为可对比度量（comparative measures）来预估它的真实效果吗？
• 假设我们知道一个模型的真实效果，并且我们获得了另一个模型（the other model）相当的离线指标（offline metrics）。我们是否就可以估计该另一个模型（the other model）的真实效果呢？如果不能，我们应使用哪种metrics进行替代？

我们提出一种新的模型评估范式：仿真指标（simulated metrics）。对于在线行为的离线仿真，我们实现了 auction simulation，并使用simulated metrics来估计该点击预估模型的在线模型效果。由于simulated metrics被设计用于模拟在线行为，我们期望更少遭受效果差异问题。另外，由于simulated metrics直接估计像user CTR等在线指标，他们可以被直接对比，即使模型基于不同数据进行构建。

4.评估指标

我们集中关注点击预估问题中的metrics。一个点击预估模型会估计：给定query下，广告的位置无偏(position-unbiased) CTR。我们将它看成是一个二分类问题。

我们将NDCG排除在外，是因为它更偏向于ranking算法，在eariler ranks位置放置更多相关结果。如第2.1节所述，在搜索广告领域，排序（ranks）不光由pClick scores（例如：预估点击）决定，也会由rank scores影响。因此，使用NDCG的rank顺序来对pClick的效果进行measure是不合适的。

我们也会在review中排除Precision-Recall（PR）分析，因为在PR曲线和ROC曲线间有一个连接，从而在PR曲线和AUC间会有一个连接【9】。Davis等人展示了：当且仅当在PR空间内主导的曲线，会在ROC空间中主导。

4.1 AUC

考虑一个二元分类器，它会产生：

• p：表示一个事件发生的概率
• 1-p：表示事件不会发生的概率

p和1-p表示：每个case是两种事件其中之一。为了预估所属class，threshold是必要的。AUC（Area under the ROC (Receiver Operating Characteristic) 曲线），提供了一个在threshold所有可能范围间的判别式衡量（discriminative measure）.

在一个混淆矩阵中，4个不同部分的概率对比：

• 真阳率- true positive rate (TPR) ：也叫做sensitivity
• 真阴率- true negative rate (TNR) ：也叫做specificity
• 假阳率- false positive rate (FPR) ：也叫做 commission
• 假阴率- false negative rate (FNR) ：也叫做 omission errors

从混淆矩阵中派生出的这4个scores和其它关于accuracy的measures，比如：precision, recall, or accuracy 都依赖于threshold。

ROC曲线是一个关于sensitivity (or TPR)的一个图形描述，是一个关于二分类的FPR的函数，随threshold变化。AUC计算如下：

• 按模型预估分的降序进行sort
• 为每个预估值计算真阳率（TPR）和假阳率（FPR）
• 绘制ROC曲线
• 使用梯形近似（trapezoid approximation）来计算AUC

经验上，AUC是一个关于任意scoring model的预估能力的可靠指标。对于付费搜索，AUC，特别是只在主线广告上measure的AUC，是关于模型预估能力的最可靠指标。一个好的模型（AUC>0.8），如果AUC能提升1个点（0.01），通常具有统计显著提升（statistically significant improvement）。

预估模型使用AUC的好处包括：

• AUC提供了一个：在所有可能threshold范围上，对整个模型效果的单值判别式得分归纳。这可以避免在threshold选择中的主观因素
• 可以应用到任意scoring function的预估模型上
• AUC得分介于[0, 1]之间，得分0.5表示随机预估，1表示完美预估
• AUC可以同时被用于预估模型的offline和online监控中

4.2 RIG

RIG (Relative Information Gain：相对信息增益)是一个关于log-loss的线性转换：

\[RIG = 1 - \frac{log loss}{Entropy(\gamma)} \\ = 1 - \frac{-c \cdot log(p) - (1-c) log(1-p)}{-\gamma \cdot log(\gamma) - (1-\gamma) log(1 - \gamma)}\]

其中：

• c和p分别表示observed click和pClick。
• \(\gamma\)表示评估数据的CTR

Log-loss表示click的期望概率（expected probability）。最小化log-loss意味着pClick应收敛到expected click rate上，RIG score会增加。

4.3 MSE

MSE (Mean Squared Error)会对average squared loss进行measure：

\[MSE(P) = \frac{\sum\limits_{i=1}^n (c_i \cdot (1 - p_i)^2 + (1 - c_i) \cdot p_i^2)}{n}\]

其中：

• \(p_i\)和\(c_i\)分别样本i是pClick和observed click

NMSE（Normalized MSE）是由CTR, \(\gamma\)归一化的MSE：

\[NMSE(P) = \frac{MSE(P)}{\gamma \cdot (1-\gamma)}\]

4.4 MAE

Mean Absolute Error (MAE) 由以下公式给出：

\[MAE(P) = \frac{1}{n} \sum\limits_{i=1}^n e_i\]

其中：\(e_i = p_i - c_i\)是一个 absolute error.

MAE会权衡在prediction和observation间的distance，同时忽略掉到关键operating points的距离。MAE常用于measure在时序分析中的forecast error。

经验上，对于付费搜索（sponsored search），预估pClick模型的功率来说，该指标具有一个好的效果。它与AUC一起，是最可靠的指标之一。

4.5 Prediction Error

Prediction Error（PE）会measure由CTR归一化的平均pClick：

\[PE(P) = \frac{avg(p)}{\gamma} - 1\]

当平均pClick score准确估计CTR时，PE会变0。另一方面，当pClick scores相当不准时（有可能欠估计、过估计的混合，平均值与underlying CTR相似），PE可能接近0。这使得prediction error相当不稳定，它不能被用来可靠估计分类accuracy。

4.6 Simulated Metric

尽管在controlled AB testing环境下的在线实验会提供关于用户engagement方面的模型的真实效果对比指标，AB testing环境是通过一些固定参数值集合预设定的，因而，在testing环境上的模型效果指标只对应于operating points的给定集合。在多个operating points集合上开展实验，是不实际的，因为在线实验不仅耗时，而且如果新模型效果欠佳，对于用户体验和收益都很昂贵。

作为在线评估的替代，在整个可行operating points的范围（span）上，一个模型的效果可以使用历史在线用户engagement data进行仿真。Kumar et.为federated search 开发了一种在线效果仿真方法[20]。

Auction simulation，首先：为给定query会离线复现ad auctions，并基于新的模型预估分、以及多个operating points集合选择一个ads集合。

我们使用付费搜索（sponsored search）点击日志数据来实现auction simulation，并生成多个simulated metrics。Auction simulation，首先，为给定query离线复现ad auctions，并基于新模型预估分选择ads的一个集合。在仿真期间，会使用在日志中提供的(query, ad) pair的历史用户点击来预估用户点击：

• 如果(query, ad) pair在日志中被发现，但仿真的ad-position与在日志中的posiiton不同，expected CTR会通过position-biased histric CTR（或click曲线）被校准（calibirated）。一般的，对于相同的(query, ad) pair，主线广告（mainline ads）会比sidebar ads获得更高的大CTR，在相同ad block内，对于相同的(query, ad) pair，在更高位置的广告会获得更高的CTR。
• 如果predicted(query, ad) pair不会出现在historic logs中，会使用在ad-position上的平均CTR（也被称为：reference CTR）。

Click曲线和reference CTR来源于自在搜索广告日志中的historic user responses。

经验上，对于operating points的给定集合，auction simulation会生成高度准确的ads集合，它们会被新模型选中。 Simulated metric通常结果是在线模型效果的最强离线估计之一。

5.METRICS在真实世界中的问题

在本节中，我们分析了行为、限制以及缺点。注意，我们不打算建议：由于限制和缺陷，这些指标被一起排除。我们会宁可建议metrics被小心应用和说明，特别是那些会产生误导估计的metrics。

5.1 AUC

AUC是一个可以评估预估模型效果的相当可靠的方法，它在样本数据的特定条件下仍会有缺点。该假设是：AUC是一个需要被重新检查模型效果的充分测试指标。

首先，它忽略了预估的概率值（predicted probability values）。这使得它对于预估概率的保序变换不敏感。

• 一方面，这也是个优点，它使得在不同的measurement scales上生成的数值结果是可对比测试的。
• 另一方面，对于两个tests来说，生成具有相似AUC scores、并且非常不同的预估输出是相当可能的。它可能是一个较差拟合模型（poorly fitted model）（对所有预估过拟合、或者欠拟合），具有一个良好的判别能力；而一个良好拟合模型（well-fitted model），如果出现概率略微高于不出现概率时，会具有较差的判别。

表2中的示例展示了：一个poorly-fitted model，它使用大量负样本，具有非常低的pClick scores，从而有更低的CTR，反而具有较高AUC score。在相对更高的pClick scores范围内，它会影响FPR的降低，从而提高AUC score。

表2 AUC反常示例1：一个poorly fitted model，具有更高AUC，现在大量负样本集中在pClick score范围的低端(图中的第一张图展示了：better1-fitted模型)

第二，在整个ROC空间的spectrum上（包括很少操作的区域），它会总结测试效果。例如，对于付费搜索，在mainline上放置一个ad会显著影响CTR。不管ad在mainline上被展示、还是不被展示，predicted CTR如何拟合actual CTR并不是个大问题。换句话说，ROC的极左和极右通常很少用。Baker and Pinsky提出了partial ROC曲线作为整个ROC曲线的一个替代选择。

表3 AUC反常示例2: 在FPR的两端上，样本分布的变化会非常影响AUC score，尽管实际效果提升与在practical operating point很相近

已经观察到，更高的AUC并不必然意味着更好的rankings。如表3所示，在FPR两端上样本分布的变化会非常影响AUC score。然而，模型效果在CTR上的影响可能是相同的，特别是在threshold的practical operating points上。由于AUC不会区分ROC空间的多个区域，一个模型仅仅通过在数据的两端最优化模型效果，就能最大化AUC score。这会导致在实际在线流量上，低于期望效果增益。

第三，它会等价权衡omission和omission errors。例如，在付费搜索中，在mainline中没有放置最优ads的惩罚（penalty）（omission error）远远超过放置一个次优ads的惩罚（penalty）。当误分类代价不等时，对所有可等threshold进行汇总是有瑕疵的。

表4 AUC反常示例3: 一个poorly fitted model与well-fitted model具有相似的AUC

最后，AUC高度依赖于数据底层分布。AUC会对两个具有不同负样本率的数据集进行计算。如表4所示，一个具有较低内在CTR的poorly-fitted模型，会与一个well-fitted模型具有相同的AUC。这意味着，一个使用更高负样本率训练的模型，具有较高AUC score时，并不必然意味着模型具有更好的预估效果。图1绘制了关于付费搜索和contextual ads的pClick模型的ROC曲线。如图所示，contextual ads的AUC score要比付费搜索的AUC高3%，尽管前者会更不准：付费搜索为\(\frac{avg \ pClick}{actual \ CTR} = 1.02\)，而contextual ads为0.86。

图1

5.2 RIG

类似于AUC，RIG的一个问题是，它对评估数据的底层分布是高度敏感的。由于评估数据的RIG score的范围会随着数据分布非常不同，我们不能仅评RIG scores来决定一个预估模型有多好。

图2

图2展示了RIG（实线：solid curve）和PE（虚线：doted curve）随着一个关注的CTR区间的变化情况。我们观察到，RIG scores会随着dataset中的CTR的增加而降低，即使是相同的预估模型。图2中的prediction error意味着，prediction score与true CTR有多接近。正如所期望的，click prediction error要比低的pClick score区间要高。

这种行为符合我们关于不同点击预估数据集的早期观察，它会随intrinsic CTR的level而不同。该observations建议实践时如下：

• 不应直接使用RIG scores的实际值 来对比两个预估模型效果，如果得分来自不同分布的多个数据集合。
• RIG scores可以被用于对比多个模型在同一个数据上进行test的相对效果
• 一个独立的RIG score，信息不足够去估计预估模型的效果，因为该score不仅取决于模型效果的质量，也会非常受数据分布的偏向性影响

6.离线和在线效果差异

实践中，关于离线评估指标，一个非常显著的问题是：离线和在线间的效果差异。存在这样的情况：一个预估模型在离线指标上达到显著增益，在online testing环境部署时发现效果表现并不好。

表5总结了一个点击预估模型在Bing付费搜索数据上构建的离线和在线指标，并在一个线上真实流量上进行online AB testing环境实验。Click yield（CY）是一个在线用户点击指标，它会measure每个搜索PV上广告的点击数。Mainline CY是在每次搜索PV下mainline ads的点击数。新模型vs baseline模型，会在在线环境中在user clicks上显著下降，即使在离线评估数据上AUC和RIG会有显著收益。

表5

图3对比了：在感兴趣pClick scores范围内，每个分位下（quantile），两个点击预估模型的log-loss（baseline：model-1，test：model2）。Model-2会在较低pClick score范围的分位上大量过度估计（overestimates）pClick scores。图4绘制了相同数据的prediction error。

图3

图4

对比起低pClick score范围的过度估计，pClick scores的更高范围上于click概率做出过度估计对于在线效果影响较小，因为在高pClick score范围上的广告最可能被多个模型选中。一旦展示给用户，user clicks大多数由ad-position和ads的relevances决定，而非分配的pClick scores。

另一方面，在较低pClick范围上对pClick scores的过度估计，会对在线指标做出显著负影响；对比起base model，较低质量的ads有更高机率被选中。选中的较低质量的ads，由于过度估计pClick scores，会导致对user clicks的较低rate，从而伤害在线指标。

大多数离线指标包括：RIG和AUC，不能捕获这些行为，因为：指标会贯穿pClick scores的整个范围累积该影响。

6.1 Simulated Metrics

我们会通过第4.6节描述的 auction simulation来计算simulated metric。 simulated click metrics的实验结果会伴随着表6中归纳的offline和online指标。我们首先会训练一个新模型，并最优化参数设定，来通过基于历史日志数据的auction simulation提供最好的期望用户点击指标。具有最好表现的click metrics如表所示。

• 1.https://chbrown.github.io/kdd-2013-usb/kdd/p1294.pdf

JADIDINEJAD在《The Simpson’s Paradox in the Offline Evaluation of Recommendation Systems》中提出推荐系统中的Simpson’s Paradox：

1.介绍

推荐系统通常会以online（A/B testing或interleaving）或offline方式进行评估。然而，由于online evaluation[6,14]部署研究系统的难度，推荐系统的离线评估仍然是大范围使用的evaluation方式。实际上，很难以离线方式通过使用历史用户交互日志可靠地评估一个推荐模型的效果【7，16，43】。该问题是因为存在混淆因子（confounders），例如：那些可以影响items的曝光（exposure）以及结果（outcomes）（比如：ratings）的变量。在当一个平台尝试建模用户行为时，如果没有解释在曝光的推荐items的选择偏差（selection bias），这时会出现confounding问题，从而导致不可预料的结果。在这种情况下，很难区别用户交互是来自于用户的真实偏好、还是受部署推荐系统（deployed recommender system）的影响。

通常，推荐系统的离线评估会具有两个阶段：

• 1) 收集来自一个deployed system的用户反馈集合
• 2) 使用这样的feedback来经验性评估和比较不同的推荐模型

第一阶段可以服从不同类型的confounders，即可以是由用户关于item的选择行为来初始化，或者通过受deployed推荐系统的动作影响来初始化。例如，除了其它交互机制（比如：搜索）之外，用户更可能会与被曝光的items进行交互。在这种方式下，在一个新推荐模型的离线评估中使用历史交互，而这样的交互从deployed推荐系统中获取得到，形成一个closed loop feedback，例如：deployed recommender system存在对收集到的feedback的具有一个直接影响，它可以被用来进行对其它推荐模型的离线评估。因而，新的推荐模型会根据它趋向于模拟由deployed model收集到的交互有多像来进行评估，而非有多满足用户的真实偏好。另一方面，在一个open loop（随机化）场景中，deployed model是一个随机推荐模型，例如：为users曝光随机的items。因此，在deployed model与新的推荐model间的feedback loop会打破，deployed model不会对收集到的feedback dataset具有影响，相应的，它对于在基于收集到的feedback dataset上对任意新模型的离线评估都没有影响。然而，为users曝光随机items是天然不实际的，用户体验会降级。因此，基于closed loop feedback对推荐系统进行训练和评估会是一个严重问题。

Simpson’s paradox是统计学中的一个现象，当多个不同分组的观察数据中出现的一个显著趋势，会在这些分组组合在一起时消失或者逆转【29】。在推荐场景中，当曝光（例如：推荐items）和结果（例如：用户的隐式和显式反馈）相关联时，并且曝光和结果会受一个第三方变量强烈影响时，会发生Simpson’s paradox。在统计学上，如果观察到的feedback是Simpson’s paradox的一个产物，根据confounding variable对feedback进行分层，可以消除悖论。我们会讨论：在推荐系统的情况下，该confounding variable是交互数据被收集的deployed model（或系统），a.k.a：closed loop feedback【17】。在本paper中，我们的核心目标是，对于closed loop feedback在推荐系统离线评估上提供一个in-depth研究，并提供了一个健壮的解来解决该问题。特别的，我们会讨论：从一个deployed model收集到的feedback datasets会偏向于deployed model的特性，并导致证实Simpson’s paradox的结论。我们通过研究在推荐系统离线评估上的confounding variable（例如：deployed model’s的特性），可以观察到显著趋势；当从经典离线setting中上报observations时，该趋势接着会消失或逆转。另外，我们提出了一种新的评估方法，它可以解决Simpson’s paradox，以便产生一种更合理的推荐系统离线评估方法。

为了更好地理解该问题的微妙之处，考虑一个deployed推荐模型，它会提升一个指定分组的items（例如：流行的items）——对比起只有少量交互的长尾items，存在一些少量的头部items，它们会被广泛曝光给用户并获得大量交互。当我们基于从前面deployed model收集到的feedback来评估一个新的推荐模型时，如果没有解释不同的items曝光的有多频繁，评估过程会被deployed model的特性所混淆，例如：任意模型的效果会具有这样一个趋势，展示与已经存在的deployed model相似的属性，这很可能会引起过估计（over-estimated）。在这种情况下，我们可能会选择部署一个匹配已deployed model的特性的新模型，从实际用户角度看，它会比另一个模型更低效。在本paper中，我们通过研究该问题在标准离线评估中做出结论的结果，并提出一种新的方法来解决该问题。特别的，本paper的贡献有两块：

• 我们提出了一种in-depth分析
• 为了解决该问题，提出了一个新的propensity-based stratified evaluation方法

2.相关工作

我们的工作主要受三块相关工作的启发：

• 在l2r中解决bias（2.1节）
• 算法混淆（algorithmic confounding）或closed loop feedback（2.2节）
• 在counterfactual learning和evaluation中的工作（2.3）

…

3.离线评估法

本节中，我们会将当前offline evaluation方法进行总结，称为标准holdout evaluation和counterfactual evaluation。

3.1 Holdout Evaluation

…

3.2 Counterfactual Evaluation

…

4.介绍

辛普森悖论（Simpson’s paradox）是统计学中的一种观察现象：在观察数据集的许多不同groups中都出现的一个显著趋势，当将这些groups组合在一起时会消失甚至反转。该topic在许多文献上被广泛讨论。在该现象中会出现一个明显的悖论，当聚合数据时会支持这么一个结论：它与在数据聚合前的相同的分层数据的结论相反。当两个变量间的关系被研究时，如果这些变量会被一个协变量（confounding variable）所强烈影响时，就会发生辛普森悖论。当该数据根据混杂变量（confounding variable）进行分层时，该悖论会展示出相悖的结论。在这种情况下，使用一个显著性检验（significance test）可以识别出在一个指定层做出的错误结论；然而，如第7节所示，显著性检验不可能识别出这样的统计趋势（trends）。在推荐系统的评估场景，会在所有用户上进行testing，这里讨论的悖论通常会涉及到user-item feedback生成过程。在另一方面，当因果关系（causal relations）在统计建模中被合理解决时，辛普森悖论可被解决。

在本节中，为了演示辛普森悖论，我们会从一个paper[8]中呈现一个真实示例，它会对比肾结石（kidney stone disease）的两种治疗方法（treatments）的成功率。这里的目标是：基于观察找出哪个treatment更高效。【8】会随机抽样350个病人，它们会接受每个治疗，并上报如表1所示的成功率。一个合理的结论是：treatment B要比treatment A更高效（83% vs. 78%的康复率）。另一方面，悖论是，当考虑上结石大小时，比如：treatment A对于小size（93% vs. 87%），大size（73% vs. 69%）两者都要有效，但最终的成功率会反转。[8]会讨论treatment (A vs. B) 以及结果（成功 vs. 失败）会与一个第三个混杂变量（confounding variable：这里的结石大小）有关。

表1 a) 肾结石示例。每个条目表示：恢复数/总病人数，成功率见括号 b) 推荐系统中离线评估的辛普森悖论。每个条目表示了受检模型在相应分层上的效果。*表示对比其它模型的一个显著差异（paired t-test, p<0.05）

假设 1: 医生趋向于对不严重病例（例如：小结石）选择treatment B，对于更严重病例（例如：大结石）使用treatment A进行治疗

表1验证了以上的假设，例如：大多数接受treatment A的病人都是大结石病例（group 3中350个随机病人中有263个），而大多数接受treatment B的病人都是小结石病例（Group 2的350中的270）。因此，当从接受A或B治疗的病人中被随机挑选样本时，抽样过程并不纯随机，例如：样本会倾向于：严重病例进行treatment A进行measuring，而轻症病例进行treatment B进行measuring。这就是因果分析中著名的现象：辛普森悖论。

表1b展示了在推荐系统的离线评估中的辛普森悖论示例。我们对两个推荐模型的有效性进行评估，如表1b中的A、B模型。两个模型会在相同的dataset上使用相同的evaluation metric进行评估。根据一个paired t-test，在检查的数据集上的标准离线评估表明：模型A要明显好于模型B。然而，将待检测数据集划分成两个层（Q1和Q2）表明：模型B对于待测数据集的99%（Q1）要更好，而模型A在1%（Q2）上面要更好。当Q1和Q2进行聚合时，模型B在99%待测数据集上的的统计优势会消失。在以下部分，我们会呈现：辛普森悖论是如何影响推荐系统的离线评估的，并讨论这样的悖论的原因，以及提出一个新的评估方法来解决它。

5.基于倾向的分层评估（PROPENSITY-BASED STRATIFIED EVALUATION)

当为一个推荐系统的离线评估创建一个数据集时，用户反馈不仅会用户与来自deployed recommendation system推出的items交互上被收集到到，也会通过其它形式（比如：当浏览item的目录时发生的交互、或者点了sponsored items的链接）进行收集得到。对于区分用户的不同反馈源来说并不简单，因为没有公共数据集提供这样的数据来确定用户反馈的source。因此，在本paper中，我们的研究主要关注于用户反馈的主源，称为deployed system。为了演示在推荐系统中的辛普森悖论，我们需要一个因果假设，它与第4节中的假设1相似。

图1 推荐系统中的Closed loop feedback

图1a展示了一个典型推荐系统的信息流，其中用户反馈会通过deployed system进行收集。

• 部署好的推荐系统组件（通过RecSys表示）会为target user（例如：通过推荐items的一个ranked list）过滤出items进行曝光（exposure: e）。
• 另一方面，用户在items上记录的偏好（例如：ratings或clicks）（用r表示）会被作为交互数据来训练 或 评估推荐模型的下一次生成（next-generation）。

因而，由于用户点击是从RecSys曝光的items获得的，模型本身会影响数据的生成，而它们则会被用于训练和评估。图1a中的系统是一个动态系统，其中，系统进行简单联想推理（associative reasoning ）的原因是很难的，因为每个组件会互相影响。图1b表明了在这样一个闭合循环反馈场景下的因果关系图。实线表示了在原因和效果间一个explicit/observed关系，而虚线表示了一个implicit/unobserved关系。如上所示，在推荐系统的case中，主要的混合变量是，来自交互数据的deployed model会被收集。我们的目标是，基于来自deployed model收集到的封闭循环反馈（r））评估一个推荐模型（Y）的效果会影响主干扰因子（main confounder），例如：deployed model的特性。在该情况下，很难区分: 来源于用户真实偏好影响的的用户交互，或者受deployed recommendation model影响的用户交互。因此，在该场景下，用户反馈通常会通过deployed system进行收集，我们会假定，基于闭循环反馈数据集的推荐模型离线评估，会受以下deployed recommendation model的强烈影响：

假设2: 闭环循环反馈（closed loop feedback）会从一个deployed recommendation model来收集到，并倾向于deployed model的特性（characteristics）（例如：曝光items），deployed model的该特性会在推荐模型的离线评估中作为一个混淆因子（confounding factor）。

deployed recommendation model的核心问题是：尝试建模潜在的用户偏好，在没有解释算法混淆的情况下，这使得它很难对用户行为（或者使用用户数据）做出断言。另一方面，如果图1a中的RecSys组件是一个random模型，那么在User和RecSys组件间的连接会被移除，RecSys组件会在收集到的feedback dataset上没有影响，这种情况 称为“开环循环反馈（open loop feedback）”，对比起在collection中的任意其它item，没有items会接收到或多或少的期望曝光。

如图1b所示，如果deployed model的特性（e）可以被标识和评估，离线评估（Y）会与confounder独立。因此，为了验证在推荐系统中（假设2）closed loop feedback的影响，我们必须量化deployed model的特性。结尾处，根据5,47，我们会如下定义propensity score：

定义5.1 propensity score \(p_{u,i}\)是deployed model（如图1a中的RecSys描述）对于expose item \(i \in I\)的曝光给user \(u \in U\)的趋势

propensity \(p_{u,i}\)是在一个闭环反馈场景下，deployed model将item i曝光给user u的概率。该值会对来自一个无偏开环曝光（unbiased open loop exposure）场景的系统偏差（deviation）进行量化，其中：随机items会被曝光给该用户，deployed model对收集到的feedback没有影响。propensity score \(p_{u,i}\)允许我们基于观察到的闭环feedback来设计并分析推荐模型的离线评估，因此它会模拟一些开环场景的特殊特性。

分层（Stratification）是用来标识和估计因果效应的知名方法，会在每个层调查因果效应之前，首先标识出潜在层（underlying strata）。总意图是：在confounding variable上进行分层，并研究在每个层上的潜在结果。因此，衡量不考虑confounding variable的潜在结果是可能的。在这种情况下，在confounding variable上的边缘化（marginalisation）可以作为一个组合估计（combined estimate）被使用。如前所述，在推荐系统中的假设condounding variable是deployed model的特征（假设2）。定义5.1会将该变量量化成倾向（propensities）。在这种情况下，在propensity scores上的分层会允许我们分析deployed model特性在推荐模型的离线评估上的该效应。

出于简洁性，假设我们具有一个单一的categorical confounding variable X。如果我们基于X的可能值将观察到的结果进行分层，那么潜在结果（Y）的期望值如下所示：

\[E(Y) = \sum\limits_x E(Y | X=x) P(X=x)\]

…(4)

其中：

• \(E(Y \mid X = x)\)是在给定分层x下对于observed结果的条件期望，
• \(P(X=x)\)是x的边缘分布。

例如，在肾结石的示例中，condounding variable是结石大小，基于它进行分层（\(X = \lbrace small, large \rbrace\)），潜在结果是treatment效果。我们可以基于等式(4)计算每个treatment的期望值。例如：treatment A的期望值可以按如下方式计算：

\[E(A) = E(A | X = small) P(X=small) + E(A | X = large) P(X = large)\]

…(5)

例如：基于表1a和等式(5)中的数字，treatment A的期望值（resp. B）分别计算为：0.832和0.782，

计算：

• P(X=small)=(87+270)/(87+270+263+80)=0.51,
• P(X=large)=(263+80)/(87+270+263+80)=0.49
• E(A) = 0.93 x 0.51 + 0.49 x 0.73 = 0.832
• E(B) = 0.87 x 0.51 + 0.69 x 0.49 = 0.782

E(A) > E(B)，它可以更好地估计treatments的实验效果。

相似的，对于表1b的推荐示例，模型A和模型B的期望值分别被计算为：0.343和0.351（计算所需数据参考第7节），计算如下：

• E(A) = 0.339 * 0.99 + 0.695 * 0.01 = 0.343
• E(B) = 0.350 * 0.99 + 0.418 * 0.01 = 0.351

从而得到E(B) > E(A)。

如上所示，在推荐系统中，主要的假设混淆变量是deployed model（假设2）。该变量可以量化成propensity scores（定义5.1）。Propensity是一个连续变量。在本paper中，我们会通过将propensity scores进行排序和分片成将它转换成一个categorical variable，然后转成一个预定义好数目的分层，例如：表1b中的Q1和Q2分层。在表1a和表1b的两个case，都基于假设混淆变量并使用等式（4）对等验证分层进行边缘化，会解决Simpson’s paradox。例如：在表1b中，模型B会被认为更好的model，因为它对于99%的user-item feedback在效果上要好。这个重要的趋势会被提出的分层评估进行捕获，而在标准离线评估中，当将Q1和Q2分层聚合在一起时，结论会完全逆转。在下节中，我们会研究simpson paradox的效应，以及提出的propensity-based分层评估的好处。特别的，我们研究了以下问题：

研究问题1：在closed loop feedback场景下，推荐系统的离线评估有多大程度是受deployed model特性所影响的

然而，我们的目标是评估deployed model特性在推荐模型离线评估中的confounding effect，如图1b所示。就这一点而言，相似的原理图示例如第4节所示，我们对于将基于deployed model的特性的observed closed-loop feedback进行分层这一点比较感兴趣。这样的分层分析使得我们可以去评估：在推荐系统的标准离线评估中辛普森悖论的存在。从而，我们会研究许多不同推荐模型的相关关系的显著趋势，其中：在大多数层上观察到的一个趋势，在标准离线评估中会消失或者逆转。

研究问题2:当进行一个可比离线评估时，propensity-based stratified evaluation是否可以帮助我们更好地估计实际的模型效果

在上述研究问题中，我们的目标是：评估在推荐模型的离线评估中，提出的提出的propensity-based stratified evaluation是否有效。如等式（4）所示，我们可以利用在confounding variable分布上的边缘化（marginalisation）作为潜在结果的一个组合估计。在该研究问题上，我们会评估：该估计是如何与open loop(randomised) evaluation相关的，其中deployed model是一个随机推荐模型（例如：random items会被曝光给该user）。特别的，给定一个特别的评估方法（open loop、closed loop等），我们可以去measure基于标准的rank-based评估指标（nDCG）多种推荐模型的效果，并记录这些模型的所用metrics的相对排序。我们接着研究在examined models的相对排序间的相关性，并对比从一个open loop（随机化）设定下获得的rankings，以及使用propensity-based evaluation这两者的评估。我们会利用适当的显著性检测，如第6节所述，来决定：在对比标准的离线holdout evaluation时，由d propensity-based stratified evaluation评估的模型效果要比open loop(随机) evaluation更好。

6.实验设定

下面，我们会通过实验来解决两个前面的研究问题。图2表示了实验的总结构。每个评估方法（X, Y和Z）会会基于它们的相对表现对多个检查的推荐模型进行排序。我们会使用Kendall’s \(\tau\) rank相关系数来对受检模型在每个评估方法上（Y or Z）的相对顺序间的联系，对比ground truth进行measure，例如：open loop（randomiszed） evaluation(X)。这样的相关值会在图2中被描述成\(\tau_{XY}\)和\(\tau_{XZ}\)。另外，我们会使用Steiger’s方法来测试在两个评估方法间的差异显著性，例如：baseline evaluation method(Y)以及提出的evaluation method(Z)。我们会对比propensity-based stratified evaluation、标准offline holdout和counterfactual evaluation方法作为baseline两者。以下，我们描述了我们实验设定的详情，包含：使用的数据集和评估指标、受检推荐模型、以及如何在实验中估计propensities。

图2 基于Steiger’s方法的依赖相关度（dependent correlations）显著性测试。每种评估方法（Y and Z）的效果可以通过基于与open loop (randomised) evaluation (X)之间的Kendall’s \(\tau\) rank collrelation进行measur。在baseline evaluation方法（Y）和提出的evaluation方法（Z）间的显著性差异可以基于Steiger’s方法进行measure。

6.1 Datasets和Evaluation Metrics

我们会使用4种数据集，它们被推荐系统的离线评测所广泛使用，称为：MovieLens、Netflix、Yahoo! music rating、Coat shopping dataset。

• MovieLens包含了6k users对4k items的1M的ratings
• Netflix包含了10k users对5k items的607k ratings
• 而Yahoo! dataset包含了300K ratings，它由15.4k个users对1k items进行rate得到
• Coat shopping dataset：模拟以在线方式购买coat。包含了mh 290 users对 300 items的7k ratings。

所有datasets都通过一个unknown deployed recommendation system以closed loop方式进行收集得到。另外，Yahoo! dataset还有一个独特的feature：一个关于users(5.4k)的子集会被要求对10个随机选中的items（open loop场景）进行评分（rate）。因此，对于该子集，我们会具有closed loop和open loop（random） feedback。相似的，对于Coat dataset，每个用户会被要求提供对于24个self-selected(closed loop) items、以及16个随机选中（open loop） items进行ratings。然而，在一个真实的evaluation setup中，模型会基于收集到的closed loop feedback进行训练；因为实际评估会基于open loop(random) feedback进行很难进行收集。

我们会使用normalised Discounted Cumulative Gain(nDCG@k) metric 对不同的cut-offs（k={5,10,20,30,100}），而非使用不带rank cutoff的nDCG。以便表示对于每个user的所有items的rank metric。对于所有datasets的用户rating值是一个整数 \(r \in [0, 5]\)。我们的目标是：对每个user的最相关items进行排序。因此，我们会将所有explicit rating values进行二值化，通过（r>=4）来保留最高的推荐items。在closed loop evaluation中，我们会使用80%的closed loop dataset（MovieLens, Yahoo!和Coat）来进行训练，另外20% random split作为testing另一方面，对于open loop evaluation(Yahoo! & Coat)，我们会在所有提供的open loop(randomised) feedback上进行评估。

6.2 推荐模型

我们使用由Cornac framework提供的实验来评估以下的模型：

• BO: 一个简单的baseline model：会在忽略用户偏好的情况下，推荐一个随机的items组合给每个用户
• GA：一个baseline model，会在忽略用户偏好的情况下，推荐全局平均rating给每个user
• POP：一个baseline model，会在忽略用户偏好的情况下，它会基于流行度（popularity：例如：一个指定item被评分的次数）来对items进行rank
• MF：Matrix Factorisation，一个rating prediction模型，它会将users和items表示为latent vectors。该模型会被用来预测每个user-item pair的observed rating
• PMF：Probabilistic Matrix Factorisation。MF的扩展版本。
• SVD++：
• WMF：Weighted MF。MF的扩展版本。
• NMF：Non-negative Matrix Factorisation。
• BPR：Bayesian Personalised Ranking。
• MMMF：Maximum Margin Matrix Factorisation
• NCF: Neural Collaborative Filtering
• MLP: Multi-Layer Perceptron
• GMF: Generalised Matrix Factorisation
• NeuMF: Neural Matrix Factorisation

我们对在closed-loop和open loop场景下的模型效果的相对顺序比较关心。因此，根据以下研究，我们会采用不同的超参数来控制latent factors的size：{10, 20, …, 100}，从而导致有104个模型需要评估。每个受检模型会指定相应的latent variable size。比如：size m=40 MF，则为\(MF^{40}\)。我们的代码和数据集可以在： https://github.com/terrierteam/stratified_recsys_eval.提供。

6.3 估计Propensity Scores

propensity score \(p_{u,i}\)会被定义成：deployed model将item i曝光给user u的趋势（定义5.1）。由于它对于deployed model来曝光每个item给user是不实际的，我们必须为多个user/item pairs 估计propensity scores \(p_{u,i}\)。[47]提出了一种简单方法来估计propensity scores，它基于如下的简单假设：

假设1: propensity score是用户独立的（user independent），例如：\(p_{u,i} = p_{*,i}\)。该假设是为了解决：在公开数据集中的辅助用户信息的缺失。

user independent propensity score \(p_{*,i}\)可以使用一个2-step的生成过程（generative process）来估计：

\[p_{*,i} = p_{*,i}^{select} * p_{*,i}^{interact \mid select}\]

…(6)

其中：\(p_{*,i}^{select}\)是先验概率（prior probability），item i通过deployed model被推荐出来，\(p_{*,i}^{interact \mid select}\)是user 与推荐出来的item i进行交互下的条件概率。基于这样的温和假设，我们可以估计user independent propensity score \(p_{*,i}\)如下：

\[\hat{p}_{*,i} \propto (n_i^*)^{\frac{\gamma + 1}{2}}\]

…(7)

其中，\(n_i^*\)是item i被交互的总次数，\(\gamma\)是一个参数，它影响着在items上具有不同流行度的propensity分布。power-law参数\(\gamma\)会影响着在items上的propensity分布，具体取决于dataset。根据之前的研究，对于每个dataset，我们会使用极大似然来估计\(\gamma\)参数。

7.实验结果与分析

我们在第5节提出使用一个propensity-based的直接评估方法，它会在推荐系统的离线评估中，考虑上deployed model的混杂角色（ confounding role）。在第6节中，我们提出使用Kendall’s \(\tau\)相关系数来量化在propensity-based stratified evaluation方法以及open loop evaluation间多个目标推荐模型的相对顺序间的相似度。下面，我们会会分别根据在第5节的两个研究问题开展实验，并关注和验证在标准离线评估的中 Simpson’s paradox，以及使用提出的propensity-based ed stratified evaluation方法的效果（7.2）。

7.1 RQ1: 研究Simpson’s Paradox

RQ1会研究：在推荐系统的离线评估中，基于假设2中提到的一个closed loop feedback dataset来研究deployed model的confounding effect。在第6.3节中，我们表述了一个简单的统计方法来表示deployed model的角色作为propensity scores。在下面，我们会使用estimated propensity score \(\hat{p}_{*,i}\)来将数据集划分成两个相同大小的层（ strata），称为Q1层和Q2层。

Q1和Q2 strata来分别表示用户与长尾items和头部items的交叉，我们会根据等式（7），基于每个item交互的总次数来估计propensity scores。

首先，我们会在closed loop dataset（MovieLens和Netflix）和open loop dataset（Yahoo!和Coat）上举例说明Simpson’s paradox。表2和表3会对比评估方法的效果（称为：holdout、IPS、提出的stratified评估法）。出于简洁，以下，我们会关注MovieLens dataset，分析两个模型（BPR、WMF）以及一个metric（nDCG）。我们观察到：在使用holdout和IPF评估法时，BPR要比WMF都好。然而，在同样的test dataset上进行分层分析（Q1和Q2层）表明：对于Q1分层，WMF要比BPR好很多；对于Q2分层，BPR则是支配模型。另外，我们观察到：Q1和Q2分层会分别覆盖99%和1%的user-item interactions。实际上，对于99%的test dataset（例如：Q1分层），WMF要比BPR好很多，但当我们结合Q2分层上1%的feedback时趋势会逆转，如holdout evaluation表示所示。因此，实际问题是：当使用holdout evaluation方法进行评估时认为的，BPR是否会比WMF执行的更好？分层分析表明：通过我们提出的分层评估法，WMF会被认为是更优的模型。我们注意到，BPR只会在1%的feedback dataset上是更优的模型，holdout和IPS evaluation方法两都都会受在test dataset上少量user-item interactions的影响。例如：在Q2分层中的1%的user-item interactions。该分层对应在MovieLens dataset的3499个items中只有4个items。在表3中，在MMMF和MF models间，在Netflix dataset中观察到相同的pattern。

在MovieLens和Netflix datasets中，我们不会访问open loop feedback，例如：feedback会通过一个随机曝光items进行收集。结果是，我们不能measure在一个open loop场景下的模型实验效果，对比起相应的closed loop场景。如第6.1节，我们对于在Coat dataset中的所有users，都有一些open loop feedback；而在Yahoo! dataset上只有一部分users有。表4和表5会表示在Yahoo! dataset中模型的两个pairs的效果对比。特别的，在表4中，我们会对比BPR和MF，它使用nDCG评估指标，并观察到：使用经典holdout evaluation方法，BPR要明显好于MF。另一方法，IPS评估法更偏向于MF，但，基于paired t-test(p < 0.05)上的差异没有显著。然而，基于估计倾向（Q1和Q2分层）的分层分析表明：对于Q1分层，MF要好于BPR；它可以覆盖在test dataset上92%的feedback；而BPR对于Q2分层则是更好的模型，它在closed loop test dataset上覆盖了8%的feedback。确实，对于test dataset中的大多数feedback和items（92%和99.5%），MF要胜过BPR。因此，我们会争论：通过任意的评估法（我们提出的分层评估法，或者open loop evaluation），MF应该被认为是一个更好的模型。当我们基于Q1和Q2分层（例如：holdout evaluation）的聚合数据进行评估模型时，在Yahoo! dataset上，1000个总items中只有少量5个items它对应于只有8%的总user-item interactions，会在受检模型的离线评估中，扮演着一个混杂因子的角色。当考虑上Coat dataset（表5）时，当评估GMF和SVD推荐模型的效果时，我们也会观察到相同的现象。表2、表3、表5中观察到的现象可以通过从一个closed loop场景收集到的datasets（MovieLens、Netflix、Yahoo!和Coat）被解释。因此，收集到的closed loop dataset会倾向于deployed model的特性（如表2、表4和表5中的Q2分层所捕获的）。

接着，为了完整回答RQ1，我们会评估以上观察的总结，通过验证在所有104个模型上的评估中 Simpson’s paradox的盛行。图3表明了，所有受检模型（）在Yahoo!和Coat datasets上在open loop evaluation和closed loop evaluation间的相关性。我们观察到，模型会表现出在Q1和Q2分层上的一个imbalanced效果，例如：Q1分层的nDCG score与Q2分层不成比例（\(nDCG_{Q2} >> nDCG_{Q1}\)）。另一方法，在Q1分层和open loop evaluation上Kendall’s \(\tau\)相关性，对比起Q2分层要更高。特别的，对于Coat dataset（图3b），基于Q2分层的closed loop evaluation对比open loop evaluation具有一个负向correlation。因此，在holdout evaluation中通过组合这两个异构分层，如图3a和3b所示，不能说明Q1分层覆盖feedback的大多数（在Yahoo!和Coat datasets上分别是92%和93%的total feedback），会导致不可预料的后果。特别的，在open loop evaluation和holdout evaluation间的Kendall’s \(\tau\)相关性，会比Q1分层和open loop evaluation间的对应相关性要低很多，例如：对于Yahoo!和Coat datasets，分别为：0.62 < 0.72 和 0.20 < 0.51. 这回答了RQ1: 推荐系统的offline holdout evaluation会受deployed model特性的影响（在Q2分层捕获），会导致对Simpson’s paradox的一个证实。

总之，在本节中，我们强调了在推荐系统的标准离线评估中，基于于closed loop和open loop datasets，证实了Simpson’s paradox的存在。接着，我们会研究提出的propensity-based分层评估法来解决该问题。

7.2 RQ2: 评估Propensity-based Stratified Evaluation方法

在本节中，我们会研究提出的propensity-based分层评估法会导致：对比IPS和holdout evaluation方法，结论与从open loop（随机化）evaluation获取的结果对齐的范围。确实，我们的目标是：研究每种评估法对应于open loop evaluation的范围。相反的，我们会考虑open loop evaluation，它与在线评估（A/B testing或interleaving）更相似，其中：评估过程不会受任意混淆因子的影响。如第6.2节所示，我们会利用在evaluation方法与open loop evaluation间Kendall’s \(\tau\)的rank相关系数。

表6展示了，在评估方法和ground truth（例如：open loop evaluation）间的Kendall’s \(\tau\)的rank相关系数。在分析该表时，我们会观察到，对于Yahoo! dataset，在holdout evaluation和open loop evaluation间的\(\tau\)相关系数是medium-to-strong（\(0.599 \leq \tau \leq 0.729\)）；而对于Coat dataset， weaker(\(-0.40 \leq \tau \leq 0.327\))，对于更大的截止点，两个数据集上的相关度都会轻微上升。确实，我们注意到，Coat dataset吃饭休息发货呢MovieLens/Netflix/Yahoo！会有一个不同的数据生成过程。另外，受检用户和items的数目会低于在Yahoo！dataset中数目。该发现与我们之前的研究一致：基于标准rank-based metrics的离线评估不必与在线评估的结果正相关，研究者们会质疑离线评估的合法性。

接着，我们会考虑在counterfactual evaluation(IPS)和open loop evaluation方法间的Kendall’s \(\tau\)相关性。表6表明，IPS评估方法效果要比holdout评估要稍微好些，例如：对于两个数据集中nCDG cut-offs的绝大多数，IPS的相关值要大于holdout evalution方法。然而，根据Steiger’s test，这些相关度差异没有任何在统计上是显著的。因此，我们会下结论，在评估期间，对比起holdout evaluation方法，counterfactual(IPS) evaluation方法不会更好地表示无偏用户偏好。这是因为：在IPS评估方法中，每个feedback是基于它的propensity进行加权独立（weighted individually）的。feedback sampling process（例如：从closed loop feedback中收集到的过程），并不是一个随机过程（random process）。因此，抽样的feedback会倾斜，相应的estimated propensity scores是不均的。在这种情况下，基于disproportionate propensities对feedback进行reweighting会导致在使用IPS评估模型效果评估上的高variance。

我们现在考虑表6中分层评估的相关性。这表明：在两个数据集中，对于nDCG cut-offs的绝大多数，特别是更深的cut-offs，分层评估的效果要好于holdout和IPS评估方法。例如：考虑将nDCG作为evaluation metric，我们会观察到，提出的分层评估方法效果要显著好于holdout evaluation和IPS evaluation，例如：对于Yahoo! dataset，0.710 > 0.622，0.710 > 0.644；对于Coat dataset，有0.283 > 0.202和0.283 > 0.225. 总体上，我们发现，对于两个datasets中更深的nDCG cut-offs，我们的propensity-based evaluation方法，效果要显著好于holdout和counterfactual evaluation。这可以回答RQ2.

然而，holdout evaluation的效果，IPS evaluation和提出的propensity-based分层评估方法，对于shallow nDCG cut-offs并不显著（对于Yahoo! dataset和Coat dataset来说，分别是：\(10 \leq k \leq 20 和 20 \leq k \leq 30\)）。对于deeper rank cut-offs的增加的sensitivity，支持了之前的研究：它对于推荐系统评估上deeper cut-offs的sparsity和discriminative pwoer来说更健壮。【43】发现，在feedback sampling process期间，由于只有少量items会曝光给该user，使用deeper cut-offs会允许研究者执行更健壮和discriminative evaluations。由【25】中，deeper rank cut-offs的使用对于训练listwise learning2rank技术来说可以做出相似的观察。

在feedback sub-populations (表6中的Q1和Q2分层)的进一步实验表明：受检模型的离线评估，它只基于long-tail feedback（Q1分层）更好地与open loop evaluation相关。特别的，对于Coat dataset，基于Q2分层的受检模型的离线评估，会与open loop evaluation具有一个负相关性。这支持了[9]的工作，它发现：非常少量的头部流行items会对推荐系统的rank-based evaluation进行倾斜。他们建议：当评估推荐模型的效果时，排除非常流行的items。

而表6演示了提出的分层评估方法对于两个sub-populations（Q1和Q2分层）的效果，我们接着检查了所使用分层数目的影响。特别的，在图4中，演示了提出的分层评估对于Coat和Yahoo! datasets的分层数目的影响。水平轴（X={1,2, …, 10}）会表示分层的数目，而竖直轴表示在提出的分层数目上与open loop（随机化）评估间对于104个受检模型的相关性。当我们只具有一个分层时（例如：在图4a和图4b中的X=1），提出的分层评估法对应于表6中的holdout evaluation。我们观察到，对于在两个数据集中的分层数目，对比起holdout评估（例如：X=1），提出的分层评估方法可以更好地与open loop（随机）评估相关。然而，在提出的分层评估和open loop（随机）评估间的相关度上，分层数目具有一个边缘效应（marginal effect），例如：在提出的分层评估（2<=X <=10）对于Coats和Yahoo! datasets间的平均相关度（mean correlations）是：\(0.266 \pm 0.021\)以及\(0.706 \pm 0.026\)，对比在holdout evaluation(X=1)中分别是0.202和0.622相关度。另外，对于\(2 \leq X \leq 10\)，大多数cases（coats和Yahoo!中分别是5/9和7/9）表示显著高于holdout evaluation的相关度。注意，每个dataset中的分层数目，可以使用分层原则（stratification principle）【24】来决定，它倾向于使用在每个层（stratum）内的层（strata），用户的反馈尽可能会相似。尽管不同数据集具有不同级别的closed loop effect，它取决于deployed model的特性，我们的实验表明：没有关于deployed model的进一步信息，基于estimated propensities将closed loop feedback分层为sub-populations，允许研究者们说明来自收集到的feedback dataset的closed loop effect。

8. 结论

略

参考

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

介绍

kuaishou在2020《Kraken: Memory-Efficient Continual Learning for Large-Scale Real-Time Recommendations》提出了它们的实时推荐系统。

摘要

现代工业推荐系统常常使用深度学习（DL）模型，这些模型通过更多的数据和模型参数来实现更高的模型准确性。然而，当前的开源DL框架，如TensorFlow和PyTorch，在训练具有数太字节参数的推荐模型方面显示出相对较低的可扩展性。为了有效地从每天生成数百太字节（terabytes）训练数据的数据流中学习大规模推荐模型，我们引入了一个名为Kraken的持续学习系统。Kraken包含一个特殊的参数服务器实现，它能够动态适应持续变化的sparse特征集，以持续训练和服务推荐模型。Kraken提供了一个感知sparse性的训练系统，该系统对dense和sparse参数使用不同的学习优化器，以减少内存开销。使用真实世界数据集进行的广泛实验证实了Kraken的有效性和可扩展性。Kraken可以在相同的内存资源下提高推荐任务的准确性，或者在保持模型性能的同时将内存使用量减少到原来的三分之一。

一、引言

近年来，推荐系统已经成为许多流行移动应用的基石。它们为各种内容（包括新闻文章、短视频和广告）生成个性化排序，从而提高用户与这些应用的互动体验。正如流行商业分析师所报告的，推荐系统通过增加用户参与度，为许多大公司如亚马逊和Facebook带来了相当一部分收入[1]-[3]。

时间敏感性对于推荐系统实现合理性能至关重要。例如，用户在与移动应用互动时的兴趣通常是非常非平稳的、季节性的，并且对趋势敏感。这被称为概念漂移[4]。推荐系统的另一个重要问题是所谓的冷启动问题[5]，即在有限的时间内推断新用户的偏好或新item潜在的受众。解决这些问题的一个常见方法是：使用实时持续学习（或在线学习）[6]、[7]，这意味着不断用新数据训练推荐模型以保持模型的新鲜度。这种策略适用于许多经典机器学习模型，如逻辑回归[8]、[9]和矩阵分解[10]。然而，随着深度学习（DL）在推荐系统中的兴起，DL模型的在线学习在系统可扩展性和模型质量方面面临挑战。

与用于计算机视觉（CV）和自然语言处理（NLP）的经典机器学习模型或DL模型不同，推荐系统的DL模型使用大量sparse分类特征，这些特征表示为一维或多维的高维独热二进制向量。随着不同sparse特征的数量达到数百万甚至数十亿以提高准确性，模型大小变得多太字节，因此不适合单个GPU甚至单个服务器的内存。此外，与有限的内存资源相比，每分钟都有大量新生成的内容和用户行为需要被表示到DL模型中。庞大的模型和不断流动的数据流为训练系统创造了极高的内存压力。在通过大量数据训练巨型模型的压力下，更难以有效地服务实时更新的模型。

现有系统不足以克服这些挑战。一般的开源DL框架，如TensorFlow[11]和PyTorch[12]，对于CV和NLP领域批量训练复杂DL模型进行了高度优化。先前在生产环境中的研究[1]、[13]、[14]表明，这些通用DL框架由于不善于处理大规模sparse特征，因此在大型推荐模型方面扩展性不佳。此外，不足的端到端在线学习支持使它们无法在不断增长和持续更新的模型下工作。即使是一些开源框架的内部版本也被认为需要高维护成本才能启用在线学习[15]。

在本文中，我们介绍了Kraken，这是一个考虑到sparse嵌入的生产就绪系统，用于优化在线学习和服务大规模推荐模型。据我们所知，这是第一份包含构建工业级推荐系统大规模持续学习系统在系统和算法方面的足够细节的论文。Kraken的核心是一个感知sparse性的训练系统，它有一个特定的参数服务器实现，结合数据并行和模型并行来训练推荐模型。专门的参数服务器支持自动特征准入和过期机制，以高效管理在线学习期间sparse嵌入的生命周期，利用有限的内存资源以获得更好的模型性能。此外，Kraken的在线服务系统将sparse嵌入的存储和模型预测的计算解耦，这显著节省了网络和存储成本。我们在TensorFlow 1.14之上实现了Kraken的训练系统，因此Kraken与TensorFlow API兼容。我们通过使用真实世界数据集进行离线实验和在线A/B测试来检验Kraken。结果揭示了与原始TensorFlow系统相比，Kraken的有效性和可扩展性。

二、背景与动机

A. 推荐系统中的深度学习

图1a展示了推荐系统的概览。对于给定的用户查询u，带有各种用户、item和上下文信息，推荐系统通常执行两步程序来从可能包含数十亿item的数据库中生成最相关items的$\lbrace x_i \rbrace$的排y序列表。

第一步称为检索（retrieval），它通过使用简单的机器学习模型和轻量级人为定义的规则的组合来返回数百个item，以提高效率。

在缩小候选池(candidate pool)后，后续的排序（ranking）步骤根据复杂深度学习模型生成的排序分数对所有item进行排序。排序分数通常是$ P(y \mid u, x_i)$的估计，即用户u在查看item $x_i$后，后续用户行为标签y（例如，点击、点赞）的概率。

为了训练这些模型，真实的用户反馈数据以及用户和上下文信息被记录在日志中作为训练数据。为了获得排序分数的准确预测，现代推荐模型使用大量sparse特征和复杂的DL模型[16]-[18]。sparse类别型特征通常用于表示任何两个一般实体之间的交互。例如，用户偏好特征可以是用户曾经点击过的最后K个视频ID的列表。为了有效处理sparse特征，推荐模型经常使用一种称为sparse嵌入的技术将它们转换为低维dense表示。如图1b所示，sparse特征可以被视为sparseID的向量。每个sparse特征与一个嵌入表配对，并且在转换过程中，特征的每个sparseID用于查找嵌入表中的唯一列（称为嵌入向量）。然后，通过逐元素收集操作（称为池化操作）将所需的嵌入向量组合成一个dense向量。新形成的dense向量成为模型其余部分的输入，以进行最终预测。

图1 推荐系统概述。(a) 推荐系统中的两个步骤，检索和排名。(b) 推荐系统的典型深度神经网络（DNN）模型架构。sparse特征（一系列ID，例如UID（用户ID）和VID（视频ID））首先会被映射到不同嵌入表中的dense嵌入向量（模型的sparse部分）。然后，所需的嵌入向量被组合并成为模型其余部分的输入，以进行最终预测。(c) 显示了嵌入表中的哈希冲突。

这些sparse嵌入表通常被称为推荐模型的sparse部分（sparse part）。模型的其余部分，包括多层全连接深度神经网络（DNN），被称为dense部分(dense part)。在数据大小和访问模式方面，sparse和dense部分之间存在巨大差异。如表I所示，sparse部分的大小可能是dense部分的1000倍甚至更大。然而，在每次训练或预测的小批量中，只有有限数量的嵌入向量在sparse部分被访问，而dense部分每个批次都被完全访问。Kraken重新设计了sparse嵌入的存储，并采用了更好的哈希策略，允许它支持更大的嵌入表。

当前的开源DL框架，如TensorFlow和PyTorch，使用dense可变矩阵（固定大小数组）来表示sparse嵌入。对于这些框架的常见做法是，这些sparseID需要被哈希到一个预定义的、可计数的集合中，以控制每个嵌入表的大小，称为哈希技巧（见图1c）。例如，对于一个ID为j的视频，其嵌入存储在大小为M的数组的索引(hash(j) mod M)处。这种方法可能很棘手，因为一些sparseID比其他ID更频繁地被访问（例如，那些视频更受欢迎，被更多用户点击）。不幸的是，当热门ID被哈希到同一个哈希桶时，由于值重叠，会导致预测准确性降低。避免哈希冲突的一个简单方法是增加哈希表大小，这会浪费未使用哈希桶的内存。Kraken重新设计了sparse嵌入的存储，并采用了更好的策略，允许它支持弹性扩展的嵌入表。

B. 推荐模型的并行范式

随着机器学习模型获得更多参数，由于其有限的计算和内存资源，单台机器不足以训练和服务大规模模型。许多先前的研究[11]、[19]-[21]提出了用于CV和NLP中使用的大规模神经网络的并行训练系统。典型的并行机制包括数据并行和模型并行[20]。数据并行将训练数据划分为多个数据集，每个worker一个，而模型并行将模型划分为可以并行训练的多个部分。

作为常见做法，推荐模型的并行训练结合了模型并行和数据并行，这是由于不同类型的参数特征（图2）。

• 对于模型的sparse部分：嵌入表是模型并行的，并通过哈希在多个worker之间共享，
• 而对于模型的dense部分：DNN是数据并行的，每个worker有一个独特的副本

图2 推荐模型的典型并行范式结合了模型并行性和数据并行性

sparse参数的大内存消耗基本上决定了我们至少需要多少worker来完成训练和服务。Kraken提出了几项优化，以在最低的计算资源开销下提供内存高效的学习和服务。

C. 大规模在线学习的必要性和挑战

先前的研究工作表明，在许多任务中增加深度学习模型的大小可以极大地提高它们的准确性和预测能力，而不会过拟合[22]、[23]。这一观察也适用于推荐系统，因为更大的嵌入表可以捕捉更细粒度的用户行为和item属性。图3a展示了基于DNN的推荐模型在三个工业数据集上的性能随着模型大小的增长而显著提高[13]、[24]。在大规模学习推荐模型方面，在线学习比批量训练有许多优势。

• 首先，工业推荐系统通常每天收集高达数百太字节（terabytes）的训练数据。在线学习通过流式实例使高效训练成为可能，每个训练实例只需要处理一次。
• 其次，在线学习允许新模型更频繁地更新并部署，比批量训练更重要，这对于解决第I节中提到的问题，如冷启动和概念漂移问题。

为了展示在线学习带来的好处，我们运行了一个在线A/B测试来比较Kraken的两种模式：

• 一种使用每五分钟更新一次模型的在线学习
• 另一种使用在测试期间不更新的静态模型

图3b绘制了A/B测试期间具有不同设置的两种模型的平均AUC，其中在线学习模型保持模型准确性稳定，但静态模型的AUC在一小时后下降了4.7%。它得出结论，在线学习在跟踪推荐系统中的用户兴趣方面是有效的。

图3 (a) 在三个工业数据集中，随着模型大小的增加，性能得到提升。(b) 线上学习模型与静态模型之间的性能比较。AUC值越高越好。

系统可扩展性受限于内存和长反馈循环（Long Feedback Loop）。采用在线训练推荐DL模型并将它们的sparse嵌入表扩展到多太字节的第一个挑战是：在内存效率和模型准确性之间进行权衡。如第II-A节所讨论的，sparse特征的sparseID不能在不考虑它们的重要性以及时间访问模式（例如，视频ID可能代表一个只应推广几天的趋势视频）的情况下均匀映射到哈希桶。随着在线训练的进行，sparse嵌入表动态增长，不同嵌入向量的数量增加得更快。这两种效应都导致嵌入表内哈希冲突的可能性高，模型性能下降。现有的开源训练和服务系统的另一个问题是：它们在部署大规模在线训练模型和支持实时数据反馈循环方面的效率低下[25]、[26]。在工业生产环境中，为了实现快速模型恢复和运行A/B测试以衡量它们的模型性能，需要同一任务的多个模型版本共存。因此，Kraken被重新设计，以超越以前的系统，支持具有超过数千亿参数的在线训练和服务推荐模型，同时保持稳定的模型准确性。

三、Kraken设计原则

为了构建一个内存高效的大规模推荐系统的在线学习系统，Kraken中的以下设计原则对于实现不仅系统可扩展性而且高模型质量至关重要：

• 1) 减少哈希冲突并在特征间共享内存空间。Kraken提出了一种动态地接纳和驱逐sparse嵌入的技术，以避免不必要的哈希冲突，并将所有sparse嵌入存储在全局共享的嵌入表中，以提高内存利用率。通过这种方式，Kraken不为每个sparse特征显式限制哈希桶的大小，而是允许嵌入表在在线学习过程中弹性和自动地调整大小。
• 2) 感知sparse性的训练框架。在拥有超过$10^{11}$的sparse特征的生产推荐系统中，sparse参数占内存资源的99.99%以上。Kraken引入了一个感知sparse性的训练框架来减少训练期间的内存使用。在这个框架下，我们还提出了一种新的优化器rAdaGrad，以进一步减少训练期间与sparse嵌入相关的内存使用。
• 3) 高效的持续部署和实时服务。在在线学习过程中，训练服务器中的模型始终从新生成的用户数据中学习。Kraken提出了一种高效的方法来部署不断更新的模型，而不会滞后。

为了最小化由哈希冲突导致的准确性损失，我们引入了无冲突但内存高效的嵌入结构——全局共享嵌入表（GSET），如图4所示。

图4 Kraken的全局共享嵌入表（Global Shared Embedding Table，简称GSET）

通常增加嵌入表的容量用于减少哈希冲突。然而，很难预测表的大小，因此在部署前设置一个高（通常是恒定的）嵌入表大小，特别是对于在线学习系统来说，这是不高效的。相反，我们提出了GSET，以便：

• 1)通过全局映射器将键值获取操作与特征嵌入过程解耦，它为每个嵌入表提供了高逻辑容量，通过在它们之间共享内存来灵活地调整物理内存占用，
• 2)执行自适应条目替换算法，即特殊的特征接纳和驱逐策略，确保在长期执行期间内存占用低于预设阈值。

GSET中的全局映射器：

GSET中的全局映射器将键值获取和嵌入解耦。它以特征的名称和值（例如，‘UID’和‘001’作为特征用户ID）作为输入，并返回一个由预设映射方式生成的格式化键，该键被发送到后端的内存中键值存储系统，该系统负责嵌入管理，而不是传统结构中的普通数组。键的格式主要由两个表示特征名称和特征值的域组成，并且对于模型开发人员的特殊要求具有高度的可配置性。例如，可以分别设置特征值域的宽度，以控制逻辑容量并满足不同特征的倾斜需求。有了全局映射器，GSET允许每个sparse特征的弹性增长和收缩，共享它们之间的内存资源，而不是手工制作不同大小的嵌入表。

特征接纳和驱逐：

为了在长期执行期间控制内存使用，GSET在整个在线学习过程中对所有活动特征执行不同的自适应条目替换算法。自适应条目替换算法利用sparse特征的不同特征来决定如何接纳和驱逐sparse嵌入，包括它们的频率、持续时间、特征重要性等。

• 例如，许多sparseID在我们的生产数据集中只出现一次，这些不应该被添加到GSET中。
• 另一个例子是，一些与趋势视频相关的sparseID在这些视频从数据库中退役后就不再需要了。

基于这种领域知识（即特征工程），机器学习工程师为每类sparse特征定制条目替换算法，以最大化模型性能。

GSET中使用的自适应特征接纳政策是：过滤掉频率低的sparseID。由于跟踪永远不会有任何实际用途的稀有特征的统计数据成本很高，GSET支持如[9]中介绍的概率基过滤器。概率基过滤器以概率$ p $接纳不在GSET中的sparseID。sparseID需要被看到的次数遵循几何分布，期望值为$ \frac{1}{p} $。有了这些过滤器，低频ID将在训练过程之前被丢弃，这消除了多余的计算和内存使用。

GSET中使用的传统内存缓存的条目替换算法（如LFU和LRU）旨在最大化缓存命中率，只考虑每个缓存条目被引用的频率。相反，GSET使用在线学习过程中获得的额外信息来确定达到内存限制后条目驱逐的顺序，这称为特征评分方法。GSET为每个sparseID维护一个特征分数，该分数由包含sparseID的训练样本数量以及这些样本的最近程度决定。在间隔期间，GSET通过以下公式更新每个sparseID的特征分数：

\[S^{t+1}_L = (1 - \beta)S^t_L + \beta (c^+ r + c^-)\]

其中:

• $ \beta $：是时间衰减率，
• $ r $：是重要性权重，
• $ c_+, c_- $：分别是在此间隔中包含sparseID L的正例和负例的数量。

当$ \beta = 1 $且$ r = 1 $时，特征评分方法等同于LFU。给正例和负例分配不同权重的原因是正例（例如，点击，点赞）相对较少，在模型预测中更有价值。这与处理不平衡数据集时的下采样技术[9]有相似之处。

在我们的生产工作负载中，我们发现另外两种启发式方法很有用。

第一种称为基于持续时间的政策，它为每个已更新的sparseID设置一个过期时间戳。在使用特征评分方法驱逐sparseID之前，垃圾收集器将首先回收那些已过期的sparseID。这是因为许多sparse特征有明显的生命周期，它们在训练日志中的出现在短时间内迅速消失。机器学习工程师可以在过去的数据分析上运行离线分析，以估计它们的平均持续时间，并为每个sparse特征设置一个最优的持续时间值。例如，我们网站上的许多视频在发布两天后没有视频点击或观看。因此，与视频ID相关的一些特征可以在两天后安全地回收。

第二个优化称为基于优先级的政策，它为有限大小的sparse特征设置驱逐优先级类别。在我们的生产环境中，sparse特征通常被分类为两个优先级类别：高优先级和低优先级。当GSET达到内存限制时，只有低优先级的sparse特征被特征评分方法驱逐。sparse特征的优先级通常由机器学习工程师的领域知识和特征重要性算法决定。在开始在线训练之前，可以使用[27]-[29]中的特征选择现代方法在离线分析中估计特征重要性。然后，可以在它们的总大小不超过某些内存限制的约束下，将顶级特征列表分组到高优先级类别中。例如，在我们的生产工作负载中，关闭与用户相关的特征（例如，用户ID、城市级别）的驱逐有助于提高模型准确性。

C. 高效的持续部署和实时服务

在本节中，我们主要介绍Kraken中为实时服务大规模推荐模型而构建的系统组件。

以前的服务系统设计[25]、[26]在一台预测机器内保持多个模型版本，无法支持需要跨节点共享的大规模推荐模型。

一种简单的方法是同位部署（图5a）（Co-located Deployment），它直接在推理服务器中处理分片模型。具体来说，每个推理服务器维护一个完整的dense部分和一个sparse部分分片。在预测时，它从其他对等方获取所需的参数，并在本地进行预测。然而，这种直接的方式在面对不断更新的模型时引入了相对较高的财务成本。

• 一方面，每个推理服务器需要高容量的DRAM来存储一部分sparse参数。
• 另一方面，不断的模型更新影响推理服务器，浪费它们的计算资源和NIC带宽。

为了在提供生产环境所需的功能的同时增强可扩展性，我们重新设计了预测系统，将存储服务和推理服务分别在不同的服务器上处理，称为非同位部署。

图5 预测系统的两种架构。基线方案直接将所有参数分区到不同的推理服务器上，而Kraken则将sparse嵌入的存储与模型预测的计算解耦。

非同位部署（Non-Colocated Deployment）。如图5b所示，Kraken的预测系统构建为两个服务：预测参数服务器（简称PPS）和推理服务器。

• 与训练中使用的参数服务器架构类似，预测参数服务器存储分片模型和嵌入表。
• 为了进一步减少请求延迟并节省NIC带宽，推理服务器缓存模型的某些部分，包括整个dense部分和频繁访问的嵌入向量。

当接收到包含sparse特征ID列表的请求时，推理服务器从预测参数服务器获取所需的sparse嵌入向量，然后执行模型推理。使用非同位部署的主要好处是允许这两个服务使用不同的硬件资源分别进行扩展。预测参数服务器需要大内存和高网络带宽，而推理服务器主要受计算资源的限制。因此，预测参数服务器可以使用高内存实例，推理服务器可以利用具有高计算能力的机器。

通过非同位部署，我们有两个额外的机会进一步优化服务系统。

• 一方面，为了增强局部性和负载均衡，Kraken支持按特征放置策略来根据它们的访问模式分布不同类型的参数。这个策略可以将一起访问的参数分组，并将它们放入同一个分片以获得更好的访问局部性。例如，一些用户端的二元sparse特征，如关注列表、收藏列表，通常以结合用户ID和其他项目ID的形式出现。因此，基于用户ID对这些sparse特征进行分片可以增强局部性，因为它们通常对同一用户一起访问。对于极受欢迎的参数，它们甚至可以在PPS的每个分片中复制，以减少热点并实现更好的负载均衡。
• 另一方面，虽然我们的分布式在线训练系统实现了对机器学习模型的更频繁更新，但也希望以分钟级别的延迟部署新训练的模型进行在线服务。为了同时减少负载并实现实时模型更新，Kraken的训练子系统采用不同的更新策略执行增量模型更新。对于模型的sparse部分，不是每次都传输多太字节嵌入表的完整副本，而是每个嵌入向量的更新将触发一个包含新值的更新消息，然后该消息将被发送到所有下游预测服务器以进行更新。对于模型的dense部分，由于它们的参数比sparse参数的波动性小，整个dense参数的副本将每几秒钟批量更新一次。

IV. 实现

Kraken使用C++11和Python实现。Kraken训练系统的初始版本实现了自己的工作引擎和参数服务器。然而，为了利用TensorFlow生态系统带来的好处，Kraken的新版本被构建为TensorFlow的插件，与TensorFlow的API完全兼容。该插件通过TensorFlow的C++底层API实现为定制操作符，这些操作符与Kraken的参数服务器交互，以执行sparse嵌入向量和dense变量的不同操作。为了预取和批量处理嵌入向量，我们还实现了嵌入缓存来存储在小批量中访问的嵌入向量。类似于Horovod[33]，TensorFlow插件在Python API层面添加了钩子和变量代理，以调度工作器发送梯度和参数服务器发送模型参数的时间和通信模式。

训练和服务于参数服务器的实现共享相同的代码库。参数服务器的核心（core）是一个高性能的易读键值存储，可以执行梯度聚合算法以及自适应特征管理算法。对于GSET，我们没有像[34]那样构建共享内存池，而是通过直接将所有参数分区到不同服务器来维护一个虚拟表，这是由于键值的简单语义。对于接纳算法，不需要维护任何状态，对于驱逐算法，所有策略都可以通过每个特征仅4字节（用于存储16位时间戳和16位特征分数）来支持。考虑到常见的128或256字节嵌入大小和由感知sparse性训练框架节省的空间，4字节的开销是微不足道的。

除了核心运行时，推理服务器的实现针对生产环境中的推荐任务进行了高度优化，可以支持包括CPU、GPU和FPGA在内的异构计算设备。Kraken的消息系统被构建为一个通用基础设施，不仅支持模型部署，还支持数据分发到需要可扩展解决方案的其他存储系统（例如，存储项目和用户特征的索引服务和用户档案服务）。

Kraken支持在线训练算法的异步和同步模式。在生产中，随着我们的模型扩展并需要更多的工作器，我们发现异步模式具有更高的训练速度，并且对机器故障更加健壮。因此，异步在线训练成为了训练我们的推荐模型的默认选项。

V. 评估

我们首先评估我们提出的技术的好处，然后报告Kraken在生产中实际应用的性能。

A. 实验设置

评估平台。我们在拥有64台服务器的集群上评估Kraken，除了从生产系统直接收集指标的生产性能评估外。集群中的所有服务器都配备了512GB DRAM和两个2.5GHz Intel(R) Xeon(R) Gold 6248 CPU，每个CPU有20个核心。服务器使用10 Gbps以太网连接。如果没有特别说明，每台服务器都配备了四个训练工作进程和一个参数服务器进程。

数据集。我们在公共数据集和生产数据集上衡量Kraken的性能，以便我们的实验可以轻松复现，同时展示实际工业场景中的性能。使用的公共数据集包括Criteo广告数据集、Avazu CTR数据集和MovieLens25M。Criteo广告数据集[35]在评估推荐模型时非常流行，并且很快将作为标准基准包含在MLPerf基准[36]中。Avazu CTR数据集[37]包含了一个领先广告平台的站点、应用和设备上的点击数据，共有11天。MovieLens-25M[38]通常作为一个稳定的基准数据集，包含2500万个电影评分，评分范围从1到5，以0.5为增量。在这里，我们将高于3的样本标记为正样本，其余为负样本，并将其训练为二元分类模型。两个生产数据集是从两个独立的现实世界推荐服务中收集的：Explore Feed和Follow Feed。这两项服务都向用户推荐与视频相关的内容。表III总结了不同数据集的特点。请注意，Explore Feed数据集需要5亿参数来构建一个合理的推荐模型，而Follow Feed数据集需要500亿参数（多100倍）。我们应用常见的指标，AUC和Group AUC[39]（GAUC），来评估模型的准确性。GAUC是所有用户AUC的加权平均值，以每个用户的样本数量为权重。因此，GAUC比AUC更能指示现实世界推荐系统中的模型性能。所有数据集都以在线学习的方式学习，即每个样本只训练一次。

实验比较了四种工业模型，DNN、Wide & Deep[16]、DeepFM[17]、DCN[40]在不同数据集上与Kraken和TensorFlow的结果。如果没有特别说明，默认的微基准模型是DeepFM。其他模型有类似的结论，因此我们省略它们以节省空间。更详细的设置，如模型的超参数，可以在我们的Artifact Description中找到，以便复现。

B. 端到端系统性能

我们评估Kraken的好处，包括系统方面和模型方面的表现。我们分别在TensorFlow和Kraken中应用Adam和混合优化器。具体来说，在Kraken中，dense部分的优化器是Adam，而sparse部分是rAdaGrad。选择Adam的原因是它是最受欢迎的优化器，并且在许多研究论文[17]、[41]中因其出色的收敛速度和少调整而被使用。更多与优化器相关的评估，如AdaGrad或SGD，将在后面的章节中介绍。为了公平比较，TensorFlow的嵌入表大小被设置为使内存消耗接近Kraken（可以容纳60%的所有原始特征）。

模型准确性。我们比较Kraken和TensorFlow以评估模型的准确性。由于计算资源有限，我们不对Follow Feed进行评估，因为它需要64台服务器从头开始训练，并持续一个月以验证一个可能的配置，使用一个50B参数模型。对于TensorFlow，我们尝试了五种不同的嵌入表大小组合，并仅显示最佳结果。需要强调的是，在有限内存的情况下，调整TensorFlow的嵌入表大小以获得好的模型是费力且耗时的。

图6显示了Kraken与TensorFlow相比在不同模型上带来的模型准确性提升。对于评估的四个工作负载，Kraken在公共数据集上比TensorFlow高出0.46%到6.01%的AUC，在Explore Feed上比TensorFlow高出1.64%到2.01%的GAUC，这是一个巨大的提升（在生产中，超过0.5%的提升是显著的）。Kraken的提升主要来自GSET的无哈希冲突设计和感知sparse性训练框架的适应性。此外，它显著减少了时间和计算资源，允许每个嵌入表的弹性增长，消除了对嵌入表大小的广泛调整。图6显示GSET可以实现比最佳人工调整的嵌入表更好的模型性能。

图6

系统开销。然后我们评估GSET对底层TensorFlow施加的开销，这可能影响端到端的训练速度。图7a通过在Explore Feed上变化训练服务器的数量，比较了Kraken和原生TensorFlow的吞吐量（即每秒样本数）。如图所示，Kraken的吞吐量始终接近或优于TensorFlow，从而洞察到Kraken的非常小的额外开销。此外，随着工作器数量的增加，Kraken保持线性增长，而当工作器数量增长到大约75时，TensorFlow的增长率下降。

图7

可扩展性。图7b显示Kraken在Follow Feed数据集上线性扩展。不幸的是，TensorFlow由于内存不足，不支持如此大模型的训练，当需要将如此多的特征列适应到原生TensorFlow嵌入表中时。Kraken显示出对大规模模型的更好适应性。

C. GSET评估

在本节中，我们评估GSET的设计。为了消除感知sparse性优化器的影响，我们在Kraken和TensorFlow中应用了相同的Adam优化器。如果没有特别说明，Kraken和TensorFlow使用相同的内存（足以存储60%的所有特征）。

GSET的内存效率。为了分析GSET在在线学习中的内存效率，我们在不同内存占用下（即，最多保存所有原始ID的几个比例）比较了使用Kraken和TensorFlow在Criteo数据集上不同模型的AUC。对于Kraken，特征接纳概率被设置为1，并启用了驱逐机制。如图所示，在不同的内存占用下，Kraken始终优于TensorFlow超过0.61%甚至高达3.72%。通常情况下，内存越少，GSET的提升越多。这是因为在原生TensorFlow中更激烈的哈希冲突使得模型更难学习代表输入特征的良好嵌入条目。GSET的设计减少了嵌入的哈希冲突，并在在线学习过程中学习了一组有效的特征。图8还说明了GSET的弹性增长设计可能是调整嵌入表大小的完美解决方案。

图8

特征接纳的效果。图9展示了在Explore Feed数据集中不同特征接纳概率P的效果。从图9a中，模型性能似乎不受接纳概率的影响。这是合理的，因为这些低频特征很少对整个模型做出贡献。Kraken简单地丢弃这些特征以避免频繁的过期。图9b显示了在最后一个训练小时中出现的不同频率级别的特征数量。有趣的是，不同接纳概率的低频特征数量几乎没有差异，这可能最初看起来违反直觉，但回想起来，尽管一些低频特征被过滤掉，一些相对高频的特征也更少地进入系统，从而成为新的低频特征。

图9

特征驱逐的效果。我们还进行了因素分析，以了解在保持内存使用的同时，每种特征驱逐策略对模型性能的贡献。在这个实验中，我们省略了Criteo Ad数据集，因为它的训练样本是特征匿名的，不包含时间戳信息，这将使特征驱逐盲目。

我们通过测量以下三种设置的模型性能差距来分解基线GSET仅具有LFU过期策略和结合所有三种驱逐策略的最佳性能：

• 特征评分策略（F）进一步考虑了正负样本的不同优先级。重要性权重r是从验证数据集中的[1, 3, 5]中选择的。特征分数每天衰减10%。
• 基于持续时间的策略（D）为每个特征类别设置不同的过期持续时间。我们预先采样10%的数据，分析具有相同ID的相邻样本之间的间隔时间分布，并取99.9百分位作为该特征类别的过期时间。
• 基于优先级的策略（P）禁止消除在Avazu和Explore Feed数据集中占用总内存不到10%的用户相关特征，基于我们的实践。然而，我们只在MovieLens数据集中禁用了占用较少内存并且访问更频繁的物品ID的驱逐。这是因为用户相关特征占据了高达50%，禁止驱逐它们将占用其他特征的内存，导致不满意的准确性。

图10表明，我们的特征评分策略在不同数据集上一致优于LFU策略，三种不同策略的累积可以结合它们的优势。可以得出结论，ML算法的领域知识和数据分布的感知可以使驱逐更智能，这就是为什么我们需要一个可配置的特征驱逐组件，以便ML工程师灵活定制。请注意，策略的超参数既与模型有关，也与数据集有关。我们在这里为了简单起见进行了经验设置，并且可以使用优化系统[42]进行更精细的调整。

图10

D. 感知sparse性训练框架的效果

接下来，我们展示Kraken的感知sparse性训练框架能够像原始优化器一样正确地收敛模型，并且在更少的内存资源下提供更好的准确性。在这个实验中，我们只关注优化器，因此我们为GSET提供了足够的内存，并关闭了特征接纳和驱逐功能。

表IV显示了在三个公共数据集上不同原始优化器和感知sparse性优化器的模型性能和内存消耗。在相同的内存消耗下，我们提出的混合优化器总是能够取得更好的性能，除了在两个负样本上有一些相似的性能。我们提出的组合Dense(Adam)&Sparse(rAdaGrad)在Test AUC和内存消耗方面都优于其他所有基线优化器和混合优化器。

它能够在减少3倍内存使用的同时，提供与Adam（正常优化器中最好的）一样高模型性能。尽管组合Dense(Adam)&Sparse(SGD)的OSPs稍少，但由于缺乏适应性，最终模型性能更差。它未能在实时推荐场景的sparse数据中很好地学习。Kraken的rAdaGrad提供了最小的存储开销和学习的适应性。

感知sparse性训练框架在性能和内存效率上的提升与第三节B部分一致。结果表明，Kraken的算法不依赖于模型或数据集。此外，感知sparse性训练框架节省的内存资源可以用来替换更多的sparse参数，从而提升模型性能。

E. 大规模在线预测评估

在本节中，我们构建了一个成本模型来评估Kraken预测系统的两种部署策略。我们考虑了两个集群组件的成本：预测参数服务器和推理服务器，并计算了云中每美元的预测吞吐量。基线是一个运行同位部署策略的预测系统。Kraken的非同位部署使其能够灵活地为预测参数服务器和推理服务器配置不同的服务器。这很重要，因为预测参数服务器是内存受限的，需要大内存，而推理服务器是计算受限的，不需要大内存。然而，对于基线的同位部署，所有推理服务器都需要是具有大内存的计算dense型服务器。 我们以一个16分片的Follow Feed模型为例进行进一步的成本建模。基于CPU和NIC带宽利用率的计算，一组16个预测参数服务器可以承载的推理服务器的最大数量估计为384。表V总结了使用两种不同部署策略的硬件成本。非同位部署在性价比上优于同位部署1.3倍（使用AWS价格数据[43]）或2.1倍（使用阿里云价格数据[44]）。从上述数据和分析中，我们得出结论，非同位部署在大规模推理集群中更有效，实现了更低的硬件成本。显然，通过将推理服务器从不断更新参数中解耦出来，Kraken实现了低成本和出色的推理性能。

F. 生产评估

由于Kraken已经在生产中部署了两年，我们报告了在几个现实世界应用中使用Kraken的性能指标，以展示其成功。

1) 在线A/B测试结果：我们选择了三个由Kraken支持的代表性应用：视频分享、社交网络和游戏平台。表VI显示了在使用Kraken后它们的关键业务指标的增长，如下所述：

• 视频分享是一个相关视频推荐应用，在使用户观看共享视频后提供更多视频建议。其关键业务指标是每个视频的平均播放次数（平均视频播放次数）。Kraken实现了视频播放次数51%的增长，并显著提高了用户参与度。
• 社交网络是在我们的平台上向用户推荐潜在社交联系的服务。新社交联系的平均数量是评估此服务的关键指标。Kraken将核心指标提高了1.35%，使更多用户连接到其他用户。（1.35%是显著的，与旧系统中通常的0.1%改进相比。）
• 游戏平台是一个托管不同数字游戏的在线平台，Kraken用于在其Feed中生成个性化的游戏视频推荐。其关键指标是用户在阅读Feed上花费的总时间（Feed上总时间花费）。Kraken在关键指标上提高了24.41%，显示出提高用户粘性的有效性。

2) 日常监控结果：我们还通过监控Kraken服务的推荐模型的准确性以及其在整个一天的服务吞吐量和延迟来报告生产中的Follow Feed应用的性能。（Follow Feed应用与第V-B节中的离线评估中使用的应用相同。）

• 模型准确性：图11a显示了Kraken生成的平均预测点击率（CTR-P）和Follow Feed中项目的平均点击率真实值（CTR-GT）。高点击率通常意味着高用户参与度，更准确的CTR预测有助于项目推荐。如图所示，CTR-P曲线与CTR-GT曲线非常接近，表明Kraken的模型预测准确性高。
• 系统性能：图11b展示了Kraken的系统吞吐量（即推理请求的数量）以及平均延迟和尾部延迟（P99）随时间的变化。在这一天中有两个明显的高峰，12:00至14:00和20:00至23:00。在后一个时期（图11b中的阴影区域），称为高峰时段，吞吐量高达40k QPS（每秒查询次数），是平均吞吐量的两倍。与此同时，尽管吞吐量急剧上升，Kraken仍然很好地控制了平均延迟和尾部延迟（P99）。

图11

VI. 相关工作

尽管系统和架构社区已经投入了大量精力对用于计算机视觉或自然语言处理的深度学习进行性能分析和优化，但相对较少的关注集中在在线学习和实时推荐系统中大规模深度学习模型的实时服务上。最相关的工作是Facebook的DLRM[1]、[13]，它指出了在现代生产规模下训练推荐系统的DNN所面临的独特挑战。它提供了详细的性能分析，表明推荐DL模型需要更大的存储容量并产生不规则的内存访问。他们使用蝴蝶洗牌操作符在嵌入表上实现模型并行以缓解内存限制。XDL[14]和Parallax[45]明确区分DL模型中的dense部分和sparse部分，并尝试通过许多sparse变量改进训练模型。Parallax通过使用AllReduce架构处理dense变量和PS架构处理sparse变量，为NLP的同步训练采用混合架构。然而，上述系统大多关注批量训练模型，其嵌入表大小是固定的，没有动态增长和全局空间共享。这些系统错过了实时训练和成本有效地服务10-TB DL模型的机会。传统的深度学习框架如[11]、[12]、[46]、[47]被全球的机器学习科学家和工程师使用。然而，它们在面对推荐系统中大规模实时推荐挑战时都无法扩展。HugeCTR[48]是NVIDIA为推荐系统设计的高效率GPU框架。HugeCTR将整个嵌入表分布到多个GPU的高带宽内存（HBM）中，以加速CTR模型的训练。然而，HugeCTR受到HBM大小的限制，因为所有sparse参数都必须在HBM内维护。在这种情况下，Kraken提供的内存高效学习可以被完美应用，并在节省计算资源开销方面发挥关键作用。

参数服务器（PS）[21]作为数据并行分布式训练领域中的代表性架构之一，在Kraken中作为底层通信模型使用。多年来，有许多先前的工作在许多方面优化了并行训练，包括利用集群中的GPU[24]、[49]、网络[50]和调度[51]–[53]。这些工作提出的技术与我们的工作正交，可以用来进一步改进Kraken中的训练。随着持久内存（PM）如英特尔Optane DC持久内存的出现，将传统的基于PM的键值存储[54]适应到Kraken并将是一件有趣的事情，并在新硬件带来的高能力的基础上缓解内存短缺。

持续学习已被证明是跟上推荐系统中用户兴趣快速变化的有效解决方案[6]、[7]、[9]。Continuum[55]是一个通用的持续学习系统，通过封装不同的学习框架，使用批量模式在新数据集上重新训练模型。与Kraken相比，Continuum更新模型的频率较低，并且不适用于大规模推荐模型。

VII. 结论

通过利用系统和训练算法的共同设计，Kraken提供了一个端到端的解决方案，用于实时训练和大规模推荐模型的服务。Kraken的训练系统实现了一个参数服务器，允许sparse嵌入表动态增长，并运行自动特征选择，在持续训练期间保持合理的内存大小。我们还提出了一个感知sparse性的框架，利用推荐模型的属性，在训练期间减少数据传输和内存占用。此外，Kraken的预测系统支持及时有效地部署大规模模型。Kraken已成功部署在生产中，用于广泛的推荐任务，并被证明在这些任务中迭代和服务大规模DL模型方面非常有效。

参考

• 1.https://storage.cs.tsinghua.edu.cn/papers/sc20-kraken.pdf/

介绍

google的Jeffrey Dean在2012《Large Scale Distributed Deep Networks》这篇经典paper中提出了大规模分布式DNN的设计。我们回顾一下：

摘要

最近在无监督特征学习和深度学习领域的工作表明，能够训练大型模型可以显著提高性能。在本文中，我们考虑了使用数万个CPU核心训练具有数十亿参数的深度网络的问题。我们开发了一个名为DistBelief的软件框架，可以利用数千台机器的计算集群来训练大型模型。在此框架内，我们开发了两种大规模分布式训练算法：

• （i）Downpour SGD，一种支持大量模型副本的异步随机梯度下降过程；
• （ii）Sandblaster，一个支持多种分布式批量优化过程的框架，包括L-BFGS的分布式实现。

Downpour SGD和Sandblaster L-BFGS都增加了深度网络训练的规模和速度。我们已经成功地使用我们的系统训练了一个比文献中先前报道的深度网络大30倍的网络，并在ImageNet上实现了最先进的性能，ImageNet是一个包含1600万张图像和21k类别的视觉对象识别任务。我们展示了这些相同的技术如何显著加速了一个更适度规模的深度网络的训练，用于商业语音识别服务。尽管我们专注于这些方法在训练大型神经网络方面的性能，但底层算法适用于任何基于梯度的机器学习算法。

1 引言

深度学习和无监督特征学习在许多实际应用中显示出巨大的潜力。在几个领域已经报告了最先进的性能，从语音识别[1, 2]、视觉对象识别[3, 4]到文本处理[5, 6]。还观察到，增加深度学习的规模，无论是训练样本的数量、模型参数的数量，还是两者都增加，都可以大幅提高最终分类精度[3, 4, 7]。这些结果导致了对扩大这些模型的训练和推理算法的兴趣激增[8]，并改进适用的优化程序[7, 9]。GPU的使用[1, 2, 3, 8]是近年来的一个重大进步，使得训练适度规模的深度网络变得实际。GPU方法的一个已知限制是，当模型不适合GPU内存时（通常小于6GB），训练加速很小。为了有效地使用GPU，研究人员经常减小数据或参数的大小，以便CPU到GPU的传输不是一个显著的瓶颈。虽然数据和参数的减小对于小问题（例如语音识别中的声学建模）效果很好，但对于具有大量样本和维度的问题（例如高分辨率图像）则不太吸引人。

在本文中，我们描述了一种替代方法：使用大型机器集群来分布式训练和推理深度网络。我们开发了一个名为DistBelief的软件框架，它支持在机器内部（通过多线程）和机器之间（通过消息传递）的模型并行性，框架管理并行性、同步和通信的细节。除了支持模型并行性(s model parallelism)，DistBelief框架还支持数据并行性(data parallelism)，其中使用多个模型副本来优化单个目标。在此框架内，我们设计并实现了两种新的大规模分布式训练方法：

• （i）Downpour SGD：一种异步SGD过程，利用自适应学习率并支持大量模型副本；
• （ii）Sandblaster L-BFGS：一种使用数据和模型并行性的L-BFGS的分布式实现。

Downpour SGD和Sandblaster L-BFGS与更传统的SGD和L-BFGS实现相比，都获得了显著的速度提升。我们的实验揭示了关于大规模非凸优化的几个令人惊讶的结果。

• 首先，异步SGD很少应用于非凸问题，但对于训练深度网络非常有效，特别是当与Adagrad[10]自适应学习率结合时。
• 其次，我们展示了：如果有足够的资源，L-BFGS与许多SGD变体相比具有竞争力或更快。

关于深度学习中的具体应用，我们报告了两个主要发现：我们的分布式优化方法既可以大大加速适度规模模型的训练，也可以训练比以往更大的模型。

• 为了说明第一点，我们展示了我们可以使用机器集群以不到GPU所需时间的1/10来训练一个适度规模的语音模型，达到相同的分类精度。
• 为了说明第二点，我们训练了一个超过10亿参数的大型神经网络，并使用这个网络在ImageNet数据集上大幅提高了最先进的性能，这是计算机视觉中最大的数据集之一。

2 先前的工作

近年来，商业和学术机器学习数据集以前所未有的速度增长。作为回应，许多作者已经探索了扩大机器学习算法以应对这些数据的洪流[11, 12, 13, 14, 15, 16, 17]。这些研究中的大部分集中在线性、凸模型[11, 12, 17]上。在凸情况下，分布式梯度计算[18]是自然的第一步，但有时由于同步问题而遭受减速。有一些有希望的努力来解决这个问题，例如在异步随机梯度下降中的无锁参数更新，例如Hogwild[19]。

不幸的是，将这些方法扩展到密集的非凸问题，例如在训练深度架构时遇到的问题，基本上是未知的领域。特别是，不知道是否可能在多个局部最小值存在的情况下平均参数或执行密集的异步参数更新。在深度学习的背景下，大部分工作集中在在单台机器上训练相对较小的模型（例如，Theano[20]）。扩大深度学习的一个有趣的建议是使用GPU农场来训练许多小型模型，然后平均它们的预测[21]，或者修改标准深度网络使其更易于并行化[22]。

与以前的工作相比，我们的重点是在不限制模型形式的情况下，扩大具有数十亿参数的非常大的模型的深度学习技术。在这种情况下，模型并行性，类似于[23]的精神，是一个基本成分，但必须与巧妙的分布式优化技术相结合，这些技术利用数据并行性。

我们考虑了许多现有的大规模计算工具，将其应用于我们的问题，MapReduce[24]和GraphLab[25]是显著的例子。我们得出结论：

• MapReduce，旨在并行数据处理，不适合深度网络训练中固有的迭代计算；
• 而GraphLab，旨在通用（非结构化）图计算，不会利用在深度网络中通常发现的结构化图中的计算效率。

3 模型并行性

为了促进非常大的深度网络的训练，我们开发了一个名为DistBelief的软件框架，它支持在神经网络和分层图形模型中的分布式计算。用户定义在模型的每个层的每个节点处进行的计算，以及在计算的向上和向下阶段应该传递的消息。对于大型模型，用户可以将模型分割到几台机器上（图1），以便将不同节点的计算责任分配给不同的机器。框架自动使用所有可用核心在每台机器上并行化计算，并在训练和推理期间管理机器之间的通信、同步和数据传输。

图1 DistBelief中模型并行性的例子。这里展示了一个具有局部连接性的五层深度神经网络，它被分割在四台机器（蓝色矩形）上。只有那些边跨越分区边界（粗线）的节点才需要在机器之间传输它们的状态。即使在节点有多个边跨越分区边界的情况下，其状态也只发送给边界另一侧的机器一次。在每个分区内部，单个节点的计算将在所有可用的CPU核心上并行化。

在多台机器上分布深度网络的性能优势取决于模型的连接结构和计算需求。具有大量参数或高计算需求的模型通常从访问更多的CPU和内存中受益，直到通信成本占主导地位。我们已经成功地在DistBelief框架中运行了多达144个分区的大型模型，并取得了显著的速度提升，而更适度规模的模型在多达8或16个分区上显示出不错的速度提升。（见第5节，在“模型并行性基准测试”标题下查看实验结果。）显然，具有局部连接结构的模型比全连接结构更容易进行广泛的分布，因为它们的通信需求较低。提速不理想的典型原因是：不同机器之间的处理时间有差异，导致许多机器需要等待那台最慢的机器，以便完成给定阶段的计算。尽管如此，对于我们最大的模型，我们可以有效地使用32台机器，每台机器平均使用16个核心，总共512个CPU核心训练一个大型神经网络。当与下一节描述的分布式优化算法结合使用时，这些算法利用整个神经网络的多个副本，可以利用数万个CPU核心来训练单个模型，从而显著减少整体训练时间。

4 分布式优化算法

在DistBelief框架内并行化计算使我们能够实例化和运行比以前报告的更大的神经网络。但是，为了在合理的时间内训练如此大的模型，我们不仅需要在单个模型实例内进行并行计算，也需要跨多个模型实例进行分布式训练。在本节中，我们描述了这第二级别的并行性，我们使用一组DistBelief模型实例或副本来同时解决单个优化问题。

我们比较了两种大规模分布式优化程序：

• Downpour SGD，一种在线方法
• Sandblaster L-BFGS，一种批量方法

两种方法都利用了集中式分片参数服务器的概念，模型副本使用它来共享它们的参数。两种方法都利用了DistBelief在每个单独副本内允许的分布式计算。但最重要的是，两种方法都被设计为容忍不同模型副本的处理速度差异，甚至是模型副本的大规模故障，这些副本可能被离线或随机重启。

从某种意义上说，这两种优化算法实现了数据并行性的智能版本。两种方法都允许我们同时在许多模型副本中的每一个中处理不同的训练样本，并定期组合它们的结果来优化我们的目标函数。

4.1 Downpour SGD

随机梯度下降（SGD）或许是训练深度神经网络最常用的优化过程[26, 27, 3]。不幸的是，SGD的传统公式本质上是顺序的，使得它不适用于非常大的数据集，因为在完全顺序化的方式下完成全部数据计算所需的时间是令人望而却步的。

为了将SGD应用于大型数据集，我们引入了Downpour SGD，这是一种使用单个DistBelief模型的多个副本的异步随机梯度下降变体。基本方法如下：我们将训练数据分成多个子集，并在这些子集上运行模型的副本。模型通过一个集中的参数服务器通信更新，该服务器保存模型的所有参数的当前状态，这些参数分布在许多机器上（例如，如果我们有10个参数服务器分片，每个分片负责存储和应用模型参数的1/10的更新）（图2）。这种方法在两个不同的方面是异步的：模型副本独立运行，参数服务器分片也独立运行。

图2 左边：Downpour SGD。模型副本异步地从参数服务器获取参数 $ \mathbf{w} $ 并推送梯度 $ \Delta \mathbf{w} $。右边：Sandblaster L-BFGS。一个单独的“协调器”向副本和参数服务器发送小消息，以协调批量优化。

在最简单的实现中，在处理每个小批量之前，模型副本会向参数服务器服务请求其模型参数的更新副本。由于DistBelief模型本身分布在多台机器上，因此每台机器只需要与持有与其分区相关的模型参数的参数服务器分片通信。在接收到其参数的更新副本后，DistBelief模型副本处理一小批数据以计算参数梯度，并将梯度发送到参数服务器，然后参数服务器将梯度应用于模型参数的当前值。

可以减少Downpour SGD的通信开销，通过限制每个模型副本仅在每$ n_{\text{fetch}}$ 步请求更新参数，并且仅在每$ n_{\text{push}}$步发送更新的梯度值（其中：$ n_{\text{fetch}} \text{可能不等于} n_{\text{push}}$。

实际上，获取参数（fetch）、推送梯度（push）和处理训练数据的过程可以在三个仅弱同步的线程中进行（见附录中的伪代码）。在下面报告的实验中，我们为了简单和便于与传统SGD比较，将 $ n_{\text{fetch}} = n_{\text{push}} = 1 $ 固定。

Downpour SGD比标准（同步）SGD更能够抵抗机器故障。对于同步SGD，如果一台机器失败，整个训练过程将被延迟；而对于异步SGD，如果模型副本中的一台机器失败，其他模型副本继续处理它们的训练数据并通过参数服务器更新模型参数。另一方面，Downpour SGD中的多种异步处理引入了优化过程中的大量额外随机性。最明显的是，模型副本几乎肯定是基于一组稍微过时的参数计算其梯度，因为其他模型副本可能在此期间已经更新了参数服务器上的参数。但是，除此之外还有几个其他的随机性来源：由于参数服务器分片独立运行，不能保证在任何给定时刻，每个参数服务器分片上的参数经历了相同数量的更新，或者更新以相同的顺序应用。此外，由于模型副本被允许在单独的线程中获取参数和推送梯度，可能还存在参数的时间戳的额外微妙不一致性。对于非凸问题，这些操作的安全性几乎没有理论基础，但在实践中我们发现放宽一致性要求非常有效。

我们发现一种可以大大增加Downpour SGD鲁棒性的技术是使用Adagrad[10]自适应学习率过程。Adagrad不是在参数服务器上使用单一固定学习率（图2中的η），而是为每个参数使用单独的自适应学习率。设：

• $ \eta_{i,K} $ 为第 $ i $ 个参数在第 $ K $ 次迭代的学习率
• $ \Delta w_{i,K} $ 为其梯度

则我们设置：

\[\eta_{i,K} = \frac{\gamma}{\sqrt{\sum_{j=1}^{K} (\Delta w_{i,j})^2}}\]

由于这些学习率仅从每个参数的累积平方梯度计算，Adagrad可以很容易地在每个参数服务器分片内局部实现。γ的值，所有学习率的常数缩放因子，通常比没有使用Adagrad时使用的最佳固定学习率大（可能大一个数量级）。Adagrad的使用扩展了可以同时有效工作的模型副本的最大数量，并且结合了仅使用单个模型副本“预热”模型训练的做法，然后释放其他副本，它几乎消除了使用Downpour SGD训练深度网络时的稳定性问题（见第5节的结果）。

4.2 Sandblaster L-BFGS

批量方法已被证明在训练小型深度网络方面表现良好[7]。为了将这些方法应用于大型模型和大型数据集，我们引入了Sandblaster批量优化框架，并讨论了在此框架中使用L-BFGS的实现。

Sandblaster的一个关键思想是分布式参数存储和操作。优化算法（例如L-BFGS）的核心位于协调器进程（图2），它没有直接访问模型参数。相反，协调器发出来自一小组操作（例如，点积、缩放、系数加法、乘法）的命令，每个参数服务器分片可以独立执行这些操作，并将结果存储在同一分片上。附加信息，例如L-BFGS的历史缓存，也存储在计算它的参数服务器分片上。这允许运行大型模型（数十亿参数）而不会因将所有参数和梯度发送到单个中央服务器而产生开销（见附录中的伪代码）。

在典型的L-BFGS并行化实现中，数据被分发到多台机器上，每台机器负责计算特定子集数据示例上的梯度。梯度被发送回中央服务器（或通过树形结构聚合[16]）。许多这样的方法等待最慢的机器，因此不适用于大型共享集群。为了解决这个问题，我们采用了以下负载平衡方案：协调器为N个模型副本中的每一个分配一小部分工作，远小于批次总大小的1/N，并且每当副本空闲时就分配新的部分。通过这种方法，较快的模型副本比慢的副本做更多的工作。为了进一步管理批次末尾的慢模型副本，协调器调度多份未完成的部分，并使用最先完成的模型副本的结果。这种方案类似于MapReduce框架中“备份任务”的使用[24]。数据预取，以及通过将数据的连续部分分配给同一工作器来支持数据亲和性，使得数据访问不成问题。与Downpour SGD相比，后者需要相对高频率、高带宽的参数同步与参数服务器，Sandblaster工作器仅在每个批次开始时（当它们被协调器更新时）获取参数，并且仅在完成几个部分后发送梯度（以防止副本故障和重启）。

实验

略

参考

• 1.https://www.cs.toronto.edu/~ranzato/publications/DistBeliefNIPS2012_withAppendix.pdf