Русская Википедия:Алгоритм распространения доверия
Алгоритм распространения доверия (Шаблон:Lang-en, также алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях (таких как байесовские и марковские сети). Предложен Дж. Перлом в 1982 году.
Постановка задачи
Шаблон:Стиль Рассмотрим функцию:
- <math>p^*(X) = \prod^m_{j=1}f_j(X_j)</math>, где <math>X_j = \{x_i\}_{i = 1}^n</math>
Чтобы получить вероятность, необходимо её нормализовать:
- <math>p(X) = \frac{1}{Z} \prod^m_{j=1}f_j(X_j), Z = \sum_X \prod^m_{j=1}f_j(X_j)</math>
Рассматриваются следующие задачи:
- Задача нормализации:
- найти <math>Z = \sum_X \prod^m_{j=1}f_j(X_j)</math>
- Задача маргинализации:
- найти <math>p^*_i(x_i) = \sum_{k \neq i}p^*(X)</math>
- Задача нормализованной маргинализации
- найти <math>p_i(x_i) = \sum_{k \neq i}p(X)</math>
Все эти задачи NP-полны, так что сложность их решения в худшем случае возрастает экспоненциально. Однако некоторые частные случаи можно решить быстрее, чем и занимается данный алгоритм.
Структура графа
Граф, используемый алгоритмом, состоит из вершин, соответствующих переменным, и вершин, соответствующих функциям. Функции соединены с переменными, от которых они зависят.
Пример
Например, функции
- <math>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)</math>
соответствует следующий граф:
Передача сообщений
В графе пересылаются сообщения двух видов: от функций к переменным и от переменных к функциям.
От переменной <math>x_i</math> к функции <math>f_j</math>:
- <math>q_{i \to j}(x_i) = \prod_{k \in ne(i) \setminus j} r_{k \to i}(x_i)</math> (здесь <math>ne(i)</math> — множество вершин, соседних с i)
От функции <math>f_j</math> к переменной <math>x_i</math>:
- <math>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)</math>
При этом пустое произведение считаем равным единице. Из этих формул видно, что если у вершины всего одна соседняя точка, то её (вершины) сообщение можно вычислить, не зная входящих сообщений.
Алгоритм
Существует два подхода, в зависимости от характера полученного графа:
Подход 1
Предположим, что граф является деревом. Начиная с листьев будем постепенно обходить все вершины и вычислять сообщения (при этом применяется стандартное правило передачи сообщений: сообщение можно передавать только в том случае, если его можно полностью построить).
Тогда за количество шагов, равное диаметру графа, работа алгоритма закончится.
Подход 2
Если граф не является деревом, то можно начать с того, что все переменные передают сообщение 1, а потом уже его модифицируют, когда до них доходят сообщения от функций.
Такой алгоритм в общем случае работает неверно и делает много лишнего, но все же полезен на практике.
Вычисление маргиналов
Когда рассылка сообщений закончена, маргиналы вычисляются по следующей формуле:
- <math>p^*_i(x_i) = \prod_{j \in ne(i)}r_{j \to i}(x_i)</math>
- <math>Z = \sum_i p^*_i(x_i), p(x_i) = \frac{1}{Z}p^*_i(x_i)</math>
Нормализация на лету
Если нужно рассчитать только нормализованные маргиналы (настоящие вероятности), то можно на каждом шаге нормализовать сообщения от переменных к функциям:
- <math>q_{i \to j}(x_i) = \alpha_{ij} \prod_{k \in ne(i) \setminus j} r_{k \to i}(x_i)</math>,
где <math>\alpha_{ij}</math> подобраны так, чтобы
- <math>\sum_i q_{i \to j}(x_i) = 1</math>
Математическое обоснование алгоритма
С математической точки зрения алгоритм перераскладывает изначальное разложение:
- <math>p^*(X) = \prod^m_{j=1}f_j(X_j)</math>
в произведение:
- <math>p^*(X) = \prod^m_{j=1}\phi_j(X_j) \prod^m_{i=1}\psi_i(x_i)</math>,
где <math>\phi_j</math> соответствует узлам-функциям, а <math>\psi_i</math> — узлам-переменным.
Изначально, до передачи сообщений <math>\phi_j(X_j) = f_j(X_j)</math> и <math>\psi_i(x_i) = 1</math>
Каждый раз, когда приходит сообщение <math>r_{j \to i}</math> из функции в переменную, <math>\phi</math> и <math>\psi</math> пересчитываются:
- <math>\psi_i(x_i) = \prod_{j \in ne(i)}r_{j \to i}(x_i)</math>,
- <math>\phi_j(X_i) = \frac{f_j(X_j)}{\prod_{i \in ne(j)}r_{j \to i}(x_i)}</math>
Очевидно, что общее произведение от этого не меняется, а <math>\psi_i</math> по окончании передачи сообщений станет маргиналом <math>p^*(x_i)</math>.
Ссылки
С. Николенко. Курс «Вероятностное обучение»
