TL;DR
This paper introduces novel algorithms for nonlinear Kalman filtering that directly optimize divergence measures (KL and α-divergence) between the true posterior and a Gaussian approximation. By using Monte Carlo integration and avoiding approximations to the divergences themselves, these methods achieve improved accuracy and robustness compared to standard Extended Kalman Filters (EKF) and Unscented Kalman Filters (UKF), while remaining computationally competitive with particle filters.
What Problem Does This Paper Address?
Kalman filtering is a powerful tool for estimating the state of dynamic systems, but its standard form assumes linear system dynamics and measurement models. When these models become nonlinear, the posterior distribution of the system's state is no longer guaranteed to be Gaussian, making closed-form solutions intractable. Existing nonlinear Kalman filters, like the EKF and UKF, approximate the posterior with a Gaussian distribution but often rely on approximations of the divergence measures themselves. This paper addresses the challenge of finding a better Gaussian approximation to the true, potentially non-Gaussian, posterior in nonlinear systems by directly minimizing divergence measures between the true posterior and the Gaussian approximation.
Methods
The core contribution of this paper is the development of three novel algorithms for nonlinear Kalman filtering, each based on minimizing a different divergence measure:
- Forward KL Divergence Minimization (SKF - Stochastic Search Kalman Filter): This approach uses stochastic gradient descent to directly optimize the forward KL divergence. It employs a control variate technique to reduce the variance of the gradient estimates, making the optimization more efficient. This method is iterative.
- Reverse KL Divergence Minimization (MKF - Moment Matching Kalman Filter): This algorithm minimizes the reverse KL divergence. It leverages the property that for exponential family distributions (like Gaussians), minimizing reverse KL divergence is equivalent to matching moments (mean and covariance) between the true posterior and the Gaussian approximation. This is achieved using importance sampling in a single iteration.
- α-Divergence Minimization (@KF - α-divergence Kalman Filter): This method generalizes the previous two by minimizing the α-divergence, which encompasses both forward and reverse KL divergences as special cases. Similar to MKF, it uses importance sampling to match moments of a transformed distribution, allowing for a flexible trade-off between forward and reverse KL properties. This algorithm is also a single-iteration method.
A key aspect of all proposed methods is that they avoid approximating the divergence measures themselves, instead using Monte Carlo integration to derive unbiased gradient estimates for direct optimization. The paper also introduces an adaptive sampling technique to dynamically adjust the number of samples needed for a desired accuracy, further improving computational efficiency.
Datasets
The paper evaluates the proposed algorithms on synthetic datasets for:
- Radar and Sensor Tracking: These problems involve estimating the position and velocity of a target using nonlinear measurements (distance and bearing for radar, range-only for sensor networks). The synthetic data is generated using a constant velocity model in 2D, with varying process and measurement noise parameters to simulate different levels of nonlinearity and uncertainty.
- Options Pricing: This problem involves estimating hidden state variables (volatility and interest rate) related to financial options using a Black-Scholes model. Synthetic data is generated using historical VIX and stock prices, with specified process and measurement noise.
Key Insights and Ideas
- Direct Divergence Optimization: The paper demonstrates that directly optimizing divergence measures (KL and α-divergence) between the true posterior and a Gaussian approximation can lead to more accurate and robust nonlinear Kalman filtering compared to methods that approximate the divergences.
- α-Divergence Flexibility: The α-divergence provides a generalized framework that can offer improved performance by allowing a tunable parameter to balance the properties of forward and reverse KL divergences, particularly in the presence of strong measurement noise.
- Control Variates for SKF: The use of control variates in the SKF algorithm is crucial for making stochastic gradient descent practical by significantly reducing the variance of gradient estimates.
- Moment Matching for MKF/@KF: For Gaussian approximations, matching moments (mean and covariance) is a direct consequence of minimizing reverse KL or α-divergence, providing an efficient single-iteration approach.
- Adaptive Sampling for Efficiency: Dynamically adjusting the number of samples based on the estimated uncertainty of the posterior approximation can significantly reduce computational cost without sacrificing accuracy.
Key Results
- Improved Accuracy: The proposed SKF, MKF, and αKF algorithms consistently outperformed the EKF and UKF in terms of Mean Squared Error (MSE) across radar and sensor tracking tasks, especially under conditions of high nonlinearity and parameter uncertainty.
- Robustness: The αKF, in particular, showed high robustness to parameter changes and noisy measurements, making it a strong candidate for real-world applications where these factors are prevalent.
- Competitive Performance with Particle Filters: While particle filters (PF) sometimes achieved comparable or slightly better results when parameters were known, the proposed methods (especially MKF and αKF) offered similar or better performance with significantly lower computational cost due to the absence of resampling.
- Options Pricing: The algorithms also showed improved performance in options pricing, with MKF and αKF demonstrating better prediction accuracy than EKF and UKF.
- SKF Sensitivity: The SKF algorithm, while effective, was observed to be more sensitive to parameter changes and covariance initializations compared to MKF and αKF.
Limitations and Future Work
- Gaussian Approximation: The proposed methods still rely on approximating the posterior with a Gaussian distribution. While this is a common and often effective assumption, it may not be sufficient for highly multimodal or non-Gaussian posteriors.
- Computational Cost of SKF: While SKF offers direct optimization, its iterative nature and the need for a potentially large number of particles per iteration can make it computationally more expensive than MKF and αKF.
- Parameter Tuning for αKF: While the α-divergence offers flexibility, finding the optimal value of α might require some tuning, although the paper suggests that fractional values often perform well.
- Future Work: The authors suggest that the techniques presented could be extended to nonlinear state-space models with nonlinearities in both the state transition and measurement functions. Further exploration of adaptive sampling strategies and the application of these methods to other domains are also potential future directions.
Summary updated