Maximizing the expected value of experimentation for finding top-κ rank via aggregation of pairwise comparisons
研究了如何利用实验期望值（EVE）在成对比较中选出最值得进行的比较，以高效找出前κ个对象的排名，并提出了降低计算成本的随机游走方法，适用于交互式教学等场景。
Expected Value of Experimentation (EVE) is a decision analysis tool that allows one to measure the amount of useful “actionable information” to be gained upon carrying out an “experiment”, accounting for its possible stochastic outcomes. The EVE assessment also allows one to select a “most informative” experiment out of a set of experiments that can be conducted en route to solving a decision problem. We address the following problem: find a best-vs.-worst consensus partition of objects (top-κ set) by aggregating the results from a number of pairwise comparisons of these objects. We use EVE to determine which pair of objects should be assigned to an annotator for evaluation, to gain more information about them. A challenge in evaluating the EVE is high computational cost, exponential in the size of the decision space: this has limited EVE to use in small problems with only few alternative experiments in consideration. We tackle this challenge in our problem through the modeling and perturbation analysis of random walks on the space of the compared objects. This advance enhances the appeal of using EVE in decision analysis applications reliant on pairwise comparisons. Specifically, we use it for informing the interactive teaching/learning activity Create-Rank-Compete Crowdlearning. We also show that EVE-Informed Active Sampling algorithm’s performance compares favorably to the state-of-the-art Active Ranking algorithm.