Compiling Bayesian Networks by Symbolic Probability Calculation Based on Zero-suppressed BDDs

Shin-ichi Minato, Ken Satoh, Taisuke Sato

Compiling Bayesian networks (BNs) is a hot topic within probabilistic modeling and processing. In this paper, we propose a new method for compiling BNs into Multi-Linear Functions (MLFs) based on Zero-suppressed Binary Decision Diagrams (ZBDDs), which are a graph-based representation of combinatorial item sets. Our method differs from the original approach of Darwiche et al., which encodes BNs into Conjunctive Normal Forms (CNFs) and then translates CNFs into factored MLFs. Our approach directly translates a BN into a set of factored MLFs using a ZBDD-based symbolic probability calculation. The MLF may have exponential computational complexity, but our ZBDD-based data structure provides a compact factored form of the MLF, and arithmetic operations can be executed in a time almost linear with the ZBDD size. In our method, it is not necessary to generate the MLF for the whole network, as we can extract MLFs for only part of the network related to the query, avoiding unnecessary calculation of redundant MLF terms. We present experimental results for some typical benchmark examples. Although our algorithm is simply based on the mathematical definition of probability calculation, performance is competitive to existing state-of-the-art methods.