img_bg

Краткое введение в графические модели и байесовские сети

 Оригинальная статья Университет Британской Колумбии.              автор: адъюнкт-профессор Кевин Мерфи,   

Краткое введение в графические модели и байесовские сети

 Оригинальная статья

Университет Британской Колумбии.             

автор: адъюнкт-профессор Кевин Мерфи,                                                                                                           

 

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

Многие из классических многомерных вероятностных систем, изучаемых в таких областях, как статистика, системотехника, теория информации, распознавание образов и статистическая механика, являются частными случаями общего формализма графической модели – примеры включают в себя смешанные модели, факторный анализ, скрытые марковские модели, фильтры Калмана и Изинг моделей. Структура графической модели предоставляет способ рассматривать все эти системы как примеры общего базового формализма. Эта точка зрения имеет много преимуществ – в частности, специализированные методы, которые были разработаны в одной области, могут передаваться между исследовательскими сообществами и использоваться более широко. Более того, формализм графической модели обеспечивает естественную основу для проектирования новых систем. “— Майкл Джордан, 1998.

В этом руководстве

Мы кратко обсудим следующие темы.

  • Представление или что такое графическая модель?
  • Вывод или, как мы можем использовать эти модели для эффективного ответа на вероятностные запросы?
  • Обучение или, что нам делать, если мы не знаем, что это за модель?
  • Теория принятия решений , или, что происходит, когда пришло время превращать убеждения в действия?
  • Приложения или для чего все это хорошо?

Примечание: (версия) эта страница доступна в формате PDF здесь . Также Мария Стефанова сделала здесь шведский перевод.

Статьи в популярной прессе

Следующие статьи дают меньше технических введений.

  • LA Times статья (28.10.96) о байесовских сетях.
  • Статья Economist (22.03.01) о применении Microsoft BNs.

Другие источники технической информации

Представление

Вероятностные графические модели – это графики, в которых узлы представляют случайные величины, а (отсутствие) дуг представляют условные предположения о независимости. Следовательно, они обеспечивают компактное представление совместных распределений вероятностей. Ненаправленные графические модели, также называемые марковскими случайными полями (MRF) или сетями Маркова, имеют простое определение независимости: два (набора) узлов A и B условно независимы с учетом третьего набора C, если все пути между узлами в A и B разделены узлом в C. В отличие от этого, ориентированные графические модели, также называемые байесовскими сетями или сетями убеждений (BN), имеют более сложное понятие независимости, которое учитывает направленность дуг, как мы объясним ниже.

Ненаправленные графические модели более популярны в сообществах физики и зрения, а направленные модели более популярны в сообществах искусственного интеллекта и статистики. (Можно иметь модель как с направленными, так и с ненаправленными дугами, которая называется цепным графом.) Тщательное изучение взаимосвязи между направленными и ненаправленными графическими моделями см. В книгах Pearl88, Whittaker90 и Lauritzen96.

Хотя направленные модели имеют более сложное понятие независимости, чем неориентированные модели, у них есть несколько преимуществ. Наиболее важным является то, что можно рассматривать дугу от A до B как указание на то, что A «вызывает» B. (См. Обсуждение причинно-следственной связи .) Это можно использовать в качестве руководства для построения структуры графа. Кроме того, направленные модели могут кодировать детерминированные отношения, и их легче изучать (в соответствии с данными). В оставшейся части этого урока мы будем обсуждать только направленные графические модели, то есть байесовские сети.

Помимо структуры графика, необходимо указать параметры модели. Для направленной модели мы должны указать условное распределение вероятностей (CPD) в каждом узле. Если переменные являются дискретными, это можно представить в виде таблицы (CPT), в которой указана вероятность того, что дочерний узел принимает каждое из своих различных значений для каждой комбинации значений своих родителей. Рассмотрим следующий пример, в котором все узлы являются двоичными, т. Е. Имеют два возможных значения, которые мы будем обозначать T (true) и F (false).

Мы видим, что событие «трава мокрая» (W = true) имеет две возможные причины: либо разбрызгиватель воды включен (S = true), либо идет дождь (R = true). Сила этого отношения показана в таблице. Например, мы видим, что Pr (W = true | S = true, R = false) = 0,9 (вторая строка), и, следовательно, Pr (W = false | S = true, R = false) = 1 – 0,9 = 0,1 , поскольку каждая строка должна составлять по одному. Поскольку узел C не имеет родителей, его CPT определяет априорную вероятность того, что он облачный (в данном случае 0,5). (Думайте о C как о представлении времени года: если это облачный сезон, менее вероятно, что разбрызгиватель включен, и более вероятно, что идет дождь.)

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

По цепочечному правилу вероятности общая вероятность всех узлов на приведенном выше графике равна

 P (C, S, R, W) = P (C) * P (S | C) * P (R | C, S) * P (W | C, S, R)

