Top

Published in:

2019 | OriginalPaper | Chapter

Solving Influence Diagrams with Simple Propagation

Authors : Anders L. Madsen, Cory J. Butz, Jhonatan Oliveira, André E. dos Santos

Published in: Advances in Artificial Intelligence

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Recently, Simple Propagation was introduced as an algorithm for belief update in Bayesian networks using message passing in a junction tree. The algorithm differs from other message passing algorithms such as Lazy Propagation in the message construction process. The message construction process in Simple Propagation identifies relevant potentials and variables to eliminate using the one-in, one-out-principle. This paper introduces Simple Propagation as a solution algorithm for influence diagrams with discrete variables. The one-in, one-out-principle is not directly applicable to influence diagrams. Hence, the principle is extended to cope with decision variables, utility functions, and precedence constraints to solve influence diagrams. Simple Propagation is demonstrated on an extensive example and a number of useful and interesting properties of the algorithm are described.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Personality Extraction Through LinkedIn

next chapter Uncertain Evidence for Probabilistic Relational Models

Howard, R.A., Matheson, J.E.: Influence diagrams. In: Readings in Decision Analysis, pp. 763–771. Strategic Decisions Group, Menlo Park (1981)

Kjærulff, U.B., Madsen, A.L.: Bayesian Networks and Influence Diagrams: A Guide to Construction and Analysis, 2nd edn. Springer, New York (2013). https://doi.org/10.1007/978-0-387-74101-7

Koller, D., Friedman, N.: Probabilistic Graphical Models — Principles and Techniques. MIT Press, Cambridge (2009)MATH

Lauritzen, S.L., Nilsson, D.: Representing and solving decision problems with limited information. Manage. Sci. 47, 1238–1251 (2001)CrossRef

Jensen, F.V., Vomlelova, M.: Unconstrained influence diagrams. In: Proceedings of Uncertainty in Artificial Intelligence Conference, pp. 234–241 (2002)

Madsen, A.L., Jensen, F.: Mixed influence diagrams. In: Nielsen, T.D., Zhang, N.L. (eds.) ECSQARU 2003. LNCS (LNAI), vol. 2711, pp. 208–219. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45062-7_17CrossRef

Nilsson, D., Jensen, F.V.: Probabilities of future decisions. In: Bouchon-Meunier, B., Yager, R.R., Zadeh, L.A. (eds.) Information, Uncertainty and Fusion. The Springer International Series in Engineering and Computer Science, vol. 516, pp. 161–171. Springer, Boston (2000). https://doi.org/10.1007/978-1-4615-5209-3_12CrossRef

Olmsted, S.M.: On representing and solving decision problems. Ph.D. thesis, Department of Engineering-Economic Systems, Stanford University, Stanford, CA (1983)

Shachter, R.D.: Evaluating influence diagrams. Oper. Res. 34(6), 871–882 (1986)MathSciNetCrossRef

10.

Shachter, R.D., Peot, M.A.: Decision making using probabilistic inference methods. In: Proceedings of the Eighth Conference on Uncertainty in Artificial Intelligence, pp. 276–283. Morgan Kaufmann Publishers, San Mateo (1992)

11.

Shenoy, P.P.: Valuation-based systems for Bayesian decision analysis. Oper. Res. 40(3), 463–484 (1992)MathSciNetCrossRef

12.

Jensen, F., Jensen, F.V., Dittmer, S.: From influence diagrams to junction trees. In: Proceedings of Uncertainty in Artificial Intelligence Conference, pp. 367–373. Morgan Kaufmann Publishers, San Francisco (1994)

13.

Madsen, A.L., Jensen, F.V.: Lazy evaluation of symmetric Bayesian decision problems. In: Proceedings of Uncertainty in Artificial Intelligence Conference, pp. 382–390 (1999)

14.

Cooper, G.F.: A method for using belief networks as influence diagrams. In: Proceedings of Uncertainty in Artificial Intelligence Conference, pp. 55–63 (1988)

15.

Yang, M., Zhou, L., Ruan, H.: The methods for solving influence diagrams: a review. In: International Conference on Information Technology and Applications, pp. 427–431 (2013)

16.

Jensen, F.V., Nielsen, T.D.: Probabilistic decision graphs for optimization under uncertainty. 4OR-Q J. Oper. Res. 9(1), 1–28 (2011)MathSciNetCrossRef

17.

Lee, J., Ihler, A., Dechter, R.: Join graph decomposition bounds for influence diagrams. In: Proceedings of Uncertainty in Artificial Intelligence Conference, pp. 1053–1062 (2018)

18.

Yet, B., Neil, M., Fenton, N., Constantinou, A., Demetiev, E.: An improved method for solving hybrid influence diagrams. IJAR 95, 93–112 (2018)MathSciNetMATH

19.

Butz, C.J., de Oliveira, J.S., dos Santos, A.E., Madsen, A.L.: Bayesian network inference with simple propagation. In: Proceedings of Florida Artificial Intelligence Research Society Conference, pp. 650–655 (2016)

20.

Madsen, A.L., Jensen, F.V.: Lazy propagation: a junction tree inference algorithm based on lazy evaluation. Artif. Intell. 113(1–2), 203–245 (1999)MathSciNetCrossRef

21.

Cabañas, R., Cano, A., Gómez-Olmedo, M., Madsen, A.L.: On SPI-lazy evaluation of influence diagrams. In: van der Gaag, L.C., Feelders, A.J. (eds.) PGM 2014. LNCS (LNAI), vol. 8754, pp. 97–112. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11433-0_7CrossRef

22.

Madsen, A.L., Nilsson, D.: Solving influence diagrams using HUGIN, Shafer-Shenoy and lazy propagation. In: Proceedings of Uncertainty in Artificial Intelligence Conference, pp. 337–345 (2001)

23.

Nielsen, T.D., Jensen, F.V.: Welldefined decision scenarios. In: Proceedings of Uncertainty in Artificial Intelligence Conference, pp. 502–511 (1999)

24.

Nielsen, T.D.: Decomposition of influence diagrams. In: Benferhat, S., Besnard, P. (eds.) ECSQARU 2001. LNCS (LNAI), vol. 2143, pp. 144–155. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44652-4_14CrossRef

Title: Solving Influence Diagrams with Simple Propagation
Authors: Anders L. Madsen
Cory J. Butz
Jhonatan Oliveira
André E. dos Santos
Publisher: Springer International Publishing
Book: Advances in Artificial Intelligence
Print ISBN: 978-3-030-18304-2

Electronic ISBN: 978-3-030-18305-9

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-18305-9_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner