粒子滤波|机器学习推导系列（十九）

作者: 酷酷的群 | 来源:发表于2021-01-22 15:07 被阅读0次

粒子滤波|机器学习推导系列（十九）
卡尔曼滤波|机器学习推导系列（十八）
粒子滤波学习笔记
粒子滤波
粒子滤波
python数据分析与机器学习(Numpy,Pandas,Mat
绪论|机器学习推导系列（一）
逻辑回归从零实现以及PyTorch实现
智能科学技术中心技术必备
核方法|机器学习推导系列（八）

一、概述

粒子滤波（Particle Filter）是动态模型的非线性，非高斯的版本，也就是说 $z_t$ 和 $z_{t-1}$ 、 $x_t$ 和 $z_t$ 的关系是非线性的，其噪声也是非高斯的：

$z_{t}=g(z_{t-1},\mu ,\varepsilon )\\ x_{t}=h(z_{t},\mu ,\delta )$

对于卡尔曼滤波，可以通过高斯分布的性质直接解得其概率分布。但是对于粒子滤波，由于其状态转移概率和发射概率是任意的，所以没办法得到其概率分布，只能通过采样的方法来进行估计，通常我们在实际应用中更加关心的并非概率分布而是概率分布关于某函数的期望，因此本文主要介绍如何通过采样的方法来求某个函数依概率分布的期望。

二、序列重要性采样

对于分布 $p(z)$ ，要求期望 $E_{p(z)}[f(z)]$ ，重要性采样（Importance Sampling）的方法是引入一个新的分布 $q(z)$ ，然后对 $q(z)$ 进行采样，其做法如下：

$E_{p(z)}[f(z)]=\int f(z)\cdot p(z)\mathrm{d}z\\ =\int f(z)\cdot \frac{p(z)}{q(z)}\cdot q(z)\mathrm{d}z\\ \approx \frac{1}{N}\sum_{i=1}^{N}f(z_{i})\cdot \underset{权重}{\underbrace{\frac{p(z_{i})}{q(z_{i})}}}\\ z_{i}\sim q(z),i=1,2,\cdots ,N$

在滤波问题中，关心的概率分布是 $p(z_{t}|x_{1:t})$ ，权重就是：

$w_{t}^{(i)}=\frac{p(z_{t}^{(i)}|x_{1:t})}{q(z_{t}^{(i)}|x_{1:t})},i=1,2,\cdots ,N$

使用重要性采样的一个问题就是计算量过大，这是因为在每个时刻都要采样 $N$ 次，然而权重的分子这一项计算一次是非常困难的，因此我们期望得到一个 $w_{t}^{(i)}$ 与 $w_{t-1}^{(i)}$ 之间的递推关系来简化这个过程，因此便有了序列重要性采样（Sequential Importance Sampling，SIS）。

在SIS中我们不直接使用 $p(z_{t}^{(i)}|x_{1:t})$ 来进行采样，而是使用 $p(z_{1:t}^{(i)}|x_{1:t})$ ，这是为了计算上的简便，之所以可以这么用 $p(z_{1:t}^{(i)}|x_{1:t})$ 来进行采样，是因为满足：

$w_{t}^{(i)}\propto \frac{p(z_{1:t}^{(i)}|x_{1:t})}{q(z_{1:t}^{(i)}|x_{1:t})}$

现在我们首先要找到 $p(z_{1:t}|x_{1:t})$ 与 $p(z_{1:t-1}|x_{1:t-1})$ 之间的递推关系：

${\color{Red}{p(z_{1:t}|x_{1:t})}}=\frac{p(z_{1:t},x_{1:t})}{p(x_{1:t})}\\ =\frac{1}{C}p(z_{1:t},x_{1:t})\\ =\frac{1}{C}p(x_{t}|z_{1:t},x_{1:t-1})\cdot p(z_{1:t},x_{1:t-1})\\ =\frac{1}{C}p(x_{t}|z_{t})\cdot p(z_{t}|z_{1:t-1},x_{1:t-1})\cdot p(z_{1:t-1},x_{1:t-1})\\ =\frac{1}{C}p(x_{t}|z_{t})\cdot p(z_{t}|z_{t-1})\cdot p(z_{1:t-1}|x_{1:t-1})\cdot \underset{D}{\underbrace{p(x_{1:t-1})}}\\ =\frac{D}{C}p(x_{t}|z_{t})\cdot p(z_{t}|z_{t-1})\cdot {\color{Red}{p(z_{1:t-1}|x_{1:t-1})}}$

由于 $q(z_{1:t}|x_{1:t})$ 是我们指定的，因此可以指定：

${\color{Red}{q(z_{1:t}|x_{1:t})}}=q(z_{t}|z_{1:t-1},x_{1:t})\cdot {\color{Red}{q(z_{1:t-1}|x_{1:t-1})}}$

所以有：

$w_{t}^{(i)}\propto \frac{p(z_{1:t}^{(i)}|x_{1:t})}{q(z_{1:t}^{(i)}|x_{1:t})}\propto \frac{p(x_{t}|z_{t}^{(i)})\cdot p(z_{t}^{(i)}|z_{t-1}^{(i)})\cdot {\color{Red}{p(z_{1:t-1}^{(i)}|x_{1:t-1})}}}{q(z_{t}^{(i)}|z_{1:t-1}^{(i)},x_{1:t})\cdot {\color{Red}{q(z_{1:t-1}^{(i)}|x_{1:t-1})}}}=\frac{p(x_{t}|z_{t}^{(i)})\cdot p(z_{t}^{(i)}|z_{t-1}^{(i)})}{q(z_{t}^{(i)}|z_{1:t-1}^{(i)},x_{1:t})}\cdot w_{t-1}^{(i)}$

总结一下，SIS的迭代过程如下：

前提： $t-1$ 时刻完成采样并计算得到权重
$t$ 时刻：
①根据 $q(z_{t}|z_{1:t-1}^{(i)},x_{1:t})$ 完成采样得到 $z_{t}^{(i)}$ ，并且计算权重 $w_{t}^{(i)}$ ；
②对权重进行归一化， $w_{t}^{(i)}\rightarrow \hat{w}_{t}^{(i)},\sum_{i=1}^{N}\hat{w}_{t}^{(i)}=1$ 。

三、重要性重采样

重要性重采样(Sampling Importance Resampling,SIR)是在上述SIS基础上进行改进的算法，与SIS相比其添加了两个部分，一个是重采样，另一个是特定的 $q(z_{t}|z_{1:t-1},x_{1:t})$ 概率分布。

重采样

SIS算法会出现权值退化的现象，在一定时间后可能会出现大部分权重都逼近于 $0$ 的情况。简单解释一下，这主要还是由于维度灾难的问题，在高维空间中需要大量的样本。使用重采样可以缓解这一现象。

下面以 $N=3$ 为例来阐述重采样的过程，在下表中展示了3个采样粒子的权重（归一化后的权重可以理解为pdf），并且计算了pdf的cdf：

	$z^{(1)}$	$z^{(2)}$	$z^{(3)}$
pdf	0.1	0.1	0.8
cdf	0.1	0.2	1

画出例子的cdf图像如下：

cdf

重采样是指在均匀分布 $u\sim U(0,1)$ 上进行采样，然后依照cdf找到对应的新的粒子 $z^{(i)}$ ，重采样以后的新的权重 $\hat{\hat{w}}=\frac{1}{N}$ 。

在SIS的基础上加上重采样，就是基本的粒子滤波算法（Basic Particle Filter）。

选择合适的提议分布

选择恰当的提议分布也是一种解决权重衰减的方法。这里一个常用的选择就是：

$q(z_{t}|z_{1:t-1},x_{1:t})=p(z_{t}|z_{t-1})$

则此时的权重 $w_{t}^{(i)}$ 的计算公式就变为了：

$w_{t}^{(i)}=\frac{p(x_{t}|z_{t}^{(i)})\cdot p(z_{t}^{(i)}|z_{t-1}^{(i)})}{q(z_{t}^{(i)}|z_{1:t-1}^{(i)},x_{1:t})}\cdot w_{t-1}^{(i)}=\frac{p(x_{t}|z_{t}^{(i)})\cdot {\color{Red}{p(z_{t}^{(i)}|z_{t-1}^{(i)})}}}{{\color{Red}{p(z_{t}^{(i)}|z_{t-1}^{(i)})}}}\cdot w_{t-1}^{(i)}=p(x_{t}|z_{t}^{(i)})\cdot w_{t-1}^{(i)}$

这种方法叫做生成与测试方法（generate and test），生成过程指的是通过 $p(z_{t}|z_{t-1}^{(i)})$ 生成一个新的样本 $z^{(i)}$ 。然后计算权重 $w_{t}^{(i)}=p(x_{t}|z_{t}^{(i)})\cdot w_{t-1}^{(i)}$ ，这里通过将 $w_{t-1}^{(i)}$ 与 $p(x_{t}|z_{t}^{(i)})$ 相乘来得到新的权重 $w_{t}^{(i)}$ ，当生成的样本 $z^{(i)}$ 对应的 $p(x_{t}|z_{t}^{(i)})$ 较大时，得到的新的权重 $w_{t}^{(i)}$ 也就越大，这就相当于测试过程，这就好比表明样本 $z^{(i)}$ 是比较合适的。

算法

在SIS的基础上加上重采样和上述特定的提议分布就得到了SIR算法，其迭代的流程如下：

前提： $t-1$ 时刻完成采样并计算得到权重
$t$ 时刻：
①根据 $q(z_{t}|z_{1:t-1}^{(i)},x_{1:t})=p(z_{t}|z_{t-1}^{(i)})$ 完成采样得到 $z_{t}^{(i)}$ ，并且计算权重 $w_{t}^{(i)}=p(x_{t}|z_{t}^{(i)})\cdot w_{t-1}^{(i)}$ ；
②对权重进行归一化， $w_{t}^{(i)}\rightarrow \hat{w}_{t}^{(i)},\sum_{i=1}^{N}\hat{w}_{t}^{(i)}=1$ 。
③重采样

粒子滤波|机器学习推导系列（十九）
一、概述粒子滤波（Particle Filter）是动态模型的非线性，非高斯的版本，也就是说和、和的关系是非线性...
卡尔曼滤波|机器学习推导系列（十八）
一、概述 HMM 模型适用于隐变量是离散的值的时候，对于连续隐变量的 HMM，常用卡尔曼滤波（Kalman Fil...
粒子滤波学习笔记
本文参考博客地址粒子滤波粒子滤波的状态转移方程和观测方程如下：其中的x(t)为t时刻状态，u(t)为控制量，w...
粒子滤波
参考博客 //================================================= ...
粒子滤波
上图中还应打出地标的位置。粒子滤波的核心思路是通过两种测量的比较，反推出观测者本身的位置。测量类型I：从未知观...
python数据分析与机器学习(Numpy,Pandas,Mat
机器学习怎么学？机器学习包含数学原理推导和实际应用技巧，所以需要清楚算法的推导过程和如何应用。深度学习是机器学...
绪论|机器学习推导系列（一）
一、频率派 vs 贝叶斯派机器学习主要解决从数据中获取其概率分布的问题，通过一些机器学习的算法可以从大量数据中找...
逻辑回归从零实现以及PyTorch实现
逻辑回归原理参考链接：线性分类|机器学习推导系列（四）[https://www.jianshu.com/p/4e7...
智能科学技术中心技术必备
1. 粒子滤波 2.卷积神经网络
核方法|机器学习推导系列（八）
一、线性不可分问题有时线性可分的数据夹杂一点噪声，可以通过改进算法来实现分类，比如感知机的口袋算法和支持向量机的...

粒子滤波|机器学习推导系列（十九）

一、概述

二、序列重要性采样

三、重要性重采样

相关文章

粒子滤波|机器学习推导系列（十九）

卡尔曼滤波|机器学习推导系列（十八）

粒子滤波学习笔记

粒子滤波

粒子滤波

python数据分析与机器学习(Numpy,Pandas,Mat

绪论|机器学习推导系列（一）

逻辑回归从零实现以及PyTorch实现

智能科学技术中心技术必备

核方法|机器学习推导系列（八）

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员

人工智能