Марковское случайное поле

Пример марковского случайного поля. Каждое ребро представляет зависимость. В этом примере: A зависит от B и D. B зависит от A и D. D зависит от A, B и E. E зависит от D и C. C зависит от E.

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

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

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

Определение

Учитывая неориентированный граф $G=(V,E)$, набор случайных величин $X=(X_{v})_{v\in V}$ индексируется $V$ образуют марковское случайное поле относительно $G$ если они удовлетворяют локальным марковским свойствам:

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

$X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\smallsetminus \{u,v\}}$

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

$X_{v}\perp \!\!\!\perp X_{V\smallsetminus \operatorname {N} [v]}\mid X_{\operatorname {N} (v)}$

где ${\textstyle \operatorname {N} (v)}$ множество соседей $v$, и $\operatorname {N} [v]=v\cup \operatorname {N} (v)$ это закрытый район $v$.

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

$X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}$

где каждый путь от узла в $A$ к узлу в $B$ проходит через $S$.

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

Связь между тремя марковскими свойствами особенно ясна в следующей формулировке:

• Попарно: Для любого $i,j\in V$ не равные и не соседние, $X_{i}\perp \!\!\!\perp X_{j}|X_{V\smallsetminus \{i,j\}}$.
• Локальный: Для любого $i\in V$ и $J\subset V$ не содержащий или примыкающий к $i$, $X_{i}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (\{i\}\cup J)}$.
• Глобально: для любого $I,J\subset V$ не пересекающиеся и не соседние, $X_{I}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (I\cup J)}$.

Факторизация клики

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

Учитывая набор случайных величин $X=(X_{v})_{v\in V}$, позволять $P(X=x)$ быть вероятностью определенной конфигурации поля $x$ в $X$-то есть, $P(X=x)$ - вероятность обнаружить, что случайные величины $X$ приобретать особое значение $x$. Потому что $X$ множество, вероятность $x$ следует понимать в отношении совместного распределения $X_{v}$.

Если эту плотность соединений можно разложить по кликам $G$ как

$P(X=x)=\prod _{C\in \operatorname {cl} (G)}\varphi _{C}(x_{C})$

затем $X$ образует марковское случайное поле относительно $G$. Здесь, $\operatorname {cl} (G)$ представляет собой множество клик $G$. Определение эквивалентно, если используются только максимальные клики. Функции $\varphi _{C}$ иногда называют факторными потенциалами или кликовыми потенциалами . Обратите внимание, однако, что используется противоречивая терминология: слово потенциал часто применяется к логарифму $\varphi _{C}$. Это связано с тем, что в статистической механике $\log(\varphi _{C})$ прямую интерпретацию как потенциальную энергию конфигурации имеет  $x_{C}$.

Некоторые MRF не факторизуются: простой пример можно построить на цикле из 4 узлов с некоторыми бесконечными энергиями, то есть конфигурациями нулевых вероятностей, даже если, что более уместно, позволить бесконечным энергиям действовать на полный граф на $V$.

Факторизация MRF, если выполнено хотя бы одно из следующих условий:

• плотность положительна (по теореме Хаммерсли – Клиффорда )
• граф хордальный (по эквивалентности байесовской сети )

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

Экспоненциальное семейство

Любое положительное марковское случайное поле можно записать как семейство экспонент в канонической форме с характерными функциями. $f_{k}$ так что полное совместное распределение можно записать как

$P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right)$

где обозначение

$w_{k}^{\top }f_{k}(x_{\{k\}})=\sum _{i=1}^{N_{k}}w_{k,i}\cdot f_{k,i}(x_{\{k\}})$

— это просто скалярное произведение конфигураций полей, а Z — это функция статистического распределения :

$Z=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right).$

Здесь, ${\mathcal {X}}$ обозначает набор всех возможных присвоений значений всем случайным переменным сети. Обычно функции функции $f_{k,i}$ определяются так, что они являются индикаторами конфигурации клики, т.е. $f_{k,i}(x_{\{k\}})=1$ если $x_{\{k\}}$ соответствует i -й возможной конфигурации k -й клики и 0 в противном случае. Эта модель эквивалентна модели факторизации клики, приведенной выше, если $N_{k}=|\operatorname {dom} (C_{k})|$ - мощность клики и вес функции $f_{k,i}$ соответствует логарифму соответствующего фактора клики, т.е. $w_{k,i}=\log \varphi (c_{k,i})$, где $c_{k,i}$ — i -я возможная конфигурация k -й клики, т.е. -е значение i в области определения клики $C_{k}$.

Вероятность P часто называют мерой Гиббса. Такое выражение марковского поля как логистической модели возможно только в том случае, если все факторы клики отличны от нуля, т.е. если ни один из элементов ${\mathcal {X}}$ присваивается вероятность 0. Это позволяет применять методы матричной алгебры, например , что след матрицы является логарифмом определителя , с матричным представлением графа, возникающим из матрицы инцидентности графа .

Важность статистической суммы Z заключается в том, что многие понятия статистической механики , такие как энтропия , напрямую обобщаются на случай сетей Маркова, и интуитивное таким образом можно получить понимание. Кроме того, функция распределения позволяет применять вариационные методы к решению задачи: можно привязать движущую силу к одной или нескольким случайным переменным и исследовать реакцию сети в ответ на это возмущение . Так, например, можно добавить управляющий член J _v для каждой вершины v графа к статистической сумме, чтобы получить:

$Z[J]=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})+\sum _{v}J_{v}x_{v}\right)$

Формальное дифференцирование по J _v дает математическое ожидание случайной величины X _v, связанной с вершиной v :

$E[X_{v}]={\frac {1}{Z}}\left.{\frac {\partial Z[J]}{\partial J_{v}}}\right|_{J_{v}=0}.$

корреляционные функции Аналогично вычисляются ; двухточечная корреляция:

$C[X_{u},X_{v}]={\frac {1}{Z}}\left.{\frac {\partial ^{2}Z[J]}{\partial J_{u}\,\partial J_{v}}}\right|_{J_{u}=0,J_{v}=0}.$

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

Примеры

Гауссовский

Многомерное нормальное распределение образует марковское случайное поле относительно графа. $G=(V,E)$ если недостающие ребра соответствуют нулям в матрице точности (обратной ковариационной матрице ):

$X=(X_{v})_{v\in V}\sim {\mathcal {N}}({\boldsymbol {\mu }},\Sigma )$

такой, что

$(\Sigma ^{-1})_{uv}=0\quad {\text{iff}}\quad \{u,v\}\notin E.$

Вывод

Как и в байесовской сети , можно вычислить условное распределение набора узлов. $V'=\{v_{1},\ldots ,v_{i}\}$ данные значения другому набору узлов $W'=\{w_{1},\ldots ,w_{j}\}$ в марковском случайном поле путем суммирования всех возможных присвоений $u\notin V',W'$; это называется точным выводом . Однако точный вывод является #P-полной проблемой и, следовательно, в общем случае вычислительно неразрешим. Такие методы аппроксимации, как цепь Маркова Монте-Карло и циклическое распространение убеждений, часто более осуществимы на практике. Некоторые конкретные подклассы MRF, такие как деревья (см. Дерево Чоу – Лю ), имеют алгоритмы вывода с полиномиальным временем; обнаружение таких подклассов является активной темой исследований. Существуют также подклассы MRF, которые допускают эффективный вывод MAP или, скорее всего, присваивание; примеры из них включают ассоциативные сети. Еще одним интересным подклассом являются модели разложимых моделей (когда граф хордальный ): имея замкнутую форму для MLE , можно обнаружить непротиворечивую структуру для сотен переменных.

Условные случайные поля

Основная статья: Условное случайное поле

Одним из примечательных вариантов марковского случайного поля является условное случайное поле , в котором каждая случайная величина также может быть обусловлена ​​набором глобальных наблюдений. $o$. В этой модели каждая функция $\varphi _{k}$ является отображением всех присвоений как клике k , так и наблюдениям $o$ к неотрицательным действительным числам. Эта форма сети Маркова может быть более подходящей для создания дискриминационных классификаторов , которые не моделируют распределение по наблюдениям. CRF были предложены Джоном Д. Лафферти , Эндрю МакКаллумом и Фернандо К. Н. Перейрой в 2001 году.

Разнообразные приложения

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

См. также

• Составной граф ограничений
• Графическая модель
• Сеть зависимостей (графическая модель)
• Теорема Хаммерсли – Клиффорда
• Сеть Хопфилда
• Взаимодействующая система частиц
• Модель Изинга
• Лог-линейный анализ
• Цепь Маркова
• Марковская логическая сеть
• Метод максимальной энтропии
• Стохастический клеточный автомат