华为在《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)所示:

\[p(y=1 | x, pos) = p(seen | x, pos) p(y = 1 | x, pos, seen)\]

…(1)

如果我们进一步假设(注意:此处为PAL的关键假设)

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

那么,等式(1)被简化成等式(2) :

\[p(y=1 | x, pos) = p(seen | pos) p(y=1 | x, seen)\]

…(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被定义成:

\[L(\theta_{ps}, \theta_{pCTR}) = \frac{1}{N} \sum\limits_{i=1}^N l(y_i, bCTR_i) = \frac{1}{N} \sum\limits_{i=1}^N l(y_i, ProbSeen_i \times pCTR_i)\]

…(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的影响会分别被隐式学到。

\[\theta_{ps} = \theta_{ps} - \eta \cdot \frac{1}{N} \sum\limits_{i=1}^N (bCTR_i - y_i) \cdot pCTR_i \cdot \frac{\partial ProbSeen_i}{\partial \theta_{ps}}\]

…(4)

\[\theta_{pCTR} = \theta_{pCTR} - \eta \cdot \frac{1}{N} \sum\limits_{i=1}^N (bCTR_i - y_i) \cdot ProbSeen_i \cdot \frac{\partial pCTR_i}{\partial \theta_{pCTR}}\]

…(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上的距离,如下所示:

\[D(\delta_M, L) = \frac{1}{|U|} \sum\limits_{u \in U} (\sum\limits_{i=1}^L |i - \delta_{M,u}(i)| )\]

…(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)定义:

\[Personlization@L = \frac{1}{ |U| \times (|U|-1)} \sum\limits_{a \in U} \sum\limits_{b \in U} (1 - \frac{q_{ab}(L)}{L})\]

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

参考

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的线性组合。假设:

\[\hat{y} = sigmoid(W_Y Z_Y + W_{BY} Z_{BY} + c)\]

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

\[Loss_B(b, \hat{b}; \theta_B) = \sum\limits_{i=0}^n (b_i - \hat{b}_i)^2\]

…(2)

noisy loss:

\[Loss_N(y, \hat{y}, b, \hat{b}; \theta_A, \theta_{BY}, \theta_Y) = (1-\lambda) Loss_Y(y, \hat{y}) + \lambda \cdot Cov_B(b, \hat{b})^2\]

…(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\)。

\[Loss_Y(y, \hat{y}) = \frac{1}{n} \sum\limits_{i=0}^n y_i log(\hat{y}_i) + (1-y_i) log(\hat{y}_i)\]

…(4)

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

\[Cov_B(b, \hat{b})^2 = (\frac{1}{n-1} \sum\limits_{i=0}^n (b_i - \bar{b})(\hat{b}_i - \bar{\hat{b}})^2\]

…(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\)会从两个不同但重合的正态分布上生成,根据:

\[x_j = \begin{cases} N(0, \sigma), & \text{if $Y=0$} \\ N(1, \sigma), & \text{if $Y=1$} \end{cases}\]

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

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

图片名称

图2

图片名称

图3

根据第i-1天的Reserviir数据集中的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.

。。。

参考

介绍

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:

\[w_i^T = e_i^T W\]

…(1)

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

\[a^T = [0, \cdots, a_{i_1}, \cdots, a_{i_k}, \cdots, 0]\]

其中,

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

注意,t embedding lookups的一个mini-batch可以写成:

\[S = A^T W\]

…(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方法通过最小化下面的等式来求解该问题:

\[min \sum\limits_{(i,j) \in S} r_{ij} - w_i^T v_j\]

…(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,通过定义以下形式的模型,来将二阶交叉并入到一个线性模型中:

\[\hat{y} = b + w^T x + x^T upper(VV^T) x\]

…(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\)组成:

\[\hat{y} = W_k \sigma(W_{k-1} \sigma(W_1 x + b_1) \cdots) + b_{k-1}) + b_k)\]

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

参考

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)”(证明见附录):

\[\underset{t \rightarrow \infty} {lim} sup || \mu_t - \mu_0 ||_2 = \infty,\]

…(1)

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

\[\underset{t \rightarrow \infty} {lim} || \mu_t - \mu_0 ||_2 = \infty\]

…(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_{t+1} = \mu_t + f(\mu_t, \xi_t)\]

其中:

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

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

\[F(\mu, x) = P_{\xi \sim U([0,1])} (f(\mu, \xi) \leq x)\]

是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\)来获得:

\[\mu_t(a) = (\mu_0(a) + \frac{b(a)}{k(a)} (1 + k(a))^t - \frac{b(a)}{k(a)}\]

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'\)会收到/未收到一个点击,例如:

\[\mu_{t+1}(a_t^i) - \mu_t(a_t^i) = \begin{cases} \delta(a_t^i) & \text{if $ c_t(a_t^i) = 1 $ } \\ -\delta(a_t^i) & \text{otherwise} \end{cases}\]

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

参考

在《The Impact of Popularity Bias on Fairness and Calibration in Recommendation》paper中,提出了polularity bias与miscalibration之间具有一定的关联:

摘要

最近,在fairness-aware的推荐系统上收获了许多关注,包括:在不同users或groups上提供一致performance的fairness。如果推荐不能公平地表示某一个确定user group的品味,而其它user groups则与他们的偏好一致时,则一个推荐系统可以被认为是unfair的。另外,我们使用一个被称为“miscalibration”的指标来measure一个推荐算法响应用户的真实偏好程度,我们会考虑多个算法在miscalibration上的不同程度。在推荐上一个知名类型的bias是polularity bias,在推荐中有少量流行items被过度呈现(over-represented),而其它items的majority不会获得大量曝光。我们推测,popularity bias是导致在推荐中的miscalibration的一个重要因素。我们的实验结果使用两个真实数据集,展示了不同user groups间algorithmic polularity bias和他们在popular items上的兴趣程度的强相关性。另外,我们展示了,一个group受algorithmic polularity bias的影响越多,他们的推荐是miscalibrated也越多。最后,我们展示了具有更大popularity bias趋势的算法会具有更大的miscalibration。

1.介绍

在推荐生成中近期关注的一个热点是:fairness。推荐的fairness在推荐的不同domain、不同users或user groups的特性(比如:protected vs. unprotected)、以及系统设计者的目标下具有不同的含义。例如,[12]中将fairness定义成不同user groups间accuracy一致性。在他们的实验中,观察到,特定groups(比如:女性)会比男性获得更低的accuracy结果。

用来衡量推荐质量的一个metrics是:calibration,它可以衡量推荐分发与用户评分过的items的一致性。例如,如果一个用户对70%的action movies以及30%的romance movies评过分,那么,该用户在推荐中也期望看到相似的pattern[27]。如果该ratio与用户profile不同,我们则称推荐是miscalibrated。Miscalibration自身不能被当成unfair,因为它只能简单意味着推荐不够个性化。然而,如果不同的users或user groups在它们的推荐中都具有不同程度的miscalibration,这可能意味着一个user group的unfair treatment。例如,[28]中定义了一些fairness metrics,它关注于不同user groups间estimation error的一致性效果。

协同推荐系统的一个显著限制是popularity bias:popular items会被高频推荐,在一些cases中,推荐甚至超过它们的popularity,而大多数其它items不能获得合适比例的关注。我们将algorithmic popularity bias定义成:一个算法扩大了在不同items上已存在的popularity差异。我们通过popularity lift指标来measure该增强效应(amplification),它表示在input和output间平均item polularity的差异。比如,关于popularity bias可能会有疑惑,可能有以下原因:long-tail items(non-popular)对于生成一个用户偏好的完整理解来说很重要。另外,long-tail推荐也可以被理解成是一个社会福利(social good);存在popularity bias的market会缺乏机会来发现更多obscure的产品,从而被大量大品牌和知名artists占据。这样的market会越来越同质化(homogeneous),为创新提供更少的机会。

在本paper中,我们推荐:popularity bias是导致推荐列表miscalibration的一个重要因素。

。。。

2.相关工作

3.Popularity bias和miscalibration

3.1 Miscalibration

miscalibration用来measure用户真实偏好与推荐算法间差异程度。前面提到,如果在所有用户上都存在miscalibration,可能意味着个性化算法的failure。当不同user groups具有不同程度的miscalibration时,意味着对特特定user groups存在unfair treatment。

。。。

为了measure 推荐的miscalibration,我们使用[27]中的metric。假设u是一个user,i是一个item。对于每个item i,存在一个features集合C来描述它。例如,一首歌可能是pop、jazz,或一个电影的genres可以是action、romance、comedy等。我们使用c来表示这些独立categories之一。我们假设每个user会对一或多个items进行评分,这意味着会对属于这些items的features c感兴趣。对于每个user u的两个分布:一个是u评分过的所有items间的categories c的分布,另一个是u的所有推荐items间categories c的分布:

  • \(p_u(c \| u)\):在过去用户u评分过的items集合\(\Gamma\)上的feature c的分布为:
\[p_u(c | u) = \frac{\sum\limits_{i \in \Gamma w_{u,i} p(c|i)}}{\sum\limits_{i \in \Gamma} w_{u,i}}\]

…(1)

其中\(w_{u,i}\)是item i的权重,表示user u评分的频率。本paper中可以将w设置为1. 更关注不同分布上的差异,而非user profile的时序方面.

  • \(q_u(c \| u)\):推荐给user u的items list的feature c上的分布:
\[q_u(c|u) = \frac{\sum\limits_{i \in \wedge} w_r(i) p(c|i)}{ \sum\limits_{i \in \wedge} w_r(i)}\]

…(2)

\(\wedge\)表示推荐items集合。item i的weight则表示推荐中的rank r(i)。比如:MRR或nDCG。此外我们将\(w_r\)设置为1, 确保\(q_u\)和\(p_u\)可比。

在两个分布间的dissimilarity程度用来计算推荐中的miscalibration。常见的比方法有:统计假设检验。本文则使用KL散度来作为miscalibration metric。在我们的数据中,许多profiles没有ratings,这会导致在\(p_u\)上出现零值,同样具有推荐列表只关注特定features,对于一些users也在\(q_u\)上也会出现零值。对于没有observations的情况KL散度是undefined。作为替代,我们使用Hellinger distance H,它适用于存在许多0的情况。miscalibration的定义如下:

\[MC_u(p_u, q_u) = H(p_u, q_u) = \frac{|| \sqrt{p_u} - \sqrt{q_u}||_2}{\sqrt{2}}\]

…(3)

通过定义发现,H distance满足三角不等式。\(\sqrt{2}\)可以确保\(H(p_u, q_u) \leq 1\)。

对于每个group G的整体的miscalibration metric \(MC_G\)可以通过在group G中所有users u的\(MC_u(p,q)\)的平均来获得。例如:

\[MC_G(p, q) = \frac{\sum_{u \in G} MC_u(p_u, q_u)}{|G|}\]

….(4)

fairness

和[27]相似,本文将unfair定义为:对于不同user groups具有不同程度miscalibration时,则存在unfair。存在许多方式来定义一个user group,可以基于以下features:gender、age、occupation(职业)、education等。相似的,我们也可以基于它们的兴趣相似程度来定义user group。例如:对某些category上的兴趣度。

3.2 rating data中的Popularity Bias

推荐算法受popularity bias影响。也就是说,少量items会被推荐给多个users,而大多数其它items不会获得大量曝光。该bias可能是因为rating data的天然特性会倾向于popular items,因为该bias会存在algorithmic amplification。图1-b展示了两个user A和B的rated items的百分比。我们可以看到,user A的推荐被popularity bias高度影响,而user B在它们推荐中则不存在popularity bias的增强效应。

在许多领域,rating data会倾向于popular items——许多流行items会获得大量ratings,而其余items则具有更少的ratings。图2展示了item popularity的长尾分布。在其它datasets中也有相似的分布。流行的items之所以流行是有原因的,algorithmic popularity bias通常会将该bias放大到一个更大的程度。

并非每个用户都在流行items上具有不同程度的兴趣[4,22]。也会存在用户只能非流行、利基(niche)的items感兴趣。推荐算法也需解决这些用户的需求。图3展示了在不同user profiles上rated items的average popularity。用户首先会基于items的average popularity进行sort,接着绘出data。在movielens上,在图的最右侧和右侧,表示存在少量user,它们具有大量average item popularity,中间部分大量用户的分布具有0.1到0.15之间的average item popularity。在Yahoo Movies中,具有少量users具有low-popularity profiles,否则,distribution是相似的。这些图表明,用户在popular items上具有不同程度的偏向。

由于原始rating data上的imbalance,通常在许多情况下,算法会增强该bias,从而过度推出popular items,使得它们具有更大的机会被更多users进行评分。这样的推荐循环会导致rich-get-richer、poor-get-poorer的恶性循环。然而,并非每个推荐算法对popularity bias具有相同的放大能力(ampli€cation power)。下一部分描述了,测量推荐算法所传播的popularity bias的程度。经验上,会根据popularity bias增强来评估不同算法的performance。

4.方法

略.

参考