Распространение веры

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

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

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

Если X = { X _i } представляет собой набор дискретных случайных величин с совместной функцией масс p , предельное распределение одного X _i представляет собой просто суммирование p по всем другим переменным:

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

Однако это быстро становится недопустимым с точки зрения вычислений: если имеется 100 двоичных переменных, то необходимо суммировать более 2 ⁹⁹  ≈ 6,338 × 10 ²⁹ возможных значений. Используя структуру многодерева, распространение убеждений позволяет гораздо более эффективно вычислять маргинальные значения.

Описание алгоритма сумм-произведений [ править ]

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

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

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

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

• Сообщение от переменного узла v к факторному узлу a является продуктом сообщений от всех других соседних факторных узлов (кроме получателя; в качестве альтернативы можно сказать, что получатель отправляет как сообщение постоянную функцию, равную «1»):

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

где N ( v ) - множество соседних (факторных) узлов к v . Если пусто, то устанавливается равномерное распределение.${\ Displaystyle N (v) \ setminus \ {а \}}$${\displaystyle \mu _{v\to a}(x_{v})}$

• Сообщение от узла фактора a к узлу переменной v является произведением фактора с сообщениями от всех других узлов, маргинальными по всем переменным, кроме той, которая связана с v :

${\displaystyle \forall x_{v}\in Dom(v),\;\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}f_{a}(\mathbf {x} '_{a})\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}}).}$

где N ( a ) - множество соседних (переменных) узлов к 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}).}$

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

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

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

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

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

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

Примерный алгоритм построения общих графиков [ править ]

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

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

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

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

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

Подобный алгоритм обычно называют алгоритмом Витерби , но также известен как частный случай алгоритма максимального произведения или минимальной суммы, который решает связанную проблему максимизации или наиболее вероятного объяснения. Вместо попытки решить маргинальное значение здесь цель состоит в том, чтобы найти значения, которые максимизируют глобальную функцию (т.е. наиболее вероятные значения в вероятностной настройке), и это может быть определено с помощью 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]

Распространение обобщенных убеждений (GBP) [ править ]

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

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

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

Распространение веры по Гауссу (GaBP) [ править ]

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

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

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

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

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

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

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

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

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

${\displaystyle Ax=b.}$

Сходимость алгоритма GaBP легче анализировать (по сравнению с общим случаем BP), и есть два известных достаточных условия сходимости. Первый был сформулирован Weiss et al. в 2000 году, когда информационная матрица A доминирует по диагонали . Второе условие сходимости сформулировано Johnson et al. ^[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. Проверено 20 марта 2014 .
• Кофлан, Джеймс. (2009). Учебное введение в распространение веры .
• Лёлигер, Ханс-Андреа (2004). «Введение в факторные графы». Журнал обработки сигналов IEEE . 21 (1): 28–41. Bibcode : 2004ISPM ... 21 ... 28L . DOI : 10.1109 / MSP.2004.1267047 .
• Маккензи, Дана (2005). « Скорость связи приближается к предельной », New Scientist . 9 июля 2005 г. Выпуск 2507 (Требуется регистрация).
• Вимерш, Хенк (2007). Итерационный дизайн приемника . Издательство Кембриджского университета. ISBN 978-0-521-87315-4.
• Yedidia, JS; Фримен, WT; Вайс, Ю. (январь 2003 г.). «Понимание распространения убеждений и их обобщений» . В Лакемейере, Герхард; Небель, Бернхард (ред.). Изучение искусственного интеллекта в новом тысячелетии . Морган Кауфманн. С. 239–269. ISBN 978-1-55860-811-5. Проверено 30 марта 2009 года .
• Yedidia, JS; Фримен, WT; Вайс, Ю. (июль 2005 г.). «Построение приближений свободной энергии и обобщенных алгоритмов распространения убеждений» . IEEE Transactions по теории информации . 51 (7): 2282–2312. CiteSeerX  10.1.1.3.5650 . DOI : 10.1109 / TIT.2005.850085 .