Reasoning about Uncertainty, second edition / Edition 2

by Joseph Y. Halpern

Overview

Formal ways of representing uncertainty and various logics for reasoning about it; updated with new material on weighted probability measures, complexity-theoretic considerations, and other topics.

In order to deal with uncertainty intelligently, we need to be able to represent it and reason about it. In this book, Joseph Halpern examines formal ways of representing uncertainty and considers various logics for reasoning about it. While the ideas presented are formalized in terms of definitions and theorems, the emphasis is on the philosophy of representing and reasoning about uncertainty. Halpern surveys possible formal systems for representing uncertainty, including probability measures, possibility measures, and plausibility measures; considers the updating of beliefs based on changing information and the relation to Bayes' theorem; and discusses qualitative, quantitative, and plausibilistic Bayesian networks.

This second edition has been updated to reflect Halpern's recent research. New material includes a consideration of weighted probability measures and how they can be used in decision making; analyses of the Doomsday argument and the Sleeping Beauty problem; modeling games with imperfect recall using the runs-and-systems approach; a discussion of complexity-theoretic considerations; the application of first-order conditional logic to security.
Reasoning about Uncertainty is accessible and relevant to researchers and students in many fields, including computer science, artificial intelligence, economics (particularly game theory), mathematics, philosophy, and statistics.

Product Details

ISBN-13:	9780262533805
Publisher:	MIT Press
Publication date:	04/07/2017
Series:	The MIT Press
Edition description:	second edition
Pages:	504
Product dimensions:	6.90(w) x 9.00(h) x 1.10(d)
Age Range:	18 Years

About the Author

Joseph Y. Halpern is Professor of Computer Science at Cornell University. He is the author of Actual Causality and the coauthor of Reasoning about Knowledge, both published by the MIT Press.

Table of Contents

Preface xiii

Changes in the Second Edition xiv

1 Introduction and Overview 1

1.1 Some Puzzles and Problems 1

1.2 An Overview of the Book 4

Notes 9

2 Representing Uncertainty 11

2.1 Possible Worlds 12

2.2 Probability Measures 14

2.2.1 Justifying Probability 16

2.3 Lower and Upper Probabilities 23

2.4 Sets of Weighted Probability Measures 30

2.5 Lexicographic and Nonstandard Probability Measures 34

2.6 Dempster-Shafer Belief Functions 36

2.7 Possibility Measures 42

2.8 Ranking Functions 45

2.9 Relative Likelihood 47

2.10 Plausibility Measures 51

2.11 Choosing a Representation 55

Exercises 57

Notes 65

3 Updating Beliefs 71

3.1 Updating Knowledge 71

3.2 Probabilistic Conditioning 73

3.2.1 Justifying Probabilistic Conditioning 76

3.2.2 Bayes' Rule 78

3.3 Conditional (Nonstandard) Probability and Lexicographic Probability 80

3.4 Conditioning with Sets of Probabilities 82

3.5 Conditioning Sets of Weighted Probabilities 86

3.6 Evidence 88

3.7 Conditioning Inner and Outer Measures 92

3.8 Conditioning Belief Functions 94

3.9 Conditioning Possibility Measures 97

3.10 Conditioning Ranking Functions 98

3.11 Conditioning Plausibility Measures 99

3.11.1 Constructing Conditional Plausibility Measures 100

3.11.2 Algebraic Conditional Plausibility Spaces 102

3.12 Jeffrey's Rule 106

3.13 Relative Entropy 108

Exercises 111

Notes 116

4 Independence and Bayesian Networks 121

4.1 Probabilistic Independence 121

4.2 Probabilistic Conditional Independence 124

4.3 Independence for Plausibility Measures 126

4.4 Random Variables 128

4.5 Bayesian Networks 131

4.5.1 Qualitative Bayesian Networks 131

4.5.2 Quantitative Bayesian Networks 133

4.5.3 Independencies in Bayesian Networks 137

4.5.4 Plausibilistic Bayesian Networks 138

