Распространение убеждений

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

Алгоритм был впервые предложен Джудеей Перл в 1982 году. который сформулировал его как точный алгоритм вывода на деревьях , позже расширенный до полидеревьев . Хотя алгоритм не является точным на общих графах, было показано, что он является полезным приближенным алгоритмом.

Мотивация

Учитывая конечный набор дискретных случайных величин $X_{1},\ldots ,X_{n}$ с совместной функцией вероятностной массы $p$, общей задачей является вычисление маргинальных распределений $X_{i}$. Маргинал одного $X_{i}$ определяется как

$p_{X_{i}}(x_{i})=\sum _{\mathbf {x} ':x'_{i}=x_{i}}p(\mathbf {x} ')$

где $\mathbf {x} '=(x'_{1},\ldots ,x'_{n})$ представляет собой вектор возможных значений для $X_{i}$, и обозначение $\mathbf {x} ':x'_{i}=x_{i}$ означает, что сумма берется по тем $\mathbf {x} '$ чей $i$-я координата равна $x_{i}$.

Вычисление маргинальных распределений с использованием этой формулы быстро становится вычислительно непомерно трудным по мере роста числа переменных. Например, дано 100 двоичных переменных $X_{1},\ldots ,X_{100}$, вычисляя один предел $X_{i}$ с использованием $p$ и приведенная выше формула будет включать суммирование по $2^{99}\approx 6.34\times 10^{29}$ возможные значения для $\mathbf {x} '$. Если известно, что функция массы вероятности $p$ факторы в удобном виде, распространение убеждений позволяет вычислять маргинальные значения гораздо более эффективно.

Описание алгоритма суммирования произведений

Варианты алгоритма распространения доверия существуют для нескольких типов графических моделей ( байесовские сети и марковские случайные поля). в частности). Здесь мы описываем вариант, который работает с факторным графом . Факторный граф — это двудольный граф, содержащий узлы, соответствующие переменным. $V$ и факторы $F$, с границами между переменными и факторами, в которых они появляются. Мы можем написать совместную массовую функцию:

$p(\mathbf {x} )=\prod _{a\in F}f_{a}(\mathbf {x} _{a})$

где $\mathbf {x} _{a}$ - вектор соседних узлов переменных с узлом фактора $a$. Любую байесовскую сеть или марковское случайное поле можно представить в виде графа факторов, используя фактор для каждого узла с его родителями или фактор для каждого узла с его окрестностями соответственно.

Алгоритм работает путем передачи действительных функций, называемых сообщениями, по краям между скрытыми узлами. Точнее, если $v$ является переменным узлом и $a$ является фактором-узлом, связанным с $v$ в графе коэффициентов, то сообщения $\mu _{v\to a}$ от $v$ к $a$ и сообщения $\mu _{a\to v}$ от $a$ к $v$ являются действительными функциями $\mu _{v\to a},\mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R}$, областью действия которого является набор значений, которые может принимать случайная величина, связанная с $v$, обозначенный $\operatorname {Dom} (v)$. Эти сообщения содержат «влияние», которое одна переменная оказывает на другую. Сообщения вычисляются по-разному в зависимости от того, является ли узел, получающий сообщение, узлом переменной или узлом фактора. Сохраняя те же обозначения:

• Сообщение $\mu _{v\to a}:\operatorname {Dom} (v)\to \mathbb {R}$ из переменного узла $v$ к факторному узлу $a$ определяется $$\mu _{v\to a}(x_{v})=\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v})$$для $x_{v}\in \operatorname {Dom} (v)$, где $N(v)$ - это набор соседних факторных узлов $v$. Если $N(v)\setminus \{a\}$ тогда пусто $\mu _{v\to a}(x_{v})$ установлено равномерное распределение по $\operatorname {Dom} (v)$.

