Publications

This paper proposes and investigates an approach to deduction in probabilistic logic, using as its medium a language that generalizes the propositional version of Nilsson's probabilistic logic by incorporating conditional probabilities. Unlike many other approaches to deduction in probabilistic logic, this approach is based on inference rules and therefore can produce proofs to explain how conclusions are drawn. We show how these rules can be incorporated into an anytime deduction procedure that proceeds by computing increasingly narrow probability intervals that contain the tightest entailed probability interval. Since the procedure can be stopped at any time to yield partial information concerning the probability range of any entailed sentence, one can make a tradeoff between precision and computation time. The deduction method presented here contrasts with other methods whose ability to perform logical reasoning is either limited or requires finding all truth assignments consistent with the given sentences.

This paper discusses the problem of abstract­ ing conditional probabilistic actions. We identify two distinct types of abstraction: intra­action abstraction and inter­action ab­ straction. We define what it means for the abstraction of an action to be correct and then derive two methods of intra­action ab­ straction and two methods of inter­action ab­ straction which are correct according to this criterion. We illustrate the developed tech­ niques by applying them to actions described with the temporal action representation used in the drips decision­theoretic planner and we describe how the planner uses abstraction to reduce the complexity of planning.

Decision­theoretic refinement planning is a new technique for finding optimal courses of ac­ tion. The authors sought to determine whether this technique could identify optimal strate­ gies for medical diagnosis and therapy. An existing model of acute deep venous thrombosis (DVT) of the lower extremities was encoded for analysis by the drips decision­theoretic refinement planning system. The encoding represented 6,206 possible plans. The drips planner used abstraction techniques to eliminate 5,551 plans (89%) from consideration with­ out examining them explicitly. It determined that, given the parameters specified, the most cost­effective management strategy was ``no tests, no treatment.'' This result differed from the published result of ``perform ultrasonography, treat if positive''; drips had revealed an error in the reference article's manually constructed decision trees. We conclude that decision­theoretic planning is useful for examining large medical decision problems, and that it can help reduce errors introduced by manual construction of decision trees.

We present an educational tool for bringing the in­ formation contained in a Bayesian network to the end user in an easily intelligible form. The banter shell is designed to tutor users in evaluation of hypotheses and selection of optimal diagnostic procedures. ban­ ter can be used with any Bayesian network contain­ ing nodes that can be classified into hypotheses, obser­ vations, and diagnostic procedures. We present algo­ rithms for determining optimal diagnostic procedures and for explanation generation.

We describe the early stages of the development and validation of a Bayesian network to assist in the detection of breast cancer. MammoNet integrates mammo­ graphic findings, demographic factors, and physical examination to determine the probability of malignancy. Conditional probabilities were obtained from the medical literature and from expert opinion. Problems (and solutions) encountered while developing the model are discussed. MammoNet is imple­ mented as a knowledge base of rules; problem­specific networks are constructed using a Bayesian network construction algorithm. The model's performance was evaluated with 77 cases drawn from a textbook and a clinical teaching file; MammoNet performed well, and achieved an area under the receiver operating curve of 0.881 (± 0.045).

Any anytime algorithm used for decision­making should have the property that it considers the most important aspects of the decision problem first. In this way, the algorithm can first eliminate disastrous decisions and recognize particularly ad­ vantageous decisions, considering finer details if time permits. We view planning as a decision­making process and discuss the design of anytime algorithms for decision­ theoretic planning. In particular, we present an anytime decision­theoretic planning algorithm that uses abstraction to focus attention first on those aspects of a planning problem that have the highest impact on expected utility. We discuss control schemes for refining this behavior and methods for automatically creating good abstractions.

We present a general theory of action abstraction for reducing the complexity of decision­theoretic planning. We develop projection rules for abstract actions and prove our abstraction techniques to be correct. We present a planning algorithm that uses the abstraction theory to efficiently explore the space of possible plans by eliminating suboptimal classes of plans without explicitly examining all plans in those classes. An instance of the algorithm has been implemented as the drips decision­theoretic refinement planning system. We apply the planner to the problem of selecting the optimal test/treat strategy for managing patients suspected of having deep­vein thrombosis of the lower extremities. We show that drips significantly outperforms a standard branch­and­bound decision tree evaluation algorithm on this domain. We would like to thank Charles Kahn for pointing us to the DVT application.

