baidu在《MOBIUS: Towards the Next Generation of Query-Ad Matching in Baidu’s Sponsored Search》介绍了它们的query-ad matching策略。

摘要

为了构建一个高效的竞价搜索引擎(sponsored search engine),baidu使用一个3-layer的漏斗(funnel-shaped)结构,来从数十亿候选广告中筛选(screen)出数百万的广告并进行排序(sort),同时需要考虑低响应时延以及计算资源限制。给定一个user query,top matching layer负责提供语义相关的ad candidates给next layer,而底层的ranking layer则会关注这些ad的商业指标(比如:CPM、ROI等等)。在matching和ranking目标(objectives)间的明显分别会产生一个更低的商业回报。Mobius项目旨在解决该问题。我们尝试训练matching layer时,除了考虑query-ad相关性外,会考虑上CPM作为一个额外的optimization目标,通过从数十亿个query-ad pairs上直接预测CTR来完成。特别的,该paper会详述:当离线训练neural click networks,如何使用active learning来克服在matching layer上click history的低效(insufficiency),以及如何使用SOTA ANN search技术来更高效地检索ads(这里的ANN表示approximate NNS)。

1.介绍

baidu每天会处理数十亿的在线用户,来处理它们的多种queries。我们都知道,广告对于所在主流商业搜索引擎来说都是主要收入来源。本paper中,主要解释在baidu search ads系统上的最新尝试和开发。如图2所示,在搜索广告中它扮演着重要角色,会与user query相关的该广告会吸引点击,当它们的广告被点击时,广告主会支付广告费。baidu竞价搜索系统的目标是,在在线用户、广告主、付费搜索平台间形成一个闭环。

图片名称

图2

通常,付费搜索引擎会通过一个two-step process来展示广告。第一个step会检索给定一个query的相关广告,下一step会基于预测user engagement来对这些ads进行rank。由于在baidu中竞价搜索引擎的商用性,我们采用一个3-layer漏斗形结构的系统。如图3所示,top matching layer负责提供与一个user query以及user的profile相关的ad候选池到next layer。为了覆盖更多的语义相关广告,此处会大量使用expansion【1,3,4】以及NLP技术【2】。底层的ranking layer会更关注商业指标,比如:cost per mile(CPM=CTR x Bid),回报(ROI),等。

图片名称

图3

然而,在matching和ranking objectives间的不同,出于多种原因会导致一个更低的商业回报。给定一个user query,我们必须采用复杂模型,并花费大量计算资源在对数百或数千个ad候选进行ranking。可能令人失望的是,ranking模型上报分析得到:许多相关ads并没有提供高CPM,从而不会被展示。为了解决该问题,Baidu Search Ads建立“Mobius”项目,它的目标是建立关于付费搜索引擎的next generation query-ad matching system。之项目旨在统一不同的 learning objectives,包括:query-ad相关度以及许多其它商业指标,并符合:低延迟、计算资源的限制,以及对用户体验的较小不良影响。

本paper中,我们介绍了Mobius-V1: 它会让matching layer除query-ad相关度外,采用CPM作为一个额外的optimization objective。Mobius-V1能为数十亿user query&ad pair精准和快速预测CTR。为了达到该目标,我们必须解决以下主要问题:

  • 1.低效的点击历史(insufficient click history):由ranking layer所采用的原始的neural click模型会通过高频ads和user queries进行训练。它趋向于估计一个具有更高CTR的query-ad pair来展示,尽管它们具有低相关性。
  • 2.高计算/存储开销:Mobius期望预测关于数十亿user query&ad pairs的多个指标(包括:相关度、CTR、ROI等)。它天然会面对对计算资源更大开销的挑战。

为了解决上述问题,我们受active learning【34,41】的思想启发,首先设计了一个“teacher-student” framework来加大训练数据,为我们的大规模neural click model来为数十亿user query&ad pair预测CTR。特别的,一个离线数据生成器会负责要建人造query-ad pairs来给出数十亿的user queries和ad candidates。这些query-ad pairs会被一个teacher agent进行judge,它派生自原始的matching layer,并擅长于衡量关于一个query-ad pair的语义相关度。它可以在人造query-ad pairs上帮助检测bad cases(比如:高CTR但低相关度)。我们的neural click model,作为一个student,通过额外bad cases被教会(teach)来提升在长尾queries和ads上的泛化能力。为了节省计算资源,并满足低响应时延的要求,我们进一步采用大量最近的SOTA ANN search,以及MIPS(Maximum Inner Product Search)技术来高效索引和检索大量ads。

2.Baidu付费搜索的愿景(vision)

