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

    Прошлая статья привлекла большой интерес. И даже, на некоторое время, стала лучшей за 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

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

    P.S. если у кого-то есть база с несколькими тысячами голосов. Причем голоса запоминаются отдельно. То огромная просьба поделиться. Несколько баз позволят привести численные показатели прогнозирования.

    Читайте продолжение
    Share post

    Comments 36

      +8
      На bash.orh.ru ситуация немного противоположная:

      Изначально постились весьма мудрые шутки, но посещаемость была низкой.

      С ростом посещаемости начались постинги всяких ололошечек.

      Одновременно с ростом посещаемости всякие недавние ололошечки получают большее количество голосов, чем мудрые шутки древних времён.
        +1
        Мое мнение в следующем.

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

        А после набора некоего минимального порога оценок смело можно ранжировать по среднему значению.
          +3
          Автор, вы пытаетесь идти с палкой и камнем против теоремы Эрроу ( ru.wikipedia.org/wiki/Теорема_Эрроу ). Коллективный выбор никогда не будет хорошим.

          Кроме того, вы пытаетесь идти против математической теории эволюционной динамики. Сложный организм всегда обыгрывает по сумме взаимодействий более простой организм. Человек ведёт себя сложно, все математические формулы — просто. Человек обдурит рейтинг всегда.

          Нужно отдавать себе отчёт, что эти рейтинги — просто забава.
            0
            Теорема Эрроу для 3 и более альтернатив и при условии того, что предпочтения индивидуума относительно предлагаемых к выбору альтернатив не могут измеряться количественно.

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

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

              Голосование в бюллетене тоже подпадает под теорему Эрроу.

              Вы не думайте, что открываете что-то новое в жизни, «Нобеля» Эрроу не зря получил.
              +1
              Коллективный выбор никогда не будет хорошим.

              Будет, в тематическом сообществе. Чем более узка тематика, тем более хорошим он будет.

              Однако и для большого коллектива он может быть хорошим, например, для выбора новостей. News2 вполне себе неплохо работает. Но, конечно, коллективный выбор не будет работать для фильмов/музыки и т.д., и рейтинг IMDB почти на 100% бессмысленный.
                0
                Для фильмов будет работать, просто это должен быть персонализированный рейтинг. Глобальный топ100, конечно, не учитывает вкусов конкретного человека, да и вообще много чего.
                  0
                  Так я об этом и говорю. Персональный рейтинг (рекомендации) — работать будут. Топ в сообществе ценителей аниме или артхауса — тоже (чем-то хуже, чем-то лучше)
                  0
                  Под «хорошим» подразумевается то, что написано в теореме Эрроу. У любого коллективного выбора будет недостаток. Даже в узком сообществе как Хабр голосовалкой можно манипулировать. И это соответствует теореме Эрроу.

                  Зачем вы спорите с математикой? Голосовалка на сайте под теорему Эрроу подпадает. Думаете эмпирически или так вот умозрительно опровергнуть нобелевского лауреата?
                    0
                    Не хочу как-то спорить с нобелевским лауреатом. Бесспорно его теорема верна в том пространстве утверждений которую он рассматривает. Наверно, на её основе можно утверждать, что результатом полностью демократических выборов всегда кто-то будет недоволен. И, на Хабре, наверняка есть недовольные результатами рейтинга. Но, скорее всего это будут люди, чьё мнение сильно отличается от большинства хабропользователей. А что есть сообщество, как не люди объединённые общим мнением/ценностями/вкусами/идеями или чем-то ещё? Значит просто этим людям нужно другое место тусовки, более конгруэнтное его ценностям/мнению/мировозрению.

                    И уж точно эта теорема не может быть использована как доказательство бесполезности рейтинга на Хабре. Хотя бы потому, что он работает :)
                      0
                      Я не хочу сказать, что рейтинг бесполезен. Он полезен и нужен, но у него есть недостатки.

                      Суть недостатков вовсе не в том, что кто-то будет недоволен. Прочтите, пожалуйста, страничку про теорему, чтобы понять, что это. Это

                      Как мне кажется, автор статьи борется с некоторыми следствиями теоремы, с которыми можно только смириться.

                      Сейчас многие программисты работают с темами, которые хорошо проработаны в экономике во второй половине 20 века, и многие переизобретают велосипеды.
                        0
                        Хотел написать, что за недостатки. Это, например, манипулируемость посторонними альтернативами. Когда один кандидат оттягивает голоса у похожего — это как раз такая манипуляция.

                        Это диктатура. У одного фильма рейтинг 3,9 из 5, у другого 4,0. Пришёл человек, поставил первому 5, второму 0, и второй фильм в рейтинге опустился ниже первого. Получается, хотя на сайте все посчитали лучше (или не хуже) второй фильм, один человек перетянул коллективный выбор и сделал его таким, как ему хочется.
                          0
                          Насколько я понимаю в этой и моей статье осуществляется попытка бороться с вполне конкретными недостатками. А именно:

                          1. «Проблема одного голоса» — недостаток данных при малом числе голосов для рассчёта «среднего голоса».
                            Пример: рейтинг при одном положительном голосе будет выше, чем при 1000 положительных и одном отрицательном
                          2. Проблема слишком высокого рейтинга у статей с большим числом голосов при подсчёте по хаброалгоритму (UP — DOWN).
                            Пример: +100/-10=90 (90% положительных) будет ниже чем +1000/-900=100 (53% положительных)

                          Ещё одна проблема, которую затрагивает автор — это «богатые богатеют». Суть в том, что при дефолтном показе самых рейтинговых постов вначале, происходит положительная обратная связь. За них ещё больше начинают голосовать. Но я не понимаю как она соотностися с контентом. Это проблема пользовательского интерфейса, а не самого алгоритма. На хабре по-дефолту ты смотришь ленту постов отсортированных по дате, а не по рейтингу, а просмотр топа — это адвансед фича, которая помогает когда мало времени и хочется посмотрить «что тут у нас самого важного произошло» за день/неделю/месяц/всё время. Помимо прочего, Хабр вместо писсимизации высокого рейтинга с помощью логарифмирования (как на Reddit) просто обрубает возможность голосовать через 3 дня. И это тоже работает: у всех постов фактически равный шанс на получение высокого балла.
                  +5
                  Блин, после такой картинки не смог нормально прочитать всю статью! Разве можно так? А что делать, если мне нравится и плюс, и минус? :-)
                  • UFO just landed and posted this here
                    +1
                    Бонус новичка еще Яндекс вводил для ранжирования много лет назад — весьма рабочая схема, за исключением того, что в топ могут пролезть шлаковые вещи. Впрочем, они быстро опускаются. Быстро получить оценки можно не из рейтинга «лучшее», а из рейтинга «новое» — как разместить пару рейтингов на сайте — проблема из другой области, но весьма несложная.

                    Но это уже третья статья по теме, а авторы не учитывают очень интересный аспект голосования. Уровень поставленной оценки также может зависить от того, КТО её ставит. Так или иначе мы собираем и храним информацию о пользователях. И если человек голосует правильно, например его «вкус на голосования» на 95% совпадает с тем, какой рейтинг набирает статья в итоге — то его оценке можно верить больше, чем того, чей хулиганский «вкус» совпадает с мнением большинства на 20%.
                    Или по репутации. Если голосует человек с репутацией 0 — то это одно, а если с репутацией, близкой к максимальной, то относиться к этой оценке можно значительно более доверительно. Ведь пользователи с максимальной репутацией это пол-дороги к редакторам сайта (при условии, что у нас нормальная система репутации, а не как на… )
                      0
                      Вместо R с чертой можно поставить нижнюю оценку, например, 1 или верхнюю, например 5 (если 5 звезд). И получим прогноз снизу или сверху. При прогнозе сверху будет бонус новичкам. При прогнозе снизу — штраф.
                      Однако, прогноз сверху или снизу это уже некоторая абстрактная величина и сильно зависит от выбора методики.

                      По поводу разных весов голосов пользователей, то это формула не исключает их. Ri может быть не средней оценкой, а средневзвешаной по рейтингу/репутации пользователей. Также можно считать СКО оценок пользователя к итоговым и если он часто отбивается от большинства снижать его голос.
                      0
                      Я считаю систему рейтинга на хабре весьма близкой к идеальной. То, что голосование прекращается через 24 часа, отсекает эффект «богатеют богатые». Плюсы и минусы вместо звёздочек отсеивают проблему «одного голоса».

                      Тот факт, что при голосовании в голосах пользователей не используется их вес (например, карма), делает голосование прозрачным и демократичным.

                      Чего ещё желать, о чём ещё писать статьи?
                        0
                        Демократичность голосования приводит к тому, что в топ вылазят обзоры смартфонов и обсуждение патентов. Надо учитывать вес людей, при чем, в зависимости от активности в Хабе, а не общую карму.
                          0
                          Что поделать, это недостаток всех инструментов или сайтов «общего назначения». Хотя да, от патентных войн и обзоров китайских планшетов уже тошнит.
                            0
                            Это проблема голосовалки. Если бы вес голоса зависел от рейтинга в блоге статьи (а в нетематический блогах, вес голоса был бы минимальным), дела обстояли бы иначе. Понятно, что если один пишет на Си, другой верстает, а трети админит, то мало какая специализированная статья будет интересна им всем. При этом, зрелища любят все и радостно голосуют за освещение очередного чиха в суде.

                            Администрация решила, что подписки на любимые блоги решает проблему, но судя по отзывам тех, кто пишет технические статьи — это не так. Обидно потратить кучу времени на написание статьи с серьезным анализом и уступить в рейтинге десятку переводов желтухи и всяким посмехуечкам.
                              0
                              Полностью с вами согласен. Я даже провёл эксперимент — решил сравнить количество плюсов по моим техническим статьям с плюсами, которые получил за перепост статьи про закрытие Апорта. Ну и, думаю, вы догадываетесь что получилось.

                              Но если подумать с другого угла, например, есть тематический блог «Программирование воображаемого робота-носорога на воображаемом fortran-подобном языке» не интересный вообще никому, кроме пользователей A, B и С. Все три пользователя имеют по 20 публикаций в этот блог, соответственно их голоса очень весомы, а голоса пользователей D, E и F, которым не сдались воображаемые носороги, не могут заминусовать кросс-плюсы A B и C. В итоге никому не интересная статья станет в топ выдачи.

                              Может тогда стоит учитывать и многочисленность подписчиков блога в некоем коэффициенте? Но тогда подписчиков блога «Патентные войны» будет очень много, что опять выведет его в топы.

                              В общем, закон большинства не отменить. И Ализары всегда будут популярнее технарей.
                                0
                                В теории алгоритм типа Имхонет может решить данную проблему и каждому будет выдаваться его персональный топ.
                                  0
                                  Но тогда каждому будет выдаваться ЕГО персональный топ. А как тогда сказать, что ты вошёл в топ на хабре? В чей топ?

                                  «Глянь, на первой странице хабра новость» — потеряет смысл.

                                  Мне кажется, это искусственные ограничения на рейтинг. Пока большинству нравятся статейки про патенты с брюсом уиллисом, или статьи про выход нового айфончика — не бывать утопии.
                                    0
                                    А нафига вам входить во всеобщий топ? Славы ради замусоривать мозги тем единицам, которым ваш пост не понравился?
                                    Кстати, если отказаться от всеобщей славы, минусов получится меньше.
                                    Я — за Имхонет!
                                      0
                                      Так тогда надо сидеть не на хабре, а на форуме — имхо там имхонет. Ни тебе рейтингов, тема одна, говори пиши что хочешь — полная ана… демократия.
                                        0
                                        С форумами как раз основная проблема в поиске нужной информации, которая порой бывает там очень ценной. Но статьи по формату гораздо лучше. Наверное, я мечтаю о помеси хабра и википедии :-)
                            +1
                            Это вообще проблема из другой оперы. Никакой рейтинг её не решит вообще никогда. Больше сообщество → больше разброс интересов → меньше вес будут набирать специализированные узкотематические статьи и больше общедоступные.

                            Проблему решают только персональные рекоммендации, т.е. рейтинг статьи для кокретного человека. Или, хотя бы для группы (к примеру, рейтинг статьи в конкретном Хабе, кстати — крутая идея).
                          0
                          Реквестирую продолжение серии расчета рейтинга статей, с учетом рейтинга пользователей.
                            0
                            С весами из Klout ;-)
                              +1
                              при этом сразу стоит учесть тематичность кармы
                              0
                              Вот это уже интереснее и убедительнее. Спасибо, жду продолжения!

                              Я кстати долго думал как совместить Willson Score с рейтингом IMDB (описанный вами в предыдущей статье взвешенный рейтинг). Даже пропало злобное желание предъявить права на свою картинку, которую вы эксплутаируете :)
                                0
                                А в чем проблема сделать экспонентную формулу? Оценки выставленные позже с возрастом имеют меньше влияния на конечный рейтинг. Проблема одного голоса вообще высосана из пальца. Что мешает учитывать количество голосов в формуле? Суть в том, что нужно абстрагироваться от прямых значений, которые несет голосовалка. +4 -3 это не +4 и -3. Нужно учитывать когда были поставлены эти 4 и 3, какова была волатильность в этих оценках (все тупо плюсовали или была борьба?) еще пару параметров (помимо времени, общее количество голосовавших) и все это на 100% — получим средневзвешанный рейтинг.

                                Только до всего этого надо определиться с целью рейтинга. Для чего вам он конкретно нужен, тк рейтинг — это инструмент и им можно разных целей добиваться.
                                  0
                                  Мне кажется что можно использовать разный вес одного голоса. У каждого пользователя должна быть свой собственный рейтинг. Рейтинг пользователя можно оценивать по количеству полезной информации, которую он уже предоставил сайту, заполненности его профиля, оценкам его камментов и т.п. Что-то типа кармы. И оценки пользователя с бОльшим рейтингом будут иметь большее значение для подсчета рейтинга статьи. Мне казалось именно так работают рейтинги новостей сайтах социальных новостей news2.ru, smi2.ru
                                    0
                                    У меня тоже были мысли о рейтингах, в частности что делать если статистика мала. Например для постов с малым количеством проголосовавших использовать «презумпцию невиновности» и помещать их в какой-нибудь топ, но без авторства. Дальше статья либо быстро выходит из топа, либо закрепляется там. Еще можно попробовать проводить эксперименты и приблизительно оценивать величину эффекта обратной связи, соответственно делать поправку на него.

                                    А вообще всё это сильно зависит от сайта, на котором что-то рейтингуется. Нужно учитывать его специфику. Одно дело ютуб, другое хабр. Разумеется на ресурсах типа хабра проблему недостаточной статистики нужно решать в комплексе с другими подходами, в частности с использованием веса голосов пользователей. Если за пост мало голосов, но это авторитетные люди, это нужно учитывать. Помнится я так и делал, когда разрабатывал рейтинговую систему для одного сайта.
                                      0
                                      Ну вот, понадобилась статья, изображений нет. Когда уже народ научится юзать habrastprage… Удали её автор, так проще.

                                      Only users with full accounts can post comments. Log in, please.