• Сообщение $\mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R}$ из факторного узла $a$ к переменному узлу $v$ определяется как произведение коэффициента с сообщениями от всех других узлов, маргинализированное по всем переменным, кроме той, которая связана с $v$, $$\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}\left(f_{a}(\mathbf {x} '_{a})\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}})\right)$$для $x_{v}\in \operatorname {Dom} (v)$, где $N(a)$ - это набор соседних (переменных) узлов для $a$. Если $N(a)\setminus \{v\}$ пусто, то $\mu _{a\to v}(x_{v})=f_{a}(x_{v})$, поскольку в этом случае $x_{v}=x_{a}$.

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

При типичном запуске каждое сообщение будет итеративно обновляться от предыдущего значения соседних сообщений. Для обновления сообщений можно использовать различное планирование. В случае, когда графическая модель представляет собой дерево, оптимальное планирование сходится после вычисления каждого сообщения ровно один раз (см. следующий подраздел). Когда граф факторов имеет циклы, такого оптимального планирования не существует, и типичным выбором является обновление всех сообщений одновременно на каждой итерации.

После сходимости (если сходимость произошла) предполагаемое предельное распределение каждого узла пропорционально произведению всех сообщений от соседних факторов (без константы нормализации):

$p_{X_{v}}(x_{v})\propto \prod _{a\in N(v)}\mu _{a\to v}(x_{v}).$

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

$p_{X_{a}}(\mathbf {x} _{a})\propto f_{a}(\mathbf {x} _{a})\prod _{v\in N(a)}\mu _{v\to a}(x_{v}).$

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

Точный алгоритм для деревьев

В случае, когда граф фактора представляет собой дерево , алгоритм распространения доверия вычисляет точные маргинальные значения. Более того, при правильном планировании обновлений сообщений они прекратятся после двух полных проходов по дереву. Оптимальное планирование можно описать следующим образом:

Прежде чем начать, граф ориентируется, назначая один узел корнем ; любой некорневой узел, который соединен только с одним другим узлом, называется листом .

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

Второй шаг включает передачу сообщений обратно: начиная с корня, сообщения передаются в обратном направлении. Алгоритм завершается, когда все листья получили свои сообщения.

Примерный алгоритм для общих графов

Хотя алгоритм Belief Propagation изначально был разработан для ациклических графических моделей, его можно использовать и в общих графах . Алгоритм иногда называют циклическим распространением убеждений , поскольку графы обычно содержат циклы или циклы. Инициализацию и планирование обновлений сообщений необходимо немного скорректировать (по сравнению с ранее описанным расписанием для ациклических графов), поскольку графы могут не содержать листьев. Вместо этого все переменные сообщения инициализируются значением 1 и используются те же определения сообщений, что и выше, обновляя все сообщения на каждой итерации (хотя сообщения, поступающие из известных листьев или подграфов с древовидной структурой, могут больше не нуждаться в обновлении после достаточного количества итераций). Легко показать, что в дереве определения сообщений этой модифицированной процедуры будут сходиться к множеству определений сообщений, приведенному выше, за количество итераций, равное диаметру дерева .

Точные условия, при которых будет сходиться запутанное распространение убеждений, до сих пор не совсем понятны; известно, что на графах, содержащих одну петлю, она в большинстве случаев сходится, однако полученные вероятности могут быть неверными. Существует несколько достаточных (но не необходимых) условий сходимости циклического распространения убеждений к единственной фиксированной точке. Существуют графы, которые не могут сходиться или которые будут колебаться между несколькими состояниями при повторяющихся итерациях. Такие методы, как диаграммы EXIT, могут обеспечить приблизительную визуализацию хода распространения убеждений и приблизительный тест на сходимость.

Существуют и другие приближенные методы маргинализации, включая вариационные методы и методы Монте-Карло .

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

Связанные проблемы алгоритма и сложности

Подобный алгоритм обычно называют алгоритмом Витерби , но он также известен как частный случай алгоритма максимального произведения или минимальной суммы, который решает соответствующую проблему максимизации или наиболее вероятного объяснения. Вместо того, чтобы пытаться решить маргинальную задачу, цель здесь состоит в том, чтобы найти значения $\mathbf {x}$ который максимизирует глобальную функцию (т.е. наиболее вероятные значения в вероятностных условиях), и его можно определить с помощью arg max :

$\operatorname {*} {\arg \max }_{\mathbf {x} }g(\mathbf {x} ).$

Алгоритм, решающий эту проблему, почти идентичен алгоритму распространения убеждений, с заменой сумм в определениях на максимумы.

Стоит отметить, что задачи вывода, такие как маргинализация и максимизация, NP-трудно решить точно и приблизительно (по крайней мере, для относительной ошибки ) в графической модели. Точнее, определенная выше проблема маргинализации является #P-полной , а максимизация — NP-полной .

Использование памяти для распространения убеждений можно уменьшить за счет использования алгоритма острова (при небольших затратах по времени).

Отношение к свободной энергии

Алгоритм суммы произведений связан с расчетом свободной энергии в термодинамике . Пусть Z — статистическая сумма . Распределение вероятностей

$P(\mathbf {X} )={\frac {1}{Z}}\prod _{f_{j}}f_{j}(x_{j})$

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

$E(\mathbf {X} )=-\log \prod _{f_{j}}f_{j}(x_{j}).$

Тогда свободная энергия системы равна

$F=U-H=\sum _{\mathbf {X} }P(\mathbf {X} )E(\mathbf {X} )+\sum _{\mathbf {X} }P(\mathbf {X} )\log P(\mathbf {X} ).$

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

Обобщенное распространение убеждений (GBP)

Алгоритмы распространения убеждений обычно представляются как уравнения обновления сообщений на графе факторов, включающие сообщения между узлами переменных и соседними узлами факторов и наоборот. Рассмотрение сообщений между регионами в графе — это один из способов обобщения алгоритма распространения доверия. Существует несколько способов определения набора регионов в графе, которые могут обмениваться сообщениями. Один из методов использует идеи, представленные Кикучи в физической литературе. Кикучи и известен как метод кластерных вариаций .

Улучшения производительности алгоритмов распространения убеждений также можно достичь за счет нарушения симметрии реплик в распределениях полей (сообщений). Это обобщение приводит к новому виду алгоритма, называемому распространением опроса (SP), который оказался очень эффективным в NP-полных задачах, таких как выполнимость. и раскраска графа .

Кластерный вариационный метод и алгоритмы распространения опросов — это два разных улучшения распространения убеждений. Имя «Распространение обобщенного опроса» (GSP) ожидает присвоения алгоритму, который объединяет оба обобщения.

Распространение убеждений по Гауссу (GaBP)

Распространение убеждений по Гауссу — это вариант алгоритма распространения убеждений, когда базовые распределения являются гауссовскими . Первой работой, анализирующей эту специальную модель, была плодотворная работа Вайса и Фримена.

Алгоритм GaBP решает следующую проблему маргинализации:

$P(x_{i})={\frac {1}{Z}}\int _{j\neq i}\exp(-{\tfrac {1}{2}}x^{T}Ax+b^{T}x)\,dx_{j}$

где Z — константа нормализации, A — симметричная положительно определенная матрица (обратная ковариационная матрица, также известная как матрица точности ), а b — вектор сдвига.

Эквивалентно можно показать, что с использованием модели Гаусса решение проблемы маргинализации эквивалентно задаче назначения MAP :

${\underset {x}{\operatorname {argmax} }}\ P(x)={\frac {1}{Z}}\exp(-{\tfrac {1}{2}}x^{T}Ax+b^{T}x).$

Эта задача также эквивалентна следующей задаче минимизации квадратичной формы:

${\underset {x}{\operatorname {min} }}\ 1/2x^{T}Ax-b^{T}x.$

Что также эквивалентно линейной системе уравнений

$Ax=b.$

Сходимость алгоритма GaBP легче анализировать (по сравнению с общим случаем BP), и существуют два известных достаточных условия сходимости. Первый из них был сформулирован Weiss et al. в 2000 году, когда информационная матрица A доминирует по диагонали . Второе условие сходимости было сформулировано Джонсоном и др. в 2006 г., когда спектральный радиус матрицы

$\rho (I-|D^{-1/2}AD^{-1/2}|)<1\,$

где D = диаг( А ). Позже Су и Ву установили необходимые и достаточные условия сходимости для синхронного GaBP и затухающего GaBP, а также еще одно достаточное условие сходимости для асинхронного GaBP. Для каждого случая условие сходимости включает в себя проверку 1) непустости множества (определяемого A), 2) того, что спектральный радиус определенной матрицы меньше единицы, и 3) проблемы сингулярности (при преобразовании сообщения BP в доверие). ) не происходит.

