Representations and Algorithms for Monitoring Dynamic Systems 

Avi Pfeffer

Associate Professor at Computer Science

Harvard University


Continually monitoring the state of a dynamic system is an important problem for artificial intelligence.  Dynamic Bayesian networks (DBNs) provide for compact representation of probabilistic dynamic models.  However the monitoring task is extremely difficult even for well-factored DBNs.  Therefore approximate monitoring algorithms are needed.  One family of approximate monitoring algorithms is based on the idea of factoring the joint distribution over the state of the system into a product of distributions over factors consisting of subsets of variables.  Factoring relies on the notion of weak interaction between subsystems.  We identify a new notion of weak interaction called separability, and show that it leads to the property that, in order to compute the factor distributions at one point in time, only the factored distributions at the previous time point are needed.  We also define an approximate form of separability. We show that separability and approximate separability lead to very good approximations for the monitoring task.  Unfortunately, sometimes the factoring approach is computationally infeasible.  An alternative approach to approximate monitoring is particle filtering (PF), in which the joint distribution over the state of the system is approximated by a set of samples, or particles. In high dimensional spaces, the variance of PF is high and too many particles are required to provide good performance.  We improve the performance of PF by introducing factoring, maintaining particles over factors instead of the global state space.  This has the effect of reducing the variance of PF and so reducing its error.  Maintaining factored particles also allows us to improve PF by looking ahead to future evidence before deciding which particles to propagate, thus leading to much better accuracy.

Speaker Bio:


Avi Pfeffer is Associate Professor at Computer Science at Harvard University.  His research is directed towards achieving rational behavior in intelligent systems, based on the principles of probability theory, decision theory, Bayesian learning and game theory.  He received his PhD in 2000 from Stanford University, where his dissertation on probabilistic reasoning received the Arthur Samuel Thesis Award.  Dr Pfeffer has published technical papers on probabilistic reasoning, strategic reasoning, agent modeling, temporal reasoning, and database systems.  He was awarded the NSF Career Award in 2001 for work on strategic reasoning, and the Alfred P. Sloan Foundation Research Fellowship in 2002.  Dr Pfeffer serves on the editorial board of the Journal of Artificial Intelligence Research, and on the program committees of a number of leading conferences in artificial intelligence.