Марковская сеть , Марковское случайное поле , или неориентированная графовая модель — это графовая модель , в которой множество случайных величин обладает Марковским свойством , описанным неориентированным графом . Марковская сеть отличается от другой графовой модели, Байесовской сети , представлением зависимостей между случайными величинами. Она может выразить некоторые зависимости, которые не может выразить Байесовская сеть (например, циклические зависимости); с другой стороны, она не может выразить некоторые другие. Прототипом Марковской сети была Модель Изинга намагничивания материала в статистической физике : Марковская сеть была представлена как обобщение этой модели.

Определение

Пусть задан неориентированный граф G = ( V , E ), тогда множество случайных величин ( X _v ) _{v ∈ V} индексируемых V образуют Марковское случайное поле по отношению к G , если они удовлетворяют следующим эквивалентным Марковским свойствам:

Свойство пар : Любые две несмежные переменные условно независимы с учетом всех других переменных:

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}|X_{V\setminus \{u,v\}}\quad {\text{if }}\{u,v\}\notin E}$

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

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {cl} (v)}|X_{\operatorname {ne} (v)}}$

где ne( v ) — множество соседей V , и cl( v ) = { v } ∪ ne( v ) является замкнутой окрестностью v .

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

${\displaystyle X_{A}\perp \!\!\!\perp X_{B}|X_{S}}$

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

Другими словами, граф G считается Марковским случайным полем по отношению к совместным распределенным вероятностям P ( X = х ) на множестве случайных величин X тогда и только тогда, когда разделение графа G подразумевает условную независимость: Если два узла и разделены в G после удаления из G множества узлов Z , то P ( X = х ) должна утверждать, что ${\displaystyle X_{i}}$ и ${\displaystyle X_{j}}$ условно независимы с учетом случайных величин, соответствующих Z . Если это условие выполнено, то говорят, что G является независимой картой (independency map) (или И-картой (I-map)) распределения вероятностей .

Многие определения требуют еще чтобы G было минимальной И-картой, то есть И-картой, при удалении из которой одного ребра она перестает быть И-картой. (Это разумно требовать, поскольку это приводит к наиболее компактному представлению, которое включает как можно меньше зависимостей; отметим, что полный граф это тривиальная И-карта.) В случае, когда G не только И-карта (то есть не представляет независимости, которые не указаны в P ( X = х )), но и не представляет зависимости, которые не указаны в P ( X = х ), G называется совершенной картой (perfect map) P ( X = х ). Она представляет набор независимостей указанных P ( X = х ).

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

Так как марковские свойства произвольного распределения вероятностей трудно установить, широко используется класс марковских случайных полей, которые могут быть факторизованы в соответствии с кликами графа. Множество случайных величин X = ( X _v ) _{v ∈ V} , для которых совместная плотность может быть факторизована на кликах G :

${\displaystyle p(x)=\prod _{C\in \operatorname {cl} (G)}\phi _{C}(x_{C})}$

формирует Марковское случайное поле по отношению к G , где cl( G ) множество клик G (определение эквивалентно, если используются только максимальные клики). Функции φ _C часто называют фактор потенциалами или потенциалами клик. Хотя существуют MRFs, которые не раскладываются (простой пример может быть построена на цикле 4х узлов ), в некоторых случаях может быть доказано, что они находятся в эквивалентных состояниях:

• если плотность положительна
• если граф является гармоничным

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

Пример

Логистическая модель

Логистическая модель марковского случайного поля с использованием функции ${\displaystyle f_{k}}$ , как функции полного совместного распределения можно записать в виде

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

с функцией распределения

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

где ${\displaystyle {\mathcal {X}}}$ множество возможных распределений значений случайных величин всех сети.

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

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

${\displaystyle X=(X_{v})_{v\in V}\sim {\mathcal {N}}({\boldsymbol {\mu }},\Sigma )\qquad {\text{such that}}\qquad (\Sigma ^{-1})_{uv}=0\quad {\text{if}}\quad \{u,v\}\notin E.}$

Примечания