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 aM上的兴趣,可以通过函数μt:MR来描述。
  • 如果用户对该item很感兴趣,那么μt(a)很大(positive);反之为很小(negative)

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

图片名称

图1

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

  • 如果用户在timestep t上对一个item a进行点击,那么μt+1(a)>μt(a)
  • 如果a被展示但未被点击,则μt+1(a)<μt(a). (这里, ct{0,1}l可以被定义成所对应items的关于点击的indicator vector)

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

limtsup||μtμ0||2=,

…(1)

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

limt||μtμ0||2=

…(2)

下一节中,我们将展示,在μt的动态演进上的充分条件较缓和时,degeracy发生的强弱。

对于一个无限item set M的情况,存在多种方式来扩展上述定义。出于简化,我们只考虑使用μtμ02来替代等式(1)和等式(2)中的supaMμt(a)μ0(a),当M是有限时,它等于原始定义。

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

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

由于a是固定的,为了简化概念,我们将μt(a)替换成μt。给定at根据图1,μt+1是一个关于μt的函数(可能随机,由于μt+1依赖于ctμtct依赖于μt)。我们考虑当漂移量(drift) μt+1μt是一个非线性随机函数时的通用case;对于drift的deterministic模型在附录B中。

非线性随机模型(Nonlinear Stochastic Model)

μt+1=μt+f(μt,ξt)

其中:

  • 我们假设μ0R是固定的
  • (ξt)t=1是一个关于独立均匀分布的随机变量的无限序列,它引入噪声到系统中(例如:μt+1是一个μt的随机函数)
  • 函数 f:R×[0,1]是假设是可测的,但其它任意。通过U([0,1])来定义[0,1]上的均匀分布,假设:
ˉf(μ)=EξU([0,1])[f(μ,ξ)]

是当μt=μ的期望增量μt+1μt。我们也定义了:

F(μ,x)=PξU([0,1])(f(μ,ξ)x)

是increment的累积分布。μt的渐近行为依赖于f,但在mild假设下,系统会微弱(定理1)/较强(定理2)退化。

定理1(弱退化weak degeneracy)。假设F对于所有μR(μ,0)上是连续的,存在一个μoR,使得:

  • 1) 对于所有μμo,有F(μ,0)<1
  • 2) 对于所有μμo,有F(μ,0)>0

那么序列μt是weakly degenerate,比如:limtsupμt∣=

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

定理2 (强退化: strong degeneracy)

假设定理1恒定,另外存在cR使得 μt+1μtc,存在一个ϵ>0,使得对于所有足够大的μ,有f(μ)>ϵ,对于所有足够小的μf(μ)ϵ。接着,limittμt=或者limittμt=

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

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

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 θt的预测accuracy。然而,模型accuracy如何与greedy optimal at组合一起来影响degeneration的速度?对于exact predictions的极端示例,例如:θt=μt,我们会将这样的预测模型为“oracle model”。我们会在前提假设法(surfacing assumption)下讨论,oracle模型与greedily optimal action selection组合来生成快速的degeneracy。

为了具体分析该问题,对于μt(a)aM,我们会关注degenerate线性动态模型,例如:μt+1(a)=(1+k)μt(a)+b。接着,我们可以为μt(a)求解,对于1+k(a)∣>1来获得:

μt(a)=(μ0(a)+b(a)k(a)(1+k(a))tb(a)k(a)

Sufacing Assuption:

假设[m]={1,2,,m}是size=m的candidate set。如果一个items子集 S[m]会产生positive degenerate (例如,对于所有aS, μt(a)+),那么我们假设:存在一个时间τ>0,对于所有tτ,S会占据根据μt值生成的top S的items。该μt由指数函数 1+k(a)的base value进行排序。

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

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

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

4.2 探索量(Amount of Exploration)

考虑一种ϵ-random exploration,其中at总是从一个有限candidate pool [m]中(它在θt上具有一个uniform ϵ noise),根据θt=θt+U([ϵ,ϵ]),选择出top l items。

给定相同的模型序列θtϵ越大,系统退化(degenerate)越慢。然而,实际上,θ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 μt的domain会随时间t的增加而扩展(expands)。线性增加新items通常是一个避免退化的必要条件,因为在一个有限/任意次线性(sublinearly)增长的candidate pool上,通过鸽巢原理(pigeon hole principle),必须存在至少一个item,在最坏情况下它会退化(degenerate)(在定理2描述的通用条件下)。然而,有了一个至少线性增长的candidate pool M,系统会潜在利用任意item的最大服务次数来阻止degeneration。

5.模拟实验

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

我们为图1中一个推荐系统和一个用户间的交互创建了一个simulation。初始size=m0,在timestep t上的size=mt在timestep t时,一个推荐系统会从mt个items中,根据内部模型θt来选择top l 个items at=(a1t,,alt)服务给一个user

该user会独立考虑l items的每一个,并选择点击一个子集(也可能不点击,为空),从而生成一个size=l的binary vector ct,其中ct(ait)会给出在item ait上的user feedback,根据ct(ait)Bernoulli(ϕ(μt(ait))),其中ϕ是sigmoid function ϕ(x)=1/(1+ex)

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

μt+1(ait)μt(ait)={δ(ait)if ct(ait)=1 δ(ait)otherwise

…(3)

其中,function δ会从candidate set映射到R上。从定理2中,我们知道对于所有item,有μt±。在该实验中,我们设置l=5,并从一个均匀随机分布U([0.01,0.01])中抽样drift δ。对于所有items,用户的初始兴趣μ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 mt=m=100、time horizon T=5000的candidate pool上运行仿真,来检查echo chamber和filter bubble效应。

在图2中,我们展示了user interest μ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是基于μt优化的,因此我们可以看到对于μt有一个positive的degenerative dynamics。Optimal Oracle会直接在degeneration speed上进行优化,而不会在μt上,因此我们可以看到在μt上同时有一个positive和negative degeneration。Random Model也会在两个方向上对μ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上,对于不同的实验设定比较μtμ02/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 μtμ02/t,直到5000 time steps,candidate pool sizes m=10,102,103,104。除了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 θt=θt+U([ϵ,ϵ])来对外服务top l items。candidate pool具有fixed size m=100。在图5中,我们从0到10来区分ϵ与直觉相反的是( Counter-intuitively),添加噪声到Oracle中会加速degeneration,因为对比起由μ0排序的top l items的fixed set,添加噪声会使得具有更快degenerative的items会被偶然选中,更可能满足Surfacing Assumption。给定ϵ>0,我们可以看到,随着noise level的增长,在degeneracy speed上具有一个单调递增的阻尼效应(damping effect)。

图片名称

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

Growing Candidate Pool

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

图片名称

图6 5个模型的比较,它们使用growing candidate pools,具有不同的rates η=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的分布:

  • pu(cu):在过去用户u评分过的items集合Γ上的feature c的分布为:
pu(c|u)=iΓwu,ip(c|i)iΓwu,i

…(1)

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

  • qu(cu):推荐给user u的items list的feature c上的分布:
qu(c|u)=iwr(i)p(c|i)iwr(i)

…(2)

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

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

MCu(pu,qu)=H(pu,qu)=||puqu||22

…(3)

通过定义发现,H distance满足三角不等式。2可以确保H(pu,qu)1

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

MCG(p,q)=uGMCu(pu,qu)|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.方法

略.

参考

介绍

alibaba在《Personalized Re-ranking for Recommendation》介绍了一种reranking模型。

摘要

ranking是推荐系统的核心问题,通常,一个ranking函数会从labeled dataset中学到,并会为每个单独item产生一个ranking score。然而,它可能是次优的(sub-optimal),因为scoring function被应用在每个独立item上,没有显式考虑item间的相互影响,以及用户偏好/意图间的不同。因此,这里提出了一种个性化的re-ranking模型。通过直接使用一个已经存在的ranking feature vectors,提出的re-ranking模型可以很轻易地部署成在任意ranking算法之后跟着的一个follow-up模块。它会通过采用一个transformer结构来对在推荐列表中的所有items信息进行有效编码,来直接优化整个推荐列表。特别的,transformer使用一种self-attention机制,它直接建模在整个list中任意items pair间的关系。我们证实,通过引入pre-trained embedding来为不同用户学习个性化编码函数。在offline和online的实验结果上均有较大提升。

1.介绍

通常,在推荐系统中的ranking不会考虑在list列表中其它items(特别是挨着的items)的影响。尽管pairwise和listwise l2r方法尝试解决该问题,但它们只关注充分利用labels(比如:click-through data)来优化loss function,并没有显式建模在feature space中items间的相互影响。

一些工作[1,34,37]尝试显式建模items间的相互影响,重新定义由之前ranking算法给出的intial list,这被称为“re-ranking”。构建该scoring function的主要思路是:将intra-item patterns编码成feature space。state-of-the-arts的方法有:RNN-based(比如:GlobalRerank[37]和DLCM[1])。它们会将初始列表(intial list)按顺序feed给RNN-based结构,并在每个timestep上输出编码后的vector。然而,RNN-based方法对建模在list中items间的交叉的能力有限。之前编码的item的feature信息会沿着编码距离退化(degrade)。同时,由于并行化,transformer的编码过程比RNN-based方法更高效。

除了items间的交叉外,交叉的个性化编码函数可以被考虑用于re-ranking。对推荐系统进行re-ranking是user-specific的,决取于用户的偏好。对于一个对价格敏感的用户,在re-ranking模型中,对“price”特征间进行交叉更重要。常见的global encoding function可能不是最优的,因为它会忽略每个用户在特征分布间的不同。例如,当用户关注价格对比时,具有不同价格的相似items趋向于在list中更聚集。当用户没有明显的购买意图时,推荐列表中的items趋向于更分散。因此,我们在transformer结构中引入一种个性化模块来表示关于item interactions用户偏好和意图。在我们的个性化re-ranking模型中,可以同时捕获:在推荐列表中的items、以及用户间的交叉。

2.相关工作

我们的工作主要是,重新定义由base ranker给出的initial ranking list。在这些base rankers间,l2r是一种广泛使用的方法。l2r方法可以根据loss function分为三类:point-wise、pairwise、listwise。所有这些方法可以学习一个global scoring function,对于一个特定feature的权重会被全局学到。然而,这些features的weights应可以意识到:不仅items间的交叉、以及user和items间的交叉。

【1-3,37】的工作主要是re-ranking方法。它们使用整个intial list作为input,并以不同方式建模在items间的复杂依赖。[1]使用unidirectional GRU来将整个list的信息编码到每个item的表示。[37]使用LSTM、[3]使用pointer network,不仅编码整个list信息,也会由decoder生成ranked list。对于这些使用GRU or LSTM的方法来编码items间的依赖,encoder的能力通过encoding distance进行限制。在我们的paper中,我们使用transfomer-like encoder,它基于self-attention机制以O(1) distance来建模任意两个items间的交叉。另外,对于那些使用decoder来顺序生成ordered list的方法,它们不适合online ranking系统,因为需要有严格的延迟。由于sequential decoder使用在time t-1上选中的item作为input来在time t上选择item,它不能并列行,需要n倍的inferences,其中n是output list的长度。[2]提出了一种groupwise scoring function,它可以对scoring进行并列化,但它的计算开销很高,因为它会枚举在list中所有可能的item组合。

3.re-ranking模型

在本节中,我们首先给出了一些关于l2r以及re-ranking的先验知识。接着对问题公式化来求解。概念如表1所示。

表1:

l2r方法在ranking中被广泛使用,为推荐和信息检索生成一个ordered list。l2r方法会基于items的feature vector学习一个global scoring function。有了该global function,l2r方法会通过在candidate set中的每个item。该global function通常通过对以下loss L最小化得到:

L=rRl({yi,P(yi|xi;θ)|iIr})

…(1)

其中:

  • R是对于推荐所有用户请求的集合。
  • Ir是对于请求rR的items的candidate set
  • xi表示的是item i的feature space
  • yi是在item i上的label (例如:click or not)
  • P(yixi;θ)是由ranking model给出的对于参数θ的预测点击概率
  • l是通过yiP(yixi;θ)计算得到的loss

然而,对于学习一个好的scoring function来说,xi是不足够的。我们发现推荐系统的ranking应考虑以下额外信息:

  • (a)item-pairs间的相互影响 [8,35]
  • (b)users和items间的交叉(interactions)

在item-pairs间的相互影响,可以通过使用已经存在的LTR模型为请求r从inital list Sr=[i1,i2,,in]直接学到。[1][37][2][3]提出了方法来更好利用item-pairs间的相互信息。然而,很少研究去关注users和items间的interactions。item-pairs的相互影响,对于不同用户来说是不同的。在本paper中,我们引入了一种个性化矩阵(personlized matrix) PV来学习user-specific encoding function,它可以建模item-pairs间的个性化相互影响。模型的loss function可以被公式化成等式(2)。

L=rRl({yi,P(yiX,PV;ˆθ)|iSr})

…(2)

其中:

  • Sr是由之前ranking model给出的inital list
  • ˆθ是我们的re-ranking model的参数
  • X是在list中所有items的feature matrix

4.个性化re-ranking模型

在本节中,我们首先给出了关于PRM(Personalized Re-ranking Model)的总览。接着详细介绍每一部分。

4.1 模型架构

PRM的结构如图1所示。模型包含三个部分:

  • input layer
  • encoding layer
  • output layer

它会将由之前的ranking模型生成的关于items的intial list作为input,并输出一个re-ranked list。详细结构分挨个介绍。

图片名称

4.2 Input Layer

input layer的目的是,为在initial list中的所有items准备representations,并将它feed给encoding layer。首先,我们具有一个固定长度的intial sequential list S=[i1,i2,,in],它由之前的ranking方法给出。与之前ranking方法相同,我们具有一个raw feature matrix XRn×dfeature,在X中的每一行表示每个iS的item对应的raw feature vector xi

Personalized Vector(PV)

对两个items的feature vectors进行encoding,可以建模它们之间的相互影响,但这些影响进行扩展将会影响那些未知用户。因而需要学习user-specific encoding function。尽管整个intial list的representation可以部分影响用户的偏好,但对于一个强大的personlized encoding function来说它是不够的。如图1(b)所示,我们将raw feature matrix XRn×dfeature$PV \in R^{n \times d_{pv}}concatintermediateembeddingmatrixE’ \in R^{n \times (d_{feature} + d_{pv})}$$,如等式(3)。PV通过一个pre-trained model生成,它会在下一节中介绍。PV的performance增益可以由evaluation部分被介绍。

E=[i1;pvi1xi2;pvi2xin;pvin]

…(3)

position embedding(PE)

为了利用在intial list中的顺序信息,我们将一个position embedding PERn×(dfeature+dpv)注入到input embedding中。接着,该embedding矩阵可以用等式(4)计算。本paper中会使用一个可学习的PE,它的效果要比[28]中固定的position embedding要略微好些。

E=[i1;pvi1xi2;pvi2xin;pvin]+[ei1pei2pein]

…(4)

最后,我们使用一个简单的feed-forward网络来将feature matrix ERn×(dfeature+dpv转成ERn×d,其中:d是encoding layer中每个input vector中潜在维度(latent dimensionality)。E可以通过等式(5)公式化:

E=EWE+bE

…(5)

其中,WER(dfeature+dpv)×d是投影矩阵,bE是d维向量。

4.3 Encoding Layer

如图1(a)所示,encoding layer的目标是,将item-pairs间的相互影响、以及其它额外信息进行集成,这些额外信息包含:用户偏好、intial list S的ranking顺序。为了达到该目标,我们采用Transfomer-like encoder,因于Transformer已经在许多NLP任务中被证明是有效的,特别是在机器翻译中。Transformer中的self-attention机制特别适合我们的re-ranking任务,因为它可以直接建模任意两个items间的相互影响,忽略掉两者间的距离。没有了距离衰减(distance decay),Transfomer可以捕获更多在intial list中离得较远的items间的交叉。如图1(b)所示,我们的encoding模块包含了Nx个关于Transformer encoder的块(blocks)。每个块(block)(如图1(a)所示)包含了一个attention layer和一个Feed-Forward Network(FFN) layer。

Attention Layer

attention函数如等式(6)所示:

Attention(Q,K,V)=softmax(QKTd)V

…(6)

其中矩阵Q, K, V各自表示queries、keys和values。d是matrix K的维度,为了避免内积的大值。softmax被用于将内积值转化成为value vector V添加权重。在我们的paper中,我们使用self-attention,其中:Q, K和V从相同的矩阵进行投影。

为了建模更复杂的相互影响,我们使用multi-head attention,如等式(7)所示:

S=MH(E)=Concat(head1,,headh)WOheadi=Attention(EWQ,EWK,EWV)

…(7)

其中,WQ,WK,WVRd×dWORhd×dmodel是投影矩阵。h是headers的数目。h的不同值间的影响会在下一节被研究。

FFN(Feed-forward Network)

该position-wise FFN的函数主要是为了使用在input vectors不同维度间的非线性(non-linearity)和交叉(interacitons)来增强模型。

对Encoding Layer进行Stacking

这里,我们使用attention模块,后面跟着position-wise FFN作为一块(block)Transformer encoder。通过对多个blocks进行stacking,我们可以得到更复杂和高阶的相互信息(mutual information)。

4.4 Output Layer

output layer的函数主要为每个item i=i1,,in生成一个score。(如图1(b)所示Score(i))我们在softmax layer之后使用一个linear layer。softmax layer的output是每个item的点击概率,被标记为:P(yiX,PV;ˆθ)。我们使用P(yiX,PV,ˆθ)作为Score(i)来在one-step中对items进行re-rank。Score(i)的公式为:

Score(i)=P(yiX,PV;ˆθ)=softmax(F(Nx)WF+bF),iSr

…(8)

其中:

  • F(Nx)是Transformer encoder的Nx个blocks的output
  • WF是可学习的投影矩阵
  • bF是bias term
  • n是在intial list中的items数目

在训练过程中,我们使用click-through data作为label并最小化等式(9)的loss function:

L=rRiSryilog(P(yi|X,PV;ˆθ)

…(9)

4.5 个性化模块

在本节中,我们会引入该方法来计算个性化矩阵PV,它表示user和items间的interactions。使用PRM来学习PV的最简单办法是,通过re-ranking loss以end-to-end的方式进行学习。在re-ranking任务中学到的task-specific representation缺少用户的一般偏好。因此,我们可以利用一个pre-trained NN来产生用户个性化embeddings PV,它接着被用做PRM模型的额外features。pre-trained NN可以从平台的所有click-through logs上学到。图1(c)展示了pre-trained模型的结构。sigmoid layer会输出:在给定所有行为历史(Hu)和用户的side information时,关于item i、user u的点击概率(P(yiHu,u;θ)。用户的side information包括:gender、age和purchasing level等。模型的loss通过一个point-wise cross-entropy函数来计算,如等式(10)所示:

L=iD(yilog(P(yi|Hu,u;θ))+(1yi)log(1P(yi|Hu,u;θ)

…(10)

其中:

  • D是user u在平台上展示的items set。
  • θ是pre-trained model的参数矩阵
  • yi是item i的label

受[13]的启发,我们在sigmoid layer之前采用hidden vector作为personlized vector pvi(如图1c所示),feed到我们的PRM模型中。

图1c展示了pre-trained模型的可能架构,其它模型如:FM, FFM, DeepFM, DCN, FNN和PNN也可以做为生成PV的替代方法。

5.实验

参考

介绍

youtube在2019公布了它的MMoE多目标排序系统《Recommending What Video to Watch Next: A Multitask Ranking System》。

摘要

在本paper中,我们介绍了一个大规模多目标排序系统,用于在工业界视频分享平台上推荐下一个要观看的视频。该系统会面临许多挑战,包括:存在多个竞争性的排序目标(ranking objectives),以及在user feedback中的隐式选择偏差(implicit selection biases)。为了解决这些挑战,我们探索了多种软参数共享技术(soft-parameter sharing techniques),比如:Multi-gate Mixture-of-Experts,以便对多个排序目标进行有效最优化(optimize)。另外,我们会采用一个Wide&Deep框架来减缓选择偏差(selection biases)。我们演示了我们提出的技术可以在youtube推荐质量上产生有效提升。

介绍

在本paper中,我们描述了一个关于视频推荐的大规模排序系统。也就是说:在给定用户当前观看的一个视频的情况下,推荐该用户可能会观看和享受的下一个视频。通常推荐系统会遵循一个two-stage设计:candidate generation、ranking。该paper主要关注ranking。在该stage,推荐器会具有数百个候选,接着会应用一个复杂的模型来对它们进行排序,并将最可能观看的items推荐给用户。

设计一个真实世界的大规模视频推荐系统充满挑战:

  • 通常有许多不同的、有时甚至有冲突的待优化目标。例如,我们想推荐用户点击率高、愿与朋友共享的、包括观看高的视频
  • 在该系统中通常有隐式偏差(implicit bias)。例如,一个用户通常点击和观看一个视频,仅仅只因为它的排序高,而不是因为用户最喜欢它。因此,从当前系统的数据生成来进行模型训练会是有偏的,这会造成(feedback loop effect)效应[33]。如何有效和高效地学习减少这样的biases是个开放问题。

为了解决这样的挑战,我们为ranking system提出了一个有效的多任务神经网络架构,如图1所示。它会扩展Wide&Deep模型,通过采用Multi-gate Mixture-of-Experts(MMoE) [30]来进行多任务学习。另外,它会引入一个浅层塔结构(shallow tower)来建模和移除选择偏差。我们会应用该结构到视频推荐中:给定当前用户观看的视频,推荐下一个要观看的视频。我们在实验和真实环境中均有较大提升。

图1 我们提出的ranking系统的模型架构。它会消费user logs作为训练数据,构建Multi-gate Mixture-of-Experts layers来预测两类user behaviors,比如:engagement和satisfaction。它会使用一个side-tower来纠正ranking selection bias。在顶部,会组合多个预测到一个最终的ranking score

特别的,我们首先将我们的多任务目标分组成两类:

  • 1) 参与度目标(engagement objectives),比如:用户点击(user clicks),推荐视频的参与度
  • 2) 满意度目标(satisfaction objectives),比如:用户喜欢一个视频的程度,在推荐上留下一个评分

为了学习和估计多种类型的用户行为,我们使用MMoE来自动化学习那些跨潜在冲突的多目标共享的参数。Mixture-of-Experts[21]架构会将input layer模块化成experts,每个expert会关注input的不同部分。这可以提升从复杂特征空间(由多个模块生成)中学到的表示。

接着,通过使用多个gating network,每个objective可以选择experts来相互共享或不共享。

为了建模和减小来自有偏训练数据的选择偏差(selection bias,比如:position bias),我们提出了添加一个shallow tower到主模型中,如图1左侧所示。shallow tower会将input与selection bias(比如:由当前系统决定的ranking order)相关联,接着输出一个scalar作为一个bias项来服务给主模型的最终预测。该模型架构会将训练数据中的label分解成两部分

  • 1.从主模型中学到的无偏用户效用(unbiased user utility)
  • 2.从shallow tower学到的估计倾向评分(estimated propensity score)

我们提出的模型结构可以被看成是Wide&Deep模型的一个扩展,shallow tower表示Wide部分。通过直接学习shallow tower和main model,我们可以具有优点:学习selection bias,无需对随机实验resort来获取propensity score。

为了评估我们提出的ranking系统,我们设计了offline和live实验来验证以下的效果:

  • 1) 多任务学习
  • 2) 移除一个常见的selection bias (position bias)

对比state-of-art的baseline方法,我们展示了我们提出的框架的改进。我们在Youtube上进行实验。

主要贡献有:

  • 介绍了一种end-to-end的排序系统来进行视频推荐
  • 将ranking问题公式化成一个多目标学习问题,并扩展了Multi-gate Mixture-of-Experts架构来提升在所有objectives上的效果
  • 我们提出使用一个Wide&Deep模型架构来建模和缓和position bias
  • 我们会在一个真实世界的大规模视频推荐系统上评估我们的方法,以及相应的提升

2.相关工作

3.问题描述

本节,我们首先描述了推荐下一次要观看的视频的问题,我们引入了一个two-stage setup。

除了上述提到的使用隐式反馈来构建ranking systems挑战外,对于真实的大规模视频推荐问题,我们需要考虑以下因素:

  • 多模态特征空间(Multimodal feature space)。在一个context-aware个性化推荐系统中,我们需要使用从多模态(例如:视频内容、预览图、音频、标题、描述、用户demographics)来学习候选视频的user utility。从多模态特征空间中为推荐学习表示,对比其它机器学习应用来说是独一无二的挑战。它分为两个难点:
    • 1) 桥接来自low-level的内容特征中的语义gap,以进行内容过滤(content filtering)
    • 2) 为协同过滤学习items的稀疏表示
  • 可扩展性(Scalability)。可扩展性相当重要,因为我们正构建一个数十亿用户和视频的推荐系统。模型必须在训练期间有效训练,在serving期间高效运行。尽管ranking system在每个query会对数百个candidates进行打分,真实世界场景的scoring需要实时完成,因为一些query和context信息不仅仅需要学习数十亿items和users的表示,而且需要在serving时高效运行。

回顾下我们的推荐系统的目标是:在给定当前观看的视频和上下文(context)时,提供一个关于视频的ranked list。为了处理多模态特征空间,对于每个视频,我们会抽取以下特征(比如:视频的meta-data和视频内容信号)来作为它的表示。对于context,我们会使用以下特征(比如:人口统计学user demographics、设备device、时间time、地点location)。

为了处理可扩展性,如[10]描述相似,我们的推荐系统具有两个stages:候选生成、ranking。。。

3.1 候选生成

我们的视频推荐系统会使用多种候选生成算法,每种算法会捕获query video和candidate video间的某一种相似性。例如,一个算法会通过将query video的topics相匹配来生成candidates;另一个算法则会基于该视频和query video一起被观察的频次来检索candiate videos。我们构建了与[10]相似的一个序列模型通过用户历史来生成个性化候选视频。我们也会使用[25]中提到的技术来生成context-aware high recall relevant candiadtes。最后,所有的candidates都会放到一个set中,给ranking system进行打分。

3.2 Ranking

我们的ranking系统会从数百个candidates中生成一个ranked list。不同于candidate generation,它会尝试过滤掉大多数items并只保留相关items,ranking system的目标是提供一个ranked list以便具有最高utility的items可以展示在top前面。因此,我们使用大多数高级机器学习技术常用的NN结构,以便能足够的建模表现力来学习特征关联和utility关系。

4.模型结构

4.1 系统总览

我们的ranking system会从两类用户反馈数据中学习:

  • 1) engagement行为(比如:点击和观看)
  • 2) satisfaction行为(比如:喜欢(likes)和dismissals)

