Tractable Inference for Complex Stochastic Processes
  The monitoring and control of any dynamic system depends crucially on the
ability to reason about its current status and its future trajectory. In the
case of a stochastic system, these tasks typically involve the use of a belief
state- a probability distribution over the state of the process at a given
point in time. Unfortunately, the state spaces of complex processes are very
large, making an explicit representation of a belief state intractable. Even in
dynamic Bayesian networks (DBNs), where the process itself can be represented
compactly, the representation of the belief state is intractable. We
investigate the idea of maintaining a compact approximation to the true belief
state, and analyze the conditions under which the errors due to the
approximations taken over the lifetime of the process do not accumulate to make
our answers completely irrelevant. We show that the error in a belief state
contracts exponentially as the process evolves. Thus, even with multiple
approximations, the error in our process remains bounded indefinitely. We show
how the additional structure of a DBN can be used to design our approximation
scheme, improving its performance significantly. We demonstrate the
applicability of our ideas in the context of a monitoring task, showing that
orders of magnitude faster inference can be achieved with only a small
degradation in accuracy.
