Join Graph Decomposition Bounds for Influence Diagrams
Junkyu Lee, Alexander Ihler, Rina Dechter · Uncertainty in Artificial Intelligence · 2018
We introduce a new decomposition methods for bounding the maximum expected utility of influence diagrams. The main goal is to devise an approximation scheme that is free from translations that are required by existing variational approaches. since a naive reduction from influence diagrams to Bayesian networks produces practically infeasible problems. In this work, we extend decomposition methods for the probabilistic inference by using an algebraic framework called valuation algebra which effectively captures both multiplicative and additive local structure presents in IDs. Empirical evaluation on four benchmark sets demonstrates the effectiveness of our approach compared to the translation based methods. In addition, proposed decomposition method significantly improves partition based approximation schemes with lower computational resources.