Bayesian networks (BNs) are a basis for uncertainty representation, reasoning, and learning in artificial intelligence and related disciplines. Advances in algorithmic work with BNs rely on careful experimentation.

When evaluating a new BN inference algorithm it is important to know the difficulty of the BNs that are used. Likewise, a BN learning algorithm constructs a BN from a data set. In creating new BN learning algorithms, one method of testing them is to start with a BN and use it to generate this data set. A key factor in this approach is knowing the difficulty of the BN that is to be learned. This talk describes an approach to generating BNs of increasing difficulty. Building on previous research, we present and analyze two approaches, the bipartite (BPART) and multipartite (MPART) algorithms, and present novel results regarding their relationship. We consider a few structural and distributional input parameters of the BPART and MPART algorithms and show how varying them can significantly impact the generated Bayesian networks and the hardness of inference, with emphasis on the tree clustering algorithm. Among the parameters we analyze are the ratio of the number of root nodes V to the number of non-root nodes C in the network (the C/V-ratio), the regularity of the underlying graph, and the conditional probability tables. An easy-hard-harder pattern as a function of increasing C/V-ratio is found for both BPART and MPART networks.

This talk includes joint work with Dan Roth at University at Illinois and David Wilkins at Stanford University.