Exercises 140

Notes 143

5 Expectation 145

5.1 Expectation for Probability Measures 146

5.2 Expectation for Other Notions of Likelihood 148

5.2.1 Expectation for Sets of Probability Measures 149

5.2.2 Expectation for Belief Functions 150

5.2.3 Inner and Outer Expectation 154

5.2.4 Expectation for Possibility Measures and Ranking Functions 156

5.3 Plausibilistic Expectation 157

5.4 Decision Theory 159

5.4.1 The Basic Framework 159

5.4.2 Decision Rules 161

5.4.3 Generalized Expected Utility 165

5.4.4 Comparing Conditional Probability, Lexicographic Probability, and Nonstandard Probability 172

5.5 Conditional Expectation 175

Exercises 176

Notes 185

6 Multi-Agent Systems 189

6.1 Epistemic Frames 190

6.2 Probability Frames 192

6.3 Multi-Agent Systems 195

6.4 From Probability on Runs to Probability Assignments 200

6.5 Markovian Systems 204

6.6 Protocols 207

6.7 Using Protocols to Specify Situations 210

6.7.1 A Listener-Teller Protocol 210

6.7.2 The Second-Ace Puzzle 213

6.7.3 The Monty Hall Puzzle 215

6.7.4 The Doomsday Argument and the Sleeping Beauty Problem 216

6.7.5 Modeling Games with Imperfect Recall 219

6.8 When Conditioning Is Appropriate 224

6.9 Non-SDP Systems 228

6.10 Plausibility Systems 237

Exercises 237

Notes 240

7 Logics for Reasoning about Uncertainly 245

7.1 Propositional Logic 246

7.2 Modal Epistemic Logic 249

7.2.1 Syntax and Semantics 249

7.2.2 Properties of Knowledge 251

7.2.3 Axiomatizing Knowledge 254

7.2.4 A Digression: The Role of Syntax 256

7.3 Reasoning about Probability: The Measurable Case 259

7.4 Reasoning about Other Quantitative Representations of Likelihood 264

7.5 Reasoning about Relative Likelihood 267

7.6 Reasoning about Knowledge and Probability 271

7.7 Reasoning about Independence 274

7.8 Reasoning about Expectation 276

7.8.1 Syntax and Semantics 276

7.8.2 Expressive Power 277

7.8.3 Axiomatizations 278

7.9 Complexity Considerations 280

Exercises 284

Notes 289

8 Beliefs, Defaults, and Counterfactuals 293

8.1 Belief 294

8.2 Knowledge and Belief 297

8.3 Characterizing Default Reasoning 298

8.4 Semantics for Defaults 300

8.4.1 Probabilistic Semantics 300

8.4.2 Using Possibility Measures, Ranking Functions, and Preference Orders 303

8.4.3 Using Plausibility Measures 306

8.5 Beyond System P 310

8.6 Conditional Logic 315

8.7 Reasoning about Counterfactuals 318

8.8 Combining Probability and Counterfactuals 321

Exercises 321

Notes 331

9 Belief Revision 335

9.1 The Circuit-Diagnosis Problem 336

9.2 Belief-Change Systems 342

9.3 Belief Revision 345

9.4 Belief Revision and Conditional Logic 356

9.5 Epistemic States and Iterated Revision 357

9.6 Markovian Belief Revision 360

Exercises 362

Notes 364

10 First-Order Modal Logic 367

10.1 First-Order Logic 368

10.2 First-Order Reasoning about Knowledge 375

10.3 First-Order Reasoning about Probability 378

10.4 First-Order Conditional Logic 383

10.5 An Application: Qualitative and Quantitative Reasoning about Security Protocols 390

10.6 Combining First-Order Logic and Bayesian Networks 396

Exercises 398

Notes 401

11 From Statistics to Beliefs 405

11.1 Reference Classes 406

11.2 The Random-Worlds Approach 408

11.3 Properties of Random Worlds 412

