12 апреля 2013 в 16:31

Вероятностные модели: байесовские сети tutorial

В этом блоге мы уже много о чём поговорили: были краткие описания основных рекомендательных алгоритмов (постановка задачи, user-based и item-based, SVD: 1, 2, 3, 4), о нескольких моделях для работы с контентом (наивный Байес, LDA, обзор методов анализа текстов), был цикл статей о холодном старте (постановка задачи, текстмайнинг, теги), была мини-серия о многоруких бандитах (часть 1, часть 2).

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




Задачи байесовского вывода


Сначала кратко напомню то, о чём мы уже говорили. Главным инструментом машинного обучения является теорема Байеса:
image
Здесь D — это данные, то, что мы знаем, а θ — это параметры модели, которые мы хотим обучить. Например, в модели SVD данные — это те рейтинги, которые ставили пользователи продуктам, а параметры модели — факторы, которые мы обучаем для пользователей и продуктов. image — это то, что мы хотим найти, распределение вероятностей параметров модели после того, как мы приняли во внимание данные; это называется апостериорной вероятностью (posterior probability). Эту вероятность, как правило, напрямую не найти, и здесь как раз и нужна теорема Байеса. image – это так называемое правдоподобие (likelihood), вероятность данных при условии зафиксированных параметров модели; это как раз найти обычно легко, собственно, конструкция модели обычно в том и состоит, чтобы задать функцию правдоподобия. А imageаприорная вероятность (prior probability), она является математической формализацией нашей интуиции о предмете, формализацией того, что мы знали раньше, ещё до всяких экспериментов.

Таким образом, мы приходим к одной из основных задач байесовского вывода: найти апостериорное распределение на гипотезах/параметрах:
image
и найти максимальную апостериорную гипотезу image.

Факторизация сложных распределений и байесовские сети


Но если всё так просто — умножили две функции, максимизировали результат — о чём же здесь целая наука? Проблема заключается в том, что распределения, которые нас интересуют, обычно слишком сложные, чтобы их можно было максимизировать напрямую, аналитически. В них слишком много переменных, между переменными слишком сложные связи. Но, с другой стороны, часто в них есть дополнительная структура, которую можно использовать, структура в виде независимостей (image) и условных независимостей (image) некоторых переменных.

Вспомните наш разговор о наивном Байесе: в модели там получалось неподъёмное число параметров, и мы сделали дополнительное предположение об условной независимости атрибутов (слов) при условии темы:
image
В результате сложное апостериорное распределение image удалось переписать как
image
и в этой форме с ним оказалось гораздо проще справиться (обучить параметры каждого маленького распределения по отдельности, а затем выбрать v, дающее максимум произведения). Это один из простейших примеров разложения (факторизации) сложного распределения в произведение простых. Сегодня и в последующих текстах мы сможем обобщить этот метод и довести его до непревзойдённых высот.

Итак, давайте рассмотрим один из самых удобных способов представлять большие и сложные распределения вероятностей – байесовские сети доверия (Bayesian belief networks), которые в последнее время чаще называются просто направленными графическими моделями (directed graphical models). Байесовская сеть – это направленный граф без направленных циклов (это очень важное условие!), в котором вершины соответствуют переменным в распределении, а рёбра соединяют «связанные» переменные. В каждом узле задано условное распределение узла при условии своих родителей image, и граф байесовской сети означает, что большое совместное распределение раскладывается в произведение этих условных распределений.

Вот, например, граф, соответствующий наивному байесу:
naive
Он соответствует разложению
image
у C нет предков, так что мы берём его безусловное (маргинальное) распределение, а каждый из Ai «растёт» непосредственно из C и больше ни с кем не связан.

Мы уже знаем, что в этом случае все атрибуты Ai условно независимы при условии категории C:
image
Давайте теперь рассмотрим все простейшие варианты байесовской сети и посмотрим, каким условиям независимости между переменными они соответствуют.

Байесовские сети с двумя и тремя переменными: тривиальные случаи


Начнём с сети из двух переменных, x и y. Здесь всего два варианта: либо между x и y нет ребра, либо есть. Если ребра нет, это просто значит, что x и y независимы, ведь такой граф соответствует разложению image.


А если ребро есть (пусть оно идёт из x в y, это не важно), мы получаем разложение image, которое буквально по определению условной вероятности тупо верно всегда, для любого распределения image. Таким образом, граф из двух вершин с ребром не даёт нам новой информации.


