Введение

Набор случайных переменных

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

Вывод

Как и в байесовской сети, можно вычислить условное распределение набора узлов, задав значения другому набору узлов в марковском случайном поле, путем суммирования по всем возможным назначениям значений оставшимся узлам. Это называется точным выводом. Однако точный вывод является задачей, полной по классу #P, и, следовательно, вычислительно неразрешимой в общем случае. Методы приближения, такие как метод Монте-Карло Марковских цепей и алгоритм распространения убеждений, часто более применимы на практике. Некоторые специфические подклассы МРП, такие как деревья (см. дерево Чоу–Лю), имеют алгоритмы вывода, работающие за полиномиальное время; поиск таких подклассов – активная область исследований. Существуют также подклассы МРП, позволяющие эффективно выполнять вывод MAP, или находить наиболее вероятное назначение; примерами таких подклассов являются ассоциативные сети. Другим интересным подклассом являются разложимые модели (когда граф является хордальным): благодаря наличию аналитической формулы для оценки максимального правдоподобия, можно определить согласованную структуру для сотен переменных.

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

Одним из заметных вариантов случайного поля Маркова является условное случайное поле, в котором каждая случайная переменная может также зависеть от набора глобальных наблюдений. В этой модели каждая функция является отображением всех возможных присвоений значений как клике k, так и наблюдениям в неотрицательные вещественные числа. Эта форма марковской сети может быть более подходящей для построения дискриминационных классификаторов, которые не моделируют распределение вероятностей над наблюдениями. Условные случайные поля (CRF) были предложены Джоном Д. Лафферти, Эндрю Маккалумом и Фернандо К. Н. Перейрой в 2001 году.

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

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