Lecture Notes in Economics and Mathematical Systems 425 Series Editors: Günter Fandel · Walter Trockel Herbert Dawid · Dinko Dimitrov et. al. Jürg Kohlas · Paul-Andre Monney A Mathematical Theory of Hints An Approach to the Dempster-Shafer Theory of Evidence Lecture N otes in Economics and Mathematical Systems 425 Founding Editors: M. Beckmann H. P. KUnzi Editorial Board: H. Albach, M. Beckmann, G. Feichtinger, W. Hildenbrand, W. Krelle H. P. KUnzi, K. Ritter, U. Schittko, P. Schonfeld, R. Selten Managing Editors: Praf. Dr. G. Fandel Fachbereich Wirtschaftswissenschaften Fernuniversităt Hagen Feithstr. 140lAVZ II, D-58097 Hagen, Germany Prof. Dr. W. Trockel Institut fUr Mathematische Wirtschaftsforschung (IMW) Universităt Bielefeld Universitătsstr. 25, D-33615 Bielefeld, Germany Springer-Verlag Berlin Heidelberg GmbH Jiirg Kohlas Paul-Andre Monney A Mathematical Theory of Hints An Approach to the Dempster-Shafer Theory of Evidence Springer Authors Prof. Dr. JUrg Kohlas Institute of Informatics University of Fribourg CH-1700 Fribourg, Switzerland e-mail [email protected] Dr. Paul-Andre Monney Insitute of Informatics University of Fribourg CH-1700 Fribourg, Switzerland ISBN 978-3-540-59176-4 Ligrary of Congress Cataloging-in-Publication Data Kohlas, JUrg, 1939-A mathematieal theory of hints: an approaeh to the Dempster Shafer theory of evidenee / JUrg Kohlas, Paul-Andre Monney. p.em. - (Leeture notes in eeonomies and mathematical systems; 425 ISBN 978-3-540-59176-4 ISBN 978-3-662-01674-9 (eBook) DOI 10.1007/978-3-662-01674-9 Probabilities. 2. Mathematical statistics. 3. Evidence. 1. Monney, Paul-Andre. II. Title. III. Series. QA273.K597 1995 519.5'4-dc20 95-12080 This work is subjeet to copyright. AlI rights are reserved, whether the whole or part of the material is concerned, speeificalIy the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on mierofilms or in any other way, and storage in data banks. Duplication of this publieation or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its eurrent version, and permission for use must a1ways be obtained from Springer-Verlag Berlin Heidelberg GmbH. Violations are liable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1995 Originally published by Springer-Verlag Berlin Heidelberg New York in 1995 Typesetting: Camera ready by author SPIN: 10486761 42/3142-543210 -Printed on acid-free paper Preface This book is about the theory of hints, a variant of the Dempster-Shafer theory of evidence. Since the reader may already have heard of or even be familiar with the the theory of evidence, let us begin by giving some historical notes. Evidence theory started from a course on statistica! inference taught by Arthur P. Dempster at Harvard University in the late sixties. Then Demp ster's ideas were reinterpreted by Glenn Shafer in his book A Maihemaiical TheoTY of Evidence published by Princeton University Press in 1976. Evidence is an appealing term and it is no surprise that the theory of evidence found much interest among knowledge engineers who have to model uncertain and imprecise information. After a lot of ad hoc attempts to model uncertainty in expert systems, a serious theory seemed finally available to treat this basic problem of the field. However, as the theory is not really compatible with the simple paradigms of early rule-based expert systems, misinterpretations and oversimplistic misuses of the theory caused much deception. Only slowly begins the true nature and the rea! meaning of evidence theory to emerge and to be understood. And hopefully this book wiII contribute to its better understanding as well demonstrate its usefulness and mathematica! elegance. To put the subject of this book into perspective, it is a good idea to have a closer look at Dempster's and Shafer's conceptions of the theory of evidence. It will then be easier to explain what is the essence of the theory of hints, which is our own view of the theory of evidence. Dempster originally developed a theory of lower and upper probabilities in an attempt to reconcile Bayesian statistics with Fisher's fiducial argument (Dempster, 1967, 1968). The following citation (up to symbols) is taken from Dempster (1967): "Consider a pair of spaces fl and e and a multivalued rnapping r which assigns a subset r( w) <;;; e to every w E f2. Suppose that P is a probability measure which assigns probabilities to the members of a class A of subsets of f2. If P is acceptable for the probability judgements about an uncertain outcome w E f2, aud if this uncertain outcome w is known to correspond to an uncertain outcome eE r(w), what probability e judgements may be made about the uncertain outcome Ee'?" As Dempster argues, this leads to the concept of compatible probability measures and he rcfers to the bounds as lower and upper probabilities. On the other hand, Shafer states in the preface of his book: "It (his book) offers a reinterpretation of Dempster's work, a reinterpretation that identifies his lower probabilites as epistemic probabilities 01' degrees of belief, takes the VI Preface rule for combining such degrees of belief as fundamental, and abandons the idea that they arise as lower bounds over classes of Bayesian probabilities." Given a piece of evidence relative to a question whose possible answers form the set e, Shafer postulates the existence of a function Bel on the power set e of satisfying some axiomatic conditions. He interprets the numerical value Bel(H), a number between O and 1, as the degree of belief that H contains the e answer and calls the function Bel a belieffunction. When is finite he shows that belief functions are generated by so-called basic probability assignments which in turn are used to combine belief functions. So where does the theory of hints stand with respect to these two points of view ? The point of view of hints is closer to Dempster's approach than to the one of Shafer. However it gives a new interpretation to the probabilistic structure considered in Dempster. So we keep Dempster's original structure ( il, P, r, e) but we gi ve it the following meaning: Suppose that a cert ain question, whose answer is unknown, has to be e studied. The elements of represent the possible answers to the question and we assume that there is exactly one correct, but unknown answer in e. The goal is to make assertions about the answer in the light of the available information. We assume that this informat ion allows for several different inter pretations, depending on some unknown circumstances. These interpretations are regrouped into the set il and there is exactly one correct interpretation. Not ali interpretations are equally likely and the known probability measure P on il reflects our information in that respect. Furthermore, if the interpre tation w E il is the correct one, then the answer is known to be in the subset r(w) c;:;; e. Such a structure 11. = (il,p,r,e) is called a hint. The hint 11. can then be used to judge the fact or the hypothesis, which can be true or e false, that the answer is in a subset H of by assinging to it a degree of support and a degree of plausibility. An interpretation w E il supports the hypothesis H if r( w) c;:;; H because in this case the answer is necessarily in H. The degree of support of H, denoted by sp(H), is defined as the proba bility of ali supporting interpretations of H. So sp(H) can be regarded as the probability with which H can be infered ar proved from the available infor mat ion encoded in the hint. In a similar way, if the interpretat ion w E il is correct, the subset H possibly contains the answer if r(w) n H =f 0. Then the degree of plausibility of H, denoted by pl(H), is defined as the probability of all interpretations under which H is possible. Sa like in Shafer's theory it is possible ta judge hypotheses about the answer, but in contrast to it this can be dane only in a second stage, after the hint has been constructed. For us, the degrees of support and plausibility are concepts which are derived from the notion of a hint, and not primitive objects like in Shafer's approach. Also, we speak of degrees of support and not degrees of belief because the word belief suggests an idea of personal judgement which is absent as soon as the e hint is given. Considering ali possible subsets H c;:;; leads to support and plausibility functions sp and pl. Preface VII Dempster mathematicaUy defines sp(H) and pl(H) exactly in the same way as we clid above, but the interpretation he gives to these values is different from ours. He points out that sp( H) can be regarded as the minimal amount of probability which can be transfered from il to outcomes eE Hand pl(H) as the largest possible amount of probability which can be transfered to outcomes e E H. Then he introduced the concept of compatible probability measures: P is compatible if sp(H) ~ P(H) ~ p/(H) for aU H ~ 8. Ever since sp and pl have oft en been looked at as lower and upper bounds for some unknown probability distribution by many authors. This has had unfortunate effects because it led to intriguing misinterpretations of the theory of evidence. In our opinion, the question treated by the theory of evidence is whether a hypothesis H is true or not, or more precisely, to what degree a piece of evidence supports a hypothesis H. It is quite a different question to ask what could be the probabiliiy of the hypothesis H. In the latter case the unknown is noi whether H is true or not, but the value of its probability. So let us emphasize that although approaches using partially specified probabilities may be very useful in many circumstances, the theory of evidence as developed in this book as a theory of hints does noi belong to this class of methods. It is clear today that the theory of evidence can be given various dif ferent forms. Some of them are based on probability theory and others are axiomatic theories, a priori without reference to probability theory. The first approach tries to integrate evidence theory in the framework of classical prob ability theory, and the theory of hints belongs to this category, whereas the second one deliberately goes beyond classical probability. Shafer's theory of belieffunctions and Smets' transferable belief model (Smets, 1988) are the two best known representatives of this non-standard probability approach. Despite the differences in approach and interpretation, aU of them lead essentially to mathematically equivalent theories in the finite case, which implies that they share the same basic theorems and the same computational procedures apply. However, substantial differences appear when the infinite case is considered. This book is divided into three Parts: Part 1 (Chapters 1 to 8) presents the elementary theory of hints, Part II (Chapters 9 to 12) discusses some possible applications of this theory and Part III (Qhapters 13 to 16) develops the rudiments of a general theory of hints. By discussing some simple examples, Chapter 1 intuitively introduces the idea of a hint and the related concepts of support and plausibility. These con cepts are then defined and studied formally in Chapters 2 and 3. Chapter 4 explains how to combine hints, an operat ion that is fundamental to the whole theory. Chapter 5 shows that the theory of hints provides for an adequate framework for probabilistic assumption-based reasoning, thereby establishing the link with propositional logic. The degree of support of a logical formula h is then essentiaUy equal to the probability of the assumptions that per mit to logicaUy infer h, given the knowledge base E. This idea goes back to Pearl's notion of probability of provability (Pearl, 1988), an idea also present in Laskey, Lehner (1989) and Provan (1990). The assumptions can be seen Vlll Preface as arguments in favour of hypotheses. These arguments are weighed by their likelihoods and the degree of support can then be viewed as the reliability of an associated proof system. This point of view is considered in Chapter 6. Let us note that this approach can be developed beyond the material presented in this book: The idea of arguments for hypotheses suggests that it might be possible to develop a purely qualitative theory of evidence by dropping the probabilities on the arguments. This has been do ne in Kohlas (1993 a) for propositional logic and was generalized to Boolean algebras and lattices in Kohlas (1994). It is even possible to go one step further by generalizing the notion of provability to arbitrary consequence relations in the sense of Tarski (Besnard, Kohlas, 1994). Of course, in a second step, it is always possible to reintroduce probabilities into these qualitative or symbolic versions of evi dence theory. Chapter 7 is concerned with the analysis of families of frames of discernment. This done in the abstract setting of lattices and important no tions like conditional independence of frames are discussed. Chapter 8 deals with the problem of combining hints efficiently and local propagat ion schemes are presented. Chapter 9 shows how statistical inference can be developed from the point of view of the theory of hints. This leads to interesting reinterpretations of clas sical statistical results. Chapter 10 discusses uncertainty in dynamical systems from the perspective of hints and Chapter 11 considers diagnostic problems from an evidential point of view. The last chapter of Part II, Chapter 12, explains how the theory of hints can be used to represent and support spatial and temporal reasoning. A very general class of models based on groups is analyzed and computational methods are presented. Chapter 13 presents a general theory of hints, where the sets of interpreta tions and the frames of discernment are not necessarily finite. The main result in this chapter is that every support function is generated by a generalized hint. Chapter 14 introduces the notion of inclusion between hints, as well as the the notion of canonical hint of a support function. Chapter 15 shows how to combine general hints by Dempster's rule and it is proved that inclusion of hints is preserved by this operation. Finally, the last Chapter 16 studies closed random intervals and random variables from the perspective of hints. Part I should be read first, and then either Part II and then Part III, or Part III and then Part II. \Vithin parts the chapters should be read in sequence. There is no doubt that theoretical foundations, practical use in modeling and computational aspects represent some of the possible topics for future research in evidence theory. On the theoreticallevel, evidence theory on topo logical spaces is a large open field for investigation. AIso, a hint can be seen as the generalization of a random variable and classical probability theory can largely be considered as a theory of random variables. However, Dempster's rule of combination of hints, which is a key concept in the whole theory of evidence, does not appear as such in probability theory. What is the role of this rule in probability theory ? Also, recently connections between evidence Acknowledgments IX theory and modallogic have been put forward, but there remains a lot of open questions about the relationship between evidence theory and non~standard logics. Furthermore, it seems that evidential information is essentially rela tional in nature, but conditional information has been proved very important in knowledge engineering (e.g. in Bayesian networks where the knowledge is essentially encoded as condi tional probabili ty distributions). Does this aspect really restrict the applicability of evidence theory ? Finally, from the point of view of computations, there is clearly a need for efficient approximations and heuristics for evidential calculations. In order to study a question, prob ably not ali available evidence has to be considered because the inf1uence of far-fetched information might not be substantial. So focussing strategies to simplify the reasoning is another important topic for investigation. Many of the developments in this book are tentative, especially in Parts II and III. This is due to the fact that the theory is still new and many important questions remain open. It is hoped that this text contributes to expand the new ideas on evidence theory and its applications. Fribourg, December 1994 J. Kohlas, P.A. Monney Acknowledgments We would like to thank a number of people who have helped to bring this book into existence. We are deeply indebted to Miss Ruth Leu, who corrected a lot of english mistakes and greatly improved the style of the text. We also wish to express our appreciation to Prof. Prakash Shenoy for reading some chap ters, and to Louis Cardona, Rolf Haenni, Urs Hănni and Norbert Lehmann for implementing some of the ideas contained in the book. Also, we would like to thank the Swiss National Foundation for Scientific Research and the Swiss Federal Ministry of Science and Education for their financial support (Grants Nr. 21-30186.90 and 21-32660.91). Finally, one of the authors (P.A. Monney) expresses his gratitude to the Research Commission of the Univer sity of Fribourg and the Swiss National Foundation for Scientific Research for supporting him during his twelve months stay at the U niversity of Kansas. In that regard, he wants to thank the entire Uni versi ty of Kansas communi ty for its welcome, especially Prof. Prakash Shenoy for his invitation to be part of this community.