I detta dokument studeras problemet med att sluta sig till en global preferens baserad på de partiella rankingar som tillhandahålls av många användare över olika undergrupper av objekt enligt Plackett-Luce-modellen. En fråga av särskilt intresse är hur man optimalt tilldelar objekt till användare för rankning och hur många objekttilldelningar som behövs för att uppnå ett måluppskattningsfel. För en given tilldelning av objekt till användare, vi först härleda en orakel lägre gräns för den uppskattning fel som håller även för de mer allmänna Thurstone modeller. Sedan visar vi att Cramér-Rao nedre gränsen och våra övre gränser omvänt beror på spektralgapet hos Laplacianen i en lämpligt definierad jämförelsegraf. När systemet får välja objekttilldelning föreslår vi ett slumpmässigt tilldelningsschema. Våra orakel nedre gräns och övre gränser innebär att det är minimax-optimalt upp till en logaritmisk faktor bland alla tilldelningsscheman och den nedre gränsen kan uppnås av den maximala sannolikheten estimator samt populära rank-brytande system som dekomponerar partiella rankningar i parvisa jämförelser. De numeriska experimenten bekräftar våra teoretiska rön.
För en mer allmän klass av traditionella observationer, inklusive parvisa jämförelser, ger REF en liknande optimal garanti för den maximala sannolikhetsbedömaren.
Minimax-optimal Inference from Partial Rankings
{'venue': 'NIPS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}