Fast Message Passing Algorithm Using ZDD-Based Local Structure Compilation

Masakazu Ishihata, Shan Gao, Shin-Ichi Minato
Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, PMLR 73:117-128, 2017.

Abstract

Compiling Bayesian Networks (BNs) into secondary structures to implement efficient exact inference is a hot topic in probabilistic modeling. One class of algorithms to compile BNs is to transform the BNs into junction tree structures utilizing the conditional dependency in the network. Performing message passing on the junction tree structure, we can calculate marginal probabilities for any variables in the network efficiently. However, the message passing algorithm does not consider the local structure in the network. Since the ability to exploit local structure to avoid redundant calculations has a significant impact on exact inference, in this article, we propose a fast message passing algorithm by exploiting local structure using Zero-suppressed Binary Decision Diagrams (ZDDs). We convert all the components used in message passing algorithm into Multi-linear Functions (MLFs), and then compile them into compact representation using ZDDs. We show that message passing on ZDDs can work more efficient than the conventional message passing algorithm on junction tree structures on some benchmark networks although it may be too memory consuming for some larger instances.

Cite this Paper


BibTeX
@InProceedings{pmlr-v73-shan-gao17a, title = {Fast Message Passing Algorithm Using ZDD-Based Local Structure Compilation}, author = {Ishihata, Masakazu and Gao, Shan and Minato, Shin-Ichi}, booktitle = {Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks}, pages = {117--128}, year = {2017}, editor = {Hyttinen, Antti and Suzuki, Joe and Malone, Brandon}, volume = {73}, series = {Proceedings of Machine Learning Research}, month = {20--22 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v73/shan-gao17a/shan-gao17a.pdf}, url = {https://proceedings.mlr.press/v73/shan-gao17a.html}, abstract = {Compiling Bayesian Networks (BNs) into secondary structures to implement efficient exact inference is a hot topic in probabilistic modeling. One class of algorithms to compile BNs is to transform the BNs into junction tree structures utilizing the conditional dependency in the network. Performing message passing on the junction tree structure, we can calculate marginal probabilities for any variables in the network efficiently. However, the message passing algorithm does not consider the local structure in the network. Since the ability to exploit local structure to avoid redundant calculations has a significant impact on exact inference, in this article, we propose a fast message passing algorithm by exploiting local structure using Zero-suppressed Binary Decision Diagrams (ZDDs). We convert all the components used in message passing algorithm into Multi-linear Functions (MLFs), and then compile them into compact representation using ZDDs. We show that message passing on ZDDs can work more efficient than the conventional message passing algorithm on junction tree structures on some benchmark networks although it may be too memory consuming for some larger instances. } }
Endnote
%0 Conference Paper %T Fast Message Passing Algorithm Using ZDD-Based Local Structure Compilation %A Masakazu Ishihata %A Shan Gao %A Shin-Ichi Minato %B Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks %C Proceedings of Machine Learning Research %D 2017 %E Antti Hyttinen %E Joe Suzuki %E Brandon Malone %F pmlr-v73-shan-gao17a %I PMLR %P 117--128 %U https://proceedings.mlr.press/v73/shan-gao17a.html %V 73 %X Compiling Bayesian Networks (BNs) into secondary structures to implement efficient exact inference is a hot topic in probabilistic modeling. One class of algorithms to compile BNs is to transform the BNs into junction tree structures utilizing the conditional dependency in the network. Performing message passing on the junction tree structure, we can calculate marginal probabilities for any variables in the network efficiently. However, the message passing algorithm does not consider the local structure in the network. Since the ability to exploit local structure to avoid redundant calculations has a significant impact on exact inference, in this article, we propose a fast message passing algorithm by exploiting local structure using Zero-suppressed Binary Decision Diagrams (ZDDs). We convert all the components used in message passing algorithm into Multi-linear Functions (MLFs), and then compile them into compact representation using ZDDs. We show that message passing on ZDDs can work more efficient than the conventional message passing algorithm on junction tree structures on some benchmark networks although it may be too memory consuming for some larger instances.
APA
Ishihata, M., Gao, S. & Minato, S.. (2017). Fast Message Passing Algorithm Using ZDD-Based Local Structure Compilation. Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, in Proceedings of Machine Learning Research 73:117-128 Available from https://proceedings.mlr.press/v73/shan-gao17a.html.

Related Material