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

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

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

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

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

p^*(X) = \prod^m_{j=1}f_j(X_j), где X_j = \{x_i\}_{i = 1}^n

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

p(X) = \frac{1}{Z} \prod^m_{j=1}f_j(X_j), Z = \sum_X \prod^m_{j=1}f_j(X_j)

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

  1. Задача нормализации:
найти Z = \sum_X \prod^m_{j=1}f_j(X_j)
  1. Задача маргинализации:
найти p^*_i(x_i) = \sum_{k \neq i}p^*(X)
  1. Задача нормализованной маргинализации
найти p_i(x_i) = \sum_{k \neq i}p(X)

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

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

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

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

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

p^*(X) = f_1(x_1)f_2(x_2)f_3(x_3)f_4(x_1, x_2)f_5(x_2, x_3)

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

SumProduct ExampleGraph.png

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

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

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

q_{i \to j}(x_i) = \prod_{k \in ne(i) \setminus j} r_{k \to i}(x_i) (здесь ne(i) — множество вершин, соседних с i)


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

r_{i \to j}(x_i) = \sum_{X_i \setminus x_i}(f_j(X_j) \prod_{k \in ne(i) \setminus j}q_{k \to j}(x_k)

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

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

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

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

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

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

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

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

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

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

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

p^*_i(x_i) = \prod_{j \in ne(i)}r_{j \to i}(x_i)
Z = \sum_i p^*_i(x_i), p(x_i) = \frac{1}{Z}p^*_i(x_i)

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

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

q_{i \to j}(x_i) = \alpha_{ij} \prod_{k \in ne(i) \setminus j} r_{k \to i}(x_i),

где \alpha_{ij} подобраны так, чтобы

\sum_i q_{i \to j}(x_i) = 1

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

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

p^*(X) = \prod^m_{j=1}f_j(X_j)

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

p^*(X) = \prod^m_{j=1}\phi_j(X_j) \prod^m_{i=1}\psi_i(x_i),

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

Изначально, до передачи сообщений \phi_j(X_j) = f_j(X_j) и \psi_i(x_i) = 1

Каждый раз, когда приходит сообщение r_{j \to i} из функции в переменную, \phi и \psi пересчитываются:

\psi_i(x_i) = \prod_{j \in ne(i)}r_{j \to i}(x_i),
\phi_j(X_i) = \frac{f_j(X_j)}{\prod_{i \in ne(j)}r_{j \to i}(x_i)}

Очевидно, что общее произведение от этого не меняется, а \psi_i по окончании передачи сообщений станет маргиналом p^*(x_i).

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

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