Tractable Inference for Complex Stochastic Processes

By Xavier Boyen, Daphne Koller. 1998

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Lightweight Probabilistic Deep Networks (2018, methodology): “To keep the computation lightweight, we will restrict the EP framework to assumed density ﬁltering (ADF) [7], which consists of a single EP forward pass.”
Expectation Propagation for approximate Bayesian inference (2001, methodology): “ADF has been indepen dently proposed in the statistics (Lauritzen, 1992), artifi cial intelligence (Boyen & Koller, 1998; Opper & Winther, 1999), and control (Maybeck, 1982) literatures.”
Autonomous agents modelling other agents: A comprehensive survey and open problems (2017, methodology): “there is high expected correlation within groups but 25 only little or no correlation between groups (an approach commonly used in probabilistic state estimation, e.g. Albrecht and Ramamoorthy, 2016; Boyen and Koller, 1998). The modelling agent can then use separate group models for each group. Even”
Probabilistic recognition of human faces from video (2002, methodology): “Assumed density filtering approach [28], different from CONDENSATION, is even more efficient.”
Efficient Inference for Distributions on Permutations (2007, methodology): “As we discuss later, the Fourier based approximation is equivalent to maintaining a set of low-order marginals, rather than the full joint, which we regard as being analagous to an Assumed Density Filter [6].”
Graphical Models, Exponential Families, and Variational Inference (2008, methodology): “Examples of such algorithms include the family of expectationpropagation algorithms due to Minka [172], the related class of assumed density filtering methods [149, 161, 37], expectation-consistent inference [181], structured summary-propagation algorithms [61, 112], and”
Applications of Bayesian networks and Petri nets in safety, reliability, and risk assessments: A review (2019, methodology): “For instance, for dynamic BN, the approximate Boyen-Koller algorithm (Boyen and Koller, 1998) can be used instead of the exact Junction Tree algorithm (Murphy, 2002) , when the BN is characterized by a relevant complexity.”
Analytic moment-based Gaussian process filtering (2009, unknown): “Therefore, GP-ADF is a form of Assumed Density Filtering (ADF), which has previously been introduced by Maybeck (1979), Boyen and Koller (1998), and Opper (1998). Furthermore, to compute the first two predictive moments, GP-ADF takes the uncertainty about the latent functions f, g into account.”
A family of algorithms for approximate Bayesian inference (2001, methodology): “ADF has been independently proposed in the statistics (Lauritzen, 1992; Bernardo & Giron, 1988; Stephens, 1997), artiicial intelligence (Boyen & Koller, 1998b; Opper & Winther, 1999; Barber & Sollich , 1999; Frey et al., 2000), and control literature (Kushner & Budhiraja, 2000; Maybeck, 1982).”
Learning Bayesian networks: approaches and issues (2011, methodology): “Apart from the possibly massive number of nodes if the time is far in the future, the repetitious structure of this expansion is often not amenable to standard exact techniques for multiply-connected networks; see Boyen and Koller (1998) for a look at this problem and a possible solution. Kjærulff (”
Pattern Recognition and Machine Learning (2006, unknown): “A special case of EP, known as assumed density filtering (ADF) or moment matching (Maybeck, 1982; Lauritzen, 1992; Boyen and Koller, 1998; Opper and Winther, 1999), is obtained by initializing all of the approximating factors except the first to unity and then making one pass through the factors upd”
Expectation Propagation in Gaussian Process Dynamical Systems (2012, methodology): “ iterative reﬁnement scheme of EP. 3 Expectation Propagation in GPDS EP [10,11] is an accurate and deterministic approximate inference algorithm, based on generalizations of Assumed Density Filtering [3]. EP iteratively reﬁnes the posterior distribution over the latent variables. EP is derived using”
Model-based approximate querying in sensor networks (2005, background): “For example, these models can be extended to allow for efficient representation and inference in dynamical systems [32, 33], and to answer causal queries [34].”
Learning Multilevel Distributed Representations for High-Dimensional Sequences (2007, background): “Boyen and Koller showed that the stochastic dynamics attenuates the approximation error created by projecting into the assumed density space and that this attenuation typically prevents the approximation error from diverging.”
Recent Advances in Hierarchical Reinforcement Learning (2003, background): “One approach that Rohanimanesh and Mahadevan [56] have been studying is how to exploit results from approximation of structured stochastic processes [6] to develop structured ways of approximating the next-state predictions of temporally-extended activities.”