jti and sparta: Time and Space Efficient Packages for Model-Based Prediction in Large Bayesian Networks

Abstract

A Bayesian network is a multivariate (potentially very high dimensional) probabilistic model formed by combining lower-dimensional components. In Bayesian networks, the computation of conditional probabilities is fundamental for model-based predictions. This is usually done based on message passing algorithms that utilize conditional independence structures. In this paper, we deal with a specific message passing algorithm that exploits a second structure called a junction tree and hence is known as the junction tree algorithm (JTA). In Bayesian networks for discrete variables with finite state spaces, there is a fundamental problem in high dimensions: A discrete distribution is represented by a table of values, and in high dimensions, such tables can become prohibitively large. In JTA, such tables must be multiplied which can lead to even larger tables. The jti package meets this challenge by using the package sparta by implementing methods that efficiently handle multiplication and marginalization of sparse tables through JTA. The two packages are written in the R programming language and are freely available from the Comprehensive R Archive Network.