%\pagestyle{empty} \tableofcontents \newpage %\pagestyle{fancy} \setcounter{page}{1} %new page \clearpage
背景介绍}
Dynamic Model是在概率图模型中加入了时序的因素,所以样本之间不再是独立同分布(i.i.d)的,而是有依赖关系的。而Dynamic Model的一个主要特点是,混合模型。因为,我们看到的都是观测变量序列,而每一个观测变量都对应着一个隐变量,隐变量也被称之为系统变量(System Variable),所以有时我们也将Dynamic Model称之为State Space Model。
而Dynamic Model我们可以从两个假设,两个方程,三个问题的角度去分析。
两个假设}
这是有关Dynamic Model的两个假设,也是我们研究这个模型的前提条件。这两个假设可以大大的帮助我们简化模型:
1.\textbf{ 齐次Markov假设(无后向性):}未来与过去无关,只依赖与当前的状态。数学公式描述也就是。
P(it+1|it,it−1,⋯,i1,ot,⋯,o1)=P(it+1|it)- \textbf{观测独立假设:}当前时刻的观测变量只依赖于当前时刻的隐变量。
两个方程}
这两个方程分别描述的是,隐变量状态与状态之间的转移概率,由当前时刻隐变量推出当前时刻观测变量的概率,符合化描述如下所示:
\({zt=g(zt−1,μ,ξ)xt=h(zt,μ,δ)
三大类问题}
在Dynamic Model中,我们主要可以分为三大类问题。
隐马尔可夫模型(Hidden Markov Model)}
这个在之前的章节中,我们已经有了详细的讲解。主要特点就是,隐状态z之间是离散的,而观测变量s之间并没有限制。在Hidden Markov Model中,主要关注的是Decoding问题,也就是在已知观测序列的情况下,最大化可能的隐状态。
线性动态系统(Linear Dynamic System)}
线性动态系通常也被我们称为线性高斯系统,而线性高斯系统这个名字更加形象,而线性和高斯的来源主要如下所示:
\({zt=A⋅zt−1+B+ϵϵ∼N(0,Q)xt=C⋅zt+D+δδ∼N(0,R)
Filter问题的求解}
我们的求解目标是P(zt|x1,x2,⋯,xt)。
Step 1. Prediction:这个过程我们可以理解成给zt一个先验,
P(zt|x1,x2,⋯,xt−1)=∫zt−1P(zt|zt−1)P(zt−1|x1,x2,⋯,xt−1)dzt−1Step 2. Update:这个过程我们可以理解成给zt在已知xt之后的后验,
P(zt|x1,x2,⋯,xt)∝P(xt|zt)⋅P(zt|x1,x2,⋯,xt−1)Preiction的证明}
P(zt|x1,x2,⋯,xt−1)=∫zt−1P(zt,zt−1|x1,x2,⋯,xt−1)dzt−1=∫zt−1P(zt|zt−1,x1,x2,⋯,xt−1)P(zt−1|x1,x2,⋯,xt−1)dzt−1根据Markov齐次假设,$P(z_t | z_{t-1},x_1,x_2,\cdots,x_{t-1})=P(z_t | z_{t-1}),P(z_{t-1} | x_1,x_2,\cdots,x_{t-1})就是t-1$时刻的data。替换一下就可以得到公式(5)。 |
Update的证明}
首先,我们提一下,P(x1,x2,⋯,xt)这种,只和观察数据有关的概率分布都是可以计算出来的,我们都用不同的常数来表示。:
\(P(zt|x1,x2,⋯,xt)=P(zt,x1,x2,⋯,xt)P(x1,x2,⋯,xt)=1CP(zt,x1,x2,⋯,xt)=1CP(xt|zt,x1,x2,⋯,xt−1)⏟P(xt|zt)P(zt,x1,x2,⋯,xt−1)=1CP(xt|zt)P(zt|x1,x2,⋯,xt−1)P(x1,x2,⋯,xt−1)⏟const D=DCP(xt|zt)P(zt|x1,x2,⋯,xt−1)
由于多维Gaussian Distribution非常强大的自共轭性,所以条件概率,边缘概率,联合概率这些都是Gaussian Distribution的,所以可以将高维的高斯分布进行拆解成多个低维的来进行求解就会简单一点。而Linear Dynamic System也被称为Kalman Filter。
非线性动态系统(Non-Linear Dynamic System)}
Non-Linear Dynamic System和Linear Dynamic System区别是,相邻两个隐变量状态zt和zt−1之间的关系是任意的,而且,Noise也是Gaussian的。所以,无法使用Kalman Filter一样的方法得到解析解。所以,只能采用Monte-Carlo Sampling一样的采样方法来得出近似解。
Non-Linear没有那么好的特征,求不出,只能采样。在贝叶斯框架的Inference主要要求解的是一个后验分布$P(Z | X)。而这个分布主要是用来求解期望,\mathbb{E}_{z | x}[f(x)] = \int f(z)p(z | x)dx。如果,我们可以采取N个样本,z^{(i)}\sim P(Z | X),{ z^{(1)},z^{(2)},\cdots,z^{(N)} }。那么,我们就可以通过\frac{1}{N}\sum_{i=1}^N f(z^{(i)})$来求解。这就是最简单的Monte-Carlo Sampling的方法。 |
重要性采样(Importance Sampling)}
重要性采样并不是直接对概率分布进行采样,而是对提议(Proposal)分布进行采样。也就是:
Ep(z)[f(z)]=∫p(z)f(z)dz=∫p(z)q(z)q(z)f(z)dz=∫f(z)p(z)q(z)q(z)dz≈1NN∑i=1f(zi)p(zi)q(zi) (zi∼q(z), i=1,2,⋯,N)而这里的p(zi)q(zi)也就是Weight,用来平衡不同的概率密度值之间的差距。同样重要性采样也可能会出现一些问题,就是两个分布之间的差距太大了话,总是采样采不到重要的样本,采的可能都是实际分布概率值小的部分。也就是采样效率不均匀的问题。
{ 之后为了方便描述,我们用x1:t=x1,x2,⋯,xt。}
如果是在Filtering的问题中,目标是求解$P(z_t | x_{1:t})$,权值为: |
\(w(i)t=P(z(i)t|x1:t)Q(z(i)t|x1:t)
\(t=1: w(i)1, i=1,2,⋯,N∼w(1)1,w(2)1,⋯,w(N)1t=2: w(i)2, i=1,2,⋯,N∼w(1)2,w(2)2,⋯,w(N)2⋯⋯t=T: w(i)T, i=1,2,⋯,N∼w(1)T,w(2)T,⋯,w(N)T
顺序重要性采样(Sequential Importance Sampling)}
这个算法中的主要思想就是,找到$w^{(i)}T和w^{(i)}{T-1}$之间的一个递推关系式来简化计算。
在这个算法的开始,做出了一个我觉得有点神奇的铺垫。那就是将求解的重点做了一个转变:
\(P(zt|x1:t)⟶P(z1:t|x1:t)
而$P(z_{1:t} | x_{1:t})对应的权重w_t^{(i)}$为: |
\(w(i)t∝P(z(i)1:t|x1:t)Q(z(i)1:t|x1:t)
分子P(z(i)1:t|x1:t)解析}
P(z(i)1:t|x1:t)=P(z(i)1:t,x1:t)P(x1:t⏟C)=1CP(z(i)1:t,x1:t)=1CP(xt|z(i)1:t,x1:t−1)⏟P(xt|z(i)t)P(z(i)1:t,x1:t−1)=1CP(xt|z(i)t)P(z(i)t|z(i)1:t−1,x1:t−1)⏟P(z(i)t|zt−1)P(z(i)1:t−1,x1:t−1)=1CP(xt|z(i)t)P(z(i)t|zt−1)P(z(i)1:t−1,x1:t−1)=1CP(xt|z(i)t)P(z(i)t|zt−1)P(z(i)1:t−1|x1:t−1)P(x1:t−1)⏟D=DCP(xt|z(i)t)P(z(i)t|zt−1)P(z(i)1:t−1|x1:t−1)分母Q(z(i)1:t|x1:t)解析}
分母中,我们假设:
\(Q(z(i)1:t|x1:t)=Q(z(i)t|z(i)1:t−1,x1:t)Q(z(i)1:t−1|x1:t−1)
~\
所以,我们将分子和分母的解析结果汇总可以得到:
w(i)t∝P(z(i)1:t|x1:t)Q(z(i)1:t|x1:t)∝P(xt|z(i)t)P(z(i)t|zt−1)P(z(i)1:t−1|x1:t−1)Q(z(i)t|z(i)1:t−1,x1:t)Q(z(i)1:t−1|x1:t−1)=P(xt|z(i)t)P(z(i)t|zt−1)Q(z(i)t|z(i)1:t−1,x1:t)⋅w(i)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})是ProposalDistribution很简单,很好进行求解。那么对于在t时刻的N个值w_t^{(i)}$,我们不在需要一个个的进行计算了,使用迭代公式就可以很快的求得解。 |
算法小结}
我们反复强调过,求解后验概率分布P(Z|X)大多数时候都是为了求解期望EZ|X[f(Z)],而实际上期望的问题就是一个积分问题。为什么求期望这么的重要呢,我们仔细想想。求方差的过程本质上就是一个求期望的过程:Var[X]=E[X2]−[E[X]]2。而求边缘概率也可以转换成一个求期望的问题,本质上还是一个积分的问题。
前面在公式(16)中得到了,
\(w(i)t∝P(z(i)1:t|x1:t)Q(z(i)1:t|x1:t)∝P(xt|z(i)t)P(z(i)t|zt−1)Q(z(i)t|z(i)1:t−1,x1:t)⋅w(i)t−1
\qquad \textbf{Sequential Importance Sampling Algorithm:}
\qquad 前提:t−1时刻的采样都已经完成;
\qquad t时刻对于N个采样值,for i=1, 2,⋯, N:
z(i)t∼Q(zt|zt−1,x1:t)\qquad end
\qquad $w^{(i)}t归一化,令\sum{i=1}^N w^{(i)}_t=1$。
实际上就这么简单,归一化是为了方便计算和避免程序计算时出现精度问题,而且可以对值的范围进行约束。所以,公式(9)中,我们可以将最后的结果进行改写,可得:
\(1NN∑i=1f(z(i))w(i)=N∑i=1f(z(i))ˆw(i)
Sequential Importance Sampling中的问题}
Sequential Importance Sampling最大的问题就是\textbf{权值退化}。也就是w(i)t会变得越来越小。举个例子,假如有100个权值,有99个都趋向于0,中有1个趋向于1。这样当然会出问题。
而为什么会出现这个问题呢?由于高维空间的原因,我们需要更多的样本来反映空间的特征。样本不够就会忽略一些高维特征,导致某些维度特征接近0的情况出现。
那么,解决方法有三种:
-
采更多的样本;
-
Resampling的方法;
-
选择一个更好的Proposal Distribution Q(z)。
Sampling Importance Resampling (SIR)}
那么Resampling的方法如何来解决权值退化的方法?那就是舍弃权重。之前我们用Weight来代表一个粒子的重要程度,而Resampling就是通过用粒子数量来代替Weight的方法来表示重要程度。
SIR采样方法}
经过重要性采样后,我们得到了N个样本点,以及对应的权重。那么我用权重来作为采样的概率,重新测采样出N个样本。也就是如下图所示:
\begin{figure}[H] \centering \includegraphics[width=.5\textwidth]{微信图片_20191230154011.png} \caption{Sampling Importance Resampling示意图} \label{fig:my_label_1} \end{figure}通过二次采样可以降低采样不平衡的问题。至于为什么呢?大家想一想,我在这里表达一下自己的看法。p(zi)q(zi)是Weight,如果Weight比较大的话,说明p(zi)比较大而q(zi)比较的小,也就是我们通过q(zi)采出来的数量比较少。那么我们按权重再来采一次,就可以增加采到重要性样本的概率,成功的弥补了重要性采样带来的缺陷,有效的弥补采样不均衡的问题。
那么,权值大的样本我们就采样的比较多,权值小的样本就采样的比较少。这样就去掉了权值,换了一种方法等价的来表示重要程度。就可以解决权值退化的问题。
How to do it?}
具体实现的思路其实就很简单。那就是根据概率密度函数(pdf)来计算得到概率分布函数(cdf)。然后通过从[0,1]之间进行均匀采样,来得到相应的的值。这个,我们在Markov Chain Monte Carlo 01 Sampling Method的\textbf{概率分布采样}中已经做了详细的描述。
讲到这里,Sampling Importance Resampling (SIR)实际上就是一种Basis Particle Filter,也就是SIS+Resampling,这是一种基本可以work的算法。
找一个更好的Q(Z)}
选择Q(zt|z1:t−1,x1:t)=P(zt|z(i)t−1),用状态转移矩阵来进行定义,那么我们就可以将权值改写成:
\(w(i)t∝P(xt|z(i)t)P(z(i)t|zt−1)P(zt|z(i)t−1)⋅w(i)t−1=P(xt|z(i)t)⋅w(i)t−1
\(\begin{center} Sequential Importance Sampling + Resampling + $Q(z_t|z_{1:t-1},x_{1:t})=P(z_t|z_{t-1}^{(i)})$ \end{center}
我们用,{ generate and test},来描述这个过程非常的形象。Generate是$z_t\longrightarrow P(z_t | Z_{t-1}^{(i)}),也就是状态转移矩阵。而Test是w_{t-1},也就是P(x_t | z_t^{(i)})这个实际上就是发射矩阵,这个实际上是一举两得的作用。P(x_t | z_t^{(i)})越大一方面表示了发射矩阵的概率大;另一方面是表示了采样的权重很大,采出来的样本越重要,采样的效率越高。所以,Q(z_t | z_{1:t-1},x_{1:t})=P(z_t | z_{t-1}^{(i)})呢?因为在t$起到了一语双关的重用,实现了共同目标的优化。 |
Sampling Importance Resampling (SIR)总结}
\textbf{Sampling Importance Resampling Algorithm:}
前提:t−1时刻的采样都已经完成;
1.Sampling:
t时刻对于N个采样值,for i=1, 2,⋯, N:
z(i)t∼P(zt|z(i)t−1)end
- Normalized:
- Resampling:
-
Previous
Kalman_Filter_02_Model_Construction_and_Solution -
Next
Conditional_Random_Field_01_Background