1、2023年8月2日星期三网络通信信道的隐马尔网络通信信道的隐马尔科夫模型科夫模型主要内容主要内容 需要解决的问题需要解决的问题 马尔科夫链马尔科夫链 隐马尔科夫链（隐马尔科夫链（HMM）利用利用HMM解决问题解决问题需要解决的问题需要解决的问题 IPPM定义了许多不同的端到端性能指标定义了许多不同的端到端性能指标 时延丢包率可用带宽时延抖动。?需要解决的问题需要解决的问题需要解决的问题需要解决的问题需要解决的问题需要解决的问题时延丢包率可用带宽时延抖动模模 型型马尔科夫链马尔科夫链马尔科夫链马尔科夫链 马尔可夫性马尔可夫性 如果一个过程的如果一个过程的“将来将来”仅依赖仅依赖“现在现在”而而不
2、依赖不依赖“过去过去”，则此过程具有，则此过程具有马尔可夫性，或称此过程为或称此过程为马尔可夫过程 X(t+1)=f(X(t)马尔科夫链马尔科夫链 时间和和状态都离散的马尔科夫过程称为都离散的马尔科夫过程称为马尔科马尔科夫链，夫链，记作记作Xn=X(n),n=0,1,2,在时间集在时间集T1=0,1,2,上对离散状态的过程相继上对离散状态的过程相继观察的结果观察的结果 链的状态空间记做链的状态空间记做I=a1,a2,aiR.条件概率条件概率Pij(m,m+n)=PXm+n=aj|Xm=ai 为马氏链在时刻为马氏链在时刻m处于状态处于状态ai条件下，在时刻条件下，在时刻m+n转移到状态转移到状态
3、aj的的转移概率。马尔科夫链马尔科夫链 转移概率矩阵转移概率矩阵阴天阴天晴天晴天下雨下雨 晴天晴天 阴天阴天 下雨下雨晴天晴天 0.50 0.25 0.25阴天阴天 0.375 0.25 0.375下雨下雨 0.25 0.125 0.625马尔科夫链马尔科夫链 转移概率矩阵转移概率矩阵 由于链在时刻由于链在时刻m从任何一个状态从任何一个状态ai出发，到另一时出发，到另一时刻刻m+n，必然转移到，必然转移到a1，a2，诸状态中的某一，诸状态中的某一个，所以有个，所以有当当Pij(m,m+n)与与m无关时，称马尔科夫链为无关时，称马尔科夫链为齐次马尔科夫链，通常说的马尔科夫链都是指齐次马尔，通常说
4、的马尔科夫链都是指齐次马尔科夫链科夫链1(,)1,1,2,ijjP m mniHMM实例实例 观察值序列观察值序列Urn 3Urn 1Urn 2VeilHMM实例实例 在上述实验中，有几个要点需要注意：缸间的转移不能被直接观察从缸中所选取的球的颜色和缸并不是 一一对应的每次选取哪个缸由一组转移概率决定HMM概念概念 HMM的状态是不确定或不可见的，只有的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来通过观测序列的随机过程才能表现出来 观察到的事件与状态并不是一一对应，而观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系是通过一组概率分布相联系 HMM是一个双重随机过程
5、，两个组成部是一个双重随机过程，两个组成部分：分：马尔可夫链：描述状态的转移，用：描述状态的转移，用转移概率描述描述 一般随机过程：描述状态与观察序列：描述状态与观察序列间的关系，间的关系，用用观察值概率描述描述HMM的基本要素的基本要素 用模型五元组用模型五元组（N,M,，A，B）用来）用来描述描述HMM，或简写为，或简写为=(，A，B)参数含义实例N状态数目状态数目缸的数目缸的数目M每个状态可能的观察值数每个状态可能的观察值数目目彩球颜色数目彩球颜色数目A与时间无关的状态转移概与时间无关的状态转移概率矩阵率矩阵在选定某个缸的情况下，在选定某个缸的情况下，选择另一个缸的概率选择另一个缸的概率
6、B给定状态下，观察值概率给定状态下，观察值概率分布分布每个缸中的颜色分布每个缸中的颜色分布p p初始状态空间的概率分布初始状态空间的概率分布初始时选择某口缸的概率初始时选择某口缸的概率HMM可解决的问题可解决的问题 问题问题1：给定观察序列：给定观察序列O=O1,O2,OT,以以及模型及模型=(，A，B),如何计算如何计算P(O|)？问题问题2：给定观察序列：给定观察序列O=O1,O2,OT以以及模型及模型,如何选择一个对应的状态序列如何选择一个对应的状态序列 S=q1,q2,qT，使得，使得S能够最为合理的能够最为合理的解释观察序列解释观察序列O？问题问题3：如何调整模型参数：如何调整模型参
7、数=(，A，B),使得使得P(O|)最大？最大？HMM建模建模 本文研究报文丢失过程及网络状态和参数本文研究报文丢失过程及网络状态和参数估计问题估计问题 使用使用open/close过程可以描述因特网中过程可以描述因特网中的报文丢失过程，但是有时候报文的丢失的报文丢失过程，但是有时候报文的丢失率会有较大的波动，作者认为网络信道具率会有较大的波动，作者认为网络信道具有隐藏的不同状态，在不同的状态下，报有隐藏的不同状态，在不同的状态下，报文的丢失率会有所不同，状态的转换会引文的丢失率会有所不同，状态的转换会引起丢失率的波动。起丢失率的波动。HMM建模建模 假定丢失过程为假定丢失过程为 ，如果第，如
8、果第t个报文个报文到达了接收端，则到达了接收端，则Xt=0，否则，否则Xt=1 马尔科夫链的状态空间为马尔科夫链的状态空间为S=1，2，3,K共有共有K个状态，它们之间的转换由马尔科夫链个状态，它们之间的转换由马尔科夫链Y=Yt所决所决定定 随机过程的状态转移矩阵表示为随机过程的状态转移矩阵表示为 其中其中 这个马尔科夫链是均匀的，各态遍历的，状态收敛这个马尔科夫链是均匀的，各态遍历的，状态收敛的，它的稳态分布表示为的，它的稳态分布表示为“”HMM建模建模 在每一种状态下，信道都会有在每一种状态下，信道都会有blocking和和passing两种状态两种状态 使用矩阵使用矩阵P来表示信道的丢失
9、概率，则有：来表示信道的丢失概率，则有：P=,(1=i=k)其中，其中，表示信道处于表示信道处于i状态时，第状态时，第t个报文丢失个报文丢失的概的概 率。率。HMM建模建模通 信 信 道 模 型状态个数状态个数K 状态转移矩阵状态转移矩阵 信道的丢失概率矩阵信道的丢失概率矩阵P HMM状态个数统计量状态个数统计量 为了给为了给HMM选择一个恰当的状态数目，选择一个恰当的状态数目，需要一个基于已经观察到的丢失过程需要一个基于已经观察到的丢失过程X的的无偏估计量。无偏估计量。离散型随机变量离散型随机变量X的熵定义为的熵定义为 稳态随机变量稳态随机变量X=Xi的熵定义为的熵定义为 1 J.Ziv a
10、nd N.Merhav.Estimating the number of states of a nite-state source,.IEEE Trans.Info.Theory,vol.IT-38:pp.61 65,January 1992.HMM状态个数统计量状态个数统计量 根据文献根据文献2中介绍的中介绍的AEP（渐进均分割（渐进均分割性），如果随机过程性），如果随机过程X是有限的、稳态的、是有限的、稳态的、各态遍历的，那么就会有下面的推导：各态遍历的，那么就会有下面的推导：根据前面的推导，作者定义了根据前面的推导，作者定义了HMM状态状态个数个数K的估计量公式的估计量公式 2 T.C
11、over and J.Thomas.Elements of Information theory.John Wiley and Sons,1991.HMM状态个数统计量状态个数统计量表示使用HMM描述通信信道时观察到的输出序列为x的概率 表示状态个数 n是一个任意的序列，它收敛于0，这个估计量在文献3中进行了介绍，它是一个一致的，并且是近似最优的估计量。这个式子确切的说就是在参数为这个式子确切的说就是在参数为，状态数为，状态数为j的情况下，的情况下，输出序列为输出序列为x的最大概率的最大概率1.如何选择参数如何选择参数，使得出现观察序列，使得出现观察序列x的可能性最大；的可能性最大；2.如何估
12、计随机过程的熵如何估计随机过程的熵H。使用文献使用文献4中介绍的通用压缩编码的方法（中介绍的通用压缩编码的方法（Lempel-Ziv）使用文献使用文献5中介绍的算术译码的方法来解决。中介绍的算术译码的方法来解决。3 J.Ziv and N.Merhav.Estimating the number of states of a nite-state source,IEEE Trans.Info.Theory,vol.IT-38:pp.61 65,January 1992.4 J.Ziv and A.Lempel.A universal algorithm for sequential data
13、compression.IEEE Trans.Info.Theory,vol.IT-23:pp.337 343,May 1977.5 A.Moat.Linear time adaptive arithmetic coding.IEEE Trans.Info.Theory,vol.IT-36:pp.401 406,March 1990.使用使用EM算法推断信道参数算法推断信道参数 由于马尔科夫链的状态是不明显的，必须使用由于马尔科夫链的状态是不明显的，必须使用隐藏在丢失过程中的信息来估计参数集合隐藏在丢失过程中的信息来估计参数集合。作者使用作者使用EM（最大似然估计）的方法来估计（最大似然估计）
14、的方法来估计这个参数集合。这个参数集合。EM算法是一个估计各种马尔算法是一个估计各种马尔科夫模型参数的最大似然估计方法。它有很多科夫模型参数的最大似然估计方法。它有很多的优点，特别是它的稳定性。每一次的反复都的优点，特别是它的稳定性。每一次的反复都将提高模型的似然度，这就保证了算法的收敛。将提高模型的似然度，这就保证了算法的收敛。推断信道状态推断信道状态 作者使用两种算法推断信道状态作者使用两种算法推断信道状态 MPM（Marginal Posterior Mode，边界，边界后验模式）后验模式）根据观察到的丢失过程来估计当前最有可能根据观察到的丢失过程来估计当前最有可能的状态的状态 Vite
15、rbi算法算法 使用丢失过程来估计最有可能的状态序列使用丢失过程来估计最有可能的状态序列MPM 时刻时刻t的最优状态估计值：的最优状态估计值：这个估计量可以用在自适应程序中，用来实这个估计量可以用在自适应程序中，用来实时的计算信道状态。可以将时的计算信道状态。可以将 作为网络拥塞作为网络拥塞的标识，它比使用单个报文判断网络状态要准确的标识，它比使用单个报文判断网络状态要准确很多。很多。Viterbi算法算法 MPM产生的是时刻产生的是时刻t的网络状态的网络状态 Viterbi算法产生的是较长时间段的网络算法产生的是较长时间段的网络状态序列状态序列验证验证 作者使用模拟数据和真实数据验证前面研作者使用模拟数据和真实数据验证前面研究的理论结果。究的理论结果。作者认为，只要使用四个以内的状态，就作者认为，只要使用四个以内的状态，就能描述几乎所有的丢失过程了。能描述几乎所有的丢失过程了。
