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

Factor graph

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

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

Определение

Факторный граф - это двудольный граф представляющий факторизация функции. Учитывая факторизацию функции ,

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

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

Примеры

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

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

,

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

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

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

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

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

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

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

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

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

  • Клиффорд (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