We discuss the Dempster-Shafer theory of evidence. We introduce a concept of monotonicity which is related to the diminution of the range between belief and plausibility. We show that the accumulation of knowledge in this framework exhibits a nonmonotonic property. We show how the belief structure can be used to represent typical or commonsense knowledge.

Cutset conditioning and clique-tree propagation are two popular methods for performing exact probabilistic inference in Bayesian belief networks. Cutset conditioning is based on decomposition of a subset of network nodes, whereas clique-tree propagation depends on aggregation of nodes. We describe a means to combine cutset conditioning and clique- tree propagation in an approach called aggregation after decomposition (AD). We discuss the application of the AD method in the Pathfinder system, a medical expert system that offers assistance with diagnosis in hematopathology.

In this paper, the feasibility of using finite totally ordered probability models under Alelinnas's Theory of Probabilistic Logic [Aleliunas, 1988] is investigated. The general form of the probability algebra of these models is derived and the number of possible algebras with given size is deduced. Based on this analysis, we discuss problems of denominator-indifference and ambiguity-generation that arise in reasoning by cases and abductive reasoning. An example is given that illustrates how these problems arise. The investigation shows that a finite probability model may be of very limited usage.

The domain of spare parts forecasting is examined, and is found to present unique uncertainty based problems in the architectural design of a knowledge-based system. A mixture of different uncertainty paradigms is required for the solution, with an intriguing combinatoric problem arising from an uncertain choice of inference engines. Thus, uncertainty in the system is manifested in two different meta-levels. The different uncertainty paradigms and meta-levels must be integrated into a functioning whole. FRED is an example of a difficult real-world domain to which no existing uncertainty approach is completely appropriate. This paper discusses the architecture of FRED, highlighting: the points of uncertainty and other interesting features of the domain, the specific implications of those features on the system design (including the combinatoric explosions), their current implementation & future plans,and other problems and issues with the architecture.

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.

To develop an approach to utilizing continuous statistical information within the Dempster- Shafer framework, we combine methods proposed by Strat and by Shafero We first derive continuous possibility and mass functions from probability-density functions. Then we propose a rule for combining such evidence that is simpler and more efficiently computed than Dempster's rule. We discuss the relationship between Dempster's rule and our proposed rule for combining evidence over continuous frames.

An inductive logic can be formulated in which the elements are not propositions or probability distributions, but information systems. The logic is complete for information systems with binary hypotheses, i.e., it applies to all such systems. It is not complete for information systems with more than two hypotheses, but applies to a subset of such systems. The logic is inductive in that conclusions are more informative than premises. Inferences using the formalism have a strong justification in terms of the expected value of the derived information system.

This paper describes valuation-based systems for representing and solving discrete optimization problems. In valuation-based systems, we represent information in an optimization problem using variables, sample spaces of variables, a set of values, and functions that map sample spaces of sets of variables to the set of values. The functions, called valuations, represent the factors of an objective function. Solving the optimization problem involves using two operations called combination and marginalization. Combination tells us how to combine the factors of the joint objective function. Marginalization is either maximization or minimization. Solving an optimization problem can be simply described as finding the marginal of the joint objective function for the empty set. We state some simple axioms that combination and marginalization need to satisfy to enable us to solve an optimization problem using local computation. For optimization problems, the solution method of valuation-based systems reduces to non-serial dynamic programming. Thus our solution method for VBS can be regarded as an abstract description of dynamic programming. And our axioms can be viewed as conditions that permit the use of dynamic programming.

We point out the need to use probability amplitudes rather than probabilities to model evidence accumulation in decision processes involving real physical sensors. Optical information processing systems are given as typical examples of systems that naturally gather evidence in this manner. We derive a new, amplitude-based generalization of the Hough transform technique used for object recognition in machine vision. We argue that one should use complex Hough accumulators and square their magnitudes to get a proper probabilistic interpretation of the likelihood that an object is present. Finally, we suggest that probability amplitudes may have natural applications in connectionist models, as well as in formulating knowledge-based reasoning problems.

This paper derives a formula for computing the conditional probability of a set of candidates, where a candidate is a set of disorders that explain a given set of positive findings. Such candidate sets are produced by a recent method for multidisorder diagnosis called symptom clustering. A symptom clustering represents a set of candidates compactly as a cartesian product of differential diagnoses. By evaluating the probability of a candidate set, then, a large set of candidates can be validated or pruned simultaneously. The probability of a candidate set is then specialized to obtain the probability of a single candidate. Unlike earlier results, the equation derived here allows the specification of positive, negative, and unknown symptoms and does not make assumptions about disorders not in the candidate.