機器學(xué)習(xí)-隱馬爾可夫模型課件

機器學(xué)習(xí)——

隱馬爾可夫模型目錄HMM的由來馬爾可夫性和馬爾可夫鏈HMM實例HMM的三個基本算法主要參考文獻HMM的由來

1870年，俄國有機化學(xué)家VladimirV.Markovnikov第一次提出馬爾科夫模型馬爾可夫模型馬爾可夫鏈隱馬爾可夫模型AndreiAMarkovGiftedRussianmathematicianJune14,1856-July20,1922

StPetersburgUniversityDoctoralAdvisor:PafnutyChebyshevAndreiAMarkovResearchfield:numbertheorycontinuousfractiontheorydifferentialequationsprobabilitytheorystatisticsMarkovisbestknownforhisworkinprobabilityandforstochasticprocessesespeciallyMarkovchains.Attheageof30MarkovbecameaprofessoratSt.PetersburgUniversityandamemberofSt.PetersburgAcademyofSciencesMorethan120scientificpapersClassicaltextbook“CalculusofProbabilities”PafnutyChebyshevOneofthefoundingfathersofRussianmathematicsHisfamousstudents:DmitryGraveAleksandrKorkin,AleksandrLyapunovAndreiMarkov……AccordingtotheMathematicsGenealogyProject,Chebyshevhasabout4,000mathematicaldescendants.Hisfamousworkinthefieldofprobability,statisticsandnumbertheory馬爾可夫性如果一個過程的“將來”僅依賴“現(xiàn)在”而不依賴“過去”，則此過程具有馬爾可夫性,或稱此過程為馬爾可夫過程X(t+1)=f(X(t))獨立事件概率設(shè)想我們再作一連串的實驗，而每次實驗所可能發(fā)生的結(jié)果定為E1,E2,…En,…。（可能是有限也可能是無限）。每一個結(jié)果Ek，我們?nèi)裟芙o定一個出現(xiàn)的可能性pk（即概率），則對某一特定樣本之序列Ej1

Ej2…Ejn，我們知道它出現(xiàn)的概率是p(Ej1

Ej2…Ejn)

