Implementation of Belief Propagation (BP) message passing for:
- Ising model (
- Minimum weight perfect matching (
- Minimum weight perfect b-matching (
Package is still experimental and not thoroughly tested, use it at your own risk. Code contributions are very welcome!
Problem instances can be created using Erdos graph library. Problems are passed to BP methods as Network objects with features attached to edges and vertices.
using BeliefPropagation.Ising using Erdos # Create Ising model on ErdosRenyi graph # with random couplings and constant external field. net = erdos_renyi(100, 0.02, Network) eprop!(net, "J", e -> randn()) vprop!(net, "H", v -> 1) ## Run Belief Propagation at some temperature ### and extract magnetizations fg = Ising.run_bp(net, T=2, maxiters=100); fg.mags
using BeliefPropagation.Matching using Erdos using LinearAlgebra # Create an instance of the random assignment problem net = CompleteBipartiteGraph(100, 100, Network) pos = [rand(2) for i in 1:nv(net)] eprop!(net, "w", e -> norm(pos[src(e)] .- pos[dst(e)])) ## Run Belief Propagation and obtain optimal cost and matching E, match = Matching.run_bp(net, maxiters=100);
The algorithm is guaranteed to return exact solutions only on bipartite graphs (altough it may also work on non-bipartite).
Solve an instance of the minimum-weight perfect b-matching problem.
using BeliefPropagation.BMatching using Erdos using LinearAlgebra # Create an instance of the random assignment problem net = CompleteGraph(100, Network) eprop!(net, "w", e -> rand()) vprop!(net, "b", v -> rand(1:5)) ## Run Belief Propagation and obtain optimal cost and matching E, match = BMatching.run_bp(net, maxiters=100);
- SAT.jl: a BP solver for SAT problems.
- ForneyLab.jl: Bayesian inference algorithms through message passing on Forney-style factor graphs.
- BinaryCommitteeMachineFBP.jl: Focusing Belief Propagation on commitee machines (neural network with one-hidden layer and a single output) with binary weights.
Problems to be implemented:
- Low Density Parity Check codes (LDPC)
- Potts models
- Steiner tree
Computation of Bethe free energies is also missing.