Learning Nonlinear Dynamical Systems Using an EM Algorithm

Zoubin Ghahramani, Sam T. RoweisNeurIPS 1998 · OpenReview

This paper, authored by machine learning pioneers Zoubin Ghahramani and Sam Roweis, presents a classic approach to a difficult problem: how do we learn the "rules" of a system when we can't see its internal state and the rules themselves are nonlinear?

TL;DR

The authors introduce a framework for learning nonlinear dynamical systems by combining the Expectation-Maximization (EM) algorithm with Extended Kalman Smoothing. By using Gaussian Radial Basis Functions (RBFs) to model nonlinearities, they turn a mathematically daunting "maximization" step into a simple system of linear equations that can be solved analytically.

What Problem Does This Paper Address?

In engineering and physics, we often deal with state-space models. Imagine a robot moving through a room: we have its internal state (position/velocity), inputs (motor commands), and noisy observations (camera feeds). If the physics are linear, we use Kalman Filters to track the robot.

However, the real world is rarely linear. Learning the parameters of a nonlinear system is much harder because the internal states are "hidden" and uncertain. Standard techniques often struggle because they require integrating over this uncertainty, which usually results in intractable math. The authors aim to provide a principled, batch-learning algorithm (EM) that can handle these nonlinearities and hidden variables without resorting to slow, high-variance sampling methods.

Methods

The paper utilizes the Expectation-Maximization (EM) algorithm, which alternates between two steps:

  1. The E-Step (Expectation): Given the current guess of the system's rules, what is the most likely path the hidden states took? The authors use Extended Kalman Smoothing (EKS). EKS works by linearizing the nonlinear functions at every time step, allowing for a Gaussian approximation of the hidden state's distribution.
  2. The M-Step (Maximization): Given these estimated paths (and their uncertainty), how can we improve our guess of the system's rules?
Extended Kalman Smoothing and RBF fitting

The "magic" of this paper lies in the choice of function approximator for the nonlinearities. The authors use Gaussian Radial Basis Functions (RBFs). Because both the state estimates (from the E-step) and the RBFs are Gaussian, the integrals required to update the model parameters can be solved analytically. This transforms the M-step from a complex optimization problem into a straightforward set of linear equations, effectively fitting the RBFs to the entire "Gaussian cloud" of uncertainty rather than just a point estimate.

Datasets

The paper focuses on a proof-of-concept using a synthetic dataset:

  • Synthetic 1D Nonlinear System: A system with a single input, state, and output variable. The state transition is governed by a tanh nonlinearity.
  • Training/Testing: The model was trained on a time series of inputs and outputs driven by white noise.
  • Benchmarks: The paper compares the nonlinear EM approach against a standard linear dynamical system (LDS) model.

Key Insights and Ideas

  • Analytic Tractability via RBFs: The most significant insight is that Gaussian RBFs are the "perfect fit" for the Gaussian uncertainty produced by Kalman smoothing. This synergy allows the model to account for the entire distribution of the hidden state rather than just the mean.
  • EM as a Lyapunov Function: The authors point out that while online system identification can be unstable, the EM algorithm is inherently trying to maximize likelihood, which acts as a stabilizing force (a Lyapunov function) for stable learning.
  • Principled Handling of Missing Data: Because it is based on EM, the framework naturally handles gaps in data (missing inputs or outputs), which is a common headache in real-world sensor data.

Key Results

Experimental results showing inputs/outputs, likelihood comparison, and recovered nonlinearity
  • Nonlinearity Recovery: Starting from a simple linear model initialization, the algorithm successfully "discovered" the underlying sigmoid (tanh) nonlinearity in fewer than 10 iterations of EM (shown in the rightmost plot above).
  • Superiority over Point-Estimates: The authors demonstrated that fitting the RBFs using the full covariance information (the uncertainty) from the E-step produces a much more accurate model than simply fitting the RBFs to the mean of the state estimates.
  • Efficiency: By avoiding iterative optimization (like backpropagation) in the M-step, the algorithm remains computationally efficient compared to neural-network-based alternatives of the time. The nonlinear dynamical system (NLDS) model also achieved a significantly higher log-likelihood than the baseline linear model.

Limitations and Future Work

  • Fixed Kernels: In this implementation, the centers and widths of the RBFs are fixed at the start. To update them during learning, one would need to use "partial M-steps" (gradient descent), which sacrifices the analytic simplicity.
  • The Curse of Dimensionality: RBF networks require an exponential number of kernels as the dimensionality of the state space increases, making this specific approach difficult to scale to very high-dimensional systems.
  • Initialization Sensitivity: Like all EM algorithms, it is sensitive to the starting parameters. The authors suggest a "nested initialization" (starting with a linear model) to mitigate this.
  • Stationarity: The presented version is a batch algorithm for stationary systems. The authors mention they are working on an online version for non-stationary (changing) dynamics.

Summary updated

Abstract

