Probabilistic Reasoning in Intelligent Systems

Networks of Plausible Inference

Judea Pearl

• Publisher: Morgan Kaufmann
• Year: 2014
• Print ISBN: 9781558604797
• eBook ISBN: 9780080514895
• Topic: Computer Science
• Subtopic: Artificial Intelligence (AI) & Semantics
• Index: Computer Science

Probabilistic Reasoning in Intelligent Systems is a complete and accessible account of the theoretical foundations and computational methods that underlie plausible reasoning under uncertainty. The author provides a coherent explication of probability as a language for reasoning with partial belief and offers a unifying perspective on other AI approaches to uncertainty, such as the Dempster-Shafer formalism, truth maintenance systems, and nonmonotonic logic. The author distinguishes syntactic and semantic approaches to uncertainty--and offers techniques, based on belief networks, that provide a mechanism for making semantics-based systems operational. Specifically, network-propagation techniques serve as a mechanism for combining the theoretical coherence of probability theory with modern demands of reasoning-systems technology: modular declarative inputs, conceptually meaningful inferences, and parallel distributed computation. Application areas include diagnosis, forecasting, image interpretation, multi-sensor fusion, decision support systems, plan recognition, planning, speech recognition--in short, almost every task requiring that conclusions be drawn from uncertain clues and incomplete information.Probabilistic Reasoning in Intelligent Systems will be of special interest to scholars and researchers in AI, decision theory, statistics, logic, philosophy, cognitive psychology, and the management sciences. Professionals in the areas of knowledge-based systems, operations research, engineering, and statistics will find theoretical and computational tools of immediate practical use. The book can also be used as an excellent text for graduate-level courses in AI, operations research, or applied probability.

Chapter 1

UNCERTAINTY IN AI SYSTEMS

AN OVERVIEW

Publisher Summary

This chapter highlights the basic AI paradigms of dealing with uncertainty and describes the unique qualitative features that make probability theory a loyal guardian of plausible reasoning. AI researchers tackling the problems of uncertainty in AI can be classified into three formal schools: (1) logicist, (2) neo-calculist, and (3) neo-probabilist. The logicist school attempts to deal with uncertainty using nonnumerical techniques, primarily, nonmonotonic logic. The neo-calculist school uses numerical representations of uncertainty but regards probability calculus as inadequate for the task and, thus, invents entirely new calculi such as the Dempster–Shafer calculus, fuzzy logic, and certainty factors. The neo-probabilists remain within the traditional framework of probability theory, while attempting to buttress the theory with computational facilities needed to perform AI tasks. The extensional approach of dealing with uncertainty, also known as production systems, rule-based systems, and procedure-based systems, treats uncertainty as a generalized truth value attached to formulas and computes the uncertainty of any formula as a function of the uncertainties of its subformulas. In the intentional approach, also known as declarative or model-based, uncertainty is attached to states of affairs or subsets of possible worlds.

I consider the word probability as meaning the state of mind with respect to an assertion, a coming event, or any other matter on which absolute knowledge does not exist.

— August De Morgan, 1838

1.1 INTRODUCTION

1.1.1 Why Bother with Uncertainty?

Reasoning about any realistic domain always requires that some simplifications be made. The very act of preparing knowledge to support reasoning requires that we leave many facts unknown, unsaid, or crudely summarized. For example, if we choose to encode knowledge and behavior in rules such as “Birds fly” or “Smoke suggests fire,” the rules will have many exceptions which we cannot afford to enumerate, and the conditions under which the rules apply (e.g., seeing a bird or smelling smoke) are usually ambiguously defined or difficult to satisfy precisely in real life. Reasoning with exceptions is like navigating a minefield: Most steps are safe, but some can be devastating. If we know their location, we can avoid or defuse each mine, but suppose we start our journey with a map the size of a postcard, with no room to mark down the exact location of every mine or the way they are wired together. An alternative to the extremes of ignoring or enumerating exceptions is to summarize them, i.e., provide some warning signs to indicate which areas of the minefield are more dangerous than others. Summarization is essential if we wish to find a reasonable compromise between safety and speed of movement. This book studies a language in which summaries of exceptions in the minefield of judgment and belief can be represented and processed.

1.1.2 Why Is It a Problem?

One way to summarize exceptions is to assign to each proposition a numerical measure of uncertainty and then combine these measures according to uniform syntactic principles, the way truth values are combined in logic. This approach has been adopted by first-generation expert systems, but it often yields unpredictable and counterintuitive results, examples of which will soon be presented. As a matter of fact, it is remarkable that this combination strategy went as far as it did, since uncertainty measures stand for something totally different than truth values. Whereas truth values in logic characterize the formulas under discussion, uncertainty measures characterize invisible facts, i.e., exceptions not covered in the formulas. Accordingly, while the syntax of the formula is a perfect guide for combining the visibles, it is nearly useless when it comes to combining the invisibles. For example, the machinery of Boolean algebra gives us no clue as to how the exceptions to A → C interact with those of B → C to yield the exceptions to (A ∧ B) → C. These exceptions may interact in intricate and clandestine ways, robbing us of the modularity and monotonicity that make classical logic computationally attractive.

