Publishing Partner: Cambridge University Press CUP Extra Wiley-Blackwell Publisher Login
amazon logo
More Info

New from Oxford University Press!


The Vulgar Tongue: Green's History of Slang

By Jonathon Green

A comprehensive history of slang in the English speaking world by its leading lexicographer.

New from Cambridge University Press!


The Universal Structure of Categories: Towards a Formal Typology

By Martina Wiltschko

This book presents a new theory of grammatical categories - the Universal Spine Hypothesis - and reinforces generative notions of Universal Grammar while accommodating insights from linguistic typology.

New from Brill!


Brill's MyBook Program

Do you have access to Dynamics of Morphological Productivity through your library? Then you can by the paperback for only €25 or $25! Find out more about Brill's MyBook program!

Email this page
E-mail this page

Review of  Reasoning About Uncertainty

Reviewer: Maria Leonor Santos
Book Title: Reasoning About Uncertainty
Book Author: Joseph Y. Halpern
Publisher: MIT Press
Linguistic Field(s): Computational Linguistics
Book Announcement: 15.793

Discuss this Review
Help on Posting
Date: Tue, 02 Mar 2004 11:44:22 -0300
From: Leonor Santos <>
Subject: Reasoning About Uncertainty

AUTHOR: Halpern, Joseph Y.
TITLE: Reasoning About Uncertainty
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

(numeric representations for uncertainty)
- Probability Measures
- Lower and Upper Probabilities
- Dempster-Shafer Belief Functions
- Possibility Measures
- Ranking Functions

(nonnumeric representations)
- Relative Likelihood
- Plausibility Measures

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

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.

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.

Amazon Store: