Basic Monte Carlo Sampling
应用场所
粒子滤波：针对非线性、非高斯分布的模型，用采到的样本表示概率分布（target PDF），求解
p
(
z
t
∣
x
1
:
t
)
p(z_t | x_{1:t})
p
(
z
t
∣
x
1
:
t
)
（根据1到t时刻的观测变量x求解t时刻隐变量z）
重要性采样(IS)
-
目标：计算服从于target PDF分布的函数
f(
z
)
f(z)
f
(
z
)
的期望，通过应用Monte Carlo方法在概率分布中抽取N个样本，则
p(
y
)
=
E
[
f
(
z
)
]
≈
1
N
∑
i
=
1
N
f
(
z
i
)
p(\mathbf{y})=E[f(z)] \approx\frac{1}{N}\sum_{i=1}^{N}f(z_i)
p
(
y
)
=
E
[
f
(
z
)]
≈
N
1
i
=
1
∑
N
f
(
z
i
)
但如果概率分布比较复杂，则可以通过q(z)（proposal distribution）作为桥梁(importance sampling):
E[
f
(
z
)
]
=
∫
z
f
(
z
)
p
(
z
)
d
z
=
∫
z
f
(
x
)
p
(
z
)
q
(
z
)
q
(
z
)
d
z
=
∑
i
=
1
N
f
(
z
i
)
p
(
z
i
)
q
(
z
i
)
E[f(z)] = \int_zf(z)p(z)dz = \int_zf(x)\frac{p(z)}{q(z)}q(z)dz = \sum_{i=1}^Nf(z_i)\frac{p(z_i)}{q(z_i)}
E
[
f
(
z
)]
=
∫
z
f
(
z
)
p
(
z
)
d
z
=
∫
z
f
(
x
)
q
(
z
)
p
(
z
)
q
(
z
)
d
z
=
i
=
1
∑
N
f
(
z
i
)
q
(
z
i
)
p
(
z
i
)
直接采样，然后对每个样本应用权重得到期望的近似估计，最后进行权重归一化。 -
在滤波问题求解
p(
z
t
∣
x
1
:
t
)
p(z_t | x_{1:t})
p
(
z
t
∣
x
1
:
t
)
时，权重表达式：
wt
i
=
p
(
z
t
i
∣
x
1
:
t
)
q
(
z
t
i
∣
x
1
:
t
)
w_t^i = \frac{p(z_{t}^i | x_{1:t})}{q(z_{t}^i| x_{1:t})}
w
t
i
=
q
(
z
t
i
∣
x
1
:
t
)
p
(
z
t
i
∣
x
1
:
t
)
-
例子
先从q分布得到L个样本
y~
(
ℓ
)
\tilde{\mathbf{y}}^{(\ell)}
y
~
(
ℓ
)
,然后计算权重
w(
ℓ
)
w^{(\ell)}
w
(
ℓ
)
，最后进行权重归一化得到每个样本对应的权重
w~
(
ℓ
)
\tilde{w}^{(\ell)}
w
~
(
ℓ
)
序列重要性采样(SIS)
-
求解
p(
z
1
:
t
∣
x
1
:
t
)
p(z_{1:t} | x_{1:t})
p
(
z
1
:
t
∣
x
1
:
t
)
wt
i
∝
p
(
z
1
:
t
∣
x
1
:
t
)
q
(
z
1
:
t
∣
x
1
:
t
)
w_t^i \propto \frac{p(z_{1:t} | x_{1:t})}{q(z_{1:t}| x_{1:t})}
w
t
i
∝
q
(
z
1
:
t
∣
x
1
:
t
)
p
(
z
1
:
t
∣
x
1
:
t
)
p
(
z
1
:
t
∣
x
1
:
t
)
∝
p
(
x
1
:
t
,
z
1
:
t
)
=
p
(
x
t
∣
z
1
:
t
,
x
1
:
t
−
1
)
p
(
z
1
:
t
,
x
1
:
t
−
1
)
=
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
1
:
t
−
1
,
x
1
:
t
−
1
)
p
(
z
1
:
t
−
1
,
x
1
:
t
−
1
)
=
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
t
−
1
)
p
(
z
1
:
t
−
1
,
x
1
:
t
−
1
)
∝
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
t
−
1
)
p
(
z
1
:
t
−
1
∣
x
1
:
t
−
1
)
p(z_{1:t} | x_{1:t}) \propto p(x_{1:t}, z_{1:t}) =p(x_t |z_{1:t},x_{1:t-1})p(z_{1:t}, x_{1:t-1}) \\=p(x_t | z_t)p(z_t|z_{1:t-1},x_{1:t-1})p(z_{1:t-1},x_{1:t-1}) \\=p(x_t | z_t)p(z_t|z_{t-1})p(z_{1:t-1},x_{1:t-1}) \\ \propto p(x_t | z_t)p(z_t|z_{t-1})p(z_{1:t-1}|x_{1:t-1})
p
(
z
1
:
t
∣
x
1
:
t
)
∝
p
(
x
1
:
t
,
z
1
:
t
)
=
p
(
x
t
∣
z
1
:
t
,
x
1
:
t
−
1
)
p
(
z
1
:
t
,
x
1
:
t
−
1
)
=
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
1
:
t
−
1
,
x
1
:
t
−
1
)
p
(
z
1
:
t
−
1
,
x
1
:
t
−
1
)
=
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
t
−
1
)
p
(
z
1
:
t
−
1
,
x
1
:
t
−
1
)
∝
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
t
−
1
)
p
(
z
1
:
t
−
1
∣
x
1
:
t
−
1
)
指定
q
(
z
1
:
t
∣
x
1
:
t
)
=
q
(
z
t
∣
z
1
:
t
−
1
,
x
1
:
t
)
q
(
z
1
:
t
−
1
∣
x
1
:
t
−
1
)
q(z_{1:t}| x_{1:t})=q(z_{t}|z_{1:t-1}, x_{1:t})q(z_{1:t-1}|x_{1:t-1})
q
(
z
1
:
t
∣
x
1
:
t
)
=
q
(
z
t
∣
z
1
:
t
−
1
,
x
1
:
t
)
q
(
z
1
:
t
−
1
∣
x
1
:
t
−
1
)
得到：
w
t
i
∝
p
(
z
1
:
t
∣
x
1
:
t
)
q
(
z
1
:
t
∣
x
1
:
t
)
∝
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
t
−
1
)
p
(
z
1
:
t
−
1
∣
x
1
:
t
−
1
)
q
(
z
t
∣
z
1
:
t
−
1
x
1
:
t
)
q
(
z
1
:
t
−
1
∣
x
1
:
t
−
1
)
=
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
t
−
1
)
q
(
z
t
∣
z
1
:
t
−
1
x
1
:
t
)
w
t
−
1
i
w_t^i \propto \frac{p(z_{1:t} | x_{1:t})}{q(z_{1:t}| x_{1:t})} \propto \frac{p(x_t | z_t)p(z_t|z_{t-1})p(z_{1:t-1}|x_{1:t-1})}{q(z_{t}|z_{1:t-1} x_{1:t})q(z_{1:t-1}|x_{1:t-1})} = \frac{p(x_t | z_t)p(z_t|z_{t-1})}{q(z_{t}|z_{1:t-1} x_{1:t})} w_{t-1}^i
w
t
i
∝
q
(
z
1
:
t
∣
x
1
:
t
)
p
(
z
1
:
t
∣
x
1
:
t
)
∝
q
(
z
t
∣
z
1
:
t
−
1
x
1
:
t
)
q
(
z
1
:
t
−
1
∣
x
1
:
t
−
1
)
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
t
−
1
)
p
(
z
1
:
t
−
1
∣
x
1
:
t
−
1
)
=
q
(
z
t
∣
z
1
:
t
−
1
x
1
:
t
)
p
(
x
t
∣
z
t
)
p
(
z
t
∣
z
t
−
1
)
w
t
−
1
i
- 在t-1时刻采样并计算权重
-
t时刻根据
q(
z
t
∣
z
1
:
t
−
1
x
1
:
t
)
q(z_{t}|z_{1:t-1} x_{1:t})
q
(
z
t
∣
z
1
:
t
−
1
x
1
:
t
)
采样得到N个样本
zt
i
z_t^i
z
t
i
，并计算得到N个权重 - 权重归一化
SIS 应用于Filtering
通常Filtering问题求解目标为t时刻隐变量的后验
p
(
z
t
∣
x
1
:
t
)
p(z_t | x_{1:t})
p
(
z
t
∣
x
1
:
t
)
，但SIS为了简化运算求解目标为
p
(
z
1
:
t
∣
x
1
:
t
)
p(z_{1:t} | x_{1:t})
p
(
z
1
:
t
∣
x
1
:
t
)
-
根据隐变量z的状态转移方程得到先验分布
p(
z
t
∣
z
t
−
1
)
p(z_t|z_{t-1})
p
(
z
t
∣
z
t
−
1
)
-
根据观测变量x和隐变量z的状态转移方程得到似然函数
p(
x
t
∣
z
1
:
t
)
p(x_t | z_{1:t})
p
(
x
t
∣
z
1
:
t
)
-
设定proposal distribution
q(
z
)
q(z)
q
(
z
)
为隐变量z的先验分布
p(
z
t
∣
z
t
−
1
)
p(z_t|z_{t-1})
p
(
z
t
∣
z
t
−
1
)
-
计算t时刻第
ℓ\ell
ℓ
个样本的权重
w(
ℓ
)
w^{(\ell)}
w
(
ℓ
)
然后进行权重归一化
SIS 存在的问题及改善(SIR)
-
问题：权重退化
一段时间后，大部分样本的权重会逼近0 -
加入重采样(Resampling):
Sequential importance resampling(SIR) or
Sequential importance sampling and resampling(SIS/R))：
思路是将权重作为概率分布，得到累计概率密度函数(CDF)，然后在CDF上取点。
算法流程：
-
输入：
L个SIS产生的
y~
(
ℓ
)
\tilde{\mathbf{y}}^{(\ell)}
y
~
(
ℓ
)
和对应的权重
w(
ℓ
)
w^{(\ell)}
w
(
ℓ
)
-
初始化：
新的样本集合
st
s_t
s
t
为空
样本权重
w(
ℓ
)
w^{(\ell)}
w
(
ℓ
)
的累积密度函数cdf 的第一个值
c1
c_1
c
1
为0。
i为1
-
计算权重
w(
ℓ
)
w^{(\ell)}
w
(
ℓ
)
的cdf -
从(0,
1L
\frac{1}{L}
L
1
)区间采样
u1
u_1
u
1
-
根据
u1
u_1
u
1
为L个样本生成对应的
uℓ
u_{\ell}
u
ℓ
-
遍历输入样本和权重，如果第
ℓ{\ell}
ℓ
个样本的
uℓ
u_{\ell}
u
ℓ
大于
ci
c_i
c
i
，则i+1，并将第i个样本放入新的样本集合
st
s_t
s
t
,新的权重为
1L
\frac{1}{L}
L
1
总结：SIR算法为SIS得到样本和权重之后应用重采样，得到新的L个样本，并且每个样本的权重都是
1
L
\frac{1}{L}
L
1