Affiliations: Department of Automation, Tsinghua University, Beijing 100084, China. {djw10@mails, chenfeng@mail, huoyy09@mails, liuhong07@mails}.tsinghua.edu.cn
Note: [] This work was supported by National Natural Science Foundation of China (Project No.61071131 and Project No.61271388), Beijing Natural Science Foundation (No.4122040), Research Project of Tsinghua University (No.2012Z01011) and United Technologies Research Center (UTRC). Address for correspondence: Department of Automation, Tsinghua University, Beijing 100084, China
Abstract: This paper proposes a new method, conditional probability table (CPT) decomposition, to analyze the independent and deterministic components of CPT. This method can be used to approximate and analyze Baysian networks. The decomposition of Bayesian networks is accomplished by representing CPTs as a linear combination of extreme CPTs, which forms a new framework to conduct inference. Based on this new framework, inference in Bayesian networks can be done by decomposing them into less connected and weighted subnetworks. We can achieve exact inference if the original network is decomposed into singly-connected subnetworks. Besides, approximate inference can be done by discarding the subnetworks with small weights or by a partial decomposition and application of belief propagation (BP) on the still multiply-connected subnetworks. Experiments show that the decomposition-based approximation outperforms BP in most cases.
Keywords: Bayesian network, conditional probability table, inference, decomposition
