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

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

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

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

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

Определение

Для неориентированного графа набор случайных величин, проиндексированных с помощью,   формирует марковское случайное поле относительно   того, удовлетворяют ли они локальным марковским свойствам: ${\ 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}$

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

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

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

Учитывая набор случайных величин , пусть будет вероятность конкретной конфигурации поля в  . То есть вероятность обнаружить, что случайные величины принимают конкретное значение . Поскольку это набор, вероятность того , следует понимать , которые должны быть приняты по отношению к совместному распределению из . ${\ Displaystyle X = (X_ {v}) _ {v \ in V}}$${\ Displaystyle Р (Х = х)}$${\ displaystyle x}$${\ displaystyle X}$${\ Displaystyle Р (Х = х)}$${\ 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 \ журнал (\ phi _ {C})}$ ${\ displaystyle x_ {C}}$

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

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

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

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

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

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

${\ Displaystyle P (X = x) = {\ frac {1} {Z}} \ exp \ left (\ sum _ {k} w_ {k} ^ {\ top} f_ {k} (x _ {\ {k \}})\Правильно)}$

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

${\ displaystyle w_ {k} ^ {\ top} f_ {k} (x _ {\ {k \}}) = \ sum _ {i = 1} ^ {N_ {k}} w_ {k, i} \ cdot е_ {к, я} (х _ {\ {к \}})}$

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

${\ displaystyle Z = \ sum _ {x \ in {\ mathcal {X}}} \ exp \ left (\ sum _ {k} w_ {k} ^ {\ top} f_ {k} (x _ {\ {k \}})\Правильно).}$

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

Вывод

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

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

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

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

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

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

использованная литература