Skip to main content

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

Project description

sumproduct
==========

An implementation of Belief Propagation for factor graphs, also known as
the sum product algorithm.

::

pip install sumproduct

.. figure:: http://f.cl.ly/items/2P021j2y3A2Q191F451h/unnamed0.png
:alt: Simple factor graph

Simple factor graph
The factor graph used in ``test.py``.

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([
[0.8,0.2],
[0.2,0.8],
[0.5,0.5]
])) # create a factor node potentials for p(x1 | x2)
# connect the parents to their children
g.add(f12)
g.append('f12', x2)
g.append('f12', 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])

Additional Information
^^^^^^^^^^^^^^^^^^^^^^

Check ``test.py`` 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://web4.cs.ucl.ac.uk/staff/D.Barber/pmwiki/pmwiki.php?n=Brml.HomePage>`__.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

sumproduct-0.0.3.tar.gz (7.3 kB view details)

Uploaded Source

Built Distribution

sumproduct-0.0.3-py2.py3-none-any.whl (8.4 kB view details)

Uploaded Python 2Python 3

File details

Details for the file sumproduct-0.0.3.tar.gz.

File metadata

  • Download URL: sumproduct-0.0.3.tar.gz
  • Upload date:
  • Size: 7.3 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No

File hashes

Hashes for sumproduct-0.0.3.tar.gz
Algorithm Hash digest
SHA256 9453e11ec0ec1c78fd5297c9a636f3eaf2c73ac574eddbadc590c88d4880394e
MD5 a9439dddf6fb47da9869c4cb756c2d2a
BLAKE2b-256 89dd7c6c319d96359be22727f44c19a839bd0041e99968f8b88161291aecf3bf

See more details on using hashes here.

File details

Details for the file sumproduct-0.0.3-py2.py3-none-any.whl.

File metadata

File hashes

Hashes for sumproduct-0.0.3-py2.py3-none-any.whl
Algorithm Hash digest
SHA256 2ef83aa02c3176c23e5e47361af304877648b70ac4d16719174c5df6cf786dd4
MD5 8de854a8b98114cadc1e4818cc36c9ce
BLAKE2b-256 6ff22bd30f0bbb482a1a6388436d2177fca0e7abfbd017632407329e5d71c3eb

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page