馬爾科夫鏈

西納 2018-04-19

展開全文

原理簡介

馬爾可夫鏈（Markov Chain），描述了一種狀態(tài)序列，其每個狀態(tài)值取決于前面有限個狀態(tài)。馬爾可夫鏈是具有馬爾可夫性質(zhì)的隨機變量X_1,X_2,X_3...的一個數(shù)列。這些變量的范圍，即它們所有可能取值的集合，被稱為“狀態(tài)空間”，而X_n的值則是在時間n的狀態(tài)。如果X_{n+1}對于過去狀態(tài)的條件概率分布僅是X_n的一個函數(shù)，則

P(X_{n+1}=x|X_1=x_1,X_2=x_2,...,X_n=x_n) = P(X_{n+1}=x|X_n=x_n).

這里x為過程中的某個狀態(tài)。上面這個恒等式可以被看作是馬爾可夫性質(zhì)。

理論發(fā)展

馬爾可夫在1906年首先做出了這類過程。而將此一般化到可數(shù)無限狀態(tài)空間是由柯爾莫果洛夫在1936年給出的。

物理馬爾可夫鏈通常用來建模排隊理論和統(tǒng)計學(xué)中的建模，還可作為信號模型用于熵編碼技術(shù)，如算術(shù)編碼（著名的LZMA數(shù)據(jù)壓縮算法就使用了馬爾可夫鏈與類似于算術(shù)編碼的區(qū)間編碼）。馬爾可夫鏈也有眾多的生物學(xué)應(yīng)用，特別是人口過程，可以幫助模擬生物人口過程的建模。隱蔽馬爾可夫模型還被用于生物信息學(xué)，用以編碼區(qū)域或基因預(yù)測。

過程

馬爾可夫過程的定義：

⑴設(shè){(X(t),t∈T)}是一個隨機過程，如果{X(t),t∈T}在t0時刻所處的狀態(tài)為已知時，與它在時刻t>t0之前所處的狀態(tài)無關(guān)，則稱{X(t),t∈T)}具有馬爾可夫性。

⑵設(shè){X(t),t∈T)}的狀態(tài)空間為S,如果對于任意的n≧2,任意的t1分布函數(shù)恰好等于在條件X(tn-1)=xn-1下的條件分布函數(shù)，即<....

P(X(tn)<=xn|X(t1)=x1,X(t2)=x2,...,X(tn-1)=xn-1)

=P(X(tn)<=xn|X(tn-1)=xn-1)

則稱{(X(t),t∈T)}為馬爾可夫過程。

馬爾可夫過程，能為給定樣品文本，生成粗略，但看似真實的文本：他們被用于眾多供消遣的“模仿生成器”軟件。馬爾可夫鏈還被用于譜曲。

它們是后面進行推導(dǎo)必不可少的條件：⑴尺度間具有馬爾可夫性質(zhì).隨機場從上到下形成了馬爾可夫鏈，即 Xi 的分布只依賴于 Xi,與其他更粗糙的尺度無關(guān)，這是因為 Xi 已經(jīng)包含了所有位于其上層的尺度所含有的信息.⑵ 隨機場像素的條件獨立性.若 Xi 中像素的父節(jié)點已知，則 Xi 中的像素彼此獨立.這一性質(zhì)使我們不必再考慮平面網(wǎng)格中相鄰像素間的關(guān)系，而轉(zhuǎn)為研究尺度間相鄰像素（即父子節(jié)點）間的關(guān)系.⑶ 設(shè)在給定 Xn 的情況下,Y 中的像素彼此獨立.⑷ 可分離性.若給定任一節(jié)點 xs,則以其各子節(jié)點為根的子樹所對應(yīng)的變量相互獨立.

從只有一個節(jié)點的根到和圖像大小一致的葉子節(jié)點，建立了完整的四叉樹模型，各層間的馬爾可夫鏈的因果關(guān)系使我們可以由非迭代的推導(dǎo)過程快速計算出 X 的最大后驗概率或后驗邊緣概率.

模型

完整的四叉樹模型也存在一些問題.

⑴ 因概率值過小，計算機的精度難以保障而出現(xiàn)下溢，若層次多，這一問題更為突出.雖然可以通過取對數(shù)的方法將接近于 0 的小值轉(zhuǎn)換成大的負值，但若層次過多、概率值過小，該方法也難以奏效，且為了這些轉(zhuǎn)換所采用的技巧又增加了不少計算量.

