American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Mean field limit of Ensemble Square Root filters - discrete and continuous time
  • FoDS Home
  • This Issue
  • Next Article
    A study of disproportionately affected populations by race/ethnicity during the SARS-CoV-2 pandemic using multi-population SEIR modeling and ensemble data assimilation
September  2021, 3(3): 543-561. doi: 10.3934/fods.2021018

Feedback particle filter for collective inference

Jin-Won Kim 1, , Amirhossein Taghvaei 2, , Yongxin Chen 3, and  Prashant G. Mehta 1,,

1. 

Coordinated Science Laboratory, University of Illinois, Urbana-Champaign, 1308 W. Main St., Urbana, IL 61801, USA
2. 

Department of Mechanical and Aerospace Engineering, University of California, Irvine, 4100 Calit2 Building, Irvine, CA 92697-2800, USA
3. 

School of Aerospace Engineering, Georgia Institute of Technology, Guggenheim 448B, Atlanta, GA 30332, USA

* Corresponding author: Prashant G. Mehta

Received  February 2021 Revised  June 2021 Published  September 2021 Early access  August 2021

Fund Project: Kim and Mehta are supported in part by the C3.ai Digital Transformation Institute sponsored by C3.ai Inc. and the Microsoft Corporation, and in part by the National Science Foundation grant NSF 1761622. Chen is supported by the NSF 2008513

The purpose of this paper is to describe the feedback particle filter algorithm for problems where there are a large number ($ M $) of non-interacting agents (targets) with a large number ($ M $) of non-agent specific observations (measurements) that originate from these agents. In its basic form, the problem is characterized by data association uncertainty whereby the association between the observations and agents must be deduced in addition to the agent state. In this paper, the large-$ M $ limit is interpreted as a problem of collective inference. This viewpoint is used to derive the equation for the empirical distribution of the hidden agent states. A feedback particle filter (FPF) algorithm for this problem is presented and illustrated via numerical simulations. Results are presented for the Euclidean and the finite state-space cases, both in continuous-time settings. The classical FPF algorithm is shown to be the special case (with $ M = 1 $) of these more general results. The simulations help show that the algorithm well approximates the empirical distribution of the hidden states for large $ M $.

Keywords: Feedback particle filter, ensemble Kalman filter, collective inference, data association, collective filtering.
Mathematics Subject Classification: Primary: 60G35, 62M20; Secondary: 94A12.
Citation: Jin-Won Kim, Amirhossein Taghvaei, Yongxin Chen, Prashant G. Mehta. Feedback particle filter for collective inference. Foundations of Data Science, 2021, 3 (3) : 543-561. doi: 10.3934/fods.2021018
References:
[1]

A. Bain and D. Crisan, Fundamentals of Stochastic Filtering, Stochastic Modelling and Applied Probability, 60, Springer, New York, 2009. doi: 10.1007/978-0-387-76896-0.  Google Scholar

[2]

D. Bakry, F. Barthe, P. Cattiaux and A. Guillin, A simple proof of the Poincaré inequality for a large class of probability measures including the log-concave case, Electron. Commun. Probab., 13 (2008), 60-66.  doi: 10.1214/ECP.v13-1352.  Google Scholar

[3]

Y. Bar-Shalom, F. Daum and J. Huang, The probabilistic data association filter: Estimation in the presence of measurement origin uncertainty, IEEE Control Syst. Mag., 29 (2009), 82-100.  doi: 10.1109/MCS.2009.934469.  Google Scholar

[4] Y. Bar-Shalom and T. E. Fortmann, Tracking and Data Association, Mathematics in Science and Engineering, 179, Academic Press, Inc., San Diego, CA, 1988.   Google Scholar
[5]

K. Bergemann and S. Reich, An ensemble Kalman-Bucy filter for continuous data assimilation, Meteorol. Z., 21 (2012), 213-219.  doi: 10.1127/0941-2948/2012/0307.  Google Scholar

[6]

Y. Chen, T. T. Georgiou and M. Pavon, On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint, J. Optim. Theory Appl., 169 (2016), 671-691.  doi: 10.1007/s10957-015-0803-z.  Google Scholar

[7]

Y. Chen and J. Karlsson, State tracking of linear ensembles via optimal mass transport, IEEE Control Syst. Lett., 2 (2018), 260-265.  doi: 10.1109/LCSYS.2018.2827001.  Google Scholar

[8]

T. Kirubarajan and Y. Bar-Shalom, Probabilistic data association techniques for target tracking in clutter, Proc. IEEE, 92 (2004), 536-557.  doi: 10.1109/JPROC.2003.823149.  Google Scholar

[9]

