Марковское случайное поле - Markov random field

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

В области физика и вероятность, а Марковское случайное поле (часто сокращенно MRF), Сеть Маркова или же ненаправленный графическая модель это набор случайные переменные иметь Марковская собственность описанный неориентированный граф. Другими словами, случайное поле считается Марков случайное поле, если оно удовлетворяет марковским свойствам.

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

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

Определение

Учитывая неориентированный граф ${\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\setminus \{u,v\}}}$

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

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \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}$.

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

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

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

Учитывая набор случайных величин ${\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)}\phi _{C}(x_{C})}$

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

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

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

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

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

Важность статистической суммы 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 дает ожидаемое значение случайной величины Икс_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.}$^[7]

Вывод

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

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

Основная статья: Условное случайное поле

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

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

Марковские случайные поля находят применение в самых разных областях, начиная от компьютерная графика компьютерному зрению, машинное обучение или вычислительная биология.^[12][13] MRF используются при обработке изображений для создания текстур, поскольку они могут использоваться для создания гибких и стохастических моделей изображения. При моделировании изображений задача состоит в том, чтобы найти подходящее распределение интенсивности данного изображения, где пригодность зависит от типа задачи, а MRF достаточно гибки, чтобы их можно было использовать для синтеза изображений и текстур. сжатие изображений и реставрация, сегментация изображения, Вывод 3D-изображения из 2D-изображений, регистрация изображения, синтез текстуры, сверхвысокое разрешение, стерео согласование и поиск информации. Их можно использовать для решения различных задач компьютерного зрения, которые могут быть сформулированы как задачи минимизации энергии, или задачи, в которых необходимо различать различные регионы с использованием набора отличительных признаков в рамках структуры марковского случайного поля для прогнозирования категории региона.^[14] Марковские случайные поля были обобщением модели Изинга и с тех пор широко используются в комбинаторных оптимизациях и сетях.

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

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

Рекомендации

1. Киндерманн, Росс; Снелл, Дж. Лори (1980). Марковские случайные поля и их приложения. (PDF). Американское математическое общество. ISBN  978-0-8218-5001-5. МИСТЕР  0620955.
2. Ли, С. З. (2009). Моделирование марковского случайного поля в анализе изображений. Springer. ISBN  9781848002791.
3. Лауритцен, Штеффен (1996). Графические модели. Оксфорд: Clarendon Press. п. 33. ISBN  978-0198522195.
4. Вероятностные графические модели.
5. Муссурис, Джон (1974). «Гиббсовские и марковские случайные системы со связями». Журнал статистической физики. 10 (1): 11–33. Bibcode:1974JSP .... 10 ... 11М. Дои:10.1007 / BF01011714. HDL:10338.dmlcz / 135184. МИСТЕР  0432132. S2CID  121299906.
6. Гандольфи, Альберто; Ленарда, Пьетро (2016). «Заметка о гиббсовских и марковских случайных полях с ограничениями и их моментах». Математика и механика сложных систем. 4 (3–4): 407–422. Дои:10.2140 / memocs.2016.4.407.
7. Rue, Håvard; Хелд, Леонхард (2005). Гауссовские марковские случайные поля: теория и приложения. CRC Press. ISBN  978-1-58488-432-3.
8. Таскар, Бенджамин; Чаталбашев, Васил; Коллер, Дафна (2004), "Изучение ассоциативных сетей Маркова", в Бродли, Карла Э. (ред.), Труды Двадцать первой Международной конференции по машинному обучению (ICML 2004), Банф, Альберта, Канада, 4-8 июля 2004 г., Сборник материалов международной конференции ACM, 69, Ассоциация вычислительной техники, п. 102, CiteSeerX  10.1.1.157.329, Дои:10.1145/1015330.1015444, ISBN  978-1581138283, S2CID  11312524.
9. Duchi, John C .; Тарлоу, Дэниел; Элидан, Гал; Коллер, Дафна (2006), «Использование комбинаторной оптимизации в распространении убеждений о максимальном произведении», в Шёлкопфе, Бернхард; Platt, John C .; Хоффман, Томас (ред.), Материалы двадцатой ежегодной конференции по системам обработки нейронной информации, Ванкувер, Британская Колумбия, Канада, 4-7 декабря 2006 г., Достижения в системах обработки нейронной информации, 19, MIT Press, стр. 369–376.
10. Petitjean, F .; Webb, G.I .; Николсон, А.Е. (2013). Масштабирование лог-линейного анализа до данных большой размерности (PDF). Международная конференция по интеллектуальному анализу данных. Даллас, Техас, США: IEEE.
11. «Два классических бумажных приза за доклады, представленные на ICML 2013». ICML. 2013. Получено 15 декабря 2014.
12. Киндерманн и Снелл, Росс и Лори (1980). Марковские случайные поля и их приложения. Род-Айленд: Американское математическое общество. ISBN  978-0-8218-5001-5.
13. Банф, Майкл; Ри, Сын Ю. (2017-02-01). «Улучшение вывода сети регуляции генов за счет интеграции данных с марковскими случайными полями». Научные отчеты. 7 (1): 41174. Bibcode:2017НатСР ... 741174Б. Дои:10.1038 / srep41174. ISSN  2045-2322. ЧВК  5286517. PMID  28145456.
14. Чжан и Захор, Ричард и Авидех (2014). «Автоматическая идентификация оконных областей на внутренних облаках точек с помощью LiDAR и камер». Публикации VIP Lab. CiteSeerX  10.1.1.649.303.

внешняя ссылка

• Реализация MRF на C ++ для обычных 2D-решеток