机器学习笔记之粒子滤波(二)基于序列重要性采样的重采样

引言

上一节介绍了序列重要性采样处理的问题以及迭代过程的推导。本节针对序列重要性采样的问题，介绍基于序列重要性采样的重采样(Resampling)算法。

回顾：序列重要性采样

序列重要性采样(Sequential Importance Sampling)它是一种基于 动态模型假设 与 重要性采样 相结合的通过找到相邻时刻重要性权重 之间关联关系的一种迭代算法。

这种将蒙特卡洛方法 作为底层逻辑的算法，它并非对隐变量的后验概率分布$\mathcal{P}(\mathcal{I}\mid \mathcal{O})$直接求解，而是求解$\mathcal{P}(\mathcal{I}\mid \mathcal{O})$分布下的 期望结果${\mathbb{E}}_{\mathcal{I}\mid \mathcal{O}}[f(\mathcal{I})]$：
E I ∣ O [ f ( O ) ] = ∫ I P ( I ∣ O ) ⋅ f ( O ) d I ≈ 1 N ∑ k = 1 N f ( i ( k ) ) ( i ( 1 ) , ⋯   , i ( N ) ∼ P ( I ∣ O ) ) EI∣O[f(O)]=∫IP(I∣O)⋅f(O)dI≈1NN∑k=1f(i(k))(i(1),⋯,i(N)∼P(I∣O))

