Как оценить миллион изображений с помощью краудсорсинга - PullRequest
83 голосов
/ 03 октября 2008

Я хотел бы оценить коллекцию пейзажных изображений, создав игру, в которой посетители сайта могут оценивать их, чтобы узнать, какие изображения люди находят наиболее привлекательными.

Что было бы хорошим способом сделать это?

  • Стиль Hot-or-Not ? То есть показать одно изображение, попросите пользователя оценить его от 1 до 10. На мой взгляд, это позволяет мне усреднять баллы, и мне просто нужно обеспечить равномерное распределение голосов по всем изображениям. Довольно прост в реализации.
  • Выберите A-or-B ? То есть покажите два изображения, попросите пользователя выбрать лучшее. Это привлекательно, поскольку здесь нет числового ранжирования, это просто сравнение. Но как бы я это реализовал? Моей первой мыслью было сделать это как быструю сортировку, с операциями сравнения, выполняемыми людьми, и после завершения просто повторить сортировку до бесконечности.

Как бы вы сделали это?

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

Ответы [ 12 ]

94 голосов
/ 03 октября 2008

Как уже говорили другие, рейтинг 1-10 не работает так хорошо, потому что люди имеют разные уровни.

Проблема, связанная с методом Pick A-or-B , заключается в том, что для системы не гарантируется транзитивность системы (A может бить B, но B бьет C, а C бьет A). Наличие операторов нетранзитивного сравнения нарушает алгоритмы сортировки . При использовании быстрой сортировки в этом примере буквы, не выбранные в качестве точки разворота, будут неправильно ранжироваться друг против друга.

В любой момент вы хотите получить абсолютный рейтинг всех картинок (даже если некоторые / все они связаны). Вы также хотите, чтобы ваш рейтинг не изменился , если кто-то не проголосует .

Я бы использовал Pick A-or-B (или ничью) , но определял бы рейтинг, аналогично системе рейтингов Elo , которая используется для ранжирования в играх для 2 игроков ( изначально шахматы):

Рейтинг игроков Эло система сравнивает записи матчей игроков против матчей их противников и определяет вероятность игрок, выигравший матч это коэффициент вероятности определяет, сколько очки рейтинг игроков повышается или вниз на основе результатов каждого матч. Когда игрок побеждает противник с более высоким рейтингом, рейтинг игрока повышается больше, чем если бы он или она победил игрока с более низкий рейтинг (так как игроки должны победить противников, у которых ниже рейтинги).

Система Эло:

  1. Все новые игроки начинают с базовым рейтингом 1600
  2. WinProbability = 1 / (10 ^ ((Текущий рейтинг противника - Текущий рейтинг игрока) / 400) + 1)
  3. ScoringPt = 1 очко, если они выигрывают матч, 0, если они проигрывают, и 0,5 за ничью.
  4. Новый рейтинг игрока = Старый рейтинг игрока + (K-значение * (ScoringPt - Вероятность выигрыша игрока))

Замените "игроков" на картинки, и у вас есть простой способ настроить рейтинг обеих картинок на основе формулы. Затем вы можете выполнить ранжирование, используя эти числовые оценки. (K-Value здесь - это «уровень» турнира. Это 8-16 для небольших местных турниров и 24-32 для более крупных приглашений / регионалов. Вы можете просто использовать константу, например 20).

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

РЕДАКТИРОВАТЬ: Добавлено немного мяса на основе комментариев.

40 голосов
/ 03 октября 2008

У большинства наивных подходов к проблеме есть серьезные проблемы. Хуже всего то, как bash.org и qdb.us отображает котировки - пользователи могут голосовать за котировку вверх (+1) или вниз (-1), а список лучших цитат отсортировано по общему количеству баллов. Это страдает от ужасного смещения во времени - старые цитаты набрали огромное количество положительных голосов за счет простого долголетия, даже если они лишь незначительно смешны. Этот алгоритм может иметь смысл, если шутки становятся смешнее, когда они становятся старше, но - поверьте мне - они не делают.

Существуют различные попытки исправить это - посмотреть на количество положительных голосов за период времени, взвесить более свежие голоса, внедрить систему распада для более старых голосов, рассчитать соотношение положительных и отрицательных голосов и т. Д. Большинство страдают от других недостатки.

Лучшее решение - я думаю - это то, что веб-сайты Самые смешные Самые милые , Самые прекрасные и Лучшая вещь use - модифицированная система голосования Condorcet :

Система присваивает каждому номер, исходя из того, с чем он сталкивался, какой процент из них он обычно бьет. Таким образом, каждый получает процентный балл NumberOfThingsIBeat / (NumberOfThingsIBeat + NumberOfThingsThatBeatMe). Кроме того, вещи запрещены в верхнем списке, пока они не будут сравнены с разумным процентом от набора.

Если в наборе есть победитель Кондорсе, этот метод найдет его. Поскольку это маловероятно, учитывая статистическую природу, он находит тот, который «наиболее близок» к тому, чтобы стать победителем Кондорсе.

Для получения дополнительной информации о внедрении таких систем может быть полезна страница Википедии по Ranked Pairs .

Алгоритм требует, чтобы люди сравнивали два объекта (ваш выбор Pick-A-or-B), но, честно говоря, это хорошо. Я считаю, что в теории принятия решений очень хорошо принято, что люди намного лучше сравнивают два объекта, чем в абстрактном рейтинге. Миллионы лет эволюции делают нас хорошими в выборе лучшего яблока с дерева, но ужасны в принятии решения, насколько близко мы собрали яблоко, к истинной платонической форме яблочности. (Именно поэтому, кстати, Процесс аналитической иерархии такой изящный ... но это становится немного не по теме.)

