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

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

В этом посте я дам краткое описание двух разновидностей PGM, направленных графических моделей (DGM), также известных как байесовские сети (BN) и неориентированные графические модели (UGM) или Марковские случайные поля (MRF). Я объясню различия между этими моделями и приведу примеры для обеих. В последней части поста я рассмотрю преобразование BN в MRF и обратно. Я также кратко коснусь вывода и оценки параметров в PGM. Я предоставлю ссылки на дополнительную информацию по темам, где это возможно.

Направленные графические модели (DGM)

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

Направление краев определяет влияние одной случайной величины на другую. Если граф не содержит циклов (количество вершин, соединенных в замкнутую цепочку), его обычно называют направленным ациклическим графом (DAG). Логический вывод на этих графиках может быть выполнен точно с использованием таких алгоритмов, как Распространение убеждений (BP) или исключение переменных.

Байесовские сети (BN)

Примером DGM является байесовская сеть (BN). Байесовская сеть - это DAG с вершинами (случайными величинами), представляющими наблюдаемые или скрытые переменные модели.

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

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

Этот DAG представляет (факторизованное) распределение вероятностей

, где R - случайная величина для дождя, S для дождевателя и G для влажной травы. Изучив график, вы быстро увидите, что единственной независимой переменной в модели является R. Две другие переменные зависят от вероятности дождя и / или дождя. В общем, совместное распределение для BN - это произведение условных вероятностей для каждого узла с учетом его родителей:

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

Хотя это не обязательно, BN часто используются для моделирования причинно-следственных связей. Если направление ребер в BN представляет собой причинно-следственную связь, каузальный do-исчисление, введенное Judea Pearl, позволяет модифицировать график, выполняя моделируемое вмешательство и прогнозируя влияние внешнего вмешательства (см. Этот замечательный пост, если вам нравится знать больше).

Вывод в BN

Вернемся к примеру с мокрой травой и выясним вероятность того, что трава мокрая, то есть предельная вероятность p (G). Эта задача известна как вывод. Чтобы определить предельную вероятность переменной, вы должны в целом просуммировать по всем ее родительским элементам на графике. В этом случае предельная вероятность будет

В этом случае нам нужно просуммировать все факторы. Однако для более сложных графиков можно извлечь некоторые факторы из суммы и значительно упростить вычисления, используя структуру разреженного графа.

Еще одна задача, которая может нас заинтересовать, - это вычисление условной вероятности того, что трава будет влажной, если не будет дождя. В этом случае мы поступим следующим образом:

В этом случае нам нужно только маргинализировать более S, поскольку R уже считается заданным. Эта процедура называется исключение переменных. Исключение переменных - это точный алгоритм вывода. Его также можно использовать для определения состояния сети, имеющего максимальную вероятность, путем простого обмена суммами максимальными функциями. Его обратная сторона заключается в том, что для больших BN это может быть сложно с вычислительной точки зрения. В этих случаях можно использовать приближенные алгоритмы вывода, такие как выборка Гиббса или выборка отклонения.

Выяснение независимости в BN

Как мы можем определить, являются ли два узла в BN независимыми для другого узла? Чтобы ответить на этот вопрос, введем понятие d-разделения.

Есть 3 правила d-разделения:

  • Два набора узлов X и Y разделены d, если между ними нет однонаправленного пути (любой последовательности ребер независимо от их направленности).

В этом примере узлы a и c соединены d, тогда как a и d или b и d разделены d, так как b и d являются родителями c.

  • X и Y разделены d для другого набора узлов Z, если Z «блокирует» любой однонаправленный путь между их.

В этом случае b блокирует путь между a и c, в результате чего они разделяются d.

  • Если коллайдер или его потомки находятся в наборе Z, он нарушает d-разделение своих родителей.

Это требует некоторого объяснения: коллайдер - это узел, у которого есть два или более родителей. Если коллайдер наблюдается, его родители, хотя прежде независимые, становятся зависимыми. Например, если мы имеем дело с двоичными переменными, знание коллайдера делает вероятность его родителей более или менее вероятной. На изображении выше b прерывает разделение d между a и c.

Ненаправленные графические модели (UGM) или марковские случайные поля (MRF)

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

