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
------------------------------------------------------------------------------