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

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

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

Шаблон:Стиль статьи Рассмотрим функцию:

$p^{\ast }(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^{\ast }(x_i)=\sum _{k\ne i}{p}^{\ast }(X)$

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

найти $p_i(x_i)=\sum _{k\ne i}p(X)$

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

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

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

Пример

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

$p^{\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)$

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

Файл: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_{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 }(x_i)=\prod _{j\in ne(i)}{r}_{j\to i}(x_i)$

$Z=\sum _i{p}_i^{\ast }(x_i),p(x_i)=\frac{1}{Z}{p}_i^{\ast }(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^{\ast }(X)=\prod _{j=1}^m{f}_j(X_j)$

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

$p^{\ast }(X)=\prod _{j=1}^m{\varphi }_j(X_j)\prod _{i=1}^m{\psi }_i(x_i)$,

где ${\varphi }_j$ соответствует узлам-функциям, а ${\psi }_i$ — узлам-переменным.

Изначально, до передачи сообщений ${\varphi }_j(X_j)=f_j(X_j)$ и ${\psi }_i(x_i)=1$

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

${\psi }_i(x_i)=\prod _{j\in ne(i)}{r}_{j\to i}(x_i)$,

${\varphi }_j(X_i)=\frac{f_j(X_j)}{\prod _{i\in ne(j)}{r}_{j\to i}(x_i)}$

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

Ссылки

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