WikiSort.ru - Не сортированное

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

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

Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии.

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

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

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

Алгоритм

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

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

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

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

Ссылки

С. Николенко. Курс «Вероятностное обучение» (недоступная ссылка)