隱馬爾可夫模型

隱馬爾可夫模型

HiddenMarkovModel(HMM)2011602124陳川隱馬爾可夫模型隱馬爾可夫模型（HiddenMarkovModel,HMM)是由馬爾科夫鏈發(fā)展擴(kuò)充而來(lái)的一種隨機(jī)模型，描述一個(gè)含有隱含未知參數(shù)的馬爾可夫過程。馬爾可夫過程:如果一個(gè)過程的“將來(lái)”僅依賴“現(xiàn)在”而不依賴“過去”，則此過程具有馬爾可夫性,此過程稱為馬爾可夫過程馬爾科夫鏈:時(shí)間和狀態(tài)都離散的馬爾科夫過程

{Xt,Yt}包含兩部分:一個(gè)潛在的、不可觀察的（故而稱為隱的）有限狀態(tài)馬爾科夫鏈{Xt}和一個(gè)外線的、可觀察的隨機(jī)過程{

Yt},Yt

的分布依賴于Xt。隱馬爾可夫模型HMM是用概率統(tǒng)計(jì)方法來(lái)描述時(shí)變信號(hào)的過程。它是一個(gè)動(dòng)態(tài)的統(tǒng)計(jì)模型，可以用有限狀態(tài)機(jī)（FiniteStateMachine，F(xiàn)SM）來(lái)描述。有限狀態(tài)機(jī)可以從一個(gè)狀態(tài)轉(zhuǎn)到另一個(gè)狀態(tài)，每個(gè)狀態(tài)轉(zhuǎn)換有不同的概率。某狀態(tài)是否轉(zhuǎn)移到下個(gè)狀態(tài)取決于該狀態(tài)的狀態(tài)轉(zhuǎn)移概率，而在某一狀態(tài)能看到哪個(gè)觀測(cè)值，也取決于該狀態(tài)的觀測(cè)概率。HMM可以被理解為一個(gè)雙重隨機(jī)過程，一個(gè)是系統(tǒng)狀態(tài)變化的過程，另一個(gè)是有狀態(tài)決定輸出的隨機(jī)過程。通常記HMM模型為λ＝（A，B，π），其中A為狀態(tài)轉(zhuǎn)移概率，B為觀察概率矩陣，π為初始狀態(tài)分布。HMM模型的建模工作主要為確定這三個(gè)參數(shù)。隱馬爾可夫模型狀態(tài)變遷圖（例子）

x—隱含狀態(tài)

y—可觀察的輸出

a—轉(zhuǎn)換概率（transitionprobabilities）

b—輸出概率（outputprobabilities）隱馬爾可夫模型隱馬爾可夫模型上邊的圖示強(qiáng)調(diào)了HMM的狀態(tài)變遷。有時(shí)，明確的表示出模型的演化也是有用的,我們用x（t1）與x（t2）來(lái)表達(dá)不同時(shí)刻t1

和t2的狀態(tài)。在這個(gè)圖中,每一個(gè)時(shí)間塊（x(t),y(t)）都可以向前或向后延伸。通常，時(shí)間的起點(diǎn)被設(shè)置為t=0或t=1.使用HMM解決的問題測(cè)評(píng)問題Evaluation:已知模型λ和輸出序列O，求由λ生成O的概率

譯解問題Decoding:已知模型λ和輸出序列O，求最有可能生成O的狀態(tài)轉(zhuǎn)移序列

學(xué)習(xí)問題Learning:已知模型λ和輸出序列O，求最有可能生成Ｏ的模型的參數(shù)隱馬爾可夫模型的應(yīng)用語(yǔ)音識(shí)別、光學(xué)字符識(shí)別

機(jī)器翻譯

生物信息學(xué)和基因組學(xué)基因組序列中蛋白質(zhì)編碼區(qū)域的預(yù)測(cè)對(duì)于相互關(guān)聯(lián)的DNA或蛋白質(zhì)族的建模從基本結(jié)構(gòu)中預(yù)測(cè)第二結(jié)構(gòu)元素

