Equivalent Characterization of a Class of Conditional Probabilistic Independencies

  • S. K. M. Wong
  • C. J. Butz
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 1424)


Markov networks utilize nonembedded probabilistic conditional independencies in order to provide an economical representation of a joint distribution in uncertainty management. In this paper we study several properties of nonembedded conditional independencies and show that they are in fact equivalent. The results presented here not only show the useful characteristics of an important subclass of probabilistic conditional independencies, but further demonstrate the relationship between relational theory and probabilistic reasoning.


Conditional Independency Joint Probability Distribution Fact Equivalent Bayesian Belief Network Markov Network 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Beeri, C. and Fagin, R. and Maier, D. and Yannakakis, M.: On the Desirability of Acyclic Database Schemes. J. ACM 30(3) (1983) 479–513zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Cooper, G.F.: The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks. Artificial Intelligence. 42 (1990) 393–402CrossRefzbMATHMathSciNetGoogle Scholar
  3. 3.
    Dagum, P., Luby, M.: Approximating Probabilistic Inference in Bayesian Belief Networks is NP-hard. Artificial Intelligence. 60(1) (1993) 141–153zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Fagin, R.: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Transactions on Database Systems. 2(3) (1977) 262–278CrossRefMathSciNetGoogle Scholar
  5. 5.
    Hajek, P., Havranek, T., Jirousek, R.: Uncertain Information Processing in Expert Systems. CRC Press. (1992)Google Scholar
  6. 6.
    Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann. San Francisco, California. (1988)Google Scholar
  7. 7.
    Shafer, G.: An Axiomatic Study of Computation in Hypertrees. University of Kansas. School of Business Working Papers (232). (1991)Google Scholar
  8. 8.
    Studeny, M.: Conditional Independence Relations Have No Finite Complete Characterization. Eleventh Prague Conference on Information Theory, Statistical Decision Foundation and Random Processes. (1990)Google Scholar
  9. 9.
    Wong, S.K.M., Wang, Z.W.: On Axiomatization of Probabilistic Conditional Independence. Tenth Conference on Uncertainty in Artificial Intelligence. (1994) 591–597Google Scholar
  10. 10.
    Wong, S.K.M., Butz, C.J., Xiang, Y.: A Method for Implementing a Probabilistic Model as a Relational Database. Eleventh Conference on Uncertainty in Artificial Intelligence. (1995) 556–564Google Scholar
  11. 11.
    Wong, S.K.M.: Testing Implication of Probabilistic Dependencies. Twelfth Conference on Uncertainty in Artificial Intelligence. (1996) 545–553Google Scholar
  12. 12.
    Wong, S.K.M.: The Relational Structure of Belief Networks. (submitted for publication) (1997)Google Scholar
  13. 13.
    Wong, S.K.M.: An Extended Relational Data Model for Probabilistic Reasoning. Journal of Intelligent Information Systems. 9 (1997) 181–202CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1998

Authors and Affiliations

  • S. K. M. Wong
    • 1
  • C. J. Butz
    • 1
  1. 1.University of ReginaReginaCanada

Personalised recommendations