Abstract
Maximum likelihood (ML) estimation using Newton's method in nonlinear state space models (SSMs) is a challenging problem due to the analytical intractability of the log-likelihood and its gradient and Hessian. We estimate the gradient and Hessian using Fisher's identity in combination with a smoothing algorithm. We explore two approximations of the log-likelihood and of the solution of the smoothing problem. The first is a linearization approximation which is computationally cheap, but the accuracy typically varies between models. The second is a sampling approximation which is asymptotically valid for any SSM but is more computationally costly. We demonstrate our approach for ML parameter estimation on simulated data from two different SSMs with encouraging results.
Introduction
In fields ranging from control systems to signal processing, State Space Models (SSMs) are essential for describing the evolution of hidden states over time and their relationship to noisy observations. A critical task in utilizing these models is parameter estimation—determining the underlying physical constants or noise variances that govern the system. Maximum Likelihood Estimation (MLE) is the standard statistical approach for this task.
For linear systems with Gaussian noise, the Kalman Filter provides an exact solution. However, nonlinear systems present a significant challenge: the likelihood surface is analytically intractable. This intractability prevents the direct calculation of the gradient and the Hessian (curvature), which are necessary for efficient optimization. While gradient-free or quasi-Newton methods are often employed, they frequently lack the fast, quadratic convergence properties of a true Newton’s method. This paper provides a framework to estimate these missing derivatives, enabling the practical application of Newton-based optimization in nonlinear SSMs.
Methodology
The core of the proposed approach is the use of Fisher’s identity, which transforms the problem of calculating the gradient of the log-likelihood into a state-smoothing problem. To make Newton’s method computationally feasible, the authors utilize an estimator that treats the Hessian as a "by-product" of the gradient calculation. This allows for second-order optimization without the massive computational overhead typically associated with calculating second derivatives.
The paper explores two primary strategies for approximating the log-likelihood and its derivatives:
Linearization Approximation
The linearization approach (Algorithm 2) utilizes an Extended Kalman Filter (EKF) and solves the smoothing problem via Gauss-Newton optimization. This method is computationally efficient, relying on the assumption that the system can be locally linearized without significant loss of information.
Sampling Approximation
The sampling approach (Algorithm 3) employs Sequential Monte Carlo methods, specifically particle filtering and smoothing. This method is asymptotically consistent, meaning its accuracy improves as the number of particles increases, making it robust for highly nonlinear models, albeit at a higher computational cost.
Experimental Evaluation
The methods were evaluated using two simulated nonlinear SSMs, each consisting of 100 datasets with $N=1,000$ samples:
- Model 1: Features nonlinear dynamics (an $arctan$ function) but a linear measurement equation where the unknown parameters are located.
- Model 2: A more complex case where an unknown parameter scales the nonlinearity within the state dynamics themselves.
Results and Discussion
The experiments revealed several key insights into the performance of Newton-based MLE:
- Computational Efficiency: In Model 1, the linearization method (ALG2) was approximately 23 times faster per iteration than the sampling method (FFBSi) while maintaining lower bias and Mean Squared Error (MSE).
- Model Structure Sensitivity: The effectiveness of the approximation depends heavily on the parameter's location. When parameters reside in the linear part of the model (Model 1), linearization is highly effective. However, when parameters are embedded within nonlinear functions (Model 2), linearization struggles, and sampling methods or numerical quasi-Newton methods (NUM) provide superior accuracy.
- Convergence Rates: Newton-based methods required significantly fewer iterations to converge compared to standard particle-based gradient descent, validating the inclusion of Hessian information.
| Method | Model 1 Time (sec/iter) | Model 2 Time (sec/iter) |
|---|---|---|
| Linearization (ALG2) | 0.81 | 2.73 |
| Sampling (FFBSi) | 19.0 | 22.0 |
| Quasi-Newton (NUM) | 0.19 | 0.19 |
While the numerical quasi-Newton method (NUM) appears fastest in these low-dimensional tests, the authors note that the proposed Newton framework is expected to scale more robustly as the number of parameters increases.
Conclusion
This work demonstrates that Newton's method can be successfully applied to nonlinear SSM parameter estimation by approximating derivatives through linearization or sampling. The choice between these methods involves a trade-off: linearization offers extreme speed for models that are "linear enough," while sampling provides a robust, though slower, alternative for complex nonlinearities. Future research will focus on handling the noise in particle-based derivative estimates and comparing these results against Expectation Maximization (EM) algorithms.
Summary updated