Используя условные отношения независимости, мы можем переписать это как

 P (C, S, R, W) = P (C) * P (S | C) * P (R | C) * P (W | S, R)

где нам было позволено упростить третий член, потому что R не зависит от S, учитывая его родительский C, и последний член, потому что W не зависит от C, учитывая его родительские S и R.

Мы видим, что условные отношения независимости позволяют нам представлять сустав более компактно. Здесь экономия минимальна, но в целом, если бы у нас было n двоичных узлов, для полного соединения потребовалось бы пространство O (2 ^ n) для представления, а для факторизованной формы потребовалось бы пространство O (n 2 ^ k) для представления, где k – максимальное разветвление узла. А меньшее количество параметров облегчает обучение.

Являются ли “Байесовские сети” Байесовскими?

Несмотря на название, байесовские сети не обязательно подразумевают приверженность байесовской статистике. Действительно, для оценки параметров CPD часто используются методы частых пользователей. Скорее, они так называются, потому что они используют правило Байеса для вероятностного вывода, как мы объясним ниже. (Термин «ориентированная графическая модель», возможно, более уместен.) Тем не менее, байесовские сети являются полезным представлением для иерархических байесовских моделей, которые составляют основу прикладной байесовской статистики (см., Например, проект BUGS ). В такой модели параметры обрабатываются как любая другая случайная величина и становятся узлами на графике.

вывод

Наиболее распространенная задача, которую мы хотим решить с помощью байесовских сетей, – это вероятностный вывод. Например, рассмотрим сеть разбрызгивателей воды и предположим, что мы наблюдаем тот факт, что трава влажная. Для этого есть две возможные причины: либо идет дождь, либо разбрызгиватель включен. Что более вероятно? Мы можем использовать правило Байеса для вычисления апостериорной вероятности каждого объяснения (где 0 == false и 1 == true).


где


является нормализующей константой, равной вероятности (вероятности) данных. Итак, мы видим, что более вероятно, что трава влажная, потому что идет дождь: отношение правдоподобия составляет 0,7079 / 0,4298 = 1,674.

Объясняя прочь

В приведенном выше примере обратите внимание, что эти две причины «конкурируют» за «объяснение» наблюдаемых данных. Следовательно, S и R становятся условно зависимыми, учитывая, что их общий ребенок, W, наблюдается, даже если они незначительно независимы. Например, предположим, что трава влажная, но мы также знаем, что идет дождь. Тогда задняя вероятность того, что спринклер включен, снижается:

 Pr (S = 1 | W = 1, R = 1) = 0,1945

Это называется «объяснять прочь». В статистике это известно как парадокс Берксона или «предвзятость выбора». В качестве яркого примера этого эффекта рассмотрим колледж, в который принимаются студенты с умным или спортивным характером (или оба!). Пусть C обозначает событие, когда кто-то поступает в колледж, что становится правдой, если он либо умный (B), либо спортивный (S). Предположим, что в общей популяции B и S независимы. Мы можем смоделировать наши предположения об условной независимости, используя график, который представляет собой структуру V со стрелками, указывающими вниз:

    BS
     \ /
      v
      С

Теперь посмотрим на популяцию студентов колледжа (те, для которых соблюдается С, соответствуют действительности). Будет обнаружено, что умственные способности делают вас менее склонными к спорту, и наоборот, потому что одного свойства достаточно для объяснения свидетельства о С (т. Е. P (S = 1 | C = 1, B = 1) <= P (S = 1 | C = 1)). (Если вы мне не верите, попробуйте эту маленькую демоверсию BNT !)

Нисходящее и восходящее рассуждение

В примере с разбрызгивателем воды у нас были доказательства воздействия (влажная трава), и мы выделили наиболее вероятную причину. Это называется диагностическим, или «восходящим», рассуждением, поскольку оно идет от следствий к причинам; это общая задача в экспертных системах. Байесовские сети также можно использовать для причинно-следственных или «нисходящих» рассуждений. Например, мы можем вычислить вероятность того, что трава будет мокрой, если она облачная. Следовательно, байесовские сети часто называют «порождающими» моделями, потому что они определяют, как причины создают эффекты.

причинность

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

Условная независимость в Байес Нетс

В общем, отношения условной независимости, закодированные байесовской сетью, лучше всего объяснить с помощью алгоритма «байесовского шара» (из-за Росса Шахтера), который состоит в следующем: два (набора) узлов A и B условно независимы ( с разделением d) задан набор C в том и только в том случае, если у шарика нет возможности добраться от А до В на графике, где допустимые движения мяча показаны ниже. Скрытые узлы – это узлы, значения которых неизвестны и отображаются как не затененные; наблюдаемые узлы (те, на которые мы воздействуем) затенены. Пунктирные дуги указывают направление потока мяча.

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

