rank fusion介绍

Reading time ~1 minute

《Web Metasearch: Rank vs. Score Based Rank Aggregation Methods》提出了rank fusion的问题。

1.介绍

rank fusion的问题是,给定多个judges的独立ranking偏好(一个ranking是一个items集合的线性顺序),计算一个“一致的(consensus)”ranking。该ranking fusion问题出现在许多情况下,一个著名的场景是metasearch:metasearch会处理由多个search engines对于一个给定query所返回的多个result lists组合,其中,在result list中的每个item对于各自的search engine是有序的,并且有一个相关分值。

搜索引擎们会帮助人们定位与用户信息相关的信息,但仍有一些不足:

  • i) 检索web数据是一个耗时的任务。由于web内容变化很快,每个search engine必须在覆盖率(coverage)间做个trade-off,例如,web文档的数据会与整个web以及更新频率(例如,在完整数据库的后续re-indexing间发生的时间)有关。
  • ii) 有许多信息源
  • iii) 对于一些搜索引擎,广告商付费越多,在search results上的rank会越高,这被称为:“pay-for-placement”,这在precesion上会有平均损失
  • iv) search engines会有作弊(spamming)

由于上述这些限制,必须引入metasearch engines来提升检索效果。

ranking fusion的理想场景是,每个judge(search engine)给出对所有alternative items一个完整顺序。不幸的是,在metasearch中这不太现实,有两个原因:

  • i) search engines的coverage是不同的
  • ii) search engines会限制访问top 100 or 1000个ranked items

因此,rank aggregation必须可以处理具有有限数目个entires的每个ranking。当然,如果rankings间没有重叠项,。。。设计ranking fusion的一个挑战是,当在每个ranking中的top 几百个/上午个items间存在有限个重合项(但non-trivial)。

。。。

2.ranking fusion方法

对于rank-ordered lists进行合并,存在许多方法。最基础的,他们会使用来自ranked lists中已经提供的信息。在大多数情史中,策略依赖于以下信息:

  • i) 顺序排序(irdinal rank):rank list中的一个item分配一个顺序
  • ii) 得分(score):在rank list中分配给每个item的得分

在score-based方法中,items会根据rank lists中的scores进地rank,或者对这些scores做一些转换(transformation)[1,4,8,9,12,13,17,18];而在rank-based方法中,items会根据rank lists中的rank重新排序,或者对这些ranks做一些转换[1,7,12,19]。另一种正交去重的rank fusion方法则依赖于训练数据(比如:Bayes-fuse方法[1],或者线性组合方法[17],或者偏好rank组合方法[8])。基它一些方法基于ranked items的内容。

2.1 前提

首先看一些基本定义。假设:

  • U是一个items集合,称为“universe”。
  • 是一个rank list,它与U有关,是关于子集的一个排序,例如:,对于每个是在S上的顺序关系.

如果 出现在中,写成表示i的position或rank。我们假设,通过对每个分配一个唯一的id,没有对普适性有损失。

。。。

2.2 Fusion方法

本节中,我们将讲述分析的ranking fusion方法。考虑一个包含了n个rankings的集合。假设:

  • U表示在中的items的union,例如:
  • 表示ranking(被称为fused ranking或fused rank list),它是一个rank fusion方法应用到在R中的rank lists之后得到的结果。

为了彻底说明,它足够决定分值(称为:fused score)(对于每个item ),因为会根据的值递减进行排序。我们认为:

  • 如果两个fused ranking 相等的(equal),则:
  • 如果等价的(equivalent),那么对于,有(他们具有相同的顺序)

当然,equality意味着equivalence,但反过来不成立。

2.2.1 线性组合

Fox[9]提出的ranking fusion方法基于对每个item的归一化得分(normalised score)采用不加权(unweighted)的min, max或sum。另外,Lee[12]解决了rank取代score的case。两种方法如下:

从[9,12]的测试结果看,CombMNZ被认为是最好的ranking fusion方法,它的效果要稍好于CombSUM。根据Lee的实验,CombMNZ基于该事实:“不同搜索引擎返回(return)相似的相关文档集合,但检索(retrieve)不同的不相关文档集合”。确实,CombMNZ组合函数会对常见文档进行大的加权。

。。。

2.2.1.1 Borda Count

Borda的方法[2,14]是一个基于ranks的voting方法,例如,一个candidate出现在每个voter的ranked list中,则会为相应的ranks分配一个weight。计算上非常简单,因为实现是线性的。Borda Count (BC)方法在rank fusion问题中被引入,并以如下方式运转。每个voter会对一个关于c个candidates的固定集合以偏好顺序进行rank。对于每个voter,会给top ranked candidate为c分,第二个ranked candidate会得到c-1分,以此类推。在unranked candidates间则均匀分配剩余得分。candidates会以总分(total points)的递减顺序进行rank。正式的,该方法与以下过程等价:对于每个item 以及rank list ,Borda归一化权重为(定义1)。fused rank list 根据Borda score 的顺序排序,其中在中的一个item 被定义为:

…(6)

相应的,BC等价于CombSUM方法组合上Borda rank normalisation,(例如:)。Aslam[1]也考虑过一种Weighted Borda Count,其中,在对归一化Borda weights求和的部分,会使用这些weights的一个线性组合。

2.2.2 Markovchain-based方法

[7]中提出一种关于rank fusion的有意思的方法,它基于Markov chains实现。一个系统的一个(齐次:homogeneous)Markov chain可以通过一个状态集以及一个的非负随机矩阵M(例如:每行的求和为1)来指定。该系统从S中的某个状态开始,并在每个step时会从一个state转移到另一个state。转移(transition)通过矩阵M来指导:在每个step上,如果系统从状态i移到状态j的概率为。如果给定当前状态作为概率分布,下一状态的概率分布通过表示当前状态的该vector与M相乘得到。总之,系统的起始状态(start state)根据在S上的一些分布x被选中。在m个steps后,该系统的状态会根据进行分布。在一些条件下,不需要考虑起始分布x,该系统最终会达到一个唯一确定点(状态分布不再变化)。该分布称为“稳态分布(stationary distribution)”。该分布可以通过M的左主特征向量(principal left eigenvector)y给出,例如:。实际上,一个简单的power-iteration算法可以快速获得关于y的一个合理近似。y中的entries定义了在S上的一个天然顺序。我们称这样的顺序为M的马尔可夫排序(Markov chain ordering)

对rank fusion问题使用Markov chains如下所示。状态集合(State Set) S对应于包含待排序(rank)的所有candidates的list(例如:在中的所有items的集合)。在M中的转移概率在某种程度上依赖于,待估计的是在M上的Markov chain ordering。下面,[7]提出了一些Markov chains(MC):

  • : 如果当前state为item i,那么,下一state从对应rank >= item i的所有items j的multiset中均匀选中,例如,从multiset 中均匀选中下一state。

  • :如果当前state为item i,下一state的挑选过程如下:首先从所有包含i的中均匀选中一个ranking ,接着从集合中均匀选中一个item j

  • :如果当前state为item i,下一state的挑选过程如下:首先从包含i的所有中均匀选择一个ranking ,接着均匀选择通过排序的一个item j。如果那么跳到j,否则留在i;

  • :如果当前state为item i,下一state挑选过程如下:首先从S中均匀选中一个item j。如果对于会同时对i和j进行排序的lists 中的大多数都成立,那么跳到j,否则留在i。

注意,Markov chain方法确实只依赖于ranks间的比较,即不考虑scores也不考虑hits。下面是一个示例。

示例1.考虑以下在S={1,2,3}中的三个items的rankings .

图1

它可以展示成关于的转移矩阵,分别为:

图2

下面,我们会为matrix entries展示一些示例计算。记住是给定当前state(item i)到下一state(item j)的概率。

  • 是2/6. 确实,(rank<=item 1的case:1; 1,3; 1,2,3)。因此,在中均匀选中某一元素的概率为1/6, 选中item 3的概率为2/6.

  • 是5/18. 均匀选择一个包含item 2的rank list的概率为1/3. 如果被选中,那么。因此,选中item 1的概率为1/2. 相似的,有,以及。因此,

  • 是2/9. 均匀选中一个包含item 2的概率为1/3. 在一个rank list范围内均匀选择一个item的概率也为1/3. 由于, 因此

图3

  • 是1/3. 均匀选中在S中一个item的概率为1/3. 另外,考虑图3中的表:在上表中的每个entry 是满足的lists的count数(例如,有多少rankings满足:item j的rank比item i要好)。由于存在三个lists,因此majority的阀值是2. 指的是:给定item 2, 在下一step之后我们仍停留在item 2上的概率。由于分别是2、 0、 2, 三种情况中有两种会从item 2进行转移,另一种仍会停留在item 2上。相应的是1/3.

最终,rank set R的fused rank list 是在上的Markov chain ordering。可以看到所有4种情况都是:

3.实验

3.1 数据集

使用Text Retrieval Conference(TREC)数据集。它提供了具有许多rank lists的大的、标准的数据集,准备进行fused。通常,每年会提供一个大的文档数据base S和一个包含 50个querie的list。在ad-hoc和web信息检索大会上,每个系统x会

参考

facebook DLRM介绍

# 介绍facebook在2019在《Deep Learning Recommendation Model forPersonalization and Recommendation Systems》。# 摘要facebook开发了一种SOTA的深度学习推荐模型(DLRM)...… Continue reading

ali reranking模型介绍

Published on October 15, 2019

youtube MMoE排序系统

Published on October 11, 2019