⑵ 當圖像較大而導(dǎo)致層次較多時，逐層的計算甚為繁瑣下溢現(xiàn) 象肯定會出現(xiàn)，存儲中間變量也會占用大量空間，在時間空間上都有更多的開銷 .

⑶ 分層模型存在塊效應(yīng)，即區(qū)域邊界可能出現(xiàn)跳躍，因為在該模型中，同一層隨機場中相鄰的像素不一定有同一個父節(jié)點，同一層的相鄰像素間又沒有交互，從而可能出現(xiàn)邊界不連續(xù)的現(xiàn)象.

MRF

為了解決這些問題，我們提出一種新的分層 MRF 模型——半樹模型，其結(jié)構(gòu)和圖15類似，仍然是四叉樹，

只是層數(shù)比完整的四叉樹大大減少，相當于將完整的四叉樹截為兩部分，只取下面的這部分.模型最下層仍和圖像大小一致，但最上層則不止一個節(jié)點.完整的四叉樹模型所具有的性質(zhì)完全適用于半樹模型，不同點僅在于最上層,完整的樹模型從上到下構(gòu)成了完整的因果依賴性，而半樹模型的層間因果關(guān)系被截斷，該層節(jié)點的父節(jié)點及祖先均被刪去，因此該層中的各節(jié)點不具有條件獨立性，即不滿足上述的性質(zhì)2,因而對這一層轉(zhuǎn)為考慮層內(nèi)相鄰節(jié)點間的關(guān)系.半樹模型和完整的樹模型相比，層次減少了許多，這樣，層次間的信息傳遞快了，概率值也不會因為過多層次的逐層計算而小到出現(xiàn)下溢.但第 0 層帶來了新的問題，我們必須得考慮節(jié)點間的交互，才能得出正確的推導(dǎo)結(jié)果，也正是因為在第 0 層考慮了相鄰節(jié)點間的影響，使得該模型的塊現(xiàn)象要好于完整的樹模型.對于層次數(shù)的選取，我們認為不宜多，太多則達不到簡化模型的目的，其優(yōu)勢體現(xiàn)不出來，但也不能太少，因為第0 層的概率計算仍然要采用非迭代的算法，層數(shù)少表明第0 層的節(jié)點數(shù)仍較多，計算費時，所以在實驗中將層數(shù)取為完整層次數(shù)的一半或一半稍少.

MPM 算法

3半樹模型的 MPM 算法

圖像分割即已知觀測圖像 y,估計 X 的配置，采用貝葉斯估計器，可由一個優(yōu)化問題來表示：