Теперь рассмотрим второй столбец, в котором у нас есть две расходящиеся стрелки от X (поэтому X является «корнем»). Если X скрыто, дети зависимы, потому что у них есть скрытая общая причина, поэтому мяч проходит. Если наблюдается X, его дочерние элементы становятся условно независимыми, поэтому мяч не проходит. Наконец, рассмотрим случай, когда у нас есть одна входящая и исходящая стрелка к X. Интуитивно понятно, что узлы вверх и вниз от X являются зависимыми, если X скрыт, потому что кондиционирование на узле нарушает график в этой точке.

Байесовские сети с дискретными и непрерывными узлами

Во вводном примере использовались узлы с категориальными значениями и многочленными распределениями. Также возможно создание байесовских сетей с непрерывно значащими узлами. Наиболее распространенным распределением для таких переменных является гауссов. Для дискретных узлов с непрерывными родителями мы можем использовать распределение логистики / softmax. Используя многочлены, условные гауссианы и распределение softmax, мы можем иметь богатый набор инструментов для создания сложных моделей. Некоторые примеры приведены ниже. Для получения подробной информации, нажмите здесь . (Кружками обозначены непрерывные случайные величины, квадратами обозначены дискретные rv, скрытые средние значения скрыты и наблюдаемые затененные значения.)

Для более подробной информации, смотрите эту отличную статью.

Временные модели

Динамические байесовские сети (ДБС) являются ориентированными графическими моделями случайных процессов. Они обобщают скрытые модели Маркова (HMM) и линейные динамические системы (LDS) , представляя скрытое (и наблюдаемое) состояние через переменные состояния, которые могут иметь сложные взаимозависимости. Графическая структура обеспечивает простой способ указать эти условные зависимости и, следовательно, обеспечить компактную параметризацию модели.

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

Скрытые марковские модели (HMM)

Самым простым видом DBN является скрытая марковская модель (HMM), которая имеет один дискретный скрытый узел и один дискретный или непрерывный наблюдаемый узел на срез. Мы проиллюстрируем это ниже. Как и прежде, кружки обозначают сплошные узлы, квадраты обозначают дискретные узлы, прозрачные – скрытые, наблюдаемые затененные -.

Мы «развернули» модель для 4 «временных интервалов» – предполагается, что структура и параметры будут повторяться при дальнейшем развертывании модели. Следовательно, чтобы указать DBN, нам нужно определить топологию внутри слайса (внутри слайса), топологию между слайсами (между двумя слайсами), а также параметры для первых двух слайсов. (Такая двухсекционная временная байесовская сеть часто называется 2TBN.)

Некоторые распространенные варианты HMM показаны ниже.

Линейные динамические системы (LDS) и фильтры Калмана

Линейная динамическая система (LDS) имеет ту же топологию, что и HMM, но предполагается, что все узлы имеют линейно-гауссово распределения, т.е.

    x (t + 1) = A * x (t) + w (t), w ~ N (0, Q), x (0) ~ N (init_x, init_V)
    y (t) = C * x (t) + v (t), v ~ N (0, R)

Фильтр Калмана – это способ сделать онлайн-фильтрацию в этой модели. Некоторые простые варианты LDS показаны ниже.

Фильтр Калмана был предложен в качестве модели того, как мозг интегрирует визуальные сигналы во времени, чтобы вывести состояние мира, хотя реальность, очевидно, намного сложнее. Главное не в том, что фильтр Калмана является правильной моделью, а в том, что мозг объединяет сигналы снизу вверх и сверху вниз. Рисунок ниже взят из статьи под названием «Модель фильтра Калмана зрительной коры», написанной П. Рао, «Нейронные вычисления 9 (4): 721-763, 1997».

Более сложные DBN

Также возможно создать временные модели с гораздо более сложными топологиями, такими как сеть Байесовского автоматизированного такси (BAT), показанная ниже. (Для простоты мы показываем только наблюдаемые листья для среза 2. Спасибо Дафни Коллер за предоставленную эту цифру.)

Когда некоторые из наблюдаемых узлов рассматриваются как входы (действия), а некоторые как выходы (восприятия), DBN становится POMDP . Смотрите также раздел о теории решений ниже.

Генеративная модель для генеративных моделей

Приведенный ниже рисунок, составленный Зубином Гахрамани и Сэмом Роуисом, является хорошим обобщением взаимосвязей между некоторыми популярными графическими моделями.

ВЫВОД

Графическая модель определяет полное совместное распределение вероятностей (JPD) по всем переменным. Учитывая JPD, мы можем ответить на все возможные запросы вывода путем маргинализации (суммирования по нерелевантным переменным), как показано во введении. Однако JPD имеет размер O (2 ^ n), где n – количество узлов, и мы предположили, что каждый узел может иметь 2 состояния. Следовательно, суммирование по JPD занимает экспоненциальное время. Теперь мы обсудим более эффективные методы.

Переменное исключение

Для ориентированной графической модели (сети Байеса) мы иногда можем использовать факторизованное представление JPD для эффективной маргинализации. Ключевая идея состоит в том, чтобы «вводить суммы» в максимально возможной степени при суммировании (маргинализации) не относящихся к делу терминов, например, для сети разбрызгивания воды

Обратите внимание, что, выполняя самые внутренние суммы, мы создаем новые термины, которые необходимо суммировать по очереди, например:

где

Продолжая в том же духе,

где

Этот алгоритм называется устранением переменных. Принцип распределения сумм по продуктам может быть обобщен для применения к любому коммутативному полукольцу. Это составляет основу многих распространенных алгоритмов, таких как декодирование Витерби и быстрое преобразование Фурье. Подробнее см.

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

Динамическое программирование

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

  • “Вероятностные рассуждения в интеллектуальных системах”, Иудея Перл, 1988, 2-е изд.
  • «Слияние и распространение с множественными наблюдениями в сетях убеждений», Peot и Shachter, AI 48 (1991) с. 299-318.

Если BN имеет ненаправленные циклы (как в примере с разбрызгивателем воды), локальные алгоритмы передачи сообщений подвергаются риску двойного счета. например, информация от S и R, поступающая в W, не является независимой, потому что она пришла от общей причины C. Следовательно, наиболее распространенный подход заключается в преобразовании BN в дерево путем кластеризации узлов вместе, чтобы сформировать то, что называется соединительное дерево, а затем запустить локальный алгоритм передачи сообщений на этом дереве. Схема передачи сообщений может быть алгоритмом Перла, но чаще используется вариант, разработанный для ненаправленных моделей. Для более подробной информации, нажмите здесь

Время выполнения алгоритмов DP экспоненциально по размеру самого большого кластера (эти кластеры соответствуют промежуточным членам, созданным при исключении переменных). Этот размер называется индуцированной шириной графа. Минимизация этого NP-трудна.

Аппроксимационные алгоритмы

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

  • Вариационные методы. Простейшим примером является приближение среднего поля, в котором используется закон больших чисел для аппроксимации больших сумм случайных величин их средствами. В частности, мы по существу отделяем все узлы и вводим новый параметр, называемый вариационным параметром, для каждого узла и итеративно обновляем эти параметры, чтобы минимизировать кросс-энтропию (расстояние KL) между приближенным и истинным распределением вероятности. Обновление вариационных параметров становится прокси для вывода. Приближение среднего поля дает нижнюю границу вероятности. Возможны более сложные методы, которые дают более жесткие нижние (и верхние) границы.
  • Методы отбора проб (Монте-Карло). Простейшим видом является выборка по важности, где мы выбираем случайные выборки x из P (X), (безусловное) распределение по скрытым переменным, а затем взвешиваем выборки по их вероятности, P (y | x), где y – свидетельство , Более эффективный подход в больших измерениях называется цепочкой Монте-Карло Маркова (MCMC) и включает в качестве особых случаев выборку Гиббса и алгоритм Метрополиса-Хастинга.
  • “Loopy убеждение в распространении”. Это влечет за собой применение алгоритма Перла к исходному графу, даже если он имеет циклы (ненаправленные циклы). Теоретически, существует риск двойного счета, но Яир Вайс и другие доказали, что в определенных случаях (например, один цикл) события дважды учитываются «одинаково» и, следовательно, «отменяются», чтобы дать правильный ответ. Распространение убеждений эквивалентно точному выводу модифицированного графа, называемого универсальным покрытием или развернутым / вычислительным деревом, которое имеет ту же локальную топологию, что и исходный граф. Это то же самое, что подходы Бете и резонатора / TAP в статистической физике. Следовательно, существует глубокая связь между распространением убеждений и вариационными методами, которые люди в настоящее время исследуют.
  • Ограниченный срез кондиционирования. Создавая экземпляры подмножеств переменных, мы можем разрывать циклы в графе. К сожалению, когда срез большой, это очень медленно. Инстанцируя только подмножество значений сечения, мы можем вычислить нижние оценки вероятностей, представляющих интерес. В качестве альтернативы, мы можем отобрать срезы совместно, метод, известный как блочная выборка Гиббса.
  • Методы параметрической аппроксимации. Они выражают промежуточные слагаемые в более простой форме, например, аппроксимируя их как произведение меньших факторов. «Минибукеты» и алгоритм Бойена-Коллера попадают в эту категорию.

Приблизительный вывод – огромная тема: см. Ссылки для более подробной информации.

Вывод в DBN

Общая проблема вывода для DBN состоит в том, чтобы вычислить P (X (i, t0) | y (:, t1: t2)), где X (i, t) представляет i-ю скрытую переменную в момент времени, а t Y (:, t1: t2) представляет все доказательства между моментами времени t1 и t2. (На самом деле, мы также часто хотим вычислить совместные распределения переменных по одному или нескольким временным слайсам.) Есть несколько особых случаев, представляющих интерес, проиллюстрированных ниже. Стрелка указывает на t0: именно X (t0) мы пытаемся оценить. Заштрихованная область обозначает t1: t2, доступные данные.

