QuadRank介绍

Reading time ~1 minute

在paper 《Effective rank aggregation for metasearching 》中提出了一种rank aggregation的方法:QuadRank,介绍了一种对多个ranked lists进行merge的方法,我们来了解一下:

3.QuadRank

QuadSearch的缺省ranking fusion算法是一个与位置有关(positional)的方法,可以处理partial ranked list;实际上它会处理来自基于single-crawler的搜索引擎们的top-k lists。我们这样做的原因是因为以下普通并且显著的观察:

  • i) 所有这些都被experts认为是“major”搜索引擎s
  • ii)他们在lifetimes期间是可靠的
  • ii)大多数用户和metasearch engines更偏向于他们来执行它们的搜索

假设是m个ranked lists,分别对应于每个component搜索引擎。我们假设:这些lists中的每一个list都包含了固定数目的k个items,整个过程涉及到对总共km个elements进行merge和rank。这里我们所采用的merging过程是:通过移除所有重复的elements,将m个不同的result lists合并到一个single list中。注意,该list仍是unranked,直到对list中的所有elements使用scoring函数。

两个component engines间的重合(overlapping)会随着query的不同而不同,不可预测,因此我们假设:我们最终的result list包含了N个items。在表1中我们描述了要使用的符号。

表1

在结尾我们会表述提出方法的主要思想。特别描述了QuadRank所采用的方法论,以便处理individual rankings和zone weighting,并且我们会检查URL分析的结果的意义。最终我们会讨论不同components是如何被组合到单个scoring公式中的。

3.1 处理individual rankings

每个element会接受由component engines得到的ranking,这对于一个rank aggregation方法来说是非常重要的,大多数提出的ranking算法主要基于这些rankings。相应的,我们必须设计我们的函数,来对达到较高rankings的结果进行reward。因此,对比起在更低位置的entries,具有较高rankings的entries可以被认为是:它们会与一个给定query更相关

因此,对于每个item ,我们引入和评估了该quantity:

…(2)

其中:

  • m: 表示所使用的component engines的数目
  • c: 表示在component list中的单个结果
  • k: 在每个component list中的items数目
  • 是该item被分配给第i个component engine得到的ranking

在特殊情况下,item c没有被list 进行rank,那么我们假设:。很明显,一个item可以接收的最好score是km(如果它在每个component list中都排在第一位),最低的score是1 (表示只被一个component list进行rank,并且排到最后一个)

引入的score会对那些接受了多个component engines的high rankings的items进行reward,然而,两或多个结果被分配相等的K(c)值是相对常见的。例如,考虑到以下场景:两个不同的items ,它们会接收到由4个top-10 lists 的rankings。

表2

在表2的示例中,它会有。然而,我们会坚定认为:的rank要比要高。因为:

  • 1.在更多的input rankings中出现,相应的,根据民主对称性(democratic symmetry) Saari(2000)
  • 2.在超过一半的input rankings中出现,因此根据孔多塞标准(Condorcet criterion),它是一个spam entry的概率很低

为了处理这样的case,我们必须对以下结果进行reward:该结果被尽可能多的component engines认为是与一个给定query相关。如果是结果c出现在各component engines的数目,那么我们引入rank-based score,它由以下等式决定:

…(3)

其中m是所使用engines的总数目。注意(3)中所使用的log是为了减小在可以接受的不同值之间的误差。另外,尽管使用m乘以log没啥差异(因为m对于所有items是一个常数),它可以根据你的目的进行调节,以便让 score分配更大的值。

参考

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