Теперь переходим к сетям из трёх переменных, x, y и z. Самый простой случай – когда рёбер совсем нет.

Как и с двумя переменными, это значит, что x, y и z просто независимы: image.

Другой простой случай – когда между переменными проведены все рёбра.

Этот случай тоже аналогичен рассмотренному выше; пусть, например, рёбра идут из x в y и z, а также из y в z. Мы получаем разложение
image
которое, опять же, верно всегда, для любого совместного распределения image. В этой формуле можно было бы выбирать переменные в любом порядке, ничего не изменилось бы. Обратите внимание, что направленные циклы в байесовских сетях запрещены, и в результате вариантов, как можно провести все рёбра, всего шесть, а не восемь.

Эти наблюдения, конечно, обобщаются и на случай любого числа переменных: если переменные вообще никак не связаны друг с другом, они независимы, а граф, в котором проведены все рёбра (со стрелочками в любых направлениях, но так, чтобы не получалось направленных циклов), соответствует разложению, которое всегда верно, и не даёт нам никакой информации.

Байесовские сети с тремя переменными: интересные случаи


В этом разделе мы рассмотрим три более интересных случая – это и будут те «кирпичики», из которых можно составить любую байесовскую сеть. К счастью, для этого достаточно рассмотреть графы на трёх переменных – всё остальное будет обобщаться из них. В примерах ниже я несколько погрешу против истины и буду интуитивно интерпретировать ребро, стрелочку между двумя переменными, как «x влияет на y», т.е. по сути как причинно-следственную связь. На самом деле это, конечно, не совсем так – например, часто можно развернуть ребро, не потеряв смысла (вспомните: в графе из двух переменных было всё равно, в какую сторону проводить ребро). Да и вообще это непростой философский вопрос – что такое «причинно-следственные связи» и зачем они нужны. Но для рассуждений на пальцах сойдёт.

Последовательная связь


Начнём с последовательной связи между переменными: x «влияет на» y, а y, в свою очередь, «влияет на» z.

Такой граф изображает разложение
image

Интуитивно это соответствует последовательной причинно-следственной связи: если вы будете бегать зимой без шапки, вы простудитесь, а если простудитесь, у вас поднимется температура. Очевидно, что x и y, а также y и z друг с другом связаны, между ними даже непосредственно стрелочки проведены. Связаны ли между собой в такой сети x и z, зависимы ли эти переменные? Конечно! Если вы бегаете зимой без шапки, вероятность получить высокую температуру повышается. Однако в такой сети x и z связаны только через y, и если мы уже знаем значение y, x и z становятся независимыми: если вы уже знаете, что простудились, совершенно не важно, чем это было вызвано, температура теперь повысится (или не повысится) именно от простуды.

Формально это соответствует условной независимости x и z при условии y; давайте это проверим:
image
где первое равенство – это определение условной вероятности, второе – наше разложение, а третье – применение теоремы Байеса.

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

Расходящаяся связь


Следующий возможный вариант – расходящаяся связь: x «влияет» и на y, и на z.

Такой граф изображает разложение
image

Интуитивно это соответствует двум следствиям из одной и той же причины: если вы простудитесь, у вас может подняться температура, а также может начаться насморк. Как и в предыдущем случае, очевидно, что x и y, а также x и z зависимы, и вопрос заключается в зависимости между y и z. Опять же, очевидно, что эти переменные зависимы: если у вас насморк, это повышает вероятность того, что вы простудились, а значит, вероятность высокой температуры тоже повышается.

Однако в такой сети, подобно предыдущему случаю, y и z связаны только через x, и если мы уже знаем значение общей причины x, y и z становятся независимыми: если вы уже знаете, что простудились, насморк и температура становятся независимы. Disclaimer: мои медицинские примеры крайне условны, на самом деле я понятия не имею, независимы ли в жизни насморк и температура при условии простуды, и даже подозреваю что вряд ли, т.к. многие другие болезни тоже могут вызывать оба этих симптома вместе. Но в нашей условной модели во вселенной нет других болезней, кроме простуды.

Формально это соответствует условной независимости y и z при условии x; проверить это ещё проще, чем для последовательной связи:
image