Вот простой пример вывода в LDS. Рассмотрим частицу, движущуюся в плоскости с постоянной скоростью, подверженной случайным возмущениям на ее траектории. Новая позиция (x1, x2) – это старая позиция плюс скорость (dx1, dx2) плюс шум w.

 [x1 (t)] = [1 0 1 0] [x1 (t-1)] + [wx1]
 [x2 (t)] [0 1 0 1] [x2 (t-1)] [wx2]
 [dx1 (t)] [0 0 1 0] [dx1 (t-1)] [wdx1]
 [dx2 (t)] [0 0 0 1] [dx2 (t-1)] [wdx2]

Мы предполагаем, что мы только наблюдаем положение частицы.

 [y1 (t)] = [1 0 0 0] [x1 (t)] + [vx1]
 [y2 (t)] [0 1 0 0] [x2 (t)] [vx2]
                        [дх1 (т)] 
                        [дх2 (т)]

Предположим, мы начинаем с позиции (10,10), двигаясь вправо со скоростью (1,0). Мы выбрали случайную траекторию длиной 15. Ниже мы показываем отфильтрованные и сглаженные траектории.

Среднеквадратичная ошибка отфильтрованной оценки составляет 4,9; для сглаженной оценки – 3,2. Не только сглаженная оценка лучше, но мы знаем, что она лучше, что иллюстрируется меньшими эллипсами неопределенности; это может помочь, например, в проблемах ассоциации данных. Обратите внимание, что сглаженные эллипсы больше на концах, потому что эти точки видели меньше данных. Также обратите внимание, как быстро отфильтрованные эллипсы достигают своих устойчивых значений (Рикатти). (См. Мой инструментарий фильтра Kalman для более подробной информации.)

ОБУЧЕНИЕ

Для описания BN необходимо указать две вещи: топологию (структуру) графа и параметры каждого CPD. Это можно узнать из данных. Однако структура обучения гораздо сложнее, чем параметры обучения. Кроме того, узнать, когда некоторые узлы скрыты или у нас отсутствуют данные, гораздо сложнее, чем когда все наблюдается. Это приводит к 4 случаям:

 Метод наблюдаемости структуры
 ---------------------------------------------
 Известна полная оценка максимального правдоподобия
 Известный Частичный ЭМ (или градиентное восхождение)
 Неизвестный полный поиск в пространстве модели 
 Неизвестный Частичный EM + поиск в пространстве модели 

Известная структура, полная наблюдаемость

Мы предполагаем, что цель обучения в этом случае состоит в том, чтобы найти значения параметров каждого CPD, что максимизирует вероятность данных обучения, которые содержат N случаев (предполагается, что они независимы). Нормализованная логарифмическая вероятность учебного набора D сумма терминов, по одному для каждого узла:

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

Рассмотрим оценку таблицы условной вероятности для W-узла. Если у нас есть набор тренировочных данных, мы можем просто посчитать, сколько раз трава намокла, когда идет дождь, а спринлер включен, N (W = 1, S = 1, R = 1), количество раз трава влажная, когда идет дождь, а разбрызгиватель выключен, N (W = 1, S = 0, R = 1) и т. д. Учитывая эти подсчеты (которые являются достаточной статистикой), мы можем найти оценку максимального правдоподобия КПП следующим образом:

где знаменатель равен N (S = s, R = r) = N (W = 0, S = s, R = r) + N (W = 1, S = s, R = r). Таким образом, «обучение» равнозначно подсчету (в случае многочленных распределений). Для узлов Гаусса мы можем вычислить среднее значение и дисперсию выборки и использовать линейную регрессию для оценки матрицы весов. Для других видов дистрибутивов необходимы более сложные процедуры.

Как хорошо известно из литературы HMM, ML-оценки CPT подвержены редким проблемам с данными, которые могут быть решены с использованием (смесей) априорных значений Дирихле (псевдосчетов). Это приводит к оценке максимального A Posteriori (MAP). Для гауссиан, мы можем использовать предыдущий Wishart и т. Д.

Известная структура, частичная наблюдаемость

Когда некоторые узлы скрыты, мы можем использовать алгоритм EM (ожидание максимизации), чтобы найти (локально) оптимальную оценку максимального правдоподобия параметров. Основная идея EM заключается в том, что, если бы мы знали значения всех узлов, обучение (шаг M) было бы простым, как мы видели выше. Таким образом, на этапе E мы вычисляем ожидаемые значения всех узлов, используя алгоритм вывода, а затем обрабатываем эти ожидаемые значения, как если бы они наблюдались (распределения). Например, в случае узла W мы заменяем наблюдаемое количество событий на количество раз, которое мы ожидаем увидеть каждое событие:

 P (W = w | S = s, R = r) = EN (W = w, S = s, R = r) / EN (S = s, R = r)

