Premium
An ordered examination of influence diagrams
Author(s) -
Shachter Ross D.
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230200505
Subject(s) - influence diagram , observability , computer science , representation (politics) , diagram , set (abstract data type) , inference , probabilistic logic , graphical model , theoretical computer science , algorithm , mathematical optimization , mathematics , data mining , decision tree , artificial intelligence , database , politics , political science , law , programming language
Influence diagrams are a directed network representation for decision making under uncertainty. The nodes in the diagram represent uncertain and decision variables, and the arcs indicate probabilistic dependence and observability. This paper examines the graphical orderings underlying the influence diagram and the primitive interchange operations that can reorder the network. These operations are sufficient to determine the maximal independent set and minimal relevant sets for any given inference problem, and a linear time algorithm is developed to obtain those sets. This framework is also used to examine and explain properties of the time structure of general influence diagrams with decisions.