华为在《PAL: a position-bias aware learning framework for CTR prediction in live recommender systems》提出了一种解决position-bias方法。

摘要

在推荐系统中精准预测CTR很重要。CTR模型通常基于来自traffic logs收集得到的feedback训练得到。然而，在user feedback中存在position bias，因为用户在一个item上的点击(clicks)不仅仅只因为用户喜欢这个item，还有可能是因为它具有一个较好的position。解决该问题的一种方式是：在训练数据中将position建模成一个feature。由于很简单，这种方法在工作界被广泛应用。然而，使用不同的default position值可能会导型完全不同的推荐结果。因些，该方法会导致次优(sub-optimal)的线上效果。为了解决该问题，在该paper中，我们提出了一种Position Aware Learning framework（PAL）来解决该问题。它可以建模在offline training中的position-bias，并在online inference时不使用position information。我们在一个三周的AB test上进行实验，结果表明，PAL的效果在CTR和CVR（转化率ConVersion Rate）指标上要比baseline好3%-35%。

1.介绍

实际生产环境中的推荐系统包含两个过程：offline training和online inference，如图2所示。在offline training中，会基于从traffic logs中收集到的user-item interaction信息训练一个CTR预估模型。在online inference中，训练好的模型会部署到真实线上来做出预测。

图2 不同position上的CTR

有个问题是：user-item interaction是受展示该item的positions影响的。在[14]中，CTR会随着display position而快速下降。相似的，我们也在华为maintream APP store上观察到了这样的现象。如图1所示，不管是整体的App Store (图1(a))，或是单个特定App（图1(b)），我们可以观察到：normalized CTR会随着position显著下降。

图1 生成推荐的workflow

这样的观察表明，用户点击某个item可能不仅仅是因为喜欢这个item，还有可能是因为在一个好的position上。因此，从traffic logs中收集得到的training data包含了positional bias。我们将该现象称为“position-bias”。作为CTR信号的一个重要因子，在offline training中将position-bias建模到CTR预测模型中是很必要的。

尽管提出了许多click models来建模training data中的position-bias【1-3】，在现实问题中（在online inference中position信息是不提供的）这样的研究很有限。一个实用（practical）的方法是逆倾向加权（inverse propensity weighting）【15】。在该方法中，在position信息使用一个用户定义的转换，接着该转换后的值固定。然而，如【10】所述，对于position信息很难设计一个好的转换，这会产生比自动学到的转换更差的效果。因此，【10】的作者提出在训练数据中将position建模成一个feature，这种方法在工业界广泛使用。特别的，在online inference中使用一个default position value来预测CTR，因为actual position information在那时并没提供。不幸的是，使用不同的default position values可能会导致完全不同的推荐效果，这会导致生成一个次优的online performance。

在本paper中，我们提出了PAL来建模position-bias。PAL的思想基于以下假设：一个item被用户点击基于两个因素（假设item被user看到）：

• a) item被用户看到的概率
• b) 用户在该item上点击的概率

上面的每个factor在PAL中会被建模块“as a module”，这两个modules的outputs是一个item被用户点击的概率。如果两个modules单独进行optimzied，它会导致整个系统达到一个次优的状态，因为两个modules的training objectves间不一致性（inconsistency），正如[18]中所述。为了避免这样的限制，并生成更好的CTR预测效果，PAL中的两个modules会同时进行jointly optimized。一旦这两个modules在offline training下训练完全成，第二个module可以部署到online inference上来预测CTR。

2.方法

2.1 概念

我们假设：offline的点击数据集为 ：\(S = \lbrace (x_i, pos_i \rightarrow y_i) \rbrace_{i=1}^N\)

其中：

• N：是总样本数
• \(x_i\)：是样本i的feature vector，它包含了：user profile, item features和context信息
• \(pos_i\)：是样本i的position信息
• \(y_i\)：是user feedback（如果user在该item进行点击，则\(y_i=1\)；否则\(y_i=0\)）

我们会使用x，pos，和y来分别表示feature vector、position信息和label。

2.2 Preliminary

有两种方法对在offline training中的position-bias进行建模，称为“as a feature”和”as a module”。

As a feature

该方法会将position信息建模成一个feature。在offline training中，CTR模型的input feature vector是x和pos的concatenation，例如：\(\hat{x} = [x, pos]\)。然后基于该concatenated feature vector训练一个CTR预测模型。

由于position信息被建模成offline training中的一个feature，在online inference中也应包含一个表示“position”的feature，如图3的右侧所示。然而当执行online inference时，position信息是不提供的。一种解决该问题(在inference时缺失该position)的方法是：为每个position，按top-most position到bottom-most position顺序，判断最适合的item。可以分析得到，brute-force方法具有\(O(l n T)\)的时间复杂度（其中：l是ranking list的长度，n是candidate items的数目，T是inference的latency），它对于一个低延迟的在线环境来说是不可接受的。

图3 PAL framework vs. BASE

为了减短延时，可选择一种【10】中描述的具有O(nT)复杂度的方法，它会为所有items选择一个position来作为position feature的值。然而，不同的position value会产生完全不同的推荐结果。因此，我们需要寻找一个合适的position值来达到好的online performance。这里有两种方法来比较使用不同position values进行inference的效果： online experiment和offline evaluation。前者很好，但代价高。因此，我们必须采用offline evaluation来选择合适的position value。另外，不管是使用online experiment或offline evaluation来选择position value，它都不具备良好的泛化特性，因为对于某一个应用场景的online inferenece的position value并不适用于另一个场景。

As a module

为了解决将position信息作为一个feature的上述缺陷，我们提出了一个新的框架来将position信息作为一个module，因此，我们可以在offline training中建模position-bias，并在没有position信息的online inferenece中使用。

3.PAL Framework

我们的framework受以下假设的启发：一个item被一个用户点击，只因为被该用户看到了。更特别的，给定item被用户看到，那么我们认为用户点击一个item的概率依赖于两个因素：

• a) item被用户看到的概率
• b) 用户在该item上被点击的概率

如等式(1)所示：

…(1)

如果我们进一步假设（注意：此处为PAL的关键假设）：

• a) 一个item已经被看到(seen)的概率只与该相关position被观察到的概率相关
• b) 一个item被点击(click)的概率与该position是否被看到(seen)相互独立

那么，等式(1)被简化成等式(2) ：

…(2)

如图3左侧所示，我们的PAL框架基于等式(2)设计，并包含了两个modules：

• ProbSeen：第一个module会对概率\(p(seen \mid pos)\)建模，它通过图3中的”ProbSeen”进行表示，将position信息pos作为input
• pCTR：第二个module会对概率\(p(y=1 \mid x, seen)\)进行建模，它表示了图3中的”pCTR”，表示该模型predicted CTR。它的输入是training data中的feature vector x。

任意CTR预测模型（比如：linear models和deep learning models）都可以应用于这两个modules上。

接着，学到的CTR被表示成图3中的”bCTR”，它会将在offline training中的position bias认为是这两个modules的输出的乘积。如【18】所示，如果两个modules被单独进行优化，不同的training objectives间的不一致（inconsistency）会导致整体系统达到一个次优（sub-optimal）的状态。为了避免这样的次优（sub-optimal）效果，我们在该framework中会对这两个modules进行jointly和simultaneously训练。更特别的，PAL的loss function被定义成：

…(3)

其中，\(\theta_{ps}\)和\(\theta_{pCTR}\)分别是ProbSeen module和pCTR module的参数，其中\(l(\cdot)\)是cross-entropy loss function。pCTR module，被用于online inference过程，并不会被直接最优化。实际上，当label和predicted bCTR间的logloss最小化时，ProbSeen和pCTR modules的参数可以如等式(4)和等式(5)通过SGD进行最优化，以便position-bias和user preference的影响会分别被隐式学到。

…(4)

…(5)

在offline training过程中，与[5,13,16]相似，early stop策略被用在训练过程中来获得well-trained model。一旦PAL被well-trained，module pCTR可以被部署到线上进行CTR inference。很容易观察到：position在PAL中的pCTR module并不需要，因此，我们不需要像“as a feature”那样在online inference时分配position values。

3.在线实验

在真实推荐系统中设计在线实验来验证PAL的效果。特别的，我们使用一个三周的AB test来验证PAL vs. “as a feature”的baseline方式。AB test在Company X的app Store的游戏中心的游戏推荐场景进行。

3.1 Datasets

在CompanyX的AppStore生产环境中，我们从traffic logs中抽样了10亿样本作为offline training dataset。为了更新我们的模型，training dataset以一个sliding time-window style的方式进行refresh。training的features包含了app features（例如：app id, category 等）、user features（比如：downloaded、click history等）、context features（例如：操作时间等）。

3.2 Baseline

baseline framework指的是“as a feature”策略。实际上，该baseline采用的是在[10]中的方法。正如所声明的，我们需要选择一个合适的position value作为online inference。然而，由于资源有限，对于使用所有可能positions来评估baseline framework是不可能的。因此，我们会选择合适的positions来进行offline experiment。

Settings。为了选择合适的position(s)，我们收集了两个场景的数据集(dataset 1和dataset 2)。test dataset通过next day的traffic logs中收集得到。我们在test dataset中使用不同的position values，范围从position 1到position 10. 与[5,11,13,16]相似，采用AUC和LogLoss来作为metrics对离线效果进行评估。

结果和分析。offline实验的结果如图5所示，其中Base_pk是具有position value k的baseline framework，它会为test data中的所有items分配该值。PAL框架所使用的test data没有position values。从图5看到，分配不同position values，AUC和LogLoss值在test data上变化很大。另外，BASE_p9可以达到最高的AUC，BASE_p5可以达到最低的LogLoss，Base_p1可以在AUC和LogLoss上同时达到最差的效果。我们选择最好的（BASE_p5和BASE_p9）以及最差的（BASE_p1）这两个作为baselines来做与PAL做online ABtest。值得注意的是，PAL在offline experiment中对于AUC或LogLoss均不会达到最好的效果。

图5 offline实验结果

3.3 AB test

Settings。对于control group，2%的用户被随机选中，并使用baseline framework生成的推荐结果进行呈现。对于experimental group，2%的users使用PAL生成的推荐结果进行呈现。在baseline和PAL中使用的模型是DeepFM，并使用相同的网络结构和相同的特征集。由于资源限制，我们不会在同一时间部署三个baseline（BASE_p1, BASE_p5和BASE_p9）。相反的，他们只会一个接一个地部署，每个轮流一周时间，来对比PAL。更特别的，我们会在每周分别对比PAL vs. BASE_p1､ PAL vs. BASE_p5､PAL vs. BASE_p9.

Metrics

我们采用两种metrics来对比PAL和baselines的在线效果，称为：

