这是有关Dynamic Model 的两个假设，也是我们研究这个模型的前提条件。这两个假设可以大大
齐次Markov 假设(无后向性) ：未来与过去无关，只依赖与当前的状态。数学公式描述也就是。P ( i t + 1 ∣ i t , i t − 1 , ⋯ , i 1 , o t , ⋯ , o 1 ) = P ( i t + 1 ∣ i t ) （ 1 ）
P\left(i_{t+1} | i_{t}, i_{t-1}, \cdots, i_{1}, o_{t}, \cdots, o_{1}\right)=P\left(i_{t+1} | i_{t}\right) \ \ \ \ \ \ \ \ （1）
P ( i t + 1 ∣ i t , i t − 1 , ⋯ , i 1 , o t , ⋯ , o 1 ) = P ( i t + 1 ∣ i t ) （ 1 ）
观测独立假设 ：当前时刻的观测变量只依赖于当前时刻的隐变量。P ( o t ∣ i t , i t − 1 , ⋯ , i 1 , o t , ⋯ , o 1 ) = P ( o t ∣ i t ) （ 2 ）
P\left(o_{t} | i_{t}, i_{t-1}, \cdots, i_{1}, o_{t}, \cdots, o_{1}\right)=P\left(o_{t} | i_{t}\right) \ \ \ \ \ \ \ \ （2）
P ( o t ∣ i t , i t − 1 , ⋯ , i 1 , o t , ⋯ , o 1 ) = P ( o t ∣ i t ) （ 2 ）
这两个方程分别描述的是，隐变量状态与状态之间的转移概率，由当前时刻隐变量推出当前时刻 观测变量的概率，公式化描述如下所示：{ z t = g ( z t − 1 , μ , ξ ) x t = h ( z t , μ , δ ) （ 3 ）
\left\{\begin{array}{l}
z_{t}=g\left(z_{t-1}, \mu, \xi\right) \\
x_{t}=h\left(z_{t}, \mu, \delta\right)
\end{array}\right. \ \ \ \ \ \ \ \ \ \ \ （3）
{ z t = g ( z t − 1 , μ , ξ ) x t = h ( z t , μ , δ ) （ 3 ） g ( ⋅ ) g(\cdot) g ( ⋅ ) A , h ( ⋅ ) A, h(\cdot) A , h ( ⋅ ) H M M \mathrm{HMM} H M M B B B
在 Dynamic Model 中，我们主要可以分为三大类问题。
这个在之前的章节中，我们已经有了详细的讲解。主要特点就是，隐状态 z z z s s s
线性动态系通常也被我们称为线性高斯系统，而线性高斯系统这个名字更加形象，而线性和高斯 的来源主要如下所示：{ z t = A ⋅ z t − 1 + B + ϵ ϵ ∼ N ( 0 , Q ) x t = C ⋅ z t + D + δ δ ∼ N ( 0 , R ) （ 4 ）
\left\{\begin{array}{l}
z_{t}=A \cdot z_{t-1}+B+\epsilon \quad \epsilon \sim \mathcal{N}(0, Q) \\
x_{t}=C \cdot z_{t}+D+\delta \quad \delta \sim \mathcal{N}(0, R)
\end{array}\right. \ \ \ \ \ \ （4）
{ z t = A ⋅ z t − 1 + B + ϵ ϵ ∼ N ( 0 , Q ) x t = C ⋅ z t + D + δ δ ∼ N ( 0 , R ) （ 4 ）
也就是式 (3) 中的两个酸数将符合线性和和声符合 Gaussian Distribution 的原则。而 Dynamic Model中重点关注的就是 Filter 问题，Filter 问题就是求解 P ( z t ∣ x 1 , x 2 , ⋯ , x t ) , P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t}\right), P ( z t ∣ x 1 , x 2 , ⋯ , x t ) ,
我们的求解目标是 P ( z t ∣ x 1 , x 2 , ⋯ , x t ) P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t}\right) P ( z t ∣ x 1 , x 2 , ⋯ , x t ) z t z_{t} z t P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) = ∫ z t − 1 P ( z t ∣ z t − 1 ) P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) d z t − 1 （ 5 ）
P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t-1}\right)=\int_{z_{t-1}} P\left(z_{t} | z_{t-1}\right) P\left(z_{t-1} | x_{1}, x_{2}, \cdots, x_{t-1}\right) d z_{t-1} \ \ \ \ \ \ （5）
P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) = ∫ z t − 1 P ( z t ∣ z t − 1 ) P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) d z t − 1 （ 5 ） z t z_{t} z t x t x_{t} x t P ( z t ∣ x 1 , x 2 , ⋯ , x t ) ∝ P ( x t ∣ z t ) ⋅ P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) （ 6 ）
P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t}\right) \propto P\left(x_{t} | z_{t}\right) \cdot P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t-1}\right) \ \ \ \ \ \ （6）
P ( z t ∣ x 1 , x 2 , ⋯ , x t ) ∝ P ( x t ∣ z t ) ⋅ P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) （ 6 ）
P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) = ∫ z t − 1 P ( z t , z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) d z t − 1 = ∫ z t − 1 P ( z t ∣ z t − 1 , x 1 , x 2 , ⋯ , x t − 1 ) P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) d z t − 1 （ 7 ）
\begin{aligned}
P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t-1}\right) &=\int_{z_{t-1}} P\left(z_{t}, z_{t-1} | x_{1}, x_{2}, \cdots, x_{t-1}\right) d z_{t-1} \\
&=\int_{z_{t-1}} P\left(z_{t} | z_{t-1}, x_{1}, x_{2}, \cdots, x_{t-1}\right) P\left(z_{t-1} | x_{1}, x_{2}, \cdots, x_{t-1}\right) d z_{t-1}
\end{aligned} \ \ \ \ \ \ （7）
P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) = ∫ z t − 1 P ( z t , z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) d z t − 1 = ∫ z t − 1 P ( z t ∣ z t − 1 , x 1 , x 2 , ⋯ , x t − 1 ) P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) d z t − 1 （ 7 ） P ( z t ∣ z t − 1 , x 1 , x 2 , ⋯ , x t − 1 ) = P ( z t ∣ z t − 1 ) , P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) P\left(z_{t} | z_{t-1}, x_{1}, x_{2}, \cdots, x_{t-1}\right)=P\left(z_{t} | z_{t-1}\right), P\left(z_{t-1} | x_{1}, x_{2}, \cdots, x_{t-1}\right) P ( z t ∣ z t − 1 , x 1 , x 2 , ⋯ , x t − 1 ) = P ( z t ∣ z t − 1 ) , P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) t − 1 t-1 t − 1
首先，我们提一下， P ( x 1 , x 2 , ⋯ , x t ) P\left(x_{1}, x_{2}, \cdots, x_{t}\right) P ( x 1 , x 2 , ⋯ , x t ) P ( z t ∣ x 1 , x 2 , ⋯ , x t ) = P ( z t , x 1 , x 2 , ⋯ , x t ) P ( x 1 , x 2 , ⋯ , x t ) = 1 C P ( z t , x 1 , x 2 , ⋯ , x t ) = 1 C P ( x t ∣ z t , x 1 , x 2 , ⋯ , x t − 1 ) ⏟ P ( x t ∣ z t ) P ( z t , x 1 , x 2 , ⋯ , x t − 1 ) = 1 C P ( x t ∣ z t ) P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) P ( x 1 , x 2 , ⋯ , x t − 1 ) ⏟ const D = D C P ( x t ∣ z t ) P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) （ 8 ）
\begin{aligned}
P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t}\right) &=\frac{P\left(z_{t}, x_{1}, x_{2}, \cdots, x_{t}\right)}{P\left(x_{1}, x_{2}, \cdots, x_{t}\right)} \\
&=\frac{1}{C} P\left(z_{t}, x_{1}, x_{2}, \cdots, x_{t}\right) \\
&=\frac{1}{C} \underbrace{P\left(x_{t} | z_{t}, x_{1}, x_{2}, \cdots, x_{t-1}\right)}_{P\left(x_{t} | z_{t}\right)} P\left(z_{t}, x_{1}, x_{2}, \cdots, x_{t-1}\right) \\
&=\frac{1}{C} P\left(x_{t} | z_{t}\right) P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t-1}\right) \underbrace{P\left(x_{1}, x_{2}, \cdots, x_{t-1}\right)}_{\text {const } D} \\
&=\frac{D}{C} P\left(x_{t} | z_{t}\right) P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t-1}\right)
\end{aligned} \ \ \ \ \ \ \ \ \ \ \ \ （8）
P ( z t ∣ x 1 , x 2 , ⋯ , x t ) = P ( x 1 , x 2 , ⋯ , x t ) P ( z t , x 1 , x 2 , ⋯ , x t ) = C 1 P ( z t , x 1 , x 2 , ⋯ , x t ) = C 1 P ( x t ∣ z t ) P ( x t ∣ z t , x 1 , x 2 , ⋯ , x t − 1 ) P ( z t , x 1 , x 2 , ⋯ , x t − 1 ) = C 1 P ( x t ∣ z t ) P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) const D P ( x 1 , x 2 , ⋯ , x t − 1 ) = C D P ( x t ∣ z t ) P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) （ 8 ） P ( x t ∣ z t ) P\left(x_{t} | z_{t}\right) P ( x t ∣ z t ) , P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) , P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t-1}\right) , P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) t − 1 t-1 t − 1
Non-Linear Dynamic System 和Linear Dynamic System 区别是，相邻两个隐变量状态z t z_t z t z t − 1 z_{t−1} z t − 1 ，而且，Noise 也是Gaussian 的。所以，无法使用Kalman Filter 一样的方法得到解析解。所以，只能采用Monte-Carlo Sampling 一样的采样方法来得出近似解。Non-Linear 没有那么好的特征，求不出，只能采样 。在贝叶斯框架的Inference 主要要求解的是一个后验分布 P ( Z ∣ X ) P(Z | X) P ( Z ∣ X ) z ∣ x [ f ( x ) ] = ∫ f ( z ) p ( z ∣ x ) d x _{z | x}[f(x)]=\int f(z) p(z | x) d x z ∣ x [ f ( x ) ] = ∫ f ( z ) p ( z ∣ x ) d x N N N z ( i ) ∼ P ( Z ∣ X ) , { z ( 1 ) , z ( 2 ) , ⋯ , z ( N ) } z^{(i)} \sim P(Z | X),\left\{z^{(1)}, z^{(2)}, \cdots, z^{(N)}\right\} z ( i ) ∼ P ( Z ∣ X ) , { z ( 1 ) , z ( 2 ) , ⋯ , z ( N ) } 1 N ∑ i = 1 N f ( z ( i ) ) \frac{1}{N} \sum_{i=1}^{N} f\left(z^{(i)}\right) N 1 ∑ i = 1 N f ( z ( i ) )
Filter的预测过程：P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) = ∫ z t − 1 P ( z t ∣ z t − 1 ) P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) d z t − 1 = E p ( z ) [ f ( z ) ]
P\left(z_{t} | x_{1}, x_{2}, \cdots, x_{t-1}\right)=\int_{z_{t-1}} P\left(z_{t} | z_{t-1}\right) P\left(z_{t-1} | x_{1}, x_{2}, \cdots, x_{t-1}\right) d z_{t-1} =\mathbb{E}_{p(z)}[f(z)]
P ( z t ∣ x 1 , x 2 , ⋯ , x t − 1 ) = ∫ z t − 1 P ( z t ∣ z t − 1 ) P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) d z t − 1 = E p ( z ) [ f ( z ) ] P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) P\left(z_{t-1} | x_{1}, x_{2}, \cdots, x_{t-1}\right) P ( z t − 1 ∣ x 1 , x 2 , ⋯ , x t − 1 ) q ( z ) q(z) q ( z ) E p ( z ) [ f ( z ) ] = ∫ p ( z ) f ( z ) d z = ∫ p ( z ) q ( z ) q ( z ) f ( z ) d z = ∫ f ( z ) p ( z ) q ( z ) q ( z ) d z ≈ 1 N ∑ i = 1 N f ( z i ) p ( z i ) q ( z i ) ( z i ∼ q ( z ) , i = 1 , 2 , ⋯ , N ) （ 9 ）
\begin{aligned}
\mathbb{E}_{p(z)}[f(z)]=\int p(z) f(z) d z &=\int \frac{p(z)}{q(z)} q(z) f(z) d z \\
&=\int f(z) \frac{p(z)}{q(z)} q(z) d z \\
& \approx \frac{1}{N} \sum_{i=1}^{N} f\left(z_{i}\right) \frac{p\left(z_{i}\right)}{q\left(z_{i}\right)}\left(z_{i} \sim q(z), i=1,2, \cdots, N\right)
\end{aligned} \ \ \ \ \ \ \ \ \ \ \ \ （9）
E p ( z ) [ f ( z ) ] = ∫ p ( z ) f ( z ) d z = ∫ q ( z ) p ( z ) q ( z ) f ( z ) d z = ∫ f ( z ) q ( z ) p ( z ) q ( z ) d z ≈ N 1 i = 1 ∑ N f ( z i ) q ( z i ) p ( z i ) ( z i ∼ q ( z ) , i = 1 , 2 , ⋯ , N ) （ 9 ） p ( z i ) q ( z i ) \frac{p\left(z_{i}\right)}{q\left(z_{i}\right)} q ( z i ) p ( z i ) x 1 : t = x 1 , x 2 , ⋯ , x t x_{1: t}=x_{1}, x_{2}, \cdots, x_{t} x 1 : t = x 1 , x 2 , ⋯ , x t P ( z t ∣ x 1 : t ) , P\left(z_{t} | x_{1: t}\right), P ( z t ∣ x 1 : t ) , w t ( i ) = P ( z t ( i ) ∣ x 1 : t ) Q ( z t ( i ) ∣ x 1 : t ) （ 10 ）
w_{t}^{(i)}=\frac{P\left(z_{t}^{(i)} | x_{1: t}\right)}{Q\left(z_{t}^{(i)} | x_{1: t}\right)} \ \ \ \ \ \ \ \ \ \ \ \ （10）
w t ( i ) = Q ( z t ( i ) ∣ x 1 : t ) P ( z t ( i ) ∣ x 1 : t ) （ 1 0 ） t = 1 : w 1 ( i ) , i = 1 , 2 , ⋯ , N ∼ w 1 ( 1 ) , w 1 ( 2 ) , ⋯ , w 1 ( N ) t = 2 : w 2 ( i ) , i = 1 , 2 , ⋯ , N ∼ w 2 ( 1 ) , w 2 ( 2 ) , ⋯ , w 2 ( N ) ⋯ t = T : w T ( i ) , i = 1 , 2 , ⋯ , N ∼ w T ( 1 ) , w T ( 2 ) , ⋯ , w T ( N ) （ 11 ）
\begin{array}{l}
t=1: w_{1}^{(i)}, i=1,2, \cdots, N \sim w_{1}^{(1)}, w_{1}^{(2)}, \cdots, w_{1}^{(N)} \\
t=2: w_{2}^{(i)}, i=1,2, \cdots, N \sim w_{2}^{(1)}, w_{2}^{(2)}, \cdots, w_{2}^{(N)} \\
\cdots \\
t=T: w_{T}^{(i)}, i=1,2, \cdots, N \sim w_{T}^{(1)}, w_{T}^{(2)}, \cdots, w_{T}^{(N)}
\end{array} \ \ \ \ \ \ \ \ \ \ \ \ （11）
t = 1 : w 1 ( i ) , i = 1 , 2 , ⋯ , N ∼ w 1 ( 1 ) , w 1 ( 2 ) , ⋯ , w 1 ( N ) t = 2 : w 2 ( i ) , i = 1 , 2 , ⋯ , N ∼ w 2 ( 1 ) , w 2 ( 2 ) , ⋯ , w 2 ( N ) ⋯ t = T : w T ( i ) , i = 1 , 2 , ⋯ , N ∼ w T ( 1 ) , w T ( 2 ) , ⋯ , w T ( N ) （ 1 1 ） P ( z t ( i ) ∣ x 1 : t ) P\left(z_{t}^{(i)} | x_{1: t}\right) P ( z t ( i ) ∣ x 1 : t ) w T ( i ) w_{T}^{(i)} w T ( i ) w T − 1 ( i ) w_{T-1}^{(i)} w T − 1 ( i )
这个算法中的主要思想就是，找到 w T ( i ) w_{T}^{(i)} w T ( i ) w T − 1 ( i ) w_{T-1}^{(i)} w T − 1 ( i ) P ( z t ∣ x 1 : t ) ⟶ P ( z 1 : t ∣ x 1 : t ) （ 12 ）
P\left(z_{t} | x_{1: t}\right) \longrightarrow P\left(z_{1: t} | x_{1: t}\right) \ \ \ \ \ \ \ \ \ \ \ \ （12）
P ( z t ∣ x 1 : t ) ⟶ P ( z 1 : t ∣ x 1 : t ) （ 1 2 ） P ( z t ∣ x 1 : t ) P\left(z_{t} | x_{1: t}\right) P ( z t ∣ x 1 : t ) P ( z 1 : t ∣ x 1 : t ) P\left(z_{1: t} | x_{1: t}\right) P ( z 1 : t ∣ x 1 : t ) z 1 : t − 1 z_{1: t-1} z 1 : t − 1 P ( z t ∣ x 1 : t ) P\left(z_{t} | x_{1: t}\right) P ( z t ∣ x 1 : t ) P ( z 1 : t ∣ x 1 : t ) P\left(z_{1: t} | x_{1: t}\right) P ( z 1 : t ∣ x 1 : t )
而 P ( z 1 : t ∣ x 1 : t ) P\left(z_{1: t} | x_{1: t}\right) P ( z 1 : t ∣ x 1 : t ) w t ( i ) w_{t}^{(i)} w t ( i ) w t ( i ) ∝ P ( z 1 : t ( i ) ∣ x 1 : t ) Q ( z 1 : t ( i ) ∣ x 1 : t ) （ 13 ）
w_{t}^{(i)} \propto \frac{P\left(z_{1: t}^{(i)} | x_{1: t}\right)}{Q\left(z_{1: t}^{(i)} | x_{1: t}\right)} \ \ \ \ \ \ \ \ \ \ \ \ （13）
w t ( i ) ∝ Q ( z 1 : t ( i ) ∣ x 1 : t ) P ( z 1 : t ( i ) ∣ x 1 : t ) （ 1 3 ）
P ( z 1 : t ( i ) ∣ x 1 : t ) P\left(z_{1: t}^{(i)} | x_{1: t}\right) P ( z 1 : t ( i ) ∣ x 1 : t )
P ( z 1 : t ( i ) ∣ x 1 : t ) = P ( z 1 : t ( i ) , x 1 : t ) P ( x 1 : t ) = 1 C P ( z 1 : t ( i ) , x 1 : t ) = 1 C P ( x t ∣ z 1 : t ( i ) , x 1 : t − 1 ) ⏟ P ( x t ∣ z t ( t ) ) P ( z 1 : t ( i ) , x 1 : t − 1 ) = 1 C P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t − 1 ) ⏟ P ( z t ( t ) ∣ z t − 1 ) P ( z 1 : t − 1 ( i ) , x 1 : t − 1 ) = 1 C P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z 1 : t − 1 ( i ) , x 1 : t − 1 ) = 1 C P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) P ( x 1 : t − 1 ) ⏟ D = D C P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) （ 14 ）
\begin{aligned}
P\left(z_{1: t}^{(i)} | x_{1: t}\right) &=\frac{P\left(z_{1: t}^{(i)}, x_{1: t}\right)}{P\left(x_{1: t}\right)} \\
&=\frac{1}{C} P\left(z_{1: t}^{(i)}, x_{1: t}\right) \\
&=\frac{1}{C} \underbrace{P\left(x_{t} | z_{1: t}^{(i)}, x_{1: t-1}\right)}_{P\left(x_{t} | z_{t}^{(t)}\right)} P\left(z_{1: t}^{(i)}, x_{1: t-1}\right) \\
&=\frac{1}{C} P\left(x_{t} | z_{t}^{(i)}\right) \underbrace{P\left(z_{t}^{(i)} | z_{1: t-1}^{(i)}, x_{1: t-1}\right)}_{P\left(z_{t}^{(t)} | z_{t-1}\right)} P\left(z_{1: t-1}^{(i)}, x_{1: t-1}\right) \\
&=\frac{1}{C} P\left(x_{t} | z_{t}^{(i)}\right) P\left(z_{t}^{(i)} | z_{t-1}\right) P\left(z_{1: t-1}^{(i)}, x_{1: t-1}\right) \\
&=\frac{1}{C} P\left(x_{t} | z_{t}^{(i)}\right) P\left(z_{t}^{(i)} | z_{t-1}\right) P\left(z_{1: t-1}^{(i)} | x_{1: t-1}\right) \underbrace{P\left(x_{1: t-1}\right)}_{D} \\
&=\frac{D}{C} P\left(x_{t} | z_{t}^{(i)}\right) P\left(z_{t}^{(i)} | z_{t-1}\right) P\left(z_{1: t-1}^{(i)} | x_{1: t-1}\right)
\end{aligned} \ \ \ \ \ \ \ \ \ \ \ \ （14）
P ( z 1 : t ( i ) ∣ x 1 : t ) = P ( x 1 : t ) P ( z 1 : t ( i ) , x 1 : t ) = C 1 P ( z 1 : t ( i ) , x 1 : t ) = C 1 P ( x t ∣ z t ( t ) ) P ( x t ∣ z 1 : t ( i ) , x 1 : t − 1 ) P ( z 1 : t ( i ) , x 1 : t − 1 ) = C 1 P ( x t ∣ z t ( i ) ) P ( z t ( t ) ∣ z t − 1 ) P ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t − 1 ) P ( z 1 : t − 1 ( i ) , x 1 : t − 1 ) = C 1 P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z 1 : t − 1 ( i ) , x 1 : t − 1 ) = C 1 P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) D P ( x 1 : t − 1 ) = C D P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) （ 1 4 ）
Q ( z 1 : t ( i ) ∣ x 1 : t ) Q\left(z_{1: t}^{(i)} | x_{1: t}\right) Q ( z 1 : t ( i ) ∣ x 1 : t )
分母中，我们假设：Q ( z 1 : t ( i ) ∣ x 1 : t ) = Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) Q ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) （ 15 ）
Q\left(z_{1: t}^{(i)} | x_{1: t}\right)=Q\left(z_{t}^{(i)} | z_{1: t-1}^{(i)}, x_{1: t}\right) Q\left(z_{1: t-1}^{(i)} | x_{1: t-1}\right) \ \ \ \ \ \ \ \ \ \ \ \ （15）
Q ( z 1 : t ( i ) ∣ x 1 : t ) = Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) Q ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) （ 1 5 ） Q ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) Q\left(z_{1: t-1}^{(i)} | x_{1: t-1}\right) Q ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) Q ( z 1 : t − 1 ( i ) ∣ x 1 : t ) Q\left(z_{1: t-1}^{(i)} | x_{1: t}\right) Q ( z 1 : t − 1 ( i ) ∣ x 1 : t ) Q ( ⋅ ) Q(\cdot) Q ( ⋅ ) w t ( i ) ∝ P ( z 1 : t ( i ) ∣ x 1 : t ) Q ( z 1 : t ( i ) ∣ x 1 : t ) ∝ P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) Q ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) = P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) ⋅ w t − 1 ( i ) （ 16 ）
\begin{array}{l}
w_{t}^{(i)} \propto \frac{P\left(z_{1: t}^{(i)} | x_{1: t}\right)}{Q\left(z_{1: t}^{(i)} | x_{1: t}\right)} \propto \frac{P\left(x_{t} | z_{t}^{(i)}\right) P\left(z_{t}^{(i)} | z_{t-1}\right) P\left(z_{1: t-1}^{(i)} | x_{1: t-1}\right)}{Q\left(z_{t}^{(i)} | z_{1: t-1}^{(i)}, x_{1: t}\right) Q\left(z_{1: t-1}^{(i)} | x_{1: t-1}\right)} \\ \\
=\frac{P\left(x_{t} | z_{t}^{(i)}\right) P\left(z_{t}^{(i)} | z_{t-1}\right)}{Q\left(z_{t}^{(i)} | z_{1: t-1}^{(i)}, x_{1: t}\right)} \cdot w_{t-1}^{(i)}
\end{array} \ \ \ \ \ \ \ \ \ \ \ \ （16）
w t ( i ) ∝ Q ( z 1 : t ( i ) ∣ x 1 : t ) P ( z 1 : t ( i ) ∣ x 1 : t ) ∝ Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) Q ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z 1 : t − 1 ( i ) ∣ x 1 : t − 1 ) = Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) ⋅ w t − 1 ( i ) （ 1 6 ） P ( x t ∣ z t ( i ) ) P\left(x_{t} | z_{t}^{(i)}\right) P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P\left(z_{t}^{(i)} | z_{t-1}\right) P ( z t ( i ) ∣ z t − 1 ) , Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) , Q\left(z_{t}^{(i)} | z_{1: t-1}^{(i)}, x_{1: t}\right) , Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) w t ( i ) , w_{t}^{(i)}, w t ( i ) ,
我们反复强调过，求解后验概率分布 P ( Z ∣ X ) P(Z | X) P ( Z ∣ X ) E Z ∣ X [ f ( Z ) ] , \mathbb{E}_{Z | X}[f(Z)], E Z ∣ X [ f ( Z ) ] , V a r [ X ] = E [ X 2 ] − [ E [ X ] ] 2 Var[X] = \mathbb{E}\left[X^{2}\right]-[\mathbb{E}[X]]^{2} V a r [ X ] = E [ X 2 ] − [ E [ X ] ] 2 w t ( i ) ∝ P ( z 1 i t ( i ) ∣ x 1 : t ) Q ( z 1 : t ( i ) ∣ x 1 : t ) ∝ P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) ⋅ w t − 1 ( i ) （ 17 ）
w_{t}^{(i)} \propto \frac{P\left(z_{1 i t}^{(i)} | x_{1: t}\right)}{Q\left(z_{1: t}^{(i)} | x_{1: t}\right)} \propto \frac{P\left(x_{t} | z_{t}^{(i)}\right) P\left(z_{t}^{(i)} | z_{t-1}\right)}{Q\left(z_{t}^{(i)} | z_{1: t-1}^{(i)}, x_{1: t}\right)} \cdot w_{t-1}^{(i)} \ \ \ \ \ \ \ \ \ \ \ \ （17）
w t ( i ) ∝ Q ( z 1 : t ( i ) ∣ x 1 : t ) P ( z 1 i t ( i ) ∣ x 1 : t ) ∝ Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) ⋅ w t − 1 ( i ) （ 1 7 ） Q ( ⋅ ) Q(\cdot) Q ( ⋅ ) Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) Q\left(z_{t}^{(i)} | z_{1: t-1}^{(i)}, x_{1: t}\right) Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) Q ( z t ( i ) ∣ z t − 1 ( i ) , x 1 : t ) Q\left(z_{t}^{(i)} | z_{t-1}^{(i)}, x_{1: t}\right) Q ( z t ( i ) ∣ z t − 1 ( i ) , x 1 : t )
下面，我们将硫理一下这个算法： Sequential Importance Sampling Algorithm :前提 ： t − 1 t-1 t − 1 t t t N N N i = 1 , 2 , ⋯ , N : i=1,2, \cdots, N: i = 1 , 2 , ⋯ , N : z t ( i ) ∼ Q ( z t ∣ z t − 1 , x 1 : t ) ( 18 ) w t ( i ) ∝ P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) ⋅ w t − 1 ( i ) ( 19 )
\begin{array}{c}
z_{t}^{(i)} \sim Q\left(z_{t} | z_{t-1}, x_{1: t}\right) \ \ \ \ \ \ \ \ \ \ \ \ (18) \\ \\
w_{t}^{(i)} \propto \frac{P\left(x_{t} | z_{t}^{(i)}\right) P\left(z_{t}^{(i)} | z_{t-1}\right)}{Q\left(z_{t}^{(i)} | z_{1: t-1}^{(i)}, x_{1: t}\right)} \cdot w_{t-1}^{(i)} \ \ \ \ \ \ \ \ \ \ \ \ (19)
\end{array}
z t ( i ) ∼ Q ( z t ∣ z t − 1 , x 1 : t ) ( 1 8 ) w t ( i ) ∝ Q ( z t ( i ) ∣ z 1 : t − 1 ( i ) , x 1 : t ) P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) ⋅ w t − 1 ( i ) ( 1 9 ) w t ( i ) 归一化, , 令 ∑ i = 1 N w t ( i ) = 1
w_{t}^{(i)} \text { 归一化, }, \text { 令 } \sum_{i=1}^{N} w_{t}^{(i)}=1
w t ( i ) 归一化 , , 令 i = 1 ∑ N w t ( i ) = 1 1 N ∑ i = 1 N f ( z ( i ) ) w ( i ) = ∑ i = 1 N f ( z ( i ) ) w ^ ( i ) ( 20 )
\frac{1}{N} \sum_{i=1}^{N} f\left(z^{(i)}\right) w^{(i)}=\sum_{i=1}^{N} f\left(z^{(i)}\right) \hat{w}^{(i)} \ \ \ \ \ \ \ \ \ \ \ \ (20)
N 1 i = 1 ∑ N f ( z ( i ) ) w ( i ) = i = 1 ∑ N f ( z ( i ) ) w ^ ( i ) ( 2 0 ) w ^ ( i ) \hat{w}^{(i)} w ^ ( i ) ∑ i = 1 N f ( z ( i ) ) w ^ ( i ) \sum_{i=1}^{N} f\left(z^{(i)}\right) \hat{w}^{(i)} ∑ i = 1 N f ( z ( i ) ) w ^ ( i )
Sequential Importance Sampling 最大的问题就是权值退化。也就是w t i w_t^i w t i
采更多的样本；
Resampling 的方法；
选择一个更好的Proposal Distribution Q(z)。
那么Resampling 的方法如何来解决权值退化的方法？那就是舍弃权重。之前我们用Weight 来代表一个粒子的重要程度，而Resampling 就是通过用粒子数量来代替Weight 的方法来表示重要程度。
经过重要性采样后，我们得到了N 个样本点，以及对应的权重。那么我用权重来作为采样的概率，重新测采样出N 个样本。也就是如下图所示：
通过二次采样可以降低采样不平衡的问题。至于为什么呢？大家想一想，我在这里表达一下自己的看法。p ( z i ) q ( z i ) \frac {p(zi)}{q(zi)} q ( z i ) p ( z i ) p ( z i ) p(z_i) p ( z i ) q ( z i ) q(z_i) q ( z i ) q ( z i ) q(z_i) q ( z i )
具体实现的思路其实就很简单。那就是根据概率密度函数(pdf) 来计算得到概率分布函数(cdf)。然后通过从[0,1] 之间进行均匀采样，来得到相应的的值。这个，我们在Markov Chain Monte Carlo 01 Sampling Method 的概率分布采样中已经做了详细的描述。
选择 Q ( z t ∣ z 1 : t − 1 , x 1 : t ) = P ( z t ∣ z t − 1 ( i ) ) , Q\left(z_{t} | z_{1: t-1}, x_{1: t}\right)=P\left(z_{t} | z_{t-1}^{(i)}\right), Q ( z t ∣ z 1 : t − 1 , x 1 : t ) = P ( z t ∣ z t − 1 ( i ) ) , w t ( i ) ∝ P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z t ∣ z t − 1 ( i ) ) ⋅ w t − 1 ( i ) = P ( x t ∣ z t ( i ) ) ⋅ w t − 1 ( i )
w_{t}^{(i)} \propto \frac{P\left(x_{t} | z_{t}^{(i)}\right) P\left(z_{t}^{(i)} | z_{t-1}\right)}{P\left(z_{t} | z_{t-1}^{(i)}\right)} \cdot w_{t-1}^{(i)}=P\left(x_{t} | z_{t}^{(i)}\right) \cdot w_{t-1}^{(i)}
w t ( i ) ∝ P ( z t ∣ z t − 1 ( i ) ) P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) ⋅ w t − 1 ( i ) = P ( x t ∣ z t ( i ) ) ⋅ w t − 1 ( i ) w t ( i ) = P ( x t ∣ z t ( i ) ) ⋅ w t − 1 ( i ) , w_{t}^{(i)}=P\left(x_{t} | z_{t}^{(i)}\right) \cdot w_{t-1}^{(i)}, w t ( i ) = P ( x t ∣ z t ( i ) ) ⋅ w t − 1 ( i ) , z ( i ) ∼ P ( z t ∣ z t − 1 ( i ) ) z^{(i)} \sim P\left(z_{t} | z_{t-1}^{(i)}\right) z ( i ) ∼ P ( z t ∣ z t − 1 ( i ) ) Sequential Importance Sampling + Resampling + Q ( z t ∣ z 1 : t − 1 , x 1 : t ) = P ( z t ∣ z t − 1 ( i ) )
\text { Sequential Importance Sampling }+\text { Resampling }+Q\left(z_{t} | z_{1: t-1}, x_{1: t}\right)=P\left(z_{t} | z_{t-1}^{(i)}\right)
Sequential Importance Sampling + Resampling + Q ( z t ∣ z 1 : t − 1 , x 1 : t ) = P ( z t ∣ z t − 1 ( i ) ) Q ( z t ∣ z 1 : t − 1 , x 1 : t ) = P ( z t ∣ z t − 1 ( i ) ) Q\left(z_{t} | z_{1: t-1}, x_{1: t}\right)=P\left(z_{t} | z_{t-1}^{(i)}\right) Q ( z t ∣ z 1 : t − 1 , x 1 : t ) = P ( z t ∣ z t − 1 ( i ) ) t t t z t ⟶ P ( z t ∣ Z t − 1 ( i ) ) , z_{t} \longrightarrow P\left(z_{t} | Z_{t-1}^{(i)}\right), z t ⟶ P ( z t ∣ Z t − 1 ( i ) ) , w t − 1 , w_{t-1}, w t − 1 , P ( x t ∣ z t ( i ) ) P\left(x_{t} | z_{t}^{(i)}\right) P ( x t ∣ z t ( i ) ) P ( x t ∣ z t ( i ) ) P\left(x_{t} | z_{t}^{(i)}\right) P ( x t ∣ z t ( i ) ) ( z t ∣ z 1 : t − 1 , x 1 : t ) = P ( z t ∣ z t − 1 ( i ) ) \left(z_{t} | z_{1: t-1}, x_{1: t}\right)=P\left(z_{t} | z_{t-1}^{(i)}\right) ( z t ∣ z 1 : t − 1 , x 1 : t ) = P ( z t ∣ z t − 1 ( i ) ) t t t
Sampling Importance Resampling Algorithm:t − 1 t-1 t − 1
Sampling:t t t N N N i = 1 , 2 , ⋯ , N : i=1,2, \cdots, N: i = 1 , 2 , ⋯ , N : z t ( i ) ∼ P ( z t ∣ z t − 1 ( i ) ) w t ( i ) ∝ P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) P ( z t ∣ z t − 1 ( i ) ) ⋅ w t − 1 ( i ) = P ( x t ∣ z t ( i ) ) ⋅ w t − 1 ( i )
\begin{array}{c}
z_{t}^{(i)} \sim P\left(z_{t} | z_{t-1}^{(i)}\right) \\
w_{t}^{(i)} \propto \frac{P\left(x_{t} | z_{t}^{(i)}\right) P\left(z_{t}^{(i)} | z_{t-1}\right)}{P\left(z_{t} | z_{t-1}^{(i)}\right)} \cdot w_{t-1}^{(i)}=P\left(x_{t} | z_{t}^{(i)}\right) \cdot w_{t-1}^{(i)}
\end{array}
z t ( i ) ∼ P ( z t ∣ z t − 1 ( i ) ) w t ( i ) ∝ P ( z t ∣ z t − 1 ( i ) ) P ( x t ∣ z t ( i ) ) P ( z t ( i ) ∣ z t − 1 ) ⋅ w t − 1 ( i ) = P ( x t ∣ z t ( i ) ) ⋅ w t − 1 ( i )
Normalized:w t ( i ) ⟶ w ^ t ( i ) , ∑ i = 1 N w ^ t ( i ) = 1
w_{t}^{(i)} \longrightarrow \hat{w}_{t}^{(i)}, \quad \sum_{i=1}^{N} \hat{w}_{t}^{(i)}=1
w t ( i ) ⟶ w ^ t ( i ) , i = 1 ∑ N w ^ t ( i ) = 1
Resampling:w ^ ^ t ( i ) = 1 N
\hat{\hat{w}}_{t}^{(i)}=\frac{1}{N}
w ^ ^ t ( i ) = N 1
