We consider the problem of ranking N objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We assume that objects are endowed with intrinsic qualities and that the probability with which an object is preferred to another depends only on the difference between the qualities of the two competitors. We propose a class of non-adaptive ranking algorithms that rely on a least-squares optimization criterion for the estimation of qualities. Such algorithms are shown to be asymptotically optimal (i.e., they require O(Nϵ2logNδ) comparisons to be (ϵ,δ) -PAC). Numerical results show that our schemes are very efficient also in many non-asymptotic scenarios exhibiting a performance similar to the maximum-likelihood algorithm. Moreover, we show how they can be extended to adaptive schemes and test them on real-world datasets.
Ranking a set of objects: a graph based least-square approach / Christoforou, Evgenia; Nordio, Alessandro; Tarable, Aberto; Leonardi, Emilio. - In: IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING. - ISSN 2327-4697. - ELETTRONICO. - 8:1(2021), pp. 803-813.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | Ranking a set of objects: a graph based least-square approach |
Autori: | |
Data di pubblicazione: | 2021 |
Rivista: | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1109/TNSE.2021.3053423 |
Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
TNSE3.pdf | Editorial postprint | 2a Post-print versione editoriale / Version of Record | Non Pubblico - Accesso privato/ristretto | Administrator Richiedi una copia |
LS_Ranking_final.pdf | Informal open version | 2. Post-print / Author's Accepted Manuscript | PUBBLICO - Tutti i diritti riservati | Visibile a tuttiVisualizza/Apri |
http://hdl.handle.net/11583/2862351