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

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

Примечания

Kindermann, Ross; Snell, J. Laurie. Markov Random Fields and Their Applications (англ.). — American Mathematical Society, 1980. — ISBN 0-8218-5001-6.
Moussouris, John. Gibbs and Markov random systems with constraints (англ.) // Journal of Statistical Physics : journal. — 1974. — Vol. 10, no. 1. — P. 11—33. — doi:10.1007/BF01011714.
Rue, Håvard; Held, Leonhard. Gaussian Markov random fields: theory and applications (англ.). — CRC Press, 2005. — ISBN 1584884320.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Kindermann, Ross; Snell, J. Laurie. Markov Random Fields and Their Applications (англ.). — American Mathematical Society, 1980. — ISBN 0-8218-5001-6.

[2] Moussouris, John. Gibbs and Markov random systems with constraints (англ.) // Journal of Statistical Physics : journal. — 1974. — Vol. 10, no. 1. — P. 11—33. — doi:10.1007/BF01011714.

[3] Rue, Håvard; Held, Leonhard. Gaussian Markov random fields: theory and applications (англ.). — CRC Press, 2005. — ISBN 1584884320.

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей Бэггинг Бустинг Random forest Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k-ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG