A model of knowledge representation is described in which propositional facts and the relationships among them can be supported by other facts. The set of knowledge which can be supported is called the set of cognitive units, each having associated descriptions of their explicit and implicit support structures, summarizing belief and reliability of belief. This summary is precise enough to be useful in a computational model while remaining descriptive of the underlying symbolic support structure. When a fact supports another supportive relationship between facts we call this meta-support. This facilitates reasoning about both the propositional knowledge. and the support structures underlying it.

In [12], Nilsson proposed the probabilistic logic in which the truth values of logical propositions are probability values between 0 and 1. It is applicable to any logical system for which the consistency of a finite set of propositions can be established. The probabilistic inference scheme reduces to the ordinary logical inference when the probabilities of all propositions are either 0 or 1. This logic has the same limitations of other probabilistic reasoning systems of the Bayesian approach. For common sense reasoning, consistency is not a very natural assumption. We have some well known examples: {Dick is a Quaker, Quakers are pacifists, Republicans are not pacifists, Dick is a Republican}and {Tweety is a bird, birds can fly, Tweety is a penguin}. In this paper, we shall propose some extensions of the probabilistic logic. In the second section, we shall consider the space of all interpretations, consistent or not. In terms of frames of discernment, the basic probability assignment (bpa) and belief function can be defined. Dempster's combination rule is applicable. This extension of probabilistic logic is called the evidential logic in [ 1]. For each proposition s, its belief function is represented by an interval [Spt(s), Pls(s)]. When all such intervals collapse to single points, the evidential logic reduces to probabilistic logic (in the generalized version of not necessarily consistent interpretations). Certainly, we get Nilsson's probabilistic logic by further restricting to consistent interpretations. In the third section, we shall give a probabilistic interpretation of probabilistic logic in terms of multi-dimensional random variables. This interpretation brings the probabilistic logic into the framework of probability theory. Let us consider a finite set S = {sl, s2, ..., Sn) of logical propositions. Each proposition may have true or false values; and may be considered as a random variable. We have a probability distribution for each proposition. The e-dimensional random variable (sl,..., Sn) may take values in the space of all interpretations of 2n binary vectors. We may compute absolute (marginal), conditional and joint probability distributions. It turns out that the permissible probabilistic interpretation vector of Nilsson [12] consists of the joint probabilities of S. Inconsistent interpretations will not appear, by setting their joint probabilities to be zeros. By summing appropriate joint probabilities, we get probabilities of individual propositions or subsets of propositions. Since the Bayes formula and other techniques are valid for e-dimensional random variables, the probabilistic logic is actually very close to the Bayesian inference schemes. In the last section, we shall consider a relaxation scheme for probabilistic logic. In this system, not only new evidences will update the belief measures of a collection of propositions, but also constraint satisfaction among these propositions in the relational network will revise these measures. This mechanism is similar to human reasoning which is an evaluative process converging to the most satisfactory result. The main idea arises from the consistent labeling problem in computer vision. This method is originally applied to scene analysis of line drawings. Later, it is applied to matching, constraint satisfaction and multi sensor fusion by several authors [8], [16] (and see references cited there). Recently, this method is used in knowledge aggregation by Landy and Hummel [9].

One of the most important aspects of current expert systems technology is the ability to make causal inferences about the impact of new evidence. When the domain knowledge and problem knowledge are uncertain and incomplete Bayesian reasoning has proven to be an effective way of forming such inferences [3,4,8]. While several reasoning schemes have been developed based on Bayes Rule, there has been very little work examining the comparative effectiveness of these schemes in a real application. This paper describes a knowledge based system for ship classification [1], originally developed using the PROSPECTOR updating method [2], that has been reimplemented to use the inference procedure developed by Pearl and Kim [4,5]. We discuss our reasons for making this change, the implementation of the new inference engine, and the comparative performance of the two versions of the system.

The fundamental elements of evidential reasoning problems are described, followed by a discussion of the structure of various types of problems. Bayesian inference networks and state space formalism are used as the tool for problem representation. A human-oriented decision making cycle for solving evidential reasoning problems is described and illustrated for a military situation assessment problem. The implementation of this cycle may serve as the basis for an expert system shell for evidential reasoning; i.e. a situation assessment processor.

