We are concerned with algorithms for solving reasoning problems over graphical models, which includes common tasks for belief, constraint, and mixed networks. In the following we present some of the resulting work; this list is bound to grow over time.
See our Repository for some example problem instances.
These algorithms compute the exact probability of a given set of evidence in a Bayesian network.
aolibPE computes the exact probability of evidence for Bayesian networks using AND/OR search spaces.
Bucket_Elimination performs variable elimination to obtain the exact probability of evidence.
VEC performs variable elimination plus conditioning to obtain the exact probability of evidence.
These algorithms compute the approximate probability of a given set of evidence in a Bayesian network.
IJGPIS computes approximate probability of evidence in Bayesian networks using importance sampling, Iterative Join Graph Propagation (IJGP) and Relational Consistency.
IJGPSampleSearch computes approximate probability of evidence in Bayesian networks using importance sampling, SampleSearch and Iterative Join Graph Propagation (IJGP).
Approximate Belief Updating (or posterior marginals)
These algorithms compute approximate beliefs for each variable in a network, given a certain set of evidence.
IJGP (Iterative Join Graph Propagation) computes approximate beliefs in Bayesian networks.
IJGPIS computes approximate beliefs in Bayesian networks using importance sampling, Iterative Join Graph Propagation (IJGP) and Relational Consistency.
IJGPSampleSearch computes approximate beliefs in Bayesian networks using importance sampling, SampleSearch and Iterative Join Graph Propagation (IJGP).
Compilation of AND/OR Multi-Valued Decision Diagrams (AOMDDs)
This algorithm compiles a weighted CSP or Bayesian network into an AOMDD.
aomdd compiles AOMDDs for weighted CSPs or Bayesian networks using AND/OR search.
These algorithms compute the most likely tuple in a Bayesian network given some evidence.
aolibMPE implements several exact AND/OR search algorithms to compute the most probable explanation in Bayesian networks using Mini-Bucket heuristics and caching.
mbeMPE implements the Mini-Bucket approximation of the most probable explanation in Bayesian networks.
DAOOPT is a new implementation of AND/OR Branch-and-Bound to solve MPE problems over Bayes and Markov networks. It also offers a Mini-Bucket heuristic, full caching, Breadth-Rotate AOBB for improved anytime performance, as well as stochastic local search for preprocessing. Full source code is available under GPL.
DAOOPT-UAI12 is a version of the above solver using MBE code by Alex Ihler. In addition to the features of the DAOOPT, it includes cost-shifting schemes to tighten the problem formulation and the bounds produced by MBE algorithm.
W-SEARCH implements several AND/OR search algorithms that use weighted heuristics to produce a w-optimal approximate solution to a most probable explanation problem in Bayesian or Markov networks, namely a solution guaranteed to be within the factor of w from the optimal (on logarithmic scale).
These algorithms compute the m-most likely tuples and the corresponding probabilities in a Bayesian or Markov network, reporting the solutions in the non-increasing order of the probabilities.
MBE-M-OPT uses Mini-Bucket elimination approach to compute bounds on the m-best solutions to the most probable explanation or MAP task in Bayesian or Markov networks.
M-BEST-SEARCH implements several exact best-first and depth-first branch and bound search algorithms to compute the m-best solutions to a most probable explanation in Bayesian or Markov networks using Mini-Bucket heuristics, exploring both OR and AND/OR search spaces.
These algorithms compute an optimal assignment in a weighted constraint satisfaction problem given some evidence.
aolibWCSP finds the optimal solution to weighted constraint satisfaction problems via various AND/OR search algorithms using Mini-Bucket heuristics and caching.
mbeWCSP implements the Mini-Bucket approximation for weighted constraint satisfaction problems.
This algorithm computes an optimal solution to an integer programming problem.
aolibILP computes the optimal solution to 0/1 integer linear programs using AND/OR search.
General purpose algorithms
Computing Elimination Orderings
CVO implements the Iterative Greedy Variable Ordering (IGVO) algorithm.
This algorithm decomposes a given graphical model (Bayesian, Markov or constraint network) into a tree decomposition.
quickbb A complete anytime algorithm to compute tree decomposition of a graph.
treeDecomp computes a tree decomposition of a given graphical model.
REES offers a GUI to create and edit graphical models and implements a number of algorithms. It is no longer actively developed.
Disclaimer: All software should be regarded as in development and is made available on an "as-is" basis, without warranty of any kind. It has in no way been thoroughly tested and might not function as intended or expected.