М… Да вы правы :) По крайней мере в определении. Но всё равно это нельзя считать достаточным основанием не применять данный алгоритм. Я уверен, если взять статистику голосования на Хабре, распределение всё равно будет очень близко к биноминальному.
Э… похоже на троллинг честно говоря. Я тут из себя не строю гуру мат. статистики, но уж точно понимаю, что независимость эксперимента — это невозможность поставить плюс и минус одновременно, а не влияние способа отображения объектов на выбор пользователя за что голосовать.
Биномиа́льное распределе́ние в теории вероятностей — распределение количества «успехов» в последовательности из независимых случайных экспериментов, таких что вероятность «успеха» в каждом из них постоянна и равна p (Wikiprdia).
Независимость — есть
Число экспериментов n — конечно (при бесконечном мы получаем нормальное распределение, верно?)
Вероятность постоянна (и зависит от обобщённого мнения сообщества)
Вариант с «закрыл страницу непроголосовав» — просто не входит в эксперимент. Минус означает что пользователь с постом не согласен или считает неподходящим для сообщества (неподходящим тематике, некомпетентным или неинтересным). Плюс — солгасен, пост компетентен, интересен, помог в решении проблемы и т.д. и явно подходит сообществу. Когда оценка не ставится — скорее всего человек считает его подходящим для сообщества, но неинтересным лично для себя (например не его область компетенции).
Голосованием? Можно, только я не очень понял о чём вы. Но использовать код можете как угодно.
А вот таблица, двухмерная (нас она не интересует):
Пост 1.1 Пост 1.2 Пост 1.3
Пост 2.1 Пост 2.2 Пост 2.3
Пост 3.1 Пост 3.2 Пост 3.3
Чтобы выстроить несколько постов в список нужно привести их рейтинг к одному числу. Как матрёшки (по размеру). Или гири (по весу). Нельзя отсортировать объекты по 2-м или более параметрам одновременно не приведя их к одному. Это равносильно задаче отсортировать товары так, чтобы сначала шли самые качественные и дешёвые, а в конце самые плохие и дорогие :) Никто не мешеат вам выводить список постов разными алгоритмами (по цене, дате, числу комментариев или проценту женщин среди комментирующих). Но всё равно, для каждого случая вам нужно будет сопоставить публикации число (рейтинг), чтобы вывести их списком.
А как пользователи будут оценивать публикации (с помощью + и -, с помощью звёздочек, с помощью 100 ползунков по различным параметрам с произвольной шкалой, суммарным временем затраченным на чтение/просмотр при регистрации движения глаз, и т.д.) — это другая задача.
Как выводить рейтинг отдельной публикации (числом плюсов и минусов, суммарным рейтингом, графическим прогресс-баром, размером и цветом публикации и т.д.) — это третья задача.
Как минимизировать влияние способа выдачи публикаций на их оценку пользователями — это четвёртая задача.
Я не утверждаю, что задачи никак между собой не связаны, я просто напоминаю, что мы говорим о первой — как сопоставить каждой публикации число (рейтинг) на основе имеющихся уже оценок, чтобы получить «список лучших».
Спасибо за перевод! Что касается первого алгоритма, то он показался мне более чем странным… Я пробовал строить рейтинг на его основе, и подумал, что что-то неправильно перевёл, или не правильно понял. В итоге сделал по-своему взяв за основу сам принцип:
Т.е. мы банально прибавляем к рейтингу дату устанавливая между ними какое-то равновесие. Например рейтинг +100 = 5 дням, + 1000 = 10 дням и т.д. В качестве f1 я пробовал использовать как logn(up-down), так и тот же willson score на что-нибудь помноженный. Оба работают неплохо, но Вилсоновский мне нравится больше (за исключением работы с отрицательным рейтингом down > up).
Что происходит при отрицательном и нулевом рейтинге в Reddit — вообще не ясно. При положительном up-down к рейтингу дата прибавляется, при нулевом не прибавляется, а при отрицательном вообще (!) вычетается (при up < down, y = -1, при up = down, y = 0). Или я что-то не правильно понял?
Суть моего поста в следующем: авторы статьи решили актуальную для меня проблему не совсем понятным мне способом. Их методика с успехом применяется на многих крупных проектах. Несмотря на не до конца понятный мне математический аппарат, результат ранжирования дал замечательный результат в проведённых мною эмпирических тестах. К посту предлагаются букмарклеты для Хабра и Дару~дара для того, чтобы проверить работу алгоритма самому. Я так же многократно проверил метод на проекте sociation.org (например для получения списка слов которые чаще всего называют мужчины и женщины). Метод дал лучшие результаты из всего, что я перепробовал, включая собственные разработки.
По этому я дал перевод статьи as-is и попросил сообщество помочь с пониманием мат. стороны вопроса.
Суть же вашей статьи примерно такова:
Статья затрагивает правильную тему, однако с точки зрения математики и здравого смысла она в корне не верна.
...
нет никакого основания применять эту формулу к задаче, кроме одного эпизода из фильма, снятого по бульварному роману
...
Доверительные интервалы изначально были созданы для того, чтобы оценивать вероятность того, что гипотеза подтверждается статистикой, а не для рейтинга. Доверительные интервалы очень сильно зависят от необходимой вероятности и принцип ее выбора непонятен из статьи.
... нам предлагают сортировать по оценке (с точностью до наугад выбранного параметра) нижней границы вероятности того, что пользователь поставит +, если он все-таки проголосует.
Т.е. вы говорите: математический аппарат неверен и предложенный метод не будет работать только потому что смысл его не понятен из статьи.
Я, как бы, даже не знаю что вам на это возразить :)
Давайте не будем всё сваливать в одну кучу. Когда стоит задача вывести объекты — сначала самые лучшие/релевантные/etc, потом остальные нужен рейтинг выраженный одной цифрой. Потому что список у нас линейный. Не двухмерный, не трёхмерный, а линейный. Значит нужна одна цифра.
Есть ещё задача представления рейтинга конкретного объекта для пользователя. Это совсем другая задача. И это скорее из области интерфейсов-юзабилити.
Отсортировать объекты по рейтингу учитывая неполноту данных (когда мало голосов судить об крутости объекта можно только с определнным ± допущением)
Вывести наиболее актуальные объекты на текущее время
На Хабре для этого, соответственно, 2 раздела: лента и топы публикаций (за день/неделю/месяц/всё время). Если убрать ленту и оставить только топы, естественно богатеть будут только богатые.
Я вот тоже давно задумываюсь о связке NoSQL + Поисковый движок (Sphinx/Solr/etc.). По сути RDBMS — это тот же key-value, плюс плохой (по сравнению с Sphinx/Solr) поисковый движок, плюс реляции с обеспечением целостности данных, плюс триггеры/хранимые процедуры, целесообразность использования которых в вэбе крайне сомнительна.
Целостность вполне можно обеспечить на стороне приложения. Sphinx/Solr решают все проблемы со сложными запросами. А вот что касается альтернатив реляциям, особенно M2M — вопрос для меня пока неисследованный. К примеру M2M связь пост → хаб довольно очевидна. Пост может находится в небольшом числе хабов, можно просто хранить их в документе поста как массив, выборку по хабу разрулит SE…
А если число связей велико с обоих сторон? А если у связи есть дополнительные данные (например пользователь → хаб, где есть роль, дата вступления и т.п.)?
Довольно обидно, что Хабр как рупор Российской ИТ индустрии так компрометирует Sphinx. На самом деле Sphinx способен искать гораздо качественнее Solr/ES/etc, особенно это касается русского языка. Вдобавок у к отсутствию прожорливости Sphinx гораздо быстрее индексирует документы, а бинарный протокол сильно экономит на пересвлке данных. Вот с RealTime у него действительно беда :( Приходится держать до 3-х дельта-индексов, при этом мёрджинг оказывается накладнее полного переиндексирования.
Те же программисты, что пишут Хабр реализовали поиск на сайте darudar.org гораздо качественнее. Там правда в 10-ки меньше нагрузка, но зато в 10-ки больше данных. Видимо просто сейчас на Хабре много более приоритетных задач, чем оптимизация поиска.
Потому что ORM пишется на интерпретируемых языках с без статической типизации. И в этом есть смысл.
Реальность устроена так, что проще увеличить в 100 раз производительность серверов и писать на python/ruby/javascript, чем нанимать в 100 раз больше программистов для написания серверного кода за то же время на C. И даже после того, как код написан наступает проблема его поддержки, отладки, модернизации, масштабировании и т.п.
Это логика эволюции: машинный код → ASM → C/C++ → интерпретируемые языки →?
Между прочим, если посмотреть например OPA, то в ней JavaScript фактически используется как ассемблер :) Она в него компилируется. И судя по примеру микро-википедии на 60 строк ОПА-кода — это явно привет из будущего.
Концуренция — это замечательно. Она вносит соревновательный момент. Участники конуркетной борьбы стремятся постоянно улучшать качество. Улучшение качества становистя вопросом выживания: «стань лучше или умри».
Это замечательно до поры до времени. В какой-то момент структура становится настолько огромной и глобальной, что существование конкурентов требует немыслимое количество дополнительных ресурсов. Сколько нужно специалистов, денег, серверов, электричества и других ресурсов, чтобы существовал ещё один Гугл? А сколько нужно ресурсов для существования ещё одного интернета?..
Существование нескольких браузеров и операционных систем и так создаёт такое количество трудностей, что иногда становится не по себе, как осознаешь. Но в масштабах планеты это пока возможно и оправданно. Хотя уже появляются инициативы с налогом на IE в интернет-магазинах (действительно, это не блажь программистов, а реальные человекочасы необходимые для поддержки плохих технологий).
Второй инернет будет так же по оптоволокну и спутникам? Представляете создание и поддержку ещё одной такой структуры? Там будут использованы те же протоколы, или, для конкуренции придумаем что-то своё? Там будет тот же html/css/js или что-то конкурентное? Если да, то нужны другие браузеры. Под каждую ОС. Нужно поддерживать в актуальном состоянии сайты в обоих интернетах. А серверная часть, возможно там будет другой. И т.д.
Подитоживая, я бы лаконично сформулировал эту проблему как «проблема конкуренции конкуренции и глобализации»
У меня кстати был диплом на подобную тему. Я пытался увеличивать изображения на основе фрактального анализа. Точнее на основе алгоритма фрактального сжатия изображений. Идея в том, что картинка считается фракталом, и почти брутфорсом, ищется набор афинных преобразований в цветовом пространстве этот фрактал порождающий. Потом картинка восстанавливается примененением полученные преобразования на холсте большего размера.
Результат выходил похожим на метод Фрмана в приведённой статье, даже симпатичнее. Главная проблема — чудовищная медлительность алгоритма, при том, что в качестве примитивов использовались только квадраты. А, по хорошему, это должны быть произвольные фигуры.
Пока я это дело писал, наткнулся на схожие коммерческие алгоритмы. Но они работали в частотном пространстве и использовали вейвлеты (примерно так). Мне их результаты не нравились, т.к. картинка как-то неприятно сглаживалась.
Когда в Москве будет нормальный мобильный интернет? В час ночи я могу доехать от работы до дома непрерывно слушая интернет радио. Днём же, часто, не могу проверить почту или обновить Твиттер. Т.е. покрытие — нормальное. Но сеть не держит нагрузку, возможно недостаточная ширина канала. Я не знаю.
Год назад я ездил с Яндексом фотографировать панорамы городов. К удивлению, такого паршивого интернета как в Москве нет ни в одном городе. Во многих городах я покупал симку и смотрел потоковое видео, даже качал торренты!
Это касается всех трёх операторов. Каждый из них отвратителен по-своему.
Вариант с «закрыл страницу непроголосовав» — просто не входит в эксперимент. Минус означает что пользователь с постом не согласен или считает неподходящим для сообщества (неподходящим тематике, некомпетентным или неинтересным). Плюс — солгасен, пост компетентен, интересен, помог в решении проблемы и т.д. и явно подходит сообществу. Когда оценка не ставится — скорее всего человек считает его подходящим для сообщества, но неинтересным лично для себя (например не его область компетенции).
Голосованием? Можно, только я не очень понял о чём вы. Но использовать код можете как угодно.
Букмарклеты внизу статьи, после слова «букмарклеты» :)
А вот таблица, двухмерная (нас она не интересует):
Чтобы выстроить несколько постов в список нужно привести их рейтинг к одному числу. Как матрёшки (по размеру). Или гири (по весу). Нельзя отсортировать объекты по 2-м или более параметрам одновременно не приведя их к одному. Это равносильно задаче отсортировать товары так, чтобы сначала шли самые качественные и дешёвые, а в конце самые плохие и дорогие :) Никто не мешеат вам выводить список постов разными алгоритмами (по цене, дате, числу комментариев или проценту женщин среди комментирующих). Но всё равно, для каждого случая вам нужно будет сопоставить публикации число (рейтинг), чтобы вывести их списком.
А как пользователи будут оценивать публикации (с помощью + и -, с помощью звёздочек, с помощью 100 ползунков по различным параметрам с произвольной шкалой, суммарным временем затраченным на чтение/просмотр при регистрации движения глаз, и т.д.) — это другая задача.
Как выводить рейтинг отдельной публикации (числом плюсов и минусов, суммарным рейтингом, графическим прогресс-баром, размером и цветом публикации и т.д.) — это третья задача.
Как минимизировать влияние способа выдачи публикаций на их оценку пользователями — это четвёртая задача.
Я не утверждаю, что задачи никак между собой не связаны, я просто напоминаю, что мы говорим о первой — как сопоставить каждой публикации число (рейтинг) на основе имеющихся уже оценок, чтобы получить «список лучших».
Т.е. мы банально прибавляем к рейтингу дату устанавливая между ними какое-то равновесие. Например рейтинг +100 = 5 дням, + 1000 = 10 дням и т.д. В качестве f1 я пробовал использовать как logn(up-down), так и тот же willson score на что-нибудь помноженный. Оба работают неплохо, но Вилсоновский мне нравится больше (за исключением работы с отрицательным рейтингом down > up).
Что происходит при отрицательном и нулевом рейтинге в Reddit — вообще не ясно. При положительном up-down к рейтингу дата прибавляется, при нулевом не прибавляется, а при отрицательном вообще (!) вычетается (при up < down, y = -1, при up = down, y = 0). Или я что-то не правильно понял?
По этому я дал перевод статьи as-is и попросил сообщество помочь с пониманием мат. стороны вопроса.
Суть же вашей статьи примерно такова:
Т.е. вы говорите: математический аппарат неверен и предложенный метод не будет работать только потому что смысл его не понятен из статьи.
Я, как бы, даже не знаю что вам на это возразить :)
Есть ещё задача представления рейтинга конкретного объекта для пользователя. Это совсем другая задача. И это скорее из области интерфейсов-юзабилити.
Но это решает проблему выдачи «актуальных объектов» на текущее время. И реальный (итоговый) рейтинг объекта не имеет к этому отношения.
Ещё раз: есть 2 совершенно разные задачи:
На Хабре для этого, соответственно, 2 раздела: лента и топы публикаций (за день/неделю/месяц/всё время). Если убрать ленту и оставить только топы, естественно богатеть будут только богатые.
Целостность вполне можно обеспечить на стороне приложения. Sphinx/Solr решают все проблемы со сложными запросами. А вот что касается альтернатив реляциям, особенно M2M — вопрос для меня пока неисследованный. К примеру M2M связь пост → хаб довольно очевидна. Пост может находится в небольшом числе хабов, можно просто хранить их в документе поста как массив, выборку по хабу разрулит SE…
А если число связей велико с обоих сторон? А если у связи есть дополнительные данные (например пользователь → хаб, где есть роль, дата вступления и т.п.)?
Те же программисты, что пишут Хабр реализовали поиск на сайте darudar.org гораздо качественнее. Там правда в 10-ки меньше нагрузка, но зато в 10-ки больше данных. Видимо просто сейчас на Хабре много более приоритетных задач, чем оптимизация поиска.
Реальность устроена так, что проще увеличить в 100 раз производительность серверов и писать на python/ruby/javascript, чем нанимать в 100 раз больше программистов для написания серверного кода за то же время на C. И даже после того, как код написан наступает проблема его поддержки, отладки, модернизации, масштабировании и т.п.
Это логика эволюции: машинный код → ASM → C/C++ → интерпретируемые языки →?
Между прочим, если посмотреть например OPA, то в ней JavaScript фактически используется как ассемблер :) Она в него компилируется. И судя по примеру микро-википедии на 60 строк ОПА-кода — это явно привет из будущего.
Это замечательно до поры до времени. В какой-то момент структура становится настолько огромной и глобальной, что существование конкурентов требует немыслимое количество дополнительных ресурсов. Сколько нужно специалистов, денег, серверов, электричества и других ресурсов, чтобы существовал ещё один Гугл? А сколько нужно ресурсов для существования ещё одного интернета?..
Существование нескольких браузеров и операционных систем и так создаёт такое количество трудностей, что иногда становится не по себе, как осознаешь. Но в масштабах планеты это пока возможно и оправданно. Хотя уже появляются инициативы с налогом на IE в интернет-магазинах (действительно, это не блажь программистов, а реальные человекочасы необходимые для поддержки плохих технологий).
Второй инернет будет так же по оптоволокну и спутникам? Представляете создание и поддержку ещё одной такой структуры? Там будут использованы те же протоколы, или, для конкуренции придумаем что-то своё? Там будет тот же html/css/js или что-то конкурентное? Если да, то нужны другие браузеры. Под каждую ОС. Нужно поддерживать в актуальном состоянии сайты в обоих интернетах. А серверная часть, возможно там будет другой. И т.д.
Подитоживая, я бы лаконично сформулировал эту проблему как «проблема конкуренции конкуренции и глобализации»
Результат выходил похожим на метод Фрмана в приведённой статье, даже симпатичнее. Главная проблема — чудовищная медлительность алгоритма, при том, что в качестве примитивов использовались только квадраты. А, по хорошему, это должны быть произвольные фигуры.
Пока я это дело писал, наткнулся на схожие коммерческие алгоритмы. Но они работали в частотном пространстве и использовали вейвлеты (примерно так). Мне их результаты не нравились, т.к. картинка как-то неприятно сглаживалась.
Когда в Москве будет нормальный мобильный интернет? В час ночи я могу доехать от работы до дома непрерывно слушая интернет радио. Днём же, часто, не могу проверить почту или обновить Твиттер. Т.е. покрытие — нормальное. Но сеть не держит нагрузку, возможно недостаточная ширина канала. Я не знаю.
Год назад я ездил с Яндексом фотографировать панорамы городов. К удивлению, такого паршивого интернета как в Москве нет ни в одном городе. Во многих городах я покупал симку и смотрел потоковое видео, даже качал торренты!
Это касается всех трёх операторов. Каждый из них отвратителен по-своему.