Date: Tue, 02 Mar 2004 11:44:22 -0300 From: Leonor Santos Subject: Reasoning About Uncertainty
AUTHOR: Halpern, Joseph Y. TITLE: Reasoning About Uncertainty PUBLISHER: MIT Press YEAR: 2003
Maria Leonor Santos, Universidade Federal da Paraíba/ Universidade Federal de Santa Catarina
Uncertainty is a familiar topic to linguists and philosophers of language. According to J. Y. Halpern (page 1):
- uncertainty is fundamental and unavoidable in life, - we need to be able to represent it and reason about it, - reasoning about uncertainty can be a subtle task.
The book, thus, describes several tools available to represent uncertainty as well as to reason about it. It is a course book which contains a Preface, 12 Chapters, a list of References, a Glossary of Symbols and an Index. Each chapter starts with an introduction describing its content and explaining briefly how the chapter fits in the overall plan of the book. The chapters also include exercises and a section of notes, which provides references to the material. Suggestions on how to select material for regular courses are found on page 8.
Chapter 1 - Introduction and Overview This chapter starts with the description of several puzzles (the Second-Ace puzzle, the Monty Hall puzzle, the Two-Coin problem, etc). In the presence of uncertainty, that is, when we deal with lack of information, different levels of difficulty are likely to arise. The puzzles show that reasoning in such situations calls for a variety of approaches, depending on the kind of information which is either available or missing, and also depending on the purpose of the intended modeling. After presenting the puzzles, the author describes the content of chapters 2 to 11, in a clear and concise overview. There is also a chart depicting the dependence between chapters on page 9.
Chapter 2 - Representing Uncertainty This chapter surveys formal approaches available for the representation of uncertainty. It can be divided in three parts: an introduction on sets of possible worlds (2.1), an assessment of the formal approaches (2.2 to 2.8), and a section containing suggestions on how to choose an approach for modeling a real-life situation (2.9).
The first part is a brief presentation of the concept of sets of possible worlds, which is used by all the representations for uncertainty discussed in the book. The author also comments on how to select sets of possible worlds for specific cases, and how to decide what kind of information should be part of the description of a possible world.
The second part (assessment of the formal approaches) starts with the characterization of probability measures and probability spaces. The author discusses the shortcomings of probability as a representation for uncertainty in certain situations, and shows the relative advantages and disadvantages of other representations.
The following representations for uncertainty are discussed:
(numeric representations for uncertainty) - Probability Measures - Lower and Upper Probabilities - Dempster-Shafer Belief Functions - Possibility Measures - Ranking Functions
Each representation is formally presented, and the intuitions that it is supposed to capture are also discussed. Prominence is given to the evaluation of differences and similarities between the representations, and to the possibility of converting one representation into another (for example, ranking functions seen as possibility measures, on page 44). Plausibility measures are presented as a generalization of all the other modes of representation.
The third part of the chapter is a summary of the strong points of the different approaches in relation to different needs.
Chapter 3 - Updating Beliefs This chapter deals with the fact that an agent may acquire knowledge and that the acquisition may change the agent's beliefs. This, in turn, has an impact on the reasoning process. The way the agent's beliefs are updated is related to the representation chosen for uncertainty. The author discusses several types of conditioning (the updating of beliefs in the context of each of the representations available for uncertainty), the use of Bayes' Rule, the possibility of generalizing conditioning (Jeffrey's Rule) and the applicability of the formal notion of entropy to represent "minimal changes" between worlds.
Chapter 4 - Independence and Bayesian Networks Intuitively, two events are said to be independent if they are unrelated, that is, if the occurrence of one event does not play any role in bringing about ^Ö or hindering ^Ö the occurrence of the other. The first part of the chapter is devoted to the expression of independence by means of probability, conditional probability, plausibility measures and random variables. The second part of the chapter discusses the use of Bayesian networks in relation to the expression of independence.
Chapter 5 - Expectation In this chapter, the definition for expectation is first studied in terms of probability, and then in terms of the other notions of likelihood (sets of probability measures, belief functions, inner and outer measures, possibility measures and ranking functions). The author provides a notion of expectation for plausibility that can be considered as a generalization of the other definitions of expectation. He also discusses the role of expectation in decision theory, as well as conditional expectation, that is, ways of formalizing the updating of expectation in the presence of the new information available for an agent.
Chapter 6 - Multi-Agent Systems The author now considers interactive situations, in which two or more agents reason about the reasoning of the other agents involved (the agents may be either competing or cooperating). In this new context, time has to be treated in an explicit form, and it may be necessary to consider additional structure for the possible worlds. After reviewing epistemic frames and probability frames, he discusses multi-agent systems and the need to make protocols explicit. The chapter also contains sections on Markovian systems, on conditioning, on Non-SPD Systems ('SDP' being 'state-dependent probability') and plausibility systems.
Chapter 7 - Logics for Reasoning about Uncertainty After a brief introduction to propositional logic and to the notions it is intended to capture, modal epistemic logics are considered, as well as the possibility of employing logics to depict knowledge, probability, and the other representations of uncertainty already discussed in the preceding chapters, such as relative likelihood, independence and expectation.
Chapter 8 - Beliefs, Defaults and Counterfactuals This chapter examines how certain representations for uncertainty are likely to be useful for dealing with default and counterfactual reasoning. The chapter starts with a characterization of knowledge and belief. Next, the author comments on the properties of a "default conditional" connective, in contrast with the material conditional (the "standard" conditional connective), and considers an axiom system P for default reasoning, composed of the six core properties of the default conditional. Then, the author presents semantics for defaults: probabilistic semantics, as well as semantics based on possibility measures, ranking functions, preference orders and plausibility measures. He also reviews a few attempts which have been made to build systems for default reasoning which are stronger than P. The last part of the chapter discusses counterfactual reasoning, by means of presenting a conditional logic which can be used either to reason about counterfactuals or defaults.
Chapter 9 - Belief Revision In chapter 3, the author surveyed the means for representing the updating of an agent's beliefs. In chapter 9 he extends the discussion to belief revision in general, and proposes that it can be adequately understood as conditioning.
Chapter 10 - First-Order Modal Logic While chapters 7-9 considered reasoning about uncertainty by means of propositional logic and modal propositional logic, chapter 10 examines the use of first-order logic. First-order logic, more expressive than propositional logic, is briefly described, both syntactically and semantically. Next, the author discusses first-order epistemic logic, first-order reasoning about probability, and first-order conditional logic. He also shows that the more expressive power of first-order logic does not make it automatically a better tool (than propositional logic) for reasoning about uncertainty in all situations.
Chapter 11 - From Statistics to Beliefs In this chapter the author presents reference classes as an approach for relating statistics and an agent's beliefs. Due to the limitations of reference classes, he introduces the random-worlds approach as a more general alternative. The chapter also contains a discussion of the problems that are likely to arise with the random- worlds approach, and its application to default reasoning.
Chapter 12 - Final Words The conclusion is a summary of what the author considers as the key points in his discussion of uncertainty. He stresses, for example, the variety of approaches available to the representation of uncertainty, the advantages of using conditioning, and the value of having a general tool for the representation of uncertainty such as plausibility. The connection between statistical information and degrees of belief, which was the theme of chapter 11, is said to be related to the larger problem of learning. He also suggests that there are situations in real life in which probability does not seem to be necessary for decisions. Thus, the formal reasoning about uncertainty could profit from the study of the situations in which simpler approaches can be used.
It is difficult to describe the positive aspects of the book in a concise paragraph, for there are many good points to highlight. It is a rich book, full of wide- spanning information. It is a panoramic view presented with depth, and a course book that can be used as a reference book. It also succeeds in discussing a huge collection of problems and approaches in a unified way, enabling the reader to see a strong sense of direction in the presentation.
I should also like to mention a few details:
- systematic references from one section to the other help the reader to perceive the links between them (this is especially relevant to students);
- several suggestions for research are given (for example, on pages 89 and 110);
- the solutions for paradoxes and puzzles are not presented as definite ones. The whole discussion, on the contrary, seems to stress that solutions depend on the representation chosen for uncertainty and also on several other assumptions (see, for example, comments on page 179). I consider the assessments of the Monty Hall puzzle particularly interesting;
- good humor is constant in the book, in an unassuming and easy way, which is quite an advantage for the reader.
The mathematical presentation of ideas, in terms of definitions and theorems, is likely to be time-consuming for those who do not usually deal with similar formalizations. Besides, the book discusses a large selection of concepts, including sets of possible worlds, algebras, probability, propositional logics, modal logics and even limits (although limits "do not play a significant role in the book", page 17). Depending on their background, a few readers may feel more comfortable with the logic-centered chapters, and a few others with the probability-centered chapters. I agree with the author (Preface, page xiii) that there is enough detail to help readers from different kinds of background to find their way through the text. However, some previous training in propositional logic and probability is not only helpful but, in my view, necessary.
Surely, uncertainty is a fundamental feature of human language. So, linguists can profit immensely from the accurate, thorough way in which the technical results and conceptual discussions are presented in this book. However, this book seems to have been primarily intended for researchers in other areas (computer science, artificial intelligence, economics, mathematics, philosophy and statistics are mentioned, non-exclusively, in the Preface). I think it was not, unfortunately, written with linguists in mind, for only a small number of passages in the book mention the treatment of human language. Similarly, none of the examples and puzzles are about human language, as far as I could see. Thus, it does not seem directly appropriate as a course book for students of linguistics, with the possible exception of very specific cases, such as graduate programs on computational linguistics with a heavy emphasis on the formal description of tools. In summary, Reasoning about Uncertainty is an excellent book for all linguists interested in the philosophical discussion of uncertainty and on the formal tools for representing it, but it does not directly examine uncertainty in natural languages. I hope that a new book comes out soon, building a more explicit bridge between what was presented in this book and the current research on human language from the point of view of linguistics.
ABOUT THE REVIEWER:
ABOUT THE REVIEWER
Maria Leonor Santos teaches Linguistics at Federal University of Paraíba, Brazil, and is now working on her thesis on conditionals (in Brazilian Portuguese) at Federal University of Santa Catarina. Her main interests are Logic, Lexical Semantics, and History of Linguistics.