Sławomir T. Wierzchoń, D.Eng.habil., received Ph.D. in mathematical modeling of imprecise systems (1980) from Technical University of Warsaw, Dr. Sc. (Dr. Eng. habil.) from the Polish Academy of Sciences in 1997. His fields of interest include managing uncertainty in knowledge-based systems, Bayesian networks, Dempster- Shafer's theory of evidence, fuzzy sets and their application, genetic algorithms and artificial immune systems. Currently he is Associate Professor in the Institute of Computer Science Polish Academy of Sciences; also Extraordinary Professor and head of the Information Systems and Computer Networks Department at the Białystok University of Technology. S.T. Wierzchoń acted as a consultant in many projects for the industry and software firms. Further he headed university research projects and participated in national and international research projects. He is an author and co-author of more than 100 papers published in international journals, proceedings of the international conferences or as book chapters. He published also two monographs devoted to managing uncertain information and artificial immune systems.

• Instytut Podstaw Informatyki PAN, ul. Ordona 21, 01-237 Warszawa or
• Instytut Informatyki, Politechnika. Białostocka, ul. Wiejska 45A, 15-351 Białystok
• stw@ipipan.waw.pl

Mieczysław A. Kłopotek, D.Eng.habil., received M.Sc. in 1983 and Ph.D. in computer science in 1984 from Dresden University of Technology, Germany. Dr.Sc. (Dr.Eng.habil.) from the Polish Academy of Sciences in 1998. Currently he is Associate Professor at the Institute of Computer Science of Polish Academy of Sciences; also Extraordinary Professor and head of Artificial Intelligence Department at the University of Podlasie. Author and co-author of more than 150 publications and technical expert in machine learning, data mining, pattern recognition, expert systems, reasoning under uncertainty and computer systems integration. He published two monographs on data mining with uncertain data and on intelligent search engines. M.A.Kłopotek possesses almost 20 years of experience implementing advanced Information Technology systems. He was involved in numerous consulting engagements for the industry and software firms. Furthermore, he headed university research projects and participated in national and international research projects. He is member of the Editorial Board of the International Journal Machine Graphics and Vision.

• Instytut Podstaw Informatyki PAN, ul. Ordona 21, 01-237 Warszawa or
• Instytut Informatyki, Akademia Podlaska, Sienkiewicza 51, 08-110 Siedlce
• klopotek@ipipan.waw.pl

About this Book

This book summarizes more than ten years of research of the Authors in the domain of evidential reasoning. To large extent it presents original contributions of the Authors in this area, including new efficient reasoning methods, learning mechanisms, sample generation mechanisms and case-based interpretation schemes applicable in the Mathematical Theory of Evidence and in its generalizations to valuation-based systems. The book starts with a general introduction to reasoning under uncertainty and then concentrates on the evidential reasoning and its generalization to valuation-based systems. The exposition of the theoretical foundations is accompanied by explanatory examples. This book is addressed at young researchers and students interested in advanced topics in artificial intelligence who look for still open and promising areas of research. It may be also beneficial for software engineers, in particular for knowledge engineers who look for powerful methods of representation of vague and/or incomplete knowledge as encountered in many practical applications of expert systems and other knowledge based systems.

Contents

• Preface   7
• 1. Introduction   9
• 2. Expert systems and decision analysis. An overview   13
  • 2.1. Subjective versus objective probability   13
  • 2.2. Assessing subjective probability   15
  • 2.3. Qualitative structuring and conditional independence   17
  • 2.4. Bayesian formalism   17
  • 2.5. Decision theory   23
  • 2.6. Early Bayesian expert systems   24
  • 2.7. Knowledge-based expert systems   26
• 3. Graphical knowledge representation   31
  • 3.1. Influence diagrams   31
  • 3.2. Bayesian networks   32
    • 3.2.1. An example of a Bayesian network   32
    • 3.2.2. Independence assumption   34
  • 3.3. A summary of the three main paradigms of expert systems   38
    • 3.3.1. Rule-based systems   38
    • 3.3.2. Neural networks   39
    • 3.3.3. Bayesian networks   41
    • 3.3.4. Comparing neural networks and Bayesian networks   42
    • 3.3.5. Combining Bayesian networks and neural networks   43
  • 3.4. Types of Bayesian networks   44
  • 3.5. Modelling tricks   48
  • 3.6. Applications of Bayesian networks   51
  • 3.7. Other graphical representations   52
    • 3.7.1. Bubble graphs   52
    • 3.7.2. Markov networks   53
    • 3.7.3. Chain Graphs   58
• 4. Introduction to general probabilistic reasoning   59
  • 4.1. Definitions and notation   59
  • 4.2. Basic queries to a Bayesian network   59
  • 4.3. An elimination algorithm for belief assessment   60
  • 4.4. Elimination algorithm for MPE (elim-max)   64
    • 4.4.1. Backward part   64
    • 4.4.2. Forward part   64
  • 4.5. Elimination algorithm for MAP (elim-map)   66
  • 4.6. Combining elimination and conditioning   66
  • 4.7. Elimination algorithm for MEU (elim-meu)   67
• 5. Introduction \newline to the Dempster-Shafer Theory   69
  • 5.1. DST versus empirical data   69
  • 5.2. Some comments   72
  • 5.3. Basics of the Dempster-Shafer Theory   73
  • 5.4. Basics of belief function decomposition and reasoning   75
  • 5.5. Valuation based systems   76
  • 5.6. Computing marginals in a Markov tree   82
  • 5.7. Query processing in VBS   91
• 6. Fundamental problems \newline of the Dempster-Shafer Theory   115
  • 6.1. The frequency interpretation problem in DST   115
  • 6.2. Problems of decomposition of belief function   124
    • 6.2.1. Logical networks of Zhu and Lee   124
    • 6.2.2. Directed acyclic graphs of Smets   126
    • 6.2.3. Cano's et al. a-priori conditionals in directed acyclic graphs   130
    • 6.2.4. Hypergraphs of Shenoy and Shafer   131
  • 6.3. Testing conditional independence   132
    • 6.3.1. A solution   134
    • 6.3.2. Analysis of three-dimensional belief distributions   135
    • 6.3.3. Some formal properties of the new measure   138
• 7. Lower/upper bound \newline interpretation   139
  • 7.1. Case-based understanding of belief functions   139
  • 7.2. Correct approximation of apriorical conditional belief functions   142
  • 7.3. The impact on reasoning   146
  • 7.4. Conclusion   148
• 8. Qualitative interpretation   149
  • 8.1. The traditional interpretation in rough set theory   150
  • 8.2. New interpretation   151
    • 8.2.1. Conditioning as selection of a subtable   154
    • 8.2.2. Combination as relational join   155
    • 8.2.3. Relational marginalization and decombination   156
    • 8.2.4. Multivariate beliefs and multidecision tables   158
  • 8.3. Concluding remarks   161
• 9. Quantitative interpretation   163
  • 9.1. Introduction   163
    • 9.1.1. Instead of an informal introduction - an example   163
    • 9.1.2. Formal introduction of the new interpretation   170
  • 9.2. Independence and shades of conditionality   175
  • 9.3. Belief from data   179
  • 9.4. Independence from data   180
  • 9.5. Conditional independence from data   181
  • 9.6. Discussion   182
  • 9.7. Formal properties of anti-conditional independence   186
    • 9.7.1. Introduction   186
    • 9.7.2. Cano's et al. a priori conditionals in DAGs   188
    • 9.7.3. Shenoy's notion of conditionality   189
    • 9.7.4. New graphoidal belief functions   192
    • 9.7.5. Discussion   201
  • 9.8. Conclusions   204
• 10. Knowledge acquisition from data   205
  • 10.1. Introduction   206
  • 10.2. Shenoy \& Shafer reasoning versus frequency interpretations   210
  • 10.3. A concept of belief network   211
  • 10.4. Recovery of tree-structured belief networks   215
  • 10.5. Recovery of polytree-structured belief networks   217
  • 10.6. Recovery of general type belief networks   218
    • 10.6.1. General claims   218
  • 10.7. Recovery when there are latent variables   227
    • 10.7.1. Causal inference algorithm   228
    • 10.7.2. From CI output to belief network   231
    • 10.7.3. The new algorithm   233
    • 10.7.4. Differences with the Spirtes et al. CI algorithm   239
    • 10.7.5. Properties of the new algorithm   240
    • 10.7.6. Experiments   247
    • 10.7.7. The FCI algorithm and its correction   248
  • 10.8. Discussion   252
  • 10.9. Conclusions   254
• 11. Examples   255
  • 11.1. The database   255
  • 11.2. Measuring function and DS functions   255
  • 11.3. Labeling / reasoning   259
  • 11.4. Statistical independence   261
  • 11.5. Belief network from data   263
• 12. Sample generation   279
  • 12.1. Introduction   279
  • 12.2. The problem   282
  • 12.3. The Solution   282
  • 12.4. Summary   290
• 13. Concluding remarks   291
• References   295

  ---

  S.T.Wierzchoń , M.A.Klopotek (Created on January 12th, 2002)