I detta dokument undersöks adaptive (active) PAC (sannolikt ungefär korrekt) top-k ranking (dvs. top-k objekt val) och totala ranking problem från l-wise (l ≥ 2) jämförelser under multinomial logit (MNL) modell. Genom att adaptivt välja uppsättningar för att fråga och observera den bullriga utgången av den mest gynnade objektet i varje fråga, vill vi utforma ranking algoritmer som återställer top-k eller total ranking med så få frågor som möjligt. För PAC top-k ranking problem, vi härleda en lägre gräns på provet komplexitet (aka antal frågor), och föreslå en algoritm som är samplecomplexity-optimal upp till en O(log(k + l) / log k) faktor. När l = 2 (dvs. parvisa jämförelser) eller l = O(poly(k)), matchar denna algoritm den nedre gränsen. För PAC total ranking problem, vi härleda en tight lägre gräns, och föreslå en algoritm som matchar den lägre gränsen. När l = 2 reduceras MNL-modellen till den populära Plackett-Luce-modellen (PL). I detta sammanhang överträffar våra resultat fortfarande den senaste tekniken både teoretiskt och numeriskt. Vi jämför också våra algoritmer med den senaste tekniken med hjälp av syntetiska data samt verkliga data för att verifiera effektiviteten hos våra algoritmer.
Med tanke på vinnarfeedback under PL-modellen undersöker REF PAC top-k och totala rankingproblem från k-wise (k ≥ 2) jämförelser, samtidigt som man studerar urvalet komplexitet att identifiera, med hög sannolikhet, top-k ranking.
PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}