mbforbes / py-factorgraph Goto Github PK

Factor graphs and loopy belief propagation implemented in Python

License: MIT License

Python 100.00%

factor-graph factor graph loopy-belief-propagation lbp sum-product

py-factorgraph's Introduction

py-factorgraph

This is a tiny python library that allows you to build factor graphs and run the (loopy) belief propagation algorithm with ease. It depends only on numpy.

Installation

pip install factorgraph

Example

Code (found in examples/simplegraph.py)

import numpy as np
import factorgraph as fg

# Make an empty graph
g = fg.Graph()

# Add some discrete random variables (RVs)
g.rv('a', 2)
g.rv('b', 3)

# Add some factors, unary and binary
g.factor(['a'], potential=np.array([0.3, 0.7]))
g.factor(['b', 'a'], potential=np.array([
        [0.2, 0.8],
        [0.4, 0.6],
        [0.1, 0.9],
]))

# Run (loopy) belief propagation (LBP)
iters, converged = g.lbp(normalize=True)
print('LBP ran for %d iterations. Converged = %r' % (iters, converged))
print()

# Print out the final messages from LBP
g.print_messages()
print()

# Print out the final marginals
g.print_rv_marginals(normalize=True)

Run with python -m examples.simplegraph. Output:

LBP ran for 3 iterations. Converged = True

Current outgoing messages:
	b -> f(b, a) 	[ 0.33333333  0.33333333  0.33333333]
	f(a) -> a 	[ 0.3  0.7]
	a -> f(a) 	[ 0.23333333  0.76666667]
	a -> f(b, a) 	[ 0.3  0.7]
	f(b, a) -> b 	[ 0.34065934  0.2967033   0.36263736]
	f(b, a) -> a 	[ 0.23333333  0.76666667]

Marginals for RVs (normalized):
a
	 0 	 0.11538461538461539
	 1 	 0.8846153846153845
b
	 0 	 0.34065934065934067
	 1 	 0.29670329670329676
	 2 	 0.3626373626373626

Visualization

You can use factorgraph-viz to visualize factor graphs interactively in your web browser.

Tests

pip install pytest-cov coveralls
py.test --cov=factorgraph tests/

Projects using `py-factorgraph`

Open an issue or send a PR if you'd like your project listed here.

verbphysics

Contributing

There's plenty of low-hanging fruit to work on if you'd like to contribute to this project. Here are some ideas:

Unit tests
Auto-generated python docs (what's popular these days?)
Performance: measure bottlenecks and improve them (ideas: numba; parallelization for large graphs;)
Remove or improve ctrl-C catching (the E_STOP)
Cleaning up the API (essentially duplicate constructors for RVs and Factors within the Graph code; probably should have a node superclass for RVs and Factors that pulls out common code).

Releasing

Notes for myself on how to release new versions:

# Bump version in setup.py. Then,
python setup.py sdist
pip install twine
twine upload dist/*

Thanks

to Matthew R. Gormley and Jason Eisner for the Structured Belief Propagation for NLP Tutorial, which was extremely helpful for me in learning about factor graphs and understanding the sum product algorithm.
to Ryan Lester for pyfac, whose tests I used directly to test my implementation

py-factorgraph's People

Contributors

Stargazers

Watchers

py-factorgraph's Issues

Why loopy in the example?

In my understanding, the loopy BP is suitd to cyclic graph while the BP is suited to acyclic graph.
The loop BP will conduct the message passing in the cyclic graph repeatedly until convergence, while the BP only conduct one forward propagation and one backpropagation between all leafs and one randomly selected root.
In your example, the factor graph contains two RVs and two factors, which present as an acyclic graph, but it seems that you conduct a loopy BP algorithm as follow:

        while cur_iter < max_iters and not converged and not E_STOP:
            # Bookkeeping
            cur_iter += 1

            if progress:
                # self.print_messages(nodes)
                logger.debug('\titeration %d / %d (max)', cur_iter, max_iters)

            # Comptue outgoing messages:
            converged = True
            for n in nodes:
                n_converged = n.recompute_outgoing(normalize=normalize)
                converged = converged and n_converged

Is there anything wrong with my understanding on the belief propagation algorithm or the example?

Python 3 on pypi?

Hi there

Any plans to release the Python 3 version of this onto PyPI? I believe the PyPI version is still on 0.0.2 from 2017 which looks like Python 2 to me?

Thanks a lot

potential param of fg.Graph().factor() and porting to pomegranate

Hi @mbforbes @hyanwong ,
I'm wondering if you could comment on how to port (to do runtime analysis) of a fg model with the library pomegranate. Specifically, if we take your example in README how would you port that to a BayesianNetwork() in pomegranate to do LBP for comparison? The crux of the issue is the interpretation of the potential param for the fg.Graph().factor(), can you explain and perhaps comment on the porting (here is an example of pomegranate interface: https://pomegranate.readthedocs.io/en/latest/BayesianNetwork.html).
Thanks!

g.factor(['a'], potential=np.array([0.3, 0.7])) is wrong?

In the example, condition probability should be g.factor(['b'], potential=np.array([0.x, 0.x, 0.x])), not factor 'a', right ?

Why the marginals for 'a' is not normalized in the example?

After running the example, the marginal for 'b' is normalized while the one for 'a' is not normalized. Why?

Marginals for RVs:
a
         0       0.07
         1       0.5366666666666666
b
         0       0.3406593406593406
         1       0.2967032967032967
         2       0.36263736263736257

Issue with example provided

In the example result the marginal probability of 'a' doesn't normalize to 1?

Why 'a' send message to 'f(a)'?

Thank you very much for your codes, it really help my research a lot!

In my understanding, the factor graph in the example is shown above. According the sum-product algorithm, if we want to compute the marginal probability, the messages from the factors to the rvs need to be computed. But in the printed results of the example, the messages from the factors to the rvs are computed. Why? Is this redundant?