HMM的優(yōu)點(diǎn)

模擬蛋白質(zhì)家族對(duì)數(shù)據(jù)庫(kù)進(jìn)行搜索進(jìn)行多序列比對(duì)用于基因?qū)ふ业鞍踪|(zhì)二級(jí)結(jié)構(gòu)預(yù)測(cè)跨膜片段預(yù)測(cè)

HMM的缺點(diǎn)

訓(xùn)練所用的樣本數(shù)有限

HMM是一個(gè)線性模型，不能描述蛋白質(zhì)序列中的高階相關(guān)性只有當(dāng)事件獨(dú)立時(shí)，模型產(chǎn)生一個(gè)序列的概率才是產(chǎn)生各個(gè)獨(dú)立氨基酸的概率的乘積

分值計(jì)算方法的差異會(huì)影響序列預(yù)測(cè)的結(jié)果閾值的選取

ProfileHMM起始結(jié)束

ProfileHMM

圖是HMM的狀態(tài)轉(zhuǎn)移圖，圖中幾何圖形表示模型的不同狀態(tài)，各狀態(tài)間的箭頭表示狀態(tài)間的轉(zhuǎn)換途徑。方形代表匹配狀態(tài)（主狀態(tài)），即輸出的氨基酸和基本序列中對(duì)應(yīng)的氨基酸匹配。圓形表示刪除或缺失狀態(tài)，也就是從原始蛋白質(zhì)序列中去掉一個(gè)特定的氨基酸。菱形表示氨基酸的插入，即在原始蛋白質(zhì)序列中插入一個(gè)氨基酸?！捌鹗肌焙汀敖Y(jié)束”兩個(gè)空態(tài)，它們并不產(chǎn)生任何氨基酸。匹配狀態(tài)和插入狀態(tài)與輸出概率相關(guān)，意味著20種氨基酸種哪一種可能發(fā)生輸出概率在狀態(tài)轉(zhuǎn)移的規(guī)則中是隱含的，這也是“隱”馬爾可夫模型名字由來(lái)。

家族成員

位置

12345CCGTLCGHSVGCGSLCGGTLCCGSS0.80.6———0.20.40.8————0.2—————0.60.2———0.4—————0.6————0.212345氨基酸C出現(xiàn)的概率，Prob（C）氨基酸G出現(xiàn)的概率，Prob（G）氨基酸H出現(xiàn)的概率，Prob（H）氨基酸S出現(xiàn)的概率，Prob（S）氨基酸T出現(xiàn)的概率，Prob（T）氨基酸L出現(xiàn)的概率，Prob（L）氨基酸V出現(xiàn)的概率，Prob（V）位置

使用HMM

給序列打分0.4C0.05C0.3a0.01y起始—結(jié)束0.490.40.30.480.480.270.30.460.50.0150.0150.490.4800.70.970.970.060.060.460.460.30.0150.0150.050.060.0150.731蛋白質(zhì)ＡＣＣＹ的一個(gè)可能的ＨＭＭ我們可以用訓(xùn)練好的ＨＭＭ對(duì)序列進(jìn)行打分，根據(jù)分值來(lái)衡量這條序列是否屬于由此ＨＭＭ代表的蛋白質(zhì)家族。得分高于閾值，證明這條序列是這個(gè)家族的成員；得分低于閾值，說明它不是家族的成員。HMM用于分析蛋白質(zhì)序列的原理是分析蛋白質(zhì)產(chǎn)生不同序列的概率。對(duì)于給定的模型，計(jì)算產(chǎn)生某條序列的概率就是計(jì)算這條路徑上所有輸出概率和轉(zhuǎn)移概率的乘積。上圖示的HMM，是產(chǎn)生氨基酸序列ACCY的路徑已被加粗。標(biāo)出了感興趣的氨基酸殘基的輸出概率，第一個(gè)插入狀態(tài)輸出殘基A的概率為0.3，在第一個(gè)匹配狀態(tài)輸出殘基C的概率為0.6.這條路徑產(chǎn)生ACCY的概率為：0.4×0.3×0.46×0.6×0.97×0.5×0.015×0.73×0.01×1=1.76×10-6如果將這個(gè)概率乘積取對(duì)數(shù)，就可以用加法替代乘法，而得到這條序列的原始計(jì)分（RawScore），圖中路徑產(chǎn)生ACCY的計(jì)分值為：㏑(0.4)+㏑(0.3)+㏑(0.46)㏑(0.6)+㏑(0.97)+㏑(0.5)+㏑(0.015)+㏑(0.73)+㏑(0.01)+㏑(1)=-13.25隱馬爾可夫模型算法已知模型參數(shù)，計(jì)算某一特定輸出序列的概率.通常使用Forward算法解決.已知模型參數(shù)，尋找最可能的能產(chǎn)生某一特定輸出序列的隱含狀態(tài)的序列.通常使用Viterbi算法解決.已知輸出序列，尋找最可能的狀態(tài)轉(zhuǎn)移以及輸出概率.通常使用Baum-Welch算法以及ReversedViterbi算法解決.另外,最近的一些方法使用JunctionTree來(lái)解決這三個(gè)問題。

