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

редактировать

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

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

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

p X i (xi) = ∑ x ′: xi ′ = xip (x ′). {\ displaystyle p_ {X_ {i}} (x_ {i}) = \ sum _ {\ mathbf {x} ': x' _ {i} = x_ {i}} p (\ mathbf {x} '). }

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

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

Содержание

1 Описание алгоритма суммы-произведения
2 Точный алгоритм для деревьев
3 Приближенный алгоритм для общих графиков
4 Связанный алгоритм и вопросы сложности
5 Связь со свободной энергией
6 Распространение обобщенных убеждений (GBP)
7 Распространение убеждений по Гауссу (GaBP)
8 Синдромное декодирование АД
9 Ссылки
10 Дополнительная литература

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

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

p (x) = ∏ a ∈ F fa (xa) {\ displaystyle p (\ mathbf {x}) = \ prod _ {a \ in F} f_ {a} ( \ mathbf {x} _ {a})}

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

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

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

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

∀ xv ∈ D om (v), μ v → a (xv) = ∏ a ∗ ∈ N (v) ∖ {a} μ a ∗ → v (xv). {\ 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}).}

\ 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. Если

N (v) ∖ {a} {\ displaystyle N (v) \ setminus \ {a \}}

N (v) \ setminus \ {a \}

пусто, тогда

μ v → a (xv) {\ displaystyle \ mu _ {v \ to a} (x_ {v})}

\ mu _ {v \ to a} (x_ {v})

устанавливается на равномерное распределение.

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

∀ xv ∈ D om (v), μ a → v (xv) = ∑ xa ′: xv ′ = xvfa (xa ′) ∏ v ∗ ∈ N (a) ∖ {v} μ v ∗ → a (xv ∗ ′). {\ 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 ^ {*}}).}

\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. Если

N (a) ∖ {v} {\ displaystyle N (a) \ setminus \ {v \}}

N (а) \ setminus \ {v \}

пусто, то

μ a → v (xv) = fa (xv) {\ displaystyle \ mu _ {a \ to v} (x_ {v}) = f_ {a} (x_ {v})}

\ mu _ {a \ to v} (x_ {v}) = f_ {a} (x_ {v})

, поскольку в этом случае

xv = xa {\ displaystyle x_ {v} = x_ {a}}

x_ {v} = x_ {a}

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

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

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

p X v (xv) ∝ ∏ a ∈ N (v) μ a → v (xv). {\ displaystyle p_ {X_ {v}} (x_ {v}) \ propto \ prod _ {a \ in N (v)} \ mu _ {a \ to v} (x_ {v}).}

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

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

p X a (xa) ∝ fa (xa) ∏ v ∈ N ( а) μ v → a (xv). {\ displaystyle p_ {X_ {a}} (\ mathbf {x} _ {a}) \ propto f_ {a} (\ mathbf {x} _ {a}) \ prod _ {v \ in N (a)} \ mu _ {v \ to a} (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}).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Связь со свободной энергией

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

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

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

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

E (X) = журнал ⁡ ∏ fjfj (xj). {\ displaystyle E (\ mathbf {X}) = \ log \ prod _ {f_ {j}} f_ {j} (x_ {j}).}

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

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

F = U - H = ∑ XP (X) E (X) + ∑ XP (X) журнал ⁡ P (X). {\ Displaystyle F = UH = \ сумма _ {\ mathbf {X}} P (\ mathbf {X}) E (\ mathbf {X}) + \ sum _ {\ mathbf {X}} P (\ mathbf {X }) \ log P (\ mathbf {X}).}

F = UH = \ sum _ {\ mathbf {X}} P (\ mat hbf {X}) E (\ mathbf {X}) + \ sum _ {\ mathbf {X}} P (\ mathbf {X}) \ log P (\ mathbf {X}).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А х = b. {\ displaystyle Ax = b.}

Ax = b.

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

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

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

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

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

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

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

∀ xv ∈ D om (v), μ v → a (xv) = P (X v) ∏ a ∗ ∈ N (v) ∖ {a} μ a ∗ → v (xv). {\ 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 \ 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) {\ displaystyle P (X_ {v})}

{\ displaystyle P (X_ {v})}

- априорная вероятность ошибки для переменной

v {\ displaystyle v}

v

∀ xv ∈ D om (v), μ a → v (xv) = ∑ xa ′: xv ′ = xv δ (синдром (xv ′) = s) ∏ v ∗ ∈ N (a) ∖ {v} μ v ∗ → a (xv ∗ ′). {\ displaystyle \ forall x_ {v} \ in Dom (v), \; \ mu _ {a \ to v} (x_ {v}) = \ sum _ {\ mathbf {x} '_ {a}: x '_ {v} = x_ {v}} \ delta ({\ text {синдром}} ({\ mathbf {x}}' _ {v}) = {\ mathbf {s}}) \ prod _ {v ^ {*} \ in N (a) \ setminus \ {v \}} \ mu _ {v ^ {*} \ to a} (x '_ {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^{*}}).

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

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

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

v → a: lv = lv (0) + ∑ a ∗ ∈ N (v) ∖ {a} (L a ∗) {\ displaystyle v \ to a: l_ {v} = l_ {v} ^ {(0)} + \ sum _ {a ^ {*} \ in N (v) \ setminus \ {a \}} (L_ {a ^ {*}})}

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

a → v: L a = (- 1) sa 2 tanh - 1 ⁡ ∏ v ∗ ∈ N (a) ∖ {v} tanh ⁡ (lv ∗ / 2) {\ displaystyle a \ to v: L_ {a} = (- 1) ^ {s_ {a}} 2 \ tanh ^ {- 1} \ prod _ {v ^ {*} \ in N (a) \ setminus \ {v \}} \ tanh (l_ {v ^ {*}} / 2)}

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

где

lv (0) = журнал ⁡ (P (xv = 0) / P (xv = 1)) = const {\ displaystyle l_ {v} ^ {(0)} = \ log (P (x_ {v} = 0) / P (x_ {v} = 1)) = {\ text {const}}}

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

Апостериорное логарифмическое отношение правдоподобия можно оценить как $lv = lv (0) + ∑ a ∈ N (v) (L a) {\ displayst yle l_ {v} = l_ {v} ^ {(0)} + \ sum _ {a \ in N (v)} (L_ {a})}$ ${\ 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, J.S.; Freeman, W.T.; Вайс, Ю. (январь 2003 г.). «Понимание распространения убеждений и их обобщений». В Лакемейере, Герхард; Небель, Бернхард (ред.). Изучение искусственного интеллекта в новом тысячелетии. Морган Кауфманн. С. 239–269. ISBN 978-1-55860-811-5. Проверено 30 марта 2009 г.
Yedidia, J.S.; Freeman, W.T.; Вайс, Ю. (июль 2005 г.). «Построение приближений свободной энергии и обобщенных алгоритмов распространения убеждений». Транзакции IEEE по теории информации. 51(7): 2282–2312. CiteSeerX 10.1.1.3.5650. doi : 10.1109 / TIT.2005.850085. Проверено 28 марта 2009 г.