где EN (x) – ожидаемое количество раз, когда событие x происходит во всем обучающем наборе, учитывая текущее предположение параметров. Эти ожидаемые значения могут быть рассчитаны следующим образом

 EN (.) = E sum_k I (. | D (k)) = sum_k P (. | D (k))

где I (x | D (k)) – функция индикатора, которая равна 1, если событие x происходит в обучающем случае k, и 0 в противном случае.

Учитывая ожидаемые значения, мы максимизируем параметры, а затем повторно вычисляем ожидаемые значения и т. Д. Эта итерационная процедура гарантированно сходится к локальному максимуму поверхности правдоподобия. Также возможно сделать градиентное восхождение на поверхности правдоподобия (выражение градиента также включает в себя ожидаемые значения), но EM обычно быстрее (так как использует естественный градиент) и проще (так как не имеет параметра размера шага и заботится о ограничения параметров (например, «строки» CPT должны суммироваться в одну) автоматически). В любом случае, мы видим, что когда узлы скрыты, логический вывод становится подпрограммой, которая вызывается процедурой обучения; следовательно, алгоритмы быстрого вывода имеют решающее значение.

Неизвестная структура, полная наблюдаемость

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

Целевая функция, используемая для выбора модели

Модель максимального правдоподобия будет представлять собой полный график, поскольку он имеет наибольшее количество параметров и, следовательно, может наилучшим образом соответствовать данным. Принципиальный способ избежать такого переоснащения состоит в том, чтобы поставить модель на первое место, указав, что мы предпочитаем разреженные модели. Тогда, по правилу Байеса, модель MAP является той, которая максимизирует

Принимая журналы, мы находим

где c = – \ log \ Pr (D) – постоянная, не зависящая от G.

Эффект структуры до P (G) эквивалентен штрафу за слишком сложные модели. Однако это не является строго необходимым, поскольку термин предельного правдоподобия

 P (D | G) = \ int _ {\ theta} P (D | G, \ theta)

имеет аналогичный эффект штрафования моделей со слишком большим количеством параметров (это называется бритвой Оккама).

Алгоритмы поиска для поиска лучшей модели

Целью структурного обучения является изучение дага (ориентированного ациклического графа), который лучше всего объясняет данные. Это NP-сложная задача, поскольку число дагов по N переменным является суперэкспоненциальным в N. (Для этого не существует формулы для замкнутой формы, но, чтобы дать вам представление, на 4 узлах имеется 543 Дага, и O (10 ^ 18) Дагс на 10 узлов.)

Если мы знаем порядок узлов, жизнь становится намного проще, так как мы можем изучать родительский набор для каждого узла независимо (так как счет разложим), и нам не нужно беспокоиться об ограничениях ацикличности. Для каждого узла самое большее

 \ sum_ {k = 0} ^ n \ choice {n} {k} = 2 ^ n

наборы возможных родителей для каждого узла, которые могут быть расположены в решетке, как показано ниже для n = 4. Задача состоит в том, чтобы найти самую высокую оценку в этой решетке.

Есть три очевидных способа поиска в этом графике: снизу вверх, сверху вниз или посередине. При подходе снизу вверх мы начинаем с нижней части решетки и оцениваем оценку по всем точкам на каждом последующем уровне. Мы должны решить, является ли выигрыш в баллах, достигнутый большим родительским набором, «стоящим».Стандартный подход в сообществе анализа реконструктивности (RA) использует тот факт, что \ chi ^ 2 (X, Y) \ приблизительное I (X, Y) N \ ln (4), где N – количество образцов, а I (X) , Y) – это взаимная информация (MI) между X и Y. Следовательно, мы можем использовать тест \ chi ^ 2, чтобы решить, является ли увеличение показателя MI статистически значимым. (Это также дает нам некоторую меру уверенности в изучаемых нами связях.) В качестве альтернативы мы можем использовать оценку BIC.

Конечно, если мы не знаем, достигли ли мы максимально возможной оценки, мы не знаем, когда прекратить поиск, и, следовательно, мы должны оценить все точки в решетке (хотя мы, очевидно, можем использовать ветвление и ограничение). Для больших n это неосуществимо в вычислительном отношении, поэтому общий подход заключается в поиске только до уровня K (т. Е. Для определения максимального числа родителей каждого узла), что занимает O (n ^ K) времени.

Очевидный способ избежать экспоненциальной стоимости (и необходимости ограничения K) – использовать эвристику, чтобы избежать изучения всех возможных подмножеств. (На самом деле, мы должны использовать эвристику какого-то рода, поскольку проблема изучения оптимальной структуры – это NP-hard \ cite {Chickering95}.) Один из подходов в структуре RA, называемый Расширенным анализом зависимостей (EDA) \ cite {Conant88}, составляет. Начните с оценки всех подмножеств размером до двух, оставьте все со значительным (в смысле \ chi ^ 2) ИМ с целевым узлом и возьмите объединение результирующего набора в качестве набора родителей.

