Вопрос, как написано в названиипочему точный вывод о MRF в сетке графика невозможно
Существует 3х3 сетки график на изображении выше. Мы можем преобразовать его в дерево соединений. Тогда для вывода можно использовать передачу сообщений (алгоритм продукта-суммы) (оценка правдоподобия/заднего и т. Д.). Поэтому я удивляюсь, почему точный вывод в графике сетки так тяжел?
Невозможно найти такое дерево соединений, когда сетка будет больше?
Короткий ответ: для сетки nxn сложность не менее экспоненциальна.
Дерево соединений создается из индуцированного графика MRF, который зависит от порядка исключения (какие переменные вы сначала исключаете для вычисления маргинального номера). Стоимость исключения экспоненциальна по размеру самой большой клики на индуцированном графике. Подробнее см. В статье this.
Таким образом, хотя мы можем использовать точный вывод в дереве соединений, сложность будет экспоненциальной по размеру самой большой клики на индуцированном графике используемого порядка исключения.
Наилучший возможный порядок уничтожения даст наибольший размер клики, равный ширине дерева, который равен n для сетки nxn. Но нет эффективных алгоритмов для его поиска.