?x = arg min [E C ( x,x ）′ | Y = y],x其中代價函數(shù) C 給出了真實配置為 x 而實際分割結(jié)果為 x′時的代價.在已知 y 的情況下，最小化這一代價的期望，從而得到最佳的分割.代價函數(shù)取法不同得到了不同的估計器，若 C(x,x′）=1?δ(x,x′）（當 x=x′時δ(x,x′）=1,否則 δ(x,x′）=0)得到的是 MAP 估計器，它意味著 x 和 x′只要在一個像素處有不同，則代價為 1,對誤分類的懲罰比較重，汪西莉等：一種分層馬爾可夫圖像模型及其推導(dǎo)算法

詳細說明

馬爾可夫鏈，因安德烈·馬爾可夫(A.A.Markov,1856－1922)得名，是數(shù)學(xué)中具有馬爾可夫性質(zhì)的離散時間隨機過程。該過程中，在給定當前知識或信息的情況下，過去（即當期以前的歷史狀態(tài)）對于預(yù)測將來（即當期以后的未來狀態(tài)）是無關(guān)的。

時間和狀態(tài)都是離散的馬爾可夫過程稱為馬爾可夫鏈，簡記為Xn = X(n),n = 1,2,3,4····。

馬爾可夫鏈是隨機變量的一個數(shù)列。這些變量的范圍，即他們所有可能取值的集合，被稱為“狀態(tài)空間”，而Xn的值則是在時間n的狀態(tài)。如果Xn + 1對于過去狀態(tài)的條件概率分布僅是Xn的一個函數(shù)，則

P(Xn+1=x|X0,X1,X2,...Xn)=P(Xn+1=x|Xn)

馬爾可夫鏈與布朗運動以及遍歷假說這兩個二十世紀初期物理學(xué)重要課題是相聯(lián)系的，但馬爾可夫?qū)で蟮乃坪醪粌H于數(shù)學(xué)動機，名義上是對于縱屬事件大數(shù)法則的擴張。

馬爾可夫鏈是滿足下面兩個假設(shè)的一種隨機過程：

1、t+l時刻系統(tǒng)狀態(tài)的概率分布只與t時刻的狀態(tài)有關(guān)，與t時刻以前的狀態(tài)無關(guān)；

2、從t時刻到t+l時刻的狀態(tài)轉(zhuǎn)移與t的值無關(guān)。一個馬爾可夫鏈模型可表示為=(S,P,Q)，其中各元的含義如下：

1)S是系統(tǒng)所有可能的狀態(tài)所組成的非空的狀態(tài)集，有時也稱之為系統(tǒng)的狀態(tài)空間，它可以是有限的、可列的集合或任意非空集。本文中假定S是可數(shù)集（即有限或可列）。用小寫字母i,j（或Si,Sj)等來表示狀態(tài)。

2)P是系統(tǒng)的狀態(tài)轉(zhuǎn)移概率矩陣，其中Pij表示系統(tǒng)在時刻t處于狀態(tài)i,在下一時刻t+l處于狀態(tài)j的概率,N是系統(tǒng)所有可能的狀態(tài)的個數(shù)。對于任意i∈s,有。

3)Q是系統(tǒng)的初始概率分布,qi是系統(tǒng)在初始時刻處于狀態(tài)i的概率，滿足。

折疊基本性質(zhì)

馬爾可夫鏈模型的性質(zhì)

馬爾可夫鏈是由一個條件分布來表示的

P(Xn + 1 | Xn)

這被稱為是隨機過程中的“轉(zhuǎn)移概率”。這有時也被稱作是“一步轉(zhuǎn)移概率”。二、三，以及更多步的轉(zhuǎn)移概率可以導(dǎo)自一步轉(zhuǎn)移概率和馬爾可夫性質(zhì)：

同樣：

這些式子可以通過乘以轉(zhuǎn)移概率并求k?1次積分來一般化到任意的將來時間n+k。

邊際分布P(Xn)是在時間為n時的狀態(tài)的分布。初始分布為P(X0)。該過程的變化可以用以下的一個時間步幅來描述：

這是Frobenius-Perron equation的一個版本。這時可能存在一個或多個狀態(tài)分布π滿足：

其中Y只是為了便于對變量積分的一個名義。這樣的分布π被稱作是“平穩(wěn)分布”(Stationary Distribution)或者“穩(wěn)態(tài)分布”(Steady-state Distribution)。一個平穩(wěn)分布是一個對應(yīng)于特征根為1的條件分布函數(shù)的特征方程。

平穩(wěn)分布是否存在，以及如果存在是否唯一，這是由過程的特定性質(zhì)決定的。“不可約”是指每一個狀態(tài)都可來自任意的其它狀態(tài)。當存在至少一個狀態(tài)經(jīng)過一個固定的時間段后連續(xù)返回，則這個過程被稱為是“周期的”。

離散狀態(tài)

離散狀態(tài)空間中的馬爾可夫鏈模型

如果狀態(tài)空間是有限的，則轉(zhuǎn)移概率分布可以表示為一個具有(i,j)元素的矩陣，稱之為“轉(zhuǎn)移矩陣”：

Pij = P(Xn + 1 = i | Xn = j)

對于一個離散狀態(tài)空間,k步轉(zhuǎn)移概率的積分即為求和，可以對轉(zhuǎn)移矩陣求k次冪來求得。就是說，如果是一步轉(zhuǎn)移矩陣，就是k步轉(zhuǎn)移后的轉(zhuǎn)移矩陣。

平穩(wěn)分布是一個滿足以下方程的向量：

在此情況下，穩(wěn)態(tài)分布π * 是一個對應(yīng)于特征根為1的、該轉(zhuǎn)移矩陣的特征向量。

如果轉(zhuǎn)移矩陣不可約，并且是非周期的，則收斂到一個每一列都是不同的平穩(wěn)分布π * ，并且，