И последнее замечание: SO использует алгоритм для поиска лучших ответов, который очень похож на алгоритм bash.org для поиска лучших предложений. Это работает хорошо здесь, но ужасно терпит неудачу там - в значительной степени потому что старый, высоко оцененный, но теперь устаревший ответ здесь, вероятно, будет отредактирован. bash.org не позволяет редактировать, и неясно, как вы вообще отредактируете десятилетние анекдоты об устаревших интернет-мемах, даже если бы вы могли ... В любом случае, я считаю, что правильный алгоритм обычно зависит от деталей вашей проблемы. : -)

11 голосов
/ 16 декабря 2009

Я знаю, что этот вопрос довольно старый, но я думал, что внесу свой вклад

Я бы посмотрел на систему TrueSkill, разработанную в Microsoft Research. Это похоже на ELO, но имеет гораздо более быстрое время сходимости (выглядит экспоненциально по сравнению с линейным), поэтому вы получаете больше от каждого голоса. Это, однако, сложнее математически.

http://en.wikipedia.org/wiki/TrueSkill

8 голосов
/ 03 октября 2008

Мне не нравится стиль Hot-or-Not . Разные люди выбирают разные цифры, даже если им все одинаково нравится изображение. Также я ненавижу оценивать вещи из 10, я никогда не знаю, какое число выбрать.

Выбрать A-or-B гораздо проще и веселее. Вы видите два изображения и сравниваете изображения на сайте.

5 голосов
/ 24 декабря 2008

Эти уравнения из Википедии упрощают / более эффективны для вычисления рейтингов Эло, алгоритм для изображений A и B будет простым:

  • Получите Ne, мА, мБ и рейтинги RA, RB из вашей базы данных.
  • Рассчитайте KA, KB, QA, QB, используя количество выполненных сравнений (Ne) и количество сравнений изображения (м) и текущие оценки:

K

QA

QB

  • Рассчитать EA и EB.

EA

EB

  • Оценка S победителя: победитель равен 1, проигравший - 0, а если у вас ничья - 0,5,
  • Рассчитайте новые рейтинги для обоих, используя: New Rating

  • Обновление новых рейтингов RA, RB и отсчетов мА, мБ в базе данных.

4 голосов
/ 03 октября 2008

Рейтинг 1-10 не сработает, у всех разные уровни. Кто-то, кто всегда дает 3-7 оценок, затмевает свой рейтинг людьми, которые всегда дают 1 или 10.

a-or-b более работоспособен.

4 голосов
/ 03 октября 2008

Вы можете пойти с комбинацией.

Первый этап: Горячий стиль или нет (хотя я бы выбрал вариант с 3 вариантами голосования: отстой, Мех / ОК. Круто!)

После того, как вы отсортировали набор в 3 сегмента, я бы выбрал два изображения из одного блока и выбрал "Что лучше"

Затем вы можете использовать систему продвижения и понижения английского футбола, чтобы переместить несколько лучших «Отстой» в область Meh / OK, чтобы уточнить крайние случаи.

3 голосов
/ 17 мая 2015

Если вы предпочитаете использовать стратегию Pick A или B, я бы порекомендовал эту статью: http://research.microsoft.com/en-us/um/people/horvitz/crowd_pairwise.pdf

Чен Х., Беннетт П.Н., Коллинз-Томпсон К. и Хорвиц Е. (2013, Февраль). Парное ранжирование агрегации в краудсорсинге. В Материалы шестой международной конференции ACM по веб-поиску и интеллектуальный анализ данных (стр. 193-202). ACM.

В статье рассказывается о модели Crowd-BT , которая расширяет знаменитую модель парного сравнения Брэдли-Терри в условиях краудсорсинга. Это также дает адаптивный алгоритм обучения для повышения эффективности модели во времени и пространстве. Вы можете найти реализацию алгоритма Matlab на Github (но я не уверен, работает ли он).

3 голосов
/ 05 марта 2011

Ух ты, я опаздываю в игре.

Мне очень нравится система ELO, но, как говорит Оуэн, мне кажется, что вы не спешите получать какие-либо существенные результаты.

Я считаю, что у людей гораздо больше возможностей, чем просто сравнивать два изображения, но вы хотите, чтобы взаимодействие было минимальным.

Так как насчет того, чтобы вы показали n изображений (n - это любое число, которое вы можете визуально отобразить на экране, это может быть 10, 20, 30, в зависимости от предпочтений пользователя, может быть), и заставили их выбрать то, что они считают лучшим в этой партии , Теперь вернемся к ЭЛО. Вам нужно изменить свою рейтинговую систему, но придерживаться того же духа. Вы фактически сравнили одно изображение с n-1 другими. Таким образом, вы делаете свой рейтинг ELO n-1 раз, но вы должны разделить изменение рейтинга на n-1, чтобы соответствовать (чтобы результаты с различными значениями n были согласованы друг с другом).

Вы сделали. Теперь у вас есть лучшее из всех миров. Простая рейтинговая система, работающая со многими изображениями в один клик.

2 голосов
/ 19 декабря 2008

На несуществующем веб-сайте whatsbetter.com использовался метод стиля Эло . Вы можете прочитать о методе в их FAQ в Интернет-архиве .

...