Lifted Division for Lifted Hugin Belief Propagation
Moritz P. Hoffmann, Tanya Braun, Ralf Möller
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.
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. }
}