1、馬爾可夫模型及其應用馬爾可夫模型及其應用匯報人：呂昌偉匯報人：呂昌偉 20157167 2015年12月1日馬爾可夫隨機場馬爾可夫隨機場 3目錄馬爾可夫鏈馬爾可夫鏈 1隱馬爾可夫模型隱馬爾可夫模型 2馬爾科夫鏈：介紹 馬爾可夫鏈，因安德烈馬爾可夫（A.A.Markov，18561922）得名，是數學領域中具有馬爾可夫性質的離散時間隨機過程。 馬爾可夫在1906年首先做出了這類過程。而將此一般化到可數無限狀態空間是由柯爾莫果洛夫在1936年給出的。 安德烈馬爾可夫，俄羅斯人，物理-數學博士，圣彼得堡科學院院士，彼得堡數學學派的代表人物，以數論和概率論方面的工作著稱，他的主要著作有概率演算等。18

2、78年，榮獲金質獎章，1905年被授予功勛教授稱號。馬爾科夫鏈：定義及表示 隨機過程 是隨機變量的集合，指標t通常表示時間，此時，過程X是隨時間而變化的隨機變量X的取值模型。 X(t)是過程在時刻t的狀態，用Xt代替X(t)。 這里我們著重于特殊類型的離散時間、離散空間隨機過程X0,X1,X2,，其中Xt的值依賴于Xt-1的值，但不依賴于導致系統取那個值得狀態序列。定義定義：一個離散時間隨機過程X0，X1，X2，是馬爾可夫鏈，如果X(t):tXt1ta ,a1t1ttt002t2t1t1tttP)aX|aXPr()aX,aX,aX|aXPr(馬爾可夫性 無記憶性馬爾科夫鏈：一般性假定馬爾可夫鏈

3、的離散狀態空間為0,1,2，n(或0,1,2，如果可數無窮)。轉移概率 是過程i經一步轉移到j的概率。馬兒可夫性蘊涵馬爾可夫鏈由一步轉移矩陣唯一確定。) iX| jXPr(P1ttijPPPPPPPPPPj , i1 , i0, ij , 11 , 10, 1j , 01 , 00, 0歸一化：對所有i,0jj , i1P馬爾科夫鏈：m步轉移概率 對任意m0,我們將m步轉移概率定義為鏈從狀態i經恰好m步到達狀態j的概率。) iX| jXPr(Ptmtmj , i 在從i出發經1次轉移的條件下，我們有0k1mj ,kk , imj , iPPP 設P(m)是一個矩陣，其元素為m步轉移概率，使得第

4、i行第j列元素為由上式可得經關于m的歸納mj , iP)1m()m(PPPm)m(PP 設pi(t)表示過程在t時刻處于狀態i的概率 是在t時刻給出鏈的狀態分布的向量我們將概率分布表示成一個行向量),t (p),t (p),t (p() t (p210P) 1t (p) t (p0ji , jjiP) 1t (p) t (p馬爾科夫鏈：加權圖表示馬爾可夫鏈的另一種有用的表示是用一個有向加權圖D=(V,E,w).圖的頂點集合是鏈的狀態集存在一條有向邊 ,當且僅當Pi,j0,此時邊(i,j)的權w(i,j)由w(i,j)=Pi,j給出自圈（一條邊開始和結束在同一頂點）是允許的。對每一個i，我們仍要

5、求一個由過程逗留過的狀態序列表示為圖上的一條有向路徑。過程沿著這條路徑的概率是路徑表的權的乘積。E) j , i (1) j , i (wE) j , i ( : j3P3,1P1,3P3,212P1,2P2,20P0,1P1,0P0,3P3,3馬爾科夫鏈：例子計算恰好經過三步從狀態0到狀態3的概率。31/21/61/4121/3101/41/23/41/4路徑： 概率 0-1-0-3 3/320-1-3-3 1/96 0-3-1-3 1/160-3-3-3 3/64 總概率：41/1924/14/12/1001006/13/102/14/304/10P192/47192/10796/1316

6、/1010036/5144/7924/548/5192/4164/2948/716/3P3192/41P33 , 0馬爾科夫鏈轉移矩陣馬爾科夫鏈：應用 保險公司保險公司要對投保人未來的健康狀態作出估計，以制訂保險金和理賠金的數額例：人的健康狀況分為健康和疾病兩種狀態，設對特定年齡段的人，今年健康、明年保持健康狀態的概率為0.8，而今年患病、明年轉為健康狀態的概率為0.7，若某人投保時健康，問10年后他仍處于健康狀態的概率是多少？狀態Xn=1，第n年健康2，第n年疾病, 1 , 0n, 2 , 1i),iX(P)n(ani狀態概率：, 1 , 0n, 2 , 1j , i),iX| jX(Ppn

7、1nij轉移概率：p11=0.8 p12=1-p11=0.2p21=0.7 p22=1-p21=0.3Xn+1只取決于Xn和pij,與Xn-1,無關馬爾科夫鏈：應用 保險公司狀態轉移具有無后效性a1(n+1)=a1(n)p11+a2(n)p21a2(n+1)=a1(n)p12+a2(n)p22給定a(0),預測a(n), n=1,2設投保時健康設投保時疾病n 時狀態概率趨于穩定值，穩定值與初始狀態無關馬爾科夫鏈：應用 保險公司Xn=3為第三種狀態 死亡a1(n+1)=a1(n)p11+a2(n)p21+a3(n)p31a2(n+1)=a1(n)p12+a2(n)p22+a3(n)p32a3(n

8、+1)=a1(n)p13+a2(n)p23+a3(n)p33設投保時處于健康狀態，預測a(n),n=1,2隱馬爾科夫模型例如：一個隱居的人可能不能直觀的觀察到天氣的情況，但是民間傳說告訴我們海藻的狀態在某種概率上是和天氣的情況相關的。在這種情況下我們有兩個狀態集合，一個可以觀察到的狀態集合（海藻的狀態）和一個隱藏的狀態（天氣狀況）。我們希望能找到一個算法可以根據海藻的狀況和馬爾科夫假設來預測天氣的狀況。隱藏狀態的數目隱藏狀態的數目和可以觀察到的狀態可以觀察到的狀態的數目可能是不一樣的。在一個有3種狀態的天氣系統（sunny、cloudy、rainy）中，也許可以觀察到4種潮濕程度的海藻（dry

9、、dryish、damp、soggy）。可以觀察到的狀態序列和隱藏的狀態序列是概率相關的。于是我們可以將這種類型的過程建模為有一個隱藏的馬爾科夫過程和一個與這個隱藏馬爾科夫過程概率相關的并且可以觀察到的狀態集合。隱馬爾可夫模型 (Hidden Markov Model) 是一種統計模型，用來描述一個含有隱含未知參數的馬爾可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數，然后利用這些參數來作進一步的分析。隱馬爾科夫模型下圖是一個三個狀態的隱馬爾可夫模型狀態轉移圖。x 表示隱含狀態y 表示可觀察的輸出a 表示狀態轉換概率b 表示輸出概率隱馬爾科夫模型下圖顯示了天氣的例子中隱藏的狀態和可以觀察

10、到的狀態之間的關系。我們假設隱藏的狀態是一個簡單的一階馬爾科夫過程，并且他們兩兩之間都可以相互轉換。MM vs HMM1、在MM中，每一個狀態代表一個可觀察的事件2、在HMM中觀察到的事件是狀態的隨機函數，因此該模型是一雙重隨機過程，其中狀態轉移過程是不可觀察（隱藏）的馬爾可夫鏈，而可觀察的事件的隨機過程是隱藏的狀態轉換過程的隨機函數（一般隨機過程）。隱馬爾科夫模型對HMM來說，有如下三個重要假設。假設1：馬爾可夫假設（狀態構成一階馬爾可夫鏈）假設2：不動性假設（狀態與具體時間無關）假設3：輸出獨立性假設（輸出僅與當前狀態有關）)X|X(P)XX|X(P1ii11iij , i),X|X(P)

11、X|X(Pj1ji1i)X|O(P)X,X|O,O(PttT1T1隱藏的狀態和可觀察到的狀態之間有一種概率上的關系，也就是說某種隱藏狀態 H 被認為是某個可以觀察的狀態 O1 是有概率的，假設為 P(O1 | H)。隱馬爾科夫模型如果可以觀察的狀態有3種，那么P(O1 | H)+P(O2 | H)+ P(O3 | H) = 1。這樣，我們也可以得到一個另一個矩陣，稱為混淆矩陣 (confusion matrix)。這個矩陣的內容是某個隱藏的狀態被分別觀察成幾種不同的可以觀察的狀態的概率，在天氣的例子中，這個矩陣如下圖：隱馬爾科夫模型一個隱馬爾可夫模型 HMM 可用一個5元組描述：= N, M,

12、 A,B N = H1，Hn 隱藏狀態的有限集合M = O1，Om 可觀測狀態的有限集合，可以通過訓練集獲得 =i 為初始狀態概率，A=aij 為隱藏狀態的轉移矩陣 B=bik 表示某個時刻因隱藏狀態而可觀察的狀態的概率，即混淆矩陣在狀態轉移矩陣和混淆矩陣中的每個概率都是時間無關的，即當系統演化時，這些矩陣并不隨時間改變。對于一個 N 和 M 固定的 HMM 來說，用 = , A, B 表示 HMM 參數。模型的演化綠色的圓圈表示隱藏狀態紫色的圓圈表示可觀察到的狀態箭頭表示狀態之間的依存概率隱馬爾科夫模型在HMM中有三個典型問題：（一）已知模型參數，計算某一給定可觀察狀態序列的概率（二）根據可

13、觀察狀態的序列找到一個最可能的隱藏狀態序列（三）根據觀察到的序列集來找到一個最有可能的HMM 0.40.70.6HappyUnhappy0.10.4 Do nothingBeatKiss0.5Start0.60.40.30.60.10.3隱藏狀態=（Happy，Unhappy）可觀察狀態=（Do Nothing，Beat，Kiss）開始概率=Happy：0.6，Unhappy：0.4轉移概率=Happy：Happy：0.7，Unhappy：0.3，Unhappy：Happy：0.4，Unhappy：0.6發射概率=Happy：Do nothing：0.1，Beat：0.4，Kiss：0.5，U

14、nhappy：Do nothing：0.6，Beat：0.3，Kiss：0.1隱馬爾科夫模型Day 1KissDay 2BeatDay 3Do nothing推斷這三天她的狀態，Happy還是Unhappy？Start H0.3 U0.040.6*0.50.4*0.1 H U H U*0.7*0.4=0.084*0.3*0.3=0.027*0.4*0.4=0.0064*0.6*0.3=0.0072*0.7*0.1=0.00588*0.3*0.6=0.01512*0.4*0.1=0.00108*0.6*0.6=0.009720.70.6HappyUnhappy0.10.4 Do nothingB

15、eatKiss0.5Start0.60.40.30.60.10.30.4隱馬爾科夫模型HMM的應用：l 語音識別l 音字轉換l 詞性標注（POS Tagging）l 基因識別問題 狀態：編碼區域與非編碼區域 字符：ATCGl 一般化：任何與線性序列相關的現象語音識別l 氣象、氣候預報l 模式識別問題馬爾可夫隨機場馬爾可夫隨機場（Markov random fields)，也叫無向圖模型，或稱為馬爾科夫網（Markov network)馬爾科夫網絡也有條件獨立屬性。條件獨立：如果A的任意節點和B的任意節點的任意路徑上，都存在至少一個節點屬于C那么A和B條件獨立于C。clique”團”的概念：圖的