I. Kyriakides, D. Morrell and A. Papandreou-Suppappola, Sequential Monte Carlo methods for tracking multiple targets with deterministic and stochastic constraints, IEEE Trans. Signal Process., 56 (2008), 937-948.  doi: 10.1109/TSP.2007.908931.  Google Scholar

[10]

R. S. Laugesen, P. G. Mehta, S. P. Meyn and M. Raginsky, Poisson's equation in nonlinear filtering, SIAM J. Control Optim., 53 (2015), 501-525.  doi: 10.1137/13094743X.  Google Scholar

[11]

S. Pathiraja, S. Reich and W. Stannat, McKean-Vlasov sdes in nonlinear filtering, preprint, arXiv: 2007.12658. Google Scholar

[12]

S. Reich, A dynamical systems framework for intermittent data assimilation, BIT, 51 (2011), 235-249.  doi: 10.1007/s10543-010-0302-4.  Google Scholar

[13] S. Reich and C. Cotter, Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, New York, 2015.  doi: 10.1017/CBO9781107706804.  Google Scholar
[14]

D. Reid, An algorithm for tracking multiple targets, IEEE Trans. Automat. Control, 24 (1979), 843-854.  doi: 10.1109/TAC.1979.1102177.  Google Scholar

[15]

D. Sheldon, T. Sun, A. Kumar and T. Dietterich, Approximate inference in collective graphical models, Proceedings of the 30th International Conference on Machine Learning, 28 (2013), 1004–1012. Available from: http://proceedings.mlr.press/v28/sheldon13.pdf. Google Scholar

[16]

D. R. Sheldon and T. G. Dietterich, Collective graphical models, in Advances in Neural Information Processing Systems, NIPS, 2011, 1161–1169. Available from: https://papers.nips.cc/paper/2011/file/fccb3cdc9acc14a6e70a12f74560c026-Paper.pdf. Google Scholar

[17]

R. Singh, I. Haasler, Q. Zhang, J. Karlsson and Y. Chen, Inference with aggregate data: An optimal transport approach, preprint, arXiv: 2003.13933. Google Scholar

[18]

S. C. Surace, A. Kutschireiter and J.-P. Pfister, How to avoid the curse of dimensionality: Scalability of particle filters with and without importance weights, SIAM Rev., 61 (2019), 79-91.  doi: 10.1137/17M1125340.  Google Scholar

[19]

A. Taghvaei and P. G. Mehta, An optimal transport formulation of the ensemble Kalman filter, IEEE Trans. Automat. Control, 66 (2021), 3052-3067.  doi: 10.1109/TAC.2020.3015410.  Google Scholar

[20]

S. Thrun, Probabilistic robotics, Communications of the ACM, 45 (2002), 52-57.  doi: 10.1145/504729.504754.  Google Scholar

[21]

T. Yang, R. S. Laugesen, P. G. Mehta and S. P. Meyn, Multivariable feedback particle filter, Automatica J. IFAC, 71 (2016), 10-23.  doi: 10.1016/j.automatica.2016.04.019.  Google Scholar

[22]

T. Yang and P. G. Mehta, Probabilistic data association - Feedback particle filter for multiple target tracking applications, J. Dyn. Sys. Meas. Control, 140 (2018), 14pp. doi: 10.1115/1.4037781.  Google Scholar

[23]

T. Yang, P. G. Mehta and S. P. Meyn, Feedback particle filter for a continuous-time Markov chain, IEEE Trans. Automat. Control, 61 (2016), 556-561.  doi: 10.1109/TAC.2015.2444171.  Google Scholar

show all references

References:
[1]

A. Bain and D. Crisan, Fundamentals of Stochastic Filtering, Stochastic Modelling and Applied Probability, 60, Springer, New York, 2009. doi: 10.1007/978-0-387-76896-0.  Google Scholar

[2]

D. Bakry, F. Barthe, P. Cattiaux and A. Guillin, A simple proof of the Poincaré inequality for a large class of probability measures including the log-concave case, Electron. Commun. Probab., 13 (2008), 60-66.  doi: 10.1214/ECP.v13-1352.  Google Scholar

[3]

Y. Bar-Shalom, F. Daum and J. Huang, The probabilistic data association filter: Estimation in the presence of measurement origin uncertainty, IEEE Control Syst. Mag., 29 (2009), 82-100.  doi: 10.1109/MCS.2009.934469.  Google Scholar

[4] Y. Bar-Shalom and T. E. Fortmann, Tracking and Data Association, Mathematics in Science and Engineering, 179, Academic Press, Inc., San Diego, CA, 1988.   Google Scholar
[5]

K. Bergemann and S. Reich, An ensemble Kalman-Bucy filter for continuous data assimilation, Meteorol. Z., 21 (2012), 213-219.  doi: 10.1127/0941-2948/2012/0307.  Google Scholar