给定每个candidate,ranking system会使用该candidate、query和context的的特征作为输入,学习预测多个user behaviors。

对于问题公式,我们采用l2r的框架。我们会将ranking问题建模成:一个具有多个objectives的分类问题和回归问题的组合。给定一个query、candidate和context,ranking模型会预测用户采用actions(比如:点击、观看、likes和dismissals)的概率

为每个candidate做出预测的方法是point-wise的方法。作为对比,pair-wise或list-wise方法可以在两个或多个candidates的顺序上做出预测。pair-wise或list-wise方法可以被用于潜在提升推荐的多样性(diversity)。然而,我们基于serving的考虑主要使用point-wise ranking。在serving时,point-wise ranking很简单,可以高效地扩展到大量candidates上。作为比较,对于给定的candidates集合,pair-wise或list-wise方法需要对pairs或lists打分多次,以便找到最优的ranked list,限制了它们的可扩展性。

4.2 ranking objectives

我们使用user behaviors作为训练labels。由于用户可以对推荐items具有不同类型的behaviors,我们将我们的ranking system设计成支持多个objectives。每个objective的目标是预测一种类型的与user utility相关的user behavior。为了描述,以下我们将objectives分离成两个类别:engagement objectives和satisfaction objectives。

Engagement objectives会捕获user behaviors(比如:clicks和watches)。我们将这些行为的预测公式化为两种类型的任务:对于像点击这样行为的二元分类任务,以及对于像时长(time spent)相关的行为的回归任务。相似的,对于satisfaction objectives,我们将:与用户满意度相关的行为预测表示成二元分类任务或者回归任务。例如,像点击/like这样的行为可以公式化成一个二元分类任务,而像rating这样的行为被公式化成regression任务。对于二元分类任务,我们会计算cross entropy loss。而对于regression任务,我们会计算squared loss。

