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

Pinterest在《Graph Convolutional Neural Networks for Web-Scale Recommender Systems》中提出了PinSage：

介绍

深度学习方法已经在推荐系统应用中非常重要，被用于学习关于图片、文本、单个用户的有用高维embeddings。使用deep models学到的representations可以被用于补全、或者替换传统的推荐算法（比如：CF）。并且这些学到的representations具有高可用性，因为他们可以被用在许多推荐任务中。例如，使用一个deep model学到的item embeddings可以被用于item-item推荐，并且可以推荐有主题的集合（例如：playlists，或者“feed”内容）

最近，在该领域内有较大发展——特别是能够基于在图结构化数据上学习的新deep learning方法的发展，这对于推荐应用来说很基础（例如：可以利用user-to-item交互图，也可以使用社交网络图）。

在这些成就中，最著名的是Graph Convolutional Networks（GCNs）深度学习结构的成功。GCNs背后的核心思想是：学习如何从局部图邻居（local graph neighborhoods）的feature信息中进行迭代式聚合（aggregate）（图1）。这样的一个“卷积（convolution）”操作会从一个node的一跳图邻居的feature信息进行转换和聚合，并且通过将多个这样的convolutions信息进行stacking可以传播到图的远方。不同于纯content-based deep models（例如：RNNs），GCNs会同时利用内容信息和图结构。GCN-based方法已经在无数推荐系统benchmarks上设置了一个新的标准。然而，在benchmark任务上的收益还没有转换到真实生产环境中。

同时将GCN-based node embeddings的training和inference扩展到具有数十亿nodes和数百亿edges的图上是一个巨大的挑战。当在一个大数据环境中，对GCNs进行扩展很难，因为在设计底下的许多核心假设是冲突的。例如，在训练期间，所有已存在的GCN-based推荐系统需要在整个图拉普拉斯算子（full graph Laplacian）上操作，因而是不可行：当底层图（underlying graph）具有数十亿nodes，它们的结构通常是演化的。

当前工作

这里我们提出了一个高度可扩展的GCN框架，我们在Pinterest的生产环境中开发和部署过。我们的框架，是一个random-walk-based GCN 称为“PinSage”，它在30亿nodes和180亿edges的一个大型图（massive graph）上操作——该graph是GCNs的常见应用的10000倍以上大。

PinSage会利用许多关键insights来弹性提升GCNs的可扩展性：

• on-the-fly convolutions：传统的GCN算法通过将feature matrics乘以full graph Laplacian的幂来执行图卷积。相反的，PinSage算法执行很高效，通过对在一个node周围的邻居进行抽样，并且从该抽样后的邻居来动态构建一个计算图。这些动态构建的计算图（图1）指定了如何在一个特定node周围执行一个局部卷积（localized convolution），并且缓和了在训练期间对整个graph操作的需求。
• Producer-consumer minibatch construction：我们开发了一个producer-consumer架构来构建minibatches，它能确保在模型训练期间最大化GPU利用率。一个大内存、CPU-bound producer可以有效抽样node network邻居，并且获取必要。
• 有效的MapReduce inference：给定一个fully-trained GCN模型，我们会设计一个有效的MapReduce pipeline，可以将训练好的模型分散来生成数十亿节点的embeddings，可以最小化重复计算。

图1

除了在可扩展性上的这些基础优点外，我们也会引入新的训练技术和算法创新点。这些创新点会改善由PinSage学到的representations的质量，从而能导致在下游推荐系统任务上获得大的提升：

• 通过random walks来构建convolutions：通过采用节点的所有邻居来执行convolutions（图1）会导致很大的计算图，因此，我们会采用sampling。然而，random sampling是次优的，我们会开发一种新的技术，它使用short random walks来采样计算图（computation graph）。一个额外的好处是：每个node具有一个importance score，我们会在pooling/aggregation step中使用。
• Importance pooling：graph convolutions的一个核心组件是：在graph中的局部邻居的feature信息的aggregation。我们会引入一个方法来对在该aggregation中的node features的importance进行权衡，它基于random-walk相似度measures，在离线评估指标中会有一个46%的效果增益。
• 课程培训（Curriculum training）：我们设计了一个Curriculum training的scheme，其中该算法会在训练期间feed越来越hard的样本，从而产生一个12%的效果增益。

对于在Pinterest中的多个推荐任务，我们已经部署了PinSage，它是一个用户可以对交互的pins进行流行内容发现和管理的应用，其中：pins是在线内容的一个可视化书签。用户会将这些pins组织成boards，它包含了许多相似pins的collections。总之，Pinterest是世界上关于图片的最大user-curated graph（用户组织图），具有20亿唯一的pins，被收集到超过10亿的boards上。

通过大量离线metrics、A/B tests，我们展示了：对比起其它可扩展的deep content-based推荐算法，我们的方法在一个item-item推荐任务上（例如：相关pins推荐）以及一个”homefeed”推荐任务上可以达到SOTA的效果。在离线ranking指标上，我们对比baseline获得了超过40%的提升，在head-to-head人工评估上，我们的推荐要好60%。。

