Hi Todd,
I had the same problem with Lauritzen's algorithm when I tried to use
it, which led me to analyze the complexity of inference in such hybrid
models. You may want to look at the paper:
Inference in Hybrid Networks: Theoretical Limits and Practical
Algorithms,
Uri Lerner, Ronald Parr, Uncertainty in Artificial Intelligence,
Proceedings of the 17th Annual Conference on Uncertainty in Artificial
Intelligence (UAI-01)
The paper is available from my web page:
http://robotics.stanford.edu/~uri/
as well as from Ron Parr's page:
http://www.cs.duke.edu/~parr/
The short answer is that the problem of huge cliques cannot be avoided
for networks such as the one you have. In the paper we prove the
NP-hardness of the problem, not only for exact inference but also for
approximate inference. Therefore if you force your cliques to be
smaller, you will get only an approximate answer, which may be very
different from the actual one.
On a more encouraging note, the NP-hardness for approximate inference
only applies to certain "worst-case" choices of the network parameters.
Depending on the parameters of your actual problem, you may be able to
come up with efficient approximate inference algorithms. One such
algorithm, based on the observations that in many domains there are only
a few likely assignments to the discrete variables while all other
assignments are very unlikely apriori, appears in the paper. In
particular, we found this to be a useful algorithm in the fault
diagnosis domain, where it is very unlikely for many independent faults
to happen simultaneously.
Hope this helps.
Cheers,
Uri
Todd Stephenson wrote:
>
> I am working with dynamic Bayesian networks with a mixture
> of continuous and discrete variables. I am using the
> propagation algorithm given in Lauritzen and Jensen (2001),
> "Stable local computation with conditional Gaussian distributions,"
> Statistics and Computing.
>
> Consider the following DBN, with discrete variables D[1] . . . D[N]
> and continous variables C[1] . . . C[N], where any variable can be
> unobserved:
>
> D[1] ---> D[2] ---> D[3] ---> D[4] ---> . . . ---> D[N]
> | | | | |
> | | | | |
> | | | | |
> | | | | |
> V V V V V
> C[1] ---> C[2] ---> C[3] ---> C[4] ---> . . . ---> C[N]
>
> Now, in order to have a decomposable graph after triangulation,
> there can not be any path between two non-adjacent discrete variables
> that passes only through continuous vertices (Proposition 7.9
> of Cowell et al., (1999) "Probabilistic Networks and Expert Systems).
> In this case, this means that all the discrete vertices D[1] . . . D[N]
> must be fully connected (because, since there is such a path between
> every possible pair of discrete vertices, the only solution is to
> connect them all with each other in triangulation).
>
> ============================================================
>
> My question is the following:
>
> Is there a method to avoid having to fully connect all these
> discrete variables and thus have to have a large clique containing
> all of the discrete variables? I would prefer, rather, to have
> smaller cliques (e.g. the clique {D[t],D[t+1],C[t],C[t+1]}) when
> doing propagation.
>
> Thanks in advance for any input.
>
> Todd
>
> --
> Todd Stephenson
> Dalle Molle Institute for
> Perceptual Artificial Intelligence
> PO Box 592
> CH-1920 Martigny
> Switzerland
> Tel: +41 27 721 77 52
> Fax: +41 27 721 77 12
> Email: Todd.Stephenson@idiap.ch
> WWW: http://www.idiap.ch
This archive was generated by hypermail 2b29 : Tue Nov 27 2001 - 12:37:19 PST