From influence diagrams to junction trees

ABSTRACT

We present an approach to the solution of decision problems formulated as influence diagrams. This approach involves a special triangulation of the underlying graph, the construction of a junction tree with special properties, and a message passing algorithm operating on the junction tree for computation of expected utilities and optimal decision policies.

References

1. Andersen, S. K., Olesen, K. G., Jensen, F. V., and Jonson, F. (1989). Hugin--a shell for building Bayesian belief universes for expert systems. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, pages 1080-1085, Detroit, Michigan.
2. Beeri, C., Fagin, R., Maier, D., and Yannakakis, M. (1983). On the desirability of acyclic database schemes. Journal of the ACM, 30(3):479-513.
3. Howard, R. A. and Matheson, J. E. (1981). Influence diagrams. In Howard, R. A. and Matheson, J. E., editors, Readings on the Principles and Applications of Decision Analysis, pages 719-762. Strategic Decisions Group, Menlo Park, California.
4. Jenson, F. V., Lauritzen, S. L., and Olesen, K. G. (1990). Bayesian updating in causal probabilistic networks by local computations. Computational Statistics Quarterly, 4:269-282.
5. Kjærulff, U. (1990). Triangulation of graphs--algorithms giving small total state space. Research Report R-90-09, Department of Mathematics and Computer Science, Aalborg University, Denmark.
6. Lauritzen, S. L. and Spiegelhalter, D. J. (1988). Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society, Series B (Methodological), 50(2):157-224.
7. Leimer, H.-G. (1989). Triangulated graphs with marked vertices. In Andersen, L. D., Jakobsen, I. T., Thomassen, C., Tort, B., and Vestergaard, P. D., editors, Graph Theory in Memory of G. A. Dirac, volume 41 of Annals of Discrete Mathematics, pages 311-324. Elsevier Science Publishers, Amsterdam, The Netherlands.
8. Ndilikilikesha, P. (1994). Potential influence diagrams. International Journal of Approximate Reasoning, 10(3).
9. Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo, California.
10. Rose, D. J. (1970). Triangulated graphs and the elimination process. Journal of Mathematical Analysis and Applications, 32(3):597-609.
11. Shachter, R. D. (1986). Evaluating influence diagrams. Operations Research, 34(6):871-882.
12. Shachter, R. D. and Ndilikilikesha, P. (1993). Using potential influence diagrams for probabilistic inference and decision making. In Heckerman, D. and Mamdani, A., editors, Proceedings of the Ninth Conference on Uncertainty in Artificial Intelligence, pages 383-390, Washington, D. C. Morgan Kanfmann, San Mateo, California.
13. Shachter, R. D. and Peot, M. A. (1992). Decision making using probabilistic inference methods. In Dubois, D., Wellman, M. P., D'Ambrosio, B., and Smets, P., editors, Proceedings of the Eighth Conference on Uncertainty in Artificial Intelligence, pages 276-283, Stanford, California. Morgan Kaufmann, San Mateo, California.
14. Shenoy, P. P. (1992). Valuation-based systems for Bayesian decision analysis. Operations Research, 40(3):463-484.
15. Tatman, J. A. and Shachter, R. D. (1990). Dynamic programming and influence diagrams. IEEE Transactions on Systems, Man, and Cybernetics, 20(2):365-579.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Probabilistic reasoning

      • Vagueness and fuzzy logic

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Trees

• Theory of computation

  • Logic