据我们所知，这是最大的deep graph embeddings，为新一代基于graph convolutional结构的推荐系统铺平了道路。

2.相关工作

略

3.方法

在本节中，我们会描述PinSage结构、training、以及MapReduce pipeline的技术细节，可以使用一个训练好的PinSage模型来有效生成embeddings。

我们的方法的关键计算重任是：局部图卷积（localized graph convolutions）。为了为一个node（例如：一个item）生成embedding，我们会应用多个convolutional模块，它们会聚合来自该node的局部图邻居（local graph neighborhood）（图1）的feature信息（例如：可视化features、文本features）。每个module会学习如何从一个小的图邻居（graph neighborhood）来聚合信息，通过将多个这样的模型进行stacking，我们的方法可以获得关于局部网络拓朴的信息。重要的是，这些localizied convolutional modules的参数会跨所有nodes进行共享，使得我们的方法的参数复杂度完全取决于input graph size。

3.1 问题设定

Pinterest是一个内容发现应用，其中：

• 用户会将这些pins组织成boards，
• 用户会将比较相关的pins包成集合

总之，Pinterest graph包含了20亿pins，10亿boards，并且超过180亿的edges（例如：pins的成员和它们相应的boards）。

我们的任务是，生成pins的high-quality embeddings 或者 representations（例如：通过最近邻查询相关的pin推荐，或者在下游的reranking系统中使用）。为了学习这些embeddings，我们会将Pinterest环境建模成一个二部图，它包含了两个不相互交集合I（包含了pins）和C（包含了boards）的结点。注意，我们的方法也是天然泛化的，其中I被看成是一个items集合，C被看成是user-defined contexts和collections。

除了图结构外，我们也会假设：pins/items \(u \in I\)会与real-valued属性相关联，\(x_u \in R^d\)。总之，这些属性可以指定关于一个item的metadata或content信息，另外在Pinterest的case中，我们有：具有丰富文本信息和图片features有关的pins。我们的目标是，利用这些input属性，以及二部图结构来生成高质量embeddings。这些embeddings接着会被用于通过最近邻lookup的推荐系统的候选生成（例如：给定一个pin，发现相关pins）或者在对候选排序时作为features使用。

出于便利性和泛化性，当我们描述PinSage算法时，我们会简单地将完整graph的node set使用 \(V = I \cup C\)来表示，不会显式对pin和board nodes进行显式区别（除非严格必要），会统一使用更通用的术语“node”.

3.2 模型结构

我们会使用localized convolutinal模块来生成nodes的embeddings。我们从input node features开始，接着开始学习nueral networks，它会将通过graph来对features进行transform和aggregate来计算node embeddings（图1）。

前向传播算法

我们会考虑生成一个embedding的任务， 对于一个node u的\(z_u\)，它取决于node的input features和围绕该node的图结构。

算法1

PinSage算法的核心是一个localized convolution操作，其中，我们会学习如何从u的邻居（图1）的信息聚合。该过程在算法1 CONVOLVE中有详解。基本思想是：我们将关于u的邻居通过一个dense neural network进行转换成representations \(z_v \forall v \in N(u)\)，接着在vectors的结果集（第一行）上应用一个aggregator/pooling function（例如：一个element-wise mean或weighted sum，表示为\(\gamma\)）。该aggregation step会提供一个关于u的局部邻居\(N(u)\)的vector representation \(nu\)。我们接着将aggretated neighborhood vector \(n_u\)与u的当前representation \(h_u\)进行拼接，并将contantenated vector \(n_u\)与u的当前representation \(h_u\)进行concatenate在一起，并通过另一个dense neural network layer（第2行）将concatenated vector进行转换。经验上，我们观察到：当使用concatenation operation来替代average operation时会取得极大的效果提升。另外，在第3行中的normalization会使得训练更稳定，它对于normalized embeddings来说执行近似最近邻搜索更高效（第3.5节）。该算法的output是一个关于u的representation，同时包含了它自己以及它的局部图邻居间的信息。

Importance-based neighborhoods

在我们的方案中，一个重要概念是：如何定义节点邻居\(N(u)\)，例如：如何在算法1中选择要convolve的邻居集合。然而，之前的GCN方法会简单检查k-hop的图邻居，在PinSage中，我们定义了importance-based 邻居，其中：一个node u的邻居会被定义成T nodes会对node u施加最可能的影响。具体的，我们会从node u开始模拟random walks，并且计算出由random walk访问到的L1-normalized的节点访问数。u的邻居接着被定义成：对于node u具有最高的normalized visit counts的T个nodes。

该importnace-based邻居定义的优点是两面的。

• 首先，选择一个固定数目的节点来聚合，允许我们控制着在训练期间该算法的memory footprint。
• 第二，当聚合邻居的vector representations时，它会使算法1考虑邻居的importance

特别的，我们会在算法1中实现\(\gamma\)作为一个weighted-mean，它使用根据L1 normalized visit counts定义的weights。我们将该方法称为importance pooling。

Stacking convolutions

