Факторный график

Не путать с факторизацией графов .

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

Факторные графы обобщают графы ограничений . Фактор, значение которого равно 0 или 1, называется ограничением. Граф ограничений — это граф факторов, в котором все факторы являются ограничениями. Алгоритм максимального произведения для факторных графов можно рассматривать как обобщение алгоритма согласованности дуг для обработки ограничений.

Определение

Факторный граф — это двудольный граф, представляющий факторизацию функции. Учитывая факторизацию функции $g(X_{1},X_{2},\dots ,X_{n})$,

$g(X_{1},X_{2},\dots ,X_{n})=\prod _{j=1}^{m}f_{j}(S_{j}),$

где $S_{j}\subseteq \{X_{1},X_{2},\dots ,X_{n}\}$, соответствующий граф факторов $G=(X,F,E)$ состоит из переменных вершин $X=\{X_{1},X_{2},\dots ,X_{n}\}$, факторные вершины $F=\{f_{1},f_{2},\dots ,f_{m}\}$, и края $E$. Ребра зависят от факторизации следующим образом: между вершиной фактора существует ненаправленное ребро. $f_{j}$ и переменная вершина $X_{k}$ если $X_{k}\in S_{j}$. Негласно предполагается, что функция имеет действительное значение : $g(X_{1},X_{2},\dots ,X_{n})\in \mathbb {R}$.

Факторные графики можно комбинировать с алгоритмами передачи сообщений для эффективного вычисления определенных характеристик функции. $g(X_{1},X_{2},\dots ,X_{n})$, такие как предельные распределения .

Примеры

Пример графика коэффициентов

Рассмотрим функцию, которая факторизуется следующим образом:

$g(X_{1},X_{2},X_{3})=f_{1}(X_{1})f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})f_{4}(X_{2},X_{3})$,

с соответствующим графиком факторов, показанным справа. Обратите внимание, что граф фактора имеет цикл . Если мы объединимся $f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})$ в один фактор, результирующий граф факторов будет деревом . Это важное различие, поскольку алгоритмы передачи сообщений обычно точны для деревьев и лишь приблизительны для графов с циклами.

Передача сообщений по факторным графам

Популярным алгоритмом передачи сообщений на факторных графах является алгоритм суммы-произведения, который эффективно вычисляет все маргинальные значения отдельных переменных функции. В частности, предел переменной $X_{k}$ определяется как

$g_{k}(X_{k})=\sum _{X_{\bar {k}}}g(X_{1},X_{2},\dots ,X_{n})$

где обозначение $X_{\bar {k}}$ означает, что суммирование ведется по всем переменным, кроме $X_{k}$. Сообщения алгоритма суммы-произведения концептуально вычисляются в вершинах и передаются по ребрам. Сообщение от вершины переменной или к ней всегда является функцией этой конкретной переменной. Например, если переменная является двоичной, сообщенияпо ребрам, инцидентным соответствующей вершине, можно представить в виде векторов длины 2: первая запись — это сообщение, оцененное в 0, вторая запись — это сообщение, оцененное в 1. Когда переменная принадлежит полю действительных чисел , сообщения могут являются произвольными функциями, и при их представлении необходимо соблюдать особую осторожность.

используется алгоритм суммы-произведения На практике для статистического вывода , при котором $g(X_{1},X_{2},\dots ,X_{n})$ представляет собой совместное распределение или совместную функцию правдоподобия , а факторизация зависит от условных зависимостей между переменными.

Теорема Хаммерсли-Клиффорда показывает, что другие вероятностные модели, такие как байесовские сети и сети Маркова, могут быть представлены в виде факторных графов; последнее представление часто используется при выполнении вывода в таких сетях с использованием распространения убеждений . С другой стороны, байесовские сети более естественно подходят для генеративных моделей , поскольку они могут напрямую представлять причинно-следственные связи модели.

См. также

• Распространение убеждений
• Байесовский вывод
• Байесовское программирование
• Условная вероятность
• Марковская сеть
• Байесовская сеть
• Теорема Хаммерсли – Клиффорда

Внешние ссылки

• Лелигер, Ханс-Андреа (январь 2004 г.), «Введение в факторные графы» (PDF) , журнал IEEE Signal Processing Magazine , 21 (1): 28–41, Bibcode : 2004ISPM...21...28L , doi : 10.1109/MSP.2004.1267047 , S2CID   7722934
• Dimple. Архивировано 6 января 2016 г. в Wayback Machine, инструменте с открытым исходным кодом для построения и решения факторных графиков в MATLAB.
• Лелигер, Ханс-Андреа (2008), Введение в факторные графы (PDF)

Ссылки

• Клиффорд (1990), «Марковские случайные поля в статистике», в Гримметте, Греция; Валлийский, DJA (ред.), Беспорядок в физических системах, JM Hammersley Festschrift (постскриптум) , Oxford University Press , стр. 19–32, ISBN  9780198532156
• Фрей, Брендан Дж. (2003), «Расширение факторных графов для унификации направленных и ненаправленных графических моделей» , в книге Джайн, Нитин (ред.), UAI'03, Материалы 19-й конференции по неопределенности в искусственном интеллекте , Морган Кауфманн. , стр. 257–264, arXiv : 1212.2486 , ISBN.  0127056645
• Кшишанг, Фрэнк Р .; Фрей, Брендан Дж.; Лелигер, Ханс-Андреа (2001), «Графы факторов и алгоритм суммы-продукта», IEEE Transactions on Information Theory , 47 (2): 498–519, CiteSeerX   10.1.1.54.1570 , doi : 10.1109/18.910572 .
• Ваймирш, Хенк (2007), Итеративный дизайн приемника , издательство Кембриджского университета, ISBN  978-0-521-87315-4