NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Collections About News Help Login
Back to Results
Understanding the Scalability of Bayesian Network Inference using Clique Tree Growth CurvesBayesian networks (BNs) are used to represent and efficiently compute with multi-variate probability distributions in a wide range of disciplines. One of the main approaches to perform computation in BNs is clique tree clustering and propagation. In this approach, BN computation consists of propagation in a clique tree compiled from a Bayesian network. There is a lack of understanding of how clique tree computation time, and BN computation time in more general, depends on variations in BN size and structure. On the one hand, complexity results tell us that many interesting BN queries are NP-hard or worse to answer, and it is not hard to find application BNs where the clique tree approach in practice cannot be used. On the other hand, it is well-known that tree-structured BNs can be used to answer probabilistic queries in polynomial time. In this article, we develop an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs, specifically: (i) the ratio of the number of a BN's non-root nodes to the number of root nodes, or (ii) the expected number of moral edges in their moral graphs. Our approach is based on combining analytical and experimental results. Analytically, we partition the set of cliques in a clique tree into different sets, and introduce a growth curve for each set. For the special case of bipartite BNs, we consequently have two growth curves, a mixed clique growth curve and a root clique growth curve. In experiments, we systematically increase the degree of the root nodes in bipartite Bayesian networks, and find that root clique growth is well-approximated by Gompertz growth curves. It is believed that this research improves the understanding of the scaling behavior of clique tree clustering, provides a foundation for benchmarking and developing improved BN inference and machine learning algorithms, and presents an aid for analytical trade-off studies of clique tree clustering using growth curves.
Document ID
20090033938
Acquisition Source
Ames Research Center
Document Type
Preprint (Draft being sent to journal)
Authors
Mengshoel, Ole Jakob (Carnegie-Mellon Univ. Pittsburgh, PA, United States)
Date Acquired
August 24, 2013
Publication Date
June 24, 2009
Subject Category
Cybernetics, Artificial Intelligence And Robotics
Report/Patent Number
ARC-E-DAA-TN307
Funding Number(s)
CONTRACT_GRANT: NNA08205346R
CONTRACT_GRANT: NCC2-1426
CONTRACT_GRANT: NNA07BB97C
Distribution Limits
Public
Copyright
Public Use Permitted.

Related Records

There are no records associated with this record.
No Preview Available