Введение
Факторный граф — это двудольный граф, представляющий факторизацию функции. В теории вероятностей и ее приложениях факторные графы используются для представления факторизации функции распределения вероятности, что позволяет эффективно выполнять вычисления, такие как вычисление предельных распределений с помощью алгоритма суммарного произведения. Одним из значительных успехов факторных графов и алгоритма суммарного произведения является декодирование кодов коррекции ошибок, приближающихся к предельной пропускной способности, таких как коды LDPC и турбо-коды. Факторные графы обобщают графы ограничений. Фактор, принимающий значение либо 0, либо 1, называется ограничением. Граф ограничений — это факторный граф, в котором все факторы являются ограничениями. Алгоритм произведения максимумов для факторных графов можно рассматривать как обобщение алгоритма обеспечения согласованности дуг для обработки ограничений.
Передача сообщений на графиках факторов
Популярным алгоритмом передачи сообщений на факторных графах является алгоритм суммы-произведения, который эффективно вычисляет все маржинальные распределения отдельных переменных функции. В частности, маржинальное распределение переменной определяется как, где обозначение означает, что суммирование происходит по всем переменным, кроме . Сообщения в алгоритме суммы-произведения концептуально вычисляются в вершинах и передаются по ребрам. Сообщение от или к переменной вершине всегда является функцией этой конкретной переменной. Например, если переменная бинарная, сообщения по ребрам, инцидентным соответствующей вершине, могут быть представлены в виде векторов длины 2: первый элемент – значение сообщения при 0, второй элемент – значение сообщения при 1. Если переменная принадлежит области действительных чисел, сообщения могут быть произвольными функциями, и требуется особое внимание к их представлению. На практике алгоритм суммы-произведения используется для статистического вывода, где является совместным распределением или совместной функцией правдоподобия, а факторизация зависит от условных независимостей между переменными. Теорема Хаммерсли-Клиффорда показывает, что другие вероятностные модели, такие как байесовские сети и марковские сети, могут быть представлены в виде факторных графов; последнее представление часто используется при выполнении вывода над такими сетями с использованием алгоритма распространения убеждений. С другой стороны, байесовские сети более естественно подходят для генеративных моделей, поскольку они могут непосредственно представлять причинно-следственные связи модели.
where the notation means that the summation goes over all the variables, except The messages of the sum–product algorithm are conceptually computed in the vertices and passed along the edges. A message from or to a variable vertex is always a function of that particular variable. For instance, when a variable is binary, the messages
over the edges incident to the corresponding vertex can be represented as vectors of length 2: the first entry is the message evaluated in 0, the second entry is the message evaluated in 1. When a variable belongs to the field of real numbers, messages can be arbitrary functions, and special care needs to be taken in their representation. In practice, the sum–product algorithm is used for statistical inference, whereby is a joint distribution or a joint likelihood function, and the factorization depends on the conditional independencies among the variables. The Hammersley–Clifford theorem shows that other probabilistic models such as Bayesian networks and Markov networks can be represented as factor graphs; the latter representation is frequently used when performing inference over such networks using belief propagation. On the other hand, Bayesian networks are more naturally suited for generative models, as they can directly represent the causalities of the model.