The Expectation-Maximization (EM) algorithm is an iterative pro(cid:173) cedure for maximum likelihood parameter estimation from data sets with missing or hidden variables [2]. It has been applied to system identification in linear stochastic state-space models, where the state variables are hidden from the observer and both the state and the parameters of the model have to be estimated simulta(cid:173) neously [9]. We present a generalization of the EM algorithm for parameter estimation in nonlinear dynamical systems. The "expec(cid:173) tation" step makes use of Extended Kalman Smoothing to estimate the state, while the "maximization" step re-estimates the parame(cid:173) ters using these uncertain state estimates. In general, the nonlinear maximization step is difficult because it requires integrating out the uncertainty in the states. However, if Gaussian radial basis func(cid:173) tion (RBF) approximators are used to model the nonlinearities, the integrals become tractable and the maximization step can be solved via systems of linear equations. 1 Stochastic Nonlinear Dynamical Systems We examine inference and learning in discrete-time dynamical systems with hidden state Xt, inputs Ut, and outputs Yt. 1 The state evolves according to stationary nonlinear dynamics driven by the inputs and by additive noise (1) 1 All lowercase characters (except indices) denote vectors. Matrices are represented by uppercase characters. 432 Z. Ghahramani and S. T Roweis where w is zero-mean Gaussian noise with covariance Q. 2 The outputs are non(cid:173) linearly related to the states and inputs by Yt = g(Xt, Ut) + v (2) where v is zero-mean Gaussian noise with covariance R. The vector-valued non lin(cid:173) earities f and 9 are assumed to be differentiable, but otherwise arbitrary. Models of this kind have been examined for decades in various communities. Most notably, nonlinear state-space models form one of the cornerstones of modern sys(cid:173) tems and control engineering. In this paper, we examine these models within the framework of probabilistic graphical models and derive a novel learning algorithm for them based on EM. With one exception,3 this is to the best of our knowledge the first paper addressing learning of stochastic nonlinear dynamical systems of the kind we have described within the framework of the EM algorithm. The classical approach to system identification treats the parameters as hidden vari(cid:173) ables, and applies the Extended Kalman Filtering algorithm (described in section 2) to the nonlinear system with the state vector augmented by the parameters [5]. 4 This approach is inherently on-line, which may be important in certain applications. Furthermore, it provides an estimate of the covariance of the parameters at each time step. In contrast, the EM algorithm we present is a batch algorithm and does not attempt to estimate the covariance of the parameters. There are three important advantages the EM algorithm has over the classical ap(cid:173) proach. First, the EM algorithm provides a straightforward and principled method for handing missing inputs or outputs. Second, EM generalizes readily to more complex models with combinations of discrete and real-valued hidden variables. For example, one can formulate EM for a mixture of nonlinear dynamical systems. Third, whereas it is often very difficult to prove or analyze stability within the classical on-line approach, the EM algorithm is always attempting to maximize the likelihood, which acts as a Lyapunov function for stable learning. In the next sections we will describe the basic components of the learning algorithm. For the expectation step of the algorithm, we infer the conditional distribution of the hidden states using Extended Kalman Smoothing (section 2). For the maximization step we first discuss the general case (section 3) and then describe the particular case where the nonlinearities are represented using Gaussian radial basis function (RBF; [6]) networks (section 4). 2 Extended Kalman Smoothing Given a system described by equations (1) and (2), we need to infer the hidden states from a history of observed inputs and outputs. The quantity at the heart of this inference problem is the conditional density P(XtIUl,"" UT, Yl,.' " YT), for 1 ::; t ::; T, which captures the fact that the system is stochastic and therefore our inferences about x will be uncertain. 2The Gaussian noise assumption is less restrictive for nonlinear systems than for linear systems since the nonlinearity can be used to generate non-Gaussian state noise. 3The authors have just become aware that Briegel and Tresp (this volume) have applied EM to essentially the same model. Briegel and Tresp's method uses multilayer perceptrons (MLP) to approximate the nonlinearities, and requires sampling from the hidden states to fit the MLP. We use Gaussian radial basis functions (RBFs) to model the nonlinearities, which can be fit analytically without sampling (see section 4) . 41t is important not to confuse this use of the Extended Kalman algorithm, to simul(cid:173) taneously estimate parameters and hidden states, with our use of EKS, to estimate just the hidden state as part of the E step of EM. Learning Nonlinear Dynamics Using EM 433 For linear dynamical systems with Gaussian state evolution and observation noises, this conditional density is Gaussian and the recursive algorithm for computing its mean and covariance is known as Kalman smoothing [4, 8]. Kalman smoothing is directly analogous to the forward-backward algorithm for computing the conditional hidden state distribution in a hidden Markov model, and is also a special case of the belief propagation algorithm. 5 For nonlinear systems this conditional density is in general non-Gaussian and can in fact be quite complex. Multiple approaches exist for inferring the hidden state distribution of such nonlinear systems, including sampling methods [7] and varia(cid:173) tional approximations [3]. We focus instead in this paper on a classic approach from engineering, Extended Kalman Smoothing (EKS). Extended Kalman Smoothing simply applies Kalman smoothing to a local lineariza(cid:173) tion of the nonlinear system. At every point x in x-space, the derivatives of the vector-valued functions f and 9 define the matrices, Ax == M I x=x and ex == ~ I x=x' respectively. The dynamics are linearized about Xt, the mean of the Kalman filter state estimate at time t: The output equation (2) can be similarly linearized. If the prior distribution of the hidden state at t = 1 was Gaussian, then, in this linearized system, the conditional distribution of the hidden state at any time t given the history of inputs and outputs will also be Gaussian. Thus, Kalman smoothing can be used on the linearized system to infer this conditional distribution (see figure 1, left panel). (3)
BibTeX
@inproceedings{ghahramani1998learning,
  author = {Zoubin Ghahramani and Sam T. Roweis},
  title = {{Learning Nonlinear Dynamical Systems Using an EM Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1998},
  url = {https://openreview.net/forum?id=HyELW_bOZS},
}
Figure