Алгоритм GaBP был связан с областью линейной алгебры, и было показано, что алгоритм GaBP можно рассматривать как итерационный алгоритм решения линейной системы уравнений Ax = b , где A – информационная матрица, b – вектор сдвига. Эмпирически показано, что алгоритм GaBP сходится быстрее, чем классические итеративные методы, такие как метод Якоби, метод Гаусса-Зейделя , последовательная чрезмерная релаксация и другие. Кроме того, показано, что алгоритм GaBP невосприимчив к численным проблемам метода предварительно обусловленных сопряженных градиентов.

Декодирование АД по синдромам

Предыдущее описание алгоритма BP называется декодированием на основе кодовых слов, которое вычисляет приблизительную предельную вероятность. $P(x|X)$, учитывая полученное кодовое слово $X$. Существует эквивалентная форма, которые вычисляют $P(e|s)$, где $s$ это синдром полученного кодового слова $X$ и $e$ это декодированная ошибка. Декодированный входной вектор $x=X+e$. Это изменение лишь меняет интерпретацию функции масс $f_{a}(X_{a})$. Явно сообщения

$\forall x_{v}\in Dom(v),\;\mu _{v\to a}(x_{v})=P(X_{v})\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v}).$

где $P(X_{v})$ - априорная вероятность ошибки для переменной $v$$\forall x_{v}\in Dom(v),\;\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}\delta ({\text{syndrome}}({\mathbf {x} }'_{v})={\mathbf {s} })\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}}).$

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

В двоичном случае $x_{i}\in \{0,1\}$, эти сообщения можно упростить, чтобы вызвать экспоненциальное сокращение $2^{|\{v\}|+|N(v)|}$ в сложности

Определите логарифмическое отношение правдоподобия $l_{v}=\log {\frac {u_{v\to a}(x_{v}=0)}{u_{v\to a}(x_{v}=1)}}$, $L_{a}=\log {\frac {u_{a\to v}(x_{v}=0)}{u_{a\to v}(x_{v}=1)}}$, затем

$v\to a:l_{v}=l_{v}^{(0)}+\sum _{a^{*}\in N(v)\setminus \{a\}}(L_{a^{*}})$

$a\to v:L_{a}=(-1)^{s_{a}}2\tanh ^{-1}\prod _{v^{*}\in N(a)\setminus \{v\}}\tanh(l_{v^{*}}/2)$

где $l_{v}^{(0)}=\log(P(x_{v}=0)/P(x_{v}=1))={\text{const}}$

Апостериорное логарифмическое отношение правдоподобия можно оценить как $l_{v}=l_{v}^{(0)}+\sum _{a\in N(v)}(L_{a})$

Дальнейшее чтение

• Биксон, Дэнни. (2009). Страница ресурсов по распространению гауссовского доверия — веб-страница, содержащая недавние публикации, а также исходный код Matlab.
• Бишоп, Кристофер М. (2006). «Глава 8: Графические модели» (PDF) . Распознавание образов и машинное обучение . Спрингер. стр. 359–418. ISBN  978-0-387-31073-2 . Проверено 2 декабря 2023 г.
• Кофлан, Джеймс. (2009). Учебное пособие «Введение в пропаганду убеждений» .
• Лёлигер, Ханс-Андреа (2004). «Введение в факторные графы». Журнал обработки сигналов IEEE . 21 (1): 28–41. Бибкод : 2004ISPM...21...28L . дои : 10.1109/MSP.2004.1267047 . S2CID   7722934 .
• Маккензи, Дана (2005). « Скорость связи близка к предельной скорости », New Scientist . 9 июля 2005. Выпуск 2507 (Требуется регистрация)
• Ваймирш, Хенк (2007). Итеративный проект приемника . Издательство Кембриджского университета. ISBN  978-0-521-87315-4 .
• Едидия, Дж.С.; Фриман, WT; Вайс, Ю. (январь 2003 г.). «Понимание распространения убеждений и его обобщений» . В Лакмейере, Герхард; Небель, Бернхард (ред.). Исследование искусственного интеллекта в новом тысячелетии . Морган Кауфманн. стр. 239–269. ISBN  978-1-55860-811-5 . Проверено 30 марта 2009 г.
• Едидия, Дж.С.; Фриман, WT; Вайс, Ю. (июль 2005 г.). «Построение аппроксимаций свободной энергии и обобщенных алгоритмов распространения убеждений» . Транзакции IEEE по теории информации . 51 (7): 2282–2312. CiteSeerX   10.1.1.3.5650 . дои : 10.1109/TIT.2005.850085 . S2CID   52835993 .