长期以来,漏斗结构是付费搜索引擎的一个经典架构。主要组件包含了:query-ad matching和ad ranking。query-ad matching通常是一个轻量级模块,它会measure一个user query与数十亿ads间的语义相关度。作为对比,ad ranking模块则关注商业指标(比如:CPM、ROI等),并使用复杂的neural模型来对数百个ad候选进行排序后展示。这种解耦结构是个明智选择,可以节约大量计算开销。另外,它可以帮助科学研究和软件工作上作为两个模块,分配给不同的团队可以最大化目标的提升。

百度的付费搜索使用一个3-layer的漏斗结构,如图3所示。top matching layer的最优化目标是最大化在所有query-ad pairs间的平均相关度:

…(1)

然而,根据我们在baidu付费搜索引擎表现上的长期分析,我们发现,在matching和ranking objectives间的区别/差异会导致更低的CPM(关键指标)。当在ranking layer的模型上报出:许多由matching layer提供的相关ads在搜索结果中并没有被展示,因为它们在估计时没有更高的CPM,这很令人不满意。

随着计算资源的快速增长,baidu搜索ads团队(凤巢)最近确立了Mobius项目,它的目标是baidu付费搜索的下一代query-ad matching系统。该项目的蓝图如图4所示:是统一多个学习目标,包括:query-ad相关度,以及许多其它商业指标,将它们统一到单个模块中,遵循:更低的响应延迟、有限的计算开销、以及对用户体验上较小的影响。

图片名称

图4

该paper主要是Mobius的第一版,它会首先尝试teach matching layer考虑在query-ad relevance之外,将CPM作为一个额外的最优化目标。这里我们将目标公式化:

…(2)

这里,如何为数十亿的(user-queries, ad候选) pairs精准预测CTR是个挑战。

3. 系统

3.1 Active-learned CTR模型

baidu付费搜索引擎使用DNN来进行CTR模型预测(G size)具有超过6年的历史。最近Mobius-V1采用一个新的架构。构建Mobius-V1的一种简单方法是,复用在ranking layer中的original CTR模型。它是一个大规模和稀疏的DNN,擅长emmorization。然而,在CTR预测上对于长尾部的user queries和ads它也会有一个严重的 bias。如图5所示,在搜索日志中,同一用户有两个queries:”Tesla Model 3”和”White Rose”。对于过去使用的漏斗架构,在query “tesla Model 3”和ad “Mercedes-Benz”间的相关性会在matching layer中有保证。接着,在ranking layer中的neural click模型会趋向于在query-ad pair预测一个更高的CTR。

图片名称

图5

根据我们在query log上的分析,ads和user queries具有长尾效应以及冷启动问题。因此,我们不能直接利用原始的neural click model来为数十亿长尾的user queries和ads精准预测CTR。解决这个问题的关键是:如何teach我们的模型学会:将”低相关但高CTR(low relevance but high CTR)”的query-ad pairs认为是bad cases

图片名称

算法1

为了解决这个问题,我们提出了使用在matching layer中的原始relevance judger作为teacher,来让我们的neural click model知道“low relevance” query-ad pairs。我们的neural click model,作为student,会以一个active learning的方式从有争议的bad cases上获得关于relevance的额外知识。图6通过一个流图展示了这种方式,算法1展示了使用active learning来teaching我们的neural click model的伪码。总之,active learning的迭代过程具有两个阶段:data augmentation和CTR model learning。特别的,我们会详细描述这两个phase。

图片名称

图6

数据扩量(data augmentation)的阶段会将一个来自query logs的click history的batch加载到一个data augmenter开始。data augmenter每次会接收query-ad pairs,它会将它们split成两个sets:一个query set和一个ad set。接着,我们会对两个sets使用一个cross join操作(\otimes)以便构建更多的user query & ad pairs。假设在click history的batch中存在m个queries和n个ads,那么data augmenter可以帮助生成个synthetic query-ad pairs。在列出所有可能的query-ad pairs后,relevance judger会参与其中,并负责对这些pairs的relevance进行评分。由于我们希望发现低相关度的query-ad pairs,会设置一个threold来保留这些pairs作为candidate teaching materials。这些low relevance query-ad pairs,会作为teaching materials首次被feed到我们的neural click model,接着每个pair会通过前一迭代的updated model进行预测CTR来进行分配。为了teach我们的3-classes(例如:click、unclick和bad)的neural click model学会认识“low relevance but high CTR”的query-ad pairs,我们可能直觉上会设置另一个threshold,以便过滤出大多数low CTR query-ad pairs。然而,我们考虑另一个选项来对augmented data的exploration和exploitation进行balance。我们会采用一个data sampler,它会选择并标记augmented data,被称为这些synthetic query-ad pairs的predicted CTRs。一旦一个query-ad pair被抽样成一个bad case作为我们的neural click network,这些pair会被标记为一个额外的category,例如:bad。