Итак, расходящаяся связь между тремя переменными говорит нам о том, что «следствия» условно независимы при условии своей «общей причины». Если причина известна, то следствия становятся независимы; пока причина неизвестна, следствия через неё связаны. Опять же, пока вроде бы ничего удивительного.

Сходящаяся связь


У нас остался только один возможный вариант связи между тремя переменными: сходящаяся связь, когда x и y вместе «влияют на» z.

Разложение здесь получается такое:
image

Это ситуация, в которой у одного и того же следствия могут быть две разные причины: например, температура может быть следствием простуды, а может – отравления. Зависимы ли простуда и отравление? Нет! В этой ситуации, пока общее следствие неизвестно, две причины никак не связаны друг с другом, и это очень легко проверить формально:
image

Однако если «общее следствие» z становится известным, ситуация меняется. Теперь общие причины известного следствия начинают влиять друг на друга. Этот феномен по-английски называется «explaining away»: предположим, что вы знаете, что у вас температура. Это сильно повышает вероятность как простуды, так и отравления. Однако если вы теперь узнаете, что отравились, вероятность простуды уменьшится – симптом «уже объяснён» одной из возможных причин, и вторая становится менее вероятной.

Таким образом, при сходящейся связи две «причины» независимы, но только до тех пор, пока значение их «общего следствия» неизвестно; если же общее следствие получает означивание, причины становятся зависимыми.

Но есть, как говорил Василий Иванович, один нюанс: когда на пути встречается сходящаяся связь, недостаточно посмотреть только на её «общее следствие», чтобы определить независимость. На самом деле, если даже у z означивания нету, но оно есть у одного из её потомков (возможно, достаточно далёких), две причины всё равно станут зависимы. Интуитивно это тоже легко понять: например, пусть мы не наблюдаем собственно температуру, а наблюдаем её потомка – показания градусника. На свете, наверное, бывают неисправные градусники, так что это тоже некая вероятностная связь. Однако наблюдение показаний градусника точно так же делает простуду и отравление зависимыми.

Putting it all together


Последовательная, сходящаяся и расходящаяся связи – это те три кирпичика, из которых состоит любой ациклический направленный граф. И наших рассуждений вполне достаточно для того, чтобы обобщить результаты об условной зависимости и независимости на все такие графы. Конечно, здесь не время и не место для того, чтобы формально доказывать общие теоремы, но результат достаточно предсказуем – предположим, что вам нужно в большом графе проверить, независимы ли две вершины (или даже два множества вершин). Для этого вы смотрите на все пути в графе (без учёта стрелочек), соединяющие эти два множества вершин. Каждый из этих путей можно «разорвать» одной из вышеописанных конструкций: например, последовательная связь разорвётся, если в середине у неё есть означивание (значение переменной известно), а сходящаяся связь разорвётся, если, наоборот, означивания нет (причём нет ни в самой вершине из пути, ни в её потомках). Если в результате все пути окажутся разорваны, значит, множества переменных действительно независимы; если нет – нет.

