В области физики и вероятности , А случайное поле Маркова (часто сокращенно MRF ), сеть Маркова или неориентированная графическая модель представляет собой набор случайных величин , имеющие свойство Маркова описывается неориентированным графом . Другими словами, случайное поле называется марковским случайным полем, если оно удовлетворяет марковским свойствам.
Марковская сеть или MRF похожа на байесовскую сеть в представлении зависимостей; разница в том, что байесовские сети являются направленными и ациклическими , тогда как марковские сети неориентированы и могут быть циклическими. Таким образом, марковская сеть может представлять определенные зависимости, которые байесовская сеть не может (например, циклические зависимости [ требуется дополнительное объяснение ] ); с другой стороны, он не может представлять определенные зависимости, которые может иметь байесовская сеть (например, индуцированные зависимости [ требуется дополнительное объяснение ] ). Базовый граф марковского случайного поля может быть конечным или бесконечным.
Когда совместная плотность вероятности случайных величин строго положительна, это также называется случайным полем Гиббса , потому что, согласно теореме Хаммерсли – Клиффорда , оно может быть представлено мерой Гиббса для подходящего (локально определенного) энергетическая функция. Прототипом марковского случайного поля является модель Изинга ; действительно, марковское случайное поле было введено в качестве общего условия для модели Изинга. [1] В области искусственного интеллекта марковское случайное поле используется для моделирования различных задач низкого и среднего уровня в обработке изображений и компьютерном зрении . [2]
Определение
Учитывая неориентированный граф , набор случайных величин проиндексировано образуют марковское случайное поле относительно если они удовлетворяют локальным марковским свойствам:
- Парное марковское свойство : любые две несмежные переменные условно независимы при всех остальных переменных:
- Локальное марковское свойство : переменная условно независима от всех других переменных с учетом своих соседей:
- где это множество соседей , а также это замкнутая окрестность из .
- Глобальное марковское свойство : любые два подмножества переменных условно независимы с учетом разделяющего подмножества:
- где каждый путь от узла в к узлу в проходит через .
Глобальное марковское свойство сильнее, чем локальное марковское свойство, которое, в свою очередь, сильнее, чем попарное. [3] Однако указанные выше три марковских свойства эквивалентны для положительных распределений [4] (тех, которые присваивают только ненулевые вероятности ассоциированным переменным).
Факторизация клики
Поскольку марковское свойство произвольного распределения вероятностей может быть трудно установить, обычно используемым классом марковских случайных полей являются те, которые можно факторизовать в соответствии с кликами графа.
Учитывая набор случайных величин , позволять быть вероятностью конкретной конфигурации поля в . Это, вероятность обнаружить, что случайные величины приобретать особую ценность . Так как множество, вероятность Следует понимать , которые должны быть приняты по отношению к совместному распределению из.
Если эту совместную плотность можно разложить по кликам :
тогда образует марковское случайное поле относительно . Здесь, это множество клик . Определение эквивалентно, если используются только максимальные клики. Функциииногда называют факторными потенциалами или потенциалами клики . Обратите внимание, однако, что используется противоречивая терминология: слово потенциал часто применяется к логарифму. Это потому, что в статистической механике ,имеет прямую интерпретацию в качестве потенциальной энергии в виде конфигурации .
Некоторые MRF не разлагаются на множители: простой пример может быть построен на цикле из 4 узлов с некоторыми бесконечными энергиями, то есть конфигурациями с нулевой вероятностью [5], даже если один, что более уместно, позволяет бесконечным энергиям воздействовать на полный граф на. [6]
Факторизация MRF выполняется, если выполняется хотя бы одно из следующих условий:
- плотность положительна (по теореме Хаммерсли – Клиффорда )
- граф хордовый (по эквивалентности байесовской сети )
Когда такая факторизация действительно существует, можно построить факторный граф для сети.
Экспоненциальная семья
Любое положительное марковское случайное поле может быть записано как экспоненциальное семейство в канонической форме с функциями функций такое, что полное совместное распределение может быть записано как
где обозначение
- это просто скалярное произведение по конфигурациям полей, а Z - это статистическая сумма :
Здесь, обозначает набор всех возможных присвоений значений всем случайным переменным сети. Обычно функция функцииопределены так, что они являются индикаторами конфигурации клики, т. е. если соответствует i -й возможной конфигурации k -й клики и 0 в противном случае. Эта модель эквивалентна модели факторизации клики, приведенной выше, если - мощность клики, а вес признака соответствует логарифму соответствующего клик-фактора, т.е. , где это я ая возможную конфигурацию к -й клике, т.е. на я -му значение в области клики.
Вероятность P часто называют мерой Гиббса. Такое выражение марковского поля как логистической модели возможно только в том случае, если все кликовые факторы не равны нулю, т.е. если ни один из элементовприсваивается вероятность 0. Это позволяет применять методы матричной алгебры, например, что след матрицы является логарифмом определителя , с матричным представлением графа, возникающим из матрицы инцидентности графа .
Важность статистической суммы Z заключается в том, что многие концепции статистической механики , такие как энтропия , напрямую обобщаются на случай сетей Маркова, и тем самым можно получить интуитивное понимание. Кроме того, статистическая сумма позволяет применять вариационные методы к решению проблемы: можно приложить движущую силу к одной или нескольким случайным величинам и исследовать реакцию сети в ответ на это возмущение . Таким образом, например, можно добавить управляющий член J v для каждой вершины v графа к функции распределения, чтобы получить:
Формальное дифференцирование по J v дает математическое ожидание случайной величины X v, связанной с вершиной v :
Аналогичным образом вычисляются корреляционные функции ; двухточечная корреляция:
К сожалению, хотя вероятность логистической сети Маркова является выпуклой, оценка вероятности или градиента вероятности модели требует вывода в модели, что, как правило, невозможно с вычислительной точки зрения (см. «Вывод» ниже).
Примеры
Гауссовский
Многомерное нормальное распределение формирует случайное поле марковского по отношению к графеесли недостающие ребра соответствуют нулям в матрице точности ( матрица обратной ковариации ):
такой, что
- [7]
Вывод
Как и в байесовской сети, можно вычислить условное распределение набора узлов заданные значения другому набору узлов в марковском случайном поле, суммируя все возможные присвоения ; это называется точным выводом . Однако точный вывод - это # P-полная проблема и, следовательно, в общем случае трудноразрешима с вычислительной точки зрения. Методы приближения, такие как цепь Маркова Монте-Карло и зацикленное распространение убеждений , часто более осуществимы на практике. Некоторые конкретные подклассы MRF, такие как деревья (см. Дерево Чоу – Лю ), имеют алгоритмы вывода с полиномиальным временем; обнаружение таких подклассов - активная тема исследования. Существуют также подклассы MRF, которые допускают эффективный MAP или наиболее вероятный вывод назначения; примеры из них включают ассоциативные сети. [8] [9] Другой интересный подкласс - это подкласс разложимых моделей (когда граф хордовый ): имея замкнутую форму для MLE , можно обнаружить непротиворечивую структуру для сотен переменных. [10]
Условные случайные поля
Одним из примечательных вариантов марковского случайного поля является условное случайное поле , в котором каждая случайная величина также может быть обусловлена набором глобальных наблюдений.. В этой модели каждая функцияотображение всех присвоений как клике k, так и наблюдениямк неотрицательным действительным числам. Эта форма сети Маркова может быть более подходящей для создания дискриминантных классификаторов , которые не моделируют распределение по наблюдениям. CRF были предложены Джоном Д. Лафферти , Эндрю МакКаллумом и Фернандо К. Н. Перейрой в 2001 году [11].
Разнообразные приложения
Марковские случайные поля находят применение в самых разных областях, от компьютерной графики до компьютерного зрения, машинного обучения или вычислительной биологии. [12] [13] MRF используются при обработке изображений для создания текстур, поскольку их можно использовать для создания гибких и стохастических моделей изображения. При моделировании изображений задача состоит в том, чтобы найти подходящее распределение интенсивности данного изображения, где пригодность зависит от типа задачи, а MRF достаточно гибки, чтобы их можно было использовать для синтеза изображений и текстур, сжатия и восстановления изображений, сегментации изображения , 3D-изображения. вывод из 2D-изображений, совмещение изображений , синтез текстур , сверхвысокое разрешение , стереосопоставление и поиск информации . Их можно использовать для решения различных задач компьютерного зрения, которые могут быть сформулированы как задачи минимизации энергии, или задачи, в которых необходимо различать различные области с использованием набора отличительных признаков в рамках структуры марковского случайного поля для прогнозирования категории области. [14] Марковские случайные поля были обобщением модели Изинга и с тех пор широко используются в комбинаторных оптимизациях и сетях.
Смотрите также
- Составной граф ограничений
- Графическая модель
- Сеть зависимостей (графическая модель)
- Теорема Хаммерсли – Клиффорда
- Сеть Хопфилда
- Система взаимодействующих частиц
- Модель Изинга
- Логлинейный анализ
- Цепь Маркова
- Марковская логическая сеть
- Метод максимальной энтропии
- Стохастический клеточный автомат
Рекомендации
- ^ Киндерманн, Росс; Снелл, Дж. Лори (1980). Марковские случайные поля и их приложения (PDF) . Американское математическое общество. ISBN 978-0-8218-5001-5. Руководство по ремонту 0620955 .
- ^ Ли, СЗ (2009). Моделирование марковского случайного поля в анализе изображений . Springer. ISBN 9781848002791.
- ^ Лауритцен, Штеффен (1996). Графические модели . Оксфорд: Clarendon Press. п. 33. ISBN 978-0198522195.
- ^ Вероятностные графические модели .
- ^ Муссурис, Джон (1974). «Гиббсовские и марковские случайные системы со связями». Журнал статистической физики . 10 (1): 11–33. Bibcode : 1974JSP .... 10 ... 11M . DOI : 10.1007 / BF01011714 . hdl : 10338.dmlcz / 135184 . Руководство по ремонту 0432132 . S2CID 121299906 .
- ^ Гандольфи, Альберто; Ленарда, Пьетро (2016). «Заметка о гиббсовских и марковских случайных полях с ограничениями и их моментах» . Математика и механика сложных систем . 4 (3–4): 407–422. DOI : 10,2140 / memocs.2016.4.407 .
- ^ Rue, Håvard; Хелд, Леонхард (2005). Гауссовские марковские случайные поля: теория и приложения . CRC Press. ISBN 978-1-58488-432-3.
- ^ Таскар, Бенджамин; Чаталбашев, Васил; Коллер, Дафна (2004 г.), «Изучение ассоциативных сетей Маркова», в Бродли, Карла Э. (ред.), Труды Двадцать первой Международной конференции по машинному обучению (ICML 2004), Банф, Альберта, Канада, 4 июля. 8, 2004 , ACM International Conference Proceeding Series, 69 , Association for Computing Machinery , p. 102, CiteSeerX 10.1.1.157.329 , DOI : 10,1145 / 1015330,1015444 , ISBN 978-1581138283, S2CID 11312524.
- ^ Duchi, John C .; Тарлоу, Дэниел; Элидан, Гал; Коллер, Дафна (2006), «Использование комбинаторной оптимизации в рамках распространения убеждений о максимальном произведении» , в Schölkopf, Bernhard; Platt, John C .; Томас Хоффман (ред.), Труды двадцатой ежегодной конференции по системам обработки нейронной информации, Ванкувер, Британская Колумбия, Канада, 4-7 декабря 2006 г. , Достижения в системах обработки нейронной информации , 19 , MIT Press , стр. 369– 376.
- ^ Petitjean, F .; Уэбб, Г.И.; Николсон, AE (2013). Масштабирование лог-линейного анализа до данных большой размерности (PDF) . Международная конференция по интеллектуальному анализу данных. Даллас, Техас, США: IEEE.
- ^ «Два классических бумажных приза за доклады, представленные на ICML 2013» . ICML . 2013 . Проверено 15 декабря 2014 .
- ^ Киндерманн и Снелл, Росс и Лори (1980). Марковские случайные поля и их приложения . Род-Айленд: Американское математическое общество. ISBN 978-0-8218-5001-5.
- ^ Банф, Майкл; Ри, Сын Ю. (2017-02-01). «Улучшение вывода сети регуляции генов посредством интеграции данных с марковскими случайными полями» . Научные отчеты . 7 (1): 41174. Bibcode : 2017NatSR ... 741174B . DOI : 10.1038 / srep41174 . ISSN 2045-2322 . PMC 5286517 . PMID 28145456 .
- ^ Чжан и Захор, Ричард и Авидех (2014). «Автоматическая идентификация оконных областей на внутренних облаках точек с помощью LiDAR и камер». Публикации VIP Lab . CiteSeerX 10.1.1.649.303 .