Факторный граф — это двудольный граф , представляющий факторизацию функции . В теории вероятностей и ее приложениях факторные графы используются для представления факторизации функции распределения вероятностей , что позволяет проводить эффективные вычисления, такие как вычисление предельных распределений с помощью алгоритма суммы-произведения . Одной из важных историй успеха факторных графов и алгоритма суммы-произведения является декодирование кодов исправления ошибок , приближающихся к пропускной способности , таких как LDPC и турбокоды .
Факторные графы обобщают графы ограничений . Фактор, значение которого равно 0 или 1, называется ограничением. Граф ограничений — это граф факторов, в котором все факторы являются ограничениями. Алгоритм максимального произведения для факторных графов можно рассматривать как обобщение алгоритма согласованности дуг для обработки ограничений.
Факторный граф — это двудольный граф , представляющий факторизацию функции. Учитывая факторизацию функции ,
где соответствующий фактор-граф состоит из переменных вершин , фактор- вершин и ребер . Ребра зависят от факторизации следующим образом: существует ненаправленное ребро между факторной вершиной и переменной вершиной, если . Негласно предполагается, что функция имеет действительное значение : .
Факторные графики можно комбинировать с алгоритмами передачи сообщений для эффективного вычисления определенных характеристик функции , таких как маргинальные распределения .
Рассмотрим функцию, которая факторизуется следующим образом:
с соответствующим графиком факторов, показанным справа. Обратите внимание, что граф фактора имеет цикл . Если мы объединимся в один фактор, результирующий граф факторов будет деревом . Это важное различие, поскольку алгоритмы передачи сообщений обычно точны для деревьев и лишь приблизительны для графов с циклами.
Популярным алгоритмом передачи сообщений на факторных графах является алгоритм суммы-произведения, который эффективно вычисляет все маргинальные значения отдельных переменных функции. В частности, предел переменной определяется как
где обозначение означает, что суммирование проводится по всем переменным, кроме . Сообщения алгоритма суммы-произведения концептуально вычисляются в вершинах и передаются по ребрам. Сообщение от вершины переменной или к ней всегда является функцией этой конкретной переменной. Например, если переменная является двоичной, сообщения по ребрам, инцидентным соответствующей вершине, могут быть представлены как векторы длины 2: первая запись — это сообщение, оцененное в 0, вторая запись — это сообщение, оцененное в 1. Когда переменная принадлежит области действительных чисел , сообщения могут быть произвольными функциями, и при их представлении необходимо соблюдать особую осторожность.
На практике для статистического вывода используется алгоритм суммы-произведения , в соответствии с которым представляет собой совместное распределение или совместную функцию правдоподобия , а факторизация зависит от условных зависимостей между переменными.
Теорема Хаммерсли-Клиффорда показывает, что другие вероятностные модели, такие как байесовские сети и сети Маркова, могут быть представлены в виде факторных графов; последнее представление часто используется при выполнении вывода в таких сетях с использованием распространения убеждений . С другой стороны, байесовские сети более естественно подходят для генеративных моделей , поскольку они могут напрямую представлять причинно-следственные связи модели.
