On parallel implementation of sequential Monte Carlo methods: the island particle model

详细信息    查看全文

• 作者：Christelle Vergé ; Cyrille Dubarry ; Pierre Del Moral…
• 关键词：Particle approximation of Feynman ; Kac flow ; Island models ; Parallel implementation
• 刊名：Statistics and Computing
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：25
• 期：2
• 页码：243-260
• 全文大小：809 KB
• 参考文献：1. Arnaud, E., Le Gland, F.: SMC with Adaptive Resampling: Large Sample Asymptotics, pp.?481-84 (2009)
  2. Cappé, O., Moulines, E.: On the use of particle filtering for maximum likelihood parameter estimation. In: European Signal Processing Conference (EUSIPCO), Antalya, Turkey (2005)
  3. Casarin, R., Grassi, S., Ravazzolo, F., Van Dijk, H.K.: Parallel sequential Monte Carlo for efficient density combination: the deco Matlab toolboox. Tinbergen Institute Discussion Paper, 055/III (2013)
  4. Chopin, N.: A sequential particle filter method for static models. Biometrika 89, 539-52 (2002) CrossRef
  5. Chopin, N., Jacob, P., Papaspiliopoulos, O.: SMC²: a sequential Monte Carlo algorithm with particle Markov chain Monte Carlo updates. J. R. Stat. Soc. B. 75(3), 397-26 (2013). doi:10.1111/j.1467-9868.2012.01046.x CrossRef
  6. Del Moral, P.: Feynman-Kac Formulae. Genealogical and Interacting Particle Systems with Applications. Springer, Berlin (2004) CrossRef
  7. Del Moral, P., Doucet, A., Jasra, A.: On adaptive resampling strategies for sequential Monte Carlo methods. Bernoulli 18(1), 252-78 (2012a) CrossRef
  8. Del Moral, P., Hu, P., Wu, L.: On the concentration properties of interacting particle processes. Found. Trends Mach. Learn. 3(3-), 225-89 (2012b)
  9. Douc, R., Moulines, E.: Limit theorems for weighted samples with applications to sequential Monte Carlo methods. Ann. Stat. 36(5), 2344-376 (2008) CrossRef
  10. Doucet, A., Freitas, N.D. (eds.): Sequential Monte Carlo Methods in Practice. Springer, New York (2001)
  11. Durham, G., Geweke, J.: Massively parallel sequential Monte Carlo for Bayesian inference. Manuscript, URL http://www.censoc.uts.edu.au/pdfs/geweke_papers/gp_working_9.pdf (2011)
  12. Jasra, A., Doucet, A., Stephens, D.A., Holmes, C.C.: Interacting sequential Monte Carlo samplers for trans-dimensional simulation. Comput. Stat. Data Anal. 52, 1765-791 (2008) CrossRef
  13. Liu, J.S.: Monte Carlo Strategies in Scientific Computing. Springer, New York (2001)
  14. Liu, J., Chen, R.: Blind deconvolution via sequential imputations. J.?Am. Stat. Assoc. 90(420), 567-76 (1995) CrossRef
  
• 作者单位：Christelle Vergé (4) (5) (6)
  Cyrille Dubarry (2)
  Pierre Del Moral (1)
  Eric Moulines (3)
  
  4. ONERA, The French Aerospace Lab, 91761, Palaiseau, France
  5. CNES, 18 avenue Edouard Belin, 31401, Toulouse Cedex 9, France
  6. CMAP, Ecole Polytechnique, 91128, Palaiseau Cedex, France
  2. SAMOVAR, CNRS UMR 5157, Institut Télécom/Télécom SudParis, 9 rue Charles Fourier, 91000, Evry, France
  1. Centre INRIA Bordeaux Sud Ouest, 351 Cours de la Libération, 33405, Talence Cedex, France
  3. LTCI, CNRS UMR 8151, Institut Télécom/Télécom ParisTech, 46 rue Barrault, 75634, Paris Cedex 13, France
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Statistics
  Statistics Computing and Software
  Statistics
  Numeric Computing
  Mathematics
  Artificial Intelligence and Robotics
  
• 出版者：Springer Netherlands
• ISSN：1573-1375

文摘

The approximation of the Feynman-Kac semigroups by systems of interacting particles is a very active research field, with applications in many different areas. In this paper, we study the parallelization of such approximations. The total population of particles is divided into sub-populations, referred to as islands. The particles within each island follow the usual selection/mutation dynamics. We show that the evolution of each island is also driven by a Feynman-Kac semigroup, whose transition and potential can be explicitly related to ones of the original problem. Therefore, the same genetic type approximation of the Feynman-Kac semi-group may be used at the island level; each island might undergo selection/mutation algorithm. We investigate the impact of the population size within each island and the number of islands, and study different type of interactions. We find conditions under which introducing interactions between islands is beneficial. The theoretical results are supported by some Monte Carlo experiments.