TCS-TR-B-15-11

Date: Mon Mar 9 00:22:47 2015

Title: Master's Thesis: Factorization of ZDDs for Fast Probability Calculation of Bayesian Networks

Authors: Shan Gao

Contact:

First name: Shan
Last name: Gao
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060- 0814, Japan
Email: gaoshan@ist.hokudai.ac.jp

Abstract. Multi-linear Functions (MLFs) is a well known way of probability calculation based on Bayesian Network (BN). For a givern BN, we can calculate the probability in a linear time to the size of MLF. However, the size of MLF grows exponentially with the size of BN, so the computation requires exponential time and space. Minato, et al. have shown an efficient method of calculating the probability by using Zero-Suppressed BDD (ZDD). This method is more effective than the conventional approach in some cases. In this article, we present an improvement of their method by utilizing d-separation structure of BN for efficient ZDD factorization based on weak-division operation.