Итак, сегодня мы рассмотрели простое, удобное и важное представление факторизаций сложных распределений – байесовские сети. В следующий раз мы рассмотрим другое (но, конечно, похожее) графическое представление и начнём развивать алгоритмы вывода, т.е. решения задач байесовского вывода в сложных вероятностных моделях.
Автор: @snikolenko
Surfingbird
рейтинг 59,80
Компания прекратила активность на сайте

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

  • +4
    Может быть «байесовы»?
    P.S.
    Очень круто людей заинтересовывать конечно, спасибо автору. Но вообще кому интересно советую полноценную книгу взять и почитать.
  • +2
    P(D | θ) – это так называемое правдоподобие (likelihood), вероятность данных при условии зафиксированных параметров модели


    а разве не наоборот image?
    • –1
      • 0
        из вами приведенной ссылки

        Фу́нкция правдоподо́бия в математической статистике — это совместное распределение выборки из параметрического распределения, рассматриваемое как функция параметра.


        из английской педивикии

        In statistics, a likelihood function (often simply the likelihood) is a function of the parameters of a statistical model, defined as follows: the likelihood of a set of parameter values, θ, given some observed outcomes, x, is equal to the probability of those observed outcomes given those parameter values


        вы называете словом likelihood
        вероятность данных при условии зафиксированных параметров модели


        а вообще как бы наоборот, функция правдоподобия, likelihood function, или просто likelihood это функция от параметров мадели, при данных данных, простите за тавтологию; я хочу сказать что вероятность данных при фиксированных параметрах это просто условная вероятность данных P(D | θ), а likelihood наоборот

        как раз суть maximization шага в EM алгоритме, максимизировать функцию правдоподобия от параметров модели, найти argmax параметров в общем
        • –1
          Не очень понял посыл. Собственно я отреагировал на Ваше замечание о том, что тождество:
          L(\theta) = p( D | \theta)
          неверно.

          Правдоподобие (Likehood) — вероятность полученной выборки (D) при заданных значениях некоторых параметров модели (\theta), рассматриваемая как функция этих параметров.

          Исторически она вводилась для статистических моделей в которых \theta рассматривалась как неизвестная, но не случайная величина. Но потом её обобщили и на СВ.

          В этом смысле автор использует понятие верно.
          • 0
            нене, я не сказал
            что тождество:
            L(\theta) = p( D | \theta)
            неверно.

            а то что по likelihood function подразумевается не при фиксированных параметрах модели θ, а как раз функция от параметров

            вспомните expectation maximization алгоритм, на шаге expectation мы ищем ожидаемые значения данных при фиксированных параметрах θ, а на шаге максимизации мы как раз строим функцию, при фиксированных ожиданиях модели, от параметров модели, затем ищем такие параметры модели, что бы максимизировать вероятность данных. в этом то и суть likelihood function. например можно вычислить градиент f(θ) при данных D, найти максимум функции, и на следующем шаге expectation использовать как раз уже фиксированные θ
            • 0
              Фразой «зафиксированных параметров» автор подметил тот факт, что данная вероятность данных D рассматривается при реализованных параметрах \theta. То есть речь об условной плотности вероятности p (D| \theta). То, что \theta нельзя варьировать и тем самым получать функцию от детерминированной величины — автор не утверждал.

              Иначе говоря, мы сейчас по-существу доказываем друг другу одно и то же. Просто Вы слова автора интерпретировали по-своему. Тем не менее, я настаиваю, изначальная формулировка верна. Правдоподобие — это действительно «вероятность выборки при фиксированных параметрах», то есть тождественно равно P(D | \theta) и от этого никуда не деться.
    • 0
      Функция правдоподобия – это функция от той переменной, по которой условие; в данном случае от θ.
      Поэтому функция правдоподобия – не распределение вероятностей.
  • +3
    Тачикома для привлечения внимания? o_O
    • +1
      Кстати, возвращаясь к недавнему обсуждению Stand Alone Complex, хочу отметить, что второй сезон, который я досмотрел на днях, получился лучше первого. Если качество сюжетной части можно обсуждать, то построение эпизодов, чередование филлеров и сюжетных серий сделано на порядок лучше, что делает сериал ещё более захватывающим.

      Solid State Society тоже крутой.

      Так что рекомендую.
      • +1
        Спасибо, обратил внимание ещё на вашу прошлую переписку насчёт Stand Alone Complex, и теперь окончательно уверился в том, что стоит посмотреть второй сезон.
    • +2
      Мы назвали нашу рекомендательную систему Тачикома, в честь понятно какого персонажа.
      • +4
        в офисе есть статуэтка Тачикомы, ей делаются подарки и жертвоприношения. А вот и автор статьи вместе с Тачикомой clip2net.com/clip/m7004/1365791351-clip-167kb.png
        • +5
          Экое язычество.
  • +1
    Не очень понятно, зачем Вы рисуете направленные стрелки. В теории вероятностей нет понятия о причине и следствии. Есть понятие независимости и условной вероятности. Нарисовав направленную стрелку вы приумножили сущности без надобности: все три приведенных связи описывают одни и те же взаимосвязи, только циклически переставляются имена переменных.

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

    PS Рад что математика у Вас используется во благо технике
    • +1
      Причин и следствий нет, а понятие зависимости одной переменной от другой есть.
      И направление стрелок/зависимостей произвольно менять нельзя — случаи «x и y сходятся в z» и «x и y исходят из z» отличаются своими свойствами, как видно из текста.
      • 0
        Рассмотрим первую «последовательную картинку». Как вы не меняйте в ней стрелки, всё равно будут верны тождества:
        image
        p(x,z) = p(x)p(z)

        Если математическая модель неизменна, то в чем разница? По мне, так только в интерпретации.
        • +1
          • x и y исходят из z: x и y зависимы, если z неизвестна. Если z известна — становятся независимы
          • x и y сходятся в z: x и y независимы, если z неизвестна. Если z известна — становятся зависимы


          Советую посмотреть курс Probabilistic Graphical Models Дафны Коллер на coursera.org, у Вас не останется сомнений, что направленность стрелок очень важна для сетей Байеса. Есть, безусловно, и ненаправленные графические модели, но данная статья ведет речь именно о байесовских статьях сетях.

          edit: исправил последнее слово
          • 0
            Вплоть до лекции «2 — 3: Flow of Probabilistic Influence» достаточно, думаю, если и правда надумаете.
          • 0
            Спасибо за ссылку, постараюсь разобраться.

            Я правильно интерпретировал Ваш тезис?
            • 0
              Мне кажется, Ваша запись верна, но давайте призовем Сергея.

              edit: в смысле, Ваша запись соответствует тому, что я написал выше.
            • 0
              Справа — неправильно, там как раз p(z|x,y) появляется.
          • 0
            Крутой курс, пока один из самых крутых на курсере. Хех сколько незабываемых ночей проведено за домашками…
      • 0
        Судя по приведенной Вами ниже ссылке, стрелки, вероятно, относятся к:
        «Байесовская сеть, в которой дуги помимо отношений условной независимости кодируют также отношения причинности, называют причинно-следственными Байесовыми сетями (Causal Bayesian networks[1]).»

        Таким образом, стрелки лишь показывают «причинно-следственные связи». И нужны лишь для простоты составления цепи, вряд ли такая абстрактная вещь как причинно-следственная связь может влиять на теор.вер. ИМХО
    • +1
      Кроме того, если посмотреть прямо определение Байесовской сети, то это направленный граф.
      • 0
        ага верно, а марковская сеть это не орграф, но со всеми вытекающими свойствами active triplets
      • 0
        Посмотрите «Пример» в приведенной ссылке. Как там используется направление стрелок? Что поменяется, если направление стрелок поменять? Или заменить стрелки на простые линии?
    • 0
      Вообще-то я ровно об этом и пишу. :)
      В примерах ниже я несколько погрешу против истины и буду интуитивно интерпретировать ребро, стрелочку между двумя переменными, как «x влияет на y», т.е. по сути как причинно-следственную связь. На самом деле это, конечно, не совсем так – например, часто можно развернуть ребро, не потеряв смысла (вспомните: в графе из двух переменных было всё равно, в какую сторону проводить ребро). Да и вообще это непростой философский вопрос – что такое «причинно-следственные связи» и зачем они нужны. Но для рассуждений на пальцах сойдёт.
  • 0
    И вопрос с подвохом :) А почему именно image?
    • 0
      Это был ко мне вопрос? Тогда лучше его пояснить, я его не понял.

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

      (где y – то, что мы предсказываем, например значение функции, для которой мы строим регрессию, в новой точке, или значение класса для нового объекта в классификаторе). Но часто это посчитать слишком сложно или не нужно; например, часто ожидание предсказательного распределения совпадает со значением в точке максимума θ, а при пересчёте по-байесовски меняется только форма предсказательного распределения, т.е. наша «уверенность» в ответе.

      Для этой статьи это было бы уже чересчур; я к этому вернусь позже, когда буду (если до этого вообще дойдёт :) ) говорить о методах, которые сразу считают именно интеграл (например, MCMC сэмплирование часто это делает), а не максимизируют правдоподобие в явном виде сначала.
      • +1
        Сформулирую иначе: в своих задачах Вы используете простую функцию потерь при минимизации среднего риска (aka максимум АПВ), а нельзя ли получить какой-то новый профит, воспользовавшись другой ф.п. Скажем, квадратичной (что даст image).

        Я почитал ваши статьи и материал по ссылкам. Стало понятно, что Вы в основном занимаетесь классификацией, и у Вас набор категорий вместо случайных величин. Тут максимум АПВ логичен. Но если придется рекомендовать что-то количественное, и получится вот такая АПВ:

        то с аргументом максимума выйдет промах.
        • 0
          С тем, о чём я сказал в комментарии (интегралом по posterior) – не выйдет. Для этого он и нужен, да.
          Спасибо за дельный комментарий!
  • 0
    Интересно было бы почитать также и про скрытые марковские сети.

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

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