獨立于初始分布π。這是由Perron-Frobenius theorem所指出的。

正的轉(zhuǎn)移矩陣（即矩陣的每一個元素都是正的）是不可約和非周期的。矩陣被稱為是一個隨機矩陣，當且僅當這是某個馬爾可夫鏈中轉(zhuǎn)移概率的矩陣。

注意：在上面的定式化中，元素(i,j)是由j轉(zhuǎn)移到i的概率。有時候一個由元素(i,j)給出的等價的定式化等于由i轉(zhuǎn)移到j的概率。在此情況下，轉(zhuǎn)移矩陣僅是這里所給出的轉(zhuǎn)移矩陣的轉(zhuǎn)置。另外，一個系統(tǒng)的平穩(wěn)分布是由該轉(zhuǎn)移矩陣的左特征向量給出的，而不是右特征向量。

轉(zhuǎn)移概率獨立于過去的特殊況為熟知的Bernoulli scheme。僅有兩個可能狀態(tài)的Bernoulli scheme被熟知為貝努利過程

折疊編輯本段現(xiàn)實應(yīng)用

馬爾可夫鏈模型的應(yīng)用

折疊科學(xué)中的應(yīng)用

馬爾可夫鏈通常用來建模排隊理論和統(tǒng)計學(xué)中的建模，還可作為信號模型用于熵編碼技術(shù)，如算法編碼。馬爾可夫鏈最近的應(yīng)用是在地理統(tǒng)計學(xué)(geostatistics)中。其中，馬爾可夫鏈用在基于觀察數(shù)據(jù)的二到三維離散變量的隨機模擬。這一應(yīng)用類似于“克里金”地理統(tǒng)計學(xué)(Kriging geostatistics)，被稱為是“馬爾可夫鏈地理統(tǒng)計學(xué)”。這一馬爾可夫鏈地理統(tǒng)計學(xué)方法仍在發(fā)展過程中。

應(yīng)用

馬爾可夫鏈模型主要是分析一個人在某一階段內(nèi)由一個職位調(diào)到另一個職位的可能性，即調(diào)動的概率。該模型的一個基本假設(shè)就是，過去的內(nèi)部人事變動的模式和概率與未來的趨勢大體相一致。實際上，這種方法是要分析企業(yè)內(nèi)部人力資源的流動趨勢和概率，如升遷、轉(zhuǎn)職、調(diào)配或離職等方面的情況，以便為內(nèi)部的人力資源的調(diào)配提供依據(jù)?！∷幕舅枷胧牵和ㄟ^發(fā)現(xiàn)過去組織人事變動的規(guī)律，以推測組織在未來人員的供給情況。馬爾可夫鏈模型通常是分幾個時期收集數(shù)據(jù)，然后再得出平均值，用這些數(shù)據(jù)代表每一種職位中人員變動的頻率，就可以推測出人員變動情況。

具體做法是：將計劃初期每一種工作的人數(shù)量與每一種工作的人員變動概率相乘，然后縱向相加，即得到組織內(nèi)部未來勞動力的凈供給量。其基本表達式為：

Ni(t)：t時間內(nèi)I類人員數(shù)量；

Pji：人員從j類向I類轉(zhuǎn)移的轉(zhuǎn)移率；

Vi(t)：在時間(t-1,t)I類所補充的人員數(shù)。

企業(yè)人員的變動有調(diào)出、調(diào)入、平調(diào)、晉升與降級五種。表3 假設(shè)一家零售公司在1999至2000年間各類人員的變動情況。年初商店經(jīng)理有12人，在當年期間平均90%的商店經(jīng)理仍在商店內(nèi),10%的商店經(jīng)理離職，期初36位經(jīng)理助理有 11%晉升到經(jīng)理,83%留在原來的職務(wù),6%離職；如果人員的變動頻率是相對穩(wěn)定的，那么在2000年留在經(jīng)理職位上有11人(12×90%），另外，經(jīng)理助理中有4人(36×11%）晉升到經(jīng)理職位，最后經(jīng)理的總數(shù)是15人(11+4)?？梢愿鶕?jù)這一矩陣得到其他人員的供給情況，也可以計算出其后各個時期的預(yù)測結(jié)果。