rank fusion介绍

Reading time ~2 minutes

《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”。
  • \(\tau\)是一个rank list,它与U有关,是关于子集\(S \subseteq U\)的一个排序,例如:\(\tau = [x_1 \geq x_2 \geq \cdots \geq x_k\),对于每个\(x_i \in S\),\(\geq\)是在S上的顺序关系.

如果 \(i \in U\)出现在\(\tau\)中,写成\(i \in \tau\),\(\tau(i)\)表示i的position或rank。我们假设\(U = \lbrace 1,2,\cdots, \mid U \mid \rbrace\),通过对每个\(i \in U\)分配一个唯一的id,没有对普适性有损失。

。。。

2.2 Fusion方法

本节中,我们将讲述分析的ranking fusion方法。考虑一个包含了n个rankings的集合\(R=\lbrace \tau_1, \cdots, \tau_n \rbrace\)。假设:

  • U表示在\(\tau_1, \cdots, \tau_n\)中的items的union,例如:\(U = \cup_{\tau \in R, i \in \tau} \lbrace i \rbrace\)。
  • \(\hat{\tau}\)表示ranking(被称为fused ranking或fused rank list),它是一个rank fusion方法应用到在R中的rank lists之后得到的结果。

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

  • 如果两个fused ranking \(\hat{\tau}_1, \hat{\tau}_2\)是相等的(equal),则:\(\hat{\tau}_1 = \hat{\tau}_2\)
  • 如果\(\hat{\tau}_1\)和\(\hat{\tau}_2\)是等价的(equivalent),那么对于\(i \in U\),有\(\hat{\tau}_1(i) = \hat{\tau}_2(i)\)(他们具有相同的顺序)

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

2.2.1 线性组合

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

\[CombSUM: s^{\hat{\tau}}(i) = \sum\limits_{\tau \in R} w^{\tau}(i) \\ CombMNZ: s^{\hat{\tau}}(i) = h(i, R) \cdot \sum\limits_{\tau \in R} w^{\tau}(i)\]

从[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 \(i \in U\)以及rank list \(\tau \in R\),Borda归一化权重为\(w^{\tau}(i)\)(定义1)。fused rank list \(\hat{\tau}\)根据Borda score \(s^{\hat{\tau}}\)的顺序排序,其中在\(\hat{\tau}\)中的一个item \(i \in U\)被定义为:

\[s^{\hat{\tau}}(i) = \sum\limits_{\tau \in R} w^{\tau}(i)\]

…(6)

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

2.2.2 Markovchain-based方法

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

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

  • \(MC_1\): 如果当前state为item i,那么,下一state从对应rank >= item i的所有items j的multiset中均匀选中,例如,从multiset \(Q_i^{C_1} = \cup_{k=1}^n \lbrace j: \tau_k(j) \leq \tau_k(i) \rbrace\)中均匀选中下一state。

  • \(MC_2\):如果当前state为item i,下一state的挑选过程如下:首先从所有包含i的\(\tau_1, \cdots, \tau_n\)中均匀选中一个ranking \(\tau\),接着从集合\(Q_{\tau,i}^{C_2} = \lbrace \tau(j) \leq \tau(i) \rbrace\)中均匀选中一个item j

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

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

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

示例1.考虑以下在S={1,2,3}中的三个items的rankings \(R = \lbrace \tau_1, \tau_2, \tau_3 \rbrace\).

图1

它可以展示成关于\(MC_1, MC_2, MC_3, MC_4\)的转移矩阵,分别为:\(M^1, M^2, M^3, M^4\)。

图2

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

  • \(M_{13}^1\)是2/6. 确实,\(Q_1^{C_1}\)是\(\lbrace 1,1,3,1,2,3 \rbrace\)(rank<=item 1的case:1; 1,3; 1,2,3)。因此,在\(Q_1^{C_1}\)中均匀选中某一元素的概率为1/6, 选中item 3的概率为2/6.

  • \(M_{21}^2\)是5/18. 均匀选择一个包含item 2的rank list的概率为1/3. 如果\(\tau_1\)被选中,那么\(Q_{\tau_1,2}^{C_2}=\lbrace 2,1 \rbrace\)。因此,选中item 1的概率为1/2. 相似的,有\(Q_{\tau_2,2}^{C_2}=\lbrace 2,1,3 \rbrace\),以及\(Q_{\tau_3,2}^{C_2}=\lbrace 2, 3 \rbrace\)。因此,\(M_{21}^2 = \frac{1}{3} \cdot \frac{1}{2} + \frac{1}{3} \cdot \frac{1}{3} + \frac{1}{3} \cdot 0 = \frac{5}{18}\)

  • \(M_{23}^3\)是2/9. 均匀选中一个包含item 2的概率为1/3. 在一个rank list范围内均匀选择一个item的概率也为1/3. 由于\(\tau_1(3) \nless \tau_1(2), \tau_2(3) < \tau_2(2), \tau_3(3) < \tau_3(2)\), 因此\(M_{23}^3 = \frac{1}{3} \cdot 0 + \frac{1}{3} \cdot \frac{1}{3} + \frac{1}{3} \cdot \frac{1}{3} = \frac{2}{9}\)。

图3

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

最终,rank set R的fused rank list \(\hat{\tau}_k\)是在\(M^k, k=1, \cdots, 4\)上的Markov chain ordering。可以看到所有4种情况都是:\(\hat{\tau}=[3 \geq 2 \geq 1]\)。

3.实验

3.1 数据集

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

参考

DTS介绍

youku在《Deep Time-Stream Framework for Click-Through Rate Prediction by TrackingInterest Evolution》提出了一个兴趣演进的框架。# 摘要CTR预测在像视频推荐等工业应用中是一个必要...… Continue reading

DFN介绍

Published on December 15, 2020

CSCNN介绍

Published on December 11, 2020