Lifted Division for Lifted Hugin Belief Propagation

Hoffmann, Moritz; Braun, Tanya; Möller, Ralf

Research article in edited proceedings (conference)

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.

Details zur Publikation

Book title: AISTATS-22 Proceedings of the 25th International Conference on Artificial Intelligence and Statistics
Release year: 2022
Language in which the publication is written: English
Event: Digital
Link to the full text: https://proceedings.mlr.press/v151/hoffmann22a.html