Bellman filter
≈ 7 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The Bellman filter is a recursive algorithm for estimating a sequence of unobserved (latent) states in a state-space model from noisy observations. It is typically formulated for models with a linear–Gaussian state transition and a possibly nonlinear and/or non-Gaussian observation density, and it updates the state by solving a per-time-step optimisation problem involving \log p(y_t|x_t) . Under linear–Gaussian observation models, it reduces to the standard Kalman filter update. From a dynamic-programming perspective, the Bellman filter applies Bellman's principle of optimality to a mode-estimation problem, yielding a recursion for an (online) maximisation objective whose maximiser is a filtered state estimate. In contrast with grid-based maximisation (as in the Viterbi algorithm for models with discrete states), the Bellman filter keeps the state space continuous and replaces the exact Bellman value functions by parametric (typically quadratic) function-space approximations, which makes the recursion computationally feasible in moderate to high dimensions.
The Bellman filter is a recursive algorithm for estimating a sequence of unobserved (latent) states in a state-space model from noisy observations. It is typically formulated for models with a linear–Gaussian state transition and a possibly nonlinear and/or non-Gaussian observation density, and it updates the state by solving a per-time-step optimisation problem involving \log p(y_t|x_t) . Under linear–Gaussian observation models, it reduces to the standard Kalman filter update. From a dynamic-programming perspective, the Bellman filter applies Bellman's principle of optimality to a mode-estimation problem, yielding a recursion for an (online) maximisation objective whose maximiser is a filtered state estimate. In contrast with grid-based maximisation (as in the Viterbi algorithm for models with discrete states), the Bellman filter keeps the state space continuous and replaces the exact Bellman value functions by parametric (typically quadratic) function-space approximations, which makes the recursion computationally feasible in moderate to high dimensions. Although the approach is more generally applicable, a commonly used specification keeps the classic linear–Gaussian state transition while allowing a general observation density. For t=1,\dots,n : Observation equation: y_t \sim p(y_t|x_t) State-transition equation: x_t = c + T x_{t-1} + R\eta_t where \eta_t \sim \text{i.i.d. } \mathcal N(0,Q) . The filter maintains predicted quantities \hat x_{t\mid t-1} , P_{t\mid t-1} and filtered quantities \hat x_{t\mid t} , P_{t\mid t} . I(x) := \int \left[-\nabla^2 \log p(y|x)\right]\, p(y|x)\,dy, where \nabla^2 operates on x . \hat x_{t\mid t-1} = c + T\hat x_{t-1\mid t-1}, P_{t\mid t-1} = T P_{t-1\mid t-1} T^\top + R Q R^\top. This is identical to the prediction step in the Kalman filter. \hat x_{t\mid t} = \arg\max_{x\in\mathbb R^d} \left\{ \log p(y_t|x) -\tfrac12 (x-\hat x_{t\mid t-1})^\top P_{t\mid t-1}^{-1}(x-\hat x_{t\mid t-1}) \right\}, P_{t\mid t} = \left(P_{t\mid t-1}^{-1} + I(\hat x_{t\mid t})\right)^{-1}. The update step is well defined if \log p(y_t|x) is concave in x or if P_{t\mid t-1}^{-1} is sufficiently large. In some cases, I(\hat x_{t\mid t}) in the formula for P_{t\mid t} can be replaced by the realised negative Hessian -\nabla^2 \log p(y_t|\hat x_{t\mid t}) . The maximisation can be interpreted as a maximum a posteriori (MAP) estimate of x_t : it combines the log-likelihood term \log p(y_t|x_t) with a quadratic log-prior coming from the Gaussian prediction x_t|y_{1:t-1}\sim\mathcal N(\hat x_{t\mid t-1},P_{t\mid t-1}) . Equivalently, the update solves a regularised likelihood problem: it chooses the state that best explains y_t while penalising deviation from the predicted mean \hat x_{t\mid t-1} according to the precision P_{t\mid t-1}^{-1} . y_t = d + Z x_t + \varepsilon_t where \varepsilon_t \sim \text{i.i.d. } \mathcal N(0,H) , then the level update \hat x_{t\mid t} and covariance update P_{t\mid t} reduce to the usual Kalman filter update. y_t = h(x_t) + \varepsilon_t, with \varepsilon_t\sim\mathcal N(0,H) , the Bellman update objective is proportional to the (negative) nonlinear least-squares criterion \tfrac12\,(y_t-h(x))^\top H^{-1}(y_t-h(x))+\tfrac12\,(x-\hat x_{t\mid t-1})^\top P_{t\mid t-1}^{-1}(x-\hat x_{t\mid t-1}). Applying a Gauss–Newton method to this problem yields the iterated extended Kalman filter (see article on the Extended Kalman filter). Bell and Cathey show that this iterated update is a Gauss–Newton method for the corresponding maximum-likelihood problem. Equivalently, this is the special case of the Bellman filter update with \log p(y_t|x) given by the Gaussian log-likelihood -\tfrac12(y_t-h(x))^\top H^{-1}(y_t-h(x)) (up to an additive constant).
Nonlinear/non-Gaussian state-transition equation
Although the exposition above assumes a linear–Gaussian state transition (so that the prediction step has closed form), Bellman's recursive approach applies also to state-space models with a general transition density p(x_t|x_{t-1}) . In this more general setting, solving Bellman's equation involves a joint maximisation over (x_t,x_{t-1}) . In this setting, degenerate state dynamics can be handled by equating some elements of x_t to those of x_{t-1} and optimising only over the free components. J_t := P_{t\mid t} T^{\top} P_{t+1\mid t}^{-1}. Initialise at t=n with \hat{x}_{n\mid n} and P_{n\mid n} . Then for t=n-1,\dots,1 : \hat{x}_{t\mid n} = \hat{x}_{t\mid t} + J_t\bigl(\hat{x}_{t+1\mid n}-\hat{x}_{t+1\mid t}\bigr), P_{t\mid n} = P_{t\mid t} + J_t\bigl(P_{t+1\mid n}-P_{t+1\mid t}\bigr)J_t^{\top}. In the Bellman-filter setting (linear–Gaussian state transition with a general observation density), these RTS recursions still apply to the (possibly approximate) filtered quantities produced by the Bellman filter. \hat{\psi} := \arg\max_{\psi}\sum_{t=1}^n \left[ \log p\!\left(y_t|\hat{x}_{t\mid t}\right) -\frac12\log\frac{\det(P_{t\mid t-1})}{\det(P_{t\mid t})} -\frac12(\hat{x}_{t\mid t}-\hat{x}_{t\mid t-1})^{\top}P_{t\mid t-1}^{-1}(\hat{x}_{t\mid t}-\hat{x}_{t\mid t-1}) \right]. The first term \log p(y_t|\hat{x}_{t\mid t}) measures how well the Bellman-filtered (mode) estimate explains the observation y_t . The remaining terms form a nonnegative regularisation penalty that discourages overfitting by penalising large adjustments from \hat{x}_{t\mid t-1} to \hat{x}_{t\mid t} , with the determinant ratio reflecting the reduction in (approximate) state uncertainty after incorporating y_t . In the linear–Gaussian observation case this coincides with the maximum likelihood estimator; otherwise it can be interpreted as maximising a second-order approximation to the usual prediction-error decomposition.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1363151122 under CC BY-SA 4.0; modifications have been made.