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>`__.
==========
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 hashes)
Built Distribution
Close
Hashes for sumproduct-0.0.3-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2ef83aa02c3176c23e5e47361af304877648b70ac4d16719174c5df6cf786dd4 |
|
MD5 | 8de854a8b98114cadc1e4818cc36c9ce |
|
BLAKE2b-256 | 6ff22bd30f0bbb482a1a6388436d2177fca0e7abfbd017632407329e5d71c3eb |