Simple Propagation with Arc-Reversal in Bayesian Networks

Anders Madsen, Cory J. Butz, Jhonatan S. Oliveira, André E. Santos
Proceedings of the Ninth International Conference on Probabilistic Graphical Models, PMLR 72:260-271, 2018.

Abstract

Simple Propagation is a recently introduced algorithm for inference in discrete Bayesian networks using message passing in a junction tree. Simple Propagation is similar to Lazy Propagation, but uses the simple {\itshape one in, one out}-principle when computing messages between cliques of the junction tree instead of using a more in-depth graphical analysis of the set of potentials. In this paper, we describe how to apply Arc-Reversal (AR) as the marginalization algorithm during message passing in Simple Propagation. We consider both discrete and hybrid Bayesian networks, where the continuous variables are assumed to be Conditional Linear Gaussian (CLG). The use of AR eliminates the need for complex matrix operations in case of CLG networks, while offering opportunities to exploit additional independence and irrelevance properties in both cases when compared to Variable Elimination (VE). The performance of Simple Propagation with AR has been evaluated on a set of real-world Bayesian networks with discrete variables and hybrid Bayesian networks constructed by randomly replacing discrete variables with continuous variables under the CLG constraints. The performance of Simple Propagation with AR is compared with the performance of Lazy Propagation with AR. The results of the experimental performance analysis of Simple Propagation with AR are encouraring.

Cite this Paper

BibTeX
@InProceedings{pmlr-v72-madsen18a, title = {Simple Propagation with Arc-Reversal in Bayesian Networks}, author = {Madsen, Anders and Butz, Cory J. and Oliveira, Jhonatan S. and dos Santos, Andr\'{e} E.}, booktitle = {Proceedings of the Ninth International Conference on Probabilistic Graphical Models}, pages = {260--271}, year = {2018}, editor = {Kratochvíl, Václav and Studený, Milan}, volume = {72}, series = {Proceedings of Machine Learning Research}, month = {11--14 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v72/madsen18a/madsen18a.pdf}, url = {https://proceedings.mlr.press/v72/madsen18a.html}, abstract = {Simple Propagation is a recently introduced algorithm for inference in discrete Bayesian networks using message passing in a junction tree. Simple Propagation is similar to Lazy Propagation, but uses the simple {\itshape one in, one out}-principle when computing messages between cliques of the junction tree instead of using a more in-depth graphical analysis of the set of potentials. In this paper, we describe how to apply Arc-Reversal (AR) as the marginalization algorithm during message passing in Simple Propagation. We consider both discrete and hybrid Bayesian networks, where the continuous variables are assumed to be Conditional Linear Gaussian (CLG). The use of AR eliminates the need for complex matrix operations in case of CLG networks, while offering opportunities to exploit additional independence and irrelevance properties in both cases when compared to Variable Elimination (VE). The performance of Simple Propagation with AR has been evaluated on a set of real-world Bayesian networks with discrete variables and hybrid Bayesian networks constructed by randomly replacing discrete variables with continuous variables under the CLG constraints. The performance of Simple Propagation with AR is compared with the performance of Lazy Propagation with AR. The results of the experimental performance analysis of Simple Propagation with AR are encouraring.} }
Endnote
%0 Conference Paper %T Simple Propagation with Arc-Reversal in Bayesian Networks %A Anders Madsen %A Cory J. Butz %A Jhonatan S. Oliveira %A André E. Santos %B Proceedings of the Ninth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2018 %E Václav Kratochvíl %E Milan Studený %F pmlr-v72-madsen18a %I PMLR %P 260--271 %U https://proceedings.mlr.press/v72/madsen18a.html %V 72 %X Simple Propagation is a recently introduced algorithm for inference in discrete Bayesian networks using message passing in a junction tree. Simple Propagation is similar to Lazy Propagation, but uses the simple {\itshape one in, one out}-principle when computing messages between cliques of the junction tree instead of using a more in-depth graphical analysis of the set of potentials. In this paper, we describe how to apply Arc-Reversal (AR) as the marginalization algorithm during message passing in Simple Propagation. We consider both discrete and hybrid Bayesian networks, where the continuous variables are assumed to be Conditional Linear Gaussian (CLG). The use of AR eliminates the need for complex matrix operations in case of CLG networks, while offering opportunities to exploit additional independence and irrelevance properties in both cases when compared to Variable Elimination (VE). The performance of Simple Propagation with AR has been evaluated on a set of real-world Bayesian networks with discrete variables and hybrid Bayesian networks constructed by randomly replacing discrete variables with continuous variables under the CLG constraints. The performance of Simple Propagation with AR is compared with the performance of Lazy Propagation with AR. The results of the experimental performance analysis of Simple Propagation with AR are encouraring.
APA
Madsen, A., Butz, C.J., Oliveira, J.S. & Santos, A.E.. (2018). Simple Propagation with Arc-Reversal in Bayesian Networks. Proceedings of the Ninth International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 72:260-271 Available from https://proceedings.mlr.press/v72/madsen18a.html.

Related Material