Leírás
Kivonat:
We consider the problem of ranking and learning the qualities w1,…,wn of a collection of items by performing noisy comparisons among them. We assume that there is a fixed “comparison graph”, and every neighboring pair of items is compared k times. We focus more specifically on the popular Bradley-Terry-Luce model, where comparisons are i.i.d. events, and the probability for item i to win the comparison against j is wi/(wi+wj). We propose a near-linear time algorithm allowing us to recover the weights with an accuracy that outperforms all existing algorithms, and show that this accuracy is actually within a constant factor of information-theoretic lower bounds, that we also develop. This accuracy is related to the average resistance of the comparison graph. Our algorithm is based on a weighted least square, with weights determined from empirical outcomes of the comparisons. We further discuss the extension to other models of comparisons, and comparisons involving multiple items.
Zoom access: https://us06web.zoom.us/j/84349612136?pwd=Y2NsdGlLNFNad2FkR2owVS9icnF6Zz09
Meeting ID: 843 4961 2136
Passcode: 024350