粒子滤波（Particle Filter）

1.粒子滤波是动态系统非线性非高斯的情况

2.粒子滤波无法像卡尔曼滤波求得解析解，需要用蒙特卡洛采样

3.采取重要性采样方法近似计算也无法直接求解粒子滤波问题

4.序列重要性采样得到t时刻与t-1时刻样本权重的递推公式，可以求解粒子滤波5.SIS 算法会出现权值退化问题，利用重采样与生成测试方法解决，得到SIR算法

线性动态系统 线性动态系统LDS（别名:卡尔曼滤波）是在线性高斯情况下可以求得解析解。但如果模型是非线性非高斯情况，就无法求得解析解。此时需要用到蒙特卡洛采用方法，我们对这类模型称为粒子滤波，英文是Particle Filter。

粒子滤波关心的也是滤波问题：

由于是非线性非高斯，所以无法直接求得解析解，我们需要利用蒙特卡洛采样方法进行求解。

粒子滤波的概率图模型依然与HMM表示一致，只不过隐状态是连续的，观测变量不再是线性与服从高斯分布。它也满足齐次马尔科夫假设和观测独立假设。

从重要性采样到SIS

在MCMC系列中，我们介绍过蒙特卡洛采样的方法。对于粒子滤波，采用的是重要性采样方法

传送门：MCMC（蒙特卡洛采样）

把滤波问题代入上式，得到每个时刻样本的权重：

可以看到，每一个时刻t都要进行N次采样，且分子也十分难求。天才数学家找到了一个关于权重的递推公式，大大提高了计算效率。这个就是序列重要性采样（SIS）

• 序列重要性采样（SIS）
  

序列重要性采样，英文是Sequential Importance Sampling，简称SIS。它的核心思想是找到相邻时刻权重的递推公式：

该算法并不是直接对滤波问题进行求解，而是

对于分子条件概率：

我们找到了t时刻与t-1时刻的递推关系。

对于分母部分，由于是提议分布，我们可以取（假定）：

于是样本权重为：

这样，我们就得到了递推公式。算法流程为：

从SIS到SIR

SIS 算法会出现权值退化的情况，在一定时间后，可能会出现大部分权重都逼近0的情况

这是由于空间维度越来越高，需要的样本也越来越多。

要解决这个问题，一般有两种方法：

• resample，即重采样

• 选择合适的提议分布q(z)
  

重采样是以权重作为概率分布，重新在已经采样的样本中采样，然后所有样本的权重相同，这个方法的思路是将权重作为概率分布，然后得到累积密度函数，在累积密度上取点（阶梯函数）。

举一个例子，假设在t时刻采样得到3个样本点x1~x3，它们的权重是0.1,0.1,0.8：

计算它们的累积密度函数(cdf)：

然后取均匀分布u~U(0,1)，生成N个随机数，每个随机数对应取样本值：

这个就是重采样方法，本质是把重要性采样的样本作为一个离散分布重新进行采样。这种方法的SIS算法就是基本的粒子滤波算法（Basic Particle Filter），每一个样本就是一个粒子。

如果提议分布选择状态转移概率：

那么权重递推公式可以化简为：

这个叫做生成与测试方法。

我们把SIS、重采样与测试生成方法结合在一起，就是SIR算法（Sampling-Importance-Resampling），算法流程为：