Tractable Inference for Complex Stochastic Processes

Abstract

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.

Appears in Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI1998)

References in corpus (2)

• Stochastic Simulation Algorithms for Dynamic Probabilistic Networks
• A Scheme for Approximating Probabilistic Inference

Cited by in corpus (54)

• Expectation Propagation for approximate Bayesian inference
• Learning the Structure of Dynamic Probabilistic Networks
• Value-Function Approximations for Partially Observable Markov Decision Processes
• Online Planning Algorithms for POMDPs
• Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems
• Anytime Point-Based Approximations for Large POMDPs
• Finding Approximate POMDP solutions Through Belief Compression
• Learning Symbolic Models of Stochastic Domains
• Continuous Time Bayesian Networks
• Counting Belief Propagation
• Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks
• Probabilistic State-Dependent Grammars for Plan Recognition
• The Factored Frontier Algorithm for Approximate Inference in DBNs
• Inference in Hybrid Networks: Theoretical Limits and Practical Algorithms
• Approximate Planning for Factored POMDPs using Belief State Simplification
• Factored Particles for Scalable Monitoring
• Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Values Approximation
• Relational Dynamic Bayesian Networks
• Optimal Value of Information in Graphical Models
• Mean Field Variational Approximation for Continuous-Time Bayesian Networks
• Value-Directed Belief State Approximation for POMDPs
• Robust 3D reconstruction of dynamic scenes from single-photon lidar using Beta-divergences
• Approximate Smoothing and Parameter Estimation in High-Dimensional State-Space Models
• Sufficiency, Separability and Temporal Probabilistic Models
• Randomized gap and amplitude estimation
• Simplified decision making in the belief space using belief sparsification
• Discovering the Hidden Structure of Complex Dynamic Systems
• A Rate-Distortion Framework for Explaining Neural Network Decisions
• Bayesian Conditional Density Filtering
• Vector-space Analysis of Belief-state Approximation for POMDPs
• A Sufficient Statistic for Influence in Structured Multiagent Environments
• Assumed Density Filtering Q-learning
• Learning in the Presence of Corruption
• Reasoning about Hypothetical Agent Behaviours and their Parameters
• Expectation Propogation for approximate inference in dynamic Bayesian networks
• Monte-Carlo optimizations for resource allocation problems in stochastic network systems
• Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks
• Efficient inference in persistent Dynamic Bayesian Networks
• Reasoning about Probabilities in Dynamic Systems using Goal Regression
• Asynchronous Dynamic Bayesian Networks
• Factored Filtering of Continuous-Time Systems
• Bayesian Methods in Tensor Analysis
• Streaming Probabilistic Deep Tensor Factorization
• Decayed MCMC Filtering
• Factored Probabilistic Belief Tracking
• Variational Learning in Mixed-State Dynamic Graphical Models
• Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games
• Expectation Propagation in Gaussian Process Dynamical Systems: Extended Version
• Approximate Separability for Weak Interaction in Dynamic Systems
• Auxiliary Variables for Bayesian Inference in Multi-Class Queueing Networks
• Conditional Expectation Propagation
• Particle Filters in Robotics (Invited Talk)
• Towards Practical Bayesian Parameter and State Estimation
• Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks (Extended Abstract)