论文标题
顺序蒙特卡洛的分层和最佳重采样
Stratification and Optimal Resampling for Sequential Monte Carlo
论文作者
论文摘要
顺序蒙特卡洛（SMC），也称为粒子过滤器，已被广泛接受为一种强大的计算工具，用于推理动态系统。 SMC的关键步骤是重新采样，它扮演着将算法转向未来动态的角色。已经提出并在实践中使用了几种策略，包括多项式重采样，残留重采样（Liu and Chen 1998），最佳重新采样（Fearnhead和Clifford 2003），分层重采样（Kitagawa 1996）和最佳运输重新采样（Reich 2013）。我们表明，在一维情况下，最佳转运重新采样等于对排序的粒子进行重新采样，并且它们都可以最大程度地减少重采样方差以及原始和重新采样的经验分布之间的预期平方距离。在多维情况下，使用希尔伯特曲线对粒子进行排序（Gerber etal。2019）的分类重新采样差异（以$ \ MATHBB {r}^d $为$ O（m^{ - （1+2/d）}）$，与原始$ O（M^is $ res $ res $ s）相比，是一个提高的率颗粒。这种提高的速率是Gerber等人猜想的有序分层重采样方案的最低速率。 （2019）。我们还对原始和希尔伯特 - 曲线曲折的经验分布之间的瓦斯汀距离几乎肯定。鉴于这些理论结果，我们提出了分层的多种渗透生长（SMG）算法，该算法使我们能够与标准I.I.D相比更有效地探索样品空间。由Wasserstein度量测量的多种降低采样方法。提供数值证据以证明我们提出的方法的有效性。
Sequential Monte Carlo (SMC), also known as particle filters, has been widely accepted as a powerful computational tool for making inference with dynamical systems. A key step in SMC is resampling, which plays the role of steering the algorithm towards the future dynamics. Several strategies have been proposed and used in practice, including multinomial resampling, residual resampling (Liu and Chen 1998), optimal resampling (Fearnhead and Clifford 2003), stratified resampling (Kitagawa 1996), and optimal transport resampling (Reich 2013). We show that, in the one dimensional case, optimal transport resampling is equivalent to stratified resampling on the sorted particles, and they both minimize the resampling variance as well as the expected squared energy distance between the original and resampled empirical distributions; in the multidimensional case, the variance of stratified resampling after sorting particles using Hilbert curve (Gerber et al. 2019) in $\mathbb{R}^d$ is $O(m^{-(1+2/d)})$, an improved rate compared to the original $O(m^{-(1+1/d)})$, where $m$ is the number of resampled particles. This improved rate is the lowest for ordered stratified resampling schemes, as conjectured in Gerber et al. (2019). We also present an almost sure bound on the Wasserstein distance between the original and Hilbert-curve-resampled empirical distributions. In light of these theoretical results, we propose the stratified multiple-descendant growth (SMG) algorithm, which allows us to explore the sample space more efficiently compared to the standard i.i.d. multiple-descendant sampling-resampling approach as measured by the Wasserstein metric. Numerical evidence is provided to demonstrate the effectiveness of our proposed method.