[6]

Y. Chen, T. T. Georgiou and M. Pavon, On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint, J. Optim. Theory Appl., 169 (2016), 671-691.  doi: 10.1007/s10957-015-0803-z.  Google Scholar

[7]

Y. Chen and J. Karlsson, State tracking of linear ensembles via optimal mass transport, IEEE Control Syst. Lett., 2 (2018), 260-265.  doi: 10.1109/LCSYS.2018.2827001.  Google Scholar

[8]

T. Kirubarajan and Y. Bar-Shalom, Probabilistic data association techniques for target tracking in clutter, Proc. IEEE, 92 (2004), 536-557.  doi: 10.1109/JPROC.2003.823149.  Google Scholar

[9]

I. Kyriakides, D. Morrell and A. Papandreou-Suppappola, Sequential Monte Carlo methods for tracking multiple targets with deterministic and stochastic constraints, IEEE Trans. Signal Process., 56 (2008), 937-948.  doi: 10.1109/TSP.2007.908931.  Google Scholar

[10]

R. S. Laugesen, P. G. Mehta, S. P. Meyn and M. Raginsky, Poisson's equation in nonlinear filtering, SIAM J. Control Optim., 53 (2015), 501-525.  doi: 10.1137/13094743X.  Google Scholar

[11]

S. Pathiraja, S. Reich and W. Stannat, McKean-Vlasov sdes in nonlinear filtering, preprint, arXiv: 2007.12658. Google Scholar

[12]

S. Reich, A dynamical systems framework for intermittent data assimilation, BIT, 51 (2011), 235-249.  doi: 10.1007/s10543-010-0302-4.  Google Scholar

[13] S. Reich and C. Cotter, Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, New York, 2015.  doi: 10.1017/CBO9781107706804.  Google Scholar
[14]

D. Reid, An algorithm for tracking multiple targets, IEEE Trans. Automat. Control, 24 (1979), 843-854.  doi: 10.1109/TAC.1979.1102177.  Google Scholar

[15]

D. Sheldon, T. Sun, A. Kumar and T. Dietterich, Approximate inference in collective graphical models, Proceedings of the 30th International Conference on Machine Learning, 28 (2013), 1004–1012. Available from: http://proceedings.mlr.press/v28/sheldon13.pdf. Google Scholar

[16]

D. R. Sheldon and T. G. Dietterich, Collective graphical models, in Advances in Neural Information Processing Systems, NIPS, 2011, 1161–1169. Available from: https://papers.nips.cc/paper/2011/file/fccb3cdc9acc14a6e70a12f74560c026-Paper.pdf. Google Scholar

[17]

R. Singh, I. Haasler, Q. Zhang, J. Karlsson and Y. Chen, Inference with aggregate data: An optimal transport approach, preprint, arXiv: 2003.13933. Google Scholar

[18]

S. C. Surace, A. Kutschireiter and J.-P. Pfister, How to avoid the curse of dimensionality: Scalability of particle filters with and without importance weights, SIAM Rev., 61 (2019), 79-91.  doi: 10.1137/17M1125340.  Google Scholar

[19]

A. Taghvaei and P. G. Mehta, An optimal transport formulation of the ensemble Kalman filter, IEEE Trans. Automat. Control, 66 (2021), 3052-3067.  doi: 10.1109/TAC.2020.3015410.  Google Scholar

[20]

S. Thrun, Probabilistic robotics, Communications of the ACM, 45 (2002), 52-57.  doi: 10.1145/504729.504754.  Google Scholar

[21]

T. Yang, R. S. Laugesen, P. G. Mehta and S. P. Meyn, Multivariable feedback particle filter, Automatica J. IFAC, 71 (2016), 10-23.  doi: 10.1016/j.automatica.2016.04.019.  Google Scholar

[22]

T. Yang and P. G. Mehta, Probabilistic data association - Feedback particle filter for multiple target tracking applications, J. Dyn. Sys. Meas. Control, 140 (2018), 14pp. doi: 10.1115/1.4037781.  Google Scholar

[23]

T. Yang, P. G. Mehta and S. P. Meyn, Feedback particle filter for a continuous-time Markov chain, IEEE Trans. Automat. Control, 61 (2016), 556-561.  doi: 10.1109/TAC.2015.2444171.  Google Scholar

Figure 1.  Normalized error for mean (blue circle) and variance (orange circle) with the KF and CKF algorithms. The KF algorithms were run as $ M $ independent Kalman filters with fully known data associations
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Normalized error for mean (blue circle) and variance (orange circle) with the CKF and FPF algorithms. The number of agents is fixed to $ M = 30 $ for this simulation
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Junyoung Jang, Kihoon Jang, Hee-Dae Kwon, Jeehyun Lee. Feedback control of an HBV model based on ensemble kalman filter and differential evolution. Mathematical Biosciences & Engineering, 2018, 15 (3) : 667-691. doi: 10.3934/mbe.2018030
[2]

