ФЭНДОМ


Шаблон:Сирота

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

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

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

$ p^*(X) = \prod^m_{j=1}f_j(X_j) $, где $ X_j = \{x_i\}_{i = 1}^n $

Чтобы получить вероятность, необходимо ее нормализовать:

$ p(X) = \frac{1}{Z} \prod^m_{j=1}f_j(X_j), Z = \sum_X \prod^m_{j=1}f_j(X_j) $

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

найти $ Z = \sum_X \prod^m_{j=1}f_j(X_j) $
найти $ p^*_i(x_i) = \sum_{k \neq i}p^*(X) $
  • 3. Задача нормализованной маргинализации
найти $ p_i(x_i) = \sum_{k \neq i}p(X) $

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

Структура графа Править

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

Пример Править

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

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

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

Файл: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_{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) $

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

Алгоритм Править

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

Подход 1 Править

Предположим, что граф является деревом. Начиная с листьев будем постепенно обходить все вершины и вычислять сообщения (при этом применяется стандартное правило передачи сообщений: сообщение можно передавать только если его можно полностью построить).

Тогда за количество шагов, равное диаметру графа, работа алгоритма закончится.

Подход 2 Править

Если граф не является деревом, то можно начать с того, что все переменные передают сообщение 1, а потом уже его модифицируют, когда до них доходят сообщения от функций.

Такой алгоритм в общем случае работает неверно и делает много лишнего, но все же полезен на практике.

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

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

$ p^*_i(x_i) = \prod_{j \in ne(i)}r_{j \to i}(x_i) $
$ Z = \sum_i p^*_i(x_i), p(x_i) = \frac{1}{Z}p^*_i(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^*(X) = \prod^m_{j=1}f_j(X_j) $

перераскладывает в произведение

$ p^*(X) = \prod^m_{j=1}\phi_j(X_j) \prod^m_{i=1}\psi_i(x_i) $,

где $ \phi_j $ соответствует узлам-функциям, а $ \psi_i $ — узлам-переменным.

Изначально, до передачи сообщений $ \phi_j(X_j) = f_j(X_j) $ и $ \psi_i(x_i) = 1 $

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

$ \psi_i(x_i) = \prod_{j \in ne(i)}r_{j \to i}(x_i) $,
$ \phi_j(X_i) = \frac{f_j(X_j)}{\prod_{i \in ne(j)}r_{j \to i}(x_i)} $

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

Ссылки Править

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

Шаблон:Нет интервики