Peter Norvig on Decision Networks - Dictionary of Arguments
Norvig I 626
Decision Networks/influence diagrams/AI research/Norvig/Russell: Decision networks combine Bayesian networks with additional node types for actions and utilities. (Cf. Howard and Matheson, 1984(2)). In its most general form, a decision network represents information about the agent’s current state, its ossible actions, the state that will result from the agent’s action, and the utility of that state. It therefore provides a substrate for implementing utility-based agents (…). E.g. the problem of the siting of an airport (>Multi-attribute utility/AI Research).
Chance nodes: (…) represent random variables, just as they do in Bayesian networks. The agent could be uncertain about the construction cost, the level of air traffic and the potential for litigation, (…). Each chance node has associated with it a conditional distribution that is indexed by the state of the parent nodes. In decision networks, the parent nodes can include decision nodes as well as chance nodes.
Decision nodes: (…) represent points where the decision maker has a choice of
Norvig I 627
actions. The choice influences the cost, safety, and noise that will result.
Utility nodes/value nodes: (…) represent the agent’s utility function. The utility node has as parents all variables describing the outcome that directly affect utility. Associated with the utility node is a description of the agent’s utility as a function of the parent attributes. >Information value/Norvig.
Norvig I 638
Decision theory has been a standard tool in economics, finance, and management science since the 1950s. Until the 1980s, decision trees were the main tool used for representing simple decision problems. Smith (1988)(1) gives an overview of the methodology of decision analysis. Influence diagrams were introduced by Howard and Matheson (1984)(2), based on earlier work at SRI (Miller et al., 1976)(3). Howard and Matheson’s method involved the
Norvig I 639
derivation of a decision tree from a decision network, but in general the tree is of exponential size. Shachter (1986)(4) developed a method for making decisions based directly on a decision network, without the creation of an intermediate decision tree. This algorithm was also one of the first to provide complete inference for multiply connected Bayesian networks. Zhang et al. (1994)(5) showed how to take advantage of conditional independence of information to reduce the size of trees in practice; they use the term decision network for networks that use this approach (although others use it as a synonym for influence diagram). Nilsson and Lauritzen (2000)(6) link algorithms for decision networks to ongoing developments in clustering algorithms for Bayesian networks. Koller and Milch (2003)(7) show how influence diagrams can be used to solve games that involve gathering information by opposing players, and Detwarasiti and Shachter (2005)(8) show how influence diagrams can be used as an aid to decision making for a team that shares goals but is unable to share all information perfectly. The collection by Oliver and Smith (1990)(9) has a number of useful articles on decision networks, as does the 1990 special issue of the journal Networks.
1. Smith, J. Q. (1988). Decision Analysis. Chapman and Hall.
2. Howard, R. A. and Matheson, J. E. (1984). Influence diagrams. In Howard, R. A. and Matheson,
J. E. (Eds.), Readings on the Principles and Applications of Decision Analysis, pp. 721–762. Strategic
3. Miller, A. C., Merkhofer, M. M., Howard, R. A., Matheson, J. E., and Rice, T. R. (1976). Development of automated aids for decision analysis. Technical report, SRI International.
4. Shachter, R. D. (1986). Evaluating influence diagrams. Operations Research, 34, 871–882.
5. Zhang, N. L., Qi, R., and Poole, D. (1994). A computational theory of decision networks. IJAR, 11,
6. Nilsson, D. and Lauritzen, S. (2000). Evaluating influence diagrams using LIMIDs. In UAI-00, pp. 436–445.
7. Koller, D. and Milch, B. (2003). Multi-agent influence diagrams for representing and solving games.
Games and Economic Behavior, 45, 181–221.
8. Detwarasiti, A. and Shachter, R. D. (2005). Influence diagrams for team decision analysis. Decision
Analysis, 2(4), 207–228.
9. Oliver, R. M. and Smith, J. Q. (Eds.). (1990). Influence Diagrams, Belief Nets and Decision Analysis.
Wiley._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010