Detta papper undersöker preferens-baserade top-K rank aggregation problem. Antag att en samling av objekt jämförs upprepade gånger i par, och man vill återställa en konsekvent beställning som betonar de topp-K rangordnade objekten, baserat på delvis avslöjade preferenser. Vi fokuserar på Bradley-Terry-Luce (BTL) modell som postulerar en uppsättning latent preferens poäng underliggande alla objekt, där oddsen för parade jämförelser beror endast på de relativa poäng av de berörda objekten. Vi karakteriserar minimax-gränserna för identififiability för topp-K rangordnade objekt, i närvaro av slumpmässig och icke-adaptiv provtagning. Våra resultat belyser ett separationsmått som kvantifierar skillnaden i preferenspoäng mellan K th och (K + 1) th rangordnade objekt. Den minsta urvalskomplexitet som krävs för tillförlitliga topp-K-rankningsskalor omvänt med separationsmåttet oberoende av andra mått för preferensfördelning. För att närma sig denna minimax-gräns föreslår vi ett nästan linjärt tidsrankningssystem, kallat Spectral MLE, som returnerar indexen för topp-K-objekten i enlighet med en noggrann värdering. I ett nötskal börjar Spectral MLE med en första värdering med minimal squared förlust (som erhålls via en spektral metod), och förfinar sedan varje komponent successivt med hjälp av koordinatmässigt MLE. Uppmuntrande, Spectral MLE möjliggör perfekt top-K objekt identifiering under minimal prov komplexitet. Den praktiska tillämpligheten av Spectral MLE bekräftas ytterligare av numeriska experiment.
Ref studerade identifieringen av top-K-kandidaterna enligt BTL-modellen och dess urvalskomplexitet.
Spectral MLE: Top-$K$ Rank Aggregation from Pairwise Comparisons
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}