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


  • 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:

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.

©Copyright 2015 Authors