EI∣O​[f(O)]​=∫I​P(I∣O)⋅f(O)dI≈N1​k=1∑N​f(i(k))(i(1),⋯,i(N)∼P(I∣O))​
而重要性采样(Importance Sampling) 引入一个易于采样的简单分布$\mathcal{Q}(\mathcal{I})$，通过 采样结果$i^{(k)}$ 以及对应的 重要性权重${\mathcal{W}}^{(k)}$ 来求解期望结果${\mathbb{E}}_{\mathcal{I}\mid \mathcal{O}}[f(\mathcal{I})]$：
$$\begin{array}{rl}{\mathbb{E}}_{\mathcal{I}\mid \mathcal{O}}[f(\mathcal{I})]& ={\int }_{\mathcal{I}}\mathcal{Q}(\mathcal{I})\cdot \left[f(\mathcal{O})\cdot \frac{\mathcal{P}(\mathcal{I}\mid \mathcal{O})}{\mathcal{Q}(\mathcal{I})}\right]d\mathcal{I}\\ & ={\mathbb{E}}_{\mathcal{Q}(\mathcal{I})}\left[f(\mathcal{O})\cdot \frac{\mathcal{P}(\mathcal{I}\mid \mathcal{O})}{\mathcal{Q}(\mathcal{I})}\right]\\ & \approx \frac{1}{N}\sum _{k=1}^{N}f(i^{(k)})\cdot {\mathcal{W}}^{(k)}\{\begin{array}{l}{\mathcal{W}}^{(k)}=\frac{\mathcal{P}(i^{(k)})}{\mathcal{Q}(i^{(k)})}\\ i^{(1)},\cdots ,i^{(N)}\sim \mathcal{Q}(\mathcal{I})\end{array}\end{array}$$

但重要性采样在滤波问题中的缺陷在于：${\mathcal{W}}_t^{(k)}$在求解过程中计算量较大，从而导致整个算法的时间复杂度较高。
${\mathcal{W}}_t^{(k)}$表示$t$时刻第$k$次采样的重要性权重；相关描述详见序列重要性采样介绍

而序列重要性采样通过找出相邻时刻重要性权重的关联关系 来求解重要性权重，从而实现简化运算的目的：
该部分公式的解释同样详见序列重要性采样介绍。
W t = P ( i t ∣ o 1 : t ) Q ( i t ∣ o 1 : t ) ∝ P ( i 1 : t ∣ o 1 : t ) Q ( i 1 : t ∣ o 1 : t ) ∝ P ( o t ∣ i t ) ⋅ P ( i t ∣ i t − 1 ) Q ( i t ∣ i 1 : t − 1 , o 1 : t ) ⋅ W t − 1 Wt=P(it∣o1:t)Q(it∣o1:t)∝P(i1:t∣o1:t)Q(i1:t∣o1:t)∝P(ot∣it)⋅P(it∣it−1)Q(it∣i1:t−1,o1:t)⋅Wt−1

Wt​​=Q(it​∣o1:t​)P(it​∣o1:t​)​∝Q(i1:t​∣o1:t​)P(i1:t​∣o1:t​)​∝Q(it​∣i1:t−1​,o1:t​)P(ot​∣it​)⋅P(it​∣it−1​)​⋅Wt−1​​
以$t$时刻为例：

• 在算法实践过程中，只需要从分布$\mathcal{Q}$中采集$t$时刻的$N$个样本：
  $$i_t^{(1)},\cdots ,i_t^{(N)}\sim \mathcal{Q}(i_t\mid i_{1:t-1},o_{{}_{1:t}})$$
• 对应重要性权重${\mathcal{W}}_t^{(k)}$可表示为：
  其中$\mathcal{P}(o_t\mid i_t),\mathcal{P}(i_t\mid i_{t-1})$是模型中的状态转移概率和发射概率，$\mathcal{Q}$分布为简化运算，$i_t$的后验概率只和$i_{t-1}$相关。
  $$\begin{array}{rl}{\mathcal{W}}_t^{(k)}& \propto \frac{\mathcal{P}(o_t\mid i_t)\cdot \mathcal{P}(i_t\mid i_{t-1})}{\mathcal{Q}(i_t\mid i_{1:t-1},o_{1:t})}\cdot {\mathcal{W}}_{t-1}^{(k)}\\ & \propto \frac{\mathcal{P}(o_t\mid i_t)\cdot \mathcal{P}(i_t\mid i_{t-1})}{\mathcal{Q}(i_t\mid i_{t-1},o_{1:t})}\cdot {\mathcal{W}}_{t-1}^{(k)}k=1,2,\cdots ,N\end{array}$$
• 将求解的$t$时刻重要性权重结果归一化处理：
  $$\begin{array}{r}\left\{{\mathcal{W}}_t^{(1)},\cdots ,{\mathcal{W}}_t^{(N)}\right\}\to \end{array}\sum _{k=1}^N{\mathcal{W}}_t^{(k)}=1$$
  从而对应重要性采样可表示为如下形式：
  通过迭代求解的重要性权重${\mathcal{W}}_T^{(k)}$对应的归一化结果为${\hat{\mathcal{W}}}_T^{(k)}$,并且该结果成为了新的概率分布。
需要注意的是，并不是只有'最终时刻'$T$才执行归一化操作，而是每一次迭代均执行一次归一化操作。
  $$\begin{array}{rl}{\mathbb{E}}_{\mathcal{I}\mid \mathcal{O}}[f(\mathcal{I})]& \approx \frac{1}{N}\sum _{k=1}^{N}f(i^{(k)})\cdot {\mathcal{W}}^{(k)}\\ & =\sum _{k=1}^{N}f(i^{(k)})\cdot {\hat{\mathcal{W}}}_T^{(k)}\left(\sum _{k=1}^N{\hat{\mathcal{W}}}_T^{(k)}=1\right)\end{array}$$

序列重要性采样对应的算法流程如下：

基于这种序列重要性采样的滤波模型 被称为 序列重要性采样滤波(Sequential Importance Sampling Filter)。

重采样(Resampling)

序列重要性采样的缺陷

随着迭代步骤的增加，在迭代过程中，我们的重要性权重结果可能越来越不平稳。假设初始时刻得到如下标准化后的重要性权重结果如下：
$$\left\{{\mathcal{W}}_1^{(1)},{\mathcal{W}}_1^{(2)},\cdots ,{\mathcal{W}}_1^{(N)}\right\}$$
以第$k$次采样为例，$t$时刻的第$k$次采样的迭代过程表示如下：
W t ( k ) ∝ P ( o t ∣ i t ) ⋅ P ( i t ∣ i t − 1 ) Q ( i t ∣ i t − 1 , o 1 : t ) ⋅ W ^ t − 1 ( k ) ∝ P ( o t ∣ i t ) ⋅ P ( i t ∣ i t − 1 ) Q ( i t ∣ i t − 1 , o 1 : t ) ⋅ P ( o t − 1 ∣ i t − 1 ) ⋅ P ( i t − 1 ∣ i t − 2 ) Q ( i t − 1 ∣ i t − 2 , o 1 : t − 1 ) ⋅ W ^ t − 2 ( k ) ∝ ⋯ ∝ P ( o t ∣ i t ) ⋅ P ( i t ∣ i t − 1 ) Q ( i t ∣ i t − 1 , o 1 : t ) ⋅ P ( o t − 1 ∣ i t − 1 ) ⋅ P ( i t − 1 ∣ i t − 2 ) Q ( i t − 1 ∣ i t − 2 , o 1 : t − 1 ) ⋯ P ( o 1 ∣ i 1 ) ⋅ P ( i 1 ) Q ( i 1 ∣ o 1 ) ⋅ W ^ 1 ( k ) W(k)t∝P(ot∣it)⋅P(it∣it−1)Q(it∣it−1,o1:t)⋅ˆW(k)t−1∝P(ot∣it)⋅P(it∣it−1)Q(it∣it−1,o1:t)⋅P(ot−1∣it−1)⋅P(it−1∣it−2)Q(it−1∣it−2,o1:t−1)⋅ˆW(k)t−2∝⋯∝P(ot∣it)⋅P(it∣it−1)Q(it∣it−1,o1:t)⋅P(ot−1∣it−1)⋅P(it−1∣it−2)Q(it−1∣it−2,o1:t−1)⋯P(o1∣i1)⋅P(i1)Q(i1∣o1)⋅ˆW(k)1

Wt(k)​​∝Q(it​∣it−1​,o1:t​)P(ot​∣it​)⋅P(it​∣it−1​)​⋅W^t−1(k)​∝Q(it​∣it−1​,o1:t​)P(ot​∣it​)⋅P(it​∣it−1​)​⋅Q(it−1​∣it−2​,o1:t−1​)P(ot−1​∣it−1​)⋅P(it−1​∣it−2​)​⋅W^t−2(k)​∝⋯∝Q(it​∣it−1​,o1:t​)P(ot​∣it​)⋅P(it​∣it−1​)​⋅Q(it−1​∣it−2​,o1:t−1​)P(ot−1​∣it−1​)⋅P(it−1​∣it−2​)​⋯Q(i1​∣o1​)P(o1​∣i1​)⋅P(i1​)​⋅W^1(k)​​

虽然在理想状况下，我们更希望 提议分布$\mathcal{Q}$和原始分布$\mathcal{P}$无限接近，即$\frac{\mathcal{P}(\mathcal{I})}{\mathcal{Q}(\mathcal{I})}=1$，但真实情况下，这种情况是基本不可能发生的(要是$\mathcal{P}$分布足够简单，还找什么’提议分布‘$\mathcal{Q}$)。

随着 迭代过程的增加，或者乘的项数增多，最终的迭代结果可能出现如下情况：

某些采样结果对应的重要性权重向其他采样的权重方向偏移。

这会导致权值分配不平衡，使得某些样本 对应的权值退化，从而使样本权重的方差很大。使用这种概率分布近似的期望结果显然是不合适的。

使用重采样处理权值退化问题

针对权值退化问题，常见的解决方式有：

• 重新选择合适的提议分布$\hat{\mathcal{Q}}$
• 重采样(Resampling)

重采样的核心在于：

• 在序列重要性采样归一化的基础上，以归一化权重作为概率再一次进行采样。
• 再一次采样产生出的样本(粒子)，它们的权重均完全相同。
  这种操作本质上是将’归一化后的权重‘以’重采样样本数量比例来表示‘。

将所有归一化后的重要性权重组合起来，组成一个概率分布。从该概率分布中采样的操作是很容易的。

在蒙特卡洛方法介绍——基于概率分布的采样方法中介绍过这种采样方式，具体做法即：

• 在$(0,1)$均匀分布中随机选择一个结果；
• 将该结果映射到对应重要性权重的cdf函数上；
• 通过cdf函数，即可找到对应的重要性权重；

实际上，由于采样的随机性，以及采集样本(粒子)数量的有限性，这种操作极大程度地限制了重要性权重低的结果，甚至没有机会被采样出来。

再次得到的样本会汇聚在重要性权重较高的部分，从而改善了部分样本点的权值退化 问题。
这里非常推荐大家看SmokeMirror博主对于粒子滤波的介绍,这里就不贴图了。
并且称这种 序列重要性采样(Sequential Importance Sampling) + 重采样(Resampling)的方法为基本粒子滤波(Basic Particle Filter)。

下一节将介绍条件随机场(Conditional Random Field,CRF)

相关参考：
粒子滤波(Particle Filter)(自整理用)
机器学习-粒子滤波3-重采样-Basic Particle Filter
Particle Filter Resampling method