We present a new, deterministic, distributed MAP estimation algorithm for Markov Random Fields called Local Highest Confidence First (Local HCF). The algorithm has been applied to segmentation problems in computer vision and its performance compared with stochastic algorithms. The experiments show that Local HCF finds better estimates than stochastic algorithms with much less computation.

An algorithm for automated construction of a sparse Bayesian network given an unstructured probabilistic model and causal domain information from an expert has been developed and implemented. The goal is to obtain a network that explicitly reveals as much information regarding conditional independence as possible. The network is built incrementally adding one node at a time. The expert's information and a greedy heuristic that tries to keep the number of arcs added at each step to a minimum are used to guide the search for the next node to add. The probabilistic model is a predicate that can answer queries about independencies in the domain. In practice the model can be implemented in various ways. For example, the model could be a statistical independence test operating on empirical data or a deductive prover operating on a set of independence statements about the domain.

Three paediatric cardiologists assessed nearly 1000 imprecise subjective conditional probabilities for a simple belief network representing congenital heart disease, and the quality of the assessments has been measured using prospective data on 200 babies. Quality has been assessed by a Brier scoring rule, which decomposes into terms measuring lack of discrimination and reliability. The results are displayed for each of 27 diseases and 24 questions, and generally the assessments are reliable although there was a tendency for the probabilities to be too extreme. The imprecision allows the judgements to be converted to implicit samples, and by combining with the observed data the probabilities naturally adapt with experience. This appears to be a practical procedure even for reasonably large expert systems.

A number of algorithms have been developed to solve probabilistic inference problems on belief networks. These algorithms can be divided into two main groups: exact techniques which exploit the conditional independence revealed when the graph structure is relatively sparse, and probabilistic sampling techniques which exploit the "conductance" of an embedded Markov chain when the conditional probabilities have non-extreme values. In this paper, we investigate a family of "forward" Monte Carlo sampling techniques similar to Logic Sampling [Henrion, 1988] which appear to perform well even in some multiply connected networks with extreme conditional probabilities, and thus would be generally applicable. We consider several enhancements which reduce the posterior variance using this approach and propose a framework and criteria for choosing when to use those enhancements.

The arc reversal/node reduction approach to probabilistic inference is extended to include the case of instantiated evidence by an operation called "evidence reversal." This not only provides a technique for computing posterior joint distributions on general belief networks, but also provides insight into the methods of Pearl [1986b] and Lauritzen and Spiegelhalter [1988]. Although it is well understood that the latter two algorithms are closely related, in fact all three algorithms are identical whenever the belief network is a forest.

Bayesian Belief Networks have been largely overlooked by Expert Systems practitioners on the grounds that they do not correspond to the human inference mechanism. In this paper, we introduce an explanation mechanism designed to generate intuitive yet probabilistically sound explanations of inferences drawn by a Bayesian Belief Network. In particular, our mechanism accounts for the results obtained due to changes in the causal and the evidential support of a node.

We show an approach to automated control of machine vision systems based on incremental creation and evaluation of a particular family of influence diagrams that represent hypotheses of imagery interpretation and possible subsequent processing decisions. In our approach, model-based machine vision techniques are integrated with hierarchical Bayesian inference to provide a framework for representing and matching instances of objects and relationships in imagery and for accruing probabilities to rank order conflicting scene interpretations. We extend a result of Tatman and Shachter to show that the sequence of processing decisions derived from evaluating the diagrams at each stage is the same as the sequence that would have been derived by evaluating the final influence diagram that contains all random variables created during the run of the vision system.

Many Artificial Intelligence systems depend on the agent's updating its beliefs about the world on the basis of experience. Experiments constitute one type of experience, so scientific methodology offers a natural environment for examining the issues attendant to using this class of evidence. This paper presents a framework which structures the process of using scientific data from research reports for the purpose of making decisions, using decision analysis as the basis for the structure and using medical research as the general scientific domain. The structure extends the basic influence diagram for updating belief in an object domain parameter of interest by expanding the parameter into four parts: those of the patient, the population, the study sample, and the effective study sample. The structure uses biases to perform the transformation of one parameter into another, so that, for instance, selection biases, in concert with the population parameter, yield the study sample parameter. The influence diagram structure provides decision theoretic justification for practices of good clinical research such as randomized assignment and blindfolding of care providers. The model covers most research designs used in medicine: case-control studies, cohort studies, and controlled clinical trials, and provides an architecture to separate clearly between statistical knowledge and domain knowledge. The proposed general model can be the basis for clinical epidemiological advisory systems, when coupled with heuristic pruning of irrelevant biases; of statistical workstations, when the computational machinery for calculation of posterior distributions is added; and of meta-analytic reviews, when multiple studies may impact on a single population parameter.

BPS, the Bayesian Problem Solver, applies probabilistic inference and decision-theoretic control to flexible, resource-constrained problem-solving. This paper focuses on the Bayesian inference mechanism in BPS, and contrasts it with those of traditional heuristic search techniques. By performing sound inference, BPS can outperform traditional techniques with significantly less computational effort. Empirical tests on the Eight Puzzle show that after only a few hundred node expansions, BPS makes better decisions than does the best existing algorithm after several million node expansions

An efficient algorithm is developed that identifies all independencies implied by the topology of a Bayesian network. Its correctness and maximality stems from the soundness and completeness of d-separation with respect to probability theory. The algorithm runs in time O (l E l) where E is the number of edges in the network.