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∈M上的兴趣,可以通过函数μt:M→R来描述。
- 如果用户对该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−μ0‖2=(∑a∈M(μt(a)−μ0(a))2)1/2是否可以变得任意大?如果满足下面条件,几乎必然用户的兴趣序列μt被称为“弱退化(weakly degenerate)”(证明见附录):
limt→∞sup||μ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−μ0‖2来替代等式(1)和等式(2)中的supa∈M∣μt(a)−μ0(a)∣,当M是有限时,它等于原始定义。
3. 用户兴趣动态性——Echo Chamber
由于items通常以多样的类目(t diverse categorie)的方式呈现,我们简化猜想:它们间是相互独立的。通过对于所有t (例如:M={a}),设置l=1和a1t=a,我们可以移除推荐系统的影响,并单独考虑用户的动态性( Dynamics)。这使得我们分析echo chamber effect:如果item a被无限次推到,兴趣 μt(a)会发生什么?
由于a是固定的,为了简化概念,我们将μt(a)替换成μt。给定at,根据图1,μt+1是一个关于μt的函数(可能随机,由于μt+1依赖于ct和μt,ct依赖于μt)。我们考虑当漂移量(drift) μt+1−μt是一个非线性随机函数时的通用case;对于drift的deterministic模型在附录B中。
非线性随机模型(Nonlinear Stochastic Model)
μt+1=μt+f(μt,ξt)其中:
- 我们假设μ0∈R是固定的
- (ξt)∞t=1是一个关于独立均匀分布的随机变量的无限序列,它引入噪声到系统中(例如:μt+1是一个μt的随机函数)
- 函数 f:R×[0,1]是假设是可测的,但其它任意。通过U([0,1])来定义[0,1]上的均匀分布,假设:
是当μt=μ的期望增量μt+1−μt。我们也定义了:
F(μ,x)=Pξ∼U([0,1])(f(μ,ξ)≤x)是increment的累积分布。μt的渐近行为依赖于f,但在mild假设下,系统会微弱(定理1)/较强(定理2)退化。
定理1(弱退化weak degeneracy)。假设F对于所有μ∈R在(μ,0)上是连续的,存在一个μo∈R,使得:
- 1) 对于所有μ≥μo,有F(μ,0)<1
- 2) 对于所有μ≥μo,有F(μ,0)>0
那么序列μt是weakly degenerate,比如:limt→∞sup∣μt∣=∞
该假设保证了在任意闭区间内,存在一个常数概率,当分别从μo的左侧/右侧开始时,该random walk会逃离区间左侧/右侧。在stronger condition下,可以保证random walk的分散性(divergence)。
定理2 (强退化: strong degeneracy)
假设定理1恒定,另外存在c∈R使得 ‖μt+1−μt‖≤c,存在一个ϵ>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)的a∈M,我们会关注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))t−b(a)k(a)Sufacing Assuption:
假设[m]={1,2,⋯,m}是size=m的candidate set。如果一个items子集 S⊂[m]会产生positive degenerate (例如,对于所有a∈S, μ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+e−x)。
接着该系统会基于过往行为(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−μ0∣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 ‖‖μt−μ0‖‖2/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
我们通过计算supa∈M∣μt(a)−μ0(a)∣/t,将degeneracy speed的定义扩展到一个有限的candidate pool上。由于degeneracy speed对于所有5种模型不是渐近线性的(asymptotically linear),我们会在10000个time steps上直接检查sup distance supa∈M∣μ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。