Active Sampling for Pairwise Comparisons via Approximate Message Passing and Information Gain Maximization

Pairwise comparison data arise in many domains with subjective assessment\nexperiments, for example in image and video quality assessment. In these\nexperiments observers are asked to express a preference between two conditions.\nHowever, many pairwise comparison protocols require a large number of\ncomparisons to infer accurate scores, which may be unfeasible when each\ncomparison is time-consuming (e.g. videos) or expensive (e.g. medical imaging).\nThis motivates the use of an active sampling algorithm that chooses only the\nmost informative pairs for comparison. In this paper we propose ASAP, an active\nsampling algorithm based on approximate message passing and expected\ninformation gain maximization. Unlike most existing methods, which rely on\npartial updates of the posterior distribution, we are able to perform full\nupdates and therefore much improve the accuracy of the inferred scores. The\nalgorithm relies on three techniques for reducing computational cost: inference\nbased on approximate message passing, selective evaluations of the information\ngain, and selecting pairs in a batch that forms a minimum spanning tree of the\ninverse of information gain. We demonstrate, with real and synthetic data, that\nASAP offers the highest accuracy of inferred scores compared to the existing\nmethods. We also provide an open-source GPU implementation of ASAP for\nlarge-scale experiments.\n