Пользователь
0,0
рейтинг
24 февраля 2013 в 21:18

Разработка → Введение в Байесовские методы из песочницы tutorial

В качестве введения


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

В дальнейшем я бы хотел перейти к непосредственно Байесовскому анализу и рассказать об обработке реальных данных и о, на мой взгляд, отличной альтернативе языку R (о нем немного писалось тут) — Python с модулем pymc. Лично мне Python кажется гораздо более понятным и логичным, чем R с пакетами JAGS и BUGS, к тому же Python дает гораздо большую свободу и гибкость (хотя в Python есть и свои трудности, но они преодолимы, да и в простом анализе встречаются нечасто).

Немного истории


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

О вероятности и теореме Байеса


Формула Байеса и все последующее изложение требует понимания вероятности. Подробнее о вероятности можно почитать на Википедии.
На практике вероятность наступления события есть частота наступления этого события, то есть отношение количества наблюдений события к общему количеству наблюдений при большом (теоретически бесконечном) общем количестве наблюдений.
Рассмотрим следующий эксперимент: мы называем любое число из отрезка [0, 1] и смотрим за тем, что это число будет между, например, 0.1 и 0.4. Как нетрудно догадаться, вероятность этого события будет равна отношению длины отрезка [0.1, 0.4] к общей длине отрезка [0, 1] (другими словами, отношение «количества» возможных равновероятных значений к общему «количеству» значений), то есть (0.4 — 0.1) / (1 — 0) = 0.3, то есть вероятность попадания в отрезок [0.1, 0.4] равна 30%.

Теперь посмотрим на квадрат [0, 1] x [0, 1].
image

Допустим, мы должны называть пары чисел (x, y), каждое из которых больше нуля и меньше единицы. Вероятность того, что x (первое число) будет в пределах отрезка [0.1, 0.4] (показан на первом рисунке как синяя область, на данный момент для нас второе число y не важно), равна отношению площади синей области к площади всего квадрата, то есть (0.4 — 0.1) * (1 — 0) / (1 * 1) = 0.3, то есть 30%. Таким образом можно записать, что вероятность того, что x принадлежит отрезку [0.1, 0.4] равна p(0.1 <= x <= 0.4) = 0.3 или для краткости p(X) = 0.3.
Если мы теперь посмотрим на y, то, аналогично, вероятность того, что y находится внутри отрезка [0.5, 0.7] равна отношению площади зеленой области к площади всего квадрата p(0.5 <= y <= 0.7) = 0.2, или для краткости p(Y) = 0.2.
Теперь посмотрим, что можно узнать о значениях одновременно x и y.
Если мы хотим знать, какова вероятность того, что одновременно x и y находятся в соответствующих заданных отрезках, то нам нужно посчитать отношение темной площади (пересечения зеленой и синей областей) к площади всего квадрата: p(X, Y) = (0.4 — 0.1) * (0.7 — 0.5) / (1 * 1) = 0.06.

А теперь допустим мы хотим знать какова вероятность того, что y находится в интервале [0.5, 0.7], если x уже находится в интервале [0.1, 0.4]. То есть фактически у нас есть фильтр и когда мы называем пары (x, y), то мы сразу отбрасывает те пары, которые не удовлетворяют условию нахождения x в заданном интервале, а потом из отфильтрованных пар мы считаем те, для которых y удовлетворяет нашему условию и считаем вероятность как отношение количества пар, для которых y лежит в вышеупомянутом отрезке к общему количеству отфильтрованных пар (то есть для которых x лежит в отрезке [0.1, 0.4]). Мы можем записать эту вероятность как p(Y|X). Очевидно, что эта вероятность равна отношению площади темной области (пересечение зеленой и синей областей) к площади синей области. Площадь темной области равна (0.4 — 0.1) * (0.7 — 0.5) = 0.06, а площадь синей (0.4 — 0.1) * (1 — 0) = 0.3, тогда их отношение равно 0.06 / 0.3 = 0.2. Другими словами, вероятность нахождения y на отрезке [0.5, 0.7] при том, что x уже принадлежит отрезку [0.1, 0.4] равна p(Y|X) = 0.2.
Можно заметить, что с учетом всего вышесказанного и всех приведенных выше обозначений, мы можем написать следующее выражение
p(Y|X) = p(X, Y) / p(X)

