- Алгоритм sum-product
-
Алгоритм sum-product
Алгоритм «sum-product» — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе
Содержание
Постановка задачи
Рассмотрим функцию:
- , где
Чтобы получить вероятность, необходимо ее нормализовать:
Нас интересуют следующие задачи:
- 1. Задача нормализации
- найти
- 2. Задача маргинализации
- найти
- 3. Задача нормализованной маргинализации
- найти
Все эти задачи являются NP-трудными, так что сложность их решения в худшем случае возрастает экспоненциально. Однако некоторые частные случаи можно решить быстрее, чем и занимается данный алгоритм.
Структура графа
Граф, используемый алгоритмом, состоит из вершин, соответствующих переменным, и вершин, соответствующих функциям. Функции соединены с переменными, от которых они зависят.
Пример
Например функции
- p * (X) = f1(x1)f2(x2)f3(x3)f4(x1,x2)f5(x2,x3)
соответствует следующий граф:
Передача сообщений
В графе пересылаются сообщения двух видов: от функций к переменным и от переменных к функциям.
От переменной xi к функции fj:
- (здесь ne(i) — множество вершин, соседних с i)
От функции fj к переменной xi:При этом пустое произведение считаем равным единице. Из этих формул видно, что если у вершины всего один сосед, то ее сообщение можно вычислить не зная входящих сообщений.
Алгоритм
Существует два подхода, в зависимости от характера полученного графа.
Подход 1
Предположим, что граф является деревом. Начиная с листьев будем постепенно обходить все вершины и вычислять сообщения (при этом применяется стандартное правило передачи сообщений: сообщение можно передавать только если его можно полностью построить).
Тогда за количество шагов, равное диаметру графа, работа алгоритма закончится.
Подход 2
Если граф не является деревом, то можно начать с того, что все переменные передают сообщение 1, а потом уже его модифицируют, когда до них доходят сообщения от функций.
Такой алгоритм в общем случае работает неверно и делает много лишнего, но все же полезен на практике.
Вычисление маргиналов
Когда рассылка сообщений закончена, маргиналы вычисляются по следующей формуле:
Нормализация на лету
Если нужно рассчитать только нормализованные маргиналы (настоящие вероятности), то можно на каждом шаге нормализовать сообщения от переменных к функциям:
- ,
где αij подобраны так, чтобы
Математическое обоснование алгоритма
С математической точки зрения алгоритм изначальное разложение
перераскладывает в произведение
- ,
где φj соответствует узлам-функциям, а ψi — узлам-переменным.
Изначально, до передачи сообщений φj(Xj) = fj(Xj) и ψi(xi) = 1
Каждый раз, когда приходит сообщение из функции в переменную, φ и ψ пересчитываются:
- ,
Очевидно, что общее произведение от этого не меняется, а ψi по окончании передачи сообщений станет маргиналом p * (xi).
Ссылки
Wikimedia Foundation. 2010.