16、一個子圖，子圖上兩兩節點都有連接. 例如這個圖，最大團有兩個，分別是(x1,x2,x3)和(x2,x3,x4)：馬爾可夫隨機場聯合概率分解成一系列potential函數的乘積:Xc是一個最大團的所有節點，一個potential函數 ，是最大團的一個函數.這個函數具體的定義是依賴具體的應用。常量p(x)是一系列potential函數的乘積，可以將potential函數表示成指數函數:這樣p(x)就可以表示成一系列E(Xc)的和的指數函數，E(Xc)叫做能量函數，轉換之后，可以將圖理解成一個能量的集合，他的值等于各個最大團的能量的和.馬爾可夫隨機場有一個二值圖像，觀測序列，也就是我們所擁有的圖像。其中i=1,2,D, D代表像素點的個數（包括了所有圖像，我們所觀測的圖像包括噪聲）真實的圖像左邊的圖像表示真實圖像，由xi表示以10%的概率改變真實圖像的像素為其原來相反的值，生成右邊的圖像，由yi表示利用馬爾科夫隨機場實現噪聲圖還原為真實圖。馬爾可夫隨機場yi，是噪聲圖，紫色表示是已知的，是觀察值。xi是未知的，要求出xi，使xi作為像素值得到的圖，盡量接近無噪聲圖片。每個xi的值，與yi相關，也與相鄰的xj相關。這里邊，最大團是(xi,