随机分析过滤理论研讨会

这些离散算法很有趣，因为它们在一个非常简单的框架中体现了HMM理论最强大的元素。这些方法易于实现，并已成为需要机器学习算法的appliedareas中的主力。滤波、平滑和参数估计的算法与连续模型中的算法类似，但在离散环境中，理解所需的理论背景最少。8.1滤波、平滑和预测方程让n表示离散时间，并假设Xn是一个未观测到的马尔可夫链，在离散状态空间中取S表示的值。让∧表示Xn的转移概率核，因此p（Xn+1=x）=Xv∈任意x的S∧（x | v）P（Xn=v）∈ S、 P（X=X）=P（X）。噪声测量以过程Yn的形式进行，过程Yn是Xn的非线性函数，加上一些噪声，Yn=h（Xn）+wn，其中wn是均值为零且方差γ>0的iid高斯随机变量。这个离散模型的主要特点是无记忆通道，它允许进程“忘记过去”：P（Yn，Xn=x | Xn-1=v，Y0:n-1） =P（Yn | Xn=x）∧（x | v）对于任意n≥ 0和所有x，v∈ S.8.1.1过滤过滤质量函数为πn（x）P（Xn=x | Y0：n）对于所有x∈ 通过应用Bayes规则和HMM的属性，我们能够分解πnas如下，πn（x）=P（Xn=x，Y0:n）P（Y0:n）=Pv∈SP（Yn，Xn=x | Xn-1=v，Y0:n-1） P（Xn）-1=v，Y0:n-1） P（Y0:n）=P（Yn | Xn=x）Pv∈SP（Xn=x | Xn-1=v）P（Xn-1=v，Y0:n-1） P（Y0:n）=P（Yn | Xn=x）Pv∈S∧（x | v）P（Xn）-1=v | Y0:n-1） P（Yn | Y0:n）-1） =P（Yn | Xn=x）Pv∈S∧（x | v）πn-1（v）Px∈snumerator无记忆通道允许在第二行和第三行之间进行调节。

过滤质量的这种递归分解是前向鲍姆韦尔奇方程，对于高斯观测噪声πn（x）=cnψn（x）Xv的系统，可以显式地写出∈S∧（x | v）πn-1（v）（8.1），其中Cn是归一化常数，ψnis是似然函数ψn（x）P（Yn | Xn=x）=exp(-伊恩- h（x）γ).等式（8.1）很方便，因为它可以使分布保持更新，而不必在新数据到达时重新计算旧的统计数据。在“实时”中，使用该算法跟踪X的最新动向是很有效的，但在新数据到达后，旧的过滤估计将不会是最优的。必须使用平滑分布来确定过去某个时间X的最佳估计。8.1.2平滑在收集数据之前的一段时间内，平滑质量函数为πN | N（x）。=P（Xn=x | Y0:N）。通过应用贝叶斯规则和模型的性质，光滑质量可以写成如下，πn | n（x）=P（Yn+1:n | Xn=x）πn（x）P（Yn+1:n | Y0:n）=Pv∈SP（Yn+1:N | Xn+1=v，Xn=x）λ（v | x）πN（x）P（Yn+1:N | Y0:N）=Pv∈SP（Yn+2:N | Xn+1=v）ψN+1∧（v | x）πN（x）P（Yn+2:N | Y0:N+1）P（Yn+1 | Y0:N）=Pv∈SP（Yn+2:N | Xn+1=v）ψN+1∧（v | x）πN（x）P（Yn+2:N | Y0:N+1）cn+1。(*)式中，cn+1是等式（8.1）中的归一化常数。现在假设我们定义了时间n之后事件的似然函数，αNn（x）=P（Yn+1:n | Xn=x）P（Yn+1:n | Y0:n），对于n<n，按照αNn的约定≡ 1.然后，平滑质量可以写成滤波质量与απn | n（x）=αNn（x）πn（x）的乘积，并从(*) 我们可以看到，αNNI由向后的Baum-WelchEquationαNn（x）=cn+1Xv递归给出∈SαNn+1（v）ψn+1（v）∧（v | x）。（8.2）显然，平滑分布的计算需要计算时间N之前的所有滤波分布，然后向后递归计算αN。

作为交换，X的估计序列将表明X所采取的路径比过滤估计所建议的路径更合理。8.1.3预测预测分布比平滑更容易计算。当n<n时，预测分布为πn | n（x）=P（XN=x | Y0:n），仅通过外推滤波分布πn | n（x）=Xv来计算∈S∧（x | v）πN-1 | n（v）=Xv∈S∧N-n（x | v）πn（v），其中∧n-N上的转移概率- n个时间步。如果Xnis是一个正的递归马尔可夫链，那么存在一个不变量，预测分布将收敛为N→ ∞. 在某些情况下，这种收敛发生的速率将与∧中的谱隙成正比。假设XNCA可以取m-多个有限状态中的一个，并且是一个只有1个通信类的循环马尔可夫链。让∧∈ Rm×mbe是x的转移概率矩阵，假设∧ji>0，那么p（Xn+1=xi | Xn=xj）=对于所有i，j≤ m、 那么预测分布是πN | N=πN∧N-nand将以与∧的第二特征值成正比的速率指数快速收敛到不变测度。要了解这是为什么，请考虑特征向量（ui）i的基础≤mof∧，其中一些可能是广义的，ui+1（λ- βiI）=对于某些i≥ 1.假设u是Xn的唯一不变质量函数，我们得到∧=u。根据Perron-Frobenius定理，我们可以对特征值进行排序，使1=β>|β|≥ |β| ≥ ··· ≥ |βm |，我们知道β是特征多项式的简单根，因此μ不是广义特征向量。从这里我们可以看到-klog kπn∧k- uk=-klog k（πn）- u）λkk=-klog k（au+au+…amum）∧kk=-klog kau+aβku+。amum∧kk~克洛格1+a |βk|~ |β| as k→ ∞.

λ的光谱带隙为1- |β|，从收敛速度来看，更大的谱隙意味着预测分布收敛到不变测度所需的时间更短。一般来说，如果存在整数k<∞ 其中∧kji>0表示所有i，j≤ m、 8.2学习参数的Baum-Welch算法假设我们对HMM有完全准确的先验知识是不现实的。然而，X的平稳性意味着我们可以观察到X的重复行为，尽管是通过噪声测量，但我们应该能够判断X占据部分状态空间的频率和它移动的频率。如果我们已经基于某种意义上“接近”的模型计算了平滑分布，那么我们应该有nnxn=1P（Xn=x | Y0:N）≈ u（x）（8.3）NNXn=1P（Xn=x，Xn-1=v | Y0:N）≈ ∧（x | v）u（v）（8.4），其中u是x的平稳律。通过Baum-Welch算法，我们实际上可以使用一些优化技术来找到一系列具有递增可能性的模型估计，结果表明，（8.3）和（8.4）与选择模型序列的最佳改进类似。考虑两个模型参数θ和θ。

Baum-Welch算法使用KullbackLeibler散度来比较两个模型，0≤ D（θkθ）=X~X∈SN+1Pθ（X0:N=~x，Y0:N）Pθ（Y0:N）logPθ（X0:N=~x，Y0:N）Pθ（Y0:N）Pθ（X0:N=~x，Y0:N）Pθ（Y0:N）！=logPθ（Y0:N）Pθ（Y0:N）+X~X∈SN+1Pθ（X0:N=~x，Y0:N）Pθ（Y0:N）对数Pθ（X0:N=~x，Y0:N）Pθ（X0:N=~x，Y0:N）.如果我们设置q（θkθ）=X~X∈SN+1Pθ（X0:N=~x，Y0:N）对数Pθ（X0:N=~x，Y0:N）,然后我们有一个简化的表达式，0≤ D（θkθ）=logPθ（Y0:N）Pθ（Y0:N）+Q（θkθ）- Q（θkθ）Pθ（Y0:N）和重新排列不等式Q（θkθ）- Q（θkθ）Pθ（Y0:N）≤ logPθ（Y0:N）Pθ（Y0:N）！，从中我们可以看出，Q（θkθ）>Q（θkθ）意味着θ的可能性大于θ。Baum-Welch算法使用该不等式作为迭代确定估计模型参数的标准的基础。该算法得到一个序列{θ`}\'，其q（θ`-1kθ`）≥ 所以它们的概率在增加，但有界，Pθ`-1（Y0:N）≤ Pθ`（Y0:N）≤ P^θmle（Y0:N），其中^θmle是θ的最大似然估计。因此，{θ`}将在θ处有一个极限*这样pθ*（Y0:N）=lim`Pθ（Y0:N），但可能是Pθ*（Y0:N）<P^θmle（Y0:N）（见图8.1）。图8.1:Baum-Welch参数估计序列的可能性越来越大，但该序列出现在局部最大值。在进行计算时，需要找到Q（θk·）的最大值（可能只是局部最大值）。

一阶条件是找到一个的好方法，使用HMMwe可以将Q（θkθ）扩展为显式形式，Q（θkθ）=X~X∈SN+1Pθ（X0:N=~x，Y0:N）（ψθ（~x）pθ（~x）+NXn=1logψθn（~xn）∧θ（~xn | ~xn）-1)),（8.5）从中我们可以看出，可以对θ进行微分，添加拉格朗日数，然后求解最优模型估计。Baum-Welch算法等价于期望最大化（EM）算法；EM算法使对数似然函数的期望值最大化，这相当于最大化Q，θ`=arg maxθEθ`-1hlogPθ（Y0:N，X0:N）Y0:Ni=arg maxθQ（θ`-1kθ）。8.2.1参数转移概率的模型重新估计假设Xn∈ Z、 转移概率由θ参数化∈ (0, ∞) 所以p（Xn+1=i | Xn=j）=c（θ）exp{-θ| i- j |}，i、 j∈ Z、 式中c（θ）=P∞我=-∞经验{-θ| i- j |}。忽略不依赖于θ的部分，对数似然为q（θkθ）=-NXn=1Eθhθ| Xn- Xn-1 |+对数c（θ）如果我们对θ进行微分，我们有以下一阶条件：，θQ（θkθ）=-NXn=1Eθ“| Xn- Xn-1|-Pi | i- j | exp{-θ| i- j |}c（θ）FYN#=0对于任何j∈ Z.一阶条件的解是满足θh | X的θ- X|X=ji=NNXn=1Eθh |Xn- Xn-1|有限状态马尔可夫链的任意j.8.2.2模型重估计∈ S={1，…，m}，所以p（Xn+1=i | Xn=j）=∧ji代表所有i，j∈ 我们将寻找一个序列∧（`），它使Q（λ）最大化(`-1） k·）受约束所有j的pi∧ji=1≤ m、 让δjbe为jthconstraint的拉格朗日乘子，一阶条件如下：，∧jiQ（λ）(`-1） k∧）- δjXr∧jr=∧jiQ（λ）(`-1） k∧）- δj=0。(**)乘以∧j求和i中的表达式(**) 变成0=Xi∧ji∧jiQ（λ）(`-1） k∧）- δj=Xi∧ji∧jiQ（λ）(`-1） k∧）- δj表示δj=Pi∧ji∧jiQ（λ）(`-1） k∧）。

