System identification (SysID) is the process of building mathematical models of physical systems from data. In robotics, this process is often complicated by "partially observed" environments. While we can easily measure a robot's position and velocity, we cannot directly observe hidden variables like the temperature of its motors, the intentions of other agents, or the complex fluid dynamics of airflow around a fast-moving vehicle.
This paper introduces Certainty-Equivalent Expectation-Maximization (CE-EM), a highly scalable algorithm designed to identify the dynamics of nonlinear systems with unobserved states. By replacing complex probability distributions with simple point estimates, CE-EM achieves a massive 47x speedup over state-of-the-art particle-based methods and successfully models high-dimensional systems where traditional methods fail.
The Bottleneck in Standard EM
The standard tool for handling partially observed systems is the Expectation-Maximization (EM) algorithm. EM operates by alternating between estimating the hidden states and updating the model parameters.
However, EM requires an "E-step" where the algorithm must estimate the full probability distribution of all unobserved states over time. For high-dimensional, nonlinear systems, this typically involves "Particle Smoothing." Unfortunately, particle-based methods suffer heavily from the curse of dimensionality: as the number of hidden states grows, the number of particles required to get a reliable estimate increases exponentially, making the process computationally intractable for complex robots.
The CE-EM Solution
The authors propose CE-EM based on a radical but effective simplification: instead of trying to compute the full probability distribution of the hidden states (the "Expectation"), the algorithm simply finds the single most likely state trajectory (the "Certainty-Equivalent" point estimate).
Key technical components of this approach include:
- Block Coordinate-Ascent: The algorithm alternates between a Smoothing Step (finding the best hidden states given current parameters) and a Learning Step (finding the best parameters given those states).
- Trust-Region Regularization: To prevent the optimizer from making unstable jumps, a soft trust-region (similar to Levenberg-Marquardt damping) is applied, ensuring convergence even in non-convex optimization landscapes.
- Batch Nonlinear Least-Squares: By treating the smoothing step as a batch optimization problem rather than a recursive filter, CE-EM significantly improves numerical stability for long time-series data.
Key Insights: Why Point Estimates Work
Why does throwing away the full probability distribution work so well? The success of CE-EM hinges on the "Nearly Deterministic" assumption. Most robotic systems have very low "process noise" because they closely follow the laws of physics.
In these low-noise scenarios, the probability distribution of the hidden states is highly peaked (unimodal). A point estimate perfectly captures this "peak" without wasting computational resources calculating the negligible "tails" of the distribution. While CE-EM introduces a technical bias if the system has high noise, this bias is a worthwhile trade-off for the massive gains in speed and the ability to handle high-dimensional states. Furthermore, CE-EM naturally supports "gray-box" modeling, allowing researchers to bake known physics into the model while learning the unknown parameters.
Experimental Results
The authors evaluated CE-EM on two primary benchmarks: a synthetic 18-dimensional Coupled Lorenz Attractor system and the real-world Stanford Autonomous Helicopter Dataset.
Speed and Reliable Convergence
On the complex Lorenz system, CE-EM was 47 times faster per epoch than Particle EM. More importantly, it proved vastly more reliable.
As shown in the parameter convergence plots, CE-EM consistently converged to accurate parameter estimates in about 5 epochs. In contrast, Particle EM exhibited high variance, often diverging or requiring 50 to 100 epochs to reach similar levels of accuracy.
Real-World Helicopter Aerodynamics
The Stanford Autonomous Helicopter Dataset features an aerobatic helicopter performing aggressive maneuvers. This is a notoriously difficult SysID benchmark because the helicopter's acceleration is heavily influenced by unobserved "fluid states" (the wake it creates in the air).
The CE-EM trained model (labeled "NL" for Nonlinear) outperformed all baselines across various maneuvers. It achieved lower RMS error than H25 (the previous state-of-the-art neural network approach), standard Subspace Identification (SID) methods, and LSTMs, which struggled to capture the long-term dependencies of the fluid states.
Limitations and Future Work
The primary limitation of CE-EM is its reliance on the assumption that the distribution of hidden states is unimodal. If a system is highly stochastic or features multimodal hidden states (e.g., a sensor that could be in one of two distinct, divergent failure modes), the point-estimate approach of CE-EM might fail to capture the true dynamics.
Looking forward, the authors suggest that CE-EM's scalability opens the door to modeling even larger partially observed systems, ranging from distributed robotic networks to epidemiological models where true infection states are hidden and testing capacity is limited.
Summary updated