Final results of the evaluation

Description:

Over the years, many different algorithms for making queries of probability distributions represented by graphical models have been developed. There are now a number of algorithms for exact inference (e.g., junction-tree based schemes using graph triangulations, search or conditioning based approaches based on SAT/CSP techniques), and approximation methods (including variational, generalized belief propagation, and sampling schemes). Also, aspects of software implementation, such as relevant data structures, memory management, and subsidiary algorithms, can have a significant effect on actual runtime.

The purpose of this evaluation is to compare the performance of a variety of different software systems on a single set of Bayesian network (BN) problems. A number of different Bayesian networks will be made available to each participant, and each will be evaluated according to the following:

1. Exact inference only. While approximate inference is crucial in many problem domains, recent results have shown that exact inference can still be performed on a variety of interesting (and thought previously to be intractable) problems. Therefore, this first UAI competition will involve systems that perform exact inference only (meaning everyone's probability score should be numerically identical).
2. Discrete state space. All observed and hidden variables will be discrete, but will have widely varying cardinalities.
3. Evaluation will involve both wall-clock run time, and amount of memory used. Both fastest time with a memory ceiling, and smallest memory with a time limit will be evaluated.
4. Several forms of query will be possible to evaluate, including Probability(evidence) (i.e., summing out hidden variables), MPE, and MAP. The resulting scores/assignments for all queries must be correct and accurate.
5. A set of complete Bayesian network models will be made available. Some of the BNs will be strictly positive (meaning there will be no zeros in the CPTs). Other BNs will be mixtures of dense, sparse, and deterministic CPTs.
6. We will evaluate only single threaded performance (i.e., no multi-threading or parallelism in this first evaluation). We will use the same underlying (Intel-class) microprocessor running the Linux operating system for all systems. Each process will have a 2GB memory limitation.
7. Two types of BNs will be evaluated, static and dynamic (as in dynamic Bayesian networks). They will be placed in a standard easy-to-read format (to be determined).

We encourage each participant (or any interested party) to submit a BN of their own to be considered for evaluation (but we do not make guarantees that any particular BN will be used). All the resulting BNs used in the competition, and all results, will be listed on the UAI web after the competition is over (this will encourage continued standardized evaluation).