Кратко воспроизведем всю предыдущую логику теперь по отношению к p(X|Y): мы называем пары (x, y) и фильтруем те, для которых y лежит между 0.5 и 0.7, тогда вероятность того, что x находится в отрезке [0.1, 0.4] при условии, что y принадлежит отрезку [0.5, 0.7] равна отношению площади темной области к площади зеленой:
p(X|Y) = p(X, Y) / p(Y)

В двух приведенных выше формулах мы видим, что член p(X, Y) одинаков, и мы можем его исключить:
image
Мы можем переписать последнее равенство как
image

Это и есть теорема Байеса.
Интересно еще заметить, что p(Y) это фактически p(X,Y) при всех значениях X. То есть, если мы возьмем темную область и растянем ее так, что она будет покрывать все значения X, она будет в точности повторять зеленую область, а значит, она будет равна p(Y). На языке математики это будет означать следующее: image
Тогда мы можем переписать формулу Байеса в следующем виде:
image

Применение теоремы Байеса


Давайте рассмотрим следующий пример. Возьмем монетку и подкинем ее 3 раза. С одинаковой вероятностью мы можем получить следующие результаты (О — орел, Р — решка): ООО, ООР, ОРО, ОРР, РОО, РОР, РРО, РРР.

Мы можем посчитать какое количество орлов выпало в каждом случае и сколько при этом было смен орел-решка, решка-орел:
image

Мы можем рассматривать количество орлов и количество изменений как две случайные величины. Тогда таблица вероятностей будет иметь следуюший вид:
image

Теперь мы можем увидеть формулу Байеса в действии.
Но прежде проведем аналогию с квадратом, который мы рассматривали ранее.
Можно заметить, что p(1O) есть сумма третьего столбца («синяя область» квадрата) и равна сумме всех значений ячеек в этом столбце: p(1O) = 2/8 + 1/8 = 3/8
p(1С) есть сумма третьей строки («зеленая область» квадрата) и, аналогично, равна сумме всех значений ячеек в этой строке p(1С) = 2/8 + 2/8 = 4/8
Вероятность того, что мы получили одного орла и одну смену равна пересечению этих областей (то есть значение в клетке пересечения третьего столбца и третьей строки) p(1С, 1О) = 2/8
Тогда, следуя формулам описанным выше, мы можем посчитать вероятность получить одну смену, если мы получили одного орла в трех бросках:
p(1С|1О) = p(1С, 1О) / p(1О) = (2/8) / (3/8) = 2/3
или вероятность получить одного орла, если мы получили одну смену:
p(1О|1С) = p(1С, 1О) / p(1С) = (2/8) / (4/8) = 1/2
Если мы посчитаем вероятность получить одну смену при наличии одного орла p(1О|1С) через формулу Байеса, то получим:
p(1О|1С) = p(1С|1О) * p(1О) / p(1С) = (2/3) * (3/8) / (4/8) = 1/2
Что мы и получили выше.

Но какое практическое значение имеет приведенный выше пример?
Дело в том, что, когда мы анализируем реальные данные, обычно нас интересует какой-то параметр этих данных (например, среднее, дисперсия и пр.). Тогда мы можем провести следующую аналогию с вышеприведенной таблицей вероятностей: пусть строки будут нашими экспериментальными данными (обозначим их Data), а столбцы — возможными значениями интересующего нас параметра этих данных (обозначим его image). Тогда нас интересует вероятность получить определенное значение параметра на основе имеющихся данных image.
Мы можем применить формулу Баейса и записать следующее:
image
А вспомнив формулу с интегралом, можно записать следующее:
image