每个时间，我们会使用CONVOLVE操作（算法1），我们会从一个node处获得一个新的representation，并且将多个这样的convolutions相互进行stack，以便获得围绕node u的局部图结构的更多信息。特别的，我们会使用多个关于convolutions的layers，其中：在layer k上的convolutions的inputs依赖于来自layer k-1（图1）的representations output，其中：intial（例如：“layer 0”）representations等于input node features。注意，在算法1（Q,q,W,w）中的模型参数会跨nodes共享，但在layers间的参数则不同。

算法2会详细说明：stacked convolutions 是如何为一个nodes的minibatch set M生成embeddings。我们首先计算每个node的邻居，接着使用K个convolutional迭代来生成关于target nodes的layer-K的representations。final convolutional layer的output接着通过一个fully-connected neural network进行feed来生成最终的output embeddings \(z_u, \forall u \in M\)

我们接着学习模型的full set参数：对于每个convolutional layer \((Q^{k}, q^{(k)}, W^{(k)}, w^{(k)}, \forall k \in \lbrace 1,\cdots,K \rbrace)\)的weight和bias参数，以及最终dense neural network layer \(G_1, G_2, g\)的参数。在算法1中的Line 1的输出唯度（例如：Q的column-space维度）会被设置为，在所有layers上均是m。出于简洁性，我们将所有convolutional layers的输出维度设置为相当（算法1第3行），接着我们将该size参数通过d进行表示。该模型的最终output维度（算法2）也被设置为d。

算法2

3.3 模型训练

我们会以一个监督学习的方式，使用max-margin ranking loss来训练PinSage。在该setup中，我们假设：我们已经访问了一个关于items L的labeled pairs集合，其中：在该set中的pairs \((q, i) \in L\)会被假设是相关的——例如：我们假设：如果 \((q, i) \in L\)，那么item i是对于query item q的一个好推荐侯选。training阶段的目标是，最优化PinSage参数，以便在labeled set中的pairs \((q,i) \in L\)的output embedding 是非常接近的。

我们首先详细描述了margin-based loss function。根据此，我们给出了一个关于我们开发的多个技术的总览，它会导致PinSage的计算效率以及快速收敛，允许我们可以在数十亿节点的graphs和数十亿训练样本上进行训练。最终，我们描述了我们的curriculum-training scheme，它会提升推荐的总体质量。

Loss function

为了训练模型的参数，我们会使用一个Max-margin-based loss function。基本思想是：我们希望最大化正样本的inner product，例如：query item的embedding以及相应的相关item。同时，我们希望确认，负样本的inner product（例如：在query item的embedding和一个unrelated item间的inner product）要小于正样本由一些pre-defined margin给出的正样本。对于 \((z_q, z_i) \in L\)的node embeddings的单个pair的loss function：

\[J_G(z_q z_i) = E_{n_k \sim P_n(q)} max \lbrace 0, z_q \cdot z_{n_k} - z_q \cdot z_i + \Delta \rbrace\]

…(1)

其中：

• \(P_n(q)\)表示了对于item q的负样本的分布
• \(\Delta\)表示了margin hyper-parameter

我们会在下面解释负样本的采样。

使用large minibatches的Multi-GPU训练

为了在单机训练上充分利用多个GPUs，我们会以一个multi-tower的形式来运行forward和backward propagation。有了多个GPUs后，我们首先会将每个minibatch（图1底部）划分成等size的比例。每个GPU会获取minibatch的一部分，并使用参数的相同集合进行计算。在backward propagation后，在所有GPUs上每个参数的gradients会聚合到一起，会执行单频synchronous SGD。由于需要在非常大数目的样本上（数十亿规模）训练，我们会使用large batch sizes进行运营，范围从512到4096.

我们使用由Goyal[16]提出的相似技术来确保快速收敛，当处理大的batch sizes时，并保持训练和泛化的准确率。我们使用一个渐近的热启过程（gradual warmup produre），在第一个epoch，根据线性scaling rule从小到大增加learning rate。之后，learning rate会指数递减。

Producer-consumer minibatch构建

