  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.
