Lifted Division for Lifted Hugin Belief Propagation

Moritz P. Hoffmann, Tanya Braun, Ralf Möller
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:6501-6510, 2022.

Abstract

The lifted junction tree algorithm (LJT) is an inference algorithm that allows for tractable inference regarding domain sizes. To answer multiple queries efficiently, it decomposes a first-order input model into a first-order junction tree. During inference, degrees of belief are propagated through the tree. This propagation significantly contributes to the runtime complexity not just of LJT but of any tree-based inference algorithm. We present a lifted propagation scheme based on the so-called Hugin scheme whose runtime complexity is independent of the degree of the tree. Thereby, lifted Hugin can achieve asymptotic speed improvements over the existing lifted Shafer-Shenoy propagation. An empirical evaluation confirms these results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-hoffmann22a, title = { Lifted Division for Lifted Hugin Belief Propagation }, author = {Hoffmann, Moritz P. and Braun, Tanya and M\"oller, Ralf}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {6501--6510}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/hoffmann22a/hoffmann22a.pdf}, url = {https://proceedings.mlr.press/v151/hoffmann22a.html}, abstract = { The lifted junction tree algorithm (LJT) is an inference algorithm that allows for tractable inference regarding domain sizes. To answer multiple queries efficiently, it decomposes a first-order input model into a first-order junction tree. During inference, degrees of belief are propagated through the tree. This propagation significantly contributes to the runtime complexity not just of LJT but of any tree-based inference algorithm. We present a lifted propagation scheme based on the so-called Hugin scheme whose runtime complexity is independent of the degree of the tree. Thereby, lifted Hugin can achieve asymptotic speed improvements over the existing lifted Shafer-Shenoy propagation. An empirical evaluation confirms these results. } }
Endnote
%0 Conference Paper %T Lifted Division for Lifted Hugin Belief Propagation %A Moritz P. Hoffmann %A Tanya Braun %A Ralf Möller %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-hoffmann22a %I PMLR %P 6501--6510 %U https://proceedings.mlr.press/v151/hoffmann22a.html %V 151 %X The lifted junction tree algorithm (LJT) is an inference algorithm that allows for tractable inference regarding domain sizes. To answer multiple queries efficiently, it decomposes a first-order input model into a first-order junction tree. During inference, degrees of belief are propagated through the tree. This propagation significantly contributes to the runtime complexity not just of LJT but of any tree-based inference algorithm. We present a lifted propagation scheme based on the so-called Hugin scheme whose runtime complexity is independent of the degree of the tree. Thereby, lifted Hugin can achieve asymptotic speed improvements over the existing lifted Shafer-Shenoy propagation. An empirical evaluation confirms these results.
APA
Hoffmann, M.P., Braun, T. & Möller, R.. (2022). Lifted Division for Lifted Hugin Belief Propagation . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:6501-6510 Available from https://proceedings.mlr.press/v151/hoffmann22a.html.

Related Material