О сортировке контента на основе оценок пользователей: Часть 2

в 20:57, , рубрики: Алгоритмы, Веб-разработка, математика, рейтинг, рейтинги, рейтинги в виде звезд, сортировка, сортировки, сортировщик страниц, статистика, статистический анализ, теория вероятностей, теория вероятности, тервер, метки: , , , , , , , , , , ,

Прошлая статья привлекла большой интерес. И даже, на некоторое время, стала лучшей за 24 часа. У меня появилось несколько идей и на часть вопросов в комментариях нужно ответить более развернуто.
image

Проблема одного голоса vs «богатые богатеют»

Напомню, что основная проблема в том, что если считать рейтинг какой-то статьи или товара как среднее арифметическое оценок пользователей (самый простой вариант), возможен случай когда статья с одним голосом в пять балов будет выше статьи с 100 голосов в 5 балов и одним в 4ре. Назовем, это «проблемой одного голоса», хотя, она существует не только для статей с одним голосом.

Для того, чтобы этого не произошло нужно учитывать число голосов. Однако, если мы это сделаем, то получим уже другую проблему «богатые богатеют». Старые статьи будут иметь больше голосов, их рейтинг будет выше, они будут получать больше переходов и еще больше голосов и, следовательно, еще больше отрываться от молодых статей. Даже если все статьи добавлены одновременно, то этот эффект все равно будет наблюдаться. Только вверху будут не старые статьи, а те которым повезло в начале голосования получить случайный голос.

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

Хотя существует некоторые «не гладкие» решения. Например, исключить статьи с числом голосов меньшим определенного из рейтинга. Однако, в этом случае, часть статей будет убрана из рейтинга на долгое время. Если основная часть переходов статьи получают с рейтинга, то некоторые статьи в него попадут только через несколько лет. В некоторых случаях этот эффект не приемлем.

Другой вариант — выводить рейтинги за определенный промежуток времени. Например, за последние 24 часа, как на хабре. Богатые все равно будут богатеть и у статьи с возрастом в несколько часов мало шансов обогнать 23 часовую статью.

Плюс/минус и чувство справедливости

В рейтинге плюс/минус неявно включено число голосов. Сумма плюсов и минусов линейно зависит от числа просмотров статьи. Как уже говорил, «проблемы одного голоса» в этом рейтинге нет. Однако, эффект «богатые богатеют» в нем должен наблюдаться сильнее, чем в большинстве случаев решения проблемы «одного голоса» для других типов рейтингов. Однако, этого не происходит…

Большинство пользователей добросовестны и стараются помочь сайту. Хулиганов намного меньше, чем добропорядочных людей. Это философия Википедии и в том, что она работает легко убедиться просто открыв Википедию.

Пользователь скорее поставит плюс недооцененной, по его мнению, статье, чем плюс статье которая ему понравилась, но по его мнению, правильно ранжируется в рейтинге. Минус «переоцененной» статье тоже более вероятен, чем минус статье на «правильном» месте.

Можно посмотреть выдачу хабра за последние 24 часа, с точки зрения математики почти все ее статьи должны иметь возраст близкий к 24 часам. Но это не так. Совсем молодых статей в ней нет, но статьи возрастом всего в 3-5 часов довольно часто оказываются первыми. Работает механизм самоорганизации.

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

Статистическую погрешность

Если мы пытаемся побороть «проблему одного голоса» нужно вычислить некоторую величину назовем ее «статистическую погрешность» и в самом простом вычесть из рейтинга статьи. Вопрос каким образом ее вычислить. Даже, если мы знаем распределение, его коэффициенты, то погрешность в зависимости от необходимой нам уверенности может колебаться в значительном интервале. Так, что в любом случае оценка погрешности субъективна. Например, нельзя на 100% быть уверенным, что в пакет сока разливочный автомат нальет литр сока ±100мл. Автомат может заглючить и вообще ничего не налить, вероятность этого, конечно, мала, но существует.

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