Although formulas interact in intricate ways, in logic too, the interactions are visible. This enables us to calculate the impact of each new fact in stages, by a process of derivation that resembles the propagation of a wave: We compute the impact of the new fact on a set of syntactically related sentences S₁, store the results, then propagate the impact from S₁ to another set of sentences S₂, and so on, without having to return to S₁. Unfortunately, this computational scheme, so basic to logical deduction, cannot be justified under uncertainty unless one makes some restrictive assumptions of independence.

Another feature we lose in going from logic to uncertainty is incrementality. When we have several items of evidence, we would like to account for the impact of each of them individually: Compute the effect of the first item, then absorb the added impact of the next item, and so on. This, too, can be done only after making restrictive assumptions of independence. Thus, it appears that uncertainty forces us to compute the impact of the entire set of past observations to the entire set of sentences in one global step—this, of course, is an impossible task.

1.1.3 Approaches to Uncertainty

AI researchers tackling these problems can be classified into three formal schools, which I will call logicist, neo-calculist, and neo-probabilist. The logicist school attempts to deal with uncertainty using nonnumerical techniques, primarily nonmonotonic logic. The neo-calculist school uses numerical representations of uncertainty but regards probability calculus as inadequate for the task and thus invents entirely new calculi, such as the Dempster-Shafer calculus, fuzzy logic, and certainty factors. The neo-probabilists remain within the traditional framework of probability theory, while attempting to buttress the theory with computational facilities needed to perform AI tasks. There is also a school of researchers taking an informal, heuristic approach [Cohen 1985; Clancey 1985; Chandrasekaran and Mittal 1983], in which uncertainties are not given explicit notation but are instead embedded in domain-specific procedures and data structures.

This taxonomy is rather superficial, capturing the syntactic rather than the semantic variations among the various approaches. A more fundamental taxonomy can be drawn along the dimensions of extensional vs. intensional approaches.^† The extensional approach, also known as production systems, rule-based systems, and procedure-based systems, treats uncertainty as a generalized truth value attached to formulas and (following the tradition of classical logic) computes the uncertainty of any formula as a function of the uncertainties of its subformulas. In the intensional approach, also known as declarative or model-based, uncertainty is attached to “states of affairs” or subsets of “possible worlds.” Extensional systems are computationally convenient but semantically sloppy, while intensional systems are semantically clear but computationally clumsy. The trade-off between semantic clarity and computational efficiency has been the main issue of concern in past research and has transcended notational boundaries. For example, it is possible to use probabilities either extensionally (as in PROSPECTOR [Duda, Hart, and Nilsson 1976]) or intensionally (as in MUNIN [Andreassen et al. 1987]). Similarly, one can use the Dempster-Shafer notation either extensionally [Ginsberg 1984] or intensionally [Lowrance, Garvey, and Strat 1986].

1.1.4 Extensional vs. Intensional Approaches

Extensional systems, a typical representative of which is the certainty-factors calculus used in MYCIN [Shortliffe 1976], treat uncertainty as a generalized truth value; that is, the certainty of a formula is defined to be a unique function of the certainties of its subformulas. Thus, the connectives in the formula serve to select the appropriate weight-combining function. For example, the certainty of the conjunction A ∧ B is given by some function (e.g., the minimum or the product) of the certainty measures assigned to A and B individually. By contrast, in intensional systems, a typical representative of which is probability theory, certainty measures are assigned to sets of worlds...

Table of contents

• Cover image
• Title page
• Table of Contents
• THE MORGAN KAUFMANN SERIES IN REPRESENTATION AND REASONING
• Copyright
• Dedication
• Preface
• Preface to the Fourth Printing
• Chapter 1: UNCERTAINTY IN AI SYSTEMS: AN OVERVIEW
• Chapter 2: BAYESIAN INFERENCE
• Chapter 3: MARKOV AND BAYESIAN NETWORKS: Two Graphical Representations of Probabilistic Knowledge
• Chapter 4: BELIEF UPDATING BY NETWORK PROPAGATION
• Chapter 5: DISTRIBUTED REVISION OF COMPOSITE BELIEFS
• Chapter 6: DECISION AND CONTROL
• Chapter 7: TAXONOMIC HIERARCHIES, CONTINUOUS VARIABLES, AND UNCERTAIN PROBABILITIES
• Chapter 8: LEARNING STRUCTURE FROM DATA
• Chapter 9: NON-BAYESIAN FORMALISMS FOR MANAGING UNCERTAINTY
• Chapter 10: LOGIC AND PROBABILITY: THE STRANGE CONNECTION
• Bibliography
• Author Index
• Subject Index