Почему вывод в Марковских случайных полях трудно?

Question

Я изучаю Марковские случайные поля и, судя по всему, вывод в MRF сложно/вычислительно дорого. В частности, книга Кевина Мерфи «Машинное обучение: вероятностная перспектива» гласит следующее:

«В первом члене мы фиксируем y на его наблюдаемые значения, иногда это называется зажатым членом. Во втором члене y является свободным; это иногда называют незакрепленным термином или контрастным термином. Обратите внимание, что вычисление незакрепленного термина требует вывода в модели, и это должно выполняться один раз на шаг градиента. Это делает обучение ненаправленным графическим моделям более жестким, чем подготовка ориентированных графических моделей ».

Почему мы здесь делаем вывод? Я понимаю, что мы суммируем все y, что кажется дорогим, но я не вижу, где мы на самом деле оцениваем любые параметры. Википедия также говорит о умозаключениях, но говорит только о вычислении условного распределения и нуждается в сумме по всем не указанным узлам. Но .. это не то, что мы здесь делаем, не так ли?

В качестве альтернативы, у любого есть хорошая интуиция о том, почему вывод в MRF затруднен?

Источники: Глава 19 МЛ: PP: https://www.cs.ubc.ca/~murphyk/MLbook/pml-print3-ch19.pdf

Конкретная раздел показано ниже

Answer 1

При подготовке вашей ХПН, вы хотите, чтобы оценить ваши параметры, \theta.

Для этого вы можете отличить функцию потерь (Уравнение 19.38) относительно \theta, установить ее в 0 и решить для \theta.

Вы не можете аналитически решить уравнение для \theta, если вы это сделаете. Тем не менее, вы можете минимизировать Уравнение 19.38 с помощью градиентного спуска. Поскольку функция потерь является выпуклой, гарантируется, что спуск градиента даст вам оптимальное по всему миру решение, когда оно сходится.

Уравнение 19.41 - это фактический градиент, который необходимо вычислить, чтобы иметь возможность выполнять градиентный спуск. Первое слагаемое легко (и вычислительно дешево) вычислять по мере суммирования по наблюдаемым значениям y. Тем не менее, второй термин требует от вас сделать вывод. В этом выражении вы не суммируете по наблюдаемому значению y, как в первом члене. Вместо этого вам нужно вычислить конфигурацию y (вывод), а затем вычислить значение потенциальной функции в этой конфигурации.