image
Вот наша погрешность. Сигма это среднее квадратичное отклонение (далее СКО). Другими словами корень из суммы квадратов отклонений. Это некоторая мера оценки разброса. Если мы ее вычтем, то мы получим некоторую нижнюю границу оценки рейтинга.

Здесь возникают проблемы. Первая, посчитать ее в старом рейтинге можно, только если вы запомнили все оценки пользователей отдельно. Вторая, в том что для статьи с одним голосом СКО=0, а для статей с малым числом голосов СКО будет определятся со статистической погрешностью.

Самый простой метод решить эти две проблемы — считать СКО некоторым процентом от рейтинга статьи.

image

Где, Ri — рейтинг статьи. Ri с точкой — результирующий рейтинг. Ri без точки исходный рейтинг — среднеарифметическое всех голосов. N — число голосов.

Где k от 0 до 1. При k=0 случай выродиться к среднеарифметическому, при k=1 статья с одним голосом будет иметь нулевой вес. k — это мера консерватизма, чем она выше тем, богатые быстрее богатеют, но тем меньше эффект одного голоса. Проблема найти баланс, поэтому, во многих случаях значение 0.5 как середины будет оправдано.

Этот метод хорошо решает проблему «одного голоса». При этом, для большого числа голосов из-за корня рост его замедляется снижая эффект «богатые богатеют». Чтобы снизить штраф в 10 раз нужно в 100 раз увеличить число голосов. Поэтому, этот метод может применяться и не только для нормального распределения.

Замещение

По сравнению с формулой из прошлой статьи (среднего взвешивания) она менее консервативна при большом числе голосов. Другими словами, эффект «богатые богатеют» при большом числе посещений статьи будет слабее. Однако, у этой формулы есть недостатки. Непонятно что она отражает, прошлая формула была некоторой оценкой рейтинга статьи в действительности. Другая проблема в том, что рейтинг статьи может быть ниже минимального рейтинга, при k=1 и n=1 рейтинг равен нулю когда, как минимальная оценка, обычно, равна 1.

По большому счету, в этой формуле мы взяли часть рейтинга статьи, которую посчитали недостоверной, и убрали его, заменили нулем. Если рейтинг идет от одного, то нужно его замещать единицей. Однако, если мы заместим его средним рейтингом всех статей, то наш результат будет некоторой оценкой рейтинга, который статья получит в будущем, а не его нижней границей. Что правильнее и у нашего рейтинга появится смысл. Смысла сравнивать нижние границы нет почти никакого, а сравнивать мат. ожидание (прогноз) — есть. Вдобавок это снизит эффект «богатые богатеют» для молодых статей. Изначально молодые статьи будут не в конце рейтинга, а в его середине. Ведь статья с без голосов почти наверняка лучше статьи с сотней минимальных оценок.

image.
R с чертой это средний рейтинг всех статей на сайте. Формула замещает часть рейтинга статьи, аналогичной долей рейтинга средней статьи.

Это некоторое усреднение рейтинга статьи со средним рейтингом. Сейчас я докажу, что это среднее арифметическое взвешенное средней оценки статьи со средней оценкой всех статей с коэффициентами 1-k/sqrt(n) (оценка достоверной части рейтинга) и k/sqrt(n) — (недостоверная часть рейтинга статьи).

image

Значение средневзвешенного всегда между минимальным и максимальным значениями элементов. Т.е. итоговый рейтинг всегда будет находится в необходимом диапазоне (например, от 1 до 5 для 5ти звезд). Он всегда между «простым рейтингом» и рейтингом средней статьи.

Наша формула неопределенна при n=0 и мы примем за его значение средний рейтинг статей. В итоге формула примет вид:

image

Если эта статья окажется довольно простой для восприятия, то я ее продолжу и расскажу о том как улучшить оценку считая СКО и о рейтинге в стиле «мне нравится» и том когда формула на стекле все-таки применима.

Автор: Hkey

Поделиться

* - обязательные к заполнению поля