Marek J. Druzdzel

AIIM Journal 2013 Journal Article

Impact of precision of Bayesian network parameters on accuracy of medical diagnostic systems

• Agnieszka Oniśko
• Marek J. Druzdzel

Objective One of the hardest technical tasks in employing Bayesian network models in practice is obtaining their numerical parameters. In the light of this difficulty, a pressing question, one that has immediate implications on the knowledge engineering effort, is whether precision of these parameters is important. In this paper, we address experimentally the question whether medical diagnostic systems based on Bayesian networks are sensitive to precision of their parameters. Methods and materials The test networks include Hepar II, a sizeable Bayesian network model for diagnosis of liver disorders and six other medical diagnostic networks constructed from medical data sets available through the Irvine Machine Learning Repository. Assuming that the original model parameters are perfectly accurate, we lower systematically their precision by rounding them to progressively courser scales and check the impact of this rounding on the models’ accuracy. Results Our main result, consistent across all tested networks, is that imprecision in numerical parameters has minimal impact on the diagnostic accuracy of models, as long as we avoid zeroes among parameters. Conclusion The experiments’ results provide evidence that as long as we avoid zeroes among model parameters, diagnostic accuracy of Bayesian network models does not suffer from decreased precision of their parameters.

UAI Conference 2010 Conference Paper

Learning Why Things Change: The Difference-Based Causality Learner

• Mark Voortman
• Denver Dash
• Marek J. Druzdzel

In this paper, we present the Difference- Based Causality Learner (DBCL), an algorithm for learning a class of discrete-time dynamic models that represents all causation across time by means of difference equations driving change in a system. We motivate this representation with real-world mechanical systems and prove DBCL’s correctness for learning structure from time series data, an endeavour that is complicated by the existence of latent derivatives that have to be detected. We also prove that, under common assumptions for causal discovery, DBCL will identify the presence or absence of feedback loops, making the model more useful for predicting the effects of manipulating variables when the system is in equilibrium. We argue analytically and show empirically the advantages of DBCL over vector autoregression (VAR) and Granger causality models as well as modified forms of Bayesian and constraintbased structure discovery algorithms. Finally, we show that our algorithm can discover causal directions of alpha rhythms in human brains from EEG data.

ICML Conference 2009 Conference Paper

Workshop summary: Seventh annual workshop on Bayes applications

• John Mark Agosta
• Russell G. Almond
• Dennis M. Buede
• Marek J. Druzdzel
• Judy Goldsmith
• Silja Renooij

AIJ Journal 2008 Journal Article

A note on the correctness of the causal ordering algorithm

• Denver Dash
• Marek J. Druzdzel

In this paper we examine in detail the algorithm of Simon [H. A. Simon, Causal ordering and identifiability, in: W. C. Hood, T. C. Koopmans (Eds.), Studies in Econometric Method. Cowles Commission for Research in Economics, Monograph No. 14, John Wiley & Sons, Inc. , New York, 1953, pp. 49–74, Chapter III], called the causal ordering algorithm (COA), used for constructing the “causal ordering” of a system given a complete specification of the system in terms of a set of “structural” equations that govern the variables in the system. This algorithm constructs a graphical characterization of the model in a form that we call a partial causal graph. Simon argued in [H. A. Simon, Causal ordering and identifiability, in: W. C. Hood, T. C. Koopmans (Eds.), Studies in Econometric Method. Cowles Commission for Research in Economics, Monograph No. 14, John Wiley & Sons, Inc. , New York, 1953, pp. 49–74, Chapter III] and subsequent papers that a graph so generated explicates causal structure among variables in the model. We formalize this claim further by proving that any causal model based on a one-to-one correspondence between equations and variables must be consistent with the COA.

IJCAI Conference 2007 Conference Paper

• Xiaoxun Sun
• Marek J. Druzdzel
• Changhe Yuan

In this paper we propose the Dynamic Weighting A* (DWA*) search algorithm for solving MAP problems in Bayesian networks. By exploiting asymmetries in the distribution of MAP variables, the algorithm is able to greatly reduce the search space and offer excellent performance both in terms of accuracy and efficiency.

ECAI Conference 2006 Conference Paper

Knowledge Engineering for Bayesian Networks: How Common Are Noisy-MAX Distributions in Practice?

• Adam Zagorecki
• Marek J. Druzdzel

