Комментарии 22
Сайт сравнения девушек — FaceMash, упоминаемый в фильме Social Network, именно так и работает. В фильме даже умудрились рассказать об принципах работы алгоритма, и показали формулу на стекле комнаты. Может быть статье нужно было содержать побольше алгоритмов и поменьше «экселя».
Да, я когда про алгоритм прочитал, тут же задумался, насколько его можно применять для сравнения финансовых инструментов. Область применения широкая, только надо чётко понимать ограничения метода.
Про Excel — куда уж меньше, 6 строчек оставил!
Про Excel — куда уж меньше, 6 строчек оставил!
А как там (фильм не видел) велось сравнение девушек? В чём заключался «матч»?
Ды, по-моему все кто смотрел этот фильм — сразу же начали изучать эту формулу написанную на стекле ) и все таки дошли до рейтинговой системы Эло
Ого. Ладно, это ж шахматисты, разберутся.
У нас на фехтовании стоит аналогичная проблема, плюс еще заранее неизвестно количество участников, если их слишком много — на турнир физически не хватит времени. Поэтому решаем следующим образом —
участников, в среднем, от 20 до 60 человек — делим на 2, 3 или 4 группы, примерно по 10-15 человек в каждой, где каждый фехтует с каждым — а потом первые 16 мест (по очкам) идут фехтовать в финал. Таким образом даже у новичков по 10-15 боев.
У нас на фехтовании стоит аналогичная проблема, плюс еще заранее неизвестно количество участников, если их слишком много — на турнир физически не хватит времени. Поэтому решаем следующим образом —
участников, в среднем, от 20 до 60 человек — делим на 2, 3 или 4 группы, примерно по 10-15 человек в каждой, где каждый фехтует с каждым — а потом первые 16 мест (по очкам) идут фехтовать в финал. Таким образом даже у новичков по 10-15 боев.
Да, именно такая же задача. Только у нас ещё и новые участники подтягиваются во время турнира. И не хочется привязываться к временным рамкам — турнир на работе, не у всех есть одинаковое время для игры, кто-то в отпуск ушёл и т.д.
Описанная схема позволяет устраивать очень гибкие турниры.
А что «шахматисты разберутся» — у нас в турнире половина программистов, половина актуариев (считай математики), и те, и другие теоретическую часть понимают быстро. Проблемы с концепцией.
Описанная схема позволяет устраивать очень гибкие турниры.
А что «шахматисты разберутся» — у нас в турнире половина программистов, половина актуариев (считай математики), и те, и другие теоретическую часть понимают быстро. Проблемы с концепцией.
Другу фехтовальщику привет. 8 лет занимался. Эхх.
Хорошая система кстати. Не раз ее переносил на другие виды спорта :)
Хорошая система кстати. Не раз ее переносил на другие виды спорта :)
У нас была версия тупо написать ELO, но:
1) совсем не тот же фан!
2) о чём было бы писать в блоге?
На самом деле, вся затея зародилась после статьи в июльском номере французского журнала Pour la Science, в котором рассматривались разные системы рейтингов, и вот такие — байезианские — признавались наиболее точными. И что уж совсем верно — самыми интересными для программиста.
Автор рассказывал о разных вариациях, и признался, что нашёл единственное реальное применение такого алгоритма — абстрактная стратегическая online-игрушка arimaa.
Ну как можно было после этого не сесть за реализацию?!
1) совсем не тот же фан!
2) о чём было бы писать в блоге?
На самом деле, вся затея зародилась после статьи в июльском номере французского журнала Pour la Science, в котором рассматривались разные системы рейтингов, и вот такие — байезианские — признавались наиболее точными. И что уж совсем верно — самыми интересными для программиста.
Автор рассказывал о разных вариациях, и признался, что нашёл единственное реальное применение такого алгоритма — абстрактная стратегическая online-игрушка arimaa.
Ну как можно было после этого не сесть за реализацию?!
Это то, с чего мы начали, но система заточена на турнир «на вылет», а мы изначально не хотели этого делать. Плюс, сложно вливать в турнир новых игроков.
Нормальное распределение? Вот так с потолка? Вы шутите?
Если нет — извините, но вы сделали ерунду. Если бы вы просто кидали монетку, кого назначить победителем турнира, а кого последним лузером — у вас бы были более правдоподобные результаты.
Если нет — извините, но вы сделали ерунду. Если бы вы просто кидали монетку, кого назначить победителем турнира, а кого последним лузером — у вас бы были более правдоподобные результаты.
А чем вам не нравится нормальное распределение? Суть системы в создании как бы пружинок, связывающих игроков, притягивающих или расталкивающих в зависимости от результатов. Как именно определена сила и упругость пружины — не так уж и важно.
Кстати да, надо попробовать с другим законом, наверняка порядок в рейтинге не изменится…
Кстати да, надо попробовать с другим законом, наверняка порядок в рейтинге не изменится…
Смотрю тут много минусующих ( =ничерта не смыслящих в матстатистике), так что ок, отвечу по делу.
Нормальное распределение [b]в данном случае[/b] мне не нравится тем, что а) оно взято с потолка, без какого-либо доказательства применимости и б) оно взято явно ошибочно, на что указывают «пляски» рейтинга при добавлении в систему даже единчичных посторонних матчей.
Вообще нормальное распределение (и связанная с ним эвклидова метрика) любимо математиками-теоретиками за относительную простоту операций с ним. Надо проверить какую-нибудь теорию из мат. статистики — подсунули в неё нормальное распределение и более-менее просто посчитали. Ну и в учебниках примеры, соответственно, тоже все как на подбор на нормальное распределение, типа для чего посложнее студенты могут посчитать сами.
У нормального распределения есть ряд уникальных свойств — напримар, оно в определенном смысле самое «компактное». Из-за этой «компактности» оно очень неустойчиво, если у реально наблюдаемаой величины есть «длинный хвост» из значений, сильно отличающихся от среднего. Когда вы что-то там динамически считаете по мере поступления данных, каждое такое выбивающееся значение (заметно более слабый игрок случайно обыграл более сильного, например, даже чемпионы мира периодически сливают), то при обсчете нового рейтинга начинает сильно «колбасить» центральные моменты вашего распределения (мат. ожидание, дисперсию и т.п.), из-за чего вся система оказывается нестабильной.
Далеко не все величины в мире распределены нормально. Особенно если говорить о чем-то связанном с человеком. Как минимум попробуйте посмотреть на результаты своей же программы, только с Лапласом, Пуассоном и хи-квадратом. В идеале — построить нормальную гистограмму по известным результатам, аппроксимировать её разными распределениями и посчитать подобие по Колмогорову-Смирнову.
Нормальное распределение [b]в данном случае[/b] мне не нравится тем, что а) оно взято с потолка, без какого-либо доказательства применимости и б) оно взято явно ошибочно, на что указывают «пляски» рейтинга при добавлении в систему даже единчичных посторонних матчей.
Вообще нормальное распределение (и связанная с ним эвклидова метрика) любимо математиками-теоретиками за относительную простоту операций с ним. Надо проверить какую-нибудь теорию из мат. статистики — подсунули в неё нормальное распределение и более-менее просто посчитали. Ну и в учебниках примеры, соответственно, тоже все как на подбор на нормальное распределение, типа для чего посложнее студенты могут посчитать сами.
У нормального распределения есть ряд уникальных свойств — напримар, оно в определенном смысле самое «компактное». Из-за этой «компактности» оно очень неустойчиво, если у реально наблюдаемаой величины есть «длинный хвост» из значений, сильно отличающихся от среднего. Когда вы что-то там динамически считаете по мере поступления данных, каждое такое выбивающееся значение (заметно более слабый игрок случайно обыграл более сильного, например, даже чемпионы мира периодически сливают), то при обсчете нового рейтинга начинает сильно «колбасить» центральные моменты вашего распределения (мат. ожидание, дисперсию и т.п.), из-за чего вся система оказывается нестабильной.
Далеко не все величины в мире распределены нормально. Особенно если говорить о чем-то связанном с человеком. Как минимум попробуйте посмотреть на результаты своей же программы, только с Лапласом, Пуассоном и хи-квадратом. В идеале — построить нормальную гистограмму по известным результатам, аппроксимировать её разными распределениями и посчитать подобие по Колмогорову-Смирнову.
Это всё правильно (сам на работе переписываю моделирование финансов с нормального распределения на Леви и компанию), но мне кажется немножко не в тему. Речь ведь идёт не о распределении рейтингов игроков или о чём-то подобном, а о некоторой «силе расталкивания», вероятности выигрыша. То есть, по-хорошему, годится любая возрастающая функция (я от нормального распределения взял только функцию распределения, суммарное CFD). То есть нужна функция, дающая 50% в нуле, приближающаяся к 100% достаточно быстро при разнице рейтингов, и «симметричная» — приближающаяся к нулю в обратной оси.
Поэтому и проверять даже непонятно как — ещё раз, это не распределение рейтингов, эта функция описывает некую ненаблюдаемую величину, вероятность выигрыша. И как мне кажется, сама функция не имеет никакого значения, она определяют лишь «форму» рейтинга. Но не порядок игроков. То есть, грубо говоря, с одной функцией игрок, который «вдвое сильнее другого» (само по себе странное определение) будет иметь вдвое больший рейтинг, а с другой — на 2 очка больший, с третьей — нечто промежуточное и т.п. Но поскольку мы интересуемся лишь общим порядком игроков, сама функция не так уж и важна.
Я внятно свою точку зрения изложил?
Поэтому и проверять даже непонятно как — ещё раз, это не распределение рейтингов, эта функция описывает некую ненаблюдаемую величину, вероятность выигрыша. И как мне кажется, сама функция не имеет никакого значения, она определяют лишь «форму» рейтинга. Но не порядок игроков. То есть, грубо говоря, с одной функцией игрок, который «вдвое сильнее другого» (само по себе странное определение) будет иметь вдвое больший рейтинг, а с другой — на 2 очка больший, с третьей — нечто промежуточное и т.п. Но поскольку мы интересуемся лишь общим порядком игроков, сама функция не так уж и важна.
Я внятно свою точку зрения изложил?
Вы вашу силу расталкивания как считаете? Наверняка у вас есть какое-то «расстояние», и наверняка оно эвклидово — то есть корень из квадрата разности чего-то там. Так? Такое расстояние соответствует нормальному распределению, и оно плохо описывает ваш случай. Если вы это используете не только фор фан, но и в работе — обязательно сходите в какую-нибудь приличную библиотеку и возьмите книжицу про теорию решения некорректно поставленных задач. Там все строго описано, почему так нельзя делать и как нужно делать правильно. Но я неуверен, что такое можно найти в сети.
В случае шахматистов у вас дело обстоит так. Строите «плоский рейтинг» игроков — простое среднее очков, набираемых за партию, без учета силы соперников. Ну, сыграл 5 матчей — выиграл 3, слил 2 — плоский рейтинг равен 0.6. Ничья полбалла, ну как обычно.
Дальше рассматриваете каждый матч между игроками с рейтингами А и В. Соответственно «плоская разница» А-В, и она может быть от -1 до 1. Делите отрезок (-1;-1) на поддиапазоны с шагом скажем 0.1 — ну, [-1;-0.9), [-0.9; -0.8) и т.п. Это ось Х в вашей гистограмме. По оси y — среднее количество очков, которое набрали игроки (А) в матчах против соперников с рейтингом (А-В). Смотрите гистограмму, подбираете распределение — хотя это даже и не очень нужно, реальное распределение у вас уже есть в табличном виде. Для построения «честного» рейтинга просто суммируете набранные очки, деленные на поправку на разницу в классе между игроками в каждом матче. Такой рейтинг очень быстро станет стабильным, то есть большие движения рейтинга игрока из-за внешних факторов будут происходить редко.
В случае шахматистов у вас дело обстоит так. Строите «плоский рейтинг» игроков — простое среднее очков, набираемых за партию, без учета силы соперников. Ну, сыграл 5 матчей — выиграл 3, слил 2 — плоский рейтинг равен 0.6. Ничья полбалла, ну как обычно.
Дальше рассматриваете каждый матч между игроками с рейтингами А и В. Соответственно «плоская разница» А-В, и она может быть от -1 до 1. Делите отрезок (-1;-1) на поддиапазоны с шагом скажем 0.1 — ну, [-1;-0.9), [-0.9; -0.8) и т.п. Это ось Х в вашей гистограмме. По оси y — среднее количество очков, которое набрали игроки (А) в матчах против соперников с рейтингом (А-В). Смотрите гистограмму, подбираете распределение — хотя это даже и не очень нужно, реальное распределение у вас уже есть в табличном виде. Для построения «честного» рейтинга просто суммируете набранные очки, деленные на поправку на разницу в классе между игроками в каждом матче. Такой рейтинг очень быстро станет стабильным, то есть большие движения рейтинга игрока из-за внешних факторов будут происходить редко.
Первую часть не понял (ну, за исключением совета подучиться — спасибо, я уже), если есть какие-то конкретные идеи, пишите.
А по поводу второй части (проверка функции вероятности), если я правильно понял, выходит замкнутый круг: если мы построили рейтинг, то с его помощью мы можем построить функцию. Но как я писал, рейтинг мы можем построить только после выбора функции (предложенный вами вариант ну никак работать не будет, слишком разные силы у игроков, выигрыш в одной партии не равен выигрышу в другой).
То есть так можно в лучшем случае back testing (проверку, что выбранный закон уверенно воспроизводит самого себя) сделать, но даже для этого у нас мало точек. На 25 игроков 60 матчей пока что.
А по поводу второй части (проверка функции вероятности), если я правильно понял, выходит замкнутый круг: если мы построили рейтинг, то с его помощью мы можем построить функцию. Но как я писал, рейтинг мы можем построить только после выбора функции (предложенный вами вариант ну никак работать не будет, слишком разные силы у игроков, выигрыш в одной партии не равен выигрышу в другой).
То есть так можно в лучшем случае back testing (проверку, что выбранный закон уверенно воспроизводит самого себя) сделать, но даже для этого у нас мало точек. На 25 игроков 60 матчей пока что.
Что такое 120 знаков мантиссы? Сомневаюсь, что значащих десятичных цифр больше 15.
Если у вас есть величина x порядка 1E-120, то 1-x будет 0,99999… — 120 девяток, и только потом значащие цифры. То есть вы правы, конечно, значащих цифр немного, но они начинаются не сразу после запятой, и в этом и заключаются описанные грабли :-)
У меня большие сомнения, что Вы понимаете о чем говорите.
pastebin.com/XMFrjH7J
Пример из экселя, три столбца A, B и C = A — B. Выставлено максимальное количество значащих цифр (30) суть мантисса. Как-бы доказательство того, что 1 — 1e-120 = 1 и только при 1 — 1E-15 = 9,999999999999990000000000000000E-01
Скорее всего в расчетах используется число двойной точности. Может в 64 битном офисе перейдут на четверную, тогда количество девяток возрастет до 30
pastebin.com/XMFrjH7J
Пример из экселя, три столбца A, B и C = A — B. Выставлено максимальное количество значащих цифр (30) суть мантисса. Как-бы доказательство того, что 1 — 1e-120 = 1 и только при 1 — 1E-15 = 9,999999999999990000000000000000E-01
Скорее всего в расчетах используется число двойной точности. Может в 64 битном офисе перейдут на четверную, тогда количество девяток возрастет до 30
Я говорю в точности о том же, о чём и вы. Возможно я невнятно выразился, но я же в посте написал:
Проблема в том, что 1E-120 в обычной переменной держится без проблем, а вот 1 — 1E-120 уверенно округляется до единицы (120 знаков мантиссы не всякая переменная выдержит), и все расчёты идут насмарку.
То есть да, вы правы, 1 — 1e-120 = 1. И именно поэтому ничего не считается, в этом и грабли.
Когда чуть выше я писал про 120 девяток, я имел в виду математику. А когда я пишу, что это =1, я уже говорю про Excel, MatLab и пр. компьютерные системы, которым приходится в какой-то момент округлять.
Проблема в том, что 1E-120 в обычной переменной держится без проблем, а вот 1 — 1E-120 уверенно округляется до единицы (120 знаков мантиссы не всякая переменная выдержит), и все расчёты идут насмарку.
То есть да, вы правы, 1 — 1e-120 = 1. И именно поэтому ничего не считается, в этом и грабли.
Когда чуть выше я писал про 120 девяток, я имел в виду математику. А когда я пишу, что это =1, я уже говорю про Excel, MatLab и пр. компьютерные системы, которым приходится в какой-то момент округлять.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Рейтинг на основании истории