То есть фактически как результат нашего анализа мы имеет вероятность как функцию параметра. Теперь мы можем, например, максимизировать эту функцию и найти наиболее вероятное значение параметра, посчитать дисперсию и среднее значение параметра, посчитать границы отрезка, внутри которого интересующий нас параметр лежит с вероятностью 95% и пр.

Вероятность image называют апостериорной вероятностью. И для того, чтобы посчитать ее нам надо иметь
image — функцию правдоподобия и image — априорную вероятность.
Функция правдоподобия определяется нашей моделью. То есть мы создаем модель сбора данных, которая зависит от интересующего нас параметра. К примеру, мы хотим интерполировать данные с помощью прямой y = a * x + b (таким образом мы предполагаем, что все данные имеют линейную зависимость с наложенным на нее гауссовым шумом с известной дисперсией). Тогда a и b — это наши параметры, и мы хотим узнать их наиболее вероятные значения, а функция правдоподобия — гаусс со средним, заданным уравнением прямой, и данной дисперсией.
Априорная вероятность включает в себя информацию, которую мы знаем до проведения анализа. Например, мы точно знаем, что прямая должна иметь положительный наклон, или, что значение в точке пересечения с осью x должно быть положительным, — все это и не только мы можем инкорпорировать в наш анализ.
Как можно заметить, знаменатель дроби является интегралом (или в случае, когда параметры могут принимать только определенные дискретные значения, суммой) числителя по всем возможным значениям параметра. Практически это означает, что знаменатель является константой и служит для того, что нормализировать апостериорную вероятность (то есть, чтобы интеграл апостериорной вероятности был равен единице).

