Inference in Hybrid Networks: Theoretical Limits and Practical Algorithms

Abstract

An important subclass of hybrid Bayesian networks are those that represent Conditional Linear Gaussian (CLG) distributions --- a distribution with a multivariate Gaussian component for each instantiation of the discrete variables. In this paper we explore the problem of inference in CLGs. We show that inference in CLGs can be significantly harder than inference in Bayes Nets. In particular, we prove that even if the CLG is restricted to an extremely simple structure of a polytree in which every continuous node has at most one discrete ancestor, the inference task is NP-hard.To deal with the often prohibitive computational cost of the exact inference algorithm for CLGs, we explore several approximate inference algorithms. These algorithms try to find a small subset of Gaussians which are a good approximation to the full mixture distribution. We consider two Monte Carlo approaches and a novel approach that enumerates mixture components in order of prior probability. We compare these methods on a variety of problems and show that our novel algorithm is very promising for large, hybrid diagnosis problems.

Appears in Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI2001)

References in corpus (1)

• Tractable Inference for Complex Stochastic Processes

Cited by in corpus (10)

• Exact Inference in Networks with Discrete Children of Continuous Parents
• Optimal Value of Information in Graphical Models
• Lifted Inference for Relational Continuous Models
• Substructure and Boundary Modeling for Continuous Action Recognition
• Inference in Hybrid Bayesian Networks Using Mixtures of Gaussians
• Expectation Propogation for approximate inference in dynamic Bayesian networks
• Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting
• Discriminative Switching Linear Dynamical Systems applied to Physiological Condition Monitoring
• Gaussian Mixture Reduction for Time-Constrained Approximate Inference in Hybrid Bayesian Networks
• Inference with Seperately Specified Sets of Probabilities in Credal Networks