Partition Functions of Normal Factor Graphs

Abstract

One of the most common types of functions in mathematics, physics, and engineering is a sum of products, sometimes called a partition function. After "normalization," a sum of products has a natural graphical representation, called a normal factor graph (NFG), in which vertices represent factors, edges represent internal variables, and half-edges represent the external variables of the partition function. In physics, so-called trace diagrams share similar features. We believe that the conceptual framework of representing sums of products as partition functions of NFGs is an important and intuitive paradigm that, surprisingly, does not seem to have been introduced explicitly in the previous factor graph literature. Of particular interest are NFG modifications that leave the partition function invariant. A simple subclass of such NFG modifications offers a unifying view of the Fourier transform, tree-based reparameterization, loop calculus, and the Legendre transform.

8 pages, 17 figures. To be presented at 2011 Information Theory and Applications Workshop, La Jolla, CA, February 7, 2011

Cited by in corpus (9)

• The Bethe Permanent of a Non-Negative Matrix
• A Factor-Graph Representation of Probabilities in Quantum Mechanics
• Codes on graphs: Models for elementary algebraic topology and statistical physics
• Codes on Graphs: Fundamentals
• An Importance Sampling Scheme on Dual Factor Graphs. I. Models in a Strong External Field
• Holographic Transformation, Belief Propagation and Loop Calculus for Generalized Probabilistic Theories
• The Bethe Free Energy Allows to Compute the Conditional Entropy of Graphical Code Instances. A Proof from the Polymer Expansion
• Holographic Transformation for Quantum Factor Graphs
• Gauging Variational Inference