一旦多个ranking objectives和它们的问题类型被定下来,我们可以为这些预测任务训练一个multitask ranking模型。对于每个candidate,我们将它们作为多个预测的输入,并使用一个形如加权乘法的组合函数(combination function)来输出一个组合分(combined score)。该权值通过人工调参,以便在user engagements和user satisfactions上达到最佳效果。

4.3 使用MMoE建模任务关系和冲突

多目标的ranking systems常使用一个共享的bottom模型架构。然而,当任务间的关联很低时,这样的hard-parameter sharing技术有时会伤害到多目标学习。为了缓和多目标间的冲突,我们采用并扩展了一个最近发布的模型架构:MMoE(Multi-gate Mixture-of-Experts)【30】。

MMoE是一个soft-parameter sharing模型结构,它的设计是为了建模任务的冲突(conflicts)与关系(relation)。通过在跨多个任务上共享experts,它采用Mixture-of-Experts(MoE)结构到多任务学习中,而对于每个task也具有一个gating network进行训练。MMoE layer的设计是为了捕获任务的不同之处,对比起shared-bottom模型它无需大量模型参数。关键思路是,使用MoE layer来替代共享的ReLU layer,并为每个task添加一个独立的gating network。

对于我们的ranking system,我们提出在一个共享的hidden layer的top上添加experts,如图2b所示。这是因为MoE layer可以帮助学习来自input的模态信息(modularized information)。当在input layer的top上、或lower hidden layers上直接使用它时,它可以更好地建模多模态特征空间。然而,直接在input layer上应用MoE layer将极大增加模型training和serving的开销。这是因为,通常input layer的维度要比hidden layers的要更高

