Bayesian-Inference as Model-Counting Benchmarks


These benchmark problems are from Solving Bayesian Networks by Weighted Model Counting, by Tian Sang, Paul Beame, and Henry Kautz, Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05), Pittsburgh, PA, 2005.


The problems are available in several formats:

Some of the problems in dne or bif format require an evidence file. These are provided in XML format.

The Grid Networks and Deterministic-QMR problems were first encoded as Bayesian networks, and then translated to weighted model counting using our program bif2cnf, which may be downloaded as a Linux binary.

The Plan Recognition problems were created by a modified version of the blackbox planning system. It directly output both cnf and dne format. The cnf encoding is essentially the same as blackbox's ordinary satisfiability encoding. The dne encoding adds dummy nodes and evidence in order to represent clauses.

The Benchmarks

Grid Networks

A grid network is an N x N grid, where there are two directed edges from a node to its neighbors right and down. The upper-left node is a source, and the bottom-right node is a sink. The query is to compute the probability of the sink being true given no evidence. The deterministic ratio is a parameter specifying the fraction of nodes that are deterministic, that is, whose values are determined given the values of their parents. There are 10 random instances generated for each size. 

Plan Recognition Problems

Given prior probabilities on actions and facts, the task is to compute marginal probabilities on all variables. Goals and initial conditions are observed true. Bayesian networks are generated from the plan graphs, where addional nodes (all observed false) are added to represent mutex, action-effect and preconditions of actions. Because the values of weights on variables do not affect Cachet's trace and performance, all weights are assumed to be 0.5, which is the default value and therefore is omitted in the cnf encoding. A detailed example of encoding a 4-step logistics problem is included in the archive.

Deterministic QMR

Each problem is given by a two layer bipartite network in which the top layer consists of diseases and the bottom layer consists of symptoms. If a disease may result a symptom, there is an edge from the disease to the
symptom. In the CPTs for DQMR (unlike those of QMR-DT) a symptom is completely determined by the diseases that cause it; {\em i.e.}, it is modeled as an OR rather than a noisy OR of its inputs. As in QMR-DT, every disease has an independent prior probability. For our experiments, we varied the numbers of diseases and symptoms from 50 to 100 and chose the edges of the bipartite graph randomly, with each symptom caused by four randomly chosen diseases. The problem was to compute the marginal probabilities for all the diseases given a set of consistent observations of symptoms. The size of the observation set varied between 10% to 30% of all symptoms.

Return to the Cachet home page