• 实际CTR（realistic CTR）：\(rCTR = \frac{\#downloads}{\#impressions}\)
• 实际转化率（realistic Conversion Rate）：\(rCVR = \frac{\#downloads}{\#users}\)

其中：#downloads, #impressions 以及 #users分别表示天级别的下载数、曝光数、访问用户数。

这与predicted CTR不同（例如图3中的“pCTR”），”rCTR”是我们在线观察到的realistic CTR。

结果

图4表示了online experiements的结果。蓝色和红色的histograms展示了PAL对比baseline在rCTR和rCVR上的提升。首先，rCTR和rCVR的metrics在整个三周的AB test上均获得提升，验证了PAL要比baselines要好。第二，我们也观察到，首周中（baseline使用BASE_p1）rCTR和rCVR（图4虚线）的平均提升是最高的，第二周最低（baseline使用BASE_p5）。该现象告诉我们，baseline的效果对于分配不同的position values区别很大，因为推荐可能与所分配的不同的position values完全不同。

图4 Online AB test的结果

3.4 在线分析

为了完全理解AB test，并验证我们提出的框架在online inference上消除，我们分析了PAL和baselines的推荐结果。

第一个实验是为了对比与ground truth ranking之间的ranking distance。我们将ground truth ranking定义成一个关于items的list，它通过\(f(rCTR, bid)\)的值降序排列。会采用Spearman’s Footrule来measure在两个rankings中的位移 (displacement)，它被广泛用于measure两个rankings间的距离。我们定义了【ground truth ranking】与【由PAL或baselines生成的ranking \(\delta_M\)】在top-L上的距离，如下所示：

…(6)

其中：

• u是在user group U中的一个具有popularity \(\mid U \mid\)的user
• \(\delta_{M,u}\)是由model M为user u生成的推荐列表
• \(\delta_{M,u}(i)\)：在ground truth ranking中的第i个item在推荐\(\delta_{M,u}\)中的position 处

我们对比了\(M \in \lbrace PAL, BASE_{p1}, BASE_{p5}, BASE_{p9} \rbrace\)以及\(L \in [1, 20]\)的\(D(\delta_M, L)\)，如图6(a)所示，其中，线色实线是PAL的结果，其它线是baselines的结果。我们可以看到，PAL会生成对比ground truth ranking最短的距离，这意味着由PAL生成的推荐与我们在线观察到的real ranking最相似。这通过PAL在offline training中使用position-bias建模、并在online inference中消除position-bias来完成，这可以解释，PAL的效果要好于baselines。

图6 online分析

第二个实验对比了PAL和baselines间的个性化（personalization）。Personalization@L 可以mearure 在一个跨不同users的ranking中top-L的inter-user diversity（推荐结果的一个重要因子）。Personalization@L由等式(7)定义：

…(7)

其中，\(\mid U \mid\)是user group U的size，\(q_{ab}(L)\)是user a和user b在top-L中公共items的数目。Personlization@L 越高表明，跨不同users在top-L positions上更diverse的推荐items。

我们分别计算了关于PAL 以及baselines的personalization@L。图6(b)表明，在top-5(L=5）、top-10(L=10)以及top-20(L=20)上不同frameworks关于推荐的的personalization。我们可以看到在推荐中由PAL生成的的top items会比baselines生成的更多样一些。由于PAL能在消除position-bias影响后更好地捕获到不同users的特定兴趣、以及根据用户个性化兴趣生成的推荐items。

参考

• 1.https://www.researchgate.net/publication/335771749_PAL_a_position-bias_aware_learning_framework_for_CTR_prediction_in_live_recommender_systems

microsoft在《Modeling and Simultaneously Removing Bias via Adversarial Neural Networks》paper中提出了一种使用adversarial network解决position bias的方法：

介绍

在online广告系统中，需要对给定一个query估计一个ad的ctr，或PClick。通过结合该PClick估计以及一个广告主的bid，我们可以运行一个auction来决定在一个页面上的哪个位置放置ads。这些ad的曝光(impressions)以及他们相应的features被用来训练新的PClick模型。这里，在线广告会存在feedback loop问题，其中：之前看到过的ads会占据着training set，在页面上越高位置的ads会由大部分正样本(clicks)组成。该bias使得在所有ads、queries以及positions（或D）上估计一个好的PClick很难，因为features的比例过高（overrepresentation）与高CTR占据feature space有关。

我们假设：在一个page上的position（例如：mainline、sidebar或bottom）可以概括PClick bias的一大部分。实际上，我们的目标是学习这样的一个PClick表示：它对于一个ad展示的position是不变的（invariant），也就是说，所有potential ads对于给定页面上的一个位置，仍然会是单一的相对排序。尽管我们可以很容易地使用一个linear function来强制在position features，但其它features的intrinsic bias相对于position来说更难被移除。

为了学习这种位置不变特性（position invariant feature）的PClick模型，我们使用ANNs（adversarial neural networks）。ANNs会使用competing loss functions来进行建模，它在tandem（[6]）下进行最优化，最近的工作[1,9]有使用它们进隐藏或加密数据。我们的ANN representation包括了4个networks：Base、Prediction、Bias、以及Bypass Networks（图1）。最终在线使用的PClick prediction是来自Bypass和Prediction networks的outputs的一个线性组合的结果，它用来预测\(\hat{y}\)。然而，在训练这些predictors期间，会使用Bias network adversary(对手)进行竞争。该Bias network只使用由Base network生成的low rank vector \(Z_A\)，尝试对position做出预测。相应的，Prediction、Bypass和Base networks会最优化一个augmented loss function，它会对Bias network进行惩罚。结果是，在传给Prediction network之前，vector \(Z_A\)与position无关。

克服position/display biases的另一个方法是：使用multi-armed bandit方法来帮助生成更少的无偏训练数据以及covariate shift。然而，两者都需要来自一个exploration set中的大量样本来生成更好的估计。实际上，很难获得足够量的exploration data，因为它通常会极大影响收益。我们的ANN方法无需exploration，可以应用于已存在的dataset。

为了测试模型的有效性，我们会在真实数据集和伪造实验上进行评估。我们会生成两个伪造数据集集合，并模拟online ads系统的feedback loop，并展示systematic和user position biases可以通过ANN进行处理，并生成更精准的估计。

我们也展示了：当在CTR上进行最优化时，在模型中移除bias间的一个tradeoff。我们展示了：在评估时通过使用该tradeoff，ANN架构可以在无偏数据集上恢复一个更精准的估计。

我们的贡献如下：

• 一个新的ANN表示，用于移除在线广告的position bias
• 指定一个不同的squard covariance loss，在bias组件上进行对抗最优化（adversarial optimization）
• 引入一个bypass结构来独立和线性建模position
• 详细的人工数据生成评估，演示了在在线广告系统中的feedback问题

2.在付费搜索中的position bias

ML应用中的feedback问题是常见的。为了演示它，我们主要关注付费广告搜索中的CTR或PClick问题。一个标准的Ad selection stack包括了：

• 选择系统（selection system）：selection system会决定ads的一个子集来传给model
• 模型阶段（model phase）：model会尝试估计在分布D上的完全概率密度函数，它是整个Ads、Queries、Positions space。特别的，我们会估计\(P(Click \mid Ad, Queries, Positions\ space)\) 。
• 竞价阶段（auction phase）[7]：在auction阶段，广告主会对关键词竞价（bid）并对queries进行匹配。Ads和他们的positions会最终由PClicks和广告主bids所选择。我们主要关注model phase或PClick model。

出于许多原因，很难估计D。首先，一个在线Ads系统会从D中抽样一个小量的有偏部分。机器学习模型会使用许多features跨<Ad,Query>上进行估计PClick。许多丰富的features是counting features，它会会跨<Ad,QUERY>的过往进行统计信息（比如：该Ad/Query组合在过去的点击百分比）。Query Ad pairs经常出现在Ad stack中，它们具有丰富的informative feature信息：然而，从未见过或者很少见过的Query Ad pairs并没有这些丰富的信息。因而，对于一个模型来说，保证一个Query Ad pair在online之前没有展示过很难进行ranking，这会导致feedback loop。

第二，一个feedback loop会在training data和PClick model间形成。新的training data或ads会由之前的model的ranking顺序展示，一个新的PClick model会从之前的training data中生成。因而，产生的Feedback Loop(FL)会偏向于过往的模型和训练数据。

Position CTR，\(P(y \mid Position = p)\)是一个ad在一个页面上的给定位置p的点击概率。这可以通过对在给定位置中展示的ads的CTRs做平均计算得到。具有越高ranked positions的Ads一般也会生成更高的CTRs。之前的工作尝试建模或解释为什么存在position bias【5】。在我们的setting中，我们假设：过往ads的\(P(y \mid Position = p)\)会总结在一个在线广告系统中存在的这些issues，因为具有越高Position CTR的ads，也越可能具有与high PClicks更强相关的特性。

在理想情况下，一个PClick模型只会使用来自D中的一个大量的随机且均匀抽样数据（RUS数据：randomly and uniformly sampled data）。一个在线Ads stack的核心目标是：广告收入（ad revenue）。实际上，不可能获得一个大的随机抽样数据集，因为online展示许多随机的Ads和queries pair在代价太高。

3.背景

3.1 在线广告

biased FL的训练数据问题，可以通过multi-armed bandits来缓解。multi-armed bandits问题的核心是：寻找一个合理的Exploration & Exploitation的trade off。

在付费搜索广告的context中，会拉取一个arm，它对应的会选择一个ad进行展示。

• Exploration实际上意味着具有较低点击概率估计的ads，会导致在short-term revenue上的一个潜在损失（potential loss）。
• Exploitation偏向于那些具有最高概率估计的ads，会产生一个立即的广告收入的增益。

Bandit算法已经成功出现在展示广告文献、以及其它新闻推荐等领域。由于简洁、表现好，Thompson sampling是一个流行的方法，它对应的会根据最优的概率抽取一个arm。

这些方法在该假设下工作良好，可以探索足够的广告。在在线机器学习系统中，medium-term和short-term revenue的损失是不可接受的。我们可以获取exploration data的一个小抽样，但通常获得足够多的exploration data开销很大，它们受训练数据极大影响。因此，大量biased FL data仍然会被用于训练一个模型，这个问题仍存在。

另一种解决该问题的方法是：回答一个反事实的问题（answering the conterfactual question）[2]。Bottou et al.展示了如何使用反事实方法。该方法不会直接尝试最优化从D上的抽样数据的效果，而是估计PCLick models在过往表现有何不同。作者开发了importance sampling技术来估计具有置信区间的关于兴趣的conterfactual expectations。

Covariate shi‰ft是另一个相关问题，假设：\(P(Y \mid X)\)对于训练和测试分布是相同的，其中：Y是labels，X是features。然而，p(X)会随着training到testing分布发生shifts或者changes。与counterfactual文献相似，它会对loss function进行rebalance，通过在每个实例上乘以\(w(x)=\frac{p_{test}(x)}{p_{train}(x)}\)，以便影响在test set上的变化。然而，决定w(x)何时test set上不会具有足够样本变得非常困难。在我们的setting中RUS dataset不足够大来表示整个分布D。

3.2 Adversarial Networks

对抗网络（Adversarial networks）在最近变得流行，特别是在GANs中作为generative models的一部分。在GANs中，目标是构建一个generative model，它可以通过同时对在一个generator和discriminator network间的两个loss functions进行最优化，从一些domain中可以创建真实示例。

Adversarial networks也会用于其它目的。[1]提出使用Adversarial networks来生成某些级别的加密数据。目标是隐藏来自一个adversary的信息，。。。略

4.方法描述

给定一个biased Feedback Loop的training set我们描述了一种ANN结构来生成精准的PClick预测 \(\hat{y}\)。我们假设一个连续值特征b，它会对该bias进行归纳。我们将b定义成在Ads context中的position CTR或\(P(y \mid Position=p)\)。一个input features集合X通常与b弱相关。

4.1 网络结构

图1

ANN表示包括了如图1所示的4部分：Base network、Predction network、Bias network、以及一个Bypass Network，该networks的每一部分具有参数：\(\theta_A, \theta_Y, \theta_B, \theta_{BY}\)。

• 第一个组件，Base和Prediction networks，会独立地对b进行最优化；
• 第二个组件，Bypass network，只依赖于b。

通过以这种方式解耦模型，ANN可以从bias存在时的data进行学习。

Bypass结构会直接使用b，它通过包含它的最后的hidden state \(Z_{BY}\)作为在等式1的最后sigmoid prediction函数中的一个linear term。最终的hidden states的集合用于预测\(\hat{y}\)将包含一个来自Prediction和Bypass Network的线性组合。假设：

…(1)

其中：

• \(Z_y\)：表示在prediction network中最后的hidden activations
• \(W_Y\)：表示weights，用来乘以\(Z_Y\)
• \(W_{BY}\)：它的定义类似
• c：标准线性offset bias项

在b上的linear bypass strategy，当直接包含b时，允许ANN独立建模b，并保留在b上相对排序（relative ranking）

给定X，Base Network会输出一个hidden activations的集合，\(Z_A\)会将输入feed给Prediction和Bias networks，如图1所示。\(Z_A\)用于预测y效果很好，而预测b很差。

4.2 Loss functions

为了完成hidden activations的期望集合，我们会最小化两个competing loss函数：

• bias loss: \(Loss_B\)
• noisy loss：\(Loss_N\)

其定义分别如下：

bias loss:

…(2)

noisy loss:

…(3)

bias loss函数在等式2中定义。loss function会衡量在给定\(Z_A\)时Bias network是否可以较好预测b。在图1中，只有Bias network(orange)和\(\theta_B\)会分别根据该loss function进行最优化，从而保持所有其它参数为常数。

等式3描述了noisy loss function，它会在\(\theta_A, \theta_{BY}, \theta_Y\)上进行最优化，而保持\(\theta_B\)为常数。该loss包含了\(Loss_Y(y, \hat{y})\)来表示prediction loss，可以以多种方式定义。本工作中，我们使用binary cross entropy来定义\(Loss_Y\)。

…(4)

\(Cov_B(b, \hat{b})\)是一个sample covariance的函数，它通过在一个给定minibatch中计算跨b和\(\hat{b}\)均值来计算：

…(5)

\(Cov_B(b, \hat{b})^2\)表示来自预测噪声的距离\(\hat{b}\)。squared covariance是0，当\(\hat{b}\)与b非正相关或负相关。当存在高相关性时，只要\(\lambda\)足够大，\(Loss_N\)会被高度惩罚。

产生的\(Loss_N\)的objective function会对两种差的预测对模型进行惩罚，X用于恢复b。\(\lambda\)控制着每个项与其它有多强相关。

4.3 学习

实际上，covariance function会跨每个mini-batch进行独立计算，其中会从每个minibatch进行计算。两个loss function \(Loss_N\)和\(Loss_B\)会通过在相同的minibatch上使用SGD进行交替最优化(alternatively optimized)。

4.4 在线inference

为了在一个online setting上预测，我们会忽略Bias network，并使用其它三个networks来生成predictions： \(\hat{y}\) . 在在线广告系统中，对于在过去在线没有看到过的数据，我们将b设置为Position 1 CTR，接着它们会feed到Bypass Network中。

5.系统级bias的人工评估

我们会生成人造数据来展示自然的feedback loop或者在在线广告stack中出现的system level bias。我们首先根据一个bernoulli（概率为：\(P(Y=1)=0.1\)）生成click labels，其中Y=1表示一个点击的ad。接着，feature vectors \(x_j\)会从两个不同但重合的正态分布上生成，根据：

其中，我们设置\(\sigma=3\)。

这会构成一个完全分布D，会采用10w样本来构建一个大的Reservoir dataset。我们接着表示通过仿真一个迭代过程来表示feedback loop，其中之前的top ranked \(x_j\)（或ads）被用于训练数据来对下一个ads进行排序。图2和3展示了这个feedback loop过程，算法2演示了该仿真。

图2

图3

根据第i-1天的Reservoir数据集中的10000个实例的\(\frac{K}{2}\)候选集合使用无放回抽样随机抽取，其中K=500.模型\(M_{i-1}\)会在第i-1天上训练，并在每个候选集合上对top 2 ads进行排序，在第i天展示给用户。labels会在第i天展示，它随后会形成对可提供的\(topk_i\)训练数据供下一次迭代。

我们会重复该过程，直到迭代了T=100轮. 每次迭代中，我们会记录对于每个top 2 positions的平均position CTR \(P(y \mid Position=p)\)。p=1表示top ranked ads，p=2表示2nd top ranked ads。我们会将position CTRs看成是连续bias term b。为了启动该过程，我们会从Reservoir中抽取K个实例来构成\(topk_0\)。在一个在线Ads系统中，多天的训练数据通常被用来减小systermatic bias。后续评估中，我们会利用最近两天的训练数据（例如：\(M_i\)只在\(topk_i\)和\(topk_{i-1}\)上训练）。每个模型\(M_i\)是一个logistic regression classifier，它具有l2正则。我们在算法2的13行上设置参数r=0，来展示一个系统级的feedback loop bias。我们构成了testing data，从该feedback loop过程中独立，或从D中抽取10w样本来进行HeldOut RUS评估。

表1

在过去两天的每个position的CTR如表1所示，整个CTRs的计算在所有天上计算。所有的4 CTR values可能相等，因为他们每个都与250个训练样本相关。因此，一种naive方法是预测平均CTR values。这会构建对一个adversarial Bais Network如何来预测b的一个上界。我们会在表2中记录过去最近两天数据(4 values)的average CTR，并使用该值来计算MSE。

表2

5.1 setup

当在FL data上训练模型时，可以生成D或RUS HeldOut data。对于该FL data，我们它使用不同的\(\lambda\)来训练一个ANNs的集合，并将b设置为它的Position CTR。除了last layers外，所有hidden activations会使用hyperbolic tangent function。Prediction network的output activation function是一个sigmoid，并且Bias Network的output activation是线性的。Bypass network包含了具有1个node的1个hidden layer，而Base、Prediction、Bias networks每个都包含了带有10个nodes的1个ideen layer。我们会执行SGD，它具有minibatch size=100以及一个learning rate=0.01. 我们会在FL data上训练100个epochs。在这个主训练过程之后，我们允许Bias network在\(Loss_B\)上训练100个epochs。理想的，在给定从Base network生成的\(Z_A\)上，这会允许Bias network来预测b。

根据对比，我们会为一个带有\(\lambda=0\)的ANN执行相同的评估。该模型可以看成是一个完全独立的vanilla neural network，它在y上进行最优化，而一个独立的Bias network可以观察和最优化\(Loss_B\)，无需对Base Network进行变更。我们会对每个模型运行10个具有不同weight initialization的实验，并上报关于y的AUC以及在b上的MSEs。

5.2 主要结果

为了评估来自D的一个无偏样本，我们会使用position 1 CTR, 0.464, 它从最近一天\(topk_{T-1}\)得到。

表3展示了从D中抽取的HeldOut data的AUC和LogLoss，它会在该dataset上训练一个logistic regression模型。这是构成在AUC的一个上界的理想情况。

表3

除了使用Bypass network的ANN架构外，我们也展示了不带Bypass network的ANN的一个变种。图4展示了在FL和RUS datasets上AUCs和MSEs。x-aixs是一个reverse log scale，\(\lambda\)从0到0.99999.随着 \(\lambda\)的增大，MSE大多数会增加FL AUC error的开销。使用Bypass network的ANN的FL MSE error会下降到0.00078(如表2所示)，它与只有平均CTR的naive方法具有相同的表现。

图4

我们注意到，随着\(\lambda\)达到1，在\(Loss_N\)中的\(Loss_Y\)项变得无足轻重，因此可以是\(\lambda\)的一个集合，可以在D的AUC项上进行最优化，它在图4c上可以看到。

ANN模型从\(\lambda=0.9999\)到\(\lambda=0\)在RUS set上的AUC上会有12.6%增益，而在RUS set上只训练一个模型10%的off。

5.3 Bypass vs. non Bypass的结果

图4中的结果展示了使用Bypass vs. non-Bypass ANN在AUC上的微小提升，以及在RUS dataset上具有更高MSEs。我们也分析了根据给定不同的position CTRs在bypass network预测中的不同。我们会在第\(day_{T-1}\)天feed Position 1 CTR作为input到Bypass network中，和features一起做预测，\(\hat{y}_1\)，并在\(day_{T-1}\)feed Position 2 CTR来创建\(\hat{y}_2\)。

我们会计算average prediction。图4e展示了这些结果。随着MSE的增加，会在预测上有所不同。因此，我们会假设：Bypass network可以快速解释在ANN表示中的position CTR。

6.在user level bias上的人工评估

另一个造成position bias的factor可能是一个user level bias。用户可能会偏向于不会点在Position 1下的ads，除非是相关和用户感兴趣。我们会模拟一个额外的User level Bias信息，通过在之前的人工评估中截取position 2 ranked ad的labels来进行。算法2的12-14行的，通过使用概率r来切换observed click label从1到0.

。。。

参考

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

介绍

共享账号的推荐，很早就有人发paper，我们看下先人的一些探索《Top-N Recommendation for Shared Accounts》：

介绍

一般的推荐系统假设：每个用户账号(user account)表示单个用户(user)。然而，多个用户(user)经常共享单个账号(account)。一个示例是：一个家庭中的所有人会共享同一个在线视频账号、同一个在线音乐流账号、同一个在线电商账号、同一个商店的购物卡。

当多个用户共享账号时会引出三个问题。

首先，dominance problem。当所有推荐项（recommendations）只与共享账号的部分用户有关，至少一个用户不会获得任何相关推荐项，此时会引起“主导问题（dominance problem）”。我们会说：只有少量用户的兴趣会主宰该账号的推荐。另外，考虑一个经常购物的家庭。他们通常会在购买家庭用品时偶尔也会为孩子购买玩具。现在，很有可能所有推荐项会基于更多的家庭用品来生成，该推荐系统对孩子来说是基本没啥用。

第二，generality problem。当推荐项不仅与共享账号下所有用户兴趣都有些相关，并且又不仅仅与任一个用户相关时，会引发“generality problem”。当多个用户的不同品味兴趣被合到同一个账户上时，推荐系统更可能会推荐被大多数人喜欢的通用items（general items），忽略掉私人的品味。

第三，如果推荐系统可以为共享账号上的每个用户生成相关的推荐项，每个用户如何知道哪个推荐项是为你推荐的呢？我们称这为“presentation problem”。

如果有提供上下文信息（比如：time、location、购买意图、item内容、session logs等），context-aware推荐系统是SOTA的解决方案，它可以将accounts划分成多个用户，并检测在推荐时活跃用户的身份。

然而，通常对于划分账号来说通常没有提供这么多上下文信息：

• 第一种情况是：许多公司不会保存过往的上下文信息日志，同时也不保存timestamps
• 第二个情况是：家庭会在一个超市里进行一起购买，他们只有一个信用卡账户，当访问商店时会将购物进行放在一起。在这种情况下，context信息对于每个家庭成员来说是相同的，不能用来将家庭账号划分成各自成员。

因此，我们会介绍：在缺失上下文信息下的共享账号的top-N推荐，上面的关于共享账号的三个问题会在不使用任意上下文信息的情况下得到解决。

正式的，我们先考虑使用二元（binary）、positive-only的偏好反馈的CF的setting。我们将可提供数据表示成一个偏好矩阵，其中：行表示用户，列表示items。偏好矩阵中的每个值是1或0，其中1表示一个已知偏好，0表示未知。[12]称这种setting为one-class CF（OCCF），但它也被称为基于binary、postive-only偏好数据的top-N推荐。这种数据通常与implicit feedback有关。然而，它也是explicit feedback的结果。这不同于社交网站的例子（explicit）。其它相关的应用有：照片标签、文档的words、一个顾客购买的物品。

尽管在缺失上下文信息下共享账号的top-N推荐很重要，我们没有先前研究解决过该挑战。我们通过提出一个解决方案来解决所有item-based topN CF推荐系统的该case，基于binary、postive-only feedback来生成推荐。在这种情况下，我们覆盖了大多数应用，因为ICF很流行。大多数作者将ICF的流行性归结为：多个特性的组合（简洁、稳定、高效、准确），可以直觉性解释它们的推荐，并且能立即解释新进来的feedback。

我们展示了新的item-based top-N CF推荐系统，它允许我们在O(nlogn)下计算推荐分（非指数时间内）。

主要贡献如下：

• 正式介绍缺失上下文信息下的共享账号top-N推荐
• 提出解决方案
• 一个必要特性
• 实验表明：多个数据集上，可以检测共享账号下独立用户的偏好

2.问题定义

假设：U是用户集合，A是账号集合，I是items集合。更进一下，假设：

• \(U(a) \subseteq U\)是具有共享账号a的用户的集合（例如：账号a的用户集合）
• \(a(u) \in A\)是用户u属于的账号

注意：在该问题设定中，每个用户会属于一个账号。

首先，考虑用户评分矩阵（user-rating-matrix）\(T \in \lbrace 0, 1 \rbrace^{\mid U \mid \times \mid I \mid}\)。其中：

• \(T_{ui}=1\)表示存在用户\(u \in U\)对于item \(i \in I\)的偏好
• \(T_{ui}=0\)表示没有这样的偏好

我们给定：一个相关的推荐系统\(R_{ref}\)会产生在给定T下的期望推荐。因此，我们会说：通过相关推荐系统\(R_{ref}(T)\)在用户评分矩阵（user-rating-matrix）T上计算，如果i在u的top-N推荐中，则一个item i与一个user u相关。

不幸的是，在我们的问题设定中，T是未知的。因此，我们会给出账号评分评阵（account-rating-matrix） \(R \in \lbrace 0, 1 \rbrace^{\|A\| \times \|I\|}\)。其中：

• \(R_{ai}=1\)表示账号\(a \in A\)对于\(i \in I\)是存在一个已知偏好的
• \(R_{ai}=0\)表示不存在这样的信息

现在，缺失上下文信息的共享账号的top-N推荐，会设计一个共享账号推荐系统\(R_{sa}(R)\)，它基于账号评分评阵（account-rating-matrix）R，计算每个账号a的top \(N_a\)的推荐，如下：

• top \(N_a\)包含了在账号a的用户集合下每个用户的top-N items，有：\(N = \frac{N_a}{\mid U(a) \mid}\)。实际上，这里目标是：通过最大化在topN中具有至少一个item的用户的数目（用户多，兴趣也多），来避免dominance问题和generality问题。
• 账户a的用户集合中的某一用户，在top-Na中的哪个items是对他有意义的，这是很清楚的，presentation problem会得到解决

注意：在上面的定义中，共享账号的推荐系统不会获得共享每个账号的用户数目作为输入。更进一步，关于共享一个账号的用户的共享兴趣，不会做出任何假设。他们可以具有完全不同的兴趣，或者部分重叠的兴趣，或者完全重合的兴趣。

最后，注意该问题定义与一个典型的group推荐问题【10】正交。

• 首先，在group推荐中，在共享账号下的用户的个体profiles通常都是已知的。而在这里，他们是未知的。
• 第二：在group推荐中，通常会假设，推荐内容会被在共享账号中的所有用户所消费；而在这里，共享账号的每个用户可以区别对它有意义的推荐，并单独消费这些推荐。

3.相关推荐系统

通常，对于一个用户u的top-N推荐，推荐系统会先为每个候选推荐项i计算推荐得分 s(u,i)，接着从中选择按最高分排序的top-N推荐项。

对于binary、postive-only feedback，大多数流行的推荐系统的其中之一是，item-based CF推荐系统【2】。这些item-based推荐系统根源于这样的意图：好的推荐会与target user偏好的目标items相似，其中在两个items间的相似性会通过使用在用户喜欢的items的各自集合间的任意相似度measure进行衡量。因此，对于一个target user u，这种推荐系统：

• 首先会发现KNN(j)：这是对j的k个最相似items，其中：每个喜欢的item j（\(T_{uj}=1\)）通过使用一个相似measure \(sim(j,i)\)进行衡量。
• 接着，用户u对候选推荐项i的item-based推荐得分给定如下：

…(1)

其中：

• \(I(u) = \lbrace j \in I \mid T_{uj} = 1 \rbrace\)，这是u喜欢的items集合。

sim(j,i)的一个常见选择是cosine相似度。更进一步，归一化相似度得分可以提升表现【2】。sim(j,i)的定义如下：

我们可以使用这种推荐系统作为相关推荐系统\(R_{ref}\)。

4.相关推荐系统的共享账号问题

简单将相关推荐系统（reference recommender system）应用到account-rating-matrix R上会导致次优结果，因为RRS会有三个共享账号问题。我们使用两个示例进行说明。在两个示例中，我们考虑：

• 两个用户\(u_a\)和\(u_b\)会共享账号s
• 用户\(u_a\)对于items \(a_1\)和\(a_2\)具有一个已知偏好（相当于推荐里面的trigger item list）
• 用户\(u_b\)对于items \(b_1\), \(b_2\), \(b_3\)具有一个已知偏好（相当于推荐里面的trigger item list）
• 存在5个候候选推荐：\(r_a^1, r_a^2, r_b^1, r_b^2, r_g\)

其中：

• \(r_a^1\)和\(r_a^2\)是对于\(u_a\)来说的好推荐；
• \(r_b^1\)和\(r_b^2\)是对于\(u_b\)来说的好推荐。
• \(r_g\)是一个完全通用的推荐，对两个用户都是中性

表1、2

表1和2给出了前两个示例一些立即计算。两表左侧都是每个候选推荐项（行）与共享账号s（列）的已知偏好间的相似度。两表的右侧都是每个候选推荐项（行）的三个推荐得分（列）。这些得分使用等式（1）计算而来，分别根据左侧的相似度值得到。前两个得分分别对应于\(u_a\)和\(u_b\)，如果他们没有共享一个账号。第三个得分是对于s（两者共享）的得分。

• 第一个示例中（对应于表1）中的IB RRS会有genreality问题。对于表1，我们可以学到：如果\(u_a\)与\(u_b\)不共享账号，item-based RRS会为\(u_a\)正确安排最好的得分给\(r_a^1\)和\(r_a^2\)，为\(u_b\)安排\(r_b^1\)和\(r_b^2\)。然而，如果\(u_a\)和\(u_b\)会共享账号s，那么完全通用的item \(r_g\)会得到最高得分。在本例中，item-based RRS会具有genreality问题，因为它不会区别推荐得分（少量大值的求和，而是许多小值的总和）。

• 第二个示例（对应于表2）展示了item-based RRS会有dominance问题。从表2看到，我们学到，如果\(u_a\)不会与\(u_b\)共享一个账号，item-based RRS会为\(u_a\)正确安排最高分\(r_a^1\)和\(r_a^2\)，为\(u_b\)分配\(r_b^1\)和\(b_b^2\)。然而，即使\(u_a\)和\(u_b\)会共享账号s，\(u_b\)的所有推荐项会接收到一个比\(u_a\)的任意推荐项更高的得分。因而，\(u_b\)的推荐项会主宰账号。在这种情况下，item-based RRS会具有dominance问题，因为它不会解释：\(u_b\)具有比\(u_a\)更多的偏好。

• 两个示例都适合说明RRS存在的presentation问题。例如，考虑表1的第一行。推荐得分\(s(s, r_a^1) = 11\)是以下三项\(sim(a_1, r_a^1)=5, sim(a_2, r_a^1) = 5, s(b_1, r_a^1) = 1\)的总和。因此，它可以通过\(a_1, a_2, b_1\)来进行解释。然而这是一个坏的解释，因为由于\(b_1\)的存在，\(u_a\)会难于区分解释，会错误下结论成该推荐项对\(u_b\)来说也是有意义的。

5.解决genreality问题

前面章节表明，由于item-based RRS不会区分：一个得分是少量大相似得分的求和，还是许多小相似分得分的求程。因此会出现generality问题。因而，我们的第一步是采用item-based的推荐得分（等式1）到length-adjusted item-based（LIB）推荐得分上：

…(2)

其中，超参数\(p \in [0,1]\)。尽管这种adjustment不会立即解决genreality问题，它会提供一种方式，来区分是：在少量大相似得分的求和，还是许多小得分求和的问题。通过选择p > 0，我们可以创建一个bias，它偏向于少量大相似得分的求程。p值越大，该bias就越大。

由于因子\(\frac{1}{\mid I(u) \mid^P}\)对于所有候选推荐i来说是相同的，对于用户u根据\(S_{LIB}\)和\(S_{IB}\)的top N items是相同的。然而，当我们计算两个不同用户间的得分时，\(S_{LIB}\)也会解释用户喜欢的items总量。

为了避免generality问题，我们理想地希望：为共享账号a中的某个用户推荐与他高度相关的推荐项i。因此，我们会计算item i与每个个体用户\(u \in U(a)\)的推荐得分。正式的，我们希望根据它的推荐得分对所有item i进行排序：

不幸的是，我们不能计算理想的推荐得分，因为\(U(a)\)和I(u)是未知的。相似的，我们只知道账号a的偏好：\(I(a) = \lbrace j \in I \mid R_{aj} = 1 \rbrace\), 它表示账号a喜欢的items集合。

然而，我们可以使用它的上界对理想的推荐得分进行近似：

其中，\(2^{I(a)}\)是\(I(a)\)的幂（power）（该集合包含了所在I(a)的可能子集）。提出的近似是一个理想得分的上界，因为I(u)的每个集合对于\(u \in U(a)\)来说是\(2^{I(a)}\)的一个元素。该近似是基于假设：所有I(a)的子集，它们对应于用户更可能生成最高的推荐得分，而非将它们随机地放在一起。

相应的，我们提出使用disambiguating item-based(DAMIB)推荐系统，关于账号a对于item i的推荐得分如下：

…(3)

每个得分\(s_{DAMIB}(a, i)\)对应于一个最优的子集\(S_i^* \subseteq I(a)\)：

…(4)

因而，\(s_{DAMIB}(a, i) = s_{LIB}(S_i^*, i)\)。这样，DAMIB推荐系统不仅会计算推荐得分，也会发现账号a对于i的最大化length-adjuested item-based推荐得分的最优子集\(S_i^*\)。

换句话说，DAMIB推荐系统会基于直觉和task-specific准则，隐式地（implicitly）将共享账号a划分成子集\(S_i^*\)，每个\(S_i^*\)会对于候选推荐项i之一来最大化\(S_{LIB}\)。

• 当\(S_{LIB}(S_i^*, i)\)很高时，我们希望，\(S_i^*\)能很好地对应一个个体用户。
• 当\(S_{LIB}(S_i^*, i)\)很低时，在共享账号上没有用户对于i是一个强推荐，我们希望\(S_i^*\)是一个随机子集。

这样，我们会避免容易出错的（error prone）任务：估计在共享账号上的用户数目、并基于一个通用的聚类准则，显式地将账号a划分成它的个体用户。

更进一步，由于子集可以是潜在重合，DAMIB推荐系统不会关注在共享账号上的用户的已知偏好是否强重合、微重合、或者根本不重合。

最终，注意，对于p=0来说，它总是有：\(s_{DAMIB} = s_{LIB} = s_{IB}\)。因此，item-based推荐系统是DAMIB推荐系统的一个特例。

6.高效计算

可以发现，在等式(3)中的最大化，需要以指数时间复杂度来直接计算\(S_{LIB}\)，称为\(2^{\mid I(a) \mid}\)。相应的，直接计算\(s_{DAMIB}\)是很难的。

幸运的是，我们表明：\(S_{LIB}\)会允许我们来以O(nlogn)来计算\(s_{DAMIB}\)，其中：\(n = \mid I(a) \mid\)。该特性由定理6.1给出。

定理6.1 ： 假设a是一个账号，它喜欢items I(a)的集合。i是一个候选推荐。如果我们将所有items \(j,l \in I(a)\)进行排序，\(rank(j) < rank(l) \Leftrightarrow sim(j,i) > sim(l,i)\)，这样，子集\(S_i^* \subseteq I(a)\)会在所有\(S \in 2^{I(a)}\)上最大化\(S_{LIB}(S, i)\)，它是ranking的一个prefix。

证明：给定任意的\(S \subseteq I(a)\)。初始化P=S。当P不是一个prefix时，从P中移除最差的ranked item r，并添加最好的ranked item a到P中（它不在P中）。只要P还不是一个prefix，它会持有: \(sim(a, i) \geq sim(r, i)\)。因此，每个这样的item安排会增加\(s_{LIB}(P, i)\)（或至少等于），因为因子\(\frac{1}{\mid I(a) \mid^P}\)不会变化，在求和项\(\sum_{j \in I(a)} sim(j,i) \cdot \mid KNN(j) \cap \lbrace i \rbrace \mid\)中的一个较小项会被更一个更大的项所替代。因而，对于每个\(S \subseteq I(a)\)，它不是ranking的一个prefix，我们也可以总是找到一个prefix \(P \subseteq I(a)\)，满足：\(s_{LIB}(P,i) \geq s_{LIB}(S, i)\)。因此，子集\(S_i^*\)会最大化在所有\(S \in 2^{I(a)}\)上的\(s_{LIB}(S, i)\)，必须总是ranking的一个prefix。

由于最优的subset是一个prefix，我们可以发现，它在ranked items I(a)上的一次遍历是线性时间的。时间复杂度上的log因子会来自于对\(\mid I(a) \mid\)上进行排序。

该理论是我们方法的核心，因为它允许我们在O(nlogn)上计算\(s_{DAMIB}\)。

7.解决Dominance问题

DAMIB推荐系统允许我们检测：什么时候(when)发生domainance问题。这是因为：由DAMIB提供的每个推荐项i会伴随着一个清晰的解释，形式为：最优子集\(S_i^* \subseteq I(a)\)。因此，如果union \(U_{i \in top-N_a} S_i^*\)只是I(a)的一个小子集时，我们知道：这个小子集会在账号a的top \(N_a\)推荐中占统治地位。

可以通过选择在算法1中的ALG=DAMIB（我们称为COVER）来解决dominance问题。例如，我们为共享账号推荐的最终算法是DAMIB-COVER，其中：DAMIB-COVER(a) = COVER(a, DAMIB)。

算法1

该DAMIB-COVAER算法会使用DAMIB得分来找出\(N_a\)的最高得分候选推荐，如果它的解释(explanation)\(S_c^*\)与更高排序的候选的解释不容易区分，我们就从top \(N_a\)中移除该候选推荐项c。\(D(S_c^*, C(a)) \geq \theta_D\)的解释区分性条件，会衡量一个候选(\(S_c^*\))以及更高排序候选（ranked candidates）C(a)的explanations的union是否足够不同。

8.求解presentation问题

对于一个共享账号a，使用DAMIB-COVEAR生成top-Na推荐项是不够的，因为共享账号的用户不知道哪个推荐项属于哪个用户。这被称为presentation问题。

我们的解决方案是，将每个推荐项 \(i \in top-N_a\)、与它的解释(explanation)\(S_i^*\)表示在一起。我们期望：对于在top-Na中的items i的绝大多数，explanation \(S_i^*\)是u（共享账号a的某一用户）的偏好I(u)的一个子集。我们会在第9节进行验证该假设。

因此，我们将该推荐表示为item r推荐给喜欢s1, s2, s3的用户。接着，一个会用户认为s1, s2, s3是他的偏好，并知道r是推荐给他的。

9.实验评估

所有数所集都是公开提供的。另外，我们的源代码和数据集链接在：https://bitbucket.org/BlindReview/rsa 上有提供。该网站包含了脚本来自动化运营每个实验。另外，所有结果可以复现。

9.1 数据集

我们使用一个包含了真实的共享账号信息的数据集。CAMRa 2011数据集，它包含了家庭成员信息，关于用户对电影评分的一个子集。这样，我们可以使用该数据集构建真实共享账号。不幸的是，owner不希望分发该数据集，我们没有其它包含共享信息的数据集。然而，从CAMRa 2011数据集上，我们可以学到，大多数家庭账号包含了两个用户（290个家庭有272个），一些包含了三个（14/290），四个（4/290）。因此，我们会根据Zhang[15]的方法，来创建“人工伪造（synthetic）”的共享账号，随机将用户分成2个、3个、4个的组。尽管该方法并不完美，[15]表明‘synthetic’的共享账号会与CAMRa 2011数据集的真实共享账号特性相似。

我们在4个数据集中对解决方案进行评估：Yahoo!Music[13]、Movielens1M[4]，Book-Crossing[16]以及Wiki10+[17]数据集上。

YahooMusic: 14382个用户在1000首歌上进行评分：1-5分。由于我们会考虑binary、postive-only数据的问题设定。我们将4-5的评分转成1，忽略其它评分。平均的，一个用户具有8.7个偏好。

Movielens1M：包含了6038个用户在3533电影上，评分：1-5分。另外，我们会将4-5的评分转化为1. 平均一个用户具有95.3个偏好。

Book-Crossing：包含了两种信息。首先，用户在books上的评分：1-10分。与前2个数据集类似，我们会将评分8, 9, 10分转成偏好并忽略所有的其它评分。第二，也存在二元偏好，我们会添加到偏好列表中。总之，存在87835个用户，300695本书，每个user具有平均11个偏好。

wiki10+：包含了99162个tags，分配给20751个wikipedia文章。在本case中，我们考虑文章的标签推荐，文章看成是“users”的角色，tags看成是”items”的角色。如果一个文章a被打上至少一次的tag t标签，我们认为文章a具有tag t 的一个”perference”。在该context下，一个共享账号是一个大文章，它具有广泛主题，包含了多个更小在子主题下的“articles”。平均，每个article具有22.1个tags。

由于空间限制，我们只展示了在Yahoo!Music dataset上的数值结果。然而，对于其它三个数据集，可以在https://bitbucket.org/BlindReview/rsa上下结论，并导致相同的结论。

9.2 对比算法

我们比较了新算法：DAMIB-COVER，以及另两种算法。第一个对比算法是IB，是item-based RRS在account-rating-matrix上的应用，它忽略了shared account问题的存在。这是我们的baseline。第二个对比算法是IB-COVER，它被定义成IB-COVER(a) = COVER(a, IB). IB-COVER是与【14】的算法相似。

9.3 效果

理想的，在共享账号中所有用户的recall是1，这意味着，对于共享账号的top-Na是个体top-5的union，共有\(\|U(a)\|\)个用户共享账号。

现在，为了研究有多少用户会有共享账号的问题，我们会衡量用户没有获得任何相关推荐的比例，例如：不会发现单个的top-5个体推荐项在共享账号的top-Na推荐项。我们将该数目表示成\(rec_0^u\)，召回为0的用户占比。正式的，我们定义如下：

一个具有共享账号问题的用户的示例如表3所示。该表展示了两个来自Movielens1M数据集的两个真实用户，它们各自已知的偏好I(u)，以及item-based个体top-5推荐。它们item-based个体top-5推荐项看起来合理给出它们的已知偏好，这两个用户是同一家庭的一部分并且共享账号看起来是不现实的。相应的，表3也展示了对于’synthetic’账号的推荐项，它们会在两个cases中（ \(R_{sa} = IB\)以及\(R_{sa} = DAMIB-COVER\)）被两个用户共享。在case \(R_{sa} = IB, rec(562) = 0\)中，例如：user 56

1

2不会获得单个推荐，它会存在共享一个账号的问题。

图1展示了Yahoo!Music数据集的\(rec_0^u\)。最近邻的数目k，是一个item-based RRS的参数。存在多种方式来选择k。在这些方法中，样本是以一个offline实验的accuracy，推荐的主观质量调整；在线A/B的accuracy，计算效率，等。因此，我们会呈现关于RRS的变化带来的结果，例如：ICF RS会与其它k种选择不同。相应的，图1的每个plot会展示一个不同k的结果。

对于每种k的选择，以及单独的top-5推荐，对应于4个实验：一个账号被1、2、3、4个用户共享。注意，一个账号如果由一个用户共享，这种实际并不是共享。每个水平轴表示共享该账号的用户数目，每个垂直轴表示产生的\(rec_0^u\)。4种不同的标记表明，4种不同的共享账号推荐系统\(R_{sa}\)：

• baseline 算法IB
• IB-COVER
• 提出的DAMIB-COVER算法的两个变种

这两个变种会根据参数选择的不同有所区别：p=0.5和p=0.75。由于我们会随机重复每个实验5次，每个plot包含了5x4=20个相似的标记。然而，由于低传播、大多数标记会在相互的top上被绘制，形成dense的maker云。更进一步，由于95%的置信区间，意味着5个数据集的maker-clounds会更窄，我们没有进行绘制。相应的，两个maker-clouds会进行单独可视化，也会在5%的显著级别上具有显著不同。

我们从图1中做出4个观察：

• 首先，我们观察到，baseline的效果并不好。当他们相互共享账号时，接近19%的用户获得不相关推荐。这表明，共享账号会对于推荐系统引起极大问题

• 第二，我们提出的解法，DAMIB-COVER算法，可以提大提升\(rec_0^u\)。在一些情况下，提交是剧烈的。一个示例是$$| U(a)

  = 2\(，个体top-5会使用k=200进行生成。在本case中，当使用baseline IR算法时，12%的用户不会获得相关推荐。通过使用DAMIB-COVER(p=0.75)，该数目会减小到因子4（\)rec_0^U = 0.03$$）。

• 第三，一些IB-COVER已经在IB上进行了提升。存在多个cases，其中DAMIB-COVER会进一步在IB-COVER上提升。另外，DAMIB-COVER会胜过IB-COVER会变得在评估presentation问题时更清晰。
• 最后，当\(\| U(a) \| = 1\)，例如，当账号并不共享时，\(rec_0^u=0\)，是为baseline算法IB进行定义。然而，我们观察到，对于IB-COVER以及DAMIB算法的变种，\(rec_0^u\)可以足够低。因而，当账号不共享时，提出的DAMIB算法不会失败。

9.4 有限的trade-off

为了强调这一点：当没有账号共享时，DAMIB-COVER算法仍在传统设定下表现良好，我们也讨论了DAMIB-COVER的结果会在一个【2】使用的更确定的实验设定下。为了避免所有的困惑：该实验设定不会做关于共享账号的任何事。在该实验设定下，每个用户的一个偏好会被随机选中作为该用户的测试偏好\(h_u\)。如果一个用户只有一个偏好，不会有测试偏好被选中。剩余偏好会被在training matrix R中表示成1（由于没有账号会被共享，它在该case中是完全相同的）。R的所有其它条目都为0。我们将\(U_t\)定义成具有一个测试偏好的用户集合。对于每个user \(u \in U_t\)，每个算法会基于R对items \(\lbrace i \in I \| R_{ui} = 0 \rbrace\)进行排序。根据[2]，我们会使用hitrate@5来评估每个ranking。hitrate@5的给定如下：

其中，top5(u)是用户u的5个最高的ranked items。因而，HR@5给出了测试偏好在top5 推荐中的测试用户百分比。Yahoo!Music数据集的实验结果如图2所示。除了早前讨论的算法外，图2也包含了baseline算法POP的结果，非个性化算法会根据它们的流行度对所有items进行排序；例如：用户在training set中的用户会偏向于该item的数目。在该case中，我们会重复实验5次，使用一个不同的随机分。另外，由于低传播性，5个数据点通常会绘制在互相的顶部。图2展示了DAMIB-COVER和IB在HR@5上非常相似。因此，以HR@5作为全局accuracy几乎没有trade-off。

9.5 Presentation

在第8节中，我们提出解通过将每个推荐项与它的explanation放在一起进行presenting，来解决presentation问题。如果这样，共享账号中的一个用户可以将一个explanation看成是他的偏好的一个子集，该用户会区分该推荐项，因此可以知道推荐项对它是有意义的。对于这种解决方案，很重要的是推荐项是可辨别的，例如：它的explanation是共享账号中某一用户的偏好子集。对于一个共享账号a，我们可以使用explanation \(S_i^*\)来测量一个推荐项i的可辨识性：

理想的，ident(S_i^*) = 1，例如，explanation中的每个item是某个用户一个偏好。在最坏的情况下，\(ident(S_i^*) = 1/ \| U(a) \|\)，例如：explanation包含了一个在共享账号中所有用户的一个等量偏好，因此没有用户可以使用推荐进行区分。

图3展示了对于多个共享账号推荐系统\(R_{sa}\)，在Yahoo!Music数据集上 \(\| U(a) \| = 2\)的top10推荐的identifiability的直方图。从图3a所示，我们可以学到，如果某个用户简单地将item-based reference算法应用到Yahoo的共享账号数据集上，会发生presentation问题：很少的推荐项可以被在共享账号中的某一用户所区分出，例如：\(ident(S_i^*) = 1\)只有10%的explanations。图3b展示了使用IB-COVER来替代IB，不会对情况带来改善。然而，图3c展示了使用DAMIB-COVER可以弹性增加推荐项的区分性，例如：\(ident(S_i^*) = 1\)有近似60%的explanations。因而，DAMIB的explanations会优于iitem-based explanations。

参考

• 1.https://uploads-ssl.webflow.com/5ee118733109492e193e63d2/5f068f4e6b396d7536c1bdbc_190823%20-%20Research%20Paper%20-%20Top-N%20Recommendation%20for%20Shared%20Accounts.pdf

介绍

facebook在2019在《Deep Learning Recommendation Model for Personalization and Recommendation Systems》。

摘要

facebook开发了一种SOTA的深度学习推荐模型（DLRM）并提供了Pytorch和Caffe2的实现。另外，还设计了一种专门的并行化scheme利用在embedding tables上的模型并行机制来缓和内存限制，利用数据并行机制来从fully-connected layers中扩展（scale-out）计算。我们比较了DLRM与已存在推荐模型.

1.介绍

在大型互联网公司中的许多任务上，部署了个性化和推荐系统，包括：CTR预估和rankings。尽管这些方法具有很长的历史，这些方法最近才拥抱神经网络。对于个性化和推荐，朝着深度学习模型架构设计方向贡献了两个主要视角。

第一个视角来自于推荐系统。这些系统最初部署了content filtering，其中：运营人员会将products按categories分类，而用户选择它们喜欢的categories，因而可以基于它们的偏好进行match[22]。该领域接着演化成使用collaborative filtering，基于用户过往行为（比如：用户对商品的评分）进行推荐。最近邻方法[21]通过将users和products进行分组（grouping）在一起来提供推荐，latent factor方法通过MF技术以及特定隐式factors将users和products进行特征化，并成功部署。

第二个视角来自预测分析(predictive analytics)，它依赖于统计模型根据给定数据来对events进行分类（classify）或预测（predict）。预测模型从简单模型（比如：linear或logistic regression）转向到深度网络上来建模。为了处理类别型数据，这些模型采用了embeddings，它会将one-hot和multi-hot vectors转化成在一个抽象空间中的dense表示。该抽象空间可以被解释成由推荐系统发现的latent factors空间。

在本paper中，我们引入了一个个性化模型，它可以通过将上述两个视角进行联合来表示。模型会：

• 1.使用embeddings来处理稀疏特征（sparse features）（它可以表示categorical data）
• 2.使用一个multilayer perceptron（MLP）来处理dense features

接着使用[24]中的统计技术将这些features进行显式交叉。最终，它会使用另一个MLP来post-processing交叉来寻找event probability。我们将该模型称为：DLRM（深度学习推荐模型）。见图1。该模型的PyTorch和Caffe2实现已公开。

2.模型设计与架构

在本节中，我们会描述DLRM的设计。我们会从网络的high-level组件开始，并解释how和why它们以一种特别的方式组合在一起，对未来模型设计有启发，接着描述组成模型的low-level operators和primitives，用于未来的硬件和系统设计。

2.1 DLRM组件

通过回顾以往模型，DLRM的high-level组件可以很容易理解。我们会避免完整回顾，把精力集中在早期模型的4个技术上，它可以在DLRM中的高级组件中被解释。

2.1.1 Embeddings

为了处理类型化数据，embeddings可以将每个category映射到一个在抽象空间中的dense表示上。特别的，每个embedding lookup可以被解释成使用一个one-hot vector \(e_i\)来获得embedding table \(W \in R^{m \times d}\)相应的row vector：

…(1)

在更复杂的情况下，一个embedding也可以表示成多个items的加权组合**，它具有一个关于weights的multi-hot vector：

其中，

• 对于\(i=i_1, \cdots, i_k\)，元素\(a_i \neq 0\)，否则为0 ，其中\(i=i_1, \cdots, i_k\)是相应的items。

注意，t embedding lookups的一个mini-batch可以写成：

…(2)

其中，sparse matrix为：\(A = [a_1, \cdots, a_t]\)。

DLRMs会使用embedding tables来将categorical features映射成dense representations。然而，在这些embeddings被设计后，如何利用它们来生成更精准的预测呢？我们先来回顾下latent factor。

2.1.2 Matrix Factorization

推荐问题的常用形式，我们给定一个集合S：用户会对一些商品进行评分。我们通过两个vector：

• \(w_i \in R^d, i=1,\cdots, n\)来表示第i个商品，
• \(v_j \in R^d, j=1, \cdots, m\)来表示第j个user

以便寻找所有的ratings，其中n和m各表示products和users的总数。更严格的，当第i个商品已经被第j个user评分时，集合S包含了(i,j) tuples。

MF方法通过最小化下面的等式来求解该问题：

…(3)

其中：

• \(r_{ij} \in R\)是第j个user对第i个product的rating，\(i=1, \cdots, m; j = 1, \cdots, n\)。

接着，假设：\(W^T = [w_1, \cdots, w_m]\)和\(V^T = [v_1, \cdots, v_n]\)，我们希望将full matrix的ratings \(R=[r_{ij}]\)近似为矩阵乘法 \(R \approx W V^T\)。注意，W和V可以被解释成两个embedding tables，其中每一行表示在latent factor space中的一个user/product。这些embedding vectors的dot product会生成后续rating的一个有意义的预测，这对于FM和DLRM的设计来说是一个key observation。

2.1.3 Factorization Machine

在经典问题中，我们希望定义一个预测函数：\(\phi: R^n \rightarrow T\)，从一个输入数据点\(x \in R^n\)到一个target label \(y \in T\)上的预测。作为示例，我们可以通过定义 \(T = \lbrace +1, -1 \rbrace\)预测CTR，其中：+1表示点击，-1表示未点击。

FM使用categorical data，通过定义以下形式的模型，来将二阶交叉并入到一个线性模型中：

…(4)

其中：

• 1.\(V \in R^{n \times d}\)
• 2.\(w \in R^n\)
• 3.\(b \in R\)
• 4.\(d << n\)的参数
• 5.upper会严格选择该矩阵的上三角部分【24】。

FM与SVM和polynomial kernels有明显区别，因为它们将二阶交叉矩阵分解成latent factors（或embedding vectors）（和MF很像），它能更有效地处理稀疏数据。通过只捕获不同embedding vectors pairs间的交叉，这可以极大减小二阶交叉的复杂度，生成线性的计算复杂度。

2.1.4 MLP(Multilayer Perceptrons)

同时，在机器学习上的最近许多成功都归因于deep learning。DL最基础的模型是：MLP。预测函数由一串交替的FC layers和activation function \(\sigma: R \rightarrow R\)组成：

…(5)

其中：

• \(W_l \in R^{n_l \times n_{l-1}}\)是weight matrix
• \(b_l \in R^{n_l}\)：表示对于\(layer \ l=1,\cdots,k\)的bias

该方法被用于捕获更复杂的交叉。例如，给定足够参数，MLP会具有够深和够宽，可以拟合任意想预测的数据。这些方法的变种被广告用于CV和NLP中。例如：NCF被用于MLPerf benchmark的一部分，它使用MLP，而非dot product来计算MF中embeddings间的交叉。

2.2 DLRM架构

我们已经描述了在RS中不同的模型。我们将这些想法进行组合来构建SOTA的个性化模型。

假设用户和商品通过许多连续型特征（continuous features）和类别型特征（categorical features）进行描述。

• 为了处理categorical features，每个categorical feature可以通过一个相同维度的embedding vector表示，即MF中latent factors。
• 为了处理continous features，会通过一个MLP来进行转换，它会生成和embedding vectors相同长度的dense representation。

我们将根据FMs提供的处理sparse data的方式，将它们传给MLPs，显式地(explicitly)计算不同特征间的二阶交叉（second-order interaction）。这可以通过使用所有embedding vectors的pairs和dense features间的dot product来做到。用这些dot products可以使另一个MLP(top 或 output MLP)将original-processed dense features和post-processed一起concatenated，接着被feed到一个sigmoid function来提供一个概率。

我们将产生的模型称为：DLRM。如图1所示，并在表1中展示了PyTorch和Caffe2的DLRM所用到的一些operators。

表1

2.3 与之前的模型比较

许多deep learning-based的推荐模型，使用相似的底层思想来生成高阶项来处理sparse features。Wide&Deep, Deep&Cross, DeepFM, xDeepFM网络，例如，设计专有网络来有系统的构建高阶交叉。这些网络接着将来自这些专有模型和MLP的结果进行求和（sum），将它传给一个linear layer及sigmoid activation来生成一个最终概率。DLRM以一种结构化的方式与embeddings交互，通过只考虑由final MLP中embeddings pairs间的dot-product生成的cross-terms，模拟了FM对模型进行极大地降维。对于在其它网络的二阶交叉外的更高阶交叉，使用额外的计算/内存开销并不值。

DLRM和其它网络之间的一个关键不同点是：这些网络是如何对待embedded feature vectors和它们的cross-terms的。DLRM(以及XDeepFM)会将每个feature vector看成单个unit来表示单个category，其它像DCN(Deep&Cross)网络会将feature vector中的每个element看成是一个新的unit，这会生成不同的cross-terms。因此，Deep&Cross网络不仅会生成不同feature vectors的elements间的cross-terms（这和DLRM通过dot product方式一样），也会生成在相同feature vector的elements间的cross-terms，从而生成更高的维度。

3.并行化（Parallelism）

模型个性化和推荐系统，需要大且复杂的模型来估计大量数据上的价值。DLRMs特别包含了许多数目的参数，多阶的幅度要超过其它常见的deep learning模型（比如：CNN），transformer、RNN、GAN。这会导致训练时间上常达数周或更久。因此，对这些模型进行高效并行化，以便解决在实际规模中的问题。

如前面章节所示，DLRMs会以成对（coupled）的方式，同时处理categorical features（使用embeddings）以及continuous features（使用bottom MLP）。Embeddings会占据参数的大部分，一些tables每个都需要超过多个GBs的内存，使得DLRM对内存容量和带宽很敏感。embeddings的size使得它禁止使用数据并行化（data parallelism），因为它需要在每个设备上复制很大的embeddings。在许多cases中，这种内存限制需要模型分布跨多个设备，以便能满足内存容量需求。

在另一方面，MLP参数在内存上是更小的，但需要大量计算。因此，data-parallelism对MLPs更好，因为它可以让不同devices上的samples并发处理，只需要在当累积更新（accumulating updates）时需要通信。我们的并行化DLRM会使用一个embeddings的模型并行化(model parallelism)以及MLPs的数据并行化(data parallelism)的组合，来减缓由embeddings生成的内存瓶颈，而MLPs上的forward和backward propagations并行化。通过将model和data parallelism进行组合，是DLRM的唯一需求，因为它的架构和大模型size所导致；这样的组合并行化在Caffe2或PyTroch中并不支持（以及其它流行的DL框架），因此，我们设计了一种定制实现。我们计划在将来提供它的详细效果研究。

在我们的setup中，top MLP和interaction operator需要访问部分来自bottom MLP的mini-batch以及和所有embeddings。由于模型并行化已经被用于跨devices分布embeddings，这需要一个个性化的all-to-all通信。在embedding lookup的尾部，对于在mini-batch中的所有samples（必须根据mini-batch维度进行分割、以及与相应devieces进行通信）、对于在这些devices上的embedding tables，每个device都具有一个vector，如图2所示。Pytorch或Caffe2都不会提供model parallelism的原生支持；因此，我们通过显式将embedding operators（PyTorch的nn.EmbeddingBag, Caffe2的SparseLengthSum）映射到不同devices上来实现它。个性化的all-to-allcwpwy使用butterfly shuffle operator来实现，它可以将生成的embedding vectors进行切片（slices），并将它们转移到目标设备（target devices）上。在当前版本，这些transfers是显式的copies，但我们希望后续使用提供的通信原语（比如：all-gather以及send-recv）进一步optimize。

我们注意到，对于数据并行化MLPs，在backward pass中的参数更新会使用一个allreduce进行累积（accumulated），并以一种同步方式将它用在每个device的参数复制上，确保在每个device上的参数更新在每轮迭代上是一致的。在Pytorch中，data parallelism可以通过nn.DistributedDataParallel和nn.DataParallel模块来开启，将在每个device上的model复制，使用必要的依赖插入allreduce。在Caffe2中，我们会在梯度更新前手工插入allreduce。

4.数据

为了measure模型的acuracy，并测试它的整体效果，并将单独operators特征化，我们需要为我们的实现创建或获得一个dataset。我们模型的当前实现支持三种类型的datasets：random、synthetic、public datasets。

前两个dataset对于从系统角度实验我们的模型很有用。特别的，它允许我们通过生成即时数据，并移除数据存储依赖，来测试不同的硬件属性及瓶颈。后一个dataset允许我们执行真实数据的实验，并measure模型的accuracy。

4.1 Random

回顾DLRM，它接收continuous和categorical features作为inputs。前者可以通过生成一个随机数目的vector，通过使用一个uniform/normal(Gaussian)分布（numpy.random rand/randm缺省参数）。接着通过生成一个matrix来获得mini-batch inputs，其中每行对应在mini-batch中的一个element。

为了生成categorical features，我们需要决定在一个给定multi-hot vector中具有多少非零元素。benchmark允许该数字可以是fixed或在一个[1,k]的范围内random。接着，我们生成整型indices的相应数字，范围在[1,m]中，其中，m是在embedding W中的rows数目(2)。最后，为了创建一个mini-batch的lookups，我们将以上indices进行concatenate，并将每个单独的lookup使用lengths和offsets进行描述。

4.2 Synthetic

对应于categorical features，有许多理由支持定制索引的生成。例如，如果我们的应用使用一个特定dataset，但我们不希望出于私人目的共享它，那么我们可以选择通过distributions来表示categorical features。这可以潜在作为一种隐私保护技术的可选方法（用于联邦学习(federated learning)）。同时，如果我们希望练习系统组件（比如：学习内存行为）。。。

4.3 Public

参考

• 1.https://arxiv.org/pdf/1906.00091.pdf
• 2.https://github.com/facebookresearch/dlrm

deepmind在19年发了篇关于feedback loops的paper：《Degenerate Feedback Loops in Recommender Systems》，我们可以来看下它的paper介绍：

摘要

在生产环境中的推荐系统大量使用机器学习。这些系统的决策会影响user beliefs和preferences，从而影响学习系统接受到的feedback——这会创建一个feedback loop。这个现象被称为“echo chambers”或“filter bubbles”。本paper提供了一个新的理论分析，来检查user dynamics的角色、以及推荐系统的行为，从而从filter bubble效应中解脱出来。另外，我们提供了实际解决方案来减小系统的退化（degeneracy）。

介绍

推荐系统广泛被用于提供个性化商品和信息流。这些系统会采用user的个人特征以及过往行为来生成一个符合用户个人偏好的items list。虽然商业上很成功，但这样的系统会产生一个关于窄曝光（narrowing exposure）的自我增强的模式，从而影响用户兴趣，这样的问题称为“echo chamber”和“filte bubble”。大量研究都致力于对曝光给用户的items set上使用favor diversity来解决。然而，echo chamber和filter bubble效应的当前理解很有限，实验分析表明会有冲突结果。

在本paper中，我们将echo chamber定义为这样的效应：通过重复曝光一个特定item或item类目，一个用户的兴趣被正向地（positively reinforced）、或负向地（negatively）增强。这是Sunstein(2009)的定义概括，其中，该术语通常指的是：对相似政治意见的over-exposure和limited-exposure，会增强个人的已存在信念（beliefs）。Pariser(2011)引入了filter bubble的定义，来描述推荐系统会选择有限内容来服务用户。我们提供了一个理论方法来允许我们单独考虑echo chamber和filter bubble效应。我们将用户兴趣看成是一个动态系统（dynamical system），并将兴趣看成是系统的退化点（degeneracy points）。我们考虑不同模型的动态性，并确定系统随时间degenerate的充分条件集合。我们接着使用该分析来理解推荐系统所扮演的角色。最终我们展示了：在一个使用模拟数据和多个经典bandit算法的仿真学习中，在user dynamics和推荐系统actions间的相互作用。结果表明，推荐系统设计的许多缺陷（pitfalls）和缓和策略。

相关工作

。。。

3.模型

我们考虑一个推荐系统，它会与用户随时间一直交互。在每个timestep t上，recommender系统会从一个有限的item set M中提供l个items给一个user。总之，该系统的目标是：将可能感兴趣的items呈现（present）给用户。我们假设：

• 在timestep t上，user在一个item $a \in M$上的兴趣，可以通过函数\(\mu_t: M \rightarrow R\)来描述。
• 如果用户对该item很感兴趣，那么\(\mu_t(a)\)很大（positive）；反之为很小（negative）

给定一个推荐(recommendation) \(a_t = (a_t^1, \cdots, a_t^l) \in M^l\)，用户基于它当前的兴趣 \(\mu_t(a_t^1), \cdots, \mu_t(a_t^l)\)提供一些feedback \(c_t\)。该交互具有多个effects：在推荐系统传统文献中，feedback \(c_t\)被用于更新用于获取推荐\(a_t\)推荐系统的internal model \(\theta_t\)，接着新模型\(\theta_{t+1}\)会依赖\(\theta_t, a_t, c_t\)。实际上，\(\theta_t\)通常会预测user feedback的分布来决定哪个items \(a_t\)应被呈现给该用户。在本paper中，我们关注另一个效应（effect），并显式考虑用户与推荐系统的交互可能会在下一次交互时以不同的items来变更他的兴趣，这样，该兴趣\(\mu_{t+1}\)会依赖于\(\mu_t, a_t, c_t\)。交互的完整模型如图1所示。

图1

我们对用户兴趣的演化研究很感兴趣。这样的一个演化示例是，兴趣会通过用户与所推荐items的交互进行增强，也就是说：

• 如果用户在timestep t上对一个item a进行点击，那么\(\mu_{t+1}(a) > \mu_t(a)\)；
• 如果a被展示但未被点击，则\(\mu_{t+1}(a) < \mu_t(a)\). （这里, \(c_t \in \lbrace 0, 1 \rbrace^l\)可以被定义成所对应items的关于点击的indicator vector）

为了分析echo chamber或filter bubble效应，我们对于用户兴趣在什么时候发生非常剧烈变化非常感兴趣。在我们的模型中，这会转成\(\mu_t(a)\)采用任意不同于初始兴趣\(\mu_0(a)\)的值：大的positive values表示用户会对item a变得非常感兴趣，而大的negative values表示用户不喜欢a。正式的，对于一个有限item set M，我们会问到：L2-norm \(\| \mu_t - \mu_0 \|_2 = (\sum_{a \in M} (\mu_t(a) - \mu_0(a))^2)^{1/2}\)是否可以变得任意大？如果满足下面条件，几乎必然用户的兴趣序列\(\mu_t\)被称为“弱退化（weakly degenerate）”(证明见附录)：

…(1)

关于degenracy的”stronger”概念，需要满足：一旦\(\mu_t\)远离\(\mu_0\)，它就是个stronger degeneracy。序列\(\mu_t\)是一个较强的degenrate，（ almost surely）需满足：

…(2)

下一节中，我们将展示，在\(\mu_t\)的动态演进上的充分条件较缓和时，degeracy发生的强弱。

对于一个无限item set M的情况，存在多种方式来扩展上述定义。出于简化，我们只考虑使用\(\| \mu_t - \mu_0 \|_2\)来替代等式(1)和等式(2)中的\(sup_{a \in M} \mid \mu_t(a) - \mu_0(a) \mid\)，当M是有限时，它等于原始定义。

3. 用户兴趣动态性——Echo Chamber

由于items通常以多样的类目(t diverse categorie)的方式呈现，我们简化猜想：它们间是相互独立的。通过对于所有t (例如：\(M = \lbrace a \rbrace\))，设置\(l=1\)和\(a_t^1 = a\)，我们可以移除推荐系统的影响，并单独考虑用户的动态性( Dynamics)。这使得我们分析echo chamber effect：如果item a被无限次推到，兴趣 \(\mu_t(a)\)会发生什么？

由于a是固定的，为了简化概念，我们将\(\mu_t(a)\)替换成\(\mu_t\)。给定\(a_t\)，根据图1，\(\mu_{t+1}\)是一个关于\(\mu_t\)的函数（可能随机，由于\(\mu_{t+1}\)依赖于\(c_t\)和\(\mu_t\)，\(c_t\)依赖于\(\mu_t\)）。我们考虑当漂移量（drift） \(\mu_{t+1} - \mu_t\)是一个非线性随机函数时的通用case；对于drift的deterministic模型在附录B中。

非线性随机模型（Nonlinear Stochastic Model）

其中：

• 我们假设\(\mu_0 \in R\)是固定的
• \((\xi_t)_{t=1}^{\infty}\)是一个关于独立均匀分布的随机变量的无限序列，它引入噪声到系统中（例如：\(\mu_{t+1}\)是一个\(\mu_t\)的随机函数）
• 函数 \(f: R \times [0, 1]\)是假设是可测的，但其它任意。通过\(U([0, 1])\)来定义[0,1]上的均匀分布，假设：

是当\(\mu_t = \mu\)的期望增量\(\mu_{t+1} - \mu_t\)。我们也定义了：

是increment的累积分布。\(\mu_t\)的渐近行为依赖于f，但在mild假设下，系统会微弱（定理1）／较强（定理2）退化。

定理1（弱退化weak degeneracy）。假设F对于所有\(\mu \in R\)在\((\mu, 0)\)上是连续的，存在一个\(\mu_o \in R\)，使得：

• 1) 对于所有\(\mu \geq \mu_o\)，有\(F(\mu, 0) < 1\)
• 2) 对于所有\(\mu \geq \mu_o\)，有\(F(\mu, 0) > 0\)

那么序列\(\mu_t\)是weakly degenerate，比如：\(\underset{t \rightarrow \infty}{lim} sup \mid \mu_t \mid = \infty\)

该假设保证了在任意闭区间内，存在一个常数概率，当分别从\(\mu_o\)的左侧/右侧开始时，该random walk会逃离区间左侧/右侧。在stronger condition下，可以保证random walk的分散性（divergence）。

定理2 (强退化: strong degeneracy)

假设定理1恒定，另外存在\(c \in R\)使得 \(\| \mu_{t+1} - \mu_t \| \leq c\)，存在一个\(\epsilon > 0\)，使得对于所有足够大的\(\mu\)，有\(f(\mu) > \epsilon\)，对于所有足够小的\(\mu\)有\(f(\mu) \leq - \epsilon\)。接着，\(limit_{t \rightarrow \infty} \mu_t = \infty\)或者\(limit_{t \rightarrow \infty} \mu_t = -\infty\)。

直觉上，如果用户兴趣具有一些关于drift的非零概率，weak degeneracy在一个随机环境中发生。而strong degeneracy会持有额外的\(\mu_{t+1} - \mu_t\)被限制，对于\(\mu_t\)足够大/小，而增量\(\mu_{t+1} - \mu_t\)具有positive/negative drift，它大于一个constant。

定理1和2表明，用户兴趣会在非常温和的条件下退化（degenerate），特别的是在我们的模似实验中。在这样的cases中，如果一个item（或一个item category）是被展示有限多次时，degeneracy可以被避免，否则你只能寄希望于控制\(\mu_t\)退化的有多快了（例如：趋向于\(\infty\)）。

4.系统设计角色——filter bubble

在之前的部分讨论了对于不同user interest dynamics的degeneracy的条件。在本节中，会检查另一面：推荐系统动作对于创建filter bubbles上的影响。我们通常不知道现实世界用户兴趣的动态性。然而，我们考虑echo chamber/filter bubble的相关场景：其中在一些items上的用户兴趣具有退化动态性(degenerative dynamics)，并检查了如何设计一个推荐系统来减缓degeneracy过程。我们会考虑三个维度：model accuracy，曝光量（exploration amount），growing candidate pool。

4.1 Model accuracy

推荐系统设计者的一个常见目标是，增加internal model \(\theta_t\)的预测accuracy。然而，模型accuracy如何与greedy optimal \(a_t\)组合一起来影响degeneration的速度？对于exact predictions的极端示例，例如：\(\theta_t = \mu_t\)，我们会将这样的预测模型为“oracle model”。我们会在前提假设法（surfacing assumption）下讨论，oracle模型与greedily optimal action selection组合来生成快速的degeneracy。

为了具体分析该问题，对于\(\mu_t(a)\)的\(a \in M\)，我们会关注degenerate线性动态模型，例如：\(\mu_{t+1}(a) = (1+k) \mu_t(a) + b\)。接着，我们可以为\(\mu_t(a)\)求解，对于\(\mid 1+k(a) \mid > 1\)来获得：

Sufacing Assuption:

假设\([m] = \lbrace 1,2, \cdots, m \rbrace\)是size=m的candidate set。如果一个items子集 \(S \subset [m]\)会产生positive degenerate （例如，对于所有\(a \in S\), \(\mu_t(a) \rightarrow +\infty\)），那么我们假设：存在一个时间\(\tau > 0\)，对于所有\(t \geq \tau\)，S会占据根据\(\mu_t\)值生成的top \(\mid S \mid\)的items。该\(\mu_t\)由指数函数 \(\mid 1 + k(a) \mid\)的base value进行排序。

如果给定足够的曝光（exposure）时间，surfacing assumption可以确保很快地将items surface退化到top list上。它可以被泛化到关于\(\mu_t\)的非线性随机动态性上，从而提供：来自S的items具有一个稳定的随时间退化速度\(\mid \mu_t(a) - \mu_0(a) \mid /t\)的排序。

在通用的surfacing assumption下，在时间\(\tau\)之后，退化（degeneration）的最快方式是：根据\(\mu_t\)或oracle model的\(\theta_t\)来服务top l items。即使该assuption有一定程度的冲突，oracle model仍会产生非常高效的退化（degeneracy），通过根据\(\mu_t\)来选择top l items，由于较高的\(\mu_t\)，他不会接受到positive feedback，从而增加\(\mu_{t+1}\)、并增强过往选择。

实际上，推荐系统模型是不准确的（inaccurate）。我们可以将inaccurate models看成是具有不同级别的noises(添加到\(\theta_t\))的oracle model。

4.2 探索量（Amount of Exploration）

考虑一种\(\epsilon\)-random exploration，其中\(a_t\)总是从一个有限candidate pool [m]中（它在\(\theta_t\)上具有一个uniform \(\epsilon\) noise），根据\(\theta_t^{'} = \theta_t + U([-\epsilon, \epsilon])\)，选择出top l items。

给定相同的模型序列\(\theta_t\)，\(\epsilon\)越大，系统退化（degenerate）越慢。然而，实际上，\(\theta_t\)从observations上学到，在一个oracle model上添加的random expoloration可能会加速退化（degeneration）：random exploration可以随时间展示最正向的degenerating items，使得suracing assumption更可能为true（在图5中，我们在仿真实验中展示了该现象）。另外，如果user interests具有degenerative dynamics，随机均匀推荐items会导致degeration，虽然相当慢。

接着我们如何确保推荐系统不会使得user interests退化（degenerate）？一种方法是，限制一个item服务给user的次数（times）， 越多次会使得用户兴趣动态性退化。实际上，很难检测哪个items与dynamics退化相关，然而，如果所有items都只服务一个有限次数，这通常会阻止degeneration，这也暗示着需要一个不断增长的candidate items池子。

4.3 Growing Candidate Pool M

有了一个不断增长的（growing） candidate pool，在每个timestep时，会有一个关于new items的额外集合可提供给该user。从而，function \(\mu_t\)的domain会随时间t的增加而扩展（expands）。线性增加新items通常是一个避免退化的必要条件，因为在一个有限/任意次线性（sublinearly）增长的candidate pool上，通过鸽巢原理(pigeon hole principle)，必须存在至少一个item，在最坏情况下它会退化（degenerate）（在定理2描述的通用条件下）。然而，有了一个至少线性增长的candidate pool M，系统会潜在利用任意item的最大服务次数来阻止degeneration。

5.模拟实验

本节考虑一个\(\mu_t\)简单的degenerative dynamics，并检查在5个不同的推荐系统模型中的degeneration速度。我们进一步演示了，增加new items到candidate pool中会有一个对抗system degeneracy的有效解法。

我们为图1中一个推荐系统和一个用户间的交互创建了一个simulation。初始size=\(m_0\)，在timestep t上的size=\(m_t\)。在timestep t时，一个推荐系统会从\(m_t\)个items中，根据内部模型\(\theta_t\)来选择top l 个items \(a_t = (a_t^1, \cdots, a_t^l)\)服务给一个user。

该user会独立考虑l items的每一个，并选择点击一个子集（也可能不点击，为空），从而生成一个size=l的binary vector \(c_t\)，其中\(c_t(a_t^i)\)会给出在item \(a_t^i\)上的user feedback，根据\(c_t(a_t^i) \sim Bernoulli(\phi(\mu_t(a_t^i)))\)，其中\(\phi\)是sigmoid function \(\phi(x) = 1/(1 + e^{-x})\)。

接着该系统会基于过往行为（past actions）、feedbacks和当前模型参数\(\theta_t\)来更新模型\(\theta_{t+1}\)。我们假设，用户兴趣通过\(\theta(a')\)增加/减少，如果item \(a'\)会收到/未收到一个点击，例如：

…(3)

其中，function \(\delta\)会从candidate set映射到R上。从定理2中，我们知道对于所有item，有\(\mu_t \rightarrow \pm \infty\)。在该实验中，我们设置l=5,并从一个均匀随机分布\(U([-0.01, 0.01])\)中抽样drift \(\delta\)。对于所有items，用户的初始兴趣\(\mu_0\)是独立的，它们从一个均匀随机分布U([-1,1])中抽样得到。

内部推荐系统模型根据以下5个算法更新：

• Random model
• Oracle：
• UCB Multi-armed bandit
• Thompson Multi-armed bandit

6.1 Echo Chamber & Filter Bubble effect

我们通过在一个fixed size \(m_t = m = 100\)、time horizon T=5000的candidate pool上运行仿真，来检查echo chamber和filter bubble效应。

在图2中，我们展示了user interest \(\mu_t\)（左列）的degenreation、以及每个item的serving rate（右列），因为每个推荐模型会随时间演化。一个item的serving rate展示了在report interval内服务的频次。为了清楚地观察该分布，我们根据report time上的z-values对items进行排序。尽管所有模型会造成user interest degeneration，degeneration的speeds相当不同（Optimal Oracle > Oracle, TS, UCB > Random Model）。Oracle, TS 和 UCB是基于\(\mu_t\)优化的，因此我们可以看到对于\(\mu_t\)有一个positive的degenerative dynamics。Optimal Oracle会直接在degeneration speed上进行优化，而不会在\(\mu_t\)上，因此我们可以看到在\(\mu_t\)上同时有一个positive和negative degeneration。Random Model也会在两个方向上对\(\mu_t\)进行drifts，但以一个更慢的rate。然而，除了Random Model外，在所服务的top items上和top user interests会非常快速地收窄降到\(l=5\)的最positive的reinfofced items上。

图2

Degenracy Speed

接着，我们在fixed和growing的两种candidate sets上，为5个推荐系统模型比较了degeneracy speed。由于测量系统degeneracy的L2矩离对于所有五种模型来说是线性对称的，我们可以在有限candidate pools上，对于不同的实验设定比较\(\mid \mu_t - \mu_0 \mid_2 /t\)。

图3 5000个time steps上的系统演进，其中在report interval为500。结果是在30次运行上的平均，共享区域表示标准差。在degeneracy speed上，Optimal Oracle > Oracle > TS > UCB > Random

图3展示了5种模型的degeneracy speed，。。。。我们可以看到，Optimal Oracle会产生最快的degnereation，接着是：Oracle, TS，UCB。Random Model最慢。

Candidate Pool Size

在图4a中，我们比较了Optimal Oracle、UCB、TS的degenreacy speed \(\|\| \mu_t - \mu_0 \|\|_2 /t\)，直到5000 time steps，candidate pool sizes \(m=10, 10^2, 10^3, 10^4\)。除了random model，在给定一个大的candidate pool下，我们可以看到UCB会减慢degeneracy最多，因为它会首先强制探索任意unserved item。对于bandit算法，一个越大的candidate pool对于exploration需要一个更长时间。在给定time horizon下，由于candidate pool size增长到10000 UCB的dengeracy speed，从未达到峰值，但事实上会在给定一个更长时间上增长。TS具有越高的degereracy speed，因为在new items上具有更弱的exploration。Optimal Oracle 在给定一个更大pool上加速degeneration，因为比起一个更小的pool，它会潜在选择具有更快degenerative的items。

图4

另外，在图4b中，我们画出了所有5个模型的degeneracy speed，对于T=20000, 对比candidate pool sizes的相同变化。Optimal Oracle 和Oracle的degeneracy speed会随着candidate set的size增长。实际上，具有一个大的candidate pool可以是一个临时解法(temporary solution)来降低系统degeneration。

Noise Level的效应

接着我们展示了internal model inaccuracy在degeneracy speed上的影响。我们对比使用不同均匀随机噪声量的Oracle model，例如：系统根据noisy internal model \(\theta_t^{'} = \theta_t + U([-\epsilon, \epsilon])\)来对外服务top l items。candidate pool具有fixed size \(m=100\)。在图5中，我们从0到10来区分\(\epsilon\)。与直觉相反的是（ Counter-intuitively），添加噪声到Oracle中会加速degeneration，因为对比起由\(\mu_0\)排序的top l items的fixed set，添加噪声会使得具有更快degenerative的items会被偶然选中，更可能满足Surfacing Assumption。给定\(\epsilon > 0\)，我们可以看到，随着noise level的增长，在degeneracy speed上具有一个单调递增的阻尼效应（damping effect）。

图5 在Oracle model上具有不同noise levels \(\epsilon \in [0, 10]\)的degeneracy speed，直到T=20000. 在Oracle中添加noise会加速degeneration，但随着noise level的增长，degneracy会缓下来

Growing Candidate Pool

我们通过计算\(sup_{a \in M} \mid \mu_t(a) - \mu_0(a)\mid /t\)，将degeneracy speed的定义扩展到一个有限的candidate pool上。由于degeneracy speed对于所有5种模型不是渐近线性的（asymptotically linear），我们会在10000个time steps上直接检查sup distance \(sup_{a \in M} \mid \mu_t(a) - \mu_0(a) \mid\)。为了构建在不同growth speed上的growing candidate pools，我们定义了一个增长函数\(m_t = \lfloor m_0 + l t^{\eta}\rfloor\)，通过不同增长参数\(\eta = 0, 0.5, 1, m_0 = 100\)定义。在图6中，我们在10个独立运行上对结果进行平均。对于所有growth rates，Oracle和Optimal Oracle都是degenerate的。Random Model会在sublinear growth \(\eta=0.5\)上停止degeneration，UCB也如此，这归因于之前unserved items上进行强制exploration，尽管它的trajectory具有一个小的上翘（upward tilt）。TS模型会在sublinear growth上degenerates，但在linear growth \(\eta=1\)上停止degernation。对于所有模型，growth rate \(\eta\)越高，他们degerate会越慢，如果他们完全这样做的话。当全部可用时，线性growing candidate set和continuous random exploration看起来是一个不错的方法，来对抗\(\mu_t\)的dynamics来阻止degeneracy。

图6 5个模型的比较，它们使用growing candidate pools，具有不同的rates \(\eta = 0, 0.5, 1.0\)，degeneracy直到T=10000, 在10个运行结果上平均得到。对于所有growth rates，Oracle和Optimal Oracle都是degenerate的。Random Model和UCB会在sublinear growth上停止generation，而TS model需要linear growth才会停止degeneration。

参考

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