图2 使用MMoE来替换shared-bottom layers

我们关于expert networks的实现,等同于使用ReLU activations的multilayer perceptrons。给定task k、 prediction yk、以及最后的hidden layer hk,对于task k的具有n个experts output的MMoE layer为:fk(x),可以用以下的等式表示:

yk=hk(fk(x)),where  fk(x)=ni=1gk(i)(x)fi(x)

…(1)

其中:

  • xRd是一个lower-level shared hidden embedding
  • gk是task k的gating network
  • gk(i)(x)Rn是第i个entry
  • fi(x)是第i个expert

gating networks是使用一个softmax layer的关于input的简单线性转换。

gk(x)=softmax(Wgkx)

…(2)

其中:

WgkRn×d是线性变换的自由参数

与[32]中提到的sparse gating network对比,experts的数目会大些,每个训练样本只利用top experts,我们会使用一个相当小数目的experts。这样的设置是为了鼓励在多个gating networks间共享experts,并高效进行训练

4.4 建模和移除Position和Selection Baises

隐式反馈被广泛用于训练l2r模型。大量隐式反馈从user logs中抽取,从而训练复杂的DNN模型。然而,隐式反馈是有偏的,因为它由已经存在的ranking system所生成。Position Bias以及其它类型的selection biases,在许多不同的ranking问题中被研究和验证[2,23,41]。

在我们的ranking系统中,query是当前被观看过的视频,candidates是相关视频,用户倾向于点击和观看更接近toplist展示的视频,不管它们实际的user utility——根据观看过的视频的相关度以及用户偏好。我们的目标是移除从ranking模型中移除这样的position bias。在我们的训练数据中、或者在模型训练期间,建模和减小selection biases可以产生模型质量增益,打破由selection biases产生的feedback loop。

我们提出的模型结构与Wide&Deep模型结构相似。我们将模型预测分解为两个components:

  • 来自main tower的一个user-utility component
  • 以及来自shallow tower的一个bias component

特别的,我们使用对selection bias有贡献的features来训练了一个shallow tower,比如:position bias的position feature,接着将它添加到main model的最终logit中,如图3所示。

  • 在训练中,所有曝光(impressions)的positions都会被使用,有10%的feature drop-out rate来阻止模型过度依赖于position feature
  • 在serving时,position feature被认为是缺失的(missing)。

