Uncertainty and Vagueness in Knowledge Based Systems

The primary aim of this monograph is to provide a formal framework for the representation and management of uncertainty and vagueness in the field of artificial intelligence. It puts particular emphasis on a thorough analysis of these phenomena and on the development of sound mathematical modeling approaches. Beyond this theoretical basis the scope of the book includes also implementational aspects and a valuation of existing models and systems. The fundamental ambition of this book is to show that vagueness and un­ certainty can be handled adequately by using measure-theoretic methods. The presentation of applicable knowledge representation formalisms and reasoning algorithms substantiates the claim that efficiency requirements do not necessar­ ily require renunciation of an uncompromising mathematical modeling. These results are used to evaluate systems based on probabilistic methods as well as on non-standard concepts such as certainty factors, fuzzy sets or belief functions. The book is intended to be self-contained and addresses researchers and practioneers in the field of knowledge based systems. It is in particular suit­ able as a textbook for graduate-level students in AI, operations research and applied probability. A solid mathematical background is necessary for reading this book. Essential parts of the material have been the subject of courses given by the first author for students of computer science and mathematics held since 1984 at the University in Braunschweig.

Contenu

1. General Considerations of Uncertainty and Vagueness.- 1.1 Artificial Intelligence.- 1.2 Modeling Ignorance.- 1.3 The Scope of the Book.- 2. Introduction.- 2.1 Basic Notations.- 2.2 A Simple Example.- 2.3 Vagueness and Uncertainty.- 2.3.1 Modeling Vague Data.- 2.3.2 Modeling Partial Belief.- 3. Vague Data.- 3.1 Basic Concepts.- 3.2 On the Origin of Vague Data.- 3.3 Uncertainty Handling by Means of Layered Contexts.- 3.3.1 Possibility and Necessity.- 3.3.2 Operations with Vague Data.- 3.3.3 On the Interpretation of Vague Data.- 3.4 The General Case.- 3.5 Concluding Remarks.- 4. Probability Theory.- 4.1 Basic Concepts.- 4.1.1 Axiomatic Probability Theory.- 4.1.2 On the Interpretation of a Probability.- 4.1.3 Practical Aspects.- 4.2 Probabilities on Different Sample Spaces.- 4.3 Bayesian Inference.- 4.4 Classes of Probabilities.- 4.5 Decision Making Aspects.- 4.6 Aggregating Probability Distributions.- 4.7 Concluding Remarks.- 5. Random Sets.- 5.1 Random Variables.- 5.2 The Notion of a Random Set.- 5.2.1 Weighted Sets versus Random Sets.- 5.2.2 On the Updating of Random Sets.- 5.3 Decision Making in the Context of Vague Data.- 5.4 The Notion of an Information Source.- 5.4.1 Updating Information Sources.- 5.4.2 The Combination of Information Sources.- 5.5 Concluding Remarks.- 6. Mass Distributions.- 6.1 Basic Concepts.- 6.1.1 Condensed Representations of Random Sets.- 6.1.2 Belief Functions.- 6.2 Different Frames of Discernment.- 6.2.1 Specializations.- 6.2.2 Strict Specializations.- 6.2.3 Orthogonal Extensions.- 6.2.4 Conjunctive and Disjunctive Extensions.- 6.3 Measures for Possibility/Necessity.- 6.4 Generalized Mass Distributions.- 6.5 Decision Making with Mass Distributions.- 6.6 Knowledge Representation with Mass Distributions.- 6.6.1 Encoding Knowledge by Mass Distributions.- 6.6.2 Integration of Different Pieces of Knowledge.- 6.7 Simplifying Assumptions.- 6.8 Concluding Remarks.- 7. On Graphical Representations.- 7.1 Graphs and Trees.- 7.1.1 Undirected Graphs.- 7.1.2 Trees.- 7.2 Hypergraphs and Hypertrees.- 7.2.1 Hypertrees.- 7.2.2 Simple Hypertrees.- 7.3 Analysis of Simple Hypertrees.- 7.3.1 Markov Trees.- 7.3.2 Knowledge Representation with Hypergraphs.- 7.4 Dependency Networks.- 7.5 Triangulated Graphs.- 7.6 Directed Acyclic Graphs.- 7.7 Concluding Remarks.- 8. Modeling Aspects.- 8.1 Rule Based Approaches.- 8.2 Model Based Representations.- 8.2.1 Requirements on Models.- 8.2.2 On the Structure of Models.- 8.2.3 On the Choice of Mathematical Models.- 8.2.4 Selected Problems with Mathematical Models.- 8.3 Dependency Network Based Systems.- 9. Heuristic Models.- 9.1 MYCIN - The Certainty Factor Approach.- 9.1.1 The Mathematical Model.- 9.1.2 Uncertainty Representation in MYCIN.- 9.1.3 Related Models and Proposals.- 9.1.4 Conclusions.- 9.2 RUM - Triangular Norms and Conorms.- 9.2.1 Families of Uncertainty Calculi - Triangular Norms and Conorms.- 9.2.2 RUM.- 9.2.3 Final Remarks.- 9.3 INFERNO - A Bounds Propagation Architecture.- 9.4 Other Heuristic Models.- 10. Fuzzy Set Based Models.- 10.1 Fuzzy Sets.- 10.2 Possibility Distributions.- 10.3 Approximate Reasoning.- 10.4 Reasoning with Fuzzy Truth Value.- 10.5 Conclusions.- 11. Reasoning with L-Sets.- 11.1 Knowledge Representation with L-Sets.- 11.2 On the Interpretation of Vague Rules.- 11.3 L-Sets on Product Spaces.- 11.4 Local Computation of Marginal -Sets.- 11.5 The Propagation Algorithm.- 11.6 Aspects of Implementation.- 12. Probability Based Models.- 12.1 The Interpretation of Rules.- 12.2 The Straightforward Use of Probabilities.- 12.2.1 The Model of Ishizuka et al.- 12.2.2 The Model of Adams.- 12.2.3 Discussions.- 12.3 PROSPECTOR - Inference Networks.- 12.3.1 The Inference Network Model.- 12.3.2 PROSPECTOR.- 12.3.3 Discussion and Related Work.- 12.4 Decomposable Graphical Models.- 12.4.1 The Model of Pearl.- 12.4.2 MUNIN - An Application.- 12.4.3 HUGIN - A Professional Tool.- 12.5 Propagation Based on Dependency Networks.- 12.5.1 Knowledge Representation.- 12.5.2 Graph Structure and Conditional Independence.- 12.5.3 Local Computation of Marginal Probability Distributions...- 12.5.4 The Propagation Algorithm.- 12.5.5 Aspects of Implementation.- 12.5.6 Numerical Example.- 12.6 Concluding Remarks.- 13. Models Based on the Dempster-Shafer Theory of Evidence.- 13.1 The Mathematical Theory of Evidence.- 13.2 Knowledge Representation Aspects.- 13.2.1 Representing Pieces of Knowledge.- 13.2.2 Integration of Pieces of Evidence.- 13.3 The Straightforward Use of Belief Functions.- 13.3.1 The Model of Ishizuka et al.- 13.3.2 The Model of Ginsberg.- 13.3.3 Discussion, Related Work.- 13.4 Belief Functions in Hierarchical Hypothesis Spaces.- 13.4.1 Gordon and Shortliffe's Extension to MYCIN.- 13.4.2 The Model of Yen - A Quasi-Probabilistic Approach.- 13.5 MacEvidence - Belief Propagation in Markov Trees.- 13.5.1 Belief Propagation in Markov Trees.- 13.5.2 MacEvidence.- 13.5.3 Discussion.- 13.6 Conclusions.- 14. Reasoning with Mass Distributions.- 14.1 Matrix Notation for Specializations.- 14.1.1 Specialization Matrices.- 14.1.2 Composition of Specialization Matrices.- 14.1.3 Properties of Specialization Matrices.- 14.2 Specializations in Product Spaces.- 14.3 Knowledge Representation with Mass Distributions.- 14.4 Local Computations with Mass Distributions.- 14.5 The Propagation Algorithm.- 14.6 Aspects of Implementation.- 15. Related Research.- 15.1 Nonstandard Logics.- 15.2 Integrating Uncertainty Calculi and Logics.- 15.3 Symbolic Methods.- 15.4 Conclusions.- References.