During the ongoing debate over the representation of uncertainty in Artificial Intelligence, Cheeseman, Lemmer, Pearl, and others have argued that probability theory, and in particular the Bayesian theory, should be used as the basis for the inference mechanisms of Expert Systems dealing with uncertainty. In order to pursue the issue in a practical setting, sophisticated tools for knowledge engineering are needed that allow flexible and understandable interaction with the underlying knowledge representation schemes. This paper describes a Generalized Bayesian framework for building expert systems which function in uncertain domains, using algorithms proposed by Lemmer. It is neither rule-based nor frame-based, and requires a new system of knowledge engineering tools. The framework we describe provides a knowledge-based system architecture with an inference engine, explanation capability, and a unique aid for building consistent knowledge bases.

This paper presents a methodology for research and development of the inferencing and knowledge representation aspects of an Expert System approach for performing reasoning under uncertainty in support of a real time vehicle guidance and navigation system. Such a system could be of major benefit for non-terrain following low altitude flight systems operating in foreign hostile environments such as might be experienced by NOE helicopter or similar mission craft. An innovative extension of the evidential reasoning methodology, termed the Sum-and-Lattice-Points Method, has been developed. The research and development effort presented in this paper consists of a formal mathematical development of the Sum-and-Lattice-Points Method, its formulation and representation in a parallel environment, prototype software development of the method within an expert system, and initial testing of the system within the confines of the vehicle guidance system.

Although many investigators affirm a desire to build reasoning systems that behave consistently with the axiomatic basis defined by probability theory and utility theory, limited resources for engineering and computation can make a complete normative analysis impossible. We attempt to move discussion beyond the debate over the scope of problems that can be handled effectively to cases where it is clear that there are insufficient computational resources to perform an analysis deemed as complete. Under these conditions, we stress the importance of considering the expected costs and benefits of applying alternative approximation procedures and heuristics for computation and knowledge acquisition. We discuss how knowledge about the structure of user utility can be used to control value tradeoffs for tailoring inference to alternative contexts. We address the notion of real-time rationality, focusing on the application of knowledge about the expected timewise-refinement abilities of reasoning strategies to balance the benefits of additional computation with the costs of acting with a partial result. We discuss the benefits of applying decision theory to control the solution of difficult problems given limitations and uncertainty in reasoning resources.

Ross D. Shachter and Leonard J. Bertrand Department of Engineering-Economic Systems, Stanford University (visiting the Center for Health Policy Research and Education, Duke University, PO Box GM, Durham, NC 27706) and Strategic Decisions Group, Menlo Park, CA for the Third Workshop on Uncertainty in Artificial Intelligence Seattle, Washington, July 10-12, 1987 The generalized fault diagram, a data structure for failure analysis based on the influence diagram, is defined. Unlike the fault tree, this structure allows for dependence among the basic events and replicated logical elements. A heuristic procedure is developed for efficient processing of these structures. Deterministic logic and conditional probabilities are both appealing frameworks in which to build a knowledge base. Each has a natural graphical representation, semantic network for logic and influence diagrams (Howard and Matheson, 1981) or bayes networks (Pearl, 1986) for probabilities.

This paper reports work in progress on an explanation facility for Bayesian conditioning aimed at improving user acceptance of probability-based decision support systems. Design of the facility, which appears to be reasonably domain-independent, is based on an information processing model that accounts both for biased and normative behavior in reasoning about conditional evidence. Preliminary results indicate that the facility is both acceptable to naive users and effective in improving understanding of Bayesian conditioning.

A complete approach to reasoning under uncertainty requires support for incremental and interactive formulation and revision of, as well as reasoning with, models of the problem domain capable of representing our uncertainty. We present a hybrid reasoning scheme which combines symbolic and numeric methods for uncertainty management to provide efficient and effective support for each of these tasks. The hybrid is based on symbolic techniques adapted from Assumption-based Truth Maintenance systems (ATMS), combined with numeric methods adapted from the Dempster/Shafer theory of evidence, as extended in Baldwin's Support Logic Programming system. The hybridization is achieved by viewing an ATMS as a symbolic algebra system for uncertainty calculations. This technique has several major advantages over conventional methods for performing inference with numeric certainty estimates in addition to the ability to dynamically determine hypothesis spaces, including improved management of dependent and partially independent evidence, faster run-time evaluation of propositional certainties, the ability to query the certainty value of a proposition from multiple perspectives, and the ability to incrementally extend or revise domain models.