基于隐马尔可夫模型(hmm)的模式识别理论

基于隐马尔可夫模型（hmm）的模式识别理论报告人颜浩时间2011年4月21日地点实验室302概述基于隐马尔可夫模型（hmm）的模式识别方法在模式识别中有着广泛的应用。如语音识别、手写字识别、图想纹理建模与分类。hmm还被引入移动通信核心技术“多用户的检测”。近年来，另外在生物信息可学、故障诊断等领域也开始得到应用。近几年已经已被学者用于人脸识别的研究之中，是今年来涌现出来的优秀人脸识别方法之一。经过不断改进，尤其是最近的嵌入式隐马尔可夫模型（ehmm）已经在人脸识别方面取得很大的进展，经过实验，识别率较高，有很好的鲁棒性等优点。隐马尔可夫模型基本理论依据来源于随机过程中马尔可夫过程理论。马尔可夫及其马尔可夫过程马尔可夫（A.Markov，1856—1922）俄国数学家.他开创了一种无后效性随机过程的研究，即在已知当前状态的情况下，过程的未来状态与其过去状态无关，这就是现在大家熟悉的马尔可夫过程.马尔可夫的工作极大的丰富了概率论的内容，促使它成为自然科学和技术直接有关的最重要的数学领域之一.在工程技术方面目前已被广泛用于通信，模式识别方面。与马尔可夫过程相关的概念.随机变量与随机过程把随机现象的每个结果对应一个数，这种对应关系称为随机变量.例如某一时间内公共汽车站等车乘客的人数，电话交换台在一定时间内收到的呼叫次数等等，都是随机变量的实例.随机过程随机过程是一连串随机事件动态关系的定量描述.即和“时间”相关的随机变量。一般记为x(t)。比如在一天24小时，在每个整点时刻徐州火车站的旅客数量。马尔可夫过程与马尔可夫链设x(t)是一随机过程，过程在时刻t0+1所处的状态与时刻t0所处的状态相关，而与过程在时刻t0之前的状态无关，这个特性成为无后效性.无后效的随机过程称为马尔可夫过程(MarkovProcess).举例：比如在万恶的旧社会流离失所的百姓在每天的饥饿程度是一个随机过程。假如他们在t0时刻（今天）的饥饿状态是五分饱，他们在t0+1所（明天）的饥饿状态的概率取决于t0时刻（今天），而和t0时刻（今天）之前（昨天、前天。。。）无关。这样的一个随机过程就是一个马尔可夫过程。()xt()xt马尔可夫过程中的时间和状态既可以是连续的，又可以是离散的.我们称时间离散、状态离散的马尔可夫过程为马尔可夫链.在实际应用是使用马尔可夫链较多。如何在实际中使用马尔可夫链？马尔可夫链怎么很好地描述出来。即引入马尔可夫链转移矩阵.一个例子为了形象说明“状态”和“状态的转移”的概念，假设在一个水池中有三片荷叶，一只青蛙在三片荷叶之间跳跃玩耍，见图.观察青蛙的活动会发现青蛙的动作是随意的.为讨论方便，我们给荷叶编号，我们关心的是在一定时间内，它从一片荷叶跳到其他两片荷叶的转移结构.当青蛙在第1片荷叶上时，它下一步动作跳跃到第2、3片荷叶上或原地不动，只与现在的位置1有关，而与它以前跳过的路径无关.我们给出这只青蛙从各片荷叶上向另一片荷叶移动的转移图，见图.箭头表示跳跃的方向，数字表示跳跃的概率，白环表示青蛙保持不动.此图表明：在一定时间内，当青蛙开始时刻在第1片荷叶上时，它保持不动的概率为0.3，它跳跃到第2片荷叶上的概率为0.6，跳跃到第3片荷叶上的概率为0.1；当青蛙开始时刻在第2片荷叶上时，它保持不动的概率为0.4，它跳跃到第1片荷叶上的概率为0.2，跳跃到第3片荷叶上的概率为0.4；当青蛙开始时刻在第3片荷叶上时，它保持不动的概率为0.5，它跳跃到第1片荷叶上的概率为0.2，跳跃到第2片荷叶上的概率为0.3.我们以x(t)表示青蛙跳跃t次后所处的位置,x(t)的取值叫做状态，S={1,2,3}叫状态空间.我们称{x(t)}(t0)为一个随机过程.当从x(0)到x(t)已知时，青蛙在t+1时处在x(t+1)状态上的概率仅与t时刻状态有关，即满足以下关系式01{(1)(0),(1),...,()}{(1)()}PxtjxixixtiPxtjxti（1.1）我们称满足（8.1）式的随机过程{x(t)}(t0)为马尔可夫过程或马尔可夫链，而把（8.1）式的随机过程{x(t)}称为马尔可夫性，它反映了前一状态x(t-1)、现状态x(t)和后一状态x(t+1)之间的链接.因此，用马尔可夫链描述随机性状态变量的变化时，只需求在某一点上两个相邻随机变量的条件分布就可以了.我们称为转移概率.由于这种转移概率不依赖于时间，因此具有稳定性，我们用常数来表示.将各个状态之间的转移概率用一个矩阵表示出来，就得到一个马尔可夫链数学模型即（MarkovChainMode）：{(1)()}Pxtjxtiijp称矩阵为一步概率转移矩阵，简称转移矩阵.由于转移矩阵的每行都是独立的分布，所有每行的元素满足下列性质：111212122212.........nnnnnnppppppPppp10(,1,2,...,)1(1,2,...,)ijnijjpijnpin（1.2）（1.3）由图，青蛙跳跃的一步转移矩阵为1112132122233132330.30.60.10.20.40.40.20.30.5pppPpppppp引入这样的一个状态矩阵就能够将这个马尔可夫过程描述清楚。但是在模式识别领域，还不能直接使用马尔可夫过程，需要对之进行推广，即隐马尔可夫模型理论。目前隐马尔可夫模型理论和算法已经较为成熟。在模式识别领域有着很多成功的应用，尤其是语音识别。在人脸识别方面也取得很大的发展。下面介绍隐马尔可夫模型及其算法。在马尔可夫过程中一般情况下，只能观察到输出符号序列(ab)，而不能观测到状态之间如何转移（状态转移概率）和状态的分布（状态的概率），所以称为隐藏的马尔可夫模型。隐马尔可夫模型的定义球和缸S1SNS2P(red)=b1(1)P(yellow)=b1(2)P(bule)=b1(3)P(green)=b1(4)P(black)=b1(M)P(red)=b2(1)P(yellow)=b2(2)P(bule)=b2(3)P(green)=b2(4)P(black)=b2(M)P(red)=bN(1)P(yellow)=bN(2)P(bule)=bN(3)P(green)=bN(4)P(black)=bN(M)观察序列O={绿，绿，蓝，红，红，黄，…..蓝}设有N个缸，每个缸中装有很多彩色的球，不同颜色的球(M)的多少由一组概率分布来描述，根据某个初始概率分布，随机选择一个缸，例如第i个缸，再根据这个缸中彩色球颜色的概率分布，随机选择一个球，记O1,再把球放回缸中。根据缸的转移概率，选择下一个缸，例如第j个缸。再根据这个缸中彩色球颜色的概率分布，随机选择一个球，记O2,再把球放回缸中。最后得到描述球颜色的序列O1O2，成为观察值序列，但每次选取的缸和缸之间的转移并不能直接观察，被隐藏。解：输出aab，可能的状态序列（路径）如下，共有7种：S1S2S32.08.0ba3.011a4.022a7.03.0ba5.012a5.05.0ba2.013a6.023a[例]以下HMM中，设观察到的输出符号序列是aab。初始分布为[0.50.50],试求aab的输出概率？S1S2S3S1S2S3S3S2S10.30.50.20.40.60.30.50.20.40.6观察序列：O＝aabt=1t=2t=3初始分布π＝[0.50.50],各个状态序列（路径）产生O的概率为：P1:S1→S1→S10.5×0.8×0.3×0.8×0.3×0.2＝0.00576P2:S1→S1→S20.5×0.8×0.3×0.8×0.5×0.7＝0.0336P3:S1→S1→S30.5×0.8×0.3×0.8×0.2×0.5＝0.0096P4:S1→S2→S20.5×0.8×0.5×0.3×0.4×0.7＝0.0168P5:S1→S2→S30.5×0.8×0.5×0.3×0.6×0.5＝0.018P6:S2→S2→S20.5×0.3×0.4×0.3×0.4×0.7＝0.00504P7:S2→S2→S30.5×0.3×0.4×0.3×0.6×0.5＝0.0054由于是隐HMM模型，不知输出aab时，到底是经过了哪一条不同状态组成的路径，因此，求aab的输出概率时，将每一种可能路径的的输出概率相加得到的总的概率值作为aab的输出概率:P(O|λ)=0.00576+0.0336+0.0096+0.0168+0.018+0.00504+0.0054=0.09421.HMM包含两个随机过程：（1）马尔可夫链：一个随机过程描述的状态（S1,S2,S3）和状态转移序列（状态转移序列S1S1S2S3、S1S2S2S3和S1S1S1S3等）；（2）一个随机过程描述状态和观察值之间的统计对应关系（输出的符号组成的符号序列，如，aab）。总结各状态下输出符号的概率阵P32.HMM包含三个概率矩阵:11121321222331323311113330.30.50.2200.40.60000.80.230.30.70.50.5PaaaPaaaaaaP每个状态存在的概率矩阵P1状态之间转移的概率矩阵P2隐马尔可夫模型的参数{,,,,,}NMTAB模型中状态的数目。状态的集合N12{,,}NSSSS每个状态对应的观测符号数。观测符号集合M12{,,}MVvvv观测符号序列的长度，观测符号序列T12{,,}TOOOO状态转移概率分布A{},[],1,ijijjiAaaPSSijN状态的观测符号概率分布B{()},()[|],1,1jjkjBbkbkPvSjNkM初始状态的概率分布{},[],1iiiPSiN{,,}ABHMM的基本要素参数含义实例N状态数目缸的数目M每个状态可能的观察值数目彩球颜色数目A与时间无关的状态转移概率矩阵在选定某个缸的情况下，选择另一个缸的概率B给定状态下，观察值概率分布每个缸中的颜色分布初始状态空间的概率分布初始时选择某口缸的概率{,,,,,}NMTAB隐马尔可夫模型的基本算法识别问题：给定观测符号序列和模型，如何快速有效地计算输出概率估计模型产生观测符号序列的最有可能经过的路径。所有可能的路径中，概率最大的路径。模型训练问题：调整模型参数，使得输出概率最大。{,,}AB12{,,}TOOOO(/)PO1、前向－后向算法Forward-Backward给定一个观测序列以及一个模型，由模型产生出的概率直接方法，列举所有可能的路径，计算输出概率，然后求和。计算量为2TNT。如状态数N=5,观测值序列长度T=100，计算量为1072。前向－后向算法12{,,}TOOOO{,,}AB(/)PO√前向算法一个前向变量给定模型下，产生t以前的部分观测符号序列（包含t在内），且t时刻又处于状态的概率。迭代算法初始化：迭代计算：最后计算：()tai12()(,,;)ttiaiPOOOS12{,,}tOOOiS11()()1iiaibOiN11121()()()1NttijjtitTajaiabOjN1()()NTiPOai11()()1iiaibOiN1111121111()()()1(1)()(2)()()()NttijjtitjjttjjttNjjttTajaiabOjNaabOaabOaNabO初始状态和初始观测的联合概率。1OiS无论t时刻处于哪个状态，它都会以一定概率在t+1时刻转移到jSjSt+1t1S2S3SNS1ja2ja3jaNja()tijaia表示t时刻的观测的符号序列，并由t时刻转移到t+1时刻的状态发生的概率。12{,,}tOOOiSjS1()()NTiPOai1()N