Марковская сеть

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

Определение

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

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

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

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

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

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

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

$X_A \perp\!\!\!\perp X_B | X_S$

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

Другими словами, граф G считается Марковским случайным полем по отношению к совместным распределенным вероятностям P (X = х) на множестве случайных величин X тогда и только тогда, когда разделение графа G подразумевает условную независимость: Если два узла и разделены в G после удаления из G множества узлов Z, то P (X = х) должна утверждать, что $X_i$ и $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:

$p(x) = \prod_{C \in \operatorname{cl}(G)} \phi_C (x_C)$

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

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

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

Пример

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

Логарифмическая модель марковского случайного поля с использованием функции $f_k$, как функции полного совместного распределения можно записать в виде

$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)$

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

$Z = \sum_{x \isin \mathcal{X}} \exp \left(\sum_{k} w_k^{\top} f_k(x_{ \{ k \} })\right)$

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

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

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

$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 .$^[3]

Примечания

1. ↑ Markov Random Fields and Their Applications. — American Mathematical Society, 1980. — ISBN MR06209550-8218-5001-6
2. ↑ Moussouris, John (1974). «Gibbs and Markov random systems with constraints». Journal of Statistical Physics 10 (1): 11–33. DOI:10.1007/BF01011714. MR0432132.
3. ↑ Gaussian Markov random fields: theory and applications. — CRC Press, 2005. — ISBN 1584884320