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

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

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

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

Определение

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

внешняя ссылка

• Введение в факторные графы к Ханс-Андреа Лелигер, Журнал IEEE Signal Processing Magazine, Январь 2004 г., стр. 28–41.
• ямочка инструмент с открытым исходным кодом для построения и решения факторных графов в MATLAB.
• Введение в факторный график. Презентация ETH профессора д-ра Ханса Лелигера

Рекомендации

• Клиффорд (1990), «Марковские случайные поля в статистике», в Grimmett, G.R .; Валлийский, D.J.A. (ред.), Беспорядок в физических системах, JM Hammersley Festschrift, Oxford University Press, стр. 19–32
• Фрей, Брендан Дж. (2003), «Расширение факторных графов с целью объединения направленных и неориентированных графических моделей», в Jain, Nitin (ed.), UAI'03, Труды 19-й конференции по неопределенности в искусственном интеллекте, 7–10 августа, Акапулько, Мексика, Морган Кауфманн, стр. 257–264.
• Кшишанг, Франк Р.; Фрей, Брендан Дж .; Лелигер, Ханс-Андреа (2001), "Факторные графы и алгоритм сумм-произведений", IEEE Transactions по теории информации, 47 (2): 498–519, Дои:10.1109/18.910572, получено 2008-02-06.
• Вимерш, Хенк (2007), Итерационный дизайн приемника, Издательство Кембриджского университета, ISBN  978-0-521-87315-4