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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править вики-текст]

Неориентированный граф G = (V,E), множество случайных величин (Xv)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 = (Xv)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.