Fast Arc-Reversal

Cory J. Butz, Anders L. Madsen, Jhonatan S. Oliveira
Proceedings of The 12th International Conference on Probabilistic Graphical Models, PMLR 246:93-105, 2024.

Abstract

Fast arc-reversal (FAR) is proposed as a new exact inference algorithm in discrete Bayesian networks (BNs), merging favourable features of Arc-reversal (AR) and Variable elimination (VE). AR constantly maintains a sub-BN structure when rendering a variable barren via arc reversals, requiring more computational effort than VE, which sacrifices a sub-BN structure by directly eliminating a variable. We formally establish that FAR can recover a unique and sound sub-BN structure after consecutive variable eliminations. Experimental results on real-world benchmark networks empirically show a substantial improvement in the average run-time and variance of FAR compared to AR. We also suggest a novel method, called d-contraction, for graphically understanding FAR since FAR is not always the same as a sequence of arc reversals.

Cite this Paper

BibTeX
@InProceedings{pmlr-v246-butz24a, title = {Fast Arc-Reversal}, author = {Butz, Cory J. and Madsen, Anders L. and Oliveira, Jhonatan S.}, booktitle = {Proceedings of The 12th International Conference on Probabilistic Graphical Models}, pages = {93--105}, year = {2024}, editor = {Kwisthout, Johan and Renooij, Silja}, volume = {246}, series = {Proceedings of Machine Learning Research}, month = {11--13 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v246/main/assets/butz24a/butz24a.pdf}, url = {https://proceedings.mlr.press/v246/butz24a.html}, abstract = {Fast arc-reversal (FAR) is proposed as a new exact inference algorithm in discrete Bayesian networks (BNs), merging favourable features of Arc-reversal (AR) and Variable elimination (VE). AR constantly maintains a sub-BN structure when rendering a variable barren via arc reversals, requiring more computational effort than VE, which sacrifices a sub-BN structure by directly eliminating a variable. We formally establish that FAR can recover a unique and sound sub-BN structure after consecutive variable eliminations. Experimental results on real-world benchmark networks empirically show a substantial improvement in the average run-time and variance of FAR compared to AR. We also suggest a novel method, called d-contraction, for graphically understanding FAR since FAR is not always the same as a sequence of arc reversals.} }
Endnote
%0 Conference Paper %T Fast Arc-Reversal %A Cory J. Butz %A Anders L. Madsen %A Jhonatan S. Oliveira %B Proceedings of The 12th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2024 %E Johan Kwisthout %E Silja Renooij %F pmlr-v246-butz24a %I PMLR %P 93--105 %U https://proceedings.mlr.press/v246/butz24a.html %V 246 %X Fast arc-reversal (FAR) is proposed as a new exact inference algorithm in discrete Bayesian networks (BNs), merging favourable features of Arc-reversal (AR) and Variable elimination (VE). AR constantly maintains a sub-BN structure when rendering a variable barren via arc reversals, requiring more computational effort than VE, which sacrifices a sub-BN structure by directly eliminating a variable. We formally establish that FAR can recover a unique and sound sub-BN structure after consecutive variable eliminations. Experimental results on real-world benchmark networks empirically show a substantial improvement in the average run-time and variance of FAR compared to AR. We also suggest a novel method, called d-contraction, for graphically understanding FAR since FAR is not always the same as a sequence of arc reversals.
APA
Butz, C.J., Madsen, A.L. & Oliveira, J.S.. (2024). Fast Arc-Reversal. Proceedings of The 12th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 246:93-105 Available from https://proceedings.mlr.press/v246/butz24a.html.

Related Material