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

Набор случайных величин

Пример марковского случайного поля. Каждое ребро представляет зависимость. В этом примере: A зависит от B и D. B зависит от A и D. D зависит от A, B и E. E зависит от D и C. C зависит от E.

В области физики и вероятности марковское случайное поле ( MRF ), марковская сеть или неориентированная графическая модель — это набор случайных величин, имеющих марковское свойство , описанное неориентированным графом . Другими словами, случайное поле называется марковским случайным полем, если оно удовлетворяет марковским свойствам. Эта концепция берет свое начало в модели Шеррингтона–Киркпатрика . ^[1]

Сеть Маркова или MRF похожа на байесовскую сеть в своем представлении зависимостей; разница в том, что байесовские сети направлены и ацикличны , тогда как марковские сети ненаправлены и могут быть циклическими. Таким образом, марковская сеть может представлять определенные зависимости, которые байесовская сеть не может (например, циклические зависимости ^{[ необходимо дальнейшее объяснение ]} ); с другой стороны, она не может представлять определенные зависимости, которые байесовская сеть может (например, индуцированные зависимости ^{[ необходимо дальнейшее объяснение ]} ). Базовый граф марковского случайного поля может быть конечным или бесконечным.

Когда совместная плотность вероятности случайных величин строго положительна, ее также называют случайным полем Гиббса , поскольку, согласно теореме Хаммерсли–Клиффорда , ее можно представить мерой Гиббса для соответствующей (локально определенной) энергетической функции. Прототипическим марковским случайным полем является модель Изинга ; действительно, марковское случайное поле было введено как общая установка для модели Изинга. ^[2] В области искусственного интеллекта марковское случайное поле используется для моделирования различных задач низкого и среднего уровня в обработке изображений и компьютерном зрении . ^[3]

Определение

Учитывая неориентированный граф , набор случайных величин, индексированных по ,   образует марковское случайное поле относительно ,   ​​если они удовлетворяют локальным марковским свойствам: ${\displaystyle G=(V,E)}$ ${\displaystyle X=(X_{v})_{v\in V}}$ ${\displaystyle V}$ ${\displaystyle G}$

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

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\smallsetminus \{u,v\}}}$

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

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\smallsetminus \operatorname {N} [v]}\mid X_{\operatorname {N} (v)}}$

где — множество соседей , а — замкнутая окрестность . ${\textstyle \operatorname {N} (v)}$ ${\displaystyle v}$ ${\displaystyle \operatorname {N} [v]=v\cup \operatorname {N} (v)}$ ${\displaystyle v}$

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

${\displaystyle X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}}$

где каждый путь от узла в к узлу в проходит через . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S}$

Глобальное марковское свойство сильнее локального марковского свойства, которое, в свою очередь, сильнее парного. ^[4] Однако три вышеуказанных марковских свойства эквивалентны для положительных распределений ^[5] (тех, которые присваивают только ненулевые вероятности связанным переменным).

Связь между тремя марковскими свойствами особенно ясна в следующей формулировке:

• Попарно: Для любых не равных или не смежных, . ${\displaystyle i,j\in V}$ ${\displaystyle X_{i}\perp \!\!\!\perp X_{j}|X_{V\smallsetminus \{i,j\}}}$
• Локально: Для любого и не содержащего или не смежного с , . ${\displaystyle i\in V}$ ${\displaystyle J\subset V}$ ${\displaystyle i}$ ${\displaystyle X_{i}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (\{i\}\cup J)}}$
• Глобально: Для любых непересекающихся и не смежных, . ${\displaystyle I,J\subset V}$ ${\displaystyle X_{I}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (I\cup J)}}$

Факторизация клики

Поскольку марковское свойство произвольного распределения вероятностей может быть трудно установить, обычно используемым классом марковских случайных полей являются те, которые можно факторизовать в соответствии с кликами графа.

При наличии набора случайных величин пусть будет вероятностью конкретной конфигурации поля в  —то есть, есть вероятность обнаружения того, что случайные величины принимают конкретное значение . Поскольку — это набор, следует понимать, что вероятность следует брать относительно совместного распределения . ${\displaystyle X=(X_{v})_{v\in V}}$ ${\displaystyle P(X=x)}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle P(X=x)}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle X_{v}}$

Если эту совместную плотность можно разложить по кликам как ${\displaystyle G}$

