Box 516, St. Louis, MO 63166 ABSTRACT This paper examines the accuracy of the PROSPECTOR model for uncertain reasoning. PROSPECTOR's solutions for a large number of computer·generated inference networks were compared to those obtained from probe· bility theory and minimum cross-entropy calculations. PROSPECTOR's answers were generally accurate for a restricted subset of problems that are consistent with its assumptions. However, even within this subset, we identified conditions under which PROSPECTOR's perfor· mance deteriorates. I NTRCOUCT I ON Researchers in artificial Intelligence have proposed or implemented several approaches to uncertain reason· in-- for knowledge-based systems.

This paper examines the biases and performance of several uncertain inference systems: Mycin, a variant of Mycin. and a simplified version of probability using conditional independence assumptions. We present axiomatic arguments for using Minimum Cross Entropy inference as the best way to do uncertain inference. For Mycin and its variant we found special situations where its performance was very good, but also situations where performance was worse than random guessing, or where data was interpreted as having the opposite of its true import We have found that all three of these systems usually gave accurate results, and that the conditional independence assumptions gave the most robust results. We illustrate how the Importance of biases may be quantitatively assessed and ranked. Considerations of robustness might be a critical factor is selecting UlS's for a given application.

The purpose of this paper is to report on the most recent developments in our ongoing investigation of the representation and manipulation of uncertainty in automated reasoning systems. In our earlier studies (Tong and Shapiro, 1985) we described a series of experiments with RUBRIC (Tong et al., 1985), a system for full-text document retrieval, that generated some interesting insights into the effects of choosing among a class of scalar valued uncertainty calculi. [n order to extend these results we have begun a new series of experiments with a larger class of representations and calculi, and to help perform these experiments we have developed a general purpose inference engine.

The role of inferencing with uncertainty is becoming more important in rule-based expert systems (ES), since knowledge given by a human expert is often uncertain or imprecise. We have succeeded in designing a VLSI chip which can perform an entire inference process based on fuzzy logic. The design of the VLSI fuzzy inference engine emphasizes simplicity, extensibility, and efficiency (operational speed and layout area). It is fabricated in 2.5 um CMOS technology. The inference engine consists of three major components; a rule set memory, an inference processor, and a controller. In this implementation, a rule set memory is realized by a read only memory (ROM). The controller consists of two counters. In the inference processor, one data path is laid out for each rule. The number of the inference rule can be increased adding more data paths to the inference processor. All rules are executed in parallel, but each rule is processed serially. The logical structure of fuzzy inference proposed in the current paper maps nicely onto the VLSI structure. A two-phase nonoverlapping clocking scheme is used. Timing tests indicate that the inference engine can operate at approximately 20.8 MHz. This translates to an execution speed of approximately 80,000 Fuzzy Logical Inferences Per Second (FLIPS), and indicates that the inference engine is suitable for a demanding real-time application. The potential applications include decision-making in the area of command and control for intelligent robot systems, process control, missile and aircraft guidance, and other high performance machines.

In this paper, we describe a scheme for propagating belief functions in certain kinds of trees using only local computations. This scheme generalizes the computational scheme proposed by Shafer and Logan1 for diagnostic trees of the type studied by Gordon and Shortliffe, and the slightly more general scheme given by Shafer for hierarchical evidence. It also generalizes the scheme proposed by Pearl for Bayesian causal trees (see Shenoy and Shafer). Pearl's causal trees and Gordon and Shortliffe's diagnostic trees are both ways of breaking the evidence that bears on a large problem down into smaller items of evidence that bear on smaller parts of the problem so that these smaller problems can be dealt with one at a time. This localization of effort is often essential in order to make the process of probability judgment feasible, both for the person who is making probability judgments and for the machine that is combining them. The basic structure for our scheme is a type of tree that generalizes both Pearl's and Gordon and Shortliffe's trees. Trees of this general type permit localized computation in Pearl's sense. They are based on qualitative judgments of conditional independence. We believe that the scheme we describe here will prove useful in expert systems. It is now clear that the successful propagation of probabilities or certainty factors in expert systems requires much more structure than can be provided in a pure production-system framework. Bayesian schemes, on the other hand, often make unrealistic demands for structure. The propagation of belief functions in trees and more general networks stands on a middle ground where some sensible and useful things can be done. We would like to emphasize that the basic idea of local computation for propagating probabilities is due to Judea Pearl. It is a very innovative idea; we do not believe that it can be found in the Bayesian literature prior to Pearl's work. We see our contribution as extending the usefulness of Pearl's idea by generalizing it from Bayesian probabilities to belief functions. In the next section, we give a brief introduction to belief functions. The notions of qualitative independence for partitions and a qualitative Markov tree are introduced in Section III. Finally, in Section IV, we describe a scheme for propagating belief functions in qualitative Markov trees.

Explanation facilities are a particularly important feature of expert system frameworks. It is an area in which traditional rule-based expert system frameworks have had mixed results. While explanations about control are well handled, facilities are needed for generating better explanations concerning knowledge base content. This paper approaches the explanation problem by examining the effect an event has on a variable of interest within a symmetric Bayesian inferencing system. We argue that any effect measure operating in this context must satisfy certain properties. Such a measure is proposed. It forms the basis for an explanation facility which allows the user of the Generalized Bayesian Inferencing System to question the meaning of the knowledge base. That facility is described in detail.

Current approaches to expert systems' reasoning under uncertainty fail to capture the iterative revision process characteristic of intelligent human reasoning. This paper reports on a system, called the Non-monotonic Probabilist, or NMP (Cohen, et al., 1985). When its inferences result in substantial conflict, NMP examines and revises the assumptions underlying the inferences until conflict is reduced to acceptable levels. NMP has been implemented in a demonstration computer-based system, described below, which supports threat correlation and in-flight route replanning by Air Force pilots.

This paper describes the incorporation of uncertainty in diagnostic reasoning based on the set covering model of Reggia et. al. extended to what in the Artificial Intelligence dichotomy between deep and compiled (shallow, surface) knowledge based diagnosis may be viewed as the generic form at the compiled end of the spectrum. A major undercurrent in this is advocating the need for a strong underlying model and an integrated set of support tools for carrying such a model in order to deal with uncertainty.

There has been a considerable amount of work on uncertainty in knowledge-based systems. This work has generally been concerned with uncertainty arising from the strength of inferences and the weight of evidence. In this paper we discuss another type of uncertainty: that which is due to imprecision in the underlying primitives used to represent the knowledge of the system. In particular, a given word may denote many similar but not identical entities. Such words are said to be lexically imprecise. Lexical imprecision has caused widespread problems in many areas. Unless this phenomenon is recognized and appropriately handled, it can degrade the performance of knowledge-based systems. In particular, it can lead to difficulties with the user interface, and with the inferencing processes of these systems. Some techniques are suggested for coping with this phenomenon.

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.