ODE filter

Uses your system voice; voice and rate in settings.

Snapshot

≈ 12 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.

ODE filters are a class of probabilistic numerical methods for solving ordinary differential equations (ODEs) that frame the problem of finding a solution to an initial value problem as a Bayesian inference task. Solutions are modeled as probability distributions that also account for the discretization error introduced through the numerical approximation. This probabilistic treatment provides an computation-aware alternative to classical numerical ODE-solvers, which typically only provide point-wise error bounds. It further enables sampling of joint trajectories from the posterior, as well as quantifying uncertainty about the underlying ODE itself. ODE filters offer a flexible framework for incorporating additional information, such as measurements or conservation laws. The general ODE filtering procedure consists of two steps: The first is the definition of a Prior distribution, for the ODE solution, in the form of a stochastic processes, more specifically, as Gauss–Markov processes. Discretization results in nonlinear Gaussian state space models. Second, use a general Bayesian filtering and smoothing algorithm, from the field of recursive Bayesian estimation, to find numerical solutions to the ODE.…

ODE filters are a class of probabilistic numerical methods for solving ordinary differential equations (ODEs) that frame the problem of finding a solution to an initial value problem as a Bayesian inference task. Solutions are modeled as probability distributions that also account for the discretization error introduced through the numerical approximation. This probabilistic treatment provides an computation-aware alternative to classical numerical ODE-solvers, which typically only provide point-wise error bounds. It further enables sampling of joint trajectories from the posterior, as well as quantifying uncertainty about the underlying ODE itself. ODE filters offer a flexible framework for incorporating additional information, such as measurements or conservation laws. The general ODE filtering procedure consists of two steps: The first is the definition of a Prior distribution, for the ODE solution, in the form of a stochastic processes, more specifically, as Gauss–Markov processes. Discretization results in nonlinear Gaussian state space models. Second, use a general Bayesian filtering and smoothing algorithm, from the field of recursive Bayesian estimation, to find numerical solutions to the ODE. The naming convention of ODE filters typically reflects the underlying filtering algorithm: For instance, combining the particle filter with this framework yields the particle ODE filter. Since smoothers are extensions of filters, the literature often refers to both under the umbrella term "ODE filters". \dot{y}(t) = f(y(t),t), \quad t\in [0,T], \quad y(0) = y_0 \in \mathbb{R}^d. The vector field f: \mathbb{R}^d \times [0,T] \rightarrow \mathbb{R}^d is assumed to be Lipschitz-continuous such that a unique global solution to this ODE-IVP exists according to the Pickard-Lindelöf theorem: . Classical Numerical ODE Solvers, are algorithms that compute approximate solutions \hat{y}(t) \approx y(t) on a discrete mesh \{t_n\}_{n=0}^N,\quad 0 = t_0 . Probabilistic ODE Solvers additionally estimate the uncertainty introduced through the discretization. ODE Filters are a type of probabilistic ODE solvers, that adopt a Bayesian Inference framework to compute a posterior p\left(y(t) \mid y(0), \{ \dot{y}(t_n) = f(y(t_n), t_n) \}_{n=0}^N\right). This is done in two steps. First, prior data and likelihood is defined by modeling solutions to the ODE as a Gauss-Markov process. Second, the posterior is computed with Bayesian filtering and smoothing algorithms. X(0) \sim \mathcal{N}(\mu_0, \Sigma_0) \mathrm{d}X(t) = FX(t)\mathrm{d}t + L \mathrm{d}B_t. It describes a stochastic process ("the system"): X(t) = \left[\left(X^{(0)}(t)\right)^T, \cdots, \left(X^{(q)}(t)\right)^T\right]^T \in \mathbb{R}^{(q+1)d}. The state of the system are realizations x(t) \sim X(t) , where X^{(0)}(t) and X^{(1)}(t) model , y(t) and \dot{y}(t) respectively. Te remaining q-1 sub-vectors may be used to model higher-order derivatives. F is a state transition matrix, L a diffusion matrix, and B(t) is a vector standard Wiener process. Note that F and L need to be chosen such that \mathrm{d}X^{(0)}(t) = X^{(1)}(t)\mathrm{d}t holds . Solutions to LTI-SDEs are Gauss-Markov processes (GMP). , of the form: p\left(x(t) \mid X^{(0)}(0) = x_0 = y_0\right) = GP\left(x(t) \mid \mu(t), k(t,t')\right) \mu(t) = exp(Ft)x_0 k(t,t') = \int_0^{\mathrm{min(t,t')}}exp(F(t-\tau))LL^Texp(F(t'-\tau))^T\mathrm{d}\tau. Where \mu: [0,T] \rightarrow \mathbb{R}^{(q+1)d} and k: [0,T]\times[0,T]\rightarrow \mathbb{R}^{(q+1)d \times (q+1)d} . Gauss-Markov processes are computationally favorable over generic Gaussian process priors, as they allow for inference with linear time complexity \mathcal{O}(N) compared to the general GP inference complexity of \mathcal{O}(N^3) . Discretization of the GMP results in a linear Gaussian state space model (LGSSM): x(t_0) \sim \mathcal{N}(\mu_0, \Sigma_0) x(t_{n+1}) \mid x(t_n) \sim \mathcal{N}(A(t_{n+1}-t_n)x(t_n), Q(t_{n+1}-t_n)) A(h) = exp(Fh) Q(h) = \int_0^{h} e^{F\tau}LL^Te^{F^T\tau} \mathrm{d}\tau. Z(t) = g(X(t)) = X^{(1)}(t) - f(X^{(0)}(t), t). If it were possible to condition X(t) on the event 0 = z(t) \sim Z(t) for all t\in[0,T] , this would result in a point-mass on the true solution . This is computationally intractable (just like for all other forms of numerical simulation), which motivates the discretization of the problem and conditioning the state on discrete observations \{z(t_n)=0\}_{n=0}^N. The information operator can be modified to solve higher-order ODEs. Multiple information operators can be added to incorporate additional information, such as conservation laws or measurement data z_n \mid x(t_n) \sim \delta(z_n - g(x(t_n))). To improve the model's generality and account for numerical errors introduced by discretization, a measurement variance R_n can be added to z_n . The observations can be incorporated into the LGSSM as a nonlinear measurement model, yielding the final nonlinear Gaussian state space model (NLGSSM), that is the basis of all ODE filters: x_0 \sim \mathcal{N}(\mu_0, \Sigma_0) x_{n+1} \mid x_n \sim \mathcal{N}(A(h_{n+1})x_n, Q(h_{n+1})) z_n \mid x_n \sim \mathcal{N}(g_n(x_n), R_n). Here h_{n+1} = t_{n+1} - t_n , x_n = x(t_n) , z_n = z(t_n) , and g_n(x_n) = x_n^{(1)} - f(x_n^{(0)},t_n) . The desired posterior p\left(x(t) \mid x_0,\{z_n\}_{n=0}^N\right) can now be computed iteratively by any filtering and smoothing algorithms known from signal processing or recursive Bayesian estimation. 2: for n=0,1,\cdots,N-1 do: 3: optional: adapt dynamic model p(x_{n+1} \mid x_n) 4: optional: choose step size h_n > 0 5: predict p(x_{n+1} \mid z_{1:n}) = \int p(x_{n+1}\mid x_n)p(x_n\mid z_{1:n})\mathrm{d}x_n 6: observe the ODE z_{n+1} = 0 7: update p(x_{n+1} \mid z_{1:n+1}) = p(z_{n+1} \mid x_{n+1})p(x_{n+1} \mid z_{1:n})p(z_{n+1})^{-1} 8: optional: backward transition p(x_n|x_{n+1}, z_{1:n}) = p(x_{n+1}|x_n)p(x_n|z_{1:n})p(x_{n+1}|z_{1:n})^{-1} 9: end for 10: return \{ p(x_n \mid z_{1:n}), p(x_n \mid z_{1:n-1})\}_{n=0,\dots,N} Algorithm: ODE Smoother (f, x_0, p(x_{n+1}\mid x_n)) 1: \{p(x_n \mid z_{1:n}), p(x_n \mid z_{1:n-1})\}_{n=0,\dots,N} \;=\; \text{ODE filter}(f, x_0, p(x_{n+1}\mid x_n)) 2: for n = N-1,N-2, \cdots, 0 do: 3: compute p(x_n \mid z_{1:N}) = p(x_{n} \mid z_{1:n})\int p(x_{n+1} \mid x_n) p(x_{n+1} \mid z_{1:N}) p(x_{n+1} \mid z_{1:n})^{-1}\mathrm{d}x_{n+1} 4: end for 5: return \{ p(x_n \mid z_{1:N}) \}_{n=0,\dots,N} For nonlinear observation models, the probability distributions become non-Gaussian, rendering the above equations intractable. Therefore, to define a specific ODE filter and smoother, the predict, update, and compute steps must be specified in a tractable form. The full posterior can be computed from p(x_{0:N} \mid z_{1:N}) = p(x_N \mid z_{1:N})\prod_{n=0}^{N-1}p(x_n \mid x_{n+1},z_{n}). Having access to the full posterior enables sampling of joint trajectories that classical numerical methods do not allow. The choice of a prior distribution is replaced by choosing the free parameters of the GMP. That is choosing \mu_0, \Sigma_0, F, L, q , however, under some constraints. One of the most popular and most widely used GMPs is the q-times integrated Wiener process (i.e. integrated Brownian motion) . For simplicity we can set w.l.o.g. d=1 . The q-times Integrated Wiener process (IWP) is defined such that the sub-coordinates model the first q-derivatives of X^{(0)}(t), i.e. dX^{(n-1)} = X^{(n)}dt \quad \forall n \in [1, q] . Further, X^{ (q)} is a standard Wiener Process. This is equivalent to the drift and dispersion matrices: \breve{F}_{\mathrm{IWP}} = \left[\begin{array}{cccc}0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \\ 0 & 0 & \cdots & 0\end{array}\right], \quad \breve{L}_{\mathrm{IWP}} = \sigma \left[\begin{array}{cccc}0 \\ \vdots \\ 0 \\ 1\end{array}\right]. Note that for d>1 the full drift and dispersion matrices follow from the one-dimensional versions with a Kronecker product F_\mathrm{IWP} = \breve{F}_{\mathrm{IWP}} \otimes I_d , and L_\mathrm{IWP} = \breve{L}_{\mathrm{IWP}} \otimes I_d : . This yields the following known closed form solutions for the transition matrices [A(h)]_{i j} = [\exp (F h)]_{i j}=\mathbb{I}(j \geq i) \frac{h^{j-i}}{(j-i)!}, [Q(h)]_{i j} = \sigma^2 \frac{h^{2 q+3-i-j}}{(2 q+3-i-j)(q+1-i)!(q+1-j)!}. The ideal initialization of the IWP that considers all available information from the ODE with initial value x_0 is to evaluate all derivatives at x_0 : \mu_0 = [x_0, f(x_0), f^{ }(x_0), \cdots , f^{ }(x_0)]^T, \quad \Sigma_0 = \boldsymbol{0}. Here f^{ }(a) = [\nabla_x f^{ }\odot f](a) is recursively defined from f^{ }(a)= a and f^{ }(a) = f(a) , and \odot is the elementwise product. Computationally this can be efficiently computed via Taylor mode automatic differentiation. \hat{g}(X) = g(\xi) + J_g(\xi)(X-\xi), where J_g(\xi) \in \mathbb{R}^{d\times (q+1)d} is the Jacobian of g . This leads to an affine observation model z_n \mid x_n \sim g(z_n \mid x_n) = \mathcal{N}(H_nx_n+c_n, R_n), \quad H_n = J_g(\xi_n), \quad c_n=g(\xi_n) - J_g(\xi_n)\xi_n. The linearization point is chosen as the predicted mean from the previous observation \xi_n = m_n^- = \mathbb{E}[p(x_n \mid z_{1:n-1})] . With this, the predict, update, and compute equations all take on Gaussian form, for which closed form inference is possible. See extended Kalman filter for more details. \mathrm{\textbf{predict}}: p(x_{n+1} \mid z_{1:n}) = \mathcal{N}(x_{n+1} \mid m_{n+1}^-, P_{n+1}^-) \mathrm{\textbf{update}}: p(x_{n+1} \mid z_{1:n+1}) = \mathcal{N}(x_{n+1} \mid m_{n+1}, P_{n+1}) \mathrm{\textbf{compute}}: p(x_n \mid z_{1:N}) = \mathcal{N}(x_n \mid m_n^s, P_n^s). \dot{y}(t) = y(t) (1-y(t)),\quad t \in [0,10] \quad y(0)=y_0=0.01, for which a analytical solution exists: y(t) = \frac{1}{1+\left(\frac{1+y_0}{y_0}\right)y_0}. To solve this ODE-IVP with a PDE filter, the prior, discretization, as well as the predict, update, and compute steps need to be specified. A(h) = \left[\begin{array}{ccc}1 & h & h^2/2 \\ 0 & 1 & h\\ 0 & 0 & 1 \\ \end{array}\right], \quad \sigma = 1, \quad Q(h) = \left[\begin{array}{ccc} h^5/20 & h^4/8 & h^3/6 \\ h^4/8 & h^3/3 & h^2/2\\ h^3/6 & h^2/2 & h \\ \end{array}\right], with Taylor mode initialization: X(0) = \left[ y_0, y_0(1-y_0), y_0(1-y_0)(1-2y_0) \right]^T. We discretized the time domain uniformly with N = 20 \rightarrow h=0.5 \rightarrow t_n = n*h and observe data \{ z(t_n)=0 \}_{n=1}^N without any noise, hence R_n=0 . As filtering algorithm we use the EKF1 algorithm with the Jacobian is J_g(X) = [-X^{(0)}(1-2X^{(0)}), 1, 0] .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1338010706 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

11 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.