Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-16T21:13:49.575Z Has data issue: false hasContentIssue false
  • English
  • Français

Decomposable Probabilistic Influence Diagrams

Published online by Cambridge University Press:  27 July 2009

C. C. Chyu
C. C. Chyu
Affiliation:
Department of Industrial EngineeringUniversity of California, Berkely, California 94720 Yuan-Tze Institute of Technology, Taiwan
Get access Rights & Permissions [Opens in a new window]

Abstract

Probabilistic influence diagrams are a useful stochastic modeling tool. To calculate probabilities of interest relative to a probabilistic influence diagram efficiently, it will be helpful for us to use an associated decomposable-directed graph. We first explore and discuss some graph-theoretic and conditional independence properties of decomposable probabilistic influence diagrams. These properties are helpful in providing an efficient algorithm for obtaining a posterior decomposable probabilistic influence diagram given the state of one or more observed nodes. The connection between Shachter's “sequential creation of conditionally barren nodes” concept and Lauritzen and Spiegeihalter's “moralization and triangulation” algorithm for calculating probabilities relative to a probabilistic influence diagram is made explicit. We also discuss how to use wisely the concepts of “sequential creation of conditionally barren nodes” and “merging nodes” together with the graph-theoretic properties of decomposable directed graphs to compute probabilities relative to probabilistic influence diagrams.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 5 , Issue 2 , April 1991 , pp. 229 - 243
Copyright
Copyright © Cambridge University Press 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Almond, R. (1989). Fusion and propagation in graphical belief models. 01 1989, Research Report, S-121 revised, Department of Statistics, Harvard University, Cambridge, MA.Google Scholar
Andersen, S., Olesen, K., Jensen, F.V., & Jensen, F. (1989). HUGIN-A shell for building belief universe for expert systems. 11th International Joint Conference on Artificial Intelligence, Detroit, MI.Google Scholar
Barlow, R. (1988). Using influence diagrams. Accelerated Life Testing and Expert's Opinions in Reliability, Clarotti, C. and Lindley, D. (Eds.), Societa Italiana di Fisica, Bologna, Italy.Google Scholar
Barlow, R. & Pereira, C. (1990). Conditional independence and probabilistic influence diagrams, Topics in statistical dependence. IMS Lecture Note Series, 1–14.Google Scholar
Berge, C. (1973). Graphs and hypergraphs. Translated from French by Minieka, E.. Amsterdam: North-Holland Publishing Co.Google Scholar
Chyu, C. (1990). Computing probabilities for probabilistic influence diagrams. Ph.D thesis, IEOR Department, Berkeley, CA, 07.Google Scholar
Darroch, J., Lauritzen, S., & Speed, T. (1980). Markov fields and log-linear interaction models for contingency tables. Annals of Statistics 8: 522–539.CrossRefGoogle Scholar
Jensen, F., Olesen, K., & Andersen, S. (1988). An algebra of Bayesian belief universes for knowledge based systems, R−88−25, Institute of Electronic Systems, Aalborg University, Denmark.Google Scholar
Kiiveri, H., Speed, T., & Carlin, J. (1984). Recursive causal models. Journal of theAustralian Mathematics Society (Series A) 36: 30–52.Google Scholar
Lauritzen, S., Dawid, A., Larson, B., & Leimer, J. (1990). Independence properties of directed Markov fields. Networks 20: 491–505.CrossRefGoogle Scholar
Lauritzen, S. & Spiegeihalter, D. (1988). Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society 50(2): 157–224.Google Scholar
Lauritzen, S. & Wermuth, N. (1987). Mixed interaction models. Research Report R84−8, Institute for Elektroniske Systemer, Aalborg University center, Denmark, version 02.Google Scholar
Pearl, J. (1986). Fusion, propagation, and structuring in belief networks. Artificial Intelligence 29: 241–288.CrossRefGoogle Scholar
Rose, D., Tarjan, R., & Lueker, G. (1976). Algorithmic aspects of vertex elimination of graphs. SIAM Journal of Computing 5(2): 266–283, 06.CrossRefGoogle Scholar
Rose, D. (1970). Triangulated graphs and the elimination process. Journal of Mathematical Analysis and Applications 32: 597–609.CrossRefGoogle Scholar
Shachter, R. (1986). Evaluating influence diagrams. Operations Research 34: 871–882.CrossRefGoogle Scholar
Smith, J. (1989). Influence diagrams for statistical modelling. Annals of Statistics 17: 654–672.CrossRefGoogle Scholar
Tarjan, R. & Yannakakis, M. (1984). Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal of Computing 13(3): 566–579, 08.CrossRefGoogle Scholar
Wermuth, N. & Lauritzen, S. (1983). Graphical and recursive models for contingency tables. Biometrika 70: 553–557.CrossRefGoogle Scholar
Yannakakis, M. (1981). Computing the minimum fill-in is NP-complete. SIAM Journal of Algebraic Discrete Methods 2: 77–79.CrossRefGoogle Scholar