General problems in analyzing information in a probabilistic database are considered. The practical difficulties (and occasional advantages) of storing uncertain data, of using it conventional forward- or backward-chaining inference engines, and of working with a probabilistic version of resolution are discussed. The background for this paper is the incorporation of uncertain reasoning facilities in MRS, a general-purpose expert system building tool.

Evidential reasoning in expert systems has often used ad-hoc uncertainty calculi. Although it is generally accepted that probability theory provides a firm theoretical foundation, researchers have found some problems with its use as a workable uncertainty calculus. Among these problems are representation of ignorance, consistency of probabilistic judgements, and adjustment of a priori judgements with experience. The application of metaprobability theory to evidential reasoning is a new approach to solving these problems. Metaprobability theory can be viewed as a way to provide soft or hard constraints on beliefs in much the same manner as the Dempster-Shafer theory provides constraints on probability masses on subsets of the state space. Thus, we use the Dempster-Shafer theory, an alternative theory of evidential reasoning to illuminate metaprobability theory as a theory of evidential reasoning. The goal of this paper is to compare how metaprobability theory and Dempster-Shafer theory handle the adjustment of beliefs with evidence with respect to a particular thought experiment. Sections 2 and 3 give brief descriptions of the metaprobability and Dempster-Shafer theories. Metaprobability theory deals with higher order probabilities applied to evidential reasoning. Dempster-Shafer theory is a generalization of probability theory which has evolved from a theory of upper and lower probabilities. Section 4 describes a thought experiment and the metaprobability and DempsterShafer analysis of the experiment. The thought experiment focuses on forming beliefs about a population with 6 types of members {1, 2, 3, 4, 5, 6}. A type is uniquely defined by the values of three features: A, B, C. That is, if the three features of one member of the population were known then its type could be ascertained. Each of the three features has two possible values, (e.g. A can be either "a0" or "al"). Beliefs are formed from evidence accrued from two sensors: sensor A, and sensor B. Each sensor senses the corresponding defining feature. Sensor A reports that half of its observations are "a0" and half the observations are 'al'. Sensor B reports that half of its observations are ``b0,' and half are "bl". Based on these two pieces of evidence, what should be the beliefs on the distribution of types in the population? Note that the third feature is not observed by any sensor.

A FRAMEWORK FOR NONMONOTONIC REASONING ABOUT PROBABILISTIC ASSUMPTIONS-- The Problem Marvin S. Cohen Decision Science Consortium, Inc. Attempts to replicate probabilistic reasoning in expert systems have typically overlooked a critical ingredient of that process. The application of such models is often an iterative process, in which the plausibility of the results confirms or disconfirms the validity of assumptions made in building the model. In current expert systems, by contrast, probabilistic information is encapsulated within modular rules (involving, for example, "certainty factors"), and there is no mechanism for reviewing the overall form of the probability argument or the validity of the judgments entering into it. It involves the design of an expert system inference framework in which probabilistic statements and rules are regarded as assumptions which are explicitly tracked and reevaluated when they lead to conflict among different sources of evidence or lines of reasoning. Two conceptions of conflict and conflict resolution have been implicit in most approaches to this area. From one point of view, divergence among lines of reasoning can be regarded as stochastic; it is expected to occur some small percentage of the time, due to the chance accumulation of small errors or "noise" in an imperfect process of "measurement". From another point of view, however, divergence can be regarded as a result of faulty beliefs; that is, conflicting results are taken as evidence that one or more premises or forms of argument that led to the conflict are mistaken.