Viterbi

算法HMM可以有多條路徑產(chǎn)生序列ACCY，加粗的路徑只是其中的一種。對(duì)插入、匹配、刪除三種狀態(tài)根據(jù)它們的位置進(jìn)行編號(hào)。第一個(gè)匹配狀態(tài)的為M1，第一個(gè)刪除狀態(tài)為D1。因插入狀態(tài)多余匹配狀態(tài)或刪除狀態(tài)，在模型的開始有一個(gè)額外的插入狀態(tài)為I0.Viterbi算法用了一個(gè)矩陣，矩陣的行由序列中的氨基酸殘基組成，列由模型中的狀態(tài)組成。0.4C0.05C0.23Y0.3a0.5c0.01y起始—結(jié)束0.490.40.30.480.480.270.30.460.50.0150.0150.490.4800.70.970.970.060.060.460.460.30.0150.0150.050.060.0150.731HMM可由多條路徑產(chǎn)生序列ACCYViterbi

算法中的矩陣I0I1M1I2M2I3M3A0.12000000

C00.0150.0460000

C00000.48500

Y000000.0010.2231①計(jì)算狀態(tài)I0產(chǎn)生殘基A的概率，并填入矩陣中的第一行第一列

Prob(AinstateI0)=0.4×0.3=0.12；②分別計(jì)算狀態(tài)I1和M1產(chǎn)生殘基C的概率，填入矩陣第二行對(duì)應(yīng)的位置

Prob(CinstateI1)=0.05×0.06×0.5=0.0015

Prob(CinstateM1)=0.46×0.01=0.0046；③計(jì)算最大概率max(I1,M1)；④從最大概率出發(fā)畫一箭頭回溯至狀態(tài)I0；⑤重復(fù)②到④步，知道矩陣填完。矩陣中其他元素計(jì)算如下：

Prob(CinstateM2)=0.97×0.5=0.485

Prob(YinstateI3)=0.015×0.73×0.01=0.0001

Prob(YinstateM3)=0.97×0.23=0.2231通過回溯的箭頭可以找出模型產(chǎn)生序列ACCY的最有可能狀態(tài)路徑為起始→I0→M1→M2→M3→結(jié)束。一旦路徑已知，產(chǎn)生序列的概率就可通過路徑上所有概率相乘求出：0.12×0.0046×0.485×0.2231×0.7=4.181×10-5

Forward算法前向算法類似于Viterbi算法，但是在第三步中求和代替了求最大值，矩陣中不許回溯箭頭。計(jì)算序列的概率就是計(jì)算矩陣中最后一行的概率的和。I0I1M1I2M2I3M3A0.12000000

C00.000180.0005520000

C00000.003091200

Y000000.000000030.000069前向算法中的矩陣Prob(AinstateI0)=0.4×0.3=0.12Prob(CinstateI1)=0.12×0.05×0.06×0.5=0.00018Prob(Ci