在学习我们的CTR模型的阶段,click/unclick history以及labeled bad cases两者都被添加到augmented buffer中作为训练数据。我们的neural click network是一个large-scale和multi-layer sparse DNN,它由两个subnets组成,例如:user query DNN和ad DNN。如图6所示,在左侧的user query DNN,会使用丰富的user profiles和queries作为inputs,而右侧的ad DNN会将ad embeddings作为features。两个subsets会生成一个具有96维的distributed representation,每个都会被划分成三个vectors(32 x 3)。我们对user query DNN和ad DNN间的vectors 的这三个pairs使用3次inner product操作,并采用一个softmax layer进行CTR预估。

总之,我们贡献了一种learning范式来离线训练我们的neural click model。为了提升在CTR预测上对于长尾上数十亿query-ad pairs的泛化能力,neural click model(student)可以actively query到relevence model (teacher)来进行labels。这种迭代式监督学习被称为active learning。

3.2 Fast Ads Retrieval

在baidu付费广告搜索中,我们使用如图6的DNN(例如:user query DNN和ad DNN)来各自获取queries和ads的embeddings。给定一个query embedding,Mobius必须从数十亿ad candidates中检索最相关并且最高CPM值的ads,如等式(2)。当然,为每个query穷举式地计算它不实际,尽管brute-force search理论上可以发现我们要找的所有ads(例如:100% ad recall)。online services通常具有严格的latency限制,ad retrieval必须在一个短时间内完成。因此,我们采用ANN search技术来加速retrieval过程,如图7所示。

图片名称

图7

如图6所示,mapping function会结合user vectors和ad vectors来计算cosine相似度,接着该cosine值传给softmax layer来生成最终的CTR。这种方式下,cosine值和CTR是线性相关的。在模型被学到之后,它很明显是正相关或负相关的。如果它是负相关,我们可以很轻易地将它转换成正相关,需要对ad vector加个负号就行。这样,我们可以将CTR预测问题reduce成一个cosine ranking问题,它是一个典型的ANN search setting。

ANN search的目标是:对于一个给定的query object,从一个大语料中检索到“最相似”的对象集合,只需要扫描corpus中的一小部分对象就行。这是个基础问题,已经在CS界广泛研究。通常,ANN的最流行算法是基于space-partitioning的思想,包括:tree-based方法、random hashing方法、quantiztion-based方法、random partition tree方法等。对于这类问题,我们发现,random partition tree方法相当高效。random partition tree方法的一个已知实现是:”ANNOY”。

在上面的解决方案中,business-related weight信息在user vector和ad vector matching之后被考虑。实际上,这个weight在ads ranking很重要。为了解释在ranking之前的这个weight信息,我们通过一个weighted cosine问题公式化成fast ranking过程,如下:

…(3)

其中:

  • w是business related weight
  • x是user-query embedding
  • y是ad vector

注意,weighted cosine会造成一个inner product seraching问题,通常被称为MIPS。

3.2.3 向量压缩(Vector Compression)

为数十亿ads存储一个高维浮点feature vector会花费大量的disk space,如果这些features需要在内存中进行fast ranking时会造成很多问题。一个常见的解法是,将浮点feature vectors压缩成random binary(或integer) hash codes,或者quantized codes。压缩过程可以减小检索召回到一个范围内,但它会带来具大的存储优势。对于当前实现,我们会采用一外quantization-based方法(像K-Means)来将index vectors进行聚类,而非对index中的所有ad vectors进行ranking。当一个query到来时,我们首先会寻找query vector所分配的cluster,接着获取来自index属于相同cluster的ads。PQ的思路是,将vectors分割成许多subvectors,每个split独立进行cluster。在我们的CTR模型中,我们会将query embeddings和ad embeddings同时split成三个subvectors。接着每个vector被分配到一个关于cluster centroids的triplet上。例如,对于一个billion-scale ads的multi-index,可以使用可能的cluster centroids。在Mobious-V1中,我们使用OPQ(Optimized Product Quantization)变种。

4.实验

参考

华为在《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被用户看到的概率
  • 用户在该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的点击数据集为 :

