Алгоритм распространения доверия

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм распространения доверия (англ. belief propagation, также алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях (таких как байесовские и марковские сети).

Постановка задачи[править | править вики-текст]

Рассмотрим функцию:

, где

Чтобы получить вероятность, необходимо её нормализовать:

Рассматриваются следующие задачи:

  1. Задача нормализации:
найти
  1. Задача маргинализации:
найти
  1. Задача нормализованной маргинализации
найти

Все эти задачи NP-полны, так что сложность их решения в худшем случае возрастает экспоненциально. Однако некоторые частные случаи можно решить быстрее, чем и занимается данный алгоритм.

Структура графа[править | править вики-текст]

Граф, используемый алгоритмом, состоит из вершин, соответствующих переменным, и вершин, соответствующих функциям. Функции соединены с переменными, от которых они зависят.

Пример[править | править вики-текст]

Например функции

соответствует следующий граф:

SumProduct ExampleGraph.png

Передача сообщений[править | править вики-текст]

В графе пересылаются сообщения двух видов: от функций к переменным и от переменных к функциям.

От переменной к функции :

(здесь  — множество вершин, соседних с i)


От функции к переменной :

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

Алгоритм[править | править вики-текст]

Существует два подхода, в зависимости от характера полученного графа.

Подход 1[править | править вики-текст]

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

Тогда за количество шагов, равное диаметру графа, работа алгоритма закончится.

Подход 2[править | править вики-текст]

Если граф не является деревом, то можно начать с того, что все переменные передают сообщение 1, а потом уже его модифицируют, когда до них доходят сообщения от функций.

Такой алгоритм в общем случае работает неверно и делает много лишнего, но все же полезен на практике.

Вычисление маргиналов[править | править вики-текст]

Когда рассылка сообщений закончена, маргиналы вычисляются по следующей формуле:

Нормализация на лету[править | править вики-текст]

Если нужно рассчитать только нормализованные маргиналы (настоящие вероятности), то можно на каждом шаге нормализовать сообщения от переменных к функциям:

,

где подобраны так, чтобы

Математическое обоснование алгоритма[править | править вики-текст]

С математической точки зрения алгоритм изначальное разложение:

перераскладывает в произведение:

,

где соответствует узлам-функциям, а  — узлам-переменным.

Изначально, до передачи сообщений и

Каждый раз, когда приходит сообщение из функции в переменную, и пересчитываются:

,

Очевидно, что общее произведение от этого не меняется, а по окончании передачи сообщений станет маргиналом .

Ссылки[править | править вики-текст]

С. Николенко. Курс «Вероятностное обучение»