乘(**) 通过∧j，然后重新排列项，发现必须在∧的集合中选择最佳∧（`）ji，使得∧ji=∧ji∧jiQ（λ）(`-1） k∧Pr∧jr∧jrQ（λ(`-1） k∧）。（8.6）现在，使用（8.5）中的展开式，Q（λ）的导数(`-1） k∧）关于∧ji，可计算如下：∧jiQ（λ）(`-1） k∧=E∧jilog P（Y0:N，X0:N |∧）Y0:N，λ(`-1)= E“NXn=1∧ji{Xn=i，Xn-1=j}Y0:N，λ(`-1） #=∧jiNXk=1P（Xn=i，Xn）-1=j | Y0:N∧(`-1） 通过将其代入方程（8.6），很容易看出解是∧（`）ji=PNn=1P（Xn=i，Xn）-1=j | Y0:N∧(`-1） ）Pinumerator（8.7），其中P（Xn=i，Xn-1=j | Y0:N∧(`-1） ）=αNn（i）ψn（i）∧(`-1） jiπn-1（j）。方程（8.7）也加强了∧ji的非负性，这是算法适定性所必需的。等式（8.7）相当于（8.3）和（8.4）中推测的估计值。8.3维特比算法有时更重要的是估计X的整个路径。维特比算法应用HMM的特性以及动态规划来寻找异常最优序列bv0:N∈ SN+1最大化关节后验概率bv0:N=（bV，…，bVN）。=arg max~x∈SN+1P（X0:N=~x，Y0:N）。给定数据Y0:N，平滑可用于“回顾”和估计Xnforsome N<N，但方程（8.1）或（8.2）都不是联合后验概率，这意味着它们无法告诉我们路径x的后验概率∈ SN+1。

如果我们需要计算X路径的后验分布，问题的大小将随着N呈指数增长，但是维特比算法允许我们在不实际计算所有路径的后验概率的情况下获得X路径的MAP估计器。HMM的无记忆通道允许我们在路径上写最大化作为嵌套的最大化，max~x∈SN+1P（X0:N=~ x，Y0:N）=最大值∈SψN（v）max~x∈SN∧（v | ~xN）-1） P（X0:N）-1=~x，Y0:N-1） =ψN（bVN）max~x∈SN∧（bVN | ~xN）-1） P（X0:N）-1=~x，Y0:N-1） ，（+）式中，ψ为似然，Cn为归一化常数，均来自（8.1）中的正向鲍姆韦尔奇方程。为了利用这种嵌套结构，它有助于定义以下递归函数φ（v）ψ（v）P（X=v）φn（v）ψn（v）maxx∧（v | x）φn-1（x），对于n=1，2，3，N.然后我们把φ放在（+）的嵌套结构上，并反向工作以获得最优路径，bVN=arg maxvφN（v）bVN=arg maxv∧（bVN+1 | v）φN（v），对于N=N- 1，N- 2.2，1，0thus在O（N）中获得最佳路径-许多计算。那得花点时间|S|N为了获得路径的后验分布，需要进行许多计算。我们对维特比算法感兴趣，主要是因为滤波和平滑算法返回的估计路径可能是9。φ中的非规范化概率很快就会下降到机器精度水平以下，因此最好考虑对数版本的维特比，logφ（v）=logψ（v）+log P（X=v）logφn（v）=logψn（v）+maxx{log∧（v|X）+logφn-1（x）}并在动态规划步骤中使用对数φn，bVN=arg maxvlogφn（v）bVN=arg maxvnlog∧（bVN+1 | v）+logφn（v）o，表示n=n-1，N- 2.2, 1, 0.第九章粒子滤波蒙特卡罗方法已经成为从HMM计算量的最常用方法，而且有充分的理由；事实上，它们是获得一致估计的快速有效的方法。

尤其是，粒子过滤器用于近似过滤预期。有类似的方法利用贝叶斯公式从HMM中获取样本，但“粒子滤波”意味着顺序蒙特卡罗（SIS）和抽样重要性抽样（SIR）应用于特定的HMM。9.1粒子滤波器支持X是一个未观测到的马尔可夫链，在状态空间中取值，用S表示。设∧表示Xn的跃迁密度的核，因此ddxp（Xn+1≤ x） =Z∧（x | v）P（Xn）∈ dv）对于任何x∈ S、 和ddxp（X≤ x） =p（x）。假设观测过程Yn是Xn的非线性函数，Yn=h（Xn）+wn，其中wn是均值为零且方差γ>0的iid高斯随机变量。在这种情况下，滤波器很容易被证明是一个密度函数，递归给出为πn+1（x）=cn+1ψn+1（x）Z∧（x | v）πn（v），其中cn+1是一个归一化常数，ψn+1是一个似然函数ψn+1（x）=exp(-Yn+1- h（x）γ),但是如果我们要使用这个递归表达式，就需要在S上建立某种正交网格。另一种方法是使用粒子。9.1.1序贯重要性抽样（SIS）理想情况下，我们能够直接从过滤分布中取样，以获得阿蒙特·卡洛估计值，PPX`=1g（x`n）≈ E[g（Xn）|FYn]，对于P-large，其中x`n~ iidπn（x）。然而，计算πnalso的困难也使得获得样本变得困难。然而，相对容易的是，我们可以从无条件分布中依次获得样本，然后以近似过滤器的方式分配权重。对于“=1,2,3,4，…”，每个粒子都是一条路径x`0:n，它是根据无条件分布x生成的`~ p（·）x`n~ ∧（·| x`n）-1） 对于n=1，2，3，N.那么对于P-多粒子和任何可积函数g，强大的数定律告诉我们ppx`=1g（x`0:N）→ E[g（X0:N）]几乎可以肯定为P→ ∞.给定Y0:n，让ω`n表示粒子的重要性权重。

我们将ω`nto定义为与第个粒子路径的可能性成比例，我们可以将其递归地写为其旧权重和一个似然函数的乘积：ω`n=cnP（Y0:n | X0:n=x`0:n）=cnψn（x`n）ω`n-1对于n=0,1,2,3。。。。。，n按照ω的约定`-1.≡ 1，Cn是一个归一化常数Cn=PX`=1ψn（x`n）ω`n-1.然后可积函数g（XN）的滤波期望可以用加权粒子一致地近似，PX`=1g（x`N）ω`N=PPP`=1g（x`N）P（Y0:N | X0:N=x`0:N）PPP`=1P（Y0:N | X0:N=x`0:N）→E“g（~XN）P（Y0:N | ~X0:N）FYN#E“P（Y0:N | | X0:N）FYN#=E[g（XN）| FYN]几乎可以肯定为P→ ∞ 通过SLLN，其中X0:Nis是一个分布（p，λ）且独立于（X0:N，Y0:N）的随机变量。9.1.2采样重要性重采样（SIR）当SIR与SIS一起使用时，我们对E[g（XN）|FYN]的估计变成了粒子滤波器。SIR基本上在时间n时对样本{x`0:n}调用一个引导。这个过程将把我们的采样资源重新分配到更可能接近真实信号的粒子上。调用时，SIR执行以下操作：算法1。长官，启动程序。对于“=1。P根据{ωn，…，ωPn}从{xn，…，xPn}中抽取一个随机变量x`，sirnfrom{xn，…，xPn}。结束于{xn，…，xPn}← {x1，sirn，…，xP，sirn}。{ωn，…，ωPn}← {1/P，…，1/P}。调用SIR的常见标准可能与粒子分布的熵近似有关。在执行SIR之前的任何时间n，熵定义为n=-X\'ω\'nlogω\'n≥ -logX`（ω\'n）！>所以最大化粒子分布的熵和最小化后验权重的平方和大致相同。