aolibPE
The aolibPE package performs exact inference in Bayesian networks. Specifically, it computes the probability of the evidence.
Author
Description
The aolibPE package is based on AND/OR search spaces for graphical models, a framework that is developed by our group. AND/OR search exploits the independencies captured by the interaction graph of a problem. A small example is provided below.
A Bayesian network over variables A,B,C,D and E is defined by the conditional probability tables given below. The directed acyclic graph (DAG) shows some independencies between these variables, for example E is independent of {C,D} given {A,B}. A pseudo tree that spans the DAG guides the AND/OR search. The AND/OR search tree is given below. The black labels on the OR-to-AND arcs are probabilities from the original tables, and the red labels near each node are the values computed by the algorithm. In this problem the evidence is D=1 and E=0. The final value of the root node is the actual probability of the evidence.
The aolibPE is actually a family of algorithms. Besides AND/OR search, it is also based on AND/OR cutset conditioning, Bucket Elimination and constraint propagation.
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 four arguments:
aolibPE <networkFile> <evidenceFile> <parameterFile> <outputFile>
with the following meaning:
<networkFile> specifies the path to the problem network specification in Ergo_file_format.
<evicendeFile> 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 below for a list of parameters and refer to the example file that comes with the binary program file.
<outputFile> specifies the path to the file to which (the logarithm of) the probability of evidence is written.
Detailed step-by-step instructions are available here.
Parameters
Parameters for the algorithm, which can be specified within the parameter file:
elim: (integer) the elimination order employed to obtain the variable ordering by which to construct the And/Or search space:
- 10: weighted min-fill ordering.
iBound: (integer) specifies the cache bound (maximum number of variables in a cache table).
be: (boolean 0/1):
- 0: do not use Bucket Elimination for subproblems that fits in memory bound.
- 1: switch to Bucket Elimination for subproblems that fits in memory bound.
usePruning: (integer):
- 0: no constraint propagation.
- 1: forward checking.
- 2: relational forward checking
Download
A 32-bit Linux binary and an example parameter file is available here.
A 32-bit Windows binary and an example parameter file will be available shortly.
References
[1] AND/OR Search Spaces for Graphical Models. Rina Dechter and Robert Mateescu. In Artificial Intelligence Journal, Vol. 171, No. 2-3, pages 73-106, 2007. Link
[2] Mixtures of Deterministic-Probabilistic Networks and their AND/OR Search Space. Rina Dechter and Robert Mateescu. In proceedings of The Twentieth Conference on Uncertainty in Artificial Intelligence (UAI), 2004. Link
[3] AND/OR Cutset Conditioning. Robert Mateescu and Rina Dechter. In proceedings of The Nineteenth International Joint Conference on Artificial Intelligence (IJCAI), 2005. Link
[4] The Relationship Between AND/OR Search Spaces and Variable Elimination. Robert Mateescu and Rina Dechter. In proceedings of The Twenty First Conference on Uncertainty in Artificial Intelligence (UAI), 2005. Link