I detta dokument undersöks problemet med att rangordna en samling objekt med hjälp av parvisa jämförelser (rankningar av två objekt). I allmänhet kan rankningen av n objekt identifieras med standard sorteringsmetoder med n log 2 n parvis jämförelser. Vi är intresserade av naturliga situationer där relationer mellan objekten kan tillåta rankning med mycket färre parvisa jämförelser. Specifikt, vi antar att objekten kan inbäddas i en d-dimensionell Euclidean utrymme och att rankingen återspeglar deras relativa avstånd från en gemensam referenspunkt i R d. Vi visar att under detta antagande antalet möjliga ranking växer som n 2d och visar en algoritm som kan identifiera en slumpmässigt vald ranking med bara något mer än d log n adaptivt utvalda parvisa jämförelser, i genomsnitt. Om istället jämförelserna väljs slumpmässigt, då nästan alla parvisa jämförelser måste göras för att identifiera någon rankning. Dessutom föreslår vi en robust, feltolerant algoritm som endast kräver att de parvisa jämförelserna är förmodligen korrekta. Experimentella studier med syntetiska och verkliga dataset stödjer slutsatserna i vår teoretiska analys.
I REF utnyttjar författarna det underliggande lågdimensionella Euclidean utrymmet för data för att upptäcka rankningen med hjälp av ett litet antal parvisa jämförelser.
Active Ranking using Pairwise Comparisons
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}