The Living Thing / Notebooks : State filtering and data assimilation, a.k.a. Kalman and friends

Kalman filter and cousins, recursive estimation, predictive state models, Data assimilation. A particular sub-field of signal processing for models with hidden state.

In statistics terms, the state filters are a kind of online-updating hierarchical model for sequential observations of a dynamical system where the random state is unobserved, but you can get an optimal estimate of it based on incoming measurements and known parameters.

A unifying feature of all these is by assuming a sparse influence graph between observations and dynamics, that you can estimate behaviour using effiicent message passing.

Awaiting filing

Recently enjoyed: Sahani Pathiraja’s state filter does something cool, in attempting to identify process model noise - a conditional nonparametric density of process errors, that may be used to come up with some neat process models. I’m not convinced about her use of kernel density estimators, since these scale badly precisely when you need them most, in high dimension; but any nonparametric density estimator would, I assume, work.

Linear systems

In Kalman filters per se you are usually concerned with multivariate real vector signals representing different axes of some telemetry data problem.

The classic Kalman filter (Kalm60) assumes a linear model with Gaussian noise, although it might work with not-quite Gaussian, not-quite linear models if you prod it. You can extend this flavour to somewhat more general dynamics.

If you are doing telemetry then you probably know a prori that your model is not linear in this case, and extensions are advisable.

Non-linear dynamical systems

Cute exercise: you can derive the analytic Kalman filter for any noise and process dynamics of with Bayesian conjugate, and this leads to filters of nonlinear behaviour. Multivariate distributions are a bit of a mess for non-Gaussians, though, and a beta-Kalman filter feels contrived.

Upshot is, the non-linear extensions don’t usually rely on non-Gaussian conjugate distributions and anlytic forms, but rather do some Gaussian/linear approximation, or use randomised methods such as particle filters.

Discrete state Hidden Markov models

TBD. Viterbi algorithm.

Other interesting state filters

TODO: learn if the “Predictive state representation” of WoJS05 and SiJR04 is in fact a state filter? Looks similar to something I’ve derived… Or is this better classified as state space reconstruction?

Note that state filters can also do approximate gaussian process regresssion, apparently.

State filter inference

How about learning the parameters of the model generating your states? See linear system identification, general system identification, .

Implementations

statmodels does state filtering.

Refs

