分类:并行排序

来自Big Physics


问题背景

今年的暑期学校研究生面试面对和去年同样的情形:人数多(这当然是好事),每个被面试的学生的时间很紧张,老师的决策压力很大,而且由于要保持主试相同,老师们的工作时间长。如果能够并行面试,也就是分成多组同时进行,问题就好办多了。那么,这样做行不行呢?可是,简单的并行会导致主试群体不一样,不能垮主试团体作评价。当然,如果提供并且执行统一的标准来做评分,当然,就可以跨越主试团体了。可是,有的时候,这样的统一的标准没有或者很难执行。怎么办?

是不是可以考虑让每一个主试对被面试者做一个排序,甚至是局域排序,也就是,把肯定谁比谁强的信息提供出来,不能肯定的,就放弃对比。接着,让某些主试做跨团队比较:例如面试进行到下半场的时候,部分主试交换团队。然后,通过聚合这个谁比谁强来建立整体排序。MacKay等人的工作[1]对这个跨评价者的并行评价问题问题做了数学抽象(好像还用了类似投入产出的算法,但是看起来没有解决冲突的问题,需要进一步阅读)。关于这个聚合排序的问题,有前人的研究,例如吴俊等人的工作[2](顺便,我建议他们搞一搞网络上的传播来聚合,也就是用类PageRank算法,投入产出算法)。对于这个问题能否给一个数学证明?

大量的评价问题都牵涉到类似的情景,并行到底怎么做,行不行呢?

数学化

假定一个待评价群体有一个隐藏起来的真实的排序[math]\displaystyle{ \vec{R}=\left(R_{1}, \cdots, R_{j}, \cdots, R_{N}\right) }[/math]。假设每一个主试有一个自己的评价能力[math]\displaystyle{ \phi }[/math],这个能力决定了产生正确的对比的概率[math]\displaystyle{ P\left(\theta\left(r^{l}_i-r^{l}_j\right)\theta\left(R_i-R_j\right)=1\left|\right.\phi\right) }[/math],以及对这个对比结果的信心[math]\displaystyle{ c\left(\theta\left(r^{l}_i-r^{l}_j\right)\theta\left(R_i-R_j\right)=1\left|\right.\phi\right) }[/math]。这样的参数可以每一个主试都一样,也可以不一样。

做一个主试交叉的方案。

搜集所有主试的可能排名对[math]\displaystyle{ \theta\left(r^{l}_i-r^{l}_j\right) }[/math]并且做聚合。

现在,考虑某个主试交叉方案、某个排名聚合算法(综合考虑直接和间接联系),能不能证明聚合之后的排名,和真实排序是接近的。

也可以假定一个待评价群体的每一个个体有一个隐藏起来的真实的分数[math]\displaystyle{ X_{j} }[/math]。假设每一个主试有一个自己的评价能力[math]\displaystyle{ \phi }[/math],这个能力决定了产生正确的分数估计的概率[math]\displaystyle{ P\left(x_{j};X_{j},\phi\right) }[/math]。然后这个主试按照对每一个待评价个体产生这样的参数[math]\displaystyle{ \phi }[/math]可以每一个主试都一样,也可以不一样。

现在,考虑某个主试交叉方案、某个排名聚合算法(综合考虑直接和间接联系),能不能证明聚合之后的排名,和真实基于真实分数的排序是接近的。

传递排序:直接和间接关系

在这里,直接关系指的是:如果在一个主试给出来的排序中,被试[math]\displaystyle{ i }[/math]排在[math]\displaystyle{ j }[/math]前面,则给[math]\displaystyle{ i }[/math]一分,[math]\displaystyle{ j }[/math]零分之类的计算方法。间接关系指的是:如果在一个主试给出来的排序中,被试[math]\displaystyle{ i }[/math]排在[math]\displaystyle{ j }[/math]前面,[math]\displaystyle{ j }[/math]排在[math]\displaystyle{ k }[/math]前面,则一定的概率上也应该在[math]\displaystyle{ i }[/math][math]\displaystyle{ k }[/math]之间做某种赋分算法。具体计算可以考虑PageRank和投入产出。例如,分别从正方向(优胜于)和反方向(劣于)两个方面做一个PageRank算法,然后计算这两个得分的差。

参考文献

  1. MacKay RS, Kenna R, Low RJ, Parker S.Calibration with confidence: a principled method for panel assessment. R Soc Open Sci. 2017 Feb 8;4(2):160760. doi: 10.1098/rsos.160760 (2017).
  2. Yu Xiao, Ye Deng, Jun Wu, Hong-Zhong Deng and Xin Lu, Comparison of rank aggregation methods based on inherent ability, Naval Res Logistics 64, 556-565(2017).

本分类目前不含有任何页面或媒体文件。