Pr,吃face
This book is the culmination of an investigation into the applicability of proba
bilistic methods to tasks requiring automated reasoning under uncertainty. The
result is a computation-minded interpretation of probability theory, an interpreta
tion that exposes the qualitative nature of this centuries-old formalism, its solid
epistemological foundation, its compatibility with human intuition and, most
importantly, its am巳nability to network representations and to parallel and distri
buted computation. From this vantage point 1 have attempted to provide a
coherent account of probability as a language for reasoning with partial beliefs and
bind it, in a unifying perspective, with other artificial intelligence (AI) approaches
to uncertainty, such as th巳 Dempster-Shafer formalism, truth maintenance systems,
and nonmonotonic logic.
Probabilistic Reasoning has been written with a variety of readers in mind. It
should b巳 of interest to scholars and researchers in AI, decision theory, statistics,
logic, philosophy, cognitive psychology, and
the management sciences.
Specifically, AI researchers can take an earτlest look at probability theory, now that
it is phrased in their language, and probabilists should be challenged by the new
issues that 巳merge from the AI experiment. In addition, practitioners in the areas
of knowledge-based systems, operations research, engineering, and statistics will
find a variety of theoretical and computational tools that should be of immediate
practica1 use. Application areas include diagnosis, forecasting , image understand
ing, multi-sensor fusion, decision support systems, plan recognition, planning and
control, speech recognition 一 in short, almost any task requiring that conclusions
be drawn from uncertain clues and incomplete information.
The book is also intended as a textbook for graduate-Ievel courses in AI, opera
tions research, and applied probability. In teaching this material at various levels
of sophistication, 1 have found that the conceptual tools students acquire by treat
ing the world probabilistically grow in value, even (perhaps especially) when the
students go on to pursue other formalisms.
To my own surprise, most of these chapters tumed out to be fairly self
contained, demanding only a basic understanding of the results established in pre
vious chapters.
Chapter 1 identifies the basic AI paradigms of dealing with un
Yll
Vll1
同re臼ce
Bayesian inferenc巳 and discusses some epistemological issues that emerge from
this formalism. Those who have had no previous exposure to probability theory
(some computer science students fall into this category) might wish to consult an
introductory textbook and should follow closely the examples in Chapter 2 and
work the exercis巳s at the end of that chapter. In general, an elementary course in
probability theory or decision analysis should be sufficient for mastering most of
the book.
The casual reader se巳king a painless glimpse at the basic issues of uncertainty
should read the less technical sections in each chapter. These are indicated by a
single asterisk (ηin th巳 Contents. Chapters 1, 9, and 10 will prove especially
useful for those s巳eking a comprehensive look at how the various formalisms are
related, and how they measure up to each other under the acid test of human
mtmtlOn.
The more technically orient巳d reader will want to follow th巳 sections marked
with a double asterisk (**), glancing occasionally at the definitions and results of
other sections. This path leads the reader from traditional Bayesian inference and
its graphical representations, into network propagation techniques (Chapters 4 and
5) and decision analysis (Chapter 6), and then into belief functions (Chapter 9) and
default reasoning (Chapter 10). Knowledge engineers and developers of expert
systems, for example, are advised to go straight to Section 3.3, then read Chapters
4, 5, 6, 7, and 9.
The most advanced sections, dealing with topics closer to current research
frontiers , are marked with a triple asterisk (***). These includ巳 the theory of
graphoids (Chapter 匀, leaming methods (Chapter 8), and probabilistic semantics
for default reasoning (Section 10.2).
The reader should not view these markings as strict delineators. Just as an
advanced ski run has flat stretches and a beginn町、 run has a mogul or two, there
will be occasional pointers to human-style reasoning in the midst of technical
discussions, and references to computational issues in the midst of philosophical
discussions. Some reviewers advised me to avoid this hybrid style of writing, but 1
felt that retreating toward a more traditional organization would deny the reader
the sense of excitement that led me to these explorations. By confessing the
speculative nature of my own cutiosity 1 hope to encourage further research in
these areas.
1 owe a great debt to many people who assis
Preface
lX
My academic and professional colleagues have been generous with their time
and ideas. 1 have been most influenced by the ideas of Stephen Lauritzen, Glenn
Shafer, and David Spiegelhalt巳r, and my collaborations with Azaria Paz and
Norman Dalkey have been very rewarding. Helpful comments on selected
sections were 0能red by Emst Adams, Moshe Ben-Bassat, Alan Bundy, Norman
Dalkey, Johan de Kleer, Arthur Dempster, Richard Duda, David Heckerman,
David Etherington, M缸 Henrion, Robert Goldman, Richard Je佳句 Henry
Kyburg, Vladimir Lifschi钮, John Lowrance, David McAllester, John Pollock,
Gregory Provan, Lenhart Schubert, Ross Shachter, Glenn Shafer and Michael
Wellman.
The National Science Foundation deserves acknowledgment for sponsoring the
research that led to these results , with special thanks to Y.T. Chien, Joe Dek巳ns ,
and the late Ken Curtis, who encouraged my research when 1 was still a junior
faculty member seeking an attentive ear. Other sponsors include Lashon Booker of
the Navy Research Laboratory, Abraham Waksman of the Air-Force Office of
Scientific Research, and Richard Weis of Aerojet Electro Systems.
The manuscript was most diligently typed, processed, illustrated and proofed
by Gina G巳orge and Jackie Trang, assisted by Nina Roop and Lillian Casey. 1
thank the publisher for accommodating my idiosyncracies, and special thanks to a
very special copy editor, Danny Pearl, whose uncompromising stance made these
pages readable.
Finally, 1 owe a great debt to the rest of my family: to Tammy for reminding
me why it all matters, to Michelle for making me feel useful and even drawing
some of the figures ,拍d especially to my wife Ruth for sheltering me from the
travails of the real world and sUITounding me with so much love, support, and
hope.
J.P.
Los Angeles, Califomia
June 1988
Contents
Chapter 1
UNCERTAINTY IN AI SYSTEMS: AN OVERVIEW
1.1
1.2
1.3
1.4
INTRODUCTION*
1.1.1 Why Bother with Uncertainty?
1.1.2 Why Is It a Problem?
1.1.3
1. 1.4
Approaches to Uncertainty
Extensiona1 vs. Intensiona1 Approaches
EXTENSIONAL SYSTEMS: MERITS , DEFICIENCIES,
AND REMEDIES*
1.2.1
1.2.2
1.2.3
Computationa1 Merits
Semantic Deficiencies
Attempted Remedies and their Limitations
INTENSIONAL SYSTEMS AND NETWORK
REPRESENTATIONS*
1.3.1 Why Networks?
1.3.2 Graphoids and the Formalization of Relevance and
Causa1ity
THE CASE FOR PROBABILITIES*
1.4.1 Why Should Beliefs Combine Like Frequencies?
1.4.2
η1巳卧imitive Relationships of Probability
Language
Probability as a Faithful Guardian of Common
Sense
1.4.3
'
1
1
i
7
"
q
』
句
3
4469
12
12
13
14
15
16
19
* Basic Issues
忡 Technical and Substantive Discussions
材* Advanced Reseatch
For a detailed explanation of these levels, see Preface.
Xll
Contents
1.5
QUALITATIVE REASONING WITH PROBABILITIES*
1.5.1
1. 5.2 阶obabilities and the Logic of "Almost True"
Softened Logic vs. Hardened Probabilities
1.6
BIBLIOGRAPHICAL AND HISTORICAL REMARKS
Chapter 2
BAYESIAN INFERENCE
2.1
2.2
2.3
BASIC CONCEPTS
2.1.1
2. 1.2
2.1.3
2. 1.4
2. 1.5 Multi-Va1ued Hypotheses**
Probabilistic Fonnulation and Bayesian Inversion*
Combining Predictive and Diagnostic Supports*
Pooling of Evidence*
Recursive Bayesian Updating*
Uncertain Evidence (Cascaded Inference)*
HIERARCHICAL MODELING
2.2.1
2.2.2 Virtual (Intangible) Evidence*
2.2.3
2.2.4 Multiple Causes and "Explaining Away"*
Belief Networks and the Role of Causality*
2.2.5
Predicting Future Events**
EPISTE如lOLOGICAL ISSUES OF BELIEF UPDATING
2.3.1
Patterns of Plausible Inference: Polya vs. Bayes?*
2.3.2
The Three Prisoners Paradox: When the Bare Facts
Won'tDo*
Je佳句's Rule and the Problem of Autonomous
Inference Agents*
2.3.3
2.4
BIBLIOGRAPHICAL AND HISTORICAL REMARKS
EXERCISES
Chapter 3
MARKOV AND BAYESIAN NETWORKS: Two Graphical
Representations of Probabilistic Knowledge
3.1
FROM NUMERICAL TO GRAPHICAL
REPRESENTATIONS
3. 1. 1
Introduction*
23
24
25
26
29
29
29
34
36
37
39
444445
224790
52
52
58
62
70
73
77
78
78
Contents
3.2
3.3
3. 1.2
An Axiomatic Basis for Probabilistic
Dependencies* *
3. 1.3 On Representing Dependencies by Undirected
3. 1.4
Graphs*
Axiomatic Characterization of Graph-Isomorph
Dependencies* **
Definitions and Formal Properties***
Illustrations * *
MARF豆OVNETWORKS
3.2.1
3.2.2
3.2.3 Markov Network as a Knowledge Base***
3.2.4
Decomposable Models**
BAYESIAN NETWORKS
3.3.1
3.3.2
3.3.3
Dependence Semantics for Bayesian Networks**
Bayesian Network as a Knowledge Base**
How Expressive Are Bayesian Networks?***
3.4
BIBLIOGRAPHICAL AND HISTORICAL REMARKS
EXERCISES
APPENDIX 3-A 1汁。of of Theorem 3
APPENDIX 3-B Proof of Theorem 4
Chapter 4
BELIEF UPDATING BY NETWORK PROPAGATION
4.1
4.2
AUTONOMOUS PROPAGATION AS A
COMPUTATIONAL PARADIGM
4.1.1
Constraint Propagation and Rule-based
Computation*
4. 1.2 Why Probabilistic Reasoning Seems to Resist
Propagation*
BELIEF PROPAGATION IN CAUSAL TREES
4.2.1
4.2.2
4.2.3
Notation* *
Propagation in Chains**
Propagation in Trees**
Xlll
82
90
93
96
96
100
104
108
116
117
122
126
131
134
139
141
143
144
145
148
150
150
153
162
XIV
4.3
4.4
BELIEF PROPAGATION IN CAUSAL POLYTREES
(SINGLY CONNECTED NETWORKS)
4.3.1
4.3.2
Propagation Rules**
Canonical Models ofMulticausal Interactions**
COPING WITH LOOPS
4.4.1
4.4.2
Clustering Methods*
The Method of Conditioning (Reasoning by
Assumptions)*
Stochastic Simulation * *
4.4.3
4.5 WHAT ELSE CAN BA YESIAN NETWORKS
COMPUTE?
4.5.1
4.5.2
4.5.3
Answering Queries*
Introducing Constraints*
Answ巳ring Conjunctive Queries**
4.6
BIBLIOGRAPHICAL AND HISTORICAL REMARKS
EXERCISES
APPENDIX 4-A Auxilliary Derivations for Section 4.5.3
Chapter 5
DlSTRIBUTED REVISION OF COMPOSITE BELlEFS
5.1
INTRODUCTION
5.2
5.3
ILLUSTRATING THE PROPAGATION SCHEME
5.2.1
5.2.2
Belief Updating (A Review)*
Belief Revision*
BELIEF REVISION IN SINGLY CONNECTED
NETWORKS
5.3.1
5.3.2
5.3.3
Deriving the Propagation Rules***
Summary of Propagation Rules*
Reaching Equilibrium and Assembling a
Composite Solution**
Comparison to Belief Updating*
Coping with Loops *
5.3.4
5.3.5
Contents
175
177
184
195
197
204
210
223
223
225
226
232
234
236
239
239
241
242
245
250
251
255
257
259
260
Contents
5.4
5.5
5.6
DIAGNOSIS OF SYSTEMS WITH MULTIPLE
FAULTS
5.4.1
5.4.2
5.4.3
5.4.4
An Examp1e: E1ectronic Circuit* *
Initia1ization* *
Fau1t Interpretation机
Finding the Second-Best Interpretation* *
The Causal Model *
APPLICATION TO MEDICAL DIAGNOSIS
5.5.1
5.5.2 Message Propagation材
5.5.3
5.5.4 Generating Exp1anations*
5.5.5
Choosing the Best Interpretation*
Reversibility vs. Perseverance*
THE NATURE OF EXPLANATIONS
5.6.1
5.6.2
5.6.3
Accepting vs. Assessing Beliefs*
Is a Most-Probable Explanation Adequate?*
Circumscribing Explanations *
5.7
CONCLUSIONS
5.8
BIBLIOGRAPHICAL AND HISTORICAL REMARKS
EXERCISES
Chapter 6
DECISION AND CONTROL
6.1
FROM BELIEFS TO ACTIONS: INTRODUCTION TO
DECISION ANALYSIS
6. 1. 1 Rational Decisions and Quality Guarantees*
6. 1.2
6.1.3
6. 1.4
6.1.5
Consequences, Payoffs, and Lotteries*
Calibrating the Value of a Lottery*
The Axioms of Utility Theory**
Utility Functions*
6.2
DECISION TREES AND INFLUENCE DIAGRAMS
6.2.1
6.2.2
6.2.3
Decision Trees*
Planning with Decision Trees*
Inftuence Diagrams*
xv
263
263
265
267
271
272
273
275
278
279
280
281
281
283
285
286
287
288
289
289
289
290
292
294
297
299
299
300
306