Analysis of Three Bayesian Network Inference Algorithms: Variable Elimination, Likelihood Weighting, and Gibbs Sampling
📜 Abstract
In this paper, we describe and analyze three Bayesian network inference algorithms: variable elimination, likelihood weighting, and Gibbs sampling. Variable Elimination is an exact inference algorithm, while likelihood weighting and gibbs sampling are approximate inference algorithms. For each algorithm we study thier performance under different conditions. In section 2, we analyze variable elimination and study how different elimination orders affect performance. In section 3, we validate and describe our likelihood weghting implementation. In section 4 we analyze Gibbs sampling and experiment with the effect of burn-in (length of the initial prefix that is thrown away) on estimation accuracy. In section 5 we measure the performance of the two approximate inference algorithms in terms of their running times versus the quality of their results. We also draw conclusions on which algorithm is more appropriate for the different bayesian networks. In section 6, we describe another take on the study of how burn-in affects Gibbs sampling performance.
✨ Summary
The paper is an empirical comparison of exact variable elimination with two approximate Bayesian-network inference methods: likelihood weighting and Gibbs sampling. It validates implementations against known results, measures error using Kullback–Leibler divergence, studies the effect of elimination ordering on exact inference, and examines burn-in and sample counts for Gibbs sampling. The experiments report that elimination ordering can dominate variable-elimination runtime; a greedy ordering is usually effective but is not guaranteed to be optimal. Likelihood weighting and Gibbs sampling both become more accurate as sample counts increase, while Gibbs sampling generally benefits from an initial burn-in period. The paper also emphasizes that the best method depends on the network and query: variable elimination performed well on the tested Carpo and Burglary cases, whereas sampling was more practical for the tested Insurance cases. The authors note that the reported timings are implementation-dependent.
A web search found later works that cite the paper as background or a reference, including a 2014 article on Bayesian-network click-through-rate prediction and a 2019 University of National Colombia working paper on comparing Bayesian inference algorithms. (onlinelibrary.wiley.com) The paper also appears as assigned reading in a Bayesian-network and probabilistic-inference course guide. (faculty.ist.psu.edu) These sources document continued educational and bibliographic reuse, but the search did not identify evidence that this paper directly introduced a widely adopted algorithm, software system, or major subsequent research direction.