Probabilistic Reasoning Group

The Probabilistic Reasoning Group is a research subgroup of KDD Lab  in the Computing and Information Sciences (CIS) Department at Kansas State University. Its research emphasis is in the areas of expert systems and uncertainty in artificial intelligence.

Expert systems and uncertainty in artificial intelligence have seen a great surge of research activity during the last decade. Bayesian networks are powerful tools both for graphically representing the relationships among a set of random variables and for dealing with uncertainties in expert systems (Pearl 1988).  A Bayesian Network, or Bayesian Belief Network (BBN), is a concise representation of a joint probability distribution defined on a finite set of random variables. It is a directed acyclic graph (DAG) in which nodes represent random variables and arcs represent probabilistic dependencies among the variables. A conditional probability distribution is associated with each node and describes the dependency between the node and its parents. The networks are most often used in expert systems that reason under uncertainty.

An important feature of graphical models of uncertainty such as Bayesian networks is that they provide clear visual representations of many independence relationships embedded in the underlying probabilistic model. Once a Bayesian network is established, it can be used to represent the deep causal knowledge of a domain expert and provide probabilistic answers to many queries regarding the consequences of observed evidence in that domain.

One of the key problems in this area is Bayesian network inference, i.e. computing the posterior probabilities over query nodes X, given the evidence E encountered so far. There are two general kinds of Bayesian networks inference tasks: belief updating and belief revision. Belief updating, also called probabilistic inference, concerns the computation of posterior probabilities over query variables given the evidence, while belief revision, also called MAP explanation and used in machine learning and other applications of evidential inference, aims to find the maximally probable explanation (global assignment) to the observed evidence.

Probabilistic inference was shown to be NP-hard in 1990 by Cooper, and in 1993, Dagum and Luby showed that approximating probabilistic inference is also NP-hard. In 1994, Shimony proved that MAP explanation is NP-hard. In 1998, Abdelbar showed that approximating MAPs is also NP-hard.

Given the NP-hard complexity result, one of the major challenges is the design of efficient approximate Bayesian networks inference algorithms for very large probabilistic models under real-time constraints. There already exist many inference algorithms, both exact and approximate. Now the main problem is what works well where? One of our research directions is to characterize different classes of inference problems and identify appropriate inference algorithms for them.  We believe that by acquiring this knowledge we will be able to integrate various types of exact and approximate algorithms into a real-time decision support system in such a way that the most appropriate algorithm is executed for the specific inference problem.

Another promising direction is to explore asymmetries in the underlying joint probability distributions and search for the most likely states of the model. According to Druzdzel (1994), very often a small fraction of states covers a large portion of the total probability space. The skewness of a joint probability space may aid the design of efficient search-based and sampling-based algorithms for inference. This would combine benefits and theoretical results from the study of methods for predicting joint probability distributions, combinatorial search, and estimation of error bounds. Stochastic sampling algorithms and genetic algorithms are good candidates for searching this skewed space.

• William H. Hsu
• Sanjoy Das (affiliate)
• Stephen M. Welch (affiliate)

• Siddharth S. Chandak
• Haipeng Guo
• Roby Joehanes

• Julie A. Stilson

• Laura M. Kruse
• Sonal S. Junnarkar
• Benjamin B. Perry

Back to the KDD Lab main page