Алгоритм sum-product

Алгоритм «sum-product» — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе

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

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

<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>

Нас интересуют следующие задачи:

• 1. Задача нормализации

найти <math>Z = \sum_X \prod^m_{j=1}f_j(X_j)</math>

• 2. Задача маргинализации

найти <math>p^*_i(x_i) = \sum_{k \neq i}p^*(X)</math>

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

найти <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>

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

Файл:SumProduct ExampleGraph.png

Передача сообщений

В графе пересылаются сообщения двух видов: от функций к переменным и от переменных к функциям.

От переменной <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_{i \to j}(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>.

Ссылки

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