11.4 Random Worlds and Default Reasoning 419

11.5 Random Worlds and Maximum Entropy 424

11.6 Problems with the Random-Worlds Approach 428

Exercises 430

Notes 436

12 Final Words 439

Notes 441

References 443

Glossary of Symbols 469

Index 473

What People are Saying About This

Bas C. van Fraassen

For some years now I have been testing a hypothesis: if a topic involving probability is of current interest to a philosopher, then Joseph Halpern has proved an important result that is relevant to it. Its accuracy can be gauged by the frequency with which I recommend his papers to colleagues and students. This book, which presents all these valuable contributions in a single volume, provides a rich source of technical and philosophical insight.

Glenn Shafer

For more than a decade, the study of uncertain reasoning has been graced by the breadth, openness, and agility of Joe Halpern's intellect. More than any of his colleagues, Joe has sought to reconcile and unify the diverse insights and methods for reasoning about knowledge and uncertainty that have been developed and championed in various academic fields. This cheerful, measured, and comprehensive book will bring Joe's tone, as well as his individual contributions, to the forefront of the field. I cannot imagine a better starting place for a student of the subject.

Peter P. Wakker

Uncertainty is a central topic in many domains, such as economics, logic, artificial intelligence, and statistics. It takes an omniscientist such as Joe Halpern to treat this topic in full. His book is a rich source of unique insights, offering unexpected connections between different fields.

Endorsement

Reasoning about Uncertainty pursues its own unified theoretical perspective in a remarkably systematic way, yet it is also a remarkably rich and complete textbook. It will be a rewarding book to work through for students and researchers alike.

—Wolfgang Spohn, Department of Philosophy, University of Konstanz

From the Publisher

Halpern presents a masterful, complete, and unified account of the many ways in which the connections between logic, probability theory, and commonsensical linguistic terms can be formalized. Terms such as 'true,' 'certain,' 'plausible,' 'possible,' 'believed,' 'known,' 'default,' 'relevant,' 'independent,' and 'preferred' are given rigorous semantical and syntactical analyses, and their interrelationships explicated and exemplified. An authoritative panoramic reference for philosophers, cognitive scientists, and artificial intelligence researchers.

— Judea Pearl , Computer Science Department, University of California, Los Angeles

For some years now I have been testing a hypothesis: if a topic involving probability is of current interest to a philosopher, then Joseph Halpern has proved an important result that is relevant to it. Its accuracy can be gauged by the frequency with which I recommend his papers to colleagues and students. This book, which presents all these valuable contributions in a single volume, provides a rich source of technical and philosophical insight.

— Bas C. van Fraassen , Department of Philosophy, Princeton University

Reasoning about Uncertainty pursues its own unified theoretical perspective in a remarkably systematic way, yet it is also a remarkably rich and complete textbook. It will be a rewarding book to work through for students and researchers alike.

— Wolfgang Spohn , Department of Philosophy, University of Konstanz

Wolfgang Spohn

Reasoning about Uncertainty pursues its own unified theoretical perspective in a remarkably systematic way, yet it is also a remarkably rich and complete textbook. It will be a rewarding book to work through for students and researchers alike.

Adam Brandenburger

Reasoning about Uncertainty is a very valuable synthesis of the mathematics of uncertainty as it has developed in a number of related fields — probability, statistics, computer science, game theory, artificial intelligence, and philosophy. Researchers in all of these fields will find this a very useful book — both for its elegant treatment of technical results and for its illuminating conceptual discussions.

Judea Pearl

Halpern presents a masterful, complete, and unified account of the many ways in which the connections between logic, probability theory, and commonsensical linguistic terms can be formalized. Terms such as 'true,' 'certain,' 'plausible,' 'possible,' 'believed,' 'known,' 'default,' 'relevant,' 'independent,' and 'preferred' are given rigorous semantical and syntactical analyses, and their interrelationships explicated and exemplified. An authoritative panoramic reference for philosophers, cognitive scientists, and artificial intelligence researchers.