One problem faced in knowledge engineering for Bayesian networks is the exponential growth of the number of parameters in their conditional probability tables (CPTs). The most common practical solution is application of the noisy-OR (or their generalization, the noisy-MAX) gates, which take advantage of independence of causal interactions and provide a logarithmic reduction of the number of parameters required to specify a CPT. In this paper, we propose an algorithm that fits a noisy-MAX distribution to an existing CPT and we apply it to search for noisy-MAX gates in three existing practical Bayesian networks. We show that noisy-MAX gate provides a surprisingly good fit for as many as 50% of CPTs in these networks. The importance of this finding is that it provides an empirical justification for the use of the noisy-MAX gate as a powerful knowledge engineering tool.

UAI Conference 2004 Conference Paper

Annealed MAP

• Changhe Yuan
• Tsai-Ching Lu
• Marek J. Druzdzel

Maximum a Posteriori assignment (MAP) is the problem of finding the most probable instantiation of a set of variables given the partial evidence on the other variables in a Bayesian network. MAP has been shown to be a NP-hard problem [22], even for constrained networks, such as polytrees [18]. Hence, previous approaches often fail to yield any results for MAP problems in large complex Bayesian networks. To address this problem, we propose AnnealedMAP algorithm, a simulated annealing-based MAP algorithm. The AnnealedMAP algorithm simulates a non-homogeneous Markov chain whose invariant function is a probability density that concentrates itself on the modes of the target density. We tested this algorithm on several real Bayesian networks. The results show that, while maintaining good quality of the MAP solutions, the AnnealedMAP algorithm is also able to solve many problems that are beyond the reach of previous approaches.

UAI Conference 2003 Conference Paper

An Importance Sampling Algorithm Based on Evidence Pre-propagation

• Changhe Yuan
• Marek J. Druzdzel

Precision achieved by stochastic sampling algorithms for Bayesian networks typically deteriorates in face of extremely unlikely evidence. To address this problem, we propose the Evidence Pre-propagation Importance Sampling algorithm (EPIS-BN), an importance sampling algorithm that computes an approximate importance function by the heuristic methods: loopy belief Propagation and e-cutoff. We tested the performance of e-cutoff on three large real Bayesian networks: ANDES, CPCS, and PATHFINDER. We observed that on each of these networks the EPIS-BN algorithm gives us a considerable improvement over the current state of the art algorithm, the AIS-BN algorithm. In addition, it avoids the costly learning stage of the AIS-BN algorithm.

JMLR Journal 2003 Journal Article

Combining Knowledge from Different Sources in Causal Probabilistic Models

• Marek J. Druzdzel
• Francisco J. Díez

Building probabilistic and decision-theoretic models requires a considerable knowledge engineering effort in which the most daunting task is obtaining the numerical parameters. Authors of Bayesian networks usually combine various sources of information, such as textbooks, statistical reports, databases, and expert judgement. In this paper, we demonstrate the risks of such a combination, even when this knowledge encompasses such seemingly population-independent characteristics as sensitivity and specificity of medical symptoms. We show that the criteria ``do not combine knowledge from different sources'' or ``use only data from the setting in which the model will be used'' are neither necessary nor sufficient to guarantee the correctness of the model. Instead, we offer graphical criteria for determining when knowledge from different sources can be safely combined into the general population model. We also offer a method for building subpopulation models. The analysis performed in this paper and the criteria we propose may be useful in such fields as knowledge engineering, epidemiology, machine learning, and statistical meta-analysis. [abs] [ pdf ][ ps.gz ][ ps ]

UAI Conference 2003 Conference Paper

Robust Independence Testing for Constraint-Based Learning of Causal Structure

• Denver Dash
• Marek J. Druzdzel

Constraint-based (CB) learning is a formalism for learning a causal network with a database D by performing a series of conditional-independence tests to infer structural information. This paper considers a new test of independence that combines ideas from Bayesian learning, Bayesian network inference, and classical hypothesis testing to produce a more reliable and robust test. The new test can be calculated in the same asymptotic time and space required for the standard tests such as the chi-squared test, but it allows the specification of a prior distribution over parameters and can be used when the database is incomplete. We prove that the test is correct, and we demonstrate empirically that, when used with a CB causal discovery algorithm with noninformative priors, it recovers structural features more reliably and it produces networks with smaller KL-Divergence, especially as the number of nodes increases or the number of records decreases. Another benefit is the dramatic reduction in the probability that a CB algorithm will stall during the search, providing a remedy for an annoying problem plaguing CB learning when the database is small.

UAI Conference 2001 Conference Paper

Confidence Inference in Bayesian Networks

