Solving Influence Diagrams with Simple Propagation

Anders Læsø Madsen, Cory J. Butz, Jhonatan Oliveira, Andre E. dos Santos

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

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.
Original languageEnglish
Title of host publicationAdvances in Artificial Intelligence - 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, Proceedings
EditorsFrank Rudzicz, Marie-Jean Meurs
Number of pages12
Place of PublicationCham
PublisherSpringer
Publication date2019
Pages68-79
ISBN (Print)978-3-030-18304-2
ISBN (Electronic)978-3-030-18305-9
DOIs
Publication statusPublished - 2019
EventCanadian Conference on Artificial Intelligence - Kingston, Canada
Duration: 28 May 201931 May 2019

Conference

ConferenceCanadian Conference on Artificial Intelligence
CountryCanada
CityKingston
Period28/05/201931/05/2019
SeriesLecture Notes in Computer Science
Volume11489
ISSN0302-9743

Fingerprint

Message passing
Bayesian networks

Keywords

  • Discrete variables
  • Influence diagrams
  • Simple propagation

Cite this

Madsen, A. L., Butz, C. J., Oliveira, J., & dos Santos, A. E. (2019). Solving Influence Diagrams with Simple Propagation. In F. Rudzicz, & M-J. Meurs (Eds.), Advances in Artificial Intelligence - 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, Proceedings (pp. 68-79). Cham: Springer. Lecture Notes in Computer Science, Vol.. 11489 https://doi.org/10.1007/978-3-030-18305-9_6
Madsen, Anders Læsø ; Butz, Cory J. ; Oliveira, Jhonatan ; dos Santos, Andre E. / Solving Influence Diagrams with Simple Propagation. Advances in Artificial Intelligence - 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, Proceedings. editor / Frank Rudzicz ; Marie-Jean Meurs. Cham : Springer, 2019. pp. 68-79 (Lecture Notes in Computer Science, Vol. 11489).
@inproceedings{422f730ee13743cbb8ff400d33a322e0,
title = "Solving Influence Diagrams with Simple Propagation",
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.",
keywords = "Discrete variables, Influence diagrams, Simple propagation",
author = "Madsen, {Anders L{\ae}s{\o}} and Butz, {Cory J.} and Jhonatan Oliveira and {dos Santos}, {Andre E.}",
year = "2019",
doi = "10.1007/978-3-030-18305-9_6",
language = "English",
isbn = "978-3-030-18304-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "68--79",
editor = "Frank Rudzicz and Marie-Jean Meurs",
booktitle = "Advances in Artificial Intelligence - 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, Proceedings",
address = "Germany",

}

Madsen, AL, Butz, CJ, Oliveira, J & dos Santos, AE 2019, Solving Influence Diagrams with Simple Propagation. in F Rudzicz & M-J Meurs (eds), Advances in Artificial Intelligence - 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, Proceedings. Springer, Cham, Lecture Notes in Computer Science, vol. 11489, pp. 68-79, Canadian Conference on Artificial Intelligence, Kingston, Canada, 28/05/2019. https://doi.org/10.1007/978-3-030-18305-9_6

Solving Influence Diagrams with Simple Propagation. / Madsen, Anders Læsø; Butz, Cory J.; Oliveira, Jhonatan; dos Santos, Andre E.

Advances in Artificial Intelligence - 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, Proceedings. ed. / Frank Rudzicz; Marie-Jean Meurs. Cham : Springer, 2019. p. 68-79 (Lecture Notes in Computer Science, Vol. 11489).

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Solving Influence Diagrams with Simple Propagation

AU - Madsen, Anders Læsø

AU - Butz, Cory J.

AU - Oliveira, Jhonatan

AU - dos Santos, Andre E.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Discrete variables

KW - Influence diagrams

KW - Simple propagation

U2 - 10.1007/978-3-030-18305-9_6

DO - 10.1007/978-3-030-18305-9_6

M3 - Article in proceeding

SN - 978-3-030-18304-2

T3 - Lecture Notes in Computer Science

SP - 68

EP - 79

BT - Advances in Artificial Intelligence - 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, Proceedings

A2 - Rudzicz, Frank

A2 - Meurs, Marie-Jean

PB - Springer

CY - Cham

ER -

Madsen AL, Butz CJ, Oliveira J, dos Santos AE. Solving Influence Diagrams with Simple Propagation. In Rudzicz F, Meurs M-J, editors, Advances in Artificial Intelligence - 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019, Proceedings. Cham: Springer. 2019. p. 68-79. (Lecture Notes in Computer Science, Vol. 11489). https://doi.org/10.1007/978-3-030-18305-9_6