网络通信信道的隐马尔科夫模型

HiddenMarkovModelingfornetworkcommunicationchannels网络通信信道的隐马尔科夫模型Authors：KavéSalamatian、SandrineVatonPresentedby：Xubo2008年7月15日网络通信信道的隐马尔科夫模型2主要内容•需要解决的问题•马尔科夫链•隐马尔科夫链（HMM）•利用HMM解决问题网络通信信道的隐马尔科夫模型3需要解决的问题•IPPM定义了许多不同的端到端性能指标时延丢包率可用带宽时延抖动。。。。。。?????网络通信信道的隐马尔科夫模型4需要解决的问题网络通信信道的隐马尔科夫模型5需要解决的问题网络通信信道的隐马尔科夫模型6需要解决的问题时延丢包率可用带宽时延抖动模型网络通信信道的隐马尔科夫模型7马尔科夫链•1870年，俄国有机化学家VladimirV.Markovnikov第一次提出马尔科夫模型网络通信信道的隐马尔科夫模型8马尔科夫链•马尔可夫性–如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马尔可夫性，或称此过程为马尔可夫过程–X(t+1)=f(X(t))网络通信信道的隐马尔科夫模型9马尔科夫链•时间和状态都离散的马尔科夫过程称为马尔科夫链，记作{Xn=X(n),n=0,1,2,…}–在时间集T1={0,1,2,…}上对离散状态的过程相继观察的结果•链的状态空间记做I={a1,a2,…},ai∈R.•条件概率Pij(m,m+n)=P{Xm+n=aj|Xm=ai}为马氏链在时刻m处于状态ai条件下，在时刻m+n转移到状态aj的转移概率。网络通信信道的隐马尔科夫模型10马尔科夫链•转移概率矩阵阴天晴天下雨晴天阴天下雨晴天0.500.250.25阴天0.3750.250.375下雨0.250.1250.625网络通信信道的隐马尔科夫模型11马尔科夫链•转移概率矩阵–由于链在时刻m从任何一个状态ai出发，到另一时刻m+n，必然转移到a1，a2…，诸状态中的某一个，所以有–当Pij(m,m+n)与m无关时，称马尔科夫链为齐次马尔科夫链，通常说的马尔科夫链都是指齐次马尔科夫链1(,)1,1,2,ijjPmmni网络通信信道的隐马尔科夫模型12HMM实例观察值序列Urn3Urn1Urn2Veil网络通信信道的隐马尔科夫模型13HMM实例•在上述实验中，有几个要点需要注意：–缸间的转移不能被直接观察–从缸中所选取的球的颜色和缸并不是一一对应的–每次选取哪个缸由一组转移概率决定网络通信信道的隐马尔科夫模型14HMM概念•HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来•观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系•HMM是一个双重随机过程，两个组成部分：–马尔可夫链：描述状态的转移，用转移概率描述–一般随机过程：描述状态与观察序列间的关系，用观察值概率描述网络通信信道的隐马尔科夫模型15HMM的基本要素•用模型五元组λ＝（N,M,π，A，B）用来描述HMM，或简写为λ=(π，A，B)参数含义实例N状态数目缸的数目M每个状态可能的观察值数目彩球颜色数目A与时间无关的状态转移概率矩阵在选定某个缸的情况下，选择另一个缸的概率B给定状态下，观察值概率分布每个缸中的颜色分布p初始状态空间的概率分布初始时选择某口缸的概率网络通信信道的隐马尔科夫模型16HMM可解决的问题•问题1：给定观察序列O=O1,O2,…OT,以及模型λ=(π，A，B),如何计算P(O|λ)？•问题2：给定观察序列O=O1,O2,…OT以及模型λ,如何选择一个对应的状态序列S=q1,q2,…qT，使得S能够最为合理的解释观察序列O？•问题3：如何调整模型参数λ=(π，A，B),使得P(O|λ)最大？网络通信信道的隐马尔科夫模型17HMM建模•本文研究报文丢失过程及网络状态和参数估计问题•使用open/close过程可以描述因特网中的报文丢失过程，但是有时候报文的丢失率会有较大的波动，作者认为网络信道具有隐藏的不同状态，在不同的状态下，报文的丢失率会有所不同，状态的转换会引起丢失率的波动。网络通信信道的隐马尔科夫模型18HMM建模•假定丢失过程为，如果第t个报文到达了接收端，则Xt=0，否则Xt=1•马尔科夫链的状态空间为S={1，2，3,……,K}共有K个状态，它们之间的转换由马尔科夫链Y={Yt}所决定•随机过程的状态转移矩阵表示为其中•这个马尔科夫链是均匀的，各态遍历的，状态收敛的，它的稳态分布表示为“π”网络通信信道的隐马尔科夫模型19HMM建模•在每一种状态下，信道都会有blocking和passing两种状态•使用矩阵P来表示信道的丢失概率，则有：P=,(1=i=k)其中，表示信道处于i状态时，第t个报文丢失的概率。网络通信信道的隐马尔科夫模型20HMM建模通信信道模型状态个数K状态转移矩阵Γ信道的丢失概率矩阵P网络通信信道的隐马尔科夫模型21HMM状态个数统计量•为了给HMM选择一个恰当的状态数目，需要一个基于已经观察到的丢失过程X的无偏估计量。•离散型随机变量X的熵定义为•稳态随机变量X={Xi}的熵定义为[1]J.ZivandN.Merhav.Estimatingthenumberofstatesofanite-statesource,.IEEETrans.Info.Theory,vol.IT-38:pp.61{65,January1992.网络通信信道的隐马尔科夫模型22HMM状态个数统计量•根据文献[2]中介绍的AEP（渐进均分割性），如果随机过程X是有限的、稳态的、各态遍历的，那么就会有下面的推导：•根据前面的推导，作者定义了HMM状态个数K的估计量公式[2]T.CoverandJ.Thomas.ElementsofInformationtheory.JohnWileyandSons,1991.网络通信信道的隐马尔科夫模型23HMM状态个数统计量表示使用HMM描述通信信道时观察到的输出序列为x的概率表示状态个数n是一个任意的序列，它收敛于0，这个估计量在文献[3]中进行了介绍，它是一个一致的，并且是近似最优的估计量。这个式子确切的说就是在参数为θ，状态数为j的情况下，输出序列为x的最大概率1.如何选择参数θ，使得出现观察序列x的可能性最大；2.如何估计随机过程的熵H。•使用文献[4]中介绍的通用压缩编码的方法（Lempel-Ziv）•使用文献[5]中介绍的算术译码的方法来解决。[3]J.ZivandN.Merhav.Estimatingthenumberofstatesofanite-statesource,IEEETrans.Info.Theory,vol.IT-38:pp.61{65,January1992.[4]J.ZivandA.Lempel.Auniversalalgorithmforsequentialdatacompression.IEEETrans.Info.Theory,vol.IT-23:pp.337{343,May1977.[5]A.Moat.Lineartimeadaptivearithmeticcoding.IEEETrans.Info.Theory,vol.IT-36:pp.401{406,March1990.网络通信信道的隐马尔科夫模型24使用EM算法推断信道参数•由于马尔科夫链的状态是不明显的，必须使用隐藏在丢失过程中的信息来估计参数集合θ。•作者使用EM（最大似然估计）的方法来估计这个参数集合。EM算法是一个估计各种马尔科夫模型参数的最大似然估计方法。它有很多的优点，特别是它的稳定性。每一次的反复都将提高模型的似然度，这就保证了算法的收敛。网络通信信道的隐马尔科夫模型25推断信道状态•作者使用两种算法推断信道状态–MPM（MarginalPosteriorMode，边界后验模式）根据观察到的丢失过程来估计当前最有可能的状态–Viterbi算法使用丢失过程来估计最有可能的状态序列网络通信信道的隐马尔科夫模型26MPM•时刻t的最优状态估计值：这个估计量可以用在自适应程序中，用来实时的计算信道状态。可以将作为网络拥塞的标识，它比使用单个报文判断网络状态要准确很多。网络通信信道的隐马尔科夫模型27Viterbi算法•MPM产生的是时刻t的网络状态•Viterbi算法产生的是较长时间段的网络状态序列网络通信信道的隐马尔科夫模型28验证•作者使用模拟数据和真实数据验证前面研究的理论结果。•作者认为，只要使用四个以内的状态，就能描述几乎所有的丢失过程了。网络通信信道的隐马尔科夫模型29