Марковская сеть, Марковское случайное поле, или неориентированная графовая модель — это графовая модель, в которой множество случайных величин обладает Марковским свойством, описанным неориентированным графом. Марковская сеть отличается от другой графовой модели, Байесовской сети, представлением зависимостей между случайными величинами. Она может выразить некоторые зависимости, которые не может выразить Байесовская сеть (например, циклические зависимости); с другой стороны, она не может выразить некоторые другие. Прототипом Марковской сети была Модель Изинга намагничивания материала в статистической физике: Марковская сеть была представлена как обобщение этой модели.
Определение
Пусть задан неориентированный граф G = (V,E), тогда множество случайных величин (Xv)v ∈ V индексируемых V образуют Марковское случайное поле по отношению к G, если они удовлетворяют следующим эквивалентным Марковским свойствам:
Свойство пар: Любые две несмежные переменные условно независимы с учетом всех других переменных: X u ⊥ ⊥ X v | X V ∖ { u , v } if { u , v } ∉ E {displaystyle X_{u}perp !!!perp X_{v}|X_{Vsetminus {u,v}}quad { ext{if }}{u,v} otin E} Локальное свойство: переменная условно независима от всех других величин, с учетом своих соседей: X v ⊥ ⊥ X V ∖ cl ( v ) | X ne ( v ) {displaystyle X_{v}perp !!!perp X_{Vsetminus operatorname {cl} (v)}|X_{operatorname {ne} (v)}} где ne(v) — множество соседей V, и cl(v) = {v} ∪ ne(v) является замкнутой окрестностью v. Глобальное свойство: Любые два подмножества переменных условно независимы с учетом разделяющего подмножества: X A ⊥ ⊥ X B | X S {displaystyle X_{A}perp !!!perp X_{B}|X_{S}} где каждый путь от узла в А к узлу в B проходит через S.Другими словами, граф G считается Марковским случайным полем по отношению к совместным распределенным вероятностям P (X = х) на множестве случайных величин X тогда и только тогда, когда разделение графа G подразумевает условную независимость: Если два узла и разделены в G после удаления из G множества узлов Z, то P (X = х) должна утверждать, что X i {displaystyle X_{i}} и X j {displaystyle X_{j}} условно независимы с учетом случайных величин, соответствующих Z. Если это условие выполнено, то говорят, что G является независимой картой (independency map) (или И-картой (I-map)) распределения вероятностей.
Многие определения требуют еще чтобы G было минимальной И-картой, то есть И-картой, при удалении из которой одного ребра она перестает быть И-картой. (Это разумно требовать, поскольку это приводит к наиболее компактному представлению, которое включает как можно меньше зависимостей; отметим, что полный граф это тривиальная И-карта.) В случае, когда G не только И-карта (то есть не представляет независимости, которые не указаны в P (X = х)), но и не представляет зависимости, которые не указаны в P (X = х), G называется совершенной картой (perfect map) P (X = х). Она представляет набор независимостей указанных P (X = х).
Факторизация клик
Так как марковские свойства произвольного распределения вероятностей трудно установить, широко используется класс марковских случайных полей, которые могут быть факторизованы в соответствии с кликами графа. Множество случайных величин X = (Xv)v ∈ V, для которых совместная плотность может быть факторизована на кликах G:
p ( x ) = ∏ C ∈ cl ( G ) ϕ C ( x C ) {displaystyle p(x)=prod _{Cin operatorname {cl} (G)}phi _{C}(x_{C})}формирует Марковское случайное поле по отношению к G, где cl(G) множество клик G (определение эквивалентно, если используются только максимальные клики). Функции φC часто называют фактор потенциалами или потенциалами клик. Хотя существуют MRFs, которые не раскладываются (простой пример может быть построена на цикле 4х узлов), в некоторых случаях может быть доказано, что они находятся в эквивалентных состояниях:
- если плотность положительна
- если граф является гармоничным
Когда такое разложение существует, можно построить фактор граф для сети.
Пример
Логистическая модель
Логистическая модель марковского случайного поля с использованием функции f k {displaystyle f_{k}} , как функции полного совместного распределения можно записать в виде
P ( X = x ) = 1 Z exp ( ∑ k w k ⊤ f k ( x { k } ) ) = 1 Z exp ( ∑ k ∑ i = 1 N k w k , i ⋅ f k , i ( x { k } ) ) {displaystyle P(X=x)={frac {1}{Z}}exp left(sum _{k}w_{k}^{ op }f_{k}(x_{{k}}) ight)={frac {1}{Z}}exp left(sum _{k}sum _{i=1}^{N_{k}}w_{k,i}cdot f_{k,i}(x_{{k}}) ight)}с функцией распределения
Z = ∑ x ∈ X exp ( ∑ k w k ⊤ f k ( x { k } ) ) {displaystyle Z=sum _{xin {mathcal {X}}}exp left(sum _{k}w_{k}^{ op }f_{k}(x_{{k}}) ight)}где X {displaystyle {mathcal {X}}} множество возможных распределений значений случайных величин всех сети.
Гауссовское марковское случайное поле
Формы многомерного нормального распределения марковского случайного поля по отношению к графу G = (V, E), если отсутствующим ребрам соответствуют нули в матрице точности (обратной ковариационной матрицы):
X = ( X v ) v ∈ V ∼ N ( μ , Σ ) such that ( Σ − 1 ) u v = 0 if { u , v } ∉ E . {displaystyle X=(X_{v})_{vin V}sim {mathcal {N}}({oldsymbol {mu }},Sigma )qquad { ext{such that}}qquad (Sigma ^{-1})_{uv}=0quad { ext{if}}quad {u,v} otin E.}