隱馬爾可夫模型

HiddenMarkovmodel目錄HMM的歷史HMM的由來HMM的表述HMM的分類HMM的應(yīng)用HMM的歷史70年代，由Baum等人創(chuàng)立HMM理論80年代，由Bell實(shí)驗(yàn)室的Rabiner等人對(duì)HMM進(jìn)行了深入淺出的介紹90年代，HMM被引入計(jì)算機(jī)文字識(shí)別和移動(dòng)通信核心技術(shù)“多用戶的檢測(cè)”近年來，HMM在生物信息科學(xué)、故障診斷等領(lǐng)域也開始得到應(yīng)用HMM的由來馬爾可夫性馬爾可夫鏈隱馬爾可夫模型馬爾可夫性如果一個(gè)過程的“將來”僅依賴“現(xiàn)在”而不依賴“過去”，則此過程具有馬爾可夫性,或稱此過程為馬爾可夫過程。由俄國(guó)數(shù)學(xué)家A.A.馬爾可夫與1907年提出。X(t+1)=f(X(t))現(xiàn)實(shí)中存在很多馬爾可夫過程馬爾可夫鏈時(shí)間和狀態(tài)都離散的馬爾可夫過程稱為馬爾可夫鏈記作{Xn=X(n),n=0,1,2,…}在時(shí)間集T1={0,1,2,…}上對(duì)離散狀態(tài)的過程相繼觀察的結(jié)果鏈的狀態(tài)空間記做I={a1,a2,…},ai∈R.條件概率Pij(

m,m+n)=P{Xm+n=aj|Xm=ai}為馬氏鏈在時(shí)刻m處于狀態(tài)ai條件下，在時(shí)刻m+n轉(zhuǎn)移到狀態(tài)aj的轉(zhuǎn)移概率。馬爾可夫鏈—轉(zhuǎn)移概率矩陣陰天晴天下雨

晴天陰天下雨晴天0.500.250.25陰天0.3750.250.375下雨0.250.1250.625馬爾可夫鏈—轉(zhuǎn)移概率矩陣性質(zhì)由于鏈在時(shí)刻m從任何一個(gè)狀態(tài)ai出發(fā)，到另一時(shí)刻m+n，必然轉(zhuǎn)移到a1，a2…，諸狀態(tài)中的某一個(gè)，所以有當(dāng)Pij(m,m+n)與m無關(guān)時(shí)，稱馬爾科夫鏈為齊次馬爾可夫鏈，通常說的馬爾科夫鏈都是指齊次馬爾科夫鏈。幾種典型形狀的馬爾可夫鏈(a)轉(zhuǎn)移矩陣沒有零值的Markov鏈(b)轉(zhuǎn)移矩陣有零值的Markov鏈(c)和(d)是左-右形式表示的Markov鏈HMM實(shí)例ObservedBallSequenceUrn3Urn1Urn2VeilHMM實(shí)例——描述設(shè)有N個(gè)缸，每個(gè)缸中裝有很多彩球，球的顏色由一組概率分布描述。實(shí)驗(yàn)進(jìn)行方式如下根據(jù)初始概率分布，隨機(jī)選擇N個(gè)缸中的一個(gè)開始實(shí)驗(yàn)根據(jù)缸中球顏色的概率分布，隨機(jī)選擇一個(gè)球，記球的顏色為O1，并把球放回缸中根據(jù)描述缸的轉(zhuǎn)移的概率分布，隨機(jī)選擇下一口缸，重復(fù)以上步驟。最后得到一個(gè)描述球的顏色的序列O1,O2,…，稱為觀察值序列O。HMM實(shí)例——約束在上述實(shí)驗(yàn)中，有幾個(gè)要點(diǎn)需要注意：不能被直接觀察缸間的轉(zhuǎn)移從缸中所選取的球的顏色和缸并不是一一對(duì)應(yīng)的每次選取哪個(gè)缸由一組轉(zhuǎn)移概率決定HMM概念HMM的狀態(tài)是不確定或不可見的，只有通過觀測(cè)序列的隨機(jī)過程才能表現(xiàn)出來觀察到的事件與狀態(tài)并不是一一對(duì)應(yīng)，而是通過一組概率分布相聯(lián)系

HMM是一個(gè)雙重隨機(jī)過程，兩個(gè)組成部分：

馬爾可夫鏈：描述狀態(tài)的轉(zhuǎn)移，用轉(zhuǎn)移概率描述。

一般隨機(jī)過程：描述狀態(tài)與觀察序列間的關(guān)系，用觀察值概率描述。HMM組成

HMM組成示意圖Markov鏈（,A）隨機(jī)過程（B）狀態(tài)序列觀察值序列q1,q2,...,qTo1,o2,...,oTHMM的表述用模型五元組λ

＝（N，M，π，A，B）用來描述HMM，或簡(jiǎn)寫為λ=(π，A，B)參數(shù)含義實(shí)例N狀態(tài)數(shù)目缸的數(shù)目M每個(gè)狀態(tài)可能的觀察值數(shù)目彩球顏色數(shù)目A與時(shí)間無關(guān)的狀態(tài)轉(zhuǎn)移概率矩陣在選定某個(gè)缸的情況下，選擇另一個(gè)缸的概率B給定狀態(tài)下，觀察值概率分布每個(gè)缸中的顏色分布p初始狀態(tài)空間的概率分布初始時(shí)選擇某口缸的概率HMM可解決的問題評(píng)估問題：給定觀察序列O=O1,O2,…OT,以及模型λ=(π，A，B),如何計(jì)算P(O|λ)？算法：Forward-Backward算法解碼問題：給定觀察序列O=O1,O2,…OT以及模型λ,如何選擇一個(gè)對(duì)應(yīng)的狀態(tài)序列S=q1,q2,…qT，使得S能夠最為合理的解釋觀察序列O？算法：Viterbi算法學(xué)習(xí)問題：如何調(diào)整模型參數(shù)λ=(π，A，B),對(duì)于給定觀測(cè)值序列O=O1,O2,…OT，使得P(O|λ)最大？算法：Baum-Welch算法

HMM的應(yīng)用(1)詞性標(biāo)注

已知單詞序列w1w2…wn，求詞性序列c1c2…cn HMM模型： 將詞性理解為狀態(tài) 將單詞理解為輸出值 訓(xùn)練： 統(tǒng)計(jì)詞性轉(zhuǎn)移矩陣aij和詞性到單詞的輸 出矩陣bik

求解：

Viterbi算法HMM的應(yīng)用(2)疾病分析

已知疾病序列w1w2…wn，求表征序列c1c2…cn對(duì)應(yīng)狀態(tài)轉(zhuǎn)移過程

HMM模型： 將每種疾病理解為狀態(tài) 將輸入的表征現(xiàn)象理解為輸出值 訓(xùn)練： 統(tǒng)計(jì)從一種疾病轉(zhuǎn)移到另一種疾病的轉(zhuǎn)移 矩陣aij和某一疾病呈現(xiàn)出某一癥狀的概率 矩陣bik

求解：

Viterbi算法HMM的三個(gè)基本問題評(píng)估問題解碼問題學(xué)習(xí)問題基本問題之一：評(píng)估問題給定一個(gè)固定的狀態(tài)序列Q=(q1，q2，q3…)

表示在qt狀態(tài)下觀測(cè)到Ot的概率