其中:

  • N是总样本数
  • 是样本i的feature vector,它包含了:user profile, item features和context信息
  • 是样本i的position信息
  • 是user feedback(如果user在该item进行点击,则;否则

我们会使用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,例如:。然后基于该concatenated feature vector训练一个CTR预测模型。

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

图片名称

图3 PAL framework vs. BASE

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

As a module

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

3.PAL Framework

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

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

如等式(1)所示:

…(1)

如果我们进一步假设:

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

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

…(2)

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

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

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

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

…(3)

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

…(4)

…(5)

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

3.在线实验

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

3.1 Datasets

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

3.2 Baseline

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

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

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

图片名称

图5 offline实验结果

3.3 AB test

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

Metrics

我们采用两种metrics来对比PAL和baselines的在线效果,称为:realistic CTR: 以及 realistic Conversion Rate:,其中#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,它通过的值降序排列。会采用Spearman’s Footrule来measure在两个rankings中的位移 (displacement),它被广泛用于measure两个rankings间的距离。我们定义了【ground truth ranking】与【由PAL或baselines生成的ranking 】在top-L上的距离,如下所示:

…(6)

其中:

  • u是在user group U中的一个具有popularity 的user
  • 是由model M为user u生成的推荐列表
  • :在ground truth ranking中的第i个item在推荐中的position 处

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

图片名称

图6 online分析

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

…(7)

其中,是user group U的size,是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。

参考

介绍

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 来获得embedding table 相应的row vector:

…(1)

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

其中,

  • 对于,元素,否则为0 ,其中是相应的items。

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

…(2)

其中,sparse matrix为:

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

2.1.2 Matrix Factorization

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

  • 来表示第i个商品,
  • 来表示第j个user

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

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

…(3)

其中:

  • 是第j个user对第i个product的rating,

接着,假设:,我们希望将full matrix的ratings 近似为矩阵乘法 。注意,W和V可以被解释成两个embedding tables,其中每一行表示在latent factor space中的一个user/product。这些embedding vectors的dot product会生成后续rating的一个有意义的预测,这对于FM和DLRM的设计来说是一个key observation

2.1.3 Factorization Machine

在经典问题中,我们希望定义一个预测函数:,从一个输入数据点到一个target label 上的预测。作为示例,我们可以通过定义 预测CTR,其中:+1表示点击,-1表示未点击。

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

…(4)

其中:

  • 1.
  • 2.
  • 3.
  • 4.的参数
  • 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 组成:

…(5)

其中:

  • 是weight matrix
  • :表示对于的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$上的兴趣,可以通过函数来描述。
  • 如果用户对该item很感兴趣,那么很大(positive);反之为很小(negative)

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

图片名称

图1

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

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

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

…(1)

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

…(2)

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

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

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

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

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

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

其中:

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

是当的期望增量。我们也定义了:

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

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

  • 1) 对于所有,有
  • 2) 对于所有,有

那么序列是weakly degenerate,比如:

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

定理2 (强退化: strong degeneracy)

假设定理1恒定,另外存在使得 ,存在一个,使得对于所有足够大的,有,对于所有足够小的。接着,或者

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

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

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

为了具体分析该问题,对于,我们会关注degenerate线性动态模型,例如:。接着,我们可以为求解,对于来获得:

Sufacing Assuption:

假设是size=m的candidate set。如果一个items子集 会产生positive degenerate (例如,对于所有, ),那么我们假设:存在一个时间,对于所有,S会占据根据值生成的top 的items。该由指数函数 的base value进行排序。

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

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

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

4.2 探索量(Amount of Exploration)

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

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

5.模拟实验

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

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

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

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

…(3)

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

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

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

6.1 Echo Chamber & Filter Bubble effect

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

在图2中,我们展示了user interest (左列)的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是基于优化的,因此我们可以看到对于有一个positive的degenerative dynamics。Optimal Oracle会直接在degeneration speed上进行优化,而不会在上,因此我们可以看到在上同时有一个positive和negative degeneration。Random Model也会在两个方向上对进行drifts,但以一个更慢的rate。然而,除了Random Model外,在所服务的top items上和top user interests会非常快速地收窄降到的最positive的reinfofced items上。

图片名称

图2

Degenracy Speed

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

图片名称

图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 ,直到5000 time steps,candidate pool sizes 。除了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 来对外服务top l items。candidate pool具有fixed size 。在图5中,我们从0到10来区分与直觉相反的是( Counter-intuitively),添加噪声到Oracle中会加速degeneration,因为对比起由排序的top l items的fixed set,添加噪声会使得具有更快degenerative的items会被偶然选中,更可能满足Surfacing Assumption。给定,我们可以看到,随着noise level的增长,在degeneracy speed上具有一个单调递增的阻尼效应(damping effect)。

图片名称

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

Growing Candidate Pool

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

图片名称

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

  • :在过去用户u评分过的items集合上的feature c的分布为:

…(1)

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

  • :推荐给user u的items list的feature c上的分布:

…(2)

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

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

…(3)

通过定义发现,H distance满足三角不等式。可以确保

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

….(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.方法

略.

参考