fglib

The factor graph library (fglib) is a Python package to simulate message passing on factor graphs. It supports the

sum-product algorithm (belief propagation)
max-product algorithm
max-sum algorithm
mean-field algorithm - in development

with discrete and Gaussian random variables.

Installation

Install fglib with the Python Package Index by using

pip install fglib

Install fglib with setuptools by using

python setup.py install

Dependencies

Python 3.4 or later
NetworkX 2.0 or later
NumPy 1.14 or later
matplotlib 2.0 or later

Documentation

In order to generate the documentation site for the factor graph library, execute the following commands from the top-level directory.

$ cd docs/
$ make html

Example

Examples (like the following one) are located in the examples/ directory.

"""A simple example of the sum-product algorithm

This is a simple example of the sum-product algorithm on a factor graph
with Discrete random variables.

      /--\      +----+      /--\      +----+      /--\
     | x1 |-----| fa |-----| x2 |-----| fb |-----| x3 |
      \--/      +----+      \--/      +----+      \--/
                             |
                           +----+
                           | fc |
                           +----+
                             |
                            /--\
                           | x4 |
                            \--/

The following joint distributions are used for the factor nodes.

     fa   | x2=0 x2=1 x2=2     fb   | x3=0 x3=1     fc   | x4=0 x4=1
     ---------------------     ----------------     ----------------
     x1=0 | 0.3  0.2  0.1      x2=0 | 0.3  0.2      x2=0 | 0.3  0.2
     x1=1 | 0.3  0.0  0.1      x2=1 | 0.3  0.0      x2=1 | 0.3  0.0
                               x2=2 | 0.1  0.1      x2=2 | 0.1  0.1

"""

from fglib import graphs, nodes, inference, rv

# Create factor graph
fg = graphs.FactorGraph()

# Create variable nodes
x1 = nodes.VNode("x1", rv.Discrete)  # with 2 states (Bernoulli)
x2 = nodes.VNode("x2", rv.Discrete)  # with 3 states
x3 = nodes.VNode("x3", rv.Discrete)
x4 = nodes.VNode("x4", rv.Discrete)

# Create factor nodes (with joint distributions)
dist_fa = [[0.3, 0.2, 0.1],
           [0.3, 0.0, 0.1]]
fa = nodes.FNode("fa", rv.Discrete(dist_fa, x1, x2))

dist_fb = [[0.3, 0.2],
           [0.3, 0.0],
           [0.1, 0.1]]
fb = nodes.FNode("fb", rv.Discrete(dist_fb, x2, x3))

dist_fc = [[0.3, 0.2],
           [0.3, 0.0],
           [0.1, 0.1]]
fc = nodes.FNode("fc", rv.Discrete(dist_fc, x2, x4))

# Add nodes to factor graph
fg.set_nodes([x1, x2, x3, x4])
fg.set_nodes([fa, fb, fc])

# Add edges to factor graph
fg.set_edge(x1, fa)
fg.set_edge(fa, x2)
fg.set_edge(x2, fb)
fg.set_edge(fb, x3)
fg.set_edge(x2, fc)
fg.set_edge(fc, x4)

# Perform sum-product algorithm on factor graph
# and request belief of variable node x4
belief = inference.sum_product(fg, x4)

# Print belief of variables
print("Belief of variable node x4:")
print(belief)

References

B. J. Frey, F. R. Kschischang, H.-A. Loeliger, and N. Wiberg, "Factor graphs and algorithms," in Proc. 35th Allerton Conf. Communications, Control, and Computing, Monticello, IL, Sep. 29-Oct. 1, 1997, pp. 666-680.
F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 498–519, Feb. 2001.
H.-A. Loeliger, “An introduction to factor graphs,” IEEE Signal Process. Mag., vol. 21, no. 1, pp. 28–41, Jan. 2004.
H.-A. Loeliger, J. Dauwels, H. Junli, S. Korl, P. Li, and F. R. Kschischang, “The factor graph approach to model-based signal processing,” Proc. IEEE, vol. 95, no. 6, pp. 1295–1322, Jun. 2007.
H. Wymeersch, Iterative Receiver Design. Cambridge, UK: Cambridge University Press, 2007.
C. M. Bishop, Pattern Recognition and Machine Learning, 8th ed., ser. Information Science and Statistics. New York, USA: Springer Science+Business Media, 2009.

danbar / fglib

readme