Uncertainty in Artificial Intelligence 5 (eBook)

Front Cover 1
Uncertainty in Artificial Intelligence 5 4
Copyright Page 5
Table of Contents 8
Preface 6
Reviewers 12
Program Committee 12
Contributors 14
PART I: FUNDAMENTAL ISSUES 16
Chapter 1. Lp—A Logic for Statistical Information 18
1 Introduction 18
2 Other Probability Logics 19
3 Types of Statistical Knowledge 19
4 Syntax and Semantics 20
5 Syntax 21
6 Examples of Representation 23
7 Deductive Proof Theory 24
8 Degrees of Belief 27
Acknowledgments 28
References 28
CHAPTER 
30 
1 INTRODUCTION1 30
2 THE DISTRIBUTION OF TIME 31
3 MARKED POINT PROCESS REPRESENTATION 32
4 NETWORKS OF "DATES" 34
Acknowledgements 43
References 43
CHAPTER 
44 
1. Introduction 44
2. The credibility function 45
3. a-combined credibility spaces 46
4. The pignistic probability function 49
5. Co-credibility function 52
6. The Moebius transformations of Cr 52
7. Conclusions 53
Bibliography 53
Acknowledgements 54
Chapter 4. Can Uncertainty Management Be Realized In A Finite Totally Ordered Probability Algebra? 56
1 Introduction 56
2 Finite totally ordered probability algebras 57
3 Bayes theorem and reasoning by case 62
4 Problems with legal finite totally ordered probability 63
5 An experiment 66
6 Conclusion 68
Acknowledgements 68
References 68
Appendix A: Derivation of 69
Appendix B: Examples of legal FTOPAs 70
Appendix C 71
PART Il: DEFEASIBLE REASONING AND UNCERTAINTY 74
Chapter 5. Defeasible Reasoning and Uncertainty: Comments 76
1 Overview 76
2 Goldszmidt & Pearl
3 Bonissone et al 77
4 Loui 79
5 Reference Classes: What They Didn't Talk About, But Somebody Should! 80
Acknowledgements 80
References 80
Chapter 6. Uncertainty and Incompleteness: Breaking the Symmetry of Defeasible Reasoning 82
1 Introduction 82
2 Plausible Reasoning Module 87
3 Finding Admissible Labelings 89
4 Algorithms and Heuristics 94
5 Conclusions 96
References 97
Chapter 7. Deciding Consistency of Databases Containing Defeasible and Strict Information 102
1 Introduction 102
2 Notation and Preliminary Definitions 104
3 Probabilistic Consistency and Entailment 105
4 An Effective Procedure for Testing Consistency 108
5 Examples 109
6 Conclusions 111
Acknowledgments 111
References 111
CHAPTER 
114 
1 WHAT THE PROPOSAL IS 114
2 WHAT THE PROPOSAL ISN'T 126
3 AN OPEN CONVERSATION WITH RAIFFA 130
CHAPTER 
132 
1. INTRODUCTION 132
2. DOES AN EMU OR OSTRICH RUN? 134
3. ARTS STUDENTS AND SCIENCE STUDENTS 135
4. DISCUSSION OF THE PARADOX 136
6. CONCLUSIONS 138
ACKNOWLEDGEMENTS 139
REFERENCES 139
PART Ill: ALGORITHMS FOR INFERENCE IN BELIEF NETS 142
Chapter 10. An Introduction to Algorithms for Inference in Belief Nets 144
1. Introduction 144
2. Qualitative, real, and interval-valued belief representations 144
3. Early approaches 145
4. Exact methods 146
5. Two level belief networks 147
6. Stochastic simulation and Monte Carlo schemes 148
7. Final remarks 150
References 151
CHAPTER 
154 
1. INTRODUCTION 154
2. SOUNDNESS AND COMPLETENESS OF d -SEPARATION 155
3. THE MAIN RESULTS 157
ACKNOWLEDGEMENT 162
REFERENCES 163
Chapter 12. Interval Influence Diagrams 164
1 Introduction 164
2 Probabilistic Inference with Bounds on Probabilities 165
3 Interval Influence Diagrams 166
4 Transformations 167
5 Example 171
6 Computational Characteristics 174
7 Conclusions 174
References 175
Chapter 13. A Tractable Inference Algorithm for Diagnosing Multiple Diseases 178
1 Introduction 178
2 The QMR model 179
3 The Quickscore Algorithm 181
4 Run-Time Performance of Quickscore 184
5 Weaknesses of the Algorithm 184
6 Conclusion 185
7 Acknowledgments 185
References 185
CHAPTER 
188 
1. Introduction 188
2. Belief Diagrams 189
3. Evidence Nodes and Evidence Propagation 190
4. Probability Propagation 197
5. Control of the Evidence Process 200
6. Comparisons with the Pearl and the Lauritzen and Spiegelhalter Algorithms 202
7. Conclusions 204
References 205
Chapter 15. An Empirical Evaluation of a Randomized Algorithm for Probabilistic Inference 206
1. Introduction 206
2. Methods and Procedures 208
3. Results 214
4. Discussion and Conclusions 218
5. Acknowledgments 221
References 221
Chapter 16. Weighing and Integrating Evidence for Stochastic Simulation in Bayesian Networks 224
1 Introduction 224
2 The Evidence Weighting Technique 226
3 Evidence Weighting With Evidential Integration 227
4 Example 229
5 Discussion 230
6 Conclusions 233
References 234
CHAPTER 
236 
1. Introduction 236
2. The Algorithms 237
3. Test Results 240
4. Conclusions 242
5. Acknowledgments 245
References 245
PART IV: SOFTWARE TOOLS FOR UNCERTAIN REASONING 248
Chapter 18. Software tools for uncertain reasoning: An Introduction 250
Chapter 19. Now that I Have a Good Theory of Uncertainty, What Else Do I Need? 252
1 Normative vs. Prescriptive Theories of Uncertainty 252
2 Dynamic Classification Problems: Situation Assessment 253
3 RUM's Theory and Constraints 255
4 The Integrated RUM/RUMrunner Technology 259
5 Addressing the DCP's Reasoning Requirements 264
6 RUM/RUMrunner Applications 266
7 Conclusions 267
References 267
Chapter 20. Knowledge Acquisition Techniques for Intelligent Decision Systems: Integrating Axotl and Aquinas in DDUCKS 270
1. INTRODUCTION 270
2. APPROACH 274
3. DISCUSSION 281
ACKNOWLEDGEMENTS 282
REFERENCES 283
Chapter 21. BaRT: A Bayesian Reasoning Tool for Knowledge Based Systems 286
1. Introduction 286
2. Classificatory Problem Solving 288
3. A Bayesian Reasoning Tool 291
4. Conclusion 295
Acknowledgements 295
References 295
PART V: KNOWLEDGE ACQUISITION, MODELLING, AND EXPLANATION 298
Chapter 22. Assessment, criticism and improvement of imprecise subjective probabilities for a medical expert system 300
1. Introduction 300
2. Background, Assessments and Data 301
3. Criticising the probability assessments 302
4. Discrimination and Reliability 304
5. Learning from experience 306
6. Discussion 307
Acknowledgments 308
References 308
Chapter 23. Automated construction of sparse Bayesian networks from unstructured probabilistic models and domain information 310
1 Introduction 311
2 Bayesian networks 312
3 The construction algorithm 314
4 Results 317
5 Discussion and further work 318
6 Acknowledgements 321
References 323
Chapter 24. A Decision-Analytic Model for Using Scientific Data 324
I THE PROPLEM 324
2 A MODEL FOR THE USE OF REPORTED SCIENTIFIC DATA 326
3 USING BIASES TO PARAMETERIZE THE SPACE OF CLINICAL STUDIES 329
4 PREVIOUS ATTEMPTS TO MODEL THE USE OF SCIENTIFIC DATA 331
5 USES OF THE MODEL 331
ACKNOWLEDGMENTS 332
REFERENCES 332
Chapter 25. Verbal expressions for probability updates How much more probable is "much more probable"? 334
1. Introduction 334
2. Hypotheses about Phrase Selection Functions 335
3. Experimental Design 337
4. Analysis 338
5. Conclusions 341
Acknowledgements 342
Footnotes 342
References 342
PART VI: APPLICATIONS TO VISION AND RECOGNITION 344
Chapter 26. Map Learning with Indistinguishable Locations 346
1 Introduction 346
2 Spatial Modeling 347
3 Map Learning 350
4 Discussion 354
5 Related Work 355
References 356
Chapter 27. Plan Recognition in Stories and in Life 358
1 Introduction 358
2 Preliminaries 359
3 The "Knob" Theory 361
4 The "Mention" Theory 364
5 Conclusion 365
Appendix: Work in Progress 366
References 366
Chapter 28. HIERARCHICAL EVIDENCE ACCUMULATION IN THE PSEIKI SYSTEM and EXPERIMENTS IN MODEL-DRIVEN MOBILE ROBOT NAVIGATION 368
1. APPLICATION 368
2. REPRESENTATION AND FLOW OF CONTROL 370
3. ACCUMULATION OF EVIDENCE 376
4. EDGE-BASED vs. REGION-BASED OPERATION 380
5. ARE INDEPENDENCE CONDITIONS SATISFIED? 381
6. ROBOT SELF-LOCATION USING PSEIKI 381
7. CONCLUDING REMARKS 383
8. REFERENCES 384
Chapter 29. Model-Based Influence Diagrams For Machine Vision 386
1 Introduction 386
2 Model-Based Reasoning for Machine Vision 388
3 Sequential Control for Machine Vision Inference 389
4 Model Guided Influence Diagram Construction 390
5 Dynamic Instantiation for Sequential Control 393
6 Conclusions 399
Acknowledgments 402
References 402
CHAPTER 
404 
1 INTRODUCTION 404
2 DEMPSTER SHAFER THEORY REVIEW 405
3 PROPOSITIONAL LOGIC REVIEW 406
4 DEMPSTER SHAFER THEORY FORMULATION IN LOGIC-BASED TERMS 406
5 ATMS-BASED IMPLEMENTATION OF DEMPSTER SHAFER THEORY 409
6 MODEL-BASED VISUAL RECOGNITION USING AN EXTENDED ATMS 412
7 DISCUSSION 419
ACKNOWLEDGEMENTS 419
References 419
Chapter 31. Efficient Parallel Estimation for Markov Random Fields 422
1 Introduction 422
2 Generating Most Probable Labelings 423
3 Markov Random Fields 424
4 HCF 425
5 Local HCF 426
6 Test Results 426
7 Conclusions and Future Work 430
A Proof of Convergence for Local HCF 432
B Comparing Local HCF and HCF 433
References 433
PART VII: COMPARING APPROACHES TO UNCERTAIN REASONING 436
Chapter 32. Comparing Approaches to Uncertain Reasoning: Discussion System Condemnation Pays Off 438
CHAPTER 
442 
1.0 INTRODUCTION 442
2.0 FALLIBLE VS. INFALLIBLE ADVICE 444
3.0 OVERCOMING THE COST OF FALLIBILITY 447
4.0 DISCUSSION 450
REFERENCES 451
CHAPTER 
452 
1.0 SATISFYING REQUIREMENTS 452
2.0 STANDARD INFERENCE POLICIES 453
3.0 NONSTANDARD INFERENCE POLICIES 455
4.0 SUMMARY AND DISCUSSION 459
REFERENCES 459
CHAPTER 35. COMPARING EXPERT SYSTEMS BUILT USING DIFFERENT UNCERTAIN INFERENCE SYSTEMS 460
1. INTRODUCTION 460
2. METHOD 462
3. RESULTS AND DISCUSSION 465
4. CONCLUSIONS 468
5. REFERENCES 469
Chapter 36. Shootout-89, An Evaluation of Knowledge-based Weather Forecasting Systems 472
Author index 474