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

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

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



Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Марковская сеть" в других словарях:

  • Марковская — Марковская: Марковская деревня в Каргопольском районе Архангельской области. Марковская деревня в Красноборском районе Архангельской области. Марковская деревня в Холмогорском районе Архангельской области. Марковская деревня в Шенкурском районе… …   Википедия

  • Скрытая марковская модель — Диаграмма переходов в скрытой Марковской модели (пример) x  скрытые состояния y  наблюдаемые результаты a  вероятности переходов b  вероятность результата Скрытая Марковская модель (СММ)  статистическая модель,… …   Википедия

  • Байесовская сеть — (или Байесова сеть, Байесовская сеть доверия)  это графическая вероятностная модель, представляющая собой множество переменных и их вероятностных зависимостей. Например, байесовская сеть может быть использована для вычисления вероятности… …   Википедия

  • Графическая вероятностная модель — Графическая вероятностная модель  это вероятностная модель, в которой в виде графа представлены зависимости между случайными величинами. Вершины графа соответствуют случайным переменным, а рёбра  непосредственным вероятностным… …   Википедия

  • Список эпизодов сериала «4исла» — «4исла» (англ. Numb3rs)  детективный телевизионный сериал, созданный Николасом Фалаччи и Шерил Хьютон. Премьера телесериала состоялась 23 января 2005 года, 18 мая 2010 года CBS закрыл сериал …   Википедия

  • Ботанический сад ПетрГУ — Ботанический сад Петрозаводского университета основан в 1951 году на северо восточном берегу Петрозаводской губы Онежского озера (61.783333, 34.33333361°47′ с. ш. 34 …   Википедия

  • Марково (Усть-Кутский район) — У этого термина существуют и другие значения, см. Марково. Село Марково Страна РоссияРоссия …   Википедия

  • Нефть — (Oil) Нефть это горючая жидкость Добыча и переработка запасов нефти является основой экономики многих стран Содержание >>>>>>>>>>>>>>>>> …   Энциклопедия инвестора

  • Улица Добролюбова (Екатеринбург) — У этого топонима есть и другие значения, см. Улица Добролюбова. Улица Добролюбова …   Википедия

  • Бунд — У этого термина существуют и другие значения, см. Бунд (значения). «Всеобщий еврейский рабочий союз в Литве, Польше и России» אַלגעמיינער ייִדישער אַרבעטערסבונד אין ליטע, פּוילן און רוסלאַנד Другие названия: Бунд Идеология: социализм, антисионизм …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»