• Jian Cheng
• Marek J. Druzdzel

We present two sampling algorithms for probabilistic confidence inference in Bayesian networks. These two algorithms (we call them AIS-BN-mu and AIS-BN-sigma algorithms) guarantee that estimates of posterior probabilities are with a given probability within a desired precision bound. Our algorithms are based on recent advances in sampling algorithms for (1) estimating the mean of bounded random variables and (2) adaptive importance sampling in Bayesian networks. In addition to a simple stopping rule for sampling that they provide, the AIS-BN-mu and AIS-BN-sigma algorithms are capable of guiding the learning process in the AIS-BN algorithm. An empirical evaluation of the proposed algorithms shows excellent performance, even for very unlikely evidence.

UAI Conference 2000 Conference Paper

Causal Mechanism-based Model Constructions

• Tsai-Ching Lu
• Marek J. Druzdzel
• Tze-Yun Leong

UAI Conference 2000 Conference Paper

Computational Investigation of Low-Discrepancy Sequences in Simulation Algorithms for Bayesian Networks

• Jian Cheng
• Marek J. Druzdzel

Monte Carlo sampling has become a major vehicle for approximate inference in Bayesian networks. In this paper, we investigate a family of related simulation approaches, known collectively as quasi-Monte Carlo methods based on deterministic low-discrepancy sequences. We first outline several theoretical aspects of deterministic low-discrepancy sequences, show three examples of such sequences, and then discuss practical issues related to applying them to belief updating in Bayesian networks. We propose an algorithm for selecting direction numbers for Sobol sequence. Our experimental results show that low-discrepancy sequences (especially Sobol sequence) significantly improve the performance of simulation algorithms in Bayesian networks compared to Monte Carlo sampling.

UAI Conference 2000 Conference Paper

User Interface Tools for Navigation in Conditional Probability Tables and Elicitation of Probabilities in Bayesian Networks

• Haiqin Wang
• Marek J. Druzdzel

Elicitation of probabilities is one of the most laborious tasks in building decision-theoretic models, and one that has so far received only moderate attention in decision-theoretic systems. We propose a set of user interface tools for graphical probabilistic models, focusing on two aspects of probability elicitation: (1) navigation through conditional probability tables and (2) interactive graphical assessment of discrete probability distributions. We propose two new graphical views that aid navigation in very large conditional probability tables: the CPTree (Conditional Probability Tree) and the SCPT (shrinkable Conditional Probability Table). Based on what is known about graphical presentation of quantitative data to humans, we offer several useful enhancements to probability wheel and bar graph, including different chart styles and options that can be adapted to user preferences and needs. We present the results of a simple usability study that proves the value of the proposed tools.

UAI Conference 1999 Conference Paper

A Hybrid Anytime Algorithm for the Construction of Causal Models From Sparse Data

• Denver Dash
• Marek J. Druzdzel

We present a hybrid constraint-based/Bayesian algorithm for learning causal networks in the presence of sparse data. The algorithm searches the space of equivalence classes of models (essential graphs) using a heuristic based on conventional constraint-based techniques. Each essential graph is then converted into a directed acyclic graph and scored using a Bayesian scoring metric. Two variants of the algorithm are developed and tested using data from randomly generated networks of sizes from 15 to 45 nodes with data sizes ranging from 250 to 2000 records. Both variations are compared to, and found to consistently outperform two variations of greedy search with restarts.

AAAI Conference 1999 Conference Paper

SMILE: Structural Modeling, Inference, and Learning Engine and GeNIe: A Development Environment for Graphical Decision-Theoretic Models

• Marek J. Druzdzel
• University of Pittsburgh

SMILE (Structural Modeling, Inference, and Learning Engine) is a fully portable library of C++ classes implementing graphical decision-theoretic methods, such as Bayesian networks and influence diagrams, directly amenable to inclusion in intelligent systems. Its Windows user interface, Genie is a versatile and user-friendly development environment for graphical decision-theoretic models. Both modules, developed at the Decision Systems Laboratory, University of Pittsburgh, have been made available to the community in July 1998 at http://www2.sis.pitt.edu/~genie and have over 1,200 users worldwide (as of April 1999). This document summarizes the basic features of Genie and Smile.

UAI Conference 1997 Conference Paper

Computational Advantages of Relevance Reasoning in Bayesian Belief Networks

• Yan Lin
• Marek J. Druzdzel

This paper introduces a computational framework for reasoning in Bayesian belief networks that derives significant advantages from focused inference and relevance reasoning. This framework is based on d -separation and other simple and computationally efficient techniques for pruning irrelevant parts of a network. Our main contribution is a technique that we call relevance-based decomposition. Relevance-based decomposition approaches belief updating in large networks by focusing on their parts and decomposing them into partially overlapping subnetworks. This makes reasoning in some intractable networks possible and, in addition, often results in significant speedup, as the total time taken to update all subnetworks is in practice often considerably less than the time taken to update the network as a whole. We report results of empirical tests that demonstrate practical significance of our approach.

UAI Conference 1995 Conference Paper

Elicitation of Probabilities for Belief Networks: Combining Qualitative and Quantitative Information

• Marek J. Druzdzel
• Linda C. van der Gaag

Although the usefulness of belief networks for reasoning under uncertainty is widely accepted, obtaining numerical probabilities that they require is still perceived a major obstacle. Often not enough statistical data is available to allow for reliable probability estimation. Available information may not be directly amenable for encoding in the network. Finally, domain experts may be reluctant to provide numerical probabilities. In this paper, we propose a method for elicitation of probabilities from a domain expert that is non-invasive and accommodates whatever probabilistic information the expert is willing to state. We express all available information, whether qualitative or quantitative in nature, in a canonical form consisting of (in) equalities expressing constraints on the hyperspace of possible joint probability distributions. We then use this canonical form to derive second-order probability distributions over the desired probabilities.

UAI Conference 1994 Conference Paper

Some Properties of joint Probability Distributions

• Marek J. Druzdzel

Several Artificial Intelligence schemes for reasoning under uncertainty explore either explicitly or implicitly asymmetries among probabilities of various states of their uncertain domain models. Even though the correct working of these schemes is practically contingent upon the existence of a small number of probable states, no formal justification has been proposed of why this should be the case. This paper attempts to fill this apparent gap by studying asymmetries among probabilities of various states of uncertain models. By rewriting the joint probability distribution over a model's variables into a product of individual variables' prior and conditional probability distributions, and applying central limit theorem to this product, we can demonstrate that the probabilities of individual states of the model can be expected to be drawn from highly skewed, log-normal distributions. With sufficient asymmetry in individual prior and conditional probability distributions, a small fraction of states can be expected to cover a large portion of the total probability space with the remaining states having practically negligible probability. Theoretical discussion is supplemented by simulation results and an illustrative real-world example.

UAI Conference 1993 Conference Paper

Causality in Bayesian Belief Networks

• Marek J. Druzdzel
• Herbert A. Simon

We address the problem of causal interpretation of the graphical structure of Bayesian belief networks (BBNs). We review the concept of causality explicated in the domain of structural equations models and show that it is applicable to BBNs. In this view, which we call mechanism-based, causality is defined within models and causal asymmetries arise when mechanisms are placed in the context of a system. We lay the link between structural equations models and BBNs models and formulate the conditions under which the latter can be given causal interpretation.

AAAI Conference 1993 Conference Paper

Efficient Reasoning in Qualitative Probabilistic Networks

• Marek J. Druzdzel

Qualitative Probabilistic Networks (QPNs) are an abstraction of Bayesian belief networks replacing numerical relations by qualitative influences and synergies [Wellman, 1990b]. To reason in a QPN is to find the effect of new evidence on each node in terms of the sign of the change in belief (increase or decrease). We introduce a polynomial time algorithm for reasoning in QPNs, based on local sign propagation. It extends our previous scheme from singly connected to general multiply connected networks. Unlike existing graph-reduction algorithms, it preserves the network structure and determines the effect of evidence on all nodes in the network. This aids meta-level reasoning about the model and automatic generation of intuitive explanations of probabilistic reasoning.

UAI Conference 1993 Conference Paper

Intercausal Reasoning with Uninstantiated Ancestor Nodes

• Marek J. Druzdzel
• Max Henrion

Intercausal reasoning is a common inference pattern involving probabilistic dependence of causes of an observed common effect. The sign of this dependence is captured by a qualitative property called product synergy. The current definition of product synergy is insufficient for intercausal reasoning where there are additional uninstantiated causes of the common effect. We propose a new definition of product synergy and prove its adequacy for intercausal reasoning with direct and indirect evidence for the common effect. The new definition is based on a new property matrix half positive semi-definiteness, a weakened form of matrix positive semi-definiteness.

UAI Conference 1990 Conference Paper

Qualtitative propagation and scenario-based scheme for exploiting probabilistic reasoning

• Max Henrion
• Marek J. Druzdzel