Почему точный вывод MRF в графе сетки невозможен

Question

Почему точный вывод MRF в графе сетки невозможен

Вопрос как написано в заголовке

На изображении выше представлен график сетки 3х3. Мы можем преобразовать его в дерево соединений. Затем можно использовать передачу сообщений (алгоритм суммы продукта) для вывода (оценка вероятности / апостериора и т. Д.). Поэтому мне интересно, почему точный вывод в графе сетки так сложен?

Разве невозможно найти такое дерево соединений, когда сетка становится больше?

1

machine-learning inference message-passing markov-random-fields

Источник

user5543312 20 янв '17 в 12:07

1 ответ

Другие вопросы по тегам machine-learning inference message-passing markov-random-fields

user5433494 22 май '17 в 14:57 2017-05-22 14:57 · Answer 1 · 2017-05-22 14:57

Краткий ответ: для сетки nxn сложность по меньшей мере экспоненциальна n.

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

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

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