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.

Influence diagrams are a directed graph representation for uncertainties as probabilities. Influence diagrams have been used for the last ten years as a model structuring and elicitation device in the practical field of decision analysis. They have been a powerful communication tool during the initial discussion about a problem, as well as when explaining results after analysis. Because the diagrams are heirarchical, with the numbers "hidden" within the nodes Within the last few years, a number of theoretical results allow for the analysis to be performed directly on the influence diagram-- as assessed. In general, these techniques apply a sequence of transformations to different influence diagrams, to solve either probabilistic inference or decision analysis problems.

Much artificial intelligence research focuses on the problem of deducing the validity of unobservable propositions or hypotheses from observable evidence.! Many of the knowledge representation techniques designed for this problem encode the relationship between evidence and hypothesis in a directed manner. Moreover, the direction in which evidence is stored is typically from evidence to hypothesis.

The causal Bayesian approach is based on the assumption that effects (e.g., symptoms) that are not conditionally independent with respect to some causal agent (e.g., a disease) are conditionally independent with respect to some intermediate state caused by the agent, (e.g., a pathological condition). This paper describes the development of a causal Bayesian model for the diagnosis of appendicitis. The paper begins with a description of the standard Bayesian approach to reasoning about uncertainty and the major critiques it faces. The paper then lays the theoretical groundwork for the causal extension of the Bayesian approach, and details specific improvements we have developed. The paper then goes on to describe our knowledge engineering and implementation and the results of a test of the system. The paper concludes with a discussion of how the causal Bayesian approach deals with the criticisms of the standard Bayesian model and why it is superior to alternative approaches to reasoning about uncertainty popular in the Al community.

This paper studies the underlying rationality of those languages on the syntax and calculus grounds. Some implications of the theorem to the relationship between the CF and the Bayesian languages and the Dempster-Shafer Theory of Evidence are presented. In order for a computer program to be a plausible --odel of a (mora or less) rational process of human expertise, the program should be capable of representing beliefs in a language that is (more or less) calibrated with a well-specified normative criterion, e.g. the axioms of Subjective Probability [15], the Theory of Confir.nation Tversky, the building blocks· of a probabilistic language are syntax, calculus, and semantics [18]. The-- is a set of numbers, co--only referred to as Degrees of Belief (e.g. standard probabilities or Certainty Factors), which are used to parameterize uncertain facts, inexact rules, and competing hypotheses.

Results on approximate deduction in the context of the calculus of evidence of Dempster-Shafer and the theory of interval probabilities are reported. Approximate conditional knowledge about the truth of conditional propositions was assumed available and expressed as sets of possible values (actually numeric intervals) of conditional probabilities. Under different interpretations of this conditional knowledge, several formulas were produced to integrate unconditioned estimates (assumed given as sets of possible values of unconditioned probabilities) with conditional estimates. These formulas are discussed together with the computational characteristics of the methods derived from them. Of particular importance is one such evidence integration formulation, produced under a belief oriented interpretation, which incorporates both modus ponens and modus tollens inferential mechanisms, allows integration of conditioned and unconditioned knowledge without resorting to iterative or sequential approximations, and produces elementary mass distributions as outputs using similar distributions as inputs.

A learning algorithm is presented which given the structure of a causal tree, will estimate its link probabilities by sequential measurements on the leaves only. Internal nodes of the tree represent conceptual (hidden) variables inaccessible to observation. The method described is incremental, local, efficient, and remains robust to measurement imprecisions.

This paper presents an efficient adaptation and application of the Dempster-Shafer theory of evidence, one that can be used effectively in a massively parallel hierarchical system for visual pattern perception. It describes the techniques used, and shows in an extended example how they serve to improve the system's performance as it applies a multiple-level set of processes.