=pj1…pjn。馬可夫鏈一般及常用的統(tǒng)計中，彼此相互「獨立」大概是最有用的一個觀念。用簡單的術(shù)語來說，互相「獨立」就是彼此毫不相干，一點牽涉都沒有。但是實際生活中很多事件是相互關(guān)聯(lián)的[不是互相獨立」也就是說互相關(guān)聯(lián)的意思，但是要怎樣相關(guān)呢？如何在相關(guān)中作一些簡單的分類呢？馬可夫連就是要描述在「相關(guān)」這個概念中最簡單的一種。但即使如此，有關(guān)馬可夫鏈的理論已經(jīng)相當(dāng)豐富了。在概率理論中，它幾乎占了絕大的部分。馬可夫鏈在馬可夫鏈中我們考慮最簡單的「相關(guān)」性。在在這種情況下，我們不能給任一個事件Ej

一個概率pj

但我們給一對事件(Ej,Ek)

一個概率pjk，這個時候pjk

的解釋是一種條件概率，就是假設(shè)在某次實驗中Ej

已經(jīng)出現(xiàn)，而在下一次實驗中Ek

出現(xiàn)的概率。除了pjk

之外，我們還需要知道第一次實驗中Ej

出現(xiàn)的機率aj。有了這些資料后，一個樣本序列Ej0

Ej1…Ejn（也就是說第零次實驗結(jié)果是Ej0，第一次一次是Ej1……第n

次實驗是Ejn）的概率就很清楚的是P(Ej0,Ej1,Ejn)=aj

pj0j1

pj1j2…pjn-1jn。

馬爾科夫鏈時間和狀態(tài)都離散的馬爾科夫過程稱為馬爾科夫鏈記作{Xn=X(n),n=0,1,2,…}在時間集T1={0,1,2,…}上對離散狀態(tài)的過程相繼觀察的結(jié)果鏈的狀態(tài)空間記做I={a1,a2,…},ai∈R.條件概率Pij(

m,m+n)=P{Xm+n=aj|Xm=ai}為馬氏鏈在時刻m處于狀態(tài)ai條件下，在時刻m+n轉(zhuǎn)移到狀態(tài)aj的轉(zhuǎn)移概率。

Weather:AMarkovModelExampleofMarkovModelSnowySunnyRainy60%2%38%20%75%5%80%15%5%MarkovModelStates:Statetransitionprobabilities:

representstheprobabilityofmovingfromstateitostatej

Initialstatedistribution:

MarkovModelBegins(t=1)insomeinitialstate(s).Ateachtimestep(t=1,2,…)thesystemmovesfromcurrenttonextstate(possiblythesameasthecurrentstate)accordingtotransitionprobabilitiesassociatedwithcurrentstate.States:Statetransitionprobabilities:Initialstatedistribution:WeatherMarkovModelGiventheweatheronthefirstday,whatistheprobabilitythattheweatherforconsecutivesixdays

BasicCalculations-1SnowySunnyRainyRainyRainyt=1t=2t=3t=4t=5t=6Snowy

BasicCalculations-2

Giventhatthesystemisinaknownwheathere.g.,whatistheprobabilitythatitstaysinthesamewheatherforconsecutiveddays:BasicCalculations-3

Conditionedonstartingtheweathere.g.,computetheexpectednumberofdurationinweatherExpectednumberofconsecutivedaysis5.

TheWorldisnotfullyobservable!!!HiddenMarkovModelNotObservable-Hidden60%2%38%20%75%5%80%15%5%ExampleofHiddenMarkovModel50%0%50%60%10%30%65%5%30%HMM實例

ObservedBallSequenceUrn3Urn1Urn2Veil又一個HMM實例HMM實例——描述設(shè)有N個缸，每個缸中裝有很多彩球，球的顏色由一組概率分布描述。實驗進行方式如下根據(jù)初始概率分布，隨機選擇N個缸中的一個開始實驗根據(jù)缸中球顏色的概率分布，隨機選擇一個球，記球的顏色為O1，并把球放回缸中根據(jù)描述缸的轉(zhuǎn)移的概率分布，隨機選擇下一口缸，重復(fù)以上步驟。最后得到一個描述球的顏色的序列O1,O2,…，稱為觀察值序列O。

HMM實例——約束

在上述實驗中，有幾個要點需要注意：不能被直接觀察缸間的轉(zhuǎn)移從缸中所選取的球的顏色和缸并不是一一對應(yīng)的每次選取哪個缸由一組轉(zhuǎn)移概率決定HMM概念HMM的狀態(tài)是不確定或不可見的，只有通過觀測序列的隨機過程才能表現(xiàn)出來觀察到的事件與狀態(tài)并不是一一對應(yīng)，而是通過一組概率分布相聯(lián)系

HMM是一個雙重隨機過程，兩個組成部分：

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

一般隨機過程：描述狀態(tài)與觀察序列間的關(guān)系，用觀察值概率描述。Markov鏈（,A）隨機過程（B）狀態(tài)序列觀察值序列q1,q2,...,qTo1,o2,...,oTHMM的組成示意圖HMM組成HMM的基本要素用模型五元組＝（N,M,π，A，B）用來描述HMM，或簡寫為=(π，A，B)參數(shù)含義實例N狀態(tài)數(shù)目缸的數(shù)目M每個狀態(tài)可能的觀察值數(shù)目彩球顏色數(shù)目A與時間無關(guān)的狀態(tài)轉(zhuǎn)移概率矩陣在選定某個缸的情況下，選擇另一個缸的概率B給定狀態(tài)下，觀察值概率分布每個缸中的顏色分布p初始狀態(tài)空間的概率分布初始時選擇某口缸的概率HMM可解決的問題問題1：給定觀察序列O=O1,O2,…OT,以及模型,如何計算P(O|λ)？問題2：給定觀察序列O=O1,O2,…OT以及模型λ,如何選擇一個對應(yīng)的狀態(tài)序列S=q1,q2,…qT，使得S能夠最為合理的解釋觀察序列O？問題3：如何調(diào)整模型參數(shù),使得P(O|λ)最大？解決問題1基礎(chǔ)方法給定一個固定的狀態(tài)序列S=(q1，q2，q3…)

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

N=5,M=100,=>計算量10^72解決問題1前向法動態(tài)規(guī)劃定義前向變量初始化：遞歸：終結(jié)：前向法示意圖1 ... t t+1 ...a1jat1qN.qi.qj..q1atNatiaNjaijN=5,M=100,=>計算量3000解決問題1后向法與前向法類似定義后向變量初始化：遞歸：終結(jié)：Viterbi算法目的：給定觀察序列O以及模型λ,如何選擇一個對應(yīng)的狀態(tài)序列S，使得S能夠最為合理的解釋觀察序列O？N和T分別為狀態(tài)個數(shù)和序列長度定義：我們所要找的，就是T時刻最大的所代表的那個狀態(tài)序列Viterbi算法(續(xù))初始化：遞歸：終結(jié)：求S序列：Baum-Welch算法(模型訓(xùn)練算法)目的：給定觀察值序列O，通過計算確定一個模型l，使得P(O|l)最大。算法步驟：

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

以及觀察值序列O，訓(xùn)練新模型

l；

3.如果log

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

4.否則，令l0＝l，繼續(xù)第2步工作

Baum-Welch算法(續(xù))定義：Baum-Welch算法(續(xù)2)參數(shù)估計：幾種典型形狀的馬爾科夫鏈a.A矩陣沒有零值的Markov鏈b.A矩陣有零