TCS-TR-A-06-18Date: Mon Jul 3 14:26:17 2006 Title: Compiling Bayesian Networks by Symbolic Probability Calculation Using Zero-suppressed BDDs Authors: Shin-ichi Minato, Ken Satoh, and Taisuke Sato Contact:
Abstract. Compiling Bayesian networks (BNs) is one of the hot topics in the area of probabilistic modeling and processing. In this paper, we propose a new method of compiling BNs into multi-linear functions (MLFs) based on Zero-suppressed BDDs (ZBDDs), which are the graph-based representation of combinatorial item sets. Our method is different 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 ZBDD-based symbolic probability calculation. The MLF may have an exponential size, 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 to the ZBDD size. Our method is not necessary to generate the MLF for the whole network, but we can extract MLFs for only a part of network related to the query, to avoid unnecessary calculation of redundant terms of MLFs. We show experimental results for some typical benchmark examples. Although our algorithm is simply based on the mathematical definition of probability calculation, the performance is competitive to the existing state-of-the-art method. ©Copyright 2006 Authors |