在训练期间，由于size很大，对于数十亿nodes的feature matrix和adjacency list会在CPU memory中放置。然而，在PinSage的CONVOLVE step，每个GPU过程需要访问在邻居中节点的邻居和feature信息。从CPU内容中访问来自GPU的数据并不高效。为了解决该问题，我使用一个re-indexing技术来创建一个sub-graph \(G' = (V', E')\)包含了nodes和它的邻居，它会在当前minibatch的计算中被涉及。一个小的feature matrix会只包含了与当前minibatch的计算相关的node features，会被抽取出来，以便顺序与在G’中的nodes的index相一致。G’的adjacency list和small feature matrix会在每个minibatch迭代中被feed到GPUs中，因此，在GPU和CPU间的通信在CONVOLVE step期间不需要，极大提升了GPU利用率。

训练过程会交替使用CPUs和GPUs。模型会在GPUs中计算，然而：抽取features、re-indexing、negative sampling会在CPUs中计算。除了使用multi-tower training的并行GPU计算之外，CPU计算会使用OpenMP，我们会设计一个 producer-consumer pattern来在当前迭代中运行GPU计算，在下一迭代上并行使用CPU计算。这会进一步减少一半的训练时间。

对negative items进行采样

negative sampling会在我们的loss function中会被使用，作为edge likelihood的normalization factor的一个近似。当使用大的batch sizes训练时会提升效率，我们抽样一个关于500 negative items的集合，会在每个minibatch中与所有训练样本进行共享。对比起对于每个node独立运行负样本来说，这会极大节约需要在每个training step期间被计算的embeddings的数目。经验上，我们不会观察到在两个sampling schemes间效果的一个不同之处。

在最简单的case中，我们会从items的整个集合中均匀抽样负样本。然而，确保正样本（items(q,i)的pair）的内积大于q，500 negative items的每个都太“easy”，对于要学习的系统来说，不会提供足够好的“resolution”。特别的，我们的推荐算法可以发现在20亿items的catalog间与q 最相关的1000个relevant items. 换句话说，我们的模型会在20亿items上能够区分/标识 1个item。但在500个random negaive items，模型的resolution只有1/500. 因此，如果我们从20亿items中抽样出500个随机负样本items，任何这些与query items更轻微相关的items的机会更小。因此，该学习大概率不会做出好的参数更新，不能区分非常相关items和轻微相关items。

为了解决上述问题，对于每个正的训练样本（例如：item pair (q,i)），我们会增加“hard” negative examples，例如：items一定程度上与query item q相关，但与正样本item i不相关。我们称这些为“hard negative items”。他们会根据query item q的Personlized PageRank score通过在graph中的items进行ranking来生成。在2000-5000上排序的items会被随机抽样作为hard negative items。如图2所示，hard negative examples对比起random negative examples与query更相似，对于模型排序来说挑战更大，强制模型去学习以细粒度的方式区分items。

图2

通过training produre使用hard negative items，是需要训练至收敛的epochs数目的两倍。为了帮助收敛，我们开发了一个curriculum training scheme【4】。在训练的第一个epoch，不会使用hard negative items，以便算法快速发现在参数空间中的一个区域，其中：loss是相对小的。我们接着在后续epochs中添加hard negative items，聚焦于模型去学习如何区分高度相关pins和轻微相关pins。在训练的epoch n，我们会为每个item添加n-1个hard negative items到negative items集合。

3.4 通过MapReduce的Node embeddings

在模型被训练之后，直接使用训练好的模型来为所有items（包含了在训练期间没有见过的items）来生成embeddings仍然是很具挑战的。使用算法2以naive的方式计算nodes的embeddings，会导致重复计算，这是由nodes的K-hop邻居间的重合引起的。如图1所示，当为不同的target nodes生成embeddings时，许多nodes会在多个layers上重复计算。为了确保有效的inference，我们开发一个MapReduce方法，它无需重复计算即可运行model inference。

图3

我们观察到：node embeddings的inference可以非常好地借助于MapReduce的计算模型。图3详述了在二部图上的data flow，pin-to-board Pinterest graph，其中，我们假设：input（例如：“layer-0”） nodes是pins/items（以及layer-1 nodes是boards/contexts）。MapReduce pipeline具有两个关键部分：

• (1) 一个MapReduce 工作可以用于将所有pins投影到一个低维latent space中，其中：aggregation oepration会被执行（算法1，第一行）
• (2) 另一个MapReduce job接着用于将产生的pin representations，与他们出现的boards的ids进行联合，board embedding的计算会通过它的邻居的features进行pooling。

注意：我们的方法会避免冗余计算，每个node的latent vector只会计算一次。在boards的embedding会被包含后，我们会使用两个多的MapReduce jobs来计算关于pins的第二层的embeddings，以一个相似的方式，该过程可以尽快迭代（直到K个convolutional layers）。

3.5 高效地最近邻lookups

由PinSage生成的embeddings可以被用于许多下游推荐任务中，在许多settings中，我们可以直接使用在学到的embedding空间上通过最近邻查询这些embeddings来做出推荐。也就是说，给定一个query item q，我们可以推荐那些关于query item的embedding的embedding是K个最近邻。ANN可以通过locality sensitive hashing有效获得。在hash function被计算后，items的检索可以使用一个two-level检索过程，基于Weak AND操作符来实现。假设PingSage model通过离线训练给出，所有node embeddings会通过MapReduce进行计算，并在database中保存，有效的最近邻lookup operation可以确保系统以一个在线的方式提供服务。

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

standford在《Inductive Representation Learning on Large Graphs》中提出了GraphSage：

介绍

在large graphs中的节点（nodes）的低维vector embedding，已经被证明对于许多预估和图分析任务来说作为feature inputs是很有用的。在node embedding方法的基本思想是：使用降维技术将关于一个node的图邻居的高维信息蒸馏（distill）到一个dense vector embedding中。这些node embeddings可以接着被feed到下游的机器学习系统中，并用于分类、聚类、连接预测等任务中。

然而，之前的工作主要关注于来自单个fixed graph的embedding nodes，许多真实应用，会对于未知nodes、或者全新的subgraphs也能快速生成embeddings。这些归纳能力对于高吞吐、生产环境机器学习系统来说很重要，它会在演进的图上操作、并能总是遇到未知的nodes（例如：在Reddit上的posts、在Youtube上的users和videos）。对于生成node embeddings的归纳法来说，会面临着在具有相同形式features的各种图上的泛化（generalization）：例如：来自一个模式生物的在蛋白质的相互作用图上，训练一个embedding genreator，接着可以很容易使用训练好的模型，来对于新的生物体（organisms）收集来的数据生成node embeddings。

对比起直推式setting（transductive setting），inductive node embedding问题是特别难的，因为泛化到unseen nodes需要将新观察到的subgraphs“安排（aligning）”到已经通过算法最优化好的node embeddings中。一个inductive framework必须学习去认识一个node的邻居的结构化属性，它能表明节点的在图中的局部角色（local role），以及全局位置（global position）。

对于生成node embeddings的大多数已经存在的方法，是天然直推式的（transductive）。绝大多数方法是直接使用MF-based目标来最优化每个节点的embeddings，不会天然生成unseen data，因为他们会在一个单一fixed graph上做出预估。这些方法可以在一个inductive setting环境中被修改来执行，但这些修改版本的计算开销都很大，需要在做出新预估之前额外迭代好几轮gradient descent。一些最近的方法在图结构上使用卷积操作（convolutional operators）来进行学习，能提供一个embedding方法。因此，GCNs（graph convolutional networks）已经被成功应用到在fixed graph的直推式setting（transductive setting）上。而在本工作中，我们同时将GCNs扩展到归纳式无监督学习（inductive unsupervised learning）任务上，并提出一个framework来生成GCN方法，它使用trainable aggregation function（而不是简单的convolutions）.

我们提出了一个关于inductive node embedding的general framework，称为GraphSage（抽样和聚合：SAmple and aggreGatE）。不同于基于MF的embedding方法，我们会利用node features（例如：文本属性、node profile信息、node degrees）来学习一个embedding function，它会泛化到unseen nodes上。通过在学习算法中包含node features，我们会同时学习每个node邻居的拓朴结构，以及在邻居上的node features分布。当我们关注feature-rich graphs（例如：具有文本属性的引文数据、功能/分子标记的生物学数据），我们的方法也会利用出现在所有graphs（例如：node degrees）中的结构化features，因而，我们的算法也会被应用于没有node features的graphs中。

不同于为每个node训练一个不同的embedding vector的方式，我们的方法会训练一个关于aggregator functions的集合，它们会从一个node的局部邻居（local neighborhood）（图1）中学习到聚合特征信息（aggregates feature information）。每个aggregator function会从一个远离一个给定结点的不同跳数、搜索深度的信息进行聚合。在测试（test）或推断（inference time）时，我们使用已训练系统来为整个unseen nodes通过使用学到的aggregation functions来生成embeddings。根据之前在node embeddings生成方面的工作，我们设计了一个无监督loss function，它允许GraphSage使用task-specific supervision来进行训练。我们也表明了：GraphSage可以以一个完全监督的方式进行训练。

图1 GraphSAGE抽样和聚合方法的可视化演示

我们会在三个node分类benchmarks上评估我们的算法，它们会测试GraphSAGE的能力来在unseen data上生成有用的embeddings。我们会使用两个演进的document graphs，它们基于citation data和Reddit post data（分别预估paper和post类目），以及基于一个一个蛋白质的相互作用的multi-graph生成实验。使用这些benchmarks，我们展示了我们的方法能够有效生成unseen nodes的表示，效果对比baseline有一个大的提升。。。

2.相关工作

略

3.GraphSAGE

我们方法的关键思想是，我们会学习如何从一个节点的局部节点（local neighborhood）中聚合特征信息（例如：邻近节点的degrees和文本属性）。我们首先描述了GraphSAGE的embedding生成算法（例如：forward propagation），它会假设：为GraphSAGE模型参数已经被学习的节点生成embeddings。我们接着描述：GraphSAGE模型参数可以使用标准的SGD和BP技术被学到。

3.1 Embedding生成算法（例如：forward propagation）

在本节中，我们描述了embedding生成，或者forward propagation算法（算法1），它会假设：模型已经被训练过，并且参数是固定的。特别的，我们会假设：我们已经学到了关于K个aggregator functions的参数（表示为：\(AGGREGATE_k, \forall k \in \lbrace 1,\cdots,K\rbrace\)），它会被用于在模型的不同layers间、或者“搜索深度”上传播信息。第3.2节描述了我们是如何训练这些参数的。

• $G(V, E)$：图
• $\lbrace x_v, \forall v \in V \rbrace$：输入特征
• K：深度
• $W^k, \forall k \in \lbrace 1, \cdots, K \rbrace$： 权重矩阵
• $\sigma$：非线性激活
• $AGGREGATE_k, \forall k \in \lbrace 1,\cdots, K \rbrace$：可微聚合函数
• $N: v \rightarrow 2^v$：邻居函数（neighborhood function）

算法1

算法1的背后意图是：

• 在每个迭代中，或者搜索深度上，节点会聚合来自它们的local neighbors的信息；
• 并且随着该过程迭代，nodes随着graph的更进一步触达逐渐获得越来越多的信息。

算法1描述了case中的embedding生成过程，其中：

• \(G = (V, \epsilon)\)：表示整个graph
• \(\lbrace x_v, \forall v \in V \rbrace\)：表示graph中的所有node的input features
• K：表示深度
• \(W^k, \forall \lbrace 1,\cdots,K \rbrace\)：表示weight matrics

我们在下面描述了如何生成该过程到minibatch setting中。算法1的外循环中的每个step过程如下，其中：

• k：表示在外循环（或者搜索深度）中的当前step
• \(h^k\)：表示在该step中一个node的representation

首先，每个node \(v \in V\)会将在它的立即邻居（immediate neighborhood）\(\lbrace h_u^{k-1}, \forall u \in N(v) \rbrace\)上的nodes 的representations聚合到单个vector \(h_{N(v)}^{k-1}\)中。注意，该聚合step依赖于：在outer loop的前一迭代生成的representations，并且k=0（”bad case”）representations会被定义成input node features。

接着，在聚合了邻近的feature vectors之后，GraphSAGE会将该node的当前representation \(h_v^{k-1}\)与聚合的邻近vector \(h_{N(v)}^{k-1}\)进行拼接（concatenates），该concatenated vector会通过一个具有非线性activation function \(\sigma\)的fully connected layer进行feed，它会将representations转换成在算法的下一step进行使用（例如：\(h_v^k, \forall v \in V\)）。neighbor representations的聚合可以通过多个aggregator结构来完成，并且我们会在第3.3节中讨论不同的结构选择。

为了扩展算法1到minibatch setting中，给定一个关于input nodes的集合，我们首先对所需要的neighborhood sets（到深度K）进行forward sample，接着我们在inner loop进行运行，通过替代迭代所有nodes，我们只会计算：必须满足在每个depth上的递归的representations。

与 Weisfeiler-Lehman Isomorphism Test的关系

GraphSAGE算法在概念上受testing graph isomorphism的经典算法的启发。在算法1中，我们：

• (i) 设置\(K=\| V \|\)
• (ii) 设置weight矩阵作为identity
• (iii) 使用一个合适的hash function作为一个aggregator（无非线性），

接着算法1是一个关于WL isomorphism test的实例，也被称为“naive vertex refinement”。如果由算法1输出的representations \(\lbrace z_v, \forall v \in V \rbrace\)。该test在一些情况下会失败，但是对于许多图是合法的。GraphSAGE是对WL test的连续近似，其中，我们将hash function替代成trainable neural network aggregators。当然，我们使用GraphSAGE来生成有用的节点表示（node representations）——而非test graph isomorphism。然而，在GraphSAGE和经典的WL test间的连接，为我们的算法设计提供了理论context来学习关于节点邻居的拓朴结构。

Neighborhood定义

在本工作中，我们会均匀地抽样一个关于节点邻居的fixed-size集合，而非使用算法1中完整的邻居集合，是便保持每个batch的计算开销是固定的。也就是说，使用过载的概念，在算法1中，我们将\(N(v)\)定义为一个从集合\(\lbrace u \in V:(u,v) \in \epsilon \rbrace\)中fixed-size的均匀抽取，在每个迭代k上我们会从不同的均匀样本中进行抽样。如果没有这种抽样，单个batch的内存和runtime会不可预知，最坏情况下为\(O(\| V \|)\)。作为对比，对于GraphSAGE的每个batch space和时间复杂度被固定在\(O(\prod_{i=1}^K S_i)\)，其中\(S_i, i \in \lbrace \cdots \rbrace\)，K是user-specified常数。实际来说，我们发现我们的方法可以达到具有K=2的高效果，并且\(S_1 \cdot S_2 \leq 500\)。

3.2 学习GraphSAGE的参数

为了以一个完全无监督setting方式学习有用的、可预测的表示（representations），我们会通过SGD使用一个graph-based loss function给output representations \(z_u, \forall u \in V\)，并且调节weight矩阵 \(W^k, \forall k \in \lbrace 1,\cdots, K \rbrace\)， 以及得到的aggregator functions的参数。graph-based loss function会鼓励邻近节点具有相似的表示（representations），从而强制分离的nodes的representations具有高度的不同：

\[J_G(z_u) = - log(\sigma(z_u^T z_v)) - Q \cdot E_{v_n \sim P_n(v)} log(\sigma(- z_u^T z_{v_n}))\]

…(1)

其中:

• v：是一个node，它会与u在一个fixed-length的random walk中共现
• \(\sigma\)：是sigmoid function
• \(P_n\)：是一个negative sampling分布
• Q：定义了negative samples的数目

重要的是，不同于之前的embedding方法为每个node（通过一个embedding look-up）训练一个唯一的embedding，我们feed到该loss function的representations \(z_u\)会由在一个node的局部邻居（local neighborhood）中包含的features来生成。

该无监督setting会模拟以下情况：其中node features会提供到下游的机器学习应用，或者作为一个服务 或者 在一个静态仓库中。在本case中，其中representations只会在一个指定的下游任务中，无监督loss（等式1）可以简单地被一个task-specific目标（比如：cross-entropy loss）替换。

3.3 Aggregator结构

在N-D lattices（例如：句子、图片、或3D空间），一个node的邻居没有自然序：在算法1的aggregator function必须在一个关于vectors的无序集合上操作。理由的，一个aggregator function必须是对称的（例如：它的inputs排列是不变的），同时是可训练的，并且保持一个高度表达的能力。aggregation function的对称性确保了我们的neural network model是可训练的，并且可以被用于随意顺序的节点邻居的feature sets上。我们会检查三个候选aggregator function：

Mean aggregator

我们的第一个候选 aggregator function是mean aggregator，其中：我们简单地对在\(\lbrace h_u^{k-1}, \forall u \in N(v) \rbrace\)中的vectors做elementwise平均。该mean aggregator接近等于在transductive GCN network中的convolutional propagation rule。特别的，我们可以通过在算法1中的第4和第5行使用下面进行替换，派生一个关于GCN方法的inductive variant：

\[h_v^k \leftarrow \sigma(W \cdot MEAN(\lbrace h_v^{k-1} \rbrace \cup \lbrace h_u^{k-1}, \forall u \in N(v) \rbrace)\]

…(2)

我们将该修改版称为mean-based aggregator convolutional，因为它是一个关于一个localized spectral convolution的不平滑的线性近似。在该convolutional aggregator和其它aggregators间的一个重要区别是：在算法1的第5行，不会执行concatenation操作。例如：convolutional aggregator不会将node的前一layer representation \(h_v^{k-1}\)与he aggregated neighborhood vector \(h_{N(v)}^k\)进行concatenate。该concatenate可以被看成是关于一个关于在不同“search depths”或GraphSAGE算法中“layers”间的”skip connection”的简单形式，并且它会产生在效果上的巨大收益。

LSTM aggregator

我们也会检查一个更复杂的基于一个LSTM结构的aggregator。对比起mean aggregator，LSTMs的优点是：具有更强的表达能力。然而，需要注意的是，LSTMs没有天然的对称性（例如：它们没有排列不变性），因为他们以序列方式处理它们的inputs。我们采用LSTMs用来操作一个无序集合，通过简单地将LSTMs应用到一个关于节点邻居的随机排列上。

Pooling aggregator

该aggregator具有对称性，同时可训练。在pooling方法中，每个邻居的vector会独立地通过一个fully-connected neural network进行feed；根据该转换，一个elementwise max-pooling操作会被应用来对跨邻居集合的信息进行聚合：

\[AGGREGATE_k^{pool} = max(\lbrace \sigma(W_{pool} h_{u_i}^k + b), \forall u_i \in N(v) \rbrace)\]

…(3)

其中：

• max表示element-wise max操作符
• \(\sigma\)是一个非线性activation function

原则上，该函数会在max pooling之前被使用，可以作为一个随意的deep multi-layer perceptron，但我们关注于简单的single layer结构。该方法受最近研究【29】的一些启发。直觉上，multi-layer perceptron可以被认为是：作为在邻居集合中的每个节点表示的feature计算的一个函数集合，该模型可以有效地捕获邻居集合的不同方面。注意，原则上，任务对称vector function可以被用来替代max operator（例如：一个element-wise mean）。我们发现：关于developments test在max-pooling和mean-pooling间没有大差别，因此后续主要关注max-pooling。

实验

略

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

facebook在《MEMORY NETWORKS》中提出了memory networks，在另一文《End-To-End Memory Networks》提出了end2end的实现：

摘要

我们会介绍一种使用recurrent attention model的neural network，它构建在一个可能很大的外部memory之上。该架构与Memory network的形式一样，但与其中的model不同的是：它的训练是end-to-end的，因而在训练期间几乎是无监督学习，这使得它很容易应用到实际环境中。它可以看成是关于RNNsearch[2]的一个扩展：其中在执行每次output symbol时会执行多个计算steps（hops）。该模型的灵活性允许我们将它应用到像QA等不同的任务以及语言建模上。对比起之前的Memory Networks的研究，它几乎是无监督的。我们在Penn TreeBank和Text8 datasets上验证了我们的方法要好于RNNs和LSTMs。

1.介绍

在AI 研究领域，在QA或补全任务上，构建模型会涉及多个计算步骤，模型可以描述序列数据中的long-term dependencies。

最近的一些工作，在建模时会使用显式存储和attention；维持这样的一个storeage对于解决这样的挑战提供了一种方法。在[23]中，存储会通过一个continuous representation给出；从该存储进行读取和写入，可以通过neural networks的actions进行建模。

在本工作中，我们提出了一种新的RNN结构，其中：在输出一个symbol之前，recurrence会从一个可能很大的external memory中读取多次。我们的模型可以被看成是在[23]中的Memory Network的一个continuous form。本工作中的模型通过BP训练并不容易，需要在该network的每个layer上进行监督。模型的连续性意味着：它可以从input-output pairs通过end-to-end的方式进行训练，因此很容易应用到许多任务上，例如：语言建模或者真实的QA任务。我们的模型可以看成是RNNsearch[2]的一个版本，它在每个output symbol上具有多个计算步骤。我们会通过实验展示：在long-term memory上的多跳对于我们的模型的效果来说很重要，训练memory representation可以以可扩展的方式进行集成到end-to-end neural network model上。

2.方法

我们的模型会采用：

• 一个关于inputs \(x_1, \cdots, x_n\)的离散集合，它们会被存储到memory中
• 一个query q
• 输出一个answer a

\(x_i, q, a\)的每一个都包含了来自具有V个词的字典的symbols。该模型会将所有x写到memory中，直到达到一个确定的buffer size，接着我们会为x和q寻找一个连续的representation。这会允许在训练期间，error signal的BP通过多个memory accesses回到input。

2.1 Single Layer

我们先在single layer的case中开始描述我们的模型，它会实现一个单个memory hop操作。后续我们会展示可以对它进行stack来给出在memory上的多跳。

Input memory representation

假设我们给定一个input set \(x_1, \cdots, x_i\)被存到memory中。\(\lbrace x_i \rbrace\)的整个集合会被转到d维memory vectors \(\lbrace m_i \rbrace\)中，它通过在一个连续空间上嵌入每个\(x_i\)计算得到，在最简单的case中，使用一个embedding matrix A（其中：size=\(d \times V\)）。query q也会被嵌入来获得一个internal state u。在embedding space中，我们会计算在u和每个memory \(m_i\)间的match程度，通过以下公式对内积采用softmax得到：

\[p_i = Softmax(u^T m_i)\]

…(1)

其中，\(Softmax(z_i) = \frac{ e^{z_i} } {\sum_j e^{z_j}}\)。在该方式中，p是在inputs上的一个概率向量（probability vector）。

Output memory representation

每个\(x_i\)都具有一个相应的output vector \(c_i\)。memory o的response vector是一个在transformed input \(c_i\)与来自input的probability vector进行加权求和:

\[o = \sum_i p_i c_i\]

…(2)

由于从input到output的函数是smooth的，我们可以轻易地计算gradients以及BP。其它最近提出的memory或attention形式也采用该方法【2】【8】【9】。

生成最终的prediction

在single layer case中，output vector o和input embedding u接着通过一个最终的weight matrix W（size为\(V \times d\)）和一个softmax来生成predicted label：

\[\hat{a} = Softmax(W(o+u))\]

…(3)

整体模型如图1(a)所示。在训练期间，所有三个embedding matrics A, B, C，以及W都通过最小化\(\hat{a}\)和 true label a间的一个标准的cross-entropy loss进行联合学习。训练会使用SGD进行执行。

图1

2.2 Multiple Layers

我们现在扩展我们的模型来处理K跳的操作。memory layers会以如下方式进行stack：

• 在第一个之上的layers的input，是从layer k的output \(o^k\)和input \(u^k\)的求和（后续会有不同组合）：

\[u^{k+1} = u^k + o^k\]

…(4)

• 每个layer会具有它自己的embedding matrics \(A^k, C^k\)，用于嵌入到inputs \(\lbrace x_i \rbrace\)中。然而，如下所示，他们会被限制以便减轻训练、减少参数数目.

• 在network的顶层，W的input也会将top memory layer的input和output进行组合：

\[\hat{a} = Softmax(W u^{K+1}) = Softmax(W(o^K + u^K))\]

我们探索了在模型中两种类型的weight tying机制：

• 1.Adjacent：一个layer的output embedding是下一个的input embedding，例如：\(A^{k+1} = C^k\)。我们也会限制：a) answer prediction matrix会与最终的output embedding相似，例如：\(W^T = C^K\)， b) question embedding会与第一层的input embedding相匹配，例如：\(B = A^1\)
• 2.Layer-wise（RNN-like）：input和output embeddings对于不同的layers是相同的，例如：\(A^1 = A^2 = \cdots = A^K\)以及\(C^1 = C^2 = \cdots = C^K\)。我们已经发现：添加一个线性映射H到在hops间的u的update上是有用的；也就是说：\(u^{k+1} = H u^k + o^k\)。该mapping会随着剩余参数学习，并在我们的实验上用于layer-wise weight tying。

图1(b)展示了一个3-layer版本。总体上，它与[23]中的Memory Network相似，除了每一layer中的hard max操作已经使用了一个来自softmax的continuous weighting替换外。

注意，如果我们使用layer-wise weight tying scheme，我们的模型可以被转成一个传统的RNN，其中我们会将RNN的outputs分割成internal和external outputs。触发一个internal output可以与考虑一个memory相对应，触发一个external output对应于预测一个label。从RNN的角度，图1(b)和等式(4)的u是一个hidden state，该模型会使用A生成一个internal output p（图1(a)中的attention weights）。该模型接着会使用C来吸收p，并更新hidden state等。这里，与一个标准RNN不同的是，我们会在K hops期间，显式的基于在memory中储存的outputs作为条件，我们会采用soft的方式来保存这些outputs，而非对它们采样。这样，我们的模型会在生成一个output之前做出一些计算step，这意味着被“外部世界”见过。

其它

略

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