A Hybrid Algorithm to Compute Marginal and Joint Beliefs in Bayesian Networks and Its Complexity
This work addresses computational efficiency in probabilistic inference for AI and machine learning, but it is incremental as it builds on existing methods and confirms prior conjectures.
The paper tackles the problem of computing marginal and joint beliefs in Bayesian Networks by proposing a hybrid algorithm that combines non-serial dynamic programming with the ability to retrieve beliefs for all single variables, saving an NP-hard computation step compared to using separate algorithms.
There exist two general forms of exact algorithms for updating probabilities in Bayesian Networks. The first approach involves using a structure, usually a clique tree, and performing local message based calculation to extract the belief in each variable. The second general class of algorithm involves the use of non-serial dynamic programming techniques to extract the belief in some desired group of variables. In this paper we present a hybrid algorithm based on the latter approach yet possessing the ability to retrieve the belief in all single variables. The technique is advantageous in that it saves a NP-hard computation step over using one algorithm of each type. Furthermore, this technique re-enforces a conjecture of Jensen and Jensen [JJ94] in that it still requires a single NP-hard step to set up the structure on which inference is performed, as we show by confirming Li and D'Ambrosio's [LD94] conjectured NP-hardness of OFP.