为什么我们将position feature和device feature相交叉(cross)的原因是:不同的position biases可以在不同类型的devices上观察到

图3 添加一个shallow side tower来学习selection bias(比如:position bias)

5.实验结果

本节我们描述了我们的ranking system实验,它会在youtube上推荐next watch的视频。使用由YouTube提供的隐式反馈,我们可以训练我们的ranking models,并进行offline和live实验。

Youtube的规模和复杂度是一个完美的测试。它有19亿月活用户。每天会有数千亿的user logs关于推荐结果与用户活动的交互。Youtube的一个核心产品是,提供推荐功能:为给定一个观看过的视频推荐接下来要看的,如图4所示。

图4 在youtube上推荐watch next

5.2.3 Gating Network分布

为了进一步理解MMoE是如何帮助multi-objective optimization的,我们为在每个expert上的每个task在softmax gating network中绘制了累积概率。

5.3 建模和减小Position Bias

使用用户隐式反馈作为训练数据的一个主要挑战是,很难建模在隐式反馈和true user utility间的gap。使用多种类型的隐式信号和多种ranking objectives,在serving时在item推荐中我们具有更多把手(knobs)来tune以捕获从模型预测到user utility的转换。然而,我们仍需要建模和减小在隐式反馈中普遍存在的biases。例如:在用户和当前推荐系统交互中引起的selection biases。

这里,我们使用提出的轻量级模型架构,来评估如何来建模和减小一种类型的selection biases(例如:position bias)。我们的解决方案避免了在随机实验或复杂计算上花费太多开销。

5.3.1 用户隐反馈分析

为了验证在我们训练数据中存在的position bias,我们对不同位置做了CTR分析。图6表明,在相对位置1-9的CTR分布。所图所示,我们看到,随着位置越来越低,CTR也会降得越来越低。在更高位置上的CTR越高,这是因为推荐更相关items和position bias的组合效果。我们提出的方法会采用一个shallow tower,我们展示了该方法可以分离user utility和position bias的学习。

图6 位置1-9的CTR

5.3.2 Baseline方法

为了评估我们提出的模型架构,我们使用以下的baseline方法进行对比。

  • 直接使用position feature做为一个input feature:这种简单方法已经在工业界推荐系统中广泛使用来消除position bias,大多数用于线性l2r rank模型中。
  • 对抗学习(Adversarial learning):受域适应(domain adaptation)和机器学习公平性(machine learning fairness)中Adversarial learning的广泛使用的启发,我们使用一个相似的技术来引入一个辅助任务(auxiliary task),它可以预测在训练数据中的position。随后,在BP阶段,我们不让梯度传递到主模型(main model)中,以确保主模型的预测不依赖于position feature。

5.3.3 真实流量实验结果

表2展示了真实流量实验结果。我们可以看到提出的方法通过建模和消除position biases可以极大提升参与度指标。

5.3.4 学到的position biases

图7展示了每个position学到的position biases。从图中可知,越低的position,学到的bias越小。学到的biases会使用有偏的隐式反馈(biased implicit feedback)来估计倾向评分(propensity scores)。使用足够训练数据通过模型训练运行,可以使我们有效学到减小position biases。

图7 每个position上学到的position bias

5.4 讨论

参考

youtube在2019发布了它的双塔模型《Sampling-Bias-Corrected Neural Modeling for Large Corpus Item Recommendations》:

介绍

在许多服务上(视频推荐、app推荐、在线广告定向),推荐系统帮助用户发现感兴趣内容。在许多情况下,这些系统在一个低延时的条件下,会将数十亿用户与一个相当大的内容语料(数百万到数十亿)相连接。常用的方法是retrieval-and-ranking策略,这是一个two-stage系统。首先,一个可扩展的retrieval模型会从一个大语料中检索出一小部分相关items,接着一个成熟的ranking模型会对这些retrieved items基于一或多个目标(objectives: 比如clicks或user-ratings)进行rerank。在本文中,主要关注retrieval system。

给定一个{user, context, item}三元组,构建一个可扩展的retrieval模型的一个常用方法是:

  • 1) 分别为{user,context}和{item}各自学习query和item representations
  • 2) 在query和item representations间使用一个simple scoring function(比如:dot product)来得到对该query合适的推荐

context通常表示具有动态特性的variables,比如:天时长(time of day),用户所用设备(devices)。representation learning问题通常有以下两个挑战:

  • 1) items的corpus对于工业界规模的app来说相当大
  • 2) 从用户反馈收集得到的训练数据对于某些items相当稀疏

这会造成模型预测对于长尾内容(long-tail content)具有很大variance。对于这种cold-start问题,真实世界系统需要适应数据分布的变化来更好面对新鲜内容(fresh content)

受Netflix prize的启发,MF-based modeling被广泛用在构建retrieval systems中学习query和item的latent factors。在MF框架下,大量推荐研究在学习大规模corpus上解决了许多挑战。常见的思路是,利用query和item的content features。在item id外,content features很难被定义成大量用于描述items的features。例如,一个video的content features可以是从video frames中抽取的视觉features或音频features。MF-based模型通常只能捕获features的二阶交叉,因而,在表示具有许多格式的features collection时具有有限阶(power)。

在最近几年,受deep learning的影响,大量工作采用DNNs来推荐。Deep representations很适合编码在低维embedding space上的复杂的user states和item content features。在本paper中,采用two-tower DNNs来构建retrieval模型。图1提供了two-tower模型构建的图示,左和右分别表示{user, context}和{item}。two-tower DNN从multi-class classification NN(一个MLP模型)泛化而来[19],其中,图1的right tower被简化成一个具有item embeddings的single layer。因而,two-tower模型结构可以建模当labels具有structures或content features的情形。MLP模型通常使用许多来自一个fixed的item语料表中sampled negatives进行训练。作为对比,在使用了deep item tower后,对于计算所有item embeddings来说,由于item content features以及共享的网络参数,在许多negatives上进行抽样并训练通常是无效的。

图片名称

图1 一个2-tower DNN模型,它会学习query和candidate表示

我们考虑batch softmax optimization:其中item probability会通过在一个random batch上的所有items上计算得到。然而,在我们的实验中所示:batch softmax具有sampling bias倾向,在没有任何纠正的情况下,可能会严重限制模型效果。importance sampling和相应的bias reduction在MLP模型[4,5]中有研究。受这些工作的启发,我们提出了使用estimated item frequency的batch softmax来纠正sampling bias。对比于MLP模型,其中output item vocabulary是固定的(stationary),我们会根据vocabualary和分布随着时间变化来target streaming data。我们提出了一种新算法通过gradient descent来概述(sketch)和估计(estimate) item freqency。另外,我们使用bias-corrected modeling,并将它扩展到在youtube推荐上构建个性化retrieval system。我们也引入了一个sequential training strategy,用来吸收streaming data,与indexing和serving组件一起工作。

