Введение

Алгоритм статистического вывода на графических моделях

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

Мотивация

При заданном конечном множестве дискретных случайных переменных с совместной функцией массы вероятности, обычной задачей является вычисление предельных распределений. Предельное распределение одной переменной определяется как

где – вектор возможных значений для , а обозначение означает, что суммирование производится по всем , у которых -я координата равна . Вычисление предельных распределений с использованием этой формулы быстро становится вычислительно невыполнимым с ростом числа переменных. Например, для 100 бинарных переменных , вычисление одного предельного распределения с использованием и вышеуказанной формулы потребует суммирования по возможным значениям для . Если известно, что функция массы вероятности факторизуется удобным образом, алгоритм распространения убеждений (belief propagation) позволяет вычислять предельные распределения гораздо эффективнее.

Точный алгоритм для деревьев

В случае, когда граф факторов является деревом, алгоритм распространения убеждений вычислит точные краевые распределения. Более того, при правильном планировании обновлений сообщений он завершится после двух полных проходов по дереву. Это оптимальное планирование можно описать следующим образом:

Перед началом граф ориентируется путем выбора одного узла в качестве корня; любой узел, не являющийся корнем и соединенный только с одним другим узлом, называется листом. На первом шаге сообщения передаются к корню: начиная с листьев, каждый узел передает сообщение по (единственному) ребру к корневому узлу. Структура дерева гарантирует, что можно получить сообщения от всех других соседних узлов до передачи сообщения. Это продолжается до тех пор, пока корень не получит сообщения от всех своих соседних узлов. Второй шаг включает передачу сообщений обратно: начиная с корня, сообщения передаются в обратном направлении. Алгоритм завершается, когда все листья получат свои сообщения.

Приблизительный алгоритм для общих графиков

Хотя алгоритм распространения убеждений был первоначально разработан для ациклических графических моделей, его можно применять и к общим графам. В этом случае алгоритм иногда называют "распространением убеждений в графах с циклами", поскольку графы обычно содержат циклы или петли. Инициализацию и порядок обновления сообщений необходимо немного скорректировать (по сравнению с ранее описанным порядком для ациклических графов), так как графы могут не содержать листьев. Вместо этого все сообщения переменных инициализируются значением 1, используются те же определения сообщений, что и выше, и все сообщения обновляются на каждой итерации (хотя сообщения, поступающие из известных листьев или подграфов, имеющих древовидную структуру, могут перестать нуждаться в обновлении после достаточного количества итераций). Легко показать, что в дереве определения сообщений этой модифицированной процедуры сходятся к набору определений сообщений, приведенных выше, за число итераций, равное диаметру дерева. Точные условия, при которых распространение убеждений в графах с циклами будет сходиться, до сих пор недостаточно изучены; известно, что на графах, содержащих единственный цикл, оно сходится в большинстве случаев, но полученные вероятности могут быть неверными. Существует несколько достаточных (но не необходимых) условий сходимости распространения убеждений в графах с циклами к единственной фиксированной точке. Существуют графы, которые не сходятся, или которые колеблются между несколькими состояниями при повторных итерациях. Методы, такие как диаграммы EXIT, могут обеспечить приблизительную визуализацию прогресса распространения убеждений и приблизительную проверку сходимости. Существуют и другие приближенные методы маргинализации, включая вариационные методы и методы Монте-Карло. Один из методов точной маргинализации в общих графах называется алгоритмом дерева соединений, который представляет собой просто распространение убеждений на модифицированном графе, гарантированно являющемся деревом. Основная идея заключается в устранении циклов путем объединения их в отдельные узлы.

Связанные с алгоритмом и сложностью вопросы

Аналогичный алгоритм обычно называют алгоритмом Витерби, но также известен как частный случай алгоритма произведения максимумов или суммы минимумов, который решает связанную задачу максимизации или поиска наиболее вероятного объяснения. Вместо попытки найти маржинальное распределение, здесь целью является определение значений, максимизирующих глобальную функцию (то есть наиболее вероятных значений в вероятностном контексте), что можно выразить с помощью arg max:

Алгоритм, решающий эту задачу, почти идентичен алгоритму распространения убеждений, за исключением того, что суммы заменяются на максимумы в определениях. Важно отметить, что задачи вывода, такие как маргинализация и максимизация, сложно точно и приближённо решить в графической модели (по крайней мере, с точки зрения относительной погрешности). Более точно, задача маргинализации, определённая выше, является #P-полной, а задача максимизации – NP-полной. Объём используемой памяти в алгоритме распространения убеждений можно уменьшить, используя алгоритм "острова" (с незначительным увеличением временной сложности).

Обобщенная пропаганда убеждений (GBP)

Алгоритмы распространения убеждений обычно представляются в виде уравнений обновления сообщений на фактор-графе, включающих сообщения между переменными и соседними узлами факторов и наоборот. Рассмотрение сообщений между областями в графе является одним из способов обобщения алгоритма распространения убеждений и известно как метод кластерной вариации Кикучи. Улучшение производительности алгоритмов распространения убеждений также достигается за счет нарушения симметрии реплик в распределениях полей (сообщений). Это обобщение приводит к новому типу алгоритма, называемому алгоритмом распространения опроса (SP), который оказался очень эффективным при решении NP-полных задач, таких как задача выполнимости булевых формул и раскраска графа. Метод кластерной вариации и алгоритмы распространения опроса – это два различных улучшения алгоритма распространения убеждений. Название "обобщенное распространение опроса" (GSP) пока не присвоено алгоритму, объединяющему оба обобщения.