d-Separation: Strong Completeness of Semantics in Bayesian Network Inference

详细信息    查看全文

• 作者：Cory J. Butz
  Wen Yan
  Anders L. Madsen (21) (22)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7884
• 期：1
• 页码：25-39
• 全文大小：229KB
• 参考文献：1. Butz, C.J., Hua, S., Konkel, K., Yao, H.: Join Tree Propagation with Prioritized Messages. Networks聽55(4), 350鈥?59 (2010)
  2. Butz, C.J., Konkel, K., Lingras, P.: Join Tree Propagation Utilizing both Arc Reversal and Variable Elimination. Int. J. Approx. Reasoning聽52(7), 948鈥?59 (2011) CrossRef
  3. Butz, C.J., Yan, W., Lingras, P., Yao, Y.Y.: The CPT Structure of Variable Elimination in Discrete Bayesian Networks. In: Ras, Z.W., Tsay, L.S. (eds.) Advances in Intelligent Information Systems. SCI, vol.聽265, pp. 245鈥?57. Springer, Heidelberg (2010) CrossRef
  4. Castillo, E., Guti茅rrez, J., Hadi, A.: Expert Systems and Probabilistic Network Models. Springer, New York (1997) CrossRef
  5. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)
  6. Darwiche, A.: Modeling and Reasoning with Bayesian Networks. Cambridge University Press, New York (2009) CrossRef
  7. Kjaerulff, U.B., Madsen, A.L.: Bayesian Networks and Influence Diagrams. Springer, New York (2008) CrossRef
  8. Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge (2009)
  9. Madsen, A.L.: A Differential Semantics of Lazy AR Propagation. In: 21st Conference on Uncertainty in Artificial Intelligence, pp. 364鈥?71. Morgan Kaufmann, San Mateo (2005)
  10. Madsen, A.L.: Improvements to Message Computation in Lazy Propagation. Int. J. Approximate Reasoning聽51(5), 499鈥?14 (2010) CrossRef
  11. Meek, C.: Strong Completeness and Faithfulness in Bayesian Networks. In: 11th Conference on Uncertainty in Artificial Intelligence, pp. 411鈥?18. Morgan Kaufmann, San Mateo (1995)
  12. Pearl, J.: Fusion, Propagation and Structuring in Belief Networks. Artif. Intell.聽29, 241鈥?88 (1986) CrossRef
  13. Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco (1988)
  14. Pearl, J.: Belief Networks Revisited. Artif. Intell.聽59, 49鈥?6 (1993) CrossRef
  15. Shafer, G.: Probabilistic Expert Systems. SIAM, Philadelphia (1996) CrossRef
  16. Wong, S.K.M., Butz, C.J., Wu, D.: On the Implication Problem for Probabilistic Conditional Independency. IEEE Trans. Syst. Man Cybern. A聽30(6), 785鈥?05 (2000) CrossRef
  17. Zhang, N.L., Poole, D.: A Simple Approach to Bayesian Network Computations. In: 7th Canadian Conference on Artificial Intelligence, pp. 171鈥?78. Springer, New York (1994)
  
• 作者单位：Cory J. Butz
  Wen Yan
  Anders L. Madsen (21) (22)
  
  21. HUGIN EXPERT A/S, Aalborg, Denmark
  22. Department of Computer Science, Aalborg University, Denmark
  
• ISSN：1611-3349

文摘

It is known that d-separation can determine the minimum amount of information needed to process a query during exact inference in discrete Bayesian networks. Unfortunately, no practical method is known for determining the semantics of the intermediate factors constructed during inference. Instead, all inference algorithms are relegated to denoting the inference process in terms of potentials. In this theoretical paper, we give an algorithm, called Semantics in Inference (SI), that uses d-separation to denote the semantics of every potential constructed during inference. We show that SI possesses four salient features: polynomial time complexity, soundness, completeness, and strong completeness. SI provides a better understanding of the theoretical foundation of Bayesian networks and can be used for improved clarity, as shown via an examination of Bayesian network literature.