HMM馬爾科夫隨機場.ppt

隱馬爾可夫模型 Hidden Markov model,HMM的由來 馬爾可夫性和馬爾可夫鏈 HMM實例 HMM的三個基本算法 主要參考文獻,HMM的由來,1870年，俄國有機化學(xué)家Vladimir V. Markovnikov第一次提出馬爾科夫模型 馬爾可夫模型 馬爾可夫鏈 隱馬爾可夫模型,馬爾可夫性,如果一個過程的“將來”僅依賴“現(xiàn)在”而不依賴“過去”，則此過程具有馬爾可夫性,或稱此過程為馬爾可夫過程 X(t+1) = f( X(t) ),馬爾科夫鏈,時間和狀態(tài)都離散的馬爾科夫過程稱為馬爾科夫鏈 記作Xn = X(n), n = 0,1,2, 在時間集T1 = 0,1,2,上對離散狀態(tài)的過程相繼觀察的結(jié)果 鏈的狀態(tài)空間記做I = a1, a2, aiR. 條件概率Pij ( m ,m+n)=PXm+n = aj|Xm = ai 為馬氏鏈在時刻m處于狀態(tài)ai條件下，在時刻m+n轉(zhuǎn)移到狀態(tài)aj的轉(zhuǎn)移概率。,轉(zhuǎn)移概率矩陣,陰天,晴天,下雨,晴天 陰天 下雨 晴天 0.50 0.25 0.25 陰天 0.375 0.25 0.375 下雨 0.25 0.125 0.625,轉(zhuǎn)移概率矩陣(續(xù)),由于鏈在時刻m從任何一個狀態(tài)ai出發(fā)，到另一時刻m+n，必然轉(zhuǎn)移到a1，a2，諸狀態(tài)中的某一個，所以有 當(dāng)Pij(m,m+n)與m無關(guān)時，稱馬爾科夫鏈為齊次馬爾科夫鏈，通常說的馬爾科夫鏈都是指齊次馬爾科夫鏈。,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, ., qT,o1, o2, ., oT,HMM的組成示意圖,HMM組成,HMM的基本要素,用模型五元組 （ N, M, ，A，B）用來描述HMM，或簡寫為 =( ，A，B),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, = 計算量1072,解決問題1 前向法,動態(tài)規(guī)劃 定義前向變量 初始化： 遞歸： 終結(jié)：,前向法示意圖,1 . t t+1 .,a1j,at1,qN . qi . qj . . q1,atN,ati,aNj,aij,N=5, M=100, = 計算量3000,解決問題1 后向法,與前向法類似 定義后向變量 初始化： 遞歸： 終結(jié)：,Viterbi算法,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矩