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

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (April 2009) (Learn how and when to remove this message)

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

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

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

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

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

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

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

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

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

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

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

• Сообщение от факторного узла к переменному узлу определяется как произведение фактора с сообщениями от всех других узлов, маргинализированными по всем переменным, за исключением одного, связанного с , для , где — множество соседних (переменных) узлов к . Если пусто, то , поскольку в этом случае .${\displaystyle \mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R} }$${\displaystyle a}$${\displaystyle v}$${\displaystyle v}$$${\displaystyle \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)}$$${\displaystyle x_{v}\in \operatorname {Dom} (v)}$${\displaystyle N(a)}$${\displaystyle a}$${\displaystyle N(a)\setminus \{v\}}$${\displaystyle \mu _{a\to v}(x_{v})=f_{a}(x_{v})}$${\displaystyle x_{v}=x_{a}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы распространения убеждений обычно представляются как уравнения обновления сообщений на факторном графе, включающие сообщения между переменными узлами и их соседними факторными узлами и наоборот. Рассмотрение сообщений между областями в графе является одним из способов обобщения алгоритма распространения убеждений. ^[10] Существует несколько способов определения набора областей в графе, которые могут обмениваться сообщениями. Один из методов использует идеи, представленные Кикучи в физической литературе, ^{[11] [12] [13]} и известен как метод кластерной вариации Кикучи. ^[14]

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

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

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

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

${\displaystyle 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 :

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

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

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

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

${\displaystyle Ax=b.}$

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

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

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

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

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

${\displaystyle \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}).}$

где — априорная вероятность ошибки по переменной${\displaystyle P(X_{v})}$${\displaystyle v}$${\displaystyle \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^{*}}).}$

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

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

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

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

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

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

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

• Биксон, Дэнни. (2009). Страница ресурсов по распространению убеждений по Гауссу — веб-страница, содержащая последние публикации, а также исходный код Matlab.
• Бишоп, Кристофер М. (2006). "Глава 8: Графические модели" (PDF) . Распознавание образов и машинное обучение . Springer. стр. 359–418. ISBN 978-0-387-31073-2. Получено 2 декабря 2023 г. .
• Кофлан, Джеймс. (2009). Введение в распространение убеждений.
• Löliger, Hans-Andrea (2004). «Введение в факторные графы». Журнал обработки сигналов IEEE . 21 (1): 28–41. Bibcode : 2004ISPM...21...28L. doi : 10.1109/MSP.2004.1267047. S2CID  7722934.
• Маккензи, Дана (2005). «Скорость связи приближается к предельной скорости», New Scientist . 9 июля 2005 г. Выпуск 2507 (требуется регистрация)
• Wymeersch, Henk (2007). Итеративный проект приемника. Cambridge University Press. ISBN 978-0-521-87315-4.
• Yedidia, JS; Freeman, WT; Weiss, Y. (январь 2003 г.). «Понимание распространения убеждений и его обобщений». В Lakemeyer, Gerhard; Nebel, Bernhard (ред.). Exploring Artificial Intelligence in the New Millennium . Morgan Kaufmann. стр. 239–269. ISBN 978-1-55860-811-5. Получено 30 марта 2009 г.
• Yedidia, JS; Freeman, WT; Weiss, Y. (июль 2005 г.). «Построение приближений свободной энергии и обобщенных алгоритмов распространения убеждений». Труды IEEE по теории информации . 51 (7): 2282–2312. CiteSeerX  10.1.1.3.5650 . doi :10.1109/TIT.2005.850085. S2CID  52835993.