AAAI Publications, Twenty-Second International FLAIRS Conference

Font Size: 
Join Tree Propagation Utilizing Both Arc Reversal and Variable Elimination
Cory James Butz, Ken Konkel, Pawan Lingras

Last modified: 2009-03-18

Abstract


In this paper, we put forth the first join tree propagation algorithm  that selectively applies either arc reversal (AR) or variable elimination (VE) to build the propagated messages. Our approach utilizes a recent method for identifying the propagated join tree messages \`{a} priori. When it is determined that precisely one message is to be constructed at a join tree node, VE is utilized to build this distribution; otherwise, AR is applied as it is better suited to construct multiple distributions passed between  neighboring join tree nodes. Experimental results, involving evidence processing in  seven real-world and one benchmark Bayesian network,  empirically demonstrate that selectively applying VE and AR is faster than applying one of these methods exclusively on the entire network.

Full Text: PDF