对于没有线性高斯分布的动态系统，例如使用非高斯发射概率密度的动态系统，为了得到一个可以计算的推断算法，我们使用采样算法。特别地，我们可以使用11.1.5节讨论的采样-重要性-在采样方法，得到一个顺序的蒙特卡罗算法，被称为粒子滤波。

考虑图13.5中的图模型表示的概率分布，假设我们有观测变量$X_n =(x_1,...,x_n)$，我们希望从后验概率分布$p(z_n|X_n)$中抽取$L$个样本。使用贝叶斯定理，我们有

$$\begin{eqnarray} \mathbb{E}[f(z_n)] &=& \int f(z_n)p(z_n|X_n)dz_n \\ &=& \int f(z_n)p(z_n|x_n,X_{n-1})dz_n \\ &=& \frac{\int f(z_n)p(x_n|z_n)p(z_n|X_{n-1})dz_n}{\int p(x_n|z_n)p(z_n|X_{n-1})dz_n} \\ &\simeq& \sum\limits_{l=1}^Lw_n^{(l)}f(z_n^{(l)}) \tag{13.117} \end{eqnarray}$$

其中$\{z_n^{(l)}\}$是从$p(z_n|X_n)$中抽取的一组样本，并且我们使用了条件独立性质$p(x_n|z_n,X_{n-1}) = p(x_n|z_n)$，这个性质来自于图13.5所示的图模型。采样权值$\{w_n^{(l)}\}$的定义 为

$$w_n^{(l)} = \frac{p(x_n|z_n^{(l)})}{\sum\limits_{m=1}^Lp(x_n|z_n^{(m)})} \tag{13.118}$$

其中我们在分子和分母中使用了同样的样本。因此后验概率分布$p(z_n|X_n)$由样本集合$\{z_n^{(l)}\}$以及对应的权值$\{w_n^{(l)}\}$表示。注意，权值一定满足$0 \leq w_n^{(l)} \leq 1$以及$\sum_l w_n^{(l)} = 1$。

由于我们希望找到一个顺序采样的方法，因此我们假设我们在时刻$n$已经得到了一组样本和权值，并且我们顺序地观测到了$x_{n+1}$的值，我们希望找到时刻$n + 1$的权值和样本。我们首先从概率分布$p(z_{n+1}|X_n)$中采样。这很容易做到，因为使用贝叶斯定义，我们有

$$\begin{eqnarray} p(z_{n+1}|X_n) &=& \int p(z_{n+1}|z_n, X_n)p(z_n|X_n)dz_n \\ &=& \int p(z_{n+1}|z_n)p(z_n|X_n)dz_n \\ &=& \int p(z_{n+1}|z_n)p(z_n|x_n, X_{n−1})dz_n \\ &=& \frac{\int p(z_{n+1}|z_n)p(x_n|z_n)p(z_n|X_{n−1})dz_n}{p(x_n|z_n)p(z_n|X_{n−1})dz_n} \\ &\simeq& \sum\limits_lw_n^{(l)}p(z_{n+1}|z_n^{(l)}) \tag{13.119} \end{eqnarray}$$

其中我们使用了条件独立性质

$$\begin{eqnarray} p(z_{n+1}|z_n, X_n) &=& p(z_{n+1}|z_n) \tag{13.120} \\ p(x_n|z_n, X_{n−1}) &=& p(x_n|z_n) \tag{13.121} \end{eqnarray}$$

这可以通过对图13.5所示的图模型应用d-划分准则的方式得到。式(13.119)的概率分布是一个混合分布，样本可以通过下面的方式得到：根据混合系数$w^{(l)}$指定的概率，选择一个分量$l$， 然后从对应的分布中采样。

总结一下，我们可以将粒子滤波算法的每一步看成由两个阶段组成。在时刻$n$，我们有一个后验概率$p(z_n|X_n)$的样本表示，它根据$\{z_n^{(l)}\}$以及对应的权值$\{w_n^{(l)}\}$表示。这可以看成形如（13.119）的混合表示。为了得到下一个时刻的对应的表示，我们首先从混合分布（13.119）中抽取$L$个样本，然后对于每个样本，我们使用新的观测$x_{n+1}$计算对应的权值$w_{n+1}^{(l)} \propto p(x_{n+1}|z_{n+1}^{(l)})$。图13.23说明了单一变量$z$的情形。

图 13.22 对于一维潜在空间，粒子滤波操作的图形表示。在时刻$n$，后验概率分布$p(z_n|x_n)$被表示为混合概率分布，用圆圈表示，它的大小正比于权值$w_n^{(l)}$。之后，一组$L$个样本从这个概率分布中抽取，新的权值$w_{n+1}^{(l)}$使用$p(x_{n+1}| z_{n+1}^{(l)})$计算。

粒子滤波或者顺序蒙特卡罗方法在文献中有多个名字，包括自助滤波（bootstrap filter） （Gordon et al.， 1993）、最适幸存（survival of the fittest）（kanazawa et al.， 1995）以及凝结算法 （condensation algorithm）（Isard and Blake， 1998）。