The management of uncertainty in expert systems has usually been left to ad hoc representations and rules of combinations lacking either a sound theory or clear semantics. The objective of this paper is to establish a theoretical basis for defining the syntax and semantics of a small subset of calculi of uncertainty operating on a given term set of linguistic statements of likelihood. Each calculus is defined by specifying a negation, a conjunction and a disjunction operator. Families of Triangular norms and conorms constitute the most general representations of conjunction and disjunction operators. These families provide us with a formalism for defining an infinite number of different calculi of uncertainty. The term set will define the uncertainty granularity, i.e. the finest level of distinction among different quantifications of uncertainty. This granularity will limit the ability to differentiate between two similar operators. Therefore, only a small finite subset of the infinite number of calculi will produce notably different results. This result is illustrated by two experiments where nine and eleven different calculi of uncertainty are used with three term sets containing five, nine, and thirteen elements, respectively. Finally, the use of context dependent rule set is proposed to select the most appropriate calculus for any given situation. Such a rule set will be relatively small since it must only describe the selection policies for a small number of calculi (resulting from the analyzed trade-off between complexity and precision).

This paper covers two topics: first an introduction to Algorithmic Complexity Theory: how it defines probability, some of its characteristic properties and past successful applications. Second, we apply it to problems in A.I. - where it promises to give near optimum search procedures for two very broad classes of problems.

Various properties of relative entropy have led to its widespread use in information theory. These properties suggest that relative entropy has a role to play in systems that attempt to perform inference in terms of probability distributions. In this paper, I will review some basic properties of relative entropy as well as its role in probabilistic inference. I will also mention briefly a few existing and potential applications of relative entropy to so-called artificial intelligence (AI).

Judea Pearl Computer Science Department, Univenity of California, Loa Angelea The paper demonstrates that strict adherence to probability theory does not preclude the use of concurrent, self-activated constraint-propagation mechanisms for managing uncer tainty. Maintaining local records of sources-of-belief allows both predictive and diagnostic inferences to be activated simultanously and propagate harmoniously towards a stable equillibrium.

The use of maximum entropy inference in reasoning with uncertain information is commonly justified by an information-theoretic argument. This paper discusses a possible objection to this information-theoretic justification and shows how it can be met. I then compare maximum entropy inference with certain other currently popular methods for uncertain reasoning. In making such a comparison, one must distinguish between static and dynamic theories of degrees of belief: a static theory concerns the consistency conditions for degrees of belief at a given time; whereas a dynamic theory concerns how one's degrees of belief should change in the light of new information. It is argued that maximum entropy is a dynamic theory and that a complete theory of uncertain reasoning can be gotten by combining maximum entropy inference with probability theory, which is a static theory. This total theory, I argue, is much better grounded than are other theories of uncertain reasoning.

This paper examines the quantities used by MYCIN to reason with uncertainty, called certainty factors. It is shown that the original definition of certainty factors is inconsistent with the functions used in MYCIN to combine the quantities. This inconsistency is used to argue for a redefinition of certainty factors in terms of the intuitively appealing desiderata associated with the combining functions. It is shown that this redefinition accommodates an unlimited number of probabilistic interpretations. These interpretations are shown to be monotonic transformations of the likelihood ratio p(EIH)/p(El H). The construction of these interpretations provides insight into the assumptions implicit in the certainty factor model. In particular, it is shown that if uncertainty is to be propagated through an inference network in accordance with the desiderata, evidence must be conditionally independent given the hypothesis and its negation and the inference network must have a tree structure. It is emphasized that assumptions implicit in the model are rarely true in practical applications. Methods for relaxing the assumptions are suggested.

We propose an inequality paradigm for probabilistic reasoning based on a logic of upper and lower bounds on conditional probabilities. We investigate a family of probabilistic logics, generalizing the work of Nilsson [14]. We develop a variety of logical notions for probabilistic reasoning, including soundness, completeness justification; and convergence: reduction of a theory to a simpler logical class. We argue that a bound view is especially useful for describing the semantics of probabilistic knowledge representation and for describing intermediate states of probabilistic inference and updating. We show that the Dempster-Shafer theory of evidence is formally identical to a special case of our generalized probabilistic logic. Our paradigm thus incorporates both Bayesian "rule-based" approaches and avowedly non-Bayesian "evidential" approaches such as MYCIN and DempsterShafer. We suggest how to integrate the two "schools", and explore some possibilities for novel synthesis of a variety of ideas in probabilistic reasoning.