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

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

Постановка задачи

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

$p^{*}(X)=\prod _{j=1}^{m}f_{j}(X_{j})$, где $X_{j}=\{x_{i}\}_{i=1}^{n}$

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

$p(X)={\frac {1}{Z}}\prod _{j=1}^{m}f_{j}(X_{j}),Z=\sum _{X}\prod _{j=1}^{m}f_{j}(X_{j})$

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

1. Задача нормализации:

найти $Z=\sum _{X}\prod _{j=1}^{m}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})$

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

Передача сообщений

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

От переменной $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_{j\to i}(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 _{j=1}^{m}f_{j}(X_{j})$

в произведение:

$p^{*}(X)=\prod _{j=1}^{m}\phi _{j}(X_{j})\prod _{i=1}^{m}\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})$.

Ссылки

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