Недостаток этого жадного метода состоит в том, что он не сможет найти набор родителей, если у некоторого подмножества второго размера не будет значительного ИМ с целевой переменной. Однако симуляция Монте-Карло в \ cite {Conant88} показывает, что большинство случайных отношений обладают этим свойством. Кроме того, сильно взаимозависимые наборы родителей (которые могут не пройти тест парного ИМ) нарушают предположение о причинной независимости, которое необходимо для обоснования использования шумового ИЛИ и подобных CPD.

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

Неизвестная структура, частичная наблюдаемость

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

\ log \ Pr (D | G) \ приблизительный \ log \ Pr (D | G, \ hat {\ Theta} _G) - \ frac {\ log N} {2} \ #G

где N – количество выборок, \ hat {\ Theta} _G – оценка параметров ML, а #G – размерность модели. (В полностью наблюдаемом случае размерность модели – это число свободных параметров. В модели со скрытыми переменными это может быть меньше, чем это.) Первый член – это всего лишь вероятность, а второй – штраф за модель. сложность. (Балл BIC идентичен баллу минимальной длины описания (MDL).)

Хотя оценка BIC разбивается на сумму локальных терминов, по одному на узел, локальный поиск все еще стоит дорого, потому что нам нужно запускать EM на каждом шаге для вычисления \ hat {\ Theta}. Альтернативный подход состоит в том, чтобы выполнить локальные шаги поиска внутри шага M EM – это называется Structureal EM и, как доказывается, сходится к локальному максимуму оценки BIC (Friedman, 1997).

Изобретая новые скрытые узлы

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

(a) BN со скрытой переменной H. (b) Простейшая сеть, которая может захватить одно и то же распределение без использования скрытой переменной (созданной с использованием реверса дуги и исключения узла). Если H является двоичным, а другие узлы являются троичными, и мы предполагаем полные CPT, первая сеть имеет 45 независимых параметров, а вторая имеет 708.

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

\ cite {Ramachandran98} использует следующую эвристику для поиска узлов, которые нуждаются в новых родителях: они считают, что узел с помехами OR, который почти всегда включен, даже если его родители, не имеющие утечек, выключены, как индикатор отсутствия родителя. Обобщение этой техники за пределами шумных ИЛИ – интересная открытая проблема. Одним из подходов может быть изучение H (X | Pa (X)): если оно очень высокое, это означает, что текущий набор родителей не способен «объяснить» остаточную энтропию; если Pa (X) является лучшим (в смысле BIC или \ chi ^ 2) набором родителей, который мы смогли найти в текущей модели, это говорит о том, что нам нужно создать новый узел и добавить его в Pa (X) ,

Простая эвристика для изобретения скрытых узлов в случае DBN состоит в том, чтобы проверить, нарушается ли свойство Маркова для какого-либо конкретного узла. Если это так, это говорит о том, что нам нужны соединения с кусочками в прошлое. Эквивалентно, мы можем добавить новые переменные лага и подключиться к ним.

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

Дальнейшее чтение на обучение

Ниже приведены хорошие учебные статьи.

Теория принятия решений

Часто говорят, что «Теория принятия решений = Теория вероятностей + Теория полезности». Выше мы обрисовали в общих чертах, как мы можем компактно моделировать совместные распределения вероятностей, используя разреженные графы, чтобы отразить отношения условной независимости. Также возможно разделить мультиатрибутивные функции полезности аналогичным образом: мы создаем узел для каждого члена в сумме, который имеет в качестве родителей все атрибуты (случайные величины), от которых он зависит; как правило, узлы утилит будут иметь узлы действий в качестве родителей, поскольку утилита зависит как от состояния мира, так и от действия, которое мы выполняем. Результирующий график называется диаграммой влияния. В принципе, мы можем затем использовать диаграмму влияния для вычисления оптимального (последовательности) действий, которые необходимо выполнить, чтобы максимизировать ожидаемую полезность,хотя в вычислительном отношении это можно решить для всех, кроме самых маленьких проблем.

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

Приложения

Наиболее широко используемыми сетями Байеса, несомненно, являются те, которые встроены в продукты Microsoft, в том числе мастер ответов Office 95, помощник Office (бодрый скрепка) из Office 97 и более 30 специалистов по устранению неполадок технической поддержки.

Изначально BN возникли в результате попытки добавить вероятности в экспертные системы, и это по-прежнему наиболее распространенное использование для BN. Известный пример – QMR-DT, теоретическая переформулировка модели Quick Medical Reference (QMR).

