Алгоритм распространения доверия

Алгоритм распространения доверия (англ. belief propagation, также алгоритм «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>

1. Задача маргинализации:

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

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

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

Ссылки

[logic.pdmi.ras.ru/~sergey/index.php?page=mlbayes С. Николенко. Курс «Вероятностное обучение»]

Отрывок, характеризующий Алгоритм распространения доверия

Вечер Анны Павловны был пущен. Веретена с разных сторон равномерно и не умолкая шумели. Кроме ma tante, около которой сидела только одна пожилая дама с исплаканным, худым лицом, несколько чужая в этом блестящем обществе, общество разбилось на три кружка. В одном, более мужском, центром был аббат; в другом, молодом, красавица княжна Элен, дочь князя Василия, и хорошенькая, румяная, слишком полная по своей молодости, маленькая княгиня Болконская. В третьем Мортемар и Анна Павловна.
Виконт был миловидный, с мягкими чертами и приемами, молодой человек, очевидно считавший себя знаменитостью, но, по благовоспитанности, скромно предоставлявший пользоваться собой тому обществу, в котором он находился. Анна Павловна, очевидно, угощала им своих гостей. Как хороший метрд`отель подает как нечто сверхъестественно прекрасное тот кусок говядины, который есть не захочется, если увидать его в грязной кухне, так в нынешний вечер Анна Павловна сервировала своим гостям сначала виконта, потом аббата, как что то сверхъестественно утонченное. В кружке Мортемара заговорили тотчас об убиении герцога Энгиенского. Виконт сказал, что герцог Энгиенский погиб от своего великодушия, и что были особенные причины озлобления Бонапарта.
– Ah! voyons. Contez nous cela, vicomte, [Расскажите нам это, виконт,] – сказала Анна Павловна, с радостью чувствуя, как чем то a la Louis XV [в стиле Людовика XV] отзывалась эта фраза, – contez nous cela, vicomte.
Виконт поклонился в знак покорности и учтиво улыбнулся. Анна Павловна сделала круг около виконта и пригласила всех слушать его рассказ.
– Le vicomte a ete personnellement connu de monseigneur, [Виконт был лично знаком с герцогом,] – шепнула Анна Павловна одному. – Le vicomte est un parfait conteur [Bиконт удивительный мастер рассказывать], – проговорила она другому. – Comme on voit l'homme de la bonne compagnie [Как сейчас виден человек хорошего общества], – сказала она третьему; и виконт был подан обществу в самом изящном и выгодном для него свете, как ростбиф на горячем блюде, посыпанный зеленью.
Виконт хотел уже начать свой рассказ и тонко улыбнулся.
– Переходите сюда, chere Helene, [милая Элен,] – сказала Анна Павловна красавице княжне, которая сидела поодаль, составляя центр другого кружка.
Княжна Элен улыбалась; она поднялась с тою же неизменяющеюся улыбкой вполне красивой женщины, с которою она вошла в гостиную. Слегка шумя своею белою бальною робой, убранною плющем и мохом, и блестя белизною плеч, глянцем волос и брильянтов, она прошла между расступившимися мужчинами и прямо, не глядя ни на кого, но всем улыбаясь и как бы любезно предоставляя каждому право любоваться красотою своего стана, полных плеч, очень открытой, по тогдашней моде, груди и спины, и как будто внося с собою блеск бала, подошла к Анне Павловне. Элен была так хороша, что не только не было в ней заметно и тени кокетства, но, напротив, ей как будто совестно было за свою несомненную и слишком сильно и победительно действующую красоту. Она как будто желала и не могла умалить действие своей красоты. Quelle belle personne! [Какая красавица!] – говорил каждый, кто ее видел.
Как будто пораженный чем то необычайным, виконт пожал плечами и о опустил глаза в то время, как она усаживалась перед ним и освещала и его всё тою же неизменною улыбкой.
– Madame, je crains pour mes moyens devant un pareil auditoire, [Я, право, опасаюсь за свои способности перед такой публикой,] сказал он, наклоняя с улыбкой голову.
Княжна облокотила свою открытую полную руку на столик и не нашла нужным что либо сказать. Она улыбаясь ждала. Во все время рассказа она сидела прямо, посматривая изредка то на свою полную красивую руку, которая от давления на стол изменила свою форму, то на еще более красивую грудь, на которой она поправляла брильянтовое ожерелье; поправляла несколько раз складки своего платья и, когда рассказ производил впечатление, оглядывалась на Анну Павловну и тотчас же принимала то самое выражение, которое было на лице фрейлины, и потом опять успокоивалась в сияющей улыбке. Вслед за Элен перешла и маленькая княгиня от чайного стола.