This paper discusses techniques for perform­ ing efficient decision­theoretic planning. We give an overview of the drips decision­ theoretic refinement planning system, which uses abstraction to efficiently identify opti­ mal plans. We present techniques for au­ tomatically generating search control infor­ mation, which can significantly improve the planner's performance. We evaluate the effi­ ciency of drips both with and without the search control rules on a complex medical planning problem and compare its perfor­ mance to that of a branch­and­bound deci­ sion tree algorithm.

We define a context­sensitive temporal prob­ ability logic for representing classes of discrete­time temporal Bayesian networks. Context constraints allow inference to be focused on only the relevant portions of the probabilistic knowledge. We provide a declarative semantics for our language. We present a Bayesian network construction algorithm whose generated networks give sound and complete answers to queries. We use related concepts in logic programming to justify our approach. We have implemented a Bayesian network construction algorithm for a subset of the theory and demonstrate it's application to the problem of evaluating the effectiveness of treatments for acute cardiac conditions.

We present a language for representing context­ sensitive temporal probabilistic knowledge. Con­ text constraints allow inference to be focused on only the relevant portions of the probabilistic knowledge. We provide a declarative semantics for our language and an implemented algorithm (BNG) that generates Bayesian networks to com­ pute the posterior probabilities of queries. We il­ lustrate the use of the BNG system by applying it to the problem of modeling the effects of medica­ tions and other interventions on the condition of a patient in cardiac arrest.

Clinical decision analysis seeks to identify the optimal management strategy by modelling the un­ certainty and risks entailed in the diagnosis, natu­ ral history, and treatment of a particular problem or disorder. Decision trees are the most frequently used model in clinical decision analysis, but can be tedious to construct, cumbersome to use, and computationally prohibitive, especially with large, complex decision problems. We present a new method for clinical decision analysis that combines the techniques of decision theory and artificial in­ telligence. Our model uses a modular represen­ tation of knowledge that simplifies model building and enables more fully automated decision mak­ ing. Moreover, the model exploits problem struc­ tures to yield better computational efficiency. As an example we apply our techniques to the problem of management of acute deep venous thrombosis.

Bayesian networks use the techniques of probability theory to reason under conditions of uncertainty. We investigated the use of Bayesian networks for radiological decision support. A Bayesian network for the interpretation of mammograms (MammoNet) was developed based on five patient­history features, two physical findings, and 15 mammographic features extracted by experienced radiologists. Conditional­probability data, such as sensitivity and specificity, were derived from peer­reviewed journal articles and from expert opinion. In testing with a set of 77 cases from a mammography atlas and a clinical teaching file, MammoNet performed well in distinguishing between benign and malignant lesions, and yielded a value of 0.881 (± 0.045) for the area under the receiver operating characteristic curve. We conclude that Bayesian networks provide a potentially useful tool for mammographic decision support.

An intelligent reactive planning agent for partially ob­ servable stochastic domains requires a number of di­ verse capabilities. First, the agent must be able to intelligently allocate its resources. This means that it must be able to decide how much time to allocate to deliberation in a way that is responsive to the environ­ ment in which the agent finds itself. It must also be able to decide when to sense and how much time and effort to spend sensing.

We present a first­order logic of time, chance, and probability that is capable of expressing the four types of higher­order probability sentences relating subjective probability and objective chance at different times. We define a causal notion of objective chance and show how it can be used in conjunction with subjective probability to distinguish between causal and evidential correlation by distinguishing between conditions, events, and actions that 1) influence the agent's belief in chance and 2) the agent believes to influence chance. Furthermore, the semantics of the logic captures some commonsense inferences concerning objective chance and causality. We show that an agent's subjective probability is the expected value of its beliefs concerning objective chance. We also prove that an agent using this representation believes with certainty that the past cannot be causally influenced. To appear in IEEE SMC special issue on Higher­Order Probability.