Article Contents
Article Contents

# Feedback particle filter for collective inference

• * Corresponding author: Prashant G. Mehta
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$.

Mathematics Subject Classification: Primary: 60G35, 62M20; Secondary: 94A12.

 Citation:

• 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 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

•  [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [11] S. Pathiraja, S. Reich and W. Stannat, McKean-Vlasov sdes in nonlinear filtering, preprint, arXiv: 2007.12658. [12] S. Reich, A dynamical systems framework for intermittent data assimilation, BIT, 51 (2011), 235-249.  doi: 10.1007/s10543-010-0302-4. [13] S. Reich and  C. Cotter,  Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, New York, 2015.  doi: 10.1017/CBO9781107706804. [14] D. Reid, An algorithm for tracking multiple targets, IEEE Trans. Automat. Control, 24 (1979), 843-854.  doi: 10.1109/TAC.1979.1102177. [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. [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. [17] R. Singh, I. Haasler, Q. Zhang, J. Karlsson and Y. Chen, Inference with aggregate data: An optimal transport approach, preprint, arXiv: 2003.13933. [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. [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. [20] S. Thrun, Probabilistic robotics, Communications of the ACM, 45 (2002), 52-57.  doi: 10.1145/504729.504754. [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. [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. [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.

Figures(2)