${\displaystyle P(X=x)=\prod _{C\in \operatorname {cl} (G)}\varphi _{C}(x_{C})}$

затем образует марковское случайное поле относительно . Здесь — множество клик . Определение эквивалентно, если используются только максимальные клики. Функции иногда называют факторными потенциалами или кликовыми потенциалами . Обратите внимание, однако, что используется противоречивая терминология: слово потенциал часто применяется к логарифму . Это связано с тем, что в статистической механике имеет прямую интерпретацию как потенциальная энергия конфигурации . ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle \operatorname {cl} (G)}$ ${\displaystyle G}$ ${\displaystyle \varphi _{C}}$ ${\displaystyle \varphi _{C}}$ ${\displaystyle \log(\varphi _{C})}$  ${\displaystyle x_{C}}$

Некоторые MRF не факторизуются: простой пример можно построить на цикле из 4 узлов с некоторыми бесконечными энергиями, т.е. конфигурациями нулевых вероятностей, ^[6] даже если, что более уместно, разрешить бесконечным энергиям действовать на весь граф на . ^[7] ${\displaystyle V}$

MRF факторизуется, если выполняется хотя бы одно из следующих условий:

• плотность положительна (по теореме Хаммерсли–Клиффорда )
• граф является хордовым (по эквивалентности байесовской сети )

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

Экспоненциальная семья

Любое положительное марковское случайное поле можно записать как экспоненциальное семейство в канонической форме с функциями признаков, такими, что полное совместное распределение можно записать как ${\displaystyle f_{k}}$

${\displaystyle P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right)}$

где обозначение

${\displaystyle w_{k}^{\top }f_{k}(x_{\{k\}})=\sum _{i=1}^{N_{k}}w_{k,i}\cdot f_{k,i}(x_{\{k\}})}$

— это просто скалярное произведение по конфигурациям полей, а Z — это функция распределения :

${\displaystyle Z=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right).}$

Здесь обозначает множество всех возможных назначений значений всем случайным величинам сети. Обычно функции признаков определяются таким образом, что они являются индикаторами конфигурации клики, т. е. если соответствует i -й возможной конфигурации k -й клики и 0 в противном случае. Эта модель эквивалентна модели факторизации клик, приведенной выше, если - мощность клики, а вес признака соответствует логарифму соответствующего фактора клики, т. е . , где - i -я возможная конфигурация k -й клики, т. е. i -е значение в домене клики . ${\displaystyle {\mathcal {X}}}$ ${\displaystyle f_{k,i}}$ ${\displaystyle f_{k,i}(x_{\{k\}})=1}$ ${\displaystyle x_{\{k\}}}$ ${\displaystyle N_{k}=|\operatorname {dom} (C_{k})|}$ ${\displaystyle f_{k,i}}$ ${\displaystyle w_{k,i}=\log \varphi (c_{k,i})}$ ${\displaystyle c_{k,i}}$ ${\displaystyle C_{k}}$

Вероятность P часто называют мерой Гиббса. Это выражение марковского поля как логистической модели возможно только в том случае, если все факторы клики не равны нулю, т. е. если ни одному из элементов не присвоена вероятность 0. Это позволяет применять методы матричной алгебры, например , что след матрицы является логарифмом определителя , с матричным представлением графа, вытекающим из матрицы инцидентности графа . ${\displaystyle {\mathcal {X}}}$

Важность функции статистической разбивки Z заключается в том, что многие концепции из статистической механики , такие как энтропия , напрямую обобщаются на случай сетей Маркова, и таким образом можно получить интуитивное понимание. Кроме того, функция статистической разбивки позволяет применять вариационные методы к решению проблемы: можно прикрепить движущую силу к одной или нескольким случайным величинам и исследовать реакцию сети в ответ на это возмущение . Таким образом, например, можно добавить движущий член J _v для каждой вершины v графа к функции статистической разбивки, чтобы получить:

${\displaystyle Z[J]=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})+\sum _{v}J_{v}x_{v}\right)}$

Формальное дифференцирование по J _v дает математическое ожидание случайной величины X _{v ,} связанной с вершиной v :

${\displaystyle E[X_{v}]={\frac {1}{Z}}\left.{\frac {\partial Z[J]}{\partial J_{v}}}\right|_{J_{v}=0}.}$

Аналогично вычисляются функции корреляции ; двухточечная корреляция имеет вид:

${\displaystyle C[X_{u},X_{v}]={\frac {1}{Z}}\left.{\frac {\partial ^{2}Z[J]}{\partial J_{u}\,\partial J_{v}}}\right|_{J_{u}=0,J_{v}=0}.}$

К сожалению, хотя вероятность логистической сети Маркова является выпуклой, оценка вероятности или градиента вероятности модели требует вывода в модели, что, как правило, вычислительно неосуществимо (см. «Вывод» ниже).

Примеры

Гауссов

Многомерное нормальное распределение образует марковское случайное поле относительно графа, если отсутствующие ребра соответствуют нулям на матрице точности (обратной ковариационной матрице ): ${\displaystyle G=(V,E)}$

${\displaystyle X=(X_{v})_{v\in V}\sim {\mathcal {N}}({\boldsymbol {\mu }},\Sigma )}$

такой что

${\displaystyle (\Sigma ^{-1})_{uv}=0\quad {\text{iff}}\quad \{u,v\}\notin E.}$^[8]

Вывод

Как и в байесовской сети , можно вычислить условное распределение набора узлов, заданных значениями, в другой набор узлов в марковском случайном поле путем суммирования по всем возможным назначениям ; это называется точным выводом . Однако точный вывод является #P-полной проблемой и, таким образом, вычислительно неразрешимой в общем случае. Методы аппроксимации, такие как Монте-Карло с цепями Маркова и распространение циклических убеждений , часто более осуществимы на практике. Некоторые конкретные подклассы MRF, такие как деревья (см. дерево Чжоу–Лю ), имеют полиномиальные алгоритмы вывода; обнаружение таких подклассов является активной темой исследований. Существуют также подклассы MRF, которые допускают эффективный MAP или, скорее всего, назначение вывода; примерами этого являются ассоциативные сети. ^{[9] [10]} Другим интересным подклассом является подкласс разложимых моделей (когда граф является хордовым ): имея замкнутую форму для MLE , можно обнаружить согласованную структуру для сотен переменных. ^[11] ${\displaystyle V'=\{v_{1},\ldots ,v_{i}\}}$ ${\displaystyle W'=\{w_{1},\ldots ,w_{j}\}}$ ${\displaystyle u\notin V',W'}$

Условные случайные поля

Одним из примечательных вариантов случайного поля Маркова является условное случайное поле , в котором каждая случайная величина может быть также обусловлена ​​набором глобальных наблюдений . В этой модели каждая функция является отображением всех назначений как клике k , так и наблюдениям в неотрицательные действительные числа. Эта форма сети Маркова может быть более подходящей для создания дискриминантных классификаторов , которые не моделируют распределение по наблюдениям. CRF были предложены Джоном Д. Лафферти , Эндрю МакКаллумом и Фернандо К. Н. Перейрой в 2001 году. ^[12] ${\displaystyle o}$ ${\displaystyle \varphi _{k}}$ ${\displaystyle o}$

Разнообразные применения

Случайные поля Маркова находят применение в различных областях, от компьютерной графики до компьютерного зрения, машинного обучения или вычислительной биологии , ^{[13] [14]} и поиска информации . ^[15] MRF используются в обработке изображений для генерации текстур, поскольку они могут использоваться для генерации гибких и стохастических моделей изображений. В моделировании изображений задача состоит в том, чтобы найти подходящее распределение интенсивности заданного изображения, где пригодность зависит от типа задачи, а MRF достаточно гибки, чтобы использоваться для синтеза изображений и текстур, сжатия и восстановления изображений, сегментации изображений , вывода трехмерных изображений из двухмерных изображений, регистрации изображений , синтеза текстур , сверхразрешения , стереосопоставления и поиска информации . Их можно использовать для решения различных задач компьютерного зрения, которые могут быть поставлены как задачи минимизации энергии или задачи, где различные регионы должны быть различены с использованием набора отличительных признаков в рамках случайного поля Маркова, чтобы предсказать категорию региона. ^[16] Марковские случайные поля были обобщением модели Изинга и с тех пор широко использовались в комбинаторной оптимизации и сетях.

Смотрите также

• Составной граф ограничений
• Графическая модель
• Сеть зависимости (графическая модель)
• Теорема Хаммерсли–Клиффорда
• сеть Хопфилда
• Система взаимодействующих частиц
• модель Изинга
• Лог-линейный анализ
• цепь Маркова
• Марковская логическая сеть
• Метод максимальной энтропии
• Стохастический клеточный автомат

Ссылки

1. Шеррингтон, Дэвид; Киркпатрик, Скотт (1975), «Решаемая модель спинового стекла», Physical Review Letters , 35 (35): 1792–1796, Bibcode : 1975PhRvL..35.1792S, doi : 10.1103/PhysRevLett.35.1792
2. Киндерманн, Росс; Снелл, Дж. Лори (1980). Марковские случайные поля и их приложения (PDF) . Американское математическое общество. ISBN 978-0-8218-5001-5. MR  0620955. Архивировано из оригинала (PDF) 2017-08-10 . Получено 2012-04-09 .
3. Ли, СЗ (2009). Моделирование случайных полей Маркова в анализе изображений. Springer. ISBN 9781848002791.
4. Лауритцен, Штеффен (1996). Графические модели . Оксфорд: Кларендон Пресс. п. 33. ISBN 978-0198522195.
5. Коллер, Дафна; Фридман, Нир (2009). Вероятностные графические модели . МТИ Пресс. п. 114-122. ISBN 9780262013192.
6. Муссурис, Джон (1974). «Случайные системы Гиббса и Маркова с ограничениями». Журнал статистической физики . 10 (1): 11–33. Bibcode :1974JSP....10...11M. doi :10.1007/BF01011714. hdl : 10338.dmlcz/135184 . MR  0432132. S2CID  121299906.
7. Гандольфи, Альберто; Ленарда, Пьетро (2016). «Заметка о гиббсовских и марковских случайных полях с ограничениями и их моментами». Математика и механика сложных систем . 4 (3–4): 407–422. doi : 10.2140/memocs.2016.4.407 .
8. Рю, Ховард; Хельд, Леонхард (2005). Гауссовские марковские случайные поля: теория и приложения . CRC Press. ISBN 978-1-58488-432-3.
9. Taskar, Benjamin; Chatalbashev, Vassil; Koller, Daphne (2004), "Изучение ассоциативных сетей Маркова", в Brodley, Carla E. (ред.), Труды Двадцать первой международной конференции по машинному обучению (ICML 2004), Банф, Альберта, Канада, 4-8 июля 2004 г. , Серия трудов международной конференции ACM, т. 69, Association for Computing Machinery , стр. 102, CiteSeerX 10.1.1.157.329 , doi :10.1145/1015330.1015444, ISBN  978-1581138283, S2CID  11312524.
10. Duchi, John C.; Tarlow, Daniel; Elidan, Gal; Koller, Daphne (2006), «Использование комбинаторной оптимизации в распространении убеждений максимального произведения», в Schölkopf, Bernhard; Platt, John C.; Hoffman, Thomas (ред.), Труды двадцатой ежегодной конференции по системам обработки нейронной информации, Ванкувер, Британская Колумбия, Канада, 4-7 декабря 2006 г. , Достижения в области систем обработки нейронной информации , т. 19, MIT Press , стр. 369–376.
11. Petitjean, F.; Webb, GI; Nicholson, AE (2013). Масштабирование логлинейного анализа для многомерных данных (PDF) . Международная конференция по интеллектуальному анализу данных. Даллас, Техас, США: IEEE.
12. "Две классические премии за статьи, представленные на ICML 2013". ICML . 2013 . Получено 15 декабря 2014 .
13. Киндерманн и Снелл, Росс и Лори (1980). Марковские случайные поля и их приложения . Род-Айленд: Американское математическое общество. ISBN 978-0-8218-5001-5.
14. Банф, Майкл; Ри, Сын Й. (2017-02-01). «Улучшение вывода сети регуляции генов посредством интеграции данных с марковскими случайными полями». Scientific Reports . 7 (1): 41174. Bibcode :2017NatSR...741174B. doi :10.1038/srep41174. ISSN  2045-2322. PMC 5286517 . PMID  28145456. 
15. Метцлер, Дональд; Крофт, В. Брюс (2005). Модель случайного поля Маркова для зависимостей терминов . Труды 28-й конференции ACM SIGIR. Сальвадор, Бразилия: ACM. стр. 472–479. doi :10.1145/1076034.1076115.
16. Чжан и Захор, Ричард и Авидех (2014). «Автоматическая идентификация областей окон в облаках точек внутри помещений с использованием лидара и камер». VIP Lab Publications . CiteSeerX 10.1.1.649.303 .