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