主要4个contributions:

  • Streaming Frequency Estimation:我们提出了一个新算法,根据vocabulary和分布偏移(distribution shifts)来估计来自data stream的item frequency。我们提供了分析结果来展示该estimation的variance和bias。我们也提供了仿真来演示我们的方法在捕捉数据动态性上的效率
  • Modeling Framework:我们提供了一个通用的建模框架来构建大规模检索系统。特别的,我们针对batch softmax会在cross entropy loss中引入estimated item frequency来减小在in-batch items上的sampling bias
  • Youtube recommendation:我们描述了如何使用modeling framework来为youtube 推荐构建一个大规模的检索系统。我们引入了end-to-end 系统,包括:training、indexing、serving组件
  • offline和Live实现:我们在两个真实数据集上执行offline实验,并演示了samping bias correction的效果。我们也展示了为youtube构建的索引系统,并在真实流量实验上提升了engagement指标。

2.相关工作

2.1 content-aware&Neural Recommenders

对于提升泛化(generalization)和解决cold-start问题来说,使用users和items的content features很关键。一些研究【23】在经典MF框架上采用content features。例如,generalized MF模型(比如:SVDFeatuer和FM),可以被用来采用item content features。这些模型能捕获bi-linear,比如:second-order的特征交叉。在最近几年,DNNs对于提升推荐的accuracy很有效。对比于传统因子分解方法,DNNs由于具有高度非线性,可以很有效地博获复杂的特征交叉。He [21]直接采用CF、NCF架构来建模user-item interactions。在NCF结构中,user和items embeddings被concatenated并被传入一个multi-layer NN来获得最终预测。我们的工作与NCF有两方法区别:

  • 1) 我们利用一个two-tower NN来建模user-item interactions,以便可以在sub-linear时间内实现在大语料items的inference。
  • 2) 学习NCF依赖于point-wise loss(比如:squared或log loss),而我们会引入multi-class softmax loss以及显式的model item frequency。

在其它work中,Deep RNN(比如:LSTM)被用于采用时序信息和推荐的历史事件,例如:[12,14]。除了单独的user和item representations外,另一部分设计NN的工作主要关注于学习rank systems。最近,multi-task learning是主要技术,对于复杂推荐器上优化多目标【27,28】。Cheng[9]引入了一个wide-n-deep framework来对wide linear models和deep NN进行jointly training。

2.2 Extreme classification

在设计用于预测具有大规模输出空间的labels的模型时,softmax是一个常用函数。从语言模型到推荐模型的大量研究,都关注于训练softmax多分类模型。当classes的数目相当大时,大量采用的技术是:抽样classes的一个subset。Bengio[5]表明:一个好的sampling distribution应该与模型的output distribution相适配。为了避免计算sampling distribution的并发症,许多现实模型都采用一个简单分布(比如:unigram或uniform)作为替代。最近,Blanc[7]设计了一个有效的adaptive kernel based的sampling方法。尽管sampled softmax在许多领域很成功,但不能应用在具有content features的label的case中。这种case中的Adaptive sampling仍然是一个开放问题。许多works表明,具有tree-based的label结构(比如:hierarchical softmax),对于构建大规模分类模型很有用,可以极大减小inference time。这些方法通常需要一个预定义的基于特定categorical attributes的tree structure。因此,他们不适用于包含大量input features的情况。

2.3 two-tower模型

构建具有two tower的NN在NLP中最近很流行,比如: 建模句子相似度(sentence similarities),response suggestions,text-based IR等。我们的工作主要有,在大规模推荐系统上构建two-tower模型的有效性验证。对比于许多语言任务,我们的任务在更大corpus size上,这在Youtube这样的场景下很常见。通过真实实验发现,显式建模item frequency对于在该setting中提升retrieval accuracy很重要。然而,该问题并没有很好地解决。

3.模型框架

考虑推荐问题的一个常见设定,我们具有queries和items的一个集合。queries和items通过feature vectors {xi}Ni=1{yi}Mj=1表示。这里,xiX,yiY,是多种features的混合(比如:sparse IDs和dense features),可以在一个非常高维的空间中。这里的目标是:为给定一个query检索一个items的subset。在个性化场景中,我们假设:user和context在xi中被完全捕获。注意,我们从有限数目的queries和items开始来解释该情形。我们的模型框架没有这样的假设。

我们的目标是构建具有两个参数化embedding functions的模型:

u:X×RdRk,v:Y×RdRk

将模型参数θRd、query和candidates的features映射到一个k维的embedding space上。如图1所示,我们关注于的u, v通过两个DNN表示的case。模型的output是两个embeddings的inner product,命名为:

s(x,y)=<u(x,θ),v(y,θ)>

目标是,从一个具有T个样本的训练集中学习模型参数θ

T:={(xi,yi,Ri)}Ti=1

其中,(xi,yi)表示query xi和item yi的query,riR是每个pair相关的reward

相应的,retrieval问题可以被看成是一个具有continuous reward的multi-class分类问题。在分类任务中,每个label的重要性等价,对于所有postive pairs ri=1在recommenders中,ri可以被扩展成:对于一个特定candidate捕获到的user engagement的不同程度。例如,在新闻推荐中,ri可以是一个用户花费在特定某个文章上的时间。给定一个query x,对于从M个items {yi}Mj=1选择候选y的概率分布,常用的选择是基于softmax function,例如:

P(y|x;θ)=es(x,y)j[M]es(x,yj)

…(1)

接着进一步加入rewards ri,我们考虑上下面的weighted log-likelihood作为loss function:

LT(θ):=1Ti[T]rilog(P(yi|xi;θ))

…(2)

当M非常大时,在计算partition function时很难包括所有的candidate examples,例如:等式(1)中的分母。我们主要关注处理streaming data。因此,与从一个固定corpus中抽样得到负样本(negatives)的case进行训练MLP模型不同,对于从相同batch中的所有queries来说,我们只考虑使用in-batch items[22]作为负样本(negatives)。更确切地说,给定一个关于B pairs {(xi,yI,ri)}Bi=1的mini-batch,对于每个i[B],该batch softmax是:

PB(yi|xi;θ)=es(xi,yi)i[B]es(xi,yi)

…(3)

在我们的目标应用中,in-batch items通常从一个power-law分布中抽样得到。因此,等式(3)在full softmax上会引入了一个大的bias:流行的items通常会过度被当成negatives,因为概率高。受在sampled softmax model[5]中logQ correction的启发,我们将每个logit s(xi,yi)通过下式进行纠正:

