A Time and Space Efficient Junction Tree Architecture
This work addresses efficiency improvements for researchers and practitioners using probabilistic graphical models, though it appears incremental as it builds on existing Shafer-Shenoy and Hugin architectures.
The paper tackles the trade-off between time and space complexities in the junction tree algorithm for computing marginals of boolean multivariate probability distributions, introducing two novel architectures (ARCH-1 and ARCH-2) that achieve the speed of Hugin propagation with low space requirements, with ARCH-2 offering significantly faster performance in cases of large vertices of high degree.
The junction tree algorithm is a way of computing marginals of boolean multivariate probability distributions that factorise over sets of random variables. The junction tree algorithm first constructs a tree called a junction tree who's vertices are sets of random variables. The algorithm then performs a generalised version of belief propagation on the junction tree. The Shafer-Shenoy and Hugin architectures are two ways to perform this belief propagation that tradeoff time and space complexities in different ways: Hugin propagation is at least as fast as Shafer-Shenoy propagation and in the cases that we have large vertices of high degree is significantly faster. However, this speed increase comes at the cost of an increased space complexity. This paper first introduces a simple novel architecture, ARCH-1, which has the best of both worlds: the speed of Hugin propagation and the low space requirements of Shafer-Shenoy propagation. A more complicated novel architecture, ARCH-2, is then introduced which has, up to a factor only linear in the maximum cardinality of any vertex, time and space complexities at least as good as ARCH-1 and in the cases that we have large vertices of high degree is significantly faster than ARCH-1.