由此的復(fù)雜度：2T×NT,N=5,M=100,計(jì)算量10^72基本問題之一：前向算法定義前向變量初始化：遞歸：終結(jié)：復(fù)雜度：N2T基本問題之一：前向后向算法1 ... t t+1 ...a1jat1qN.qi.qj..q1atNatiaNjaij基本問題之一：后向算法與前向法類似，只是遞推方向不同.定義后向變量初始化：遞歸：終結(jié)：基本問題之一：后向算法后向算法示意圖：基本問題之二：Viterbi算法目的：給定觀察序列O以及模型λ,如何選擇一個(gè)對(duì)應(yīng)的狀態(tài)序列Q，使得Q能夠最為合理的解釋觀察序列O？N和T分別為狀態(tài)個(gè)數(shù)和序列長(zhǎng)度定義：我們所要找的，就是T時(shí)刻最大的所代表的那個(gè)狀態(tài)序列基本問題之二：Viterbi算法（續(xù)）初始化：遞歸：終結(jié)：求S序列：我們考慮計(jì)算t時(shí)刻到達(dá)狀態(tài)X的最可能的路徑；這條到達(dá)狀態(tài)X的路徑將通過t-1時(shí)刻的狀態(tài)A，B或C中的某一個(gè)。

因此，最可能的到達(dá)狀態(tài)X的路徑將是下面這些路徑的某一個(gè)

（狀態(tài)序列），…，A，X

（狀態(tài)序列），…，B，X

（狀態(tài)序列），…，C，X

我們想找到路徑末端是AX,BX或CX并且擁有最大概率的路徑。

即：Pr(到達(dá)狀態(tài)A最可能的路徑).Pr(X|A).Pr(觀察狀態(tài)|X)

因此，到達(dá)狀態(tài)X的最可能路徑概率是： 泛化得：基本問題之三：學(xué)習(xí)問題目的：給定觀察值序列O，通過計(jì)算確定一個(gè)模型l，使得P(O|l)最大。算法步驟：

1.初始模型（待訓(xùn)練模型）l0

, 2.基于l0以及觀察值序列O，訓(xùn)練新模型l0；

3.如果log

