Join Graph Decomposition Bounds for Influence Diagrams

Junkyu Lee, Alexander Ihler, Rina Dechter
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:1052-1061, 2018.

Abstract

We introduce a new decomposition method for bounding the maximum expected utility of in- fluence diagrams. While most current schemes use reductions to the Marginal Map task over a Bayesian Network, our approach is direct, aim- ing to avoid the large explosion in the model size that often results by such reductions. In this paper, we extend to influence diagrams the principles of decomposition methods that were applied earlier to probabilistic inference, uti- lizing an algebraic framework called valuation algebra which effectively captures both multi- plicative and additive local structures present in influence diagrams. Empirical evaluation on four benchmarks demonstrates the effectiveness of our approach compared to reduction-based approaches and illustrates significant improve- ments in the upper bounds on maximum ex- pected utility.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-lee18a, title = {Join Graph Decomposition Bounds for Influence Diagrams}, author = {Lee, Junkyu and Ihler, Alexander and Dechter, Rina}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {1052--1061}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/lee18a/lee18a.pdf}, url = {https://proceedings.mlr.press/r16/lee18a.html}, abstract = {We introduce a new decomposition method for bounding the maximum expected utility of in- fluence diagrams. While most current schemes use reductions to the Marginal Map task over a Bayesian Network, our approach is direct, aim- ing to avoid the large explosion in the model size that often results by such reductions. In this paper, we extend to influence diagrams the principles of decomposition methods that were applied earlier to probabilistic inference, uti- lizing an algebraic framework called valuation algebra which effectively captures both multi- plicative and additive local structures present in influence diagrams. Empirical evaluation on four benchmarks demonstrates the effectiveness of our approach compared to reduction-based approaches and illustrates significant improve- ments in the upper bounds on maximum ex- pected utility.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Join Graph Decomposition Bounds for Influence Diagrams %A Junkyu Lee %A Alexander Ihler %A Rina Dechter %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-lee18a %I PMLR %P 1052--1061 %U https://proceedings.mlr.press/r16/lee18a.html %V R16 %X We introduce a new decomposition method for bounding the maximum expected utility of in- fluence diagrams. While most current schemes use reductions to the Marginal Map task over a Bayesian Network, our approach is direct, aim- ing to avoid the large explosion in the model size that often results by such reductions. In this paper, we extend to influence diagrams the principles of decomposition methods that were applied earlier to probabilistic inference, uti- lizing an algebraic framework called valuation algebra which effectively captures both multi- plicative and additive local structures present in influence diagrams. Empirical evaluation on four benchmarks demonstrates the effectiveness of our approach compared to reduction-based approaches and illustrates significant improve- ments in the upper bounds on maximum ex- pected utility. %Z Reissued by PMLR on 04 October 2026.
APA
Lee, J., Ihler, A. & Dechter, R.. (2018). Join Graph Decomposition Bounds for Influence Diagrams. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:1052-1061 Available from https://proceedings.mlr.press/r16/lee18a.html. Reissued by PMLR on 04 October 2026.

Related Material