Some New Empirical Analysis of Evaluating of Iterative Join-Graph Propagation

Emma Rollon and Rina Dechter

In previous works authors showed that IBP (or equivalently, the more general class of algorithm called IJGP) is sound with respect to the inference of zero beliefs. In this report, we empirically investigate the behaviour of IBP/IJGP for near zero inferred beliefs. Specifically, we explore the hypothesis that if IBP infers that the belief of a variable is close to zero, then this inference is relatively accurate. The study includes some previously published empirical results and signifcant new analysis of empirical evaluation carried on in UAI 2006 and UAI 2008 benchmarks. We will see that while our empirical results support the hypothesis on benchmarks having no determinism, the results are quite mixed for networks with determinism.