Марковские случайные поля (MRF): Вероятностный вывод на графах

Марковское случайное поле — это неориентированный граф, в котором вершины представляют случайные переменные (например, срытый статус пикселя: "это фон" или "это объект"), а ребра представляют статистические зависимости между ними.

Ключевое свойство этой модели — Марковское свойство на графе: если мы выделим группу узлов A и группу узлов B, и полностью окружим их кольцом наблюдаемых узлов C, то, зная состояния узлов в барьере C, группы A и B становятся статистически независимыми. Иными словами, все влияние извне передается только через прямых соседей.

Но как алгоритмически вычислить совместную вероятность всех событий в таком графе? Эту проблему решила фундаментальная Теорема Хаммерсли-Клиффорда (1971). Она доказала, что вероятность состояния всего Марковского поля можно выразить через произведение локальных "потенциальных функций", определенных на максимальных кликах графа (полностью связанных подграфах).

Обычно вероятность задается через физическую метафору — Энергию (Модель Изинга): P(X) = (1/Z) * exp(-Energy(X)), где Z — нормализационная константа (статистическая сумма). Энергия системы складывается из двух частей:

1. Унарные потенциалы (Потенциалы узлов): насколько мы уверены в значении конкретного узла, опираясь только на его собственные данные (например, пиксель красный, значит это, скорее всего, яблоко).
2. Парные потенциалы (Потенциалы ребер): штраф за несоответствие соседей. Если два соседних пикселя принадлежат к разным классам (один фон, другой объект), энергия увеличивается (штраф). Модель стремится "сгладить" результат.

Задача алгоритма (так называемый MAP-inference) — найти конфигурацию всех переменных, которая минимизирует общую энергию системы. В компьютерном зрении MRF десятилетиями использовались для сверхточной сегментации изображений, удаления шума со старых фотографий и стереозрения (вычисления глубины резкости), успешно переводя стохастическую природу света на строгий язык комбинаторной оптимизации.