Decision tree induction systems are being used for knowledge acquisition in noisy domains. This paper develops a subjective Bayesian interpretation of the task tackled by these systems and the heuristic methods they use. It is argued that decision tree systems implicitly incorporate a prior belief that the simpler (in terms of decision tree complexity) of two hypotheses be preferred, all else being equal, and that they perform a greedy search of the space of decision rules to find one in which there is strong posterior belief. A number of improvements to these systems are then suggested.

This paper demonstrates a methodology for examining the accuracy of uncertain inference systems (UIS), after their parameters have been optimized, and does so for several common UIS's. This methodology may be used to test the accuracy when either the prior assumptions or updating formulae are not exactly satisfied. Surprisingly, these UIS's were revealed to be no more accurate on the average than a simple linear regression. Moreover, even on prior distributions which were deliberately biased so as give very good accuracy, they were less accurate than the simple probabilistic model which assumes marginal independence between inputs. This demonstrates that the importance of updating formulae can outweigh that of prior assumptions. Thus, when UIS's are judged by their final accuracy after optimization, we get completely different results than when they are judged by whether or not their prior assumptions are perfectly satisfied.

Bayes belief networks and influence diagrams are tools for constructing coherent probabilistic representations of uncertain knowledge. The process of constructing such a network to represent an expert's knowledge is used to illustrate a variety of techniques which can facilitate the process of structuring and quantifying uncertain relationships. These include some generalizations of the "noisy OR gate" concept. Sensitivity analysis of generic elements of Bayes' networks provides insight into when rough probability assessments are sufficient and when greater precision may be important.

David Beckerman and Holly Jimison Medical Computer Science Group Knowledge Systems Laboratory Stanford University Medical School Office Building, Room 215 Stanford, California 94305 We examine a Bayesian approach for accommodating beliefs and preferences that are held with partial confidence. An important notion highlighted by the method is that additional modeling can be valuable when complete confidence is lacking. We develop a meta-decision-analytic approach to balance the benefits of additional modeling with associated costs. We show how the approach can be used during knowledge acquisition to focus the attention of a knowledge engineer or expert on parts of a decision model that deserve additional refinement.

This paper examines Bayesian belief network inference using simulation as a method for computing the posterior probabilities of network variables. Specifically, it examines the use of a method described by Henrion, called logic sampling, and a method described by Pearl, called stochastic simulation. We first review the conditions under which logic sampling is computationally infeasible. Such cases motivated the development of the Pearl's stochastic simulation algorithm. We have found that this stochastic simulation algorithm, when applied to certain networks, leads to much slower than expected convergence to the true posterior probabilities. This behavior is a result of the tendency for local areas in the network to become fixed through many simulation cycles. The time required to obtain significant convergence can be made arbitrarily long by strengthening the probabilistic dependency between nodes. We propose the use of several forms of graph modification, such as graph pruning, arc reversal, and node reduction, in order to convert some networks into formats that are computationally more efficient for simulation.

Advanced Decision Systems Abstract We present a thorough integration of hierarchical Bayesian inference with comprehensive physical representation of objects and their relations in a system for reasoning with geometry in machine vision. Bayesian inference provides a framework (or accruing probabilities to rank order hypotheses. This is a preliminary version of visual interpretation in SUCCESSOR, an intelligent, model-based vision system integrating multiple sensors. Introduction Our design for machine vision uses an evidential accrual process, a. beginning from representation and database of a priori models o(physical objects and their photometric, geometric, and functional properties, together with their relationships and environment, b. predicting observables using models of sensors and perceptual measurement processes; c. making measurements of corresponding observables, measuring image evidence for features of objects and structures of features such as edges, vertices and regions; d. generating hypotheses of instances o(objects from those measurements and predictions; and In range imagery, measurements are 3d. There is still a difficult stage of segmenting and estimating 3d relations that disclose object structure. In 2d images, there is an additional inference from 2d projected image evidence to 3d interpretation of surfaces. System structure tends to break up into a natural hierarchy of representation and processing [Binford 80).

This paper shows that the common method used for making predictions under uncertainty in A1 and science is in error. This method is to use currently available data to select the best model from a given class of models-this process is called abduction-and then to use this model to make predictions about future data. The correct method requires averaging over all the models to make a prediction-we call this method transduction. Using transduction, an AI system will not give misleading results when basing predictions on small amounts of data, when no model is clearly best. For common classes of models we show that the optimal solution can be given in closed form.

EXAMINATION OF SHAFER'S CANONICAL EXAMPLES Kathryn Blackmond Laskey Decision Science Consortium, Inc. 7700 Leesburg Pike, Suite 421 Falls Church, VA 22043 1 Abstract In the canonical examples underlying Shafer-Dempster theory, beliefs over the hypotheses of interest are derived from a probability model for a set of auxiliary hypotheses. Beliefs are derived via a compatibility relation connecting the auxiliary hypotheses to subsets of the primary hypotheses. A belief function differs from a Bayesian probability model in that one does not condition on those parts of the evidence for which no probabilities are specified. The significance of this difference in conditioning assumptions is illustrated with two examples giving rise to identical belief functions but different Bayesian probability distributions. Introduction The artificial intelligence community is in the midst of a lively debate over the representation and manipulation of uncertainty.

This paper examines the relationship between Shafer's belief functions and convex sets of probability distributions. Kyburg's (1986) result showed that belief function models form a subset of the class of closed convex probability distributions. This paper emphasizes the importance of Kyburg's result by looking at simple examples involving Bernoulli trials. Furthermore, it is shown that many convex sets of probability distributions generate the same belief function in the sense that they support the same lower and upper values. This has implications for a decision theoretic extension. Dempster's rule of combination is also compared with Bayes' rule of conditioning.

Network detection is an important capability in many areas of applied research in which data can be represented as a graph of entities and relationships. Oftentimes the object of interest is a relatively small subgraph in an enormous, potentially uninteresting background. This aspect characterizes network detection as a "big data" problem. Graph partitioning and network discovery have been major research areas over the last ten years, driven by interest in internet search, cyber security, social networks, and criminal or terrorist activities. The specific problem of network discovery is addressed as a special case of graph partitioning in which membership in a small subgraph of interest must be determined. Algebraic graph theory is used as the basis to analyze and compare different network detection methods. A new Bayesian network detection framework is introduced that partitions the graph based on prior information and direct observations. The new approach, called space-time threat propagation, is proved to maximize the probability of detection and is therefore optimum in the Neyman-Pearson sense. This optimality criterion is compared to spectral community detection approaches which divide the global graph into subsets or communities with optimal connectivity properties. We also explore a new generative stochastic model for covert networks and analyze using receiver operating characteristics the detection performance of both classes of optimal detection techniques.