• aolibMPE

aolibMPE

Computes the Most Probable Explanation in Bayesian networks.

Author

Radu_Marinescu

Description

The library contains the implementations of the Depth-First AND/OR Branch-and-Bound with caching (AOBB) as well as the Best-First AND/OR (AOBF) search algorithms. Both algorithms exploit the independencies revealed by the underlying graphical model by traversing the context minimal AND/OR search graph associated with the input Bayesian network.

The effectiveness of the depth-first and best-first AND/OR search algorithms depends on the quality of the heuristic evaluation functions. We provide a general scheme for generating heuristic estimates of varying strengths, automatically from the functional specification of the problem, based on the Mini-Bucket approximation. Naturally, more accurate heuristic estimates may yield a smaller search space, however at a much higher computational cost. Therefore, the right trade-off between the computational overhead at each node and the pruning power exhibited during search may be hard to predict.

The Mini-Bucket heuristics can be:

• pre-compiled before search (static Mini-Bucket heuristics), or

• generated dynamically, during search (dynamic Mini-Bucket heuristics).

Input format

The belief network and the evidence need to be specified in the Ergo_file_format.

For some example problems please see our Repository.

Usage

The algorithm is invoked with three (if no evidence present) or four (if evidence present) arguments:

aolibMPE <networkFile> [<evidenceFile>] <parameterFile> <outputFile>

with the following meaning:

• <networkFile> specifies the path to the network specification in Ergo_file_format.

• <evidenceFile> (optional) specifies the path to the evidence specification according to the Ergo_file_format.

• <parameterFile> specifies the path to the file containing custom parameters for the algorithm. See the example file that comes with the binary program file for syntax reference.

• <outputFile> specifies the path to the file to which (the logarithm of) the probability of the most probable explanation is written.

Detailed step-by-step instructions are available here.

Parameters

Parameters for the algorithm, which can be specified within the parameter file:

• h: (string) the heuristic to use for finding an variable elimination order by which to construct the AND/OR search space. The following values can be used:

  • minfill: to indicate the min-fill heuristic

  • hypergraph: to indicate the hypergraph partitioning heuristic

• a: (integer) specifies which algorithm to run. The following values can be used:

  • 3: AND/OR Branch-and-Bound with static mini-bucket heuristics (i.e., AOBB+SMB(i))
  • 4: AND/OR Branch-and-Bound with dynamic mini-bucket heuristics (i.e., AOBB+DMB(i))
  • 9: Best-First AND/OR search with static mini-bucket heuristics (i.e., AOBF+SMB(i))
    • available only for Windows
  • 10: Best-First AND/OR search with dynamic mini-bucket heuristics (i.e., AOBF+DMB(i))
    • available only for Windows

• ib: (integer) specifies the i-bound of the guiding mini-bucket heuristic.

• cb: (integer) specifies the cache bound used by AND/OR Branch-and-Bound algorithms.

• cs: (string) specifies the caching scheme used by AND/OR Branch-and-Bound algorithms. The following values can be used:

  • classic: to indicate the naive caching scheme

  • adaptive: to indicate the adaptive caching scheme

• l (integer) specifies the time limit in seconds. Default value is -1, which indicates no time limit.

Download

A 32-bit Linux binary and an example parameter file is available here.

Get the 32-bit Windows binary and an example parameter file here.

If you are interested in obtaining the source code, please contact the program author.

References

[1] Radu Marinescu and Rina Dechter. AND/OR Branch-and-Bound Search for Graphical Models. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2005. Link

[2] Radu Marinescu and Rina Dechter. Memory Intensive Branch-and-Bound Search in Graphical Models. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 2006. Link

[3] Radu Marinescu and Rina Dechter. Best-First AND/OR Search for Graphical Models. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 2007. Link

[4] Radu Marinescu and Rina Dechter. Best-First AND/OR Search for Most Probable Explanations. In Proceedings of the International Conference on Uncertainty in Artificial Intelligence (UAI), 2007. Link