AMGC02
Arulampalam, M. S., Maskell, S., Gordon, N., & Clapp, T. (2002) A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Transactions on Signal Processing, 50(2), 174–188. DOI.
BaSa13
Battey, H., & Sancetta, A. (2013) Conditional estimation for dependent functional data. Journal of Multivariate Analysis, 120, 1–17. DOI.
BrPK16
Brunton, S. L., Proctor, J. L., & Kutz, J. N.(2016) Discovering governing equations from data by sparse identification of nonlinear dynamical systems. Proceedings of the National Academy of Sciences, 113(15), 3932–3937. DOI.
Carm13
Carmi, A. Y.(2013) Compressive system identification: Sequential methods and entropy bounds. Digital Signal Processing, 23(3), 751–770. DOI.
Carm14
Carmi, A. Y.(2014) Compressive System Identification. In A. Y. Carmi, L. Mihaylova, & S. J. Godsill (Eds.), Compressed Sensing & Sparse Filtering (pp. 281–324). Springer Berlin Heidelberg
CaRS15
Cassidy, B., Rae, C., & Solo, V. (2015) Brain Activity: Connectivity, Sparsity, and Mutual Information. IEEE Transactions on Medical Imaging, 34(4), 846–860. DOI.
CaFe08
Cauchemez, S., & Ferguson, N. M.(2008) Likelihood-based estimation of continuous-time epidemic models from time-series data: application to measles transmission in London. Journal of The Royal Society Interface, 5(25), 885–897. DOI.
ChHo07
Chen, B., & Hong, Y. (2007) Testing for the Markov Property in Time Series.
ClBj04
Clark, J. S., & Bjørnstad, O. N.(2004) Population time series: process variability, observation errors, missing values, lags, and hidden states. Ecology, 85(11), 3140–3150. DOI.
DuKo97
Durbin, J., & Koopman, S. J.(1997) Monte Carlo maximum likelihood estimation for non-Gaussian state space models. Biometrika, 84(3), 669–684. DOI.
DuKo12
Durbin, J., & Koopman, S. J.(2012) Time series analysis by state space methods. (2nd ed.). Oxford: Oxford University Press
EFBS04
Eden, U., Frank, L., Barbieri, R., Solo, V., & Brown, E. (2004) Dynamic Analysis of Neural Encoding by Point Process Adaptive Filtering. Neural Computation, 16(5), 971–998. DOI.
Fras08
Fraser, A. M.(2008) Hidden Markov models and dynamical systems. . Philadelphia, PA: Society for Industrial and Applied Mathematics
GoJa15
Gourieroux, C., & Jasiak, J. (2015) Filtering, Prediction and Simulation Methods for Noncausal Processes. Journal of Time Series Analysis, n/a-n/a. DOI.
HaKo05
Harvey, A., & Koopman, S. J.(2005) Structural Time Series Models. In Encyclopedia of Biostatistics. John Wiley & Sons, Ltd
HaLu14
Harvey, A., & Luati, A. (2014) Filtering With Heavy Tails. Journal of the American Statistical Association, 109(507), 1112–1122. DOI.
HeDG15
Hefny, A., Downey, C., & Gordon, G. (2015) A New View of Predictive State Methods for Dynamical System Learning. arXiv:1505.05310 [Cs, Stat].
HMCH08
Hong, X., Mitchell, R. J., Chen, S., Harris, C. J., Li, K., & Irwin, G. W.(2008) Model selection approaches for non-linear system identification: a review. International Journal of Systems Science, 39(10), 925–946. DOI.
IBAK11
Ionides, E. L., Bhadra, A., Atchadé, Y., & King, A. (2011) Iterated filtering. The Annals of Statistics, 39(3), 1776–1802. DOI.
Kalm59
Kalman, R. (1959) On the general theory of control systems. IRE Transactions on Automatic Control, 4(3), 110–110. DOI.
Kalm60
Kalman, R. E.(1960) A New Approach to Linear Filtering and Prediction Problems. Journal of Basic Engineering, 82(1), 35. DOI.
KMBT11
Kalouptsidis, N., Mileounis, G., Babadi, B., & Tarokh, V. (2011) Adaptive algorithms for sparse system identification. Signal Processing, 91(8), 1910–1919. DOI.
Kita87
Kitagawa, G. (1987) Non-Gaussian State—Space Modeling of Nonstationary Time Series. Journal of the American Statistical Association, 82(400), 1032–1041. DOI.
Kita96
Kitagawa, G. (1996) Monte Carlo Filter and Smoother for Non-Gaussian Nonlinear State Space Models. Journal of Computational and Graphical Statistics, 5(1), 1–25. DOI.
KiGe96
Kitagawa, G., & Gersch, W. (1996) Smoothness Priors Analysis of Time Series. . New York, NY: Springer New York : Imprint : Springer
KoMT11
Kobayashi, H., Mark, B. L., & Turin, W. (2011) Probability, Random Processes, and Statistical Analysis: Applications to Communications, Signal Processing, Queueing Theory and Mathematical Finance. . Cambridge University Press
KoDu00
Koopman, S. J., & Durbin, J. (2000) Fast Filtering and Smoothing for Multivariate State Space Models. Journal of Time Series Analysis, 21(3), 281–296. DOI.
LeBS09
Lei, J., Bickel, P., & Snyder, C. (2009) Comparison of Ensemble Kalman Filters under Non-Gaussianity. Monthly Weather Review, 138(4), 1293–1306. DOI.
Olfa05
Olfati-Saber, R. (2005) Distributed Kalman Filter with Embedded Consensus Filters. In 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC ’05 (pp. 8179–8184). DOI.
Robe11
Robertson, A. N.(2011) A Bayesian approach to drum tracking.
RoPl07
Robertson, A., & Plumbley, M. (2007) B-Keeper: A Beat-tracker for Live Performance. In Proceedings of the 7th International Conference on New Interfaces for Musical Expression (pp. 234–237). New York, NY, USA: ACM DOI.
RoSD13
Robertson, A., Stark, A., & Davies, M. E.(2013) Percussive Beat tracking using real-time median filtering. . Presented at the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases
RoSP11
Robertson, A., Stark, A. M., & Plumbley, M. D.(2011) Real-Time Visual Beat Tracking Using a Comb Filter Matrix.
RoRu09
Rodriguez, A., & Ruiz, E. (2009) Bootstrap prediction intervals in state–space models. Journal of Time Series Analysis, 30(2), 167–178. DOI.
RuSW05
Rudary, M., Singh, S., & Wingate, D. (2005) Predictive Linear-Gaussian Models of Stochastic Dynamical Systems. In arXiv:1207.1416 [cs].
Sark07
Sarkka, S. (2007) On Unscented Kalman Filtering for State Estimation of Continuous-Time Nonlinear Systems. IEEE Transactions on Automatic Control, 52(9), 1631–1641. DOI.
SiJR04
Singh, S., James, M. R., & Rudary, M. R.(2004) Predictive State Representations: A New Theory for Modeling Dynamical Systems. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (pp. 512–519). Arlington, Virginia, United States: AUAI Press
Sore70
Sorenson, H. W.(1970) Least-squares estimation: from Gauss to Kalman. IEEE Spectrum, 7(7), 63–68. DOI.
TaPa16
Tavakoli, S., & Panaretos, V. M.(2016) Detecting and Localizing Differences in Functional Time Series Dynamics: A Case Study in Molecular Biophysics. Journal of the American Statistical Association, 1–31. DOI.
WoJS05
Wolfe, B., James, M. R., & Singh, S. (2005) Learning Predictive State Representations in Dynamical Systems Without Reset. In Proceedings of the 22Nd International Conference on Machine Learning (pp. 980–987). New York, NY, USA: ACM DOI.