Definitions and notations with historical references are given for some numerical coefficients commonly used to quantify relations among collections of objects for the purpose of expressing approximate knowledge and probabilistic reasoning.

In previous work (Fertig and Breese, 1989; Fertig and Breese, 1990) we defined a mechanism for performing probabilistic reasoning in influence diagrams using interval rather than point-valued probabilities. In this paper we extend these procedures to incorporate decision nodes and interval-valued value functions in the diagram. We derive the procedures for chance node removal (calculating expected value) and decision node removal (optimization) in influence diagrams where lower bounds on probabilities are stored at each chance node and interval bounds are stored on the value function associated with the diagram's value node. The output of the algorithm are a set of admissible alternatives for each decision variable and a set of bounds on expected value based on the imprecision in the input. The procedure can be viewed as an approximation to a full e-dimensional sensitivity analysis where n are the number of imprecise probability distributions in the input. We show the transformations are optimal and sound. The performance of the algorithm on an influence diagrams is investigated and compared to an exact algorithm.

The most difficult task in probabilistic reasoning may be handling directed cycles in belief networks. To the best knowledge of this author, there is no serious discussion of this problem at all in the literature of probabilistic reasoning so far.

Attempts to replicate probabilistic reasoning in expert systems have typically overlooked a critical ingredient of that process. Probabilistic analysis typically requires extensive judgments regarding interdependencies among hypotheses and data, and regarding the appropriateness of various alternative models. 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.

We introduce a new heuristic algorithm for the problem of finding minimum size loop cutsets in multiply connected belief networks. We compare this algorithm to that proposed in [Suemmondt and Cooper, 1988]. We provide lower bounds on the performance of these algorithms with respect to one another and with respect to optimal. We demonstrate that no heuristic algorithm for this problem cam be guaranteed to produce loop cutsets within a constant difference from optimal. We discuss experimental results based on randomly generated networks, and discuss future work and open questions.

There currently exists a gap between the theories proposed by the probability and uncertainty and the needs of Artificial Intelligence research. These theories primarily address the needs of expert systems, using knowledge structures which must be pre-compiled and remain static in structure during runtime. Many Al systems require the ability to dynamically add and remove parts of the current knowledge structure (e.g., in order to examine what the world would be like for different causal theories). This requires more flexibility than existing uncertainty systems display. In addition, many Al researchers are only interested in using "probabilities" as a means of obtaining an ordering, rather than attempting to derive an accurate probabilistic account of a situation. This indicates the need for systems which stress ease of use and don't require extensive probability information when one cannot (or doesn't wish to) provide such information. This paper attempts to help reconcile the gap between approaches to uncertainty and the needs of many AI systems by examining the control issues which arise, independent of a particular uncertainty calculus. when one tries to satisfy these needs. Truth Maintenance Systems have been used extensively in problem solving tasks to help organize a set of facts and detect inconsistencies in the believed state of the world. These systems maintain a set of true/false propositions and their associated dependencies. However, situations often arise in which we are unsure of certain facts or in which the conclusions we can draw from available information are somewhat uncertain. The non-monotonic TMS 12] was an attempt at reasoning when all the facts are not known, but it fails to take into account degrees of belief and how available evidence can combine to strengthen a particular belief. This paper addresses the problem of probabilistic reasoning as it applies to Truth Maintenance Systems. It describes a belief Maintenance System that manages a current set of beliefs in much the same way that a TMS manages a set of true/false propositions. If the system knows that belief in fact is dependent in some way upon belief in fact2, then it automatically modifies its belief in facts when new information causes a change in belief of fact2. It models the behavior of a TMS, replacing its 3-valued logic (true, false, unknown) with an infinite valued logic, in such a way as to reduce to a standard TMS if all statements are given in absolute true/false terms. Belief Maintenance Systems can, therefore, be thought of as a generalization of Truth Maintenance Systems, whose possible reasoning tasks are a superset of those for a TMS.

In this paper a new mathematical procedure is presented for combining different pieces of evidence which are represented in the interval form to reflect our knowledge about the truth of a hypothesis. Evidences may be correlated to each other (dependent evidences) or conflicting in supports (conflicting evidences). First, assuming independent evidences, we propose a methodology to construct combination rules which obey a set of essential properties. The method is based on a geometric model. We compare results obtained from Dempster-Shafer's rule and the proposed combination rules with both conflicting and non-conflicting data and show that the values generated by proposed combining rules are in tune with our intuition in both cases. Secondly, in the case that evidences are known to be dependent, we consider extensions of the rules derived for handling conflicting evidence. The performance of proposed rules are shown by different examples. The results show that the proposed rules reasonably make decision under dependent evidences

Rather than discussing the isolated merits of a nominative theory of uncertainty, this paper focuses on a class of problems, referred to as Dynamic Classification Problem (DCP), which requires the integration of many theories, including a prescriptive theory of uncertainty. We start by analyzing the Dynamic Classification Problem and by defining its induced requirements on a supporting (plausible) reasoning system. We provide a summary of the underlying theory (based on the semantics of many-valed logics) and illustrate the constraints imposed upon it to ensure the modularity and computational performance required by the applications. We describe the technologies used for knowledge engineering (such as object-based simulator to exercise requirements, and development tools to build the Knowledge Base and functionally validate it). We emphasize the difference between development environment and run-time system, describe the rule cross-compiler, and the real-time inference engine with meta-reasoning capabilities. Finally, we illustrate how our proposed technology satisfies the pop's requirements and analyze some of the lessons reamed from its applications to situation assessment problems for Pilot's Associate and Submarine Commander Associate.

In this paper, optimum decomposition of belief networks is discussed. Some methods of decomposition are examined and a new method - the method of Minimum Total Number of States (MTNS) - is proposed. The problem of optimum belief network decomposition under our framework, as under all the other frameworks, is shown to be NP-hard. According to the computational complexity analysis, an algorithm of belief network decomposition is proposed in (Wee, 1990a) based on simulated annealing.

Within diagnostic reasoning there have been a number of proposed definitions of a diagnosis, and thus of the most likely diagnosis, including most probable posterior hypothesis, most probable interpretation, most probable covering hypothesis, etc. Most of these approaches assume that the most likely diagnosis must be computed, and that a definition of what should be computed can be made a priori, independent of what the diagnosis is used for. We argue that the diagnostic problem, as currently posed, is incomplete: it does not consider how the diagnosis is to be used, or the utility associated with the treatment of the abnormalities. In this paper we analyze several well-known definitions of diagnosis, showing that the different definitions of the most likely diagnosis have different qualitative meanings, even given the same input data. We argue that the most appropriate definition of (optimal) diagnosis needs to take into account the utility of outcomes and what the diagnosis is used for.