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

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

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

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

$p^{\ast <!--\; \ast \; -->}(X)=\underset{j=1}{\overset{m}{\prod <!--\; \prod \; -->}}{f}_j(X_j)$$p^{*}(X)=\prod _{j=1}^{m}f_{j}(X_{j})$ , где $X_j=\{x_i{\}}_{i=1}^n$$X_{j}=\{x_{i}\}_{i=1}^{n}$ 

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

$p(X)=\frac{1}{Z}\underset{j=1}{\overset{m}{\prod <!--\; \prod \; -->}}{f}_j(X_j),Z=\underset{X}{\sum <!--\; \sum \; -->}\underset{j=1}{\overset{m}{\prod <!--\; \prod \; -->}}{f}_j(X_j)$$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=\underset{X}{\sum <!--\; \sum \; -->}\underset{j=1}{\overset{m}{\prod <!--\; \prod \; -->}}{f}_j(X_j)$$Z=\sum _{X}\prod _{j=1}^{m}f_{j}(X_{j})$ 

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

найти $p_i^{\ast <!--\; \ast \; -->}(x_i)=\underset{k\ne <!--\; \ne \; -->i}{\sum <!--\; \sum \; -->}{p}^{\ast <!--\; \ast \; -->}(X)$$p_{i}^{*}(x_{i})=\sum _{k\neq i}p^{*}(X)$ 

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

найти $p_i(x_i)=\underset{k\ne <!--\; \ne \; -->i}{\sum <!--\; \sum \; -->}p(X)$$p_{i}(x_{i})=\sum _{k\neq i}p(X)$ 

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

Структура графаПравить

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

ПримерПравить

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

$p^{\ast <!--\; \ast \; -->}(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)$$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$$x_{i}$  к функции $f_j$$f_{j}$ :

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

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

$r_{j\to <!--\; \to \; -->i}(x_i)=\underset{X_i\setminus <!--\; \setminus \; -->x_i}{\sum <!--\; \sum \; -->}(f_j(X_j)\underset{k\in <!--\; \in \; -->ne(i)\setminus <!--\; \setminus \; -->j}{\prod <!--\; \prod \; -->}{q}_{k\to <!--\; \to \; -->j}(x_k)$$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^{\ast <!--\; \ast \; -->}(x_i)=\underset{j\in <!--\; \in \; -->ne(i)}{\prod <!--\; \prod \; -->}{r}_{j\to <!--\; \to \; -->i}(x_i)$$p_{i}^{*}(x_{i})=\prod _{j\in ne(i)}r_{j\to i}(x_{i})$ 

$Z=\underset{i}{\sum <!--\; \sum \; -->}{p}_i^{\ast <!--\; \ast \; -->}(x_i),p(x_i)=\frac{1}{Z}{p}_i^{\ast <!--\; \ast \; -->}(x_i)$$Z=\sum _{i}p_{i}^{*}(x_{i}),p(x_{i})={\frac {1}{Z}}p_{i}^{*}(x_{i})$ 

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

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

$q_{i\to <!--\; \to \; -->j}(x_i)={\mathrm{\alpha <!--\; \alpha \; -->}}_{ij}\underset{k\in <!--\; \in \; -->ne(i)\setminus <!--\; \setminus \; -->j}{\prod <!--\; \prod \; -->}{r}_{k\to <!--\; \to \; -->i}(x_i)$$q_{i\to j}(x_{i})=\alpha _{ij}\prod _{k\in ne(i)\setminus j}r_{k\to i}(x_{i})$ ,

где ${\mathrm{\alpha <!--\; \alpha \; -->}}_{ij}$$\alpha _{ij}$  подобраны так, чтобы

$\underset{i}{\sum <!--\; \sum \; -->}{q}_{i\to <!--\; \to \; -->j}(x_i)=1$$\sum _{i}q_{i\to j}(x_{i})=1$ 

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

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

$p^{\ast <!--\; \ast \; -->}(X)=\underset{j=1}{\overset{m}{\prod <!--\; \prod \; -->}}{f}_j(X_j)$$p^{*}(X)=\prod _{j=1}^{m}f_{j}(X_{j})$ 

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

$p^{\ast <!--\; \ast \; -->}(X)=\underset{j=1}{\overset{m}{\prod <!--\; \prod \; -->}}{\mathrm{\varphi <!--\; \varphi \; -->}}_j(X_j)\underset{i=1}{\overset{m}{\prod <!--\; \prod \; -->}}{\mathrm{\psi <!--\; \psi \; -->}}_i(x_i)$$p^{*}(X)=\prod _{j=1}^{m}\phi _{j}(X_{j})\prod _{i=1}^{m}\psi _{i}(x_{i})$ ,

где ${\mathrm{\varphi <!--\; \varphi \; -->}}_j$$\phi _{j}$  соответствует узлам-функциям, а ${\mathrm{\psi <!--\; \psi \; -->}}_i$$\psi _{i}$  — узлам-переменным.

Изначально, до передачи сообщений ${\mathrm{\varphi <!--\; \varphi \; -->}}_j(X_j)=f_j(X_j)$$\phi _{j}(X_{j})=f_{j}(X_{j})$  и ${\mathrm{\psi <!--\; \psi \; -->}}_i(x_i)=1$$\psi _{i}(x_{i})=1$ 

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

${\mathrm{\psi <!--\; \psi \; -->}}_i(x_i)=\underset{j\in <!--\; \in \; -->ne(i)}{\prod <!--\; \prod \; -->}{r}_{j\to <!--\; \to \; -->i}(x_i)$$\psi _{i}(x_{i})=\prod _{j\in ne(i)}r_{j\to i}(x_{i})$ ,

${\mathrm{\varphi <!--\; \varphi \; -->}}_j(X_i)=\frac{f_j(X_j)}{\underset{i\in <!--\; \in \; -->ne(j)}{\prod <!--\; \prod \; -->}{r}_{j\to <!--\; \to \; -->i}(x_i)}$$\phi _{j}(X_{i})={\frac {f_{j}(X_{j})}{\prod _{i\in ne(j)}r_{j\to i}(x_{i})}}$ 

Очевидно, что общее произведение от этого не меняется, а ${\mathrm{\psi <!--\; \psi \; -->}}_i$$\psi _{i}$  по окончании передачи сообщений станет маргиналом $p^{\ast <!--\; \ast \; -->}(x_i)$$p^{*}(x_{i})$ .

СсылкиПравить

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