›› 2012, Vol. 27 ›› Issue (1): 1-23.doi: 10.1007/s11390-012-1202-7

Special Issue: Artificial Intelligence and Pattern Recognition

• Artificial Intelligent and Pattern Recognition •     Next Articles

Dynamic Uncertain Causality Graph for Knowledge Representation and Reasoning: Discrete DAG Cases

Qin Zhang (张勤)   

  1. School of Computer Science and Technology, Beihang University, Beijing 100191, China
  • Received:2011-08-22 Revised:2011-12-20 Online:2012-01-05 Published:2012-01-05
  • Supported by:

    This work is supported by Guangdong Nuclear Power Group of China under Contract No. CNPRI-ST10P005 and the National Natural Science Foundation of China under Grant No. 60643006.

Developed from the dynamic causality diagram (DCD) model, a new approach for knowledge representation and reasoning named as dynamic uncertain causality graph (DUCG) is presented, which focuses on the compact representation of complex uncertain causalities and efficient probabilistic inference. It is pointed out that the existing models of compact representation and inference in Bayesian Network (BN) is applicable in single-valued cases, but may not be suitable to be applied in multi-valued cases. DUCG overcomes this problem and beyond. The main features of DUCG are: 1) compactly and graphically representing complex conditional probability distributions (CPDs), regardless of whether the cases are single-valued or multi-valued; 2) able to perform exact reasoning in the case of the incomplete knowledge representation; 3) simplifying the graphical knowledge base conditional on observations before other calculations, so that the scale and complexity of problem can be reduced exponentially; 4) the efficient two-step inference algorithm consisting of (a) logic operation to find all possible hypotheses in concern for given observations and (b) the probability calculation for these hypotheses; and 5) much less relying on the parameter accuracy. An alarm system example is provided to illustrate the DUCG methodology.

[1] Shortliffe E H, Buchanan B G. A model of inexact reason inmedicine. Mathematical Bioscience, 1975, 23(3/4): 351-379.

[2] Shafer G. A Mathematical Theory of Evidence. Princeton,NJ: Princeton University Press, 1976.

[3] Duda R O et al. Development of the Prospector consultationsystem for mineral exploration. Final report, SRI Project5821 and 6415, SRI International, 1978.

[4] Zadeh L A. The role of fuzzy logic in the management of un-certainty in expert systems. Fuzzy Sets and Systems, 1983,11: 199-227.

[5] Pearl J. Fusion, propagation, and structuring in belief net-works. Artificial Intelligence, 1986, 29(3): 241-288.

[6] Pearl J. Probabilistic Reasoning in Intelligent Systems. SanMateo: Morgan Kaufmann, 1988. ISBN 0-934613-73-7.

[7] Henrion M. Practical issues in constructing a Bayes' beliefnetwork. In Proc. the 3rd Conf. Uncertainty in ArtificialIntelligence, July 1987, pp.132-139.

[8] Srinivas S. A generalization of the noisy-OR model. In Proc.the 9th Conf. Uncertainty in Artificial Intelligence, San Fran-cisco, July 1993, pp.208-215.

[9] Diez F J. Parameter adjustment in Bayes networks: The gen-eralized noisy-OR gate. In Proc. the 9th Conf. Uncertaintyin Artificial Intelligence, 1993, pp.99-105.

[10] Pradhan M, Provan G, Middleton B, Henrion M. Knowledgeengineering for large belief networks. In Proc. the 10th Conference on Uncertainty in Artificial Intelligence, July1994, pp.484-490.

[11] Gilio A, Scozzafava R. Conditional events in probability as-sessment and revision. IEEE Trans. Systems, Man and Cy-bernetics, 1994, 24(12): 1741-1746.

[12] Zhang N L, Poole D. A simple approach to Bayesian Networkcomputation. In Proc. the 10th Biennial Canadian ArtificialIntelligence Conference, 1994, pp.171-178.

[13] D'Ambrosio B. Local expression languages for probabilisticdependence. Int. J. Approximate Reasoning, 1995, 13(1):61-68.

[14] Boutilier C, Friedman N, Goldszmidt M, Koller D. Context-specific independence in Bayesian network. In Proc. the12th Conf. Uncertainty in Artificial Intelligence, Aug. 1996,pp.115-123.

[15] Heckerman D, Breese J S. Causal independence for probabi-lity assessment and inference using Bayesian networks. IEEETrans. Systems, Man and Cybernetics, 1996, 26(6): 826-831.

[16] Cowell R G, Dawid A P, Lauritzen S L, Spiegelhalter DJ. Probabilistic Networks and Expert Systems. New York:Springer, 1999.

[17] Takikawa M, D'Ambrosio B. Multiplicative factorization ofnoisy-MAX. In Proc. the 15th Conf. Uncertainty in Artifi-cial Intelligence, July 30-Aug. 1, 1999, pp.622-630.

[18] Jensen F V. Bayesian graphical models. In Encyclopedia ofEnvironmetrics, Sussex: Wiley, 2000.

[19] Pfeffer A. Sufficiency, separability and temporal probabilisticmodels. In Proc. the 17th Conf. Uncertainty in ArtificialIntelligence, Aug. 2001, pp.421-428.

[20] Russell S J, Norvig P. Artificial Intelligence: A Modern Ap-proach, 2nd edition. Prentice Hall, 2003.

[21] Pearl J, Russell S. Bayesian networks. In The Handbook ofBrain Theory and Neural Networks, 2nd edition, Arbib M A(ed.), MIT Press, 2003.

[22] Poole D, Zhang N L. Exploiting contextual independence inprobabilistic inference. Journal of Artificial Intelligence Re-search, 2003, 18(1): 263-313.

[23] Zagorecki A, Druzdzel M. An empirical study of probabilityelicitation under noisy-OR assumption. In Proc. the 17thFLAIRS, May 2004, pp.880-885.

[24] Schubert L K. A new characterization of probabilities inBayesian networks. In Proc. the 20th Conf. Uncertaintyin Artificial Intelligence, Banff, Canada, July 7-11, 2004,pp.495-503.

[25] Lucas P J F. Bayesian network modeling through qualitativepatterns. Artificial Intelligence, 2005, 163(2): 233-263.

[26] Chavira M, Allen D, Darwiche A. Exploiting evidence inprobabilistic inference. In Proc. the 21st Conf. Uncertaintyin Artificial Intelligence, July 2005, pp.112-119.

[27] Milch B, Marthi B, Sontag D, Russell S, Ong D L, Kolobov.Approximate inference for infinite contingent Bayesian net-works. In Proc. the 10th International Workshop on Artifi-cial Intelligence and Statistics, Barbados, Jan. 2005.

[28] Zagorecki A, Voortman M, Druzdzel M J. Decomposing localprobability distributions in Bayesian networks for improvedinference and parameter learning. In Proc. the 19th FLAIRSConference, Melbourne Beach, USA, May 2006, pp.860-865.

[29] van Gerven M A J, Lucas P J F, van der Weide Th P. Ageneric qualitative characterization of independence of causalinfluence. International Journal of Approximate Reasoning,2008, 48(1): 214-236.

[30] Li W, Poupart P, van Beek P. Exploiting causal independenceusing weighted model counting. In Proc. the 23rd AAAI Con-ference on Artificial Intelligence, Chicago, USA, July 13-17,2008, pp.337-343.

[31] Zhang Q. Probabilistic reasoning based on dynamic causalitytrees/diagrams. Reliability Engineering and System Safety,1994, 46(3): 209-220.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved