隐马尔科夫模型一、引入二、定义三、隐马尔科夫模型的计算(1)估值问题(2)解码问题(3)训练问题四、隐马尔科夫各种结构H M M的由来☐1870年,俄国有机化学家V l a d i m i r V.M a r k o v n i k o v第一次提出马尔科夫模型☐马尔可夫模型和马尔可夫链☐ 隐式马尔可夫模型(H M M )马尔可夫性☐ 如果一个过程的“将来”仅依赖“现在”而不依赖“过去”,则此过程具有马尔可夫性,或称此过程为马尔可夫过程 ☐ X (t+1) = f(X(t))马尔可夫链☐ 时间和状态都离散的马尔科夫过程称为马尔科夫链。
设在时刻t 的随机变量用t S 表示,其观察值用t s 表示,则如果当11s S ,22s S =,……,t t s S =的前提下,11++=t t s S 的概率是如下式所示,则称为n 阶Markov过程。
)|()|(11111111tn t tn t t t t t t t sSs S P s S s S P +-+-++++===== (1)这里tS 1表示1S ,2S ,……,t S ,t s 1表示1s ,2s ,……,t s ,tt s S 11=表示11s S =,22s S =,……,t t s S =。
特别的当如下式成立时,则称其为1阶Markov 过程,又叫单纯马尔可夫过程。
)|()|(111111t t t t t t t t s S s S P s S s S P =====++++ (2)即:系统在任一时刻所处的状态只与此时刻的前一时刻所处的状态有关。
而且,为了处理问题方便,考虑式(2)右边的概率与时间无关的情况,即:)|[)1,(1i t j t ij s S s S P t t P ===++ (3)同时满足:0)1,(≥+ij t t P (4)∑==+Nj ij t t P 11)1,( (5) 这里ij t t P )1,(+是当时刻t 从状态i 到时刻t +1时的状态j 的转移概率,当这个转移概率是与时间无关的常数时,又叫S ,2S ,……是具有常数转移概率的Markov 过程。
隐式马尔可夫模型(H M M )HMM 类似于一阶Markov 过程。
不同点是HMM 是一个双内嵌式随机过程,即HMM 是由两个随机过程组成,一个是状态转移序列,它对应着一个单纯Markov 过程;另一个是每次转移时输出的符号组成的符号序列。
这两个随机过程,其中状态转移随机过程是不可观测的,只能通过另一个随机过程的输出观察序列观测。
设状态转移序列为S=T s s s 21,,输出的符号序列为O=1o ,T o o 2。
由于模型本身是看不见的,即模型的状态不为外界所见,只能根据观察序列推导出来,所以称为隐马尔可夫模型。
离散HMM 中的元素对于语音识别使用的HMM 可以用下面六个模型参数来定义,即:观察值序列 o 1, o 2, ..., o T图1 HMM 的组成示意图},,,,,{F B A O S M π=S :模型中状态的有限集合,即模型由哪几个状态组成。
设有N 个状态,S ={i s|i=1,2,……,N}。
记t 时刻模型所处状态为t s ,),,(1N ts s s ∈。
O :输出的观察值符号的集合,即每个状态对应的可能的观察值数目。
记M 个观察值为1o ,……,M o ,记t 时刻观察到的观察值为t o 其中1(,,)t M o o o ∈ 。
A :状态转移概率的集合。
所有转移概率可以构成一个转移概率矩阵,即:⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=NN N N a a a a A 1111其中ij a 是从状态i s 到状态j s 的转移概率,i ≤1,N j ≤且有10≤≤ij a ,∑==Nj ij a 11。
B :输出观测值概率的集合。
{()}j B b k =。
其中()[v |],1j t k t b k p o s j k M ===≤≤,其中V k k 表示第个观察符号根据B 可将HMM 分为连续型和离散型HMM 等。
()1j kb k =∑ (离散型HMM )()1jb k dk ∞-∞=⎰ (连续型HMM )π:系统初始状态概率的集合,}{i ππ=,i π表示初始状态是i s 的概率,即:1[],(1) 1i i P s i i N ππ==≤≤=∑ (6)F :系统终了状态的集合。
Markov 模型没有终了状态的概念,只是在语音识别里用的Markov 模型要设定终了状态。
π,F},为了便于表示,常用下面的形式表示一个HMM,这样,可以记一个HMM为M={S,O,A,B,π}。
HMM可以分为两部分,一个是Markov链,由π,A描述,产生的输出为状即简写为M={A,B,态序列。
另一个随机过程,由B描述,产生的输出为观察符号序列。
HMM:示例图2 两个状态的HMMHMM 的三个基本问题HMM 核心理论是解决三个基本问题: 1.已知观测序列O ={1o ,2o ……T o }和模型},,{πλB A =,如何有效计算在给定模型的条件下产生观测序列O 的条件概率)/(λO P 最大。
2.已知观测序列O ={1o ,2o ……T o }和模型},,{πλB A =,如何选择相应的在某种意义上最佳的(能最好解释观测序列的)状态序列S 。
3.如何调整模型参数},,{πλB A =以使条件概率(|)P O λ最大。
第一个问题是评估问题,实际就是一个识别的问题,即已知模型λ和一个观测序列O ,如何计算由该模型产生出该观测序列的概率(|)P O λ,问题1的求解能选择出与给定观测序列最匹配的模型。
第二个问题目的是找出模型中隐藏的部分,即找出正确的状态序列(),,k j i s s s ,这是一个典型的估计问题。
第三个问题是模型的参数最优化,通过训练自适应调整模型参数使之适应于训练序列并最优化,从而得到实际应用中最好的模型,这是一个参数训练问题。
三个问题对应算法分别为:前后向算法,Viterbi 算法和Baum-Welch 算法。
隐马尔可夫模型的计算以孤立词识别为例,设有W 个单词要识别,我们可预先得到这W 个词的标准样本,第一步就是为每一个词建立一个N 个状态的HMM 模型。
这就要用到问题3(给定观察下求模型参数)。
为了理解模型状态的物理意义,可利用问题二将每一个单词的状态序列分割为一些状态,再研究导致与每一状态响应的观察结果的那些特征。
最后,识别单词就要利用问题1,即对给定观察结果找出一个最合适的模型,使得(|)P O λ最大。
第一个问题的求解给定观察序列O ={1o ,2o ……T o }和模型},,{πλB A =,求解(|)P O λ,最直接的方法就是通过穷举所有的长度为T 状态序列。
共有TN 个状态序列,考虑其中一个:12S (...)T s s s =,1s 是初始状态。
给定S ,观察序列O 出现的概率为1(O|s,)(|,)Tt t t p p o s λλ==∏ (7)因为各观察量假设是统计独立的,因此得到:1212(O|s,)()()...()t s s s t p b o b o b o λ=⋅ (8)上面的状态序列的概率为:112231(s |)...T T s s s s s s s p a a a λπ-= (9)O 和S 的联合概率为:(O ,s |)(O |s ,)p pp λλλ= (10)将联合概率中的所有s 序列累加就得到O 的概率(给定模型参数)。
即:s(O|)(O|s,)(s |)all p p p λλλ=∑111221T 1212T ,,...,()()...()T TTs s s s s ss s s s s b o a b o a b o π-=∑(11)根据上式,要计算(O|)p λ,需要2TTN⋅规模的计算量。
如果对于N=5(状态数),T=100(观察量),需要2*100*51007210≈次计算。
前向-后向算法定义前向概率为:)(i t α=)|,(21λθi t t s o o o P =即状态模型为λ,部分观测序列为1o 2o ……t o ,且对应t 时刻HMM 的状态为i t s θ=时的概率,利用)(i t α计算输出条件概率)|(λO P 1.初始化11()(), 1i N i i i b o απ=≤≤ (12) 2.选代计算111()()() 1t T-1,1j N N t t ij j t i j i a b o αα++=⎡⎤=≤≤≤≤⎢⎥⎣⎦∑ (13)3.终止计算∑==Ni T i O P 1)()|(αλ (14)其中步骤2的迭代过程为前向算法的核心:时刻t+1的状态j 可由时刻t 的i 状态到达。
其中1i N ≤≤。
终止条件中:12()(...,|)T T T i p o o o s i αλ==。
(15)前向算法只需要2N T 次计算。
对于N=5,T=100,只需要3000次计算。
后向算法定义后向概率为12()(|,)t t t T t i i P o o o s βθλ++== ,计算过程同前向算法类似。
第二个问题的求解(Viterbi 算法)第二个问题是给定观察序列O 以及模型参数,选择相应的在某种意义上最佳的(能最好解释观测序列的)状态序列S 。
Viterbi 算法在最佳意义上确定一个状态序列S ,这个最佳的定义,是指使)|,(λO S P 最大时确定的序列。
定义)(i t δ为时刻t 沿一条路经1s 2s ……t s 且i t s θ=,产生出观测序列1o 2o ……t o 的最大概率,即有:12112112()max (,,|)t t t t i t s s s i P s s s s o o o δθλ--== (16)所以:1t+1()[max ()](o )t t ij j ij i a b δδ+=⋅ (17) 那么,求最佳状态序列S 的算法过程: 1.初始化N i 1 ),()(11≤≤=o b i i i πδ (18)1()0, 1i N i ψ=≤≤ (19)2.选代计算11()max[()](), 2t T,1j N t t ij j t i Nj i a b o δδ-≤≤=≤≤≤≤ (20) 11()arg max[()], 2t T,1j N t t ij i Nj i a ψδ-≤≤=≤≤≤≤ (21)3.终止计算)]([max 1*i P T Ni δ≤≤= (22))]([max arg 1*i s T Ni T δ≤≤= (23)4.状态序列求取**11(), 1,2,,1t t t s st T T ψ++==-- (24)其中:()t i δ为t 时刻处于i 状态时的累积输出概率,()t i ψ为t 时刻处于i 状态时的前序状态号,*t s 为最优状态序列中t 时刻所处的状态,*P 为最终的输出概率。