Здесь верхний слой представляет скрытые узлы заболевания, а нижний слой представляет наблюдаемые узлы симптомов. Цель состоит в том, чтобы определить последующую вероятность каждого заболевания с учетом всех симптомов (которые могут присутствовать, отсутствовать или быть неизвестными). QMR-DT настолько плотно связан, что точный вывод невозможен. Были использованы различные методы аппроксимации, включая выборку, вариационное и петлевое распространение убеждений.

Еще одно интересное приложение – система Vista , разработанная Эриком Хорвицем. Система Vista – это система принятия решений, которая используется в Центре управления полетами НАСА в Хьюстоне в течение нескольких лет. Система использует байесовские сети для интерпретации телеметрии в режиме реального времени и предоставляет рекомендации по вероятности альтернативных отказов движительных систем космического челнока. Он также учитывает критичность по времени и рекомендует действия с наибольшей ожидаемой полезностью. Система Vista также использует теоретико-решающие методы для управления отображением информации для динамического определения наиболее важной информации, которую нужно выделить. Хорвиц попытался применить аналогичную технологию к продуктам Microsoft, например, к проекту Lumiere.

Особые случаи BN были независимо изобретены многими различными сообществами для использования, например, в генетике (анализ сцепления), распознавании речи (HMM), отслеживании (подборка Калмана), сжатии данных (оценка плотности) и кодировании (турбокоды) и т. Д.

Примеры других приложений см. В специальном выпуске Proc. ACM 38 (3), 1995, и страница группы теории решений Microsoft .

Приложения к биологии

Это одна из самых горячих областей. Для обзора см.

Рекомендуемое вступительное чтение

книги

В обратном хронологическом порядке.

  • Дафни Коллер и Нир Фридман, “Вероятностные графические модели: принципы и методы”, MIT Press 2009
  • Аднан Дарвиш, «Моделирование и рассуждение с помощью байесовских сетей», Кембридж 2009
  • Ф.В. Дженсен. «Байесовские сети и графики решений». Springer. 2001.
    Вероятно, лучшая вступительная книга из доступных.
  • Д. Эдвардс. «Введение в графическое моделирование», 2-е изд. Springer-Verlag. 2000.
    Хорошая обработка неориентированных графических моделей со статистической точки зрения.
  • Дж. Перл. «Причинность». Кембридж. 2000.
    Полная книга по использованию причинно-следственной моделирование.
  • RG Cowell, AP Dawid, SL Lauritzen и DJ Spiegelhalter. “Вероятностные сети и экспертные системы”. Springer-Verlag. 1999.
    Вероятно, лучшая книга доступна, хотя лечение ограничено точным выводом.
  • М.И. Джордан (ред.). «Обучение в графических моделях». MIT Press. 1998.
    Свободная коллекция работ по машинному обучению, многие из которых связаны с графическими моделями. Одна из немногих книг для обсуждения приблизительного вывода.
  • Б. Фрей. «Графические модели для машинного обучения и цифровой связи», MIT Press. 1998.
    Обсуждает распознавание образов и турбокодов с использованием (направленных) графических моделей.
  • Э. Кастильо, Дж. М. Гутьеррес и А. С. Хади. «Экспертные системы и вероятностные сетевые модели». Springer-Verlag, 1997. Испанская версия доступна в Интернете бесплатно.
  • Ф. Дженсен. «Введение в байесовские сети». UCL Press. 1996. Из печати.
    Заменено его книгой 2001 года.
  • С. Лауритцен. “Графические модели”, Оксфорд. 1996.
    Окончательное математическое изложение теории графических моделей.
  • С. Рассел и П. Норвиг. «Искусственный интеллект: современный подход». Прентис Холл.1995.
    Популярный учебник для студентов, включающий читабельную главу по ориентированным графическим моделям.
  • Дж. Уиттакер. “Графические модели в прикладной многомерной статистике”, Wiley. 1990.
    Это первая книга, опубликованная по графическому моделированию с точки зрения статистики.
  • Р. Неаполитон. «Вероятностные рассуждения в экспертных системах». Джон Вили и сыновья. 1990.
  • Дж. Перл. «Вероятностные рассуждения в интеллектуальных системах: сети правдоподобного вывода». Морган Кауфманн. 1988.
    Книга, с которой все началось! Очень проницательная книга, актуальная и сегодня.

Обзор статей

Точный вывод

Приблизительный вывод

Обучение

DBNs

Top writers

Interesting articles

Джон С. Рейд, проф Физический факультет, Университет Абердина, Шотландия Оригинальная статья   История обсерватории Кромвель-Тауэр Башня Кромвеля так называлась...
Answer from our writer Before you begin your paper you must know what reform means: reform – “make changes...
Барбара Монтгомери Досси, PhD, RN, AHN-BC, FAAN, HWNC-BC оригинальная статья       ТЕОРИЯ ИНТЕГРАЛЬНОГО УХОДА (ТИУ) Теория интегрального...
Place Your Order Now!
privacy policy