Лучший алгоритм для организации матчей для краудсорсинга рейтинга?

Question

Я бы хотел создать систему, которая собирает 10 лучших предметов из набора, который может варьироваться от 20 до 2000 предметов (ранжирование среди первой десятки не имеет значения). Есть отличная статья об алгоритмах стекового потока для выполнения реальной сортировки в Как оценить миллион изображений с помощью краудсорсинга . Я склоняюсь к тому, чтобы спросить пользователей, что им больше нравится, между двумя пунктами, а затем использовать алгоритм TrueSkill .

У меня вопрос: я использую что-то вроде TrueSkill, каков наилучший алгоритм для решения, какие пары предметов показывать пользователю, чтобы оценить? У меня будет ограниченное количество возможностей спросить людей, какие предметы им нравятся больше всего, поэтому важно, чтобы представленные пары дали системе наиболее ценную информацию для определения топ-10. Опять же, меня больше всего интересует поиск десятки менее важно, как остальные предметы располагаются между собой или даже как первые десять ранжируются между собой.

Answer 1

Был разработан еще один хорошо известный алгоритм для расчета рейтинга в турнирах по Го или Шахматам.Вы можете взглянуть на Алгоритмы МакМахона , которые вычисляют такие пары и ранги одновременно.Должна быть возможность урезать этот алгоритм, так что он будет производить только набор из 10 лучших элементов.

Более подробную информацию можно найти в тезисе Кристиана Герлаха , где он описывает фактическую оптимизациюалгоритм (к сожалению, диссертация на немецком языке).

Answer 2

Эта проблема очень похожа на организацию турнира на выбывание, в котором навыки игроков недостаточно известны, а количество игроков очень велико (например, теннисные турниры школьного уровня). Поскольку круговая игра (O (n ^ 2) совпадений) очень дорога, но простой турнир на выбывание слишком упрощен, обычным вариантом является использование структуры k-исключения. По сути, каждый игрок (в вашем контексте предмет) выбивается из раздора после проигрыша в k играх. Взгляните на структуру двойного исключения: http://en.wikipedia.org/wiki/Double-elimination_tournament.

Возможно, вы сможете изменить его настолько, чтобы удовлетворить ваши потребности.