Викия

Математика

Алгоритм sum-product

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

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

Алгоритм «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).

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

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

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

Викия-сеть

Случайная вики