Miglior algoritmo per il matchmaking per una classifica di crowdsourcing?

Question

Vorrei creare un sistema che raccolga i migliori 10 elementi da un set che può variare da 20 a 2000 articoli (la classifica tra i primi dieci non è importante). C'è un eccellente post stackoverflow sugli algoritmi per fare lo stesso ordinamento allo How to rank a million images with a crowdsourced sort. Sono propenso a chiedere agli utenti che preferiscono tra due elementi e quindi utilizzare l'algoritmo TrueSkill.

La mia domanda è data Sto usando qualcosa come TrueSkill, qual è il miglior algoritmo per decidere quali coppie di oggetti mostrare un utente da valutare? Avrò un numero limitato di opportunità per chiedere alle persone quali oggetti preferiscono, quindi è importante che le coppie presentate forniscano al sistema le informazioni più preziose per identificare la top 10. Di nuovo, sono principalmente interessato a trovare la top ten, meno così come il resto degli oggetti si posiziona tra loro o anche come i primi dieci si classificano tra loro.

Answer 1

Questo problema è molto simile all'organizzazione di un torneo a eliminazione diretta in cui le abilità dei giocatori non sono ben note e il numero di giocatori è molto alto (si pensi ai tornei di tennis di livello scolastico). Dato che round robin (O (n^2) corrisponde) è molto costoso, ma un semplice torneo knock-out è troppo semplicistico, la solita opzione è quella di andare con la struttura k-eliminazione. In sostanza, ogni giocatore (nel tuo contesto un oggetto) viene messo fuori combattimento dopo aver perso k partite. Dai un'occhiata alla struttura a doppia eliminazione: http://en.wikipedia.org/wiki/Double-elimination_tournament.

Forse è possibile modificarlo a sufficienza per soddisfare le vostre esigenze.

Answer 2

Un altro algoritmo ben noto per questo è stato prodotto per calcolare le classifiche nei tornei Go o Chess. Puoi dare un'occhiata allo MacMahon Algorithms che calcola tali accoppiamenti e le classifiche allo stesso tempo. Dovrebbe essere possibile troncare questo algoritmo, in modo che produca solo un set di 10 elementi migliori.

È possibile trovare ulteriori dettagli in Christian Gerlach's thesis, dove descrive l'algoritmo di ottimizzazione effettivo (purtroppo la tesi è in tedesco).