15.793, Review: Semantics: Halpern (2003)

[LINGUIST List]

LINGUIST List:  Vol-15-793. Sat Mar 6 2004. ISSN: 1068-4875.

Subject: 15.793, Review: Semantics: Halpern (2003)

Moderators: Anthony Aristar, Wayne State U.<aristar at linguistlist.org>
            Helen Dry, Eastern Michigan U. <hdry at linguistlist.org>

Reviews (reviews at linguistlist.org):
	Sheila Collberg, U. of Arizona
	Terence Langendoen, U. of Arizona

Home Page:  http://linguistlist.org/

The LINGUIST List is funded by Eastern Michigan University, Wayne
State University, and donations from subscribers and publishers.

Editor for this issue: Naomi Ogasawara <naomi at linguistlist.org>
 ==========================================================================
What follows is a review or discussion note contributed to our Book
Discussion Forum.  We expect discussions to be informal and
interactive; and the author of the book discussed is cordially invited
to join in.

If you are interested in leading a book discussion, look for books
announced on LINGUIST as "available for review." Then contact
Sheila Dooley Collberg at collberg at linguistlist.org.

=================================Directory=================================

1)
Date:  Sat, 6 Mar 2004 15:56:48 -0500 (EST)
From:  Leonor Santos <leonor at globalite.com.br>
Subject:  Reasoning about Uncertainty

-------------------------------- Message 1 -------------------------------

Date:  Sat, 6 Mar 2004 15:56:48 -0500 (EST)
From:  Leonor Santos <leonor at globalite.com.br>
Subject:  Reasoning about Uncertainty

AUTHOR: Halpern, Joseph Y.
TITLE: Reasoning About Uncertainty
PUBLISHER: MIT Press
YEAR: 2003

Announced at http://linguistlist.org/issues/14/14-3119.html


Maria Leonor Santos, Universidade Federal da Paraíba/
Universidade Federal de Santa Catarina

SYNOPSIS

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

(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
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.

CRITICAL EVALUATION

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

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.


---------------------------------------------------------------------------

If you buy this book please tell the publisher or author
that you saw it reviewed on the LINGUIST list.

---------------------------------------------------------------------------
LINGUIST List: Vol-15-793