skip to navigation
skip to content

sumproduct 0.0.6

The sum-product algorithm. Belief propagation (message passing) for factor graphs

`sumproduct <https:"" pypi="" sumproduct="">`__

|Build Status| |Downloads|

An implementation of Belief Propagation for factor graphs, also known as
the sum-product algorithm
(`Reference <http:"" staff="" d.barber="" pmwiki="" pmwiki.php?n="Brml.HomePage">`__).


pip install sumproduct

.. figure::
:alt: Simple factor graph

Simple factor graph
The factor graph used in ```` (image made with
`yEd <http:"" en="" products_yed_applicationfeatures.html="">`__).

Basic Usage

Create a factor graph


from sumproduct import Variable, Factor, FactorGraph
import numpy as np

g = FactorGraph(silent=True) # init the graph without message printouts
x1 = Variable('x1', 2) # init a variable with 2 states
x2 = Variable('x2', 3) # init a variable with 3 states
f12 = Factor('f12', np.array([
])) # create a factor, node potential for p(x1 | x2)
# connect the parents to their children
g.append('f12', x2) # order must be the same as dimensions in factor potential!
g.append('f12', x1) # note: f12 potential's shape is (3,2), i.e. (x2,x1)

Run Inference

sum-product algorithm


>>> g.compute_marginals()
>>> g.nodes['x1'].marginal()
array([ 0.5, 0.5])

Brute force marginalization and conditioning

The sum-product algorithm can only compute exact marginals for acyclic
graphs. Check against the brute force method (at great computational
expense) if you have a loopy graph.


>>> g.brute_force()
>>> g.nodes['x1'].bfmarginal
array([ 0.5, 0.5])

Condition on Observations


>>> g.observe('x2', 2) # observe state 1 (middle of above f12 potential)
>>> g.compute_marginals(max_iter=500, tolerance=1e-6)
>>> g.nodes['x1'].marginal()
array([ 0.2, 0.8])
>>> g.brute_force()
>>> g.nodes['x1'].bfmarginal
array([ 0.2, 0.8])

Additional Information

``sumproduct`` implements a parallel message passing schedule: Message
passing alternates between Factors and Variables sending messages to all
their neighbors until the convergence of marginals.

Check ```` for a detailed example.

Implementation Details

See block comments in the code's methods for details, but the
implementation strategy comes from Chapter 5 of `David Barber's
book <http:"" staff="" d.barber="" pmwiki="" pmwiki.php?n="Brml.HomePage">`__.

.. |Build Status| image::
.. |Downloads| image::
File Type Py Version Uploaded on Size
sumproduct-0.0.6-py2.py3-none-any.whl (md5) Python Wheel 2.7 2014-12-31 9KB
sumproduct-0.0.6.tar.gz (md5) Source 2014-12-31 7KB