P(X|l)-log(P(X|l0)<Delta，說明訓(xùn)練已經(jīng)達(dá)到預(yù)期效果，算法結(jié)束。

4.否則，令l0＝l，繼續(xù)第2步工作定義：Baum-Welch算法(續(xù))參數(shù)估計(jì)：Baum-Welch算法(續(xù)2)HMM結(jié)構(gòu)全連接從左至右無跨越有跨越并行HMM認(rèn)為語音按時(shí)間順序，從相對(duì)穩(wěn)定的一段特性（狀態(tài)）隨機(jī)地過渡到另一段特性，每個(gè)狀態(tài)又隨機(jī)地輸出一個(gè)觀察值。HMM認(rèn)為語音t+1時(shí)刻的狀態(tài)由t時(shí)刻狀態(tài)的統(tǒng)計(jì)特性，即狀態(tài)轉(zhuǎn)移概率確定；這個(gè)狀態(tài)產(chǎn)生的輸出亦為隨機(jī)的，取決于該狀態(tài)生成語音觀察量的概率。無跨越模型符合人類的語音特點(diǎn)，廣泛應(yīng)用于語音識(shí)別中。有跨越用于反映音素在發(fā)音中可能被吸收或刪除的情況。TwotypesofHMMState-emissionHMM(Mooremachine):Theoutputsymbolisproducedbystates:Bythefrom-stateBytheto-stateArc-emissionHMM(Mealymachine):Theoutputsymbolisproducebytheedges;i.e.,bythe(from-state,to-state)pairs.Outputsymbolsaregenerated

bythefrom-statesStatesequence:X1,nOutputsequence:O1,no1onX1X2Xn…o2Outputsymbolsaregeneratedby

theto-statesStatesequence:X1,n+1Outputsequence:O1,no1onX2X3Xn+1…o2X1Arethetwotypesof

HMMsequivalent?Foreachstate-emissionHMM1,thereisanarc-emissionHMM2,suchthatforanysequenceO,P(O|HMM1)=P(O|HMM2).Thereverseisalsotrue.DHMM：離散的符號(hào)作為觀測(cè)量bj(x)bj(k)bj(x)CHMM：觀測(cè)量為連續(xù)概率密度函數(shù)每個(gè)狀態(tài)有不同的一組概率密度函數(shù)SCHMM：觀測(cè)量為連續(xù)概率密度函數(shù)所有狀態(tài)共享一組概率密度函數(shù)觀測(cè)序列概率表示方法HMM應(yīng)用中的問題//注：有些問題結(jié)合語音識(shí)別來具體解釋。梁大為初始模型選取多個(gè)觀察值序列訓(xùn)練數(shù)據(jù)下溢訓(xùn)練數(shù)據(jù)不足初始模型選取Baum-Welch算法的基礎(chǔ)參數(shù)。全局最大值與局部最大值

π和A的初值選取對(duì)結(jié)果影響不大。

π：π1=1

，πi=0。A：

B的初值對(duì)訓(xùn)練出的HMM參數(shù)影響較大。對(duì)離散HMM，可以采用均值或隨機(jī)設(shè)置；在連續(xù)HMM中，包含的參數(shù)越多越復(fù)雜，參數(shù)初值的設(shè)置對(duì)于迭代計(jì)算的結(jié)果越至關(guān)重要。語音單位較小時(shí)可以用手工對(duì)輸入的語音進(jìn)行狀態(tài)劃分并統(tǒng)計(jì)出相應(yīng)的概率分布作為初值；對(duì)于較大的語音單位，普遍采用分段K-均值算法。

將所有觀察值序列平均分為N段，每段對(duì)應(yīng)1個(gè)HMM狀態(tài)Xi；利用3-8所示分段K-均值算法對(duì)屬于每個(gè)狀態(tài)的所有序列分別進(jìn)行聚類，得到連續(xù)混合正態(tài)分布(GMM)，獲得初始參數(shù)。根據(jù)經(jīng)驗(yàn)、隨機(jī)或間隔選取M個(gè)點(diǎn)，分別作為高斯混合函數(shù)中M個(gè)類空間的中心點(diǎn)C1，C2，…，CM，其中表示Xi段中第j個(gè)類空間，該類中包含的觀察值個(gè)數(shù)記為；根據(jù)觀察值到各中心點(diǎn)最短的原則，將本段中的所有觀察值序列分配到類空間中去，并記類的根據(jù)上一過程中每個(gè)類所獲得的觀察值序列，計(jì)算新的中心點(diǎn)：將此段中所有觀察值序列到其對(duì)應(yīng)類中心距離的平方和作為算法收斂的條件。若與上一次循環(huán)相比，如果基本沒有變化，則算法收斂，轉(zhuǎn)入第8步，如果循環(huán)次數(shù)小于最大循環(huán)次數(shù)K，則轉(zhuǎn)入第4步繼續(xù)循環(huán)；根據(jù)上述循環(huán)計(jì)算得到的觀察值序列分別情況，利用下列公式，對(duì)狀態(tài)下的模型參數(shù)進(jìn)行初始化，其中，多個(gè)觀察值序列訓(xùn)練用N個(gè)觀察序列訓(xùn)練HMM時(shí)，要Baum-Welch算法的重估公式加以修正。設(shè)N個(gè)觀察序列為O(n)，n=1,2,…,N，其中假定各個(gè)觀察值序列相互獨(dú)立，則有重估公式修正為：數(shù)據(jù)下溢問題

在前向-后向算法中，計(jì)算前向概率變量和后向概率變量的過程中，每個(gè)參與運(yùn)算的乘積項(xiàng)都是小于1。在遞歸過程中，由于多項(xiàng)連乘，使得變量越來越小，可能會(huì)使數(shù)據(jù)無限地趨向于零，甚至?xí)鲇?jì)算機(jī)所能表示的范圍，帶來數(shù)據(jù)的溢出問題。每一步都除以一個(gè)小于1的標(biāo)定系數(shù)，使遞歸過程中的變量所處的數(shù)量級(jí)基本不變。最后，為了使最后結(jié)果不受標(biāo)定系數(shù)的影響再將標(biāo)定系數(shù)進(jìn)行分離。令t時(shí)刻的標(biāo)定系數(shù)為，標(biāo)定后的前向變量和后向變量為：