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

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

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

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

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

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

${\displaystyle 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. Задача нормализации:

найти ${\displaystyle Z=\sum _{X}\prod _{j=1}^{m}f_{j}(X_{j})}$

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

найти ${\displaystyle p_{i}^{*}(x_{i})=\sum _{k\neq i}p^{*}(X)}$

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

найти ${\displaystyle p_{i}(x_{i})=\sum _{k\neq i}p(X)}$

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

Структура графа

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

Пример

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

${\displaystyle 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})}$

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

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

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

От переменной ${\displaystyle x_{i}}$ к функции ${\displaystyle f_{j}}$:

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

От функции ${\displaystyle f_{j}}$ к переменной ${\displaystyle x_{i}}$:

${\displaystyle 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, а потом уже его модифицируют, когда до них доходят сообщения от функций.

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

Вычисление маргиналов

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

${\displaystyle p_{i}^{*}(x_{i})=\prod _{j\in ne(i)}r_{j\to i}(x_{i})}$

${\displaystyle Z=\sum _{i}p_{i}^{*}(x_{i}),p(x_{i})={\frac {1}{Z}}p_{i}^{*}(x_{i})}$

Нормализация на лету

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

${\displaystyle q_{i\to j}(x_{i})=\alpha _{ij}\prod _{k\in ne(i)\setminus j}r_{k\to i}(x_{i})}$,

где ${\displaystyle \alpha _{ij}}$ подобраны так, чтобы

${\displaystyle \sum _{i}q_{i\to j}(x_{i})=1}$

Математическое обоснование алгоритма

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

${\displaystyle p^{*}(X)=\prod _{j=1}^{m}f_{j}(X_{j})}$

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

${\displaystyle p^{*}(X)=\prod _{j=1}^{m}\phi _{j}(X_{j})\prod _{i=1}^{m}\psi _{i}(x_{i})}$,

где ${\displaystyle \phi _{j}}$ соответствует узлам-функциям, а ${\displaystyle \psi _{i}}$ — узлам-переменным.

Изначально, до передачи сообщений ${\displaystyle \phi _{j}(X_{j})=f_{j}(X_{j})}$ и ${\displaystyle \psi _{i}(x_{i})=1}$

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

${\displaystyle \psi _{i}(x_{i})=\prod _{j\in ne(i)}r_{j\to i}(x_{i})}$,

${\displaystyle \phi _{j}(X_{i})={\frac {f_{j}(X_{j})}{\prod _{i\in ne(j)}r_{j\to i}(x_{i})}}}$

Очевидно, что общее произведение от этого не меняется, а ${\displaystyle \psi _{i}}$ по окончании передачи сообщений станет маргиналом ${\displaystyle p^{*}(x_{i})}$.

Ссылки

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