sc(xi,yi)=s(xi,yj)log(pj)

这里,pj表示在一个random batch中item j的sampling概率。

有了该correction,我们有:

PcB(yi|xi;θ)=esc(xi,yi)esc(xi,yi)+j[B],jiesc(xi,yi)

接着将上述term代入到等式(2),产生:

LB(θ):=1Bi[B]rilog(PcB(yi|xi;θ))

…(4)

它是batch loss function。使用learning rate γ运行SGD会产生如下的参数更新:

θθγB(θ)

…(5)

注意,LB不需要一个关于queries和candidates的固定集合。相应的,等式(5)可以被应用到streaming training data上,它的分布随时间变化。我们提出的方法,详见算法1.

图片名称

算法1

最近邻搜索(NN Search):一旦embedding function u, v被学到,inference包含两个step:

  • 1) 计算query embedding:u(x,θ)
  • 2) 在item embeddings(通过embedding function v预计算好)上执行最近邻搜索

另外,我们的模型框架提供了选项,可以在inference时选择任意items。不再计算在所有items上的dot product,低时耗retrieval通常基于一个基于hashing技术高效相似度搜索系统,特别的,高维embeddings的compact representations通过quantization、以及end-to-end learning和coarse和PQ来构建。

归一化(Normalization)和温度(Temperature)

经验上,我们发现,添加embedding normalization,比如:u(x,θ)u(x,θ)u(x,θ)2,u(y,θ)v(y,θ)v(y,θ)2可以提升模型的trainability,从而产生更好的retrieval quality

另外,一个Temperature τ被添加到每个logit上来对predictions进行削尖(sharpen):

s(x,y)=<u(x,θ),v(y,θ)>τ

实际上,τ是一个超参数,用于调节最大化检索指标(比如:recall或precision)。

4.Streaming Frequancy估计

在本节中,我们详细介绍在算法1中所使用的streaming frequency estimation。

考虑到关于random batches的一个stream,其中每个batch包含了一个items集合。该问题为:估计在一个batch中每个item y的hitting的概率。一个重要的设计准则是:当存在多个training jobs(例如:workers)时,具有一个完全分布式的估计来支持dstributed training。

在单机或分布式训练时,一个唯一的global step,它表示trainer消费的data batches的数目,与每个sampled batch相关。在一个分布式设定中,global step通常通过parameter servers在多个workers间同步。

5. Youtube的Neural检索系统

我们在Youtube中使用提出的模型框架。该产品会基于在某个用户观看的某个video上生成视频推荐。推荐系统包含两个stages:nomination(或:retrieval)、ranking。在nomination stage,我们具有多个nominators,每个nomiator都会基于一个user和一个seed video生成成百上千的视频推荐。这些videos会按顺序打分,并在下游的一个NN ranking模型中进行rerank。在本节中,我们关注在retrieval stage中一个额外nominator。

5.1 模型总览

图片名称

图2

我们构建的youtube NN模型包含了query和candidates。图2演示了总的模型结构。在任意时间点上,用户正观看的某个video,(例如:seed video),提供了一个关于用户当前兴趣的一个很强信号。因此,我们会利用 关于seed video的features一个大集合以及用户观看历史。candidate tower的构建用来从candidate video features中学习。

training label。视频点击(video clicks)被用于正样本(positive labels)。另外,对于每个click,我们构建了一个reward ri来表示关于该video的不同程度的user engagement。另一方面,ri=1表示观看了整个视频。reward被用于example weight,如等式(4)所示。

VIdeo Features。video features在categorical和dense features中同时被用到。categorical features的样本包含了:Video Id和Channel Id。对于这两个entities的每个来说,会创建一个embedding layer来将categorical feature映射到一个dense vector上。通常,我们会处理两种categorical features。一些features(例如:Video Id)在每个video上具有一个categorical value,因此,我们具有一个embedding vector来表示它们。另外,一个feature(比如:Video topics)可以是一个关于categorical values的sparse vector,最终的embedding表示在sparse vector中的values的任一个的embeddings的加权求和。为了处理out-of-vocabulary entities,我们会将它们随机分配到一个固定的hash buckets集合中,并为每一个学习一个embedding。Hash buckets对于模型很重要,可以捕获在Youtube中的新实体(new entities),特别是5.2节所使用的sequential training。

User Features。我们使用一个user的观看历史来捕获在seed video外的user兴趣。一个示例是,用户最近观看过的k个video ids的一个sequence。我们将观看历史看成是一个bag of words (BOW),通过video id embeddings的平均来表示它。在query tower中,user和seed video features在input layer进行融合(fuse),接着传入到一个feed forward NN中。

对于相同类型的IDs,embedding可以在相关的features间共享。例如,video id embeddings的相同集合被用于:seed video、candidate video以及用户之前观看过的video。我们也做了不共享embedding的实验,但没有观看大大的模型效果提升。

5.2 Sequential training

我们的模型在tensorflow上实验,使用分布式GD在多个workers和parameter servers上训练。在Youtube中,新的training data每天都会生成,training datasets会每天重新组织。该模型训练会以如下方式使用上sequential结构。trainer会从最老的training examples开始顺序消费数据,直到最近天的训练数据,它会等待下一天的训练数据到达。这种方式下,模型可以赶得上最新的数据分布偏移(shift)。训练数据本质上由trainer以streaming方式消费。我们使用算法2 (或算法3)来估计item frequency。等式(6)的在线更新使得模型可以适应新的frequency分布。

图片名称

算法2

图片名称 算法3

5.3 Indexing和模型serving

在retrieval系统中的index pipeline会为online serving周期性地创建一个tensorflow savemodel。index pipeline会以三个stages构建:candidate example generation、embedding inference、embedding indexing,如图3所示。在第1个stage,会基于特定准则从youtube corpus中选中的videos集合。它们的features被fetched、以及被添加到candidate examples中。在第二个stage,图2的right tower用来计算来自candidate examples的embeddings。在第三个stage,我们会基于tree和quantized hashing技术来训练一个tensorflow-based embedding index model。

图片名称

图3

6.实验

本节中,我们展示了item frequency estimation的模型框架的有效性。

6.1 Frequency估计的仿真

为了评估算法2&3的有效性。我们开始一个仿真研究,我们首先使用每个提出的算法来拟合一个固定的item分布,接着在一个特定step后变更分布。为了更精准,在我们的setting中,我们使用一个关于M items的固定set,每个item根据概率qii2(其中:i[M],iqi=1)进行独立抽样。

。。。略

参考