В то время как ребра байесовских сетей представляют собой условные зависимости, неориентированные ребра MRFs представляют совместные вероятности клик в графе. Взгляните на следующий MRF:

Этот график описывает совместную функцию вероятности 6 переменных в 3 различных кликах. Таким образом, он разлагается на следующий продукт распределений:

Фундаментальным свойством MRF является то, что они удовлетворяют попарным, локальным и глобальным марковским свойствам. Эти свойства имеют глубокую связь с правилами d-разделения для BN. В частности, d-разделение определяет марковские свойства ориентированных графов.

Парное марковское свойство утверждает, что две несоседние переменные условно независимы при всех остальных переменных:

, где X_a и X_b определяют любые две несоседние переменные, а X_ G - набор всех переменных.

Локальное марковское свойство вводит понятие окрестности переменной:

, где N (a) - окрестность X_a. Другими словами, любая переменная условно не зависит от любых других переменных, учитывая ее окрестность.

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

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

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

, где Z - подходящая константа нормализации (также называемая статистической суммой), c - (максимальные) клики графа, ϕ - факторизованная функция на клике (не обязательно нормализованная), а X - это набор случайных величин.

Примеры MRF

Очень распространенным примером MRF является Скрытая марковская модель (HMM): HMM описывает динамическую систему с периодическими наблюдениями. Система меняет скрытые состояния на каждом временном шаге. Таким образом, состояние в момент времени i зависит только от состояния в момент времени i-1, то есть HMM моделируют марковские процессы. Кроме того, наблюдение в момент времени i напрямую зависит только от состояния в момент времени i.

Совместное распределение вероятностей, моделируемое HMM, выглядит следующим образом:

, где S и O - случайные величины состояния и наблюдения соответственно, а T - количество временных шагов. Вывод на основе HMM особенно прост: поскольку граф имеет структуру, подобную цепочке, можно выполнить вывод, используя алгоритмы динамического программирования. Например, вычисление вероятности нахождения системы в состоянии s в момент i с учетом всех наблюдений o_ [0: T] может быть вычислено с использованием алгоритма вперед-назад. Аналогичным образом наиболее вероятная последовательность скрытых состояний при данных наблюдениях вычисляется с помощью алгоритма Витерби.

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

Модель Изинга предполагает, что каждый узел может принимать два состояния: σ ϵ {-1, 1}. Энергия конкретного состояния описывается:

, где σ_i представляет состояние узла i, первая сумма идет по всем соседям в решетке, J_ij - это взаимодействие между узлами i и j и h_i - коэффициент энергий отдельных узлов (априорная вероятность). J_ij может быть положительным, побуждая соседние узлы иметь одинаковый знак, или отрицательным, заставляя их иметь противоположные знаки. Совместное распределение Гиббса системы определяется выражением:

Логарифмируя это выражение, оно разлагается на клики графа. Таким образом, мы можем видеть, что модель действительно является MRF согласно теореме Хаммерсли-Клиффорда. К сожалению, коэффициент нормализации в знаменателе обычно трудно вычислить, поэтому приблизительный вывод является методом выбора для задач, связанных с моделью Изинга.

Эквивалентность BN и MRF

Как связаны байесовские сети и марковские случайные поля? Разве мы не могли бы просто использовать одно или другое для представления распределения вероятностей? Как мы можем установить эквивалентность? Можно попытаться преобразовать BN в MRF, просто отбросив направления стрелок. Однако это было бы неправильно, поскольку отношения независимости, кодируемые DGM и UGM, не совпадают. Рассмотрим, например, следующую байесовскую сеть и MRF, полученный удалением стрелок:

Как видно на рисунке выше, графики в A и B не кодируют одно и то же отношение условной независимости: учитывая узел b, узлы a и c не являются независимыми согласно третьему правилу d-разделения. Однако MRF в (B) не содержит этого отношения зависимости, поскольку нет линии между a и c. Мы можем исправить это с помощью процедуры, называемой морализацией. Это правильно названо: даже если узлы a и c имеют общего потомка, они не связаны соединением. Объединяя a и c, мы компенсируем это несоответствие. Однако мы также теряем часть независимости, а именно между a и c, если b не дано. Таким образом, график становится более общим, а вывод потенциально более сложным.

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

Заключение

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