На этом я бы хотел закончить свой пост (продолжение тут). Буду рад вашим комментариям.
Максим Иришкин @Maxim_I
карма
23,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (37)

  • +6
    Сколько классных формул, алгоритмов существует. Вот бы еще знать как на практике их применять!
    • +3
      Как раз об этом я хочу написать в следующем посте. Просто если не понимать базовую теорию, о которой я здесь написал, то на практике все становится слишком запутанным.
    • 0
      Практических применений у этих формул — несчетное множество. На вот этой самой формуле Байеса построена вся современная радиотехника. Например, алгоритмы слежения за сигналом — ничто иное, как алгоритмы расчета (в приведенных в статье обозначениях) p(\theta | Data). Где \theta — различные параметры сигнала, а Data — принятый сигнал.
  • +3
    В моем текущем проекте (ИС для выявления мошенничества на производственном предприятии) используется формула Байеса в разновидности алгоритма likelihood ratio test. Для определения вероятности фрода при наличии/отсутствии нескольких фактов, косвенно свидетельствующих в пользу гипотезы о возможности совершения фрода. Алгоритм самообучаем (с обратной связью), т.е. пересчитывает свои коэффициенты (условные вероятности) при фактическом подтверждении или неподтверждении фрода при проверке службой экономической безопасности.

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

    Еще один нюанс, с которым пришлось столкнуться — к сожалению, практически все мало-мальски ПОЛЕЗНОЕ НА ПРАКТИКЕ на эту тему написано на английском языке. В русскоязычных источниках в-основном только общеизвестная теория с демонстрационными примерами лишь для самых примитивных случаев.
    • +1
      практически все мало-мальски ПОЛЕЗНОЕ НА ПРАКТИКЕ на эту тему написано на английском языке


      На русском языке довольно много материала по байесовым методам содержится в книге В.Ю. Терибежа «Введение в статистическую теорию обратных задач» (2005). В этой книге в основном рассматриваются классические обратные задачи матфизики (типа уравнения Фредгольма первого рода aka восстановление размытого изображения), но все задачи, решаемые с помощью байесовых методов, по сути относятся к классу обратных задач. (Предупреждение: для чтения этой книжки необходима хорошая математическая подготовка.)
    • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        Сама ИС на методологии COSO Internal Controls основана. Контроли в основном на жестких правилах, но есть ряд задач, когда жестких критериев нарушения нет и нужно выбрать из «генеральной совокупности» бизнес-объектов наиболее подозрительные для последующей ручной проверки. Опыт и знание бизнес-процесса обычно позволяют указать 5-7 вычисляемых событий, которые сами по себе (по отдельности) ничего не значат и «жареными фактами», подтверждающими мошенничество, не являются, но повышают подозрительность. А дальше эти события в совокупности «голосуют» за или против гипотезы о фроде применительно к конкретному бизнес-объекту (экземпляру бизнес-процесса). Формула: Постериорный шанс фрода = (априорный шанс фрода) * LR (событие1) * LR(событие2) *...* LR(событиеN). События должны быть взаимно независимыми, чтобы тупое домножение на LR работало (иначе надо учитывать разные последовательности появления событий и, соответственно, условные шансы, что крайне существенно усложнит формулу).

        МГУА глянул — очень сильная вещь, буду изучать, спасибо.
  • +1
    Хоть и на английском, но мне понравилось как разъясняются Байесовские методы в книге Christopher M. Bishop «Pattern Recognition and Machine Learning» — хорошие примеры, много иллюстраций, простой, технический английский.
    Сейчас времени не ахти как много, после диплома хочу тоже куда-нибудь это применить. Найти бы ещё простую тему =).
  • +1
    Что касается книжек, то мне очень нравится книга John K. Kruschke «Doing Bayesian Data Analysis: A Tutorial with R and BUGS». Я думаю, это одна из лучших (если не лучшая) практических книг по Байесовскому анализу данных. Она блестяще написана, там приведено большое количество программ на R и после всех глав есть упражнения к этим программам, что позволяет почувствовать теорию на практике.
    Еще есть замечательная книга D. Sivia «Data Analysis: A Bayesian Tutorial». Она ориентирована на практику, хотя там не рассматриваются вопросы реализации анализа на каком-либо языке.
    И, наконец, Andrew Gelman et all. «Bayesian Data Analysis» — это замечательный учебник, хотя в большей степени теоретический.
  • 0
    А можете привести пару практических задач, где требуется применение Байесовских методов?

    P.S. Если в статье было и я пропустил, просто ткните в абзац.
    • 0
      SpamAssasin использует байесовские методы для нахождения спама :)
  • +1
    В принципе их можно применять абсолютно везде (другой вопрос, насколько это целесообразно).
    Вообще, есть три цели анализа данных: оценка параметров, прогнозирование данных и сравнение моделей. С помощью байесовских методов можно достичь все три цели.
    Из практических примеров, можно назвать следующее, что приходит в голову.
    Как писал MAGNUS8, на основе байесовских сетей можно строить системы принятия решений.
    Еще одна практическая задача, которой занимаюсь я, состоит в обработке данных физического эксперимента. Есть данные с различных приборов. Причем одни приборы измеряют точно величину параметра, но у них большая неопределенность в координате измерения (то есть измеряют точно, но непонятно где), а другие измеряют в определенном месте, но неточно. С помощью байесовского анализа можно анализировать данные с разных приборов не изолированно, а вместе, за счет чего достигается эффект синергии, и неопределенность в результатах уменьшается.
    Еще одна частая задачка в физике и астрономии состоит в следующем. У вас есть сильнозашумленные данные, в которых есть сигналы определенной формы. Но из-за шума вы не можете сказать, в какое время сигналы появлялись и какова их амплитуда. Байесовский анализ в этом поможет.
    На основе байесовского анализа вы можете прогнозировать данные. Например, у вас есть исторический тренд какого-то параметра (например, стоимость акций, ВВП и пр.), и вы ходите узнать, с какой вероятностью в следующий момент времени произойдет скачок этого параметра на определенную величину (такой тип задач можно найти и в физике, и в, например, финансах и экономике).
    • –2
      Спасибо за развернутый ответ.
      Буду знать какие области стороной обходить.)
    • 0
      Еще одна частая задачка в физике и астрономии состоит в следующем. У вас есть сильнозашумленные данные, в которых есть сигналы определенной формы. Но из-за шума вы не можете сказать, в какое время сигналы появлялись и какова их амплитуда. Байесовский анализ в этом поможет.

      А он не превратится в этой ситуации в best-fit по методу наименьших квадратов (если априорных оценок на распределение возможных моментов начала и на закон распределения амплитуд нет)?
      • 0
        Он превратится в метод наименьших квадратов (МНК), если априорное распределение будет равномерным (с широкими границами — иначе апостериорное распределение будет «обрубаться» на границах), а функция правдоподобия — нормальной с известной дисперсией. То есть фактическим МНК является частным случаем общего анализа при определенных предположениях.
        • +1
          Я подумал, что, может быть, лучше продемонстрировать вышесказанное на формулах.
          Теорема Байеса:
          p(\theta | Data) ~ p(Data | \theta)*p(\theta) — знаменатель я опустил, т.к. он является константов для нормализации.
          Если априорное распределение равномерное, то p(\theta) ~ 1/(b-a), где a и b — границы распределения (мы их можем отодвинуть настолько далеко, насколько хотим). Этот член тоже является константой и его можно опустить,
          Если мы считаем, что функция правдоподобия нормальная, то
          p(Data | \theta) = 1/(sqrt(2*pi)*sigma) * exp(- sum( (Data_i — model)^2 / (2*sigma^2) ))
          sum( (Data_i — model)^2 / (2*sigma^2) ) есть как раз сумма \chi^2
          итого p(Data | \theta) = 1/(sqrt(2*pi)*sigma) * exp(- sum(\chi^2) )
          Коэффициент 1/(sqrt(2*pi)*sigma) есть константа (если sigma нам задано), таким образом, выкидывая все константы, мы получаем выражение для апостериорной вероятности:
          p(\theta | Data) ~ exp(- sum(\chi^2) )
          Максимум этого выражения будет как раз в точке минимума суммы \chi^2
          То есть при предположениях о равномерности априорного распределения, нормальности функции правдоподобия и заданности сигмы, из формулы Байеса непосредственно следует метод наименьших квадратов.
          • 0
            И где же здесь используется заданность сигмы? Достаточно, что она не зависит от времени.
            • 0
              Одинаковость сигмы это частный случай. Строго говоря, она не обязательно должна быть одинаковой. У вас может быть, например, два набора данных с двумя сигмами или вообще для каждой точки будет своя сигма, в этих случаях метод наименьших квадратов тоже применим и необходимо знать сигмы (или, по крайней мере, их отношения).
            • НЛО прилетело и опубликовало эту надпись здесь
              • 0
                Да, это хороший пример — как, зная неодинаковость шума, учесть её в коэффициентах МНК. Интуитивно это не очень очевидно, а так — можно подумать. Правда, потом возникнет вопрос, насколько можно доверять использованным оценкам шума, и в итоге всё скатится к чему-нибудь самому примитивному… но всякое бывает. Посмотрим…
                • 0
                  Эти коэффициетны берутся из соотношений сигм. Например, для двух точек с разными сигмами:
                  sum(\chi^2) = ( (Data_1 — model_value_at_point_1) / \sigma_1 )^2 + ( (Data_2 — model_value_at_point_2) / \sigma_2 )^2
                  С точки зрения минимизации, все равно минимизировать ли sum(\chi^2) или эту сумму, поделенную или умноженную на любую константу, поэтому мы ее можем умножить на, например, \sigma_1^2:
                  sum(\chi^2) * \sigma_1^2 = (Data_1 — model_value_at_point_1) ^2 + ( \sigma_1 / \sigma_1)^2(Data_2 — model_value_at_point_2)^2
                  Получается, что ( \sigma_1 / \sigma_1)^2 это и есть коэффициент.
                  Поэтому я говорил, что в наименьших квадратах необходимо знать сигмы или их отношения. В Байесовском анализе это ограничение снимается. Здесь можно саму сигму (или сигмы) считать как параметр и находить его постериорное распределение. Понятно, что эта неопределенность отражается и на результатах (итоговая погрешность увеличивается).
                  • НЛО прилетело и опубликовало эту надпись здесь
  • –4
    Прочитал заголовок как «Введение в бесовские методы». Видимо, надо меньше смотреть новости.
  • +1
    Отличный рассказ о теореме Байеса: yudkowsky.net/rational/bayes (на английском). Там есть очень интересные интерактивные упражнения, с помощью которых можно понять теорему практически интуитивно и к концу статьи самому ее вывести.
  • 0
    Я использовал метод Байеса в своей дипломной работе «Динамические экспертные системы при оценке рисков в страховании». Основной конечно же были генетические алгоритмы в сочетании с методом Байеса.
  • 0
    Написано очень интересно, но некоторые места не совсем понятны. В виду того, что образование гуманитарное, а все остальное самостоятельное изучение «т.к. интересно и хочу знать и применять», то возникает вопрос: какие доп. знания необходимы для полного усвоения материала?
    • +2
      Честно говоря, я затрудняюсь ответить на ваш вопрос. Тут, скорее, все зависит от того, какие именно места непонятны.
      В общем, я бы сказал, что хорошо бы прочитать учебник по теории вероятностей.
      Если говорить конкретно о Байесовских методах, то можно почитать John K. Kruschke «Doing Bayesian Data Analysis: A Tutorial with R and BUGS» (к сожалению, только на английском). Эта книга написана очень просто и интересно. Мне кажется, что там все рассказывается очень подробно и с нуля.
      • 0
        Большое спасибо.
  • 0
    По сути, вся статья сводится к анализу и иллюстрации собственно формулы Байеса. Это важно и полезно, но было бы интересно прочитать продолжение, более приближенное к реальности — с функциями распределения и их параметрами, а также с неизвестными параметры статистической модели.
    • +1
      Продолжение почти готово.
      Собственно, задача этой статьи и была в том, чтобы рассказать о формуле Байеса (да, разочаровывающе, но это так), потому что без нее невозможно понимать весь анализ. Это центральная формула, вокруг которой строится вся теория и практика.
  • 0
    Я то надеялся какие-то интересные приложения увидеть (кроме заезженных спамовых фильтров). А так — тупо пересказ параграфа из стандартного учебника, с сюсюканием и показыванием на пальцах очевидных вещей.

    Это не в упрек, а в совет. Хорошая статья должна быть уникальной, со свежими мыслями и новизной.
    • +2
      Честно говоря, я за популяризацию и за то, чтобы рассказывать просто о каких-то вещах, которые люди не знали. Как по мне, так лучше пусть 10 человек увидят впервые (или не впервые) простую картинку и действительно ее поймут, чем 1 человек увидит интересные приложения и удовлетворит свой интерес, а остальные 9 их увидят и сразу закроют.

      P.S.
      Если вы знаете «стандартный учебник» на русском языке с простым изложением данной темы, дайте ссылку, пожалуйста.
      • 0
        Если вы знаете «стандартный учебник» на русском языке с простым изложением данной темы, дайте ссылку, пожалуйста.

        В любом эта тема одинаково хорошо расписана. Я учился по Вентцель, Овчаров «Теория вероятностей и её инженерные приложения».
  • 0
    картинки все поломались:(
    • 0
      Странно. У меня все загружается правильно.
      А какие именно картинки? Или все?
      • 0
        Сейчас уже отображаеться нормально:)
      • 0
        Вот у меня сейчас не грузятся.
        Вообще все.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.