TY - JOUR

T1 - Controlled generation of hard and easy Bayesian networks

T2 - Impact on maximal clique size in tree clustering

AU - Mengshoel, Ole J.

AU - Wilkins, David C.

AU - Roth, Dan

N1 - Funding Information:
The research reported here was largely conducted while Ole J. Mengshoel was at the University of Illinois, Urbana-Champaign. Ole J. Mengshoel and David C. Wilkins gratefully acknowledge support in part by ONR Grant N00014- 95-1-0749, ARL Grant DAAL01-96-2-0003, and NRL Grant N00014-97-C-2061. Dan Roth gratefully acknowledges the support of NSF grants IIS-9801638 and SBR-987345. Vadim Bulitko, David Fried, Song Han, William Hsu, Brent Spillner, and anonymous reviewers are acknowledged for comments related to this work. David Fried, Song Han, and Misha Voloshin are acknowledged for their co-development of the software used in the experiments.

PY - 2006/11

Y1 - 2006/11

N2 - This article presents and analyzes algorithms that systematically generate random Bayesian networks of varying difficulty levels, with respect to inference using tree clustering. The results are relevant to research on efficient Bayesian network inference, such as computing a most probable explanation or belief updating, since they allow controlled experimentation to determine the impact of improvements to inference algorithms. The results are also relevant to research on machine learning of Bayesian networks, since they support controlled generation of a large number of data sets at a given difficulty level. Our generation algorithms, called BPART and MPART, support controlled but random construction of bipartite and multipartite Bayesian networks. The Bayesian network parameters that we vary are the total number of nodes, degree of connectivity, the ratio of the number of non-root nodes to the number of root nodes, regularity of the underlying graph, and characteristics of the conditional probability tables. The main dependent parameter is the size of the maximal clique as generated by tree clustering. This article presents extensive empirical analysis using the Hugin tree clustering approach as well as theoretical analysis related to the random generation of Bayesian networks using BPART and MPART.

AB - This article presents and analyzes algorithms that systematically generate random Bayesian networks of varying difficulty levels, with respect to inference using tree clustering. The results are relevant to research on efficient Bayesian network inference, such as computing a most probable explanation or belief updating, since they allow controlled experimentation to determine the impact of improvements to inference algorithms. The results are also relevant to research on machine learning of Bayesian networks, since they support controlled generation of a large number of data sets at a given difficulty level. Our generation algorithms, called BPART and MPART, support controlled but random construction of bipartite and multipartite Bayesian networks. The Bayesian network parameters that we vary are the total number of nodes, degree of connectivity, the ratio of the number of non-root nodes to the number of root nodes, regularity of the underlying graph, and characteristics of the conditional probability tables. The main dependent parameter is the size of the maximal clique as generated by tree clustering. This article presents extensive empirical analysis using the Hugin tree clustering approach as well as theoretical analysis related to the random generation of Bayesian networks using BPART and MPART.

KW - Bayesian networks

KW - C / V-ratio

KW - Controlled experiments

KW - Maximal clique size

KW - Probabilistic reasoning

KW - Random generation

KW - Tree clustering inference

UR - http://www.scopus.com/inward/record.url?scp=33750631759&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750631759&partnerID=8YFLogxK

U2 - 10.1016/j.artint.2006.09.003

DO - 10.1016/j.artint.2006.09.003

M3 - Article

AN - SCOPUS:33750631759

SN - 0004-3702

VL - 170

SP - 1137

EP - 1174

JO - Artificial Intelligence

JF - Artificial Intelligence

IS - 16-17

ER -