Andreas Bock, Colin J. Cotter. Learning landmark geodesics using the ensemble Kalman filter. Foundations of Data Science, 2021, 3 (4) : 701-727. doi: 10.3934/fods.2021020
[3]

Xin Li, Feng Bao, Kyle Gallivan. A drift homotopy implicit particle filter method for nonlinear filtering problems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021097
[4]

Sahani Pathiraja, Wilhelm Stannat. Analysis of the feedback particle filter with diffusion map based approximation of the gain. Foundations of Data Science, 2021, 3 (3) : 615-645. doi: 10.3934/fods.2021023
[5]

Alexander Bibov, Heikki Haario, Antti Solonen. Stabilized BFGS approximate Kalman filter. Inverse Problems & Imaging, 2015, 9 (4) : 1003-1024. doi: 10.3934/ipi.2015.9.1003
[6]

Russell Johnson, Carmen Núñez. The Kalman-Bucy filter revisited. Discrete & Continuous Dynamical Systems, 2014, 34 (10) : 4139-4153. doi: 10.3934/dcds.2014.34.4139
[7]

Sebastian Reich, Seoleun Shin. On the consistency of ensemble transform filter formulations. Journal of Computational Dynamics, 2014, 1 (1) : 177-189. doi: 10.3934/jcd.2014.1.177
[8]

Seung-Yeal Ha, Myeongju Kang, Bora Moon. Collective behaviors of a Winfree ensemble on an infinite cylinder. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2749-2779. doi: 10.3934/dcdsb.2020204
[9]

Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337
[10]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017
[11]

Z. G. Feng, Kok Lay Teo, N. U. Ahmed, Yulin Zhao, W. Y. Yan. Optimal fusion of sensor data for Kalman filtering. Discrete & Continuous Dynamical Systems, 2006, 14 (3) : 483-503. doi: 10.3934/dcds.2006.14.483
[12]

Andrea Arnold, Daniela Calvetti, Erkki Somersalo. Vectorized and parallel particle filter SMC parameter estimation for stiff ODEs. Conference Publications, 2015, 2015 (special) : 75-84. doi: 10.3934/proc.2015.0075
[13]

Jiangqi Wu, Linjie Wen, Jinglai Li. Resampled ensemble Kalman inversion for Bayesian parameter estimation with sequential data. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021045
[14]

Qifeng Cheng, Xue Han, Tingting Zhao, V S Sarma Yadavalli. Improved particle swarm optimization and neighborhood field optimization by introducing the re-sampling step of particle filter. Journal of Industrial & Management Optimization, 2019, 15 (1) : 177-198. doi: 10.3934/jimo.2018038
[15]

Mojtaba F. Fathi, Ahmadreza Baghaie, Ali Bakhshinejad, Raphael H. Sacho, Roshan M. D'Souza. Time-resolved denoising using model order reduction, dynamic mode decomposition, and kalman filter and smoother. Journal of Computational Dynamics, 2020, 7 (2) : 469-487. doi: 10.3934/jcd.2020019
[16]

Wawan Hafid Syaifudin, Endah R. M. Putri. The application of model predictive control on stock portfolio optimization with prediction based on Geometric Brownian Motion-Kalman Filter. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021119
[17]

Roman Czapla, Vladimir V. Mityushev. A criterion of collective behavior of bacteria. Mathematical Biosciences & Engineering, 2017, 14 (1) : 277-287. doi: 10.3934/mbe.2017018
[18]

Deborah C. Markham, Ruth E. Baker, Philip K. Maini. Modelling collective cell behaviour. Discrete & Continuous Dynamical Systems, 2014, 34 (12) : 5123-5133. doi: 10.3934/dcds.2014.34.5123
[19]

Gabrielle Demange. Collective attention and ranking methods. Journal of Dynamics & Games, 2014, 1 (1) : 17-43. doi: 10.3934/jdg.2014.1.17
[20]

Laura Martín-Fernández, Gianni Gilioli, Ettore Lanzarone, Joaquín Míguez, Sara Pasquali, Fabrizio Ruggeri, Diego P. Ruiz. A Rao-Blackwellized particle filter for joint parameter estimation and biomass tracking in a stochastic predator-prey system. Mathematical Biosciences & Engineering, 2014, 11 (3) : 573-597. doi: 10.3934/mbe.2014.11.573

 Impact Factor: 

Tools

Metrics

  • PDF downloads (82)
  • HTML views (232)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy