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

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

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

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

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

Определение

Учитывая неправомерный график $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)}$.
• Global: для любого $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\}}$ соответствует возможной конфигурации клики K -Th и 0 в противном случае. Эта модель эквивалентна модели факторизации клики, приведенной выше, если $N_{k}=|\operatorname {dom} (C_{k})|$ это кардинальность клики и вес функции $f_{k,i}$ соответствует логарифму соответствующего фактора клики, т.е. $w_{k,i}=\log \varphi (c_{k,i})$, где $c_{k,i}$ Является ли -т 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, такие как деревья (см. Дерево Chow-Liu ), имеют алгоритмы вывода полиномиального времени; Обнаружение таких подклассов является активной темой исследования. Существуют также подклассы MRF, которые разрешают эффективную карту или наиболее вероятное назначение, вывод; Примеры их включают ассоциативные сети. Другим интересным подкладом является разловная модели (когда график является хордовым ): наличие закрытой формы для MLE , можно обнаружить постоянную структуру для сотен переменных.

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

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

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

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

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

Смотрите также

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