Ahmed,

The problems you describe with the roll-up algorithm are well-known,
and they are not the fault of the algorithm.  In general, the belief 
state (the distribution over the time t states given the evidence
up to time t) does not admit a factored representation.  In other
words, in most cases, the only way to represent it is an explicit
joint distribution over the time t variables.  This phenomenon occurs
because, even in sparse DBN structures, common causes in an earlier
slice typically make all of the time t variables correlated.  

Kjaerulff [UAI '92] presents a more sophisticated algorithm than the
simple roll-up algorithm, that exploits whatever structure might be 
in the DBN.  However, because of the reasons above, that might not 
be enough for your applications.

As an alternative, Xavier Boyen and I [UAI '98] present an approximate 
inference algorithm intended to circumvent precisely this problem.
It's simple to implement and works very well for the DBNs we've tried.
If you don't mind some error in the answers, it might be a good
solution in your case.

-- Daphne
------------------------------------------------------------------------------
Professor Daphne Koller              phone: (650) 723-6598
Computer Science Department          fax:   (650) 725-1449
Gates Building 1A, Room 142          email: [EMAIL PROTECTED]
Stanford University                  URL: http://robotics.stanford.edu/~koller
Stanford, CA 94305-9010
------------------------------------------------------------------------------

Reply via email to