|
原理簡(jiǎn)介 馬爾可夫鏈（Markov Chain），描述了一種狀態(tài)序列，其每個(gè)狀態(tài)值取決于前面有限個(gè)狀態(tài)。馬爾可夫鏈?zhǔn)蔷哂旭R爾可夫性質(zhì)的隨機(jī)變量X_1,X_2,X_3...的一個(gè)數(shù)列。這些變量的范圍，即它們所有可能取值的集合，被稱為“狀態(tài)空間”，而X_n的值則是在時(shí)間n的狀態(tài)。如果X_{n+1}對(duì)于過去狀態(tài)的條件概率分布僅是X_n的一個(gè)函數(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為過程中的某個(gè)狀態(tài)。上面這個(gè)恒等式可以被看作是馬爾可夫性質(zhì)。 馬爾可夫在1906年首先做出了這類過程。而將此一般化到可數(shù)無限狀態(tài)空間是由柯爾莫果洛夫在1936年給出的。 物理馬爾可夫鏈通常用來建模排隊(duì)理論和統(tǒng)計(jì)學(xué)中的建模，還可作為信號(hào)模型用于熵編碼技術(shù)，如算術(shù)編碼（著名的LZMA數(shù)據(jù)壓縮算法就使用了馬爾可夫鏈與類似于算術(shù)編碼的區(qū)間編碼）。馬爾可夫鏈也有眾多的生物學(xué)應(yīng)用，特別是人口過程，可以幫助模擬生物人口過程的建模。隱蔽馬爾可夫模型還被用于生物信息學(xué)，用以編碼區(qū)域或基因預(yù)測(cè)。 馬爾可夫過程的定義： ⑴設(shè){(X(t),t∈T)}是一個(gè)隨機(jī)過程，如果{X(t),t∈T}在t0時(shí)刻所處的狀態(tài)為已知時(shí)，與它在時(shí)刻t>t0之前所處的狀態(tài)無關(guān)，則稱{X(t),t∈T)}具有馬爾可夫性。 ⑵設(shè){X(t),t∈T)}的狀態(tài)空間為S,如果對(duì)于任意的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)}為馬爾可夫過程。 馬爾可夫過程，能為給定樣品文本，生成粗略，但看似真實(shí)的文本：他們被用于眾多供消遣的“模仿生成器”軟件。馬爾可夫鏈還被用于譜曲。 它們是后面進(jìn)行推導(dǎo)必不可少的條件：⑴尺度間具有馬爾可夫性質(zhì).隨機(jī)場(chǎng)從上到下形成了馬爾可夫鏈，即 Xi 的分布只依賴于 Xi,與其他更粗 糙的尺度無關(guān)，這是因?yàn)?/SPAN> Xi 已經(jīng)包含了所有位于其上層的尺度所含有的信息.⑵ 隨機(jī)場(chǎng)像素的條件獨(dú)立性.若 Xi 中像素的父節(jié)點(diǎn)已知，則 Xi 中的像素彼此獨(dú)立.這一性質(zhì)使我們不必再 考慮平面網(wǎng)格中相鄰像素間的關(guān)系，而轉(zhuǎn)為研究尺度間相鄰像素（即父子節(jié)點(diǎn)）間的關(guān)系.⑶ 設(shè)在給定 Xn 的情況下,Y 中的像素彼此獨(dú)立.⑷ 可分離性.若給定任一節(jié)點(diǎn) xs,則以其各子節(jié)點(diǎn)為根的子樹所對(duì)應(yīng)的變量相互獨(dú)立. 從只有一個(gè)節(jié)點(diǎn)的根到和圖像大小一致的葉子節(jié)點(diǎn)，建立了完整的四叉樹模型，各層間的馬爾可夫鏈的因 果關(guān)系使我們可以由非迭代的推導(dǎo)過程快速計(jì)算出 X 的最大后驗(yàn)概率或后驗(yàn)邊緣概率. 完整的四叉樹模型也存在一些問題. ⑴ 因概率值過小，計(jì)算機(jī)的精度難以保障而出現(xiàn)下溢，若層次多，這一 問題更為突出.雖然可以通過取對(duì)數(shù)的方法將接近于 0 的小值轉(zhuǎn)換成大的負(fù)值，但若層次過多、概率值過小，該 方法也難以奏效，且為了這些轉(zhuǎn)換所采用的技巧又增加了不少計(jì)算量. ⑵ 當(dāng)圖像較大而導(dǎo)致層次較多時(shí)，逐層 的計(jì) 算甚 為繁瑣 下 溢 現(xiàn) 象肯定 會(huì)出 現(xiàn)，存儲(chǔ)中 間變 量也 會(huì)占 用大 量空 間，在時(shí) 間空間 上都 有更 多的 開銷 . ⑶ 分層模型存在塊效應(yīng)，即區(qū)域邊界可能出現(xiàn)跳躍，因?yàn)樵谠撃Ｐ椭?，同一層隨機(jī)場(chǎng)中相鄰的像素不一定有同 一個(gè)父節(jié)點(diǎn)，同一層的相鄰像素間又沒有交互，從而可能出現(xiàn)邊界不連續(xù)的現(xiàn)象. 為了解決這些問題，我們提出一種新的分層 MRF 模型——半樹模型，其結(jié)構(gòu)和圖15類似，仍然是四叉樹， 只是層數(shù)比完整的四叉樹大大減少，相當(dāng)于將完整的四叉樹截為兩部分，只取下面的這部分.模型最下層仍和圖像 大小一致，但最上層則不止一個(gè)節(jié)點(diǎn).完整的四叉樹模型所具有的性質(zhì)完全適用于半樹模型，不同點(diǎn)僅在于最上層,完整的樹模型從上到下構(gòu)成 了完整的因果依賴性，而半樹模型的層間因果關(guān)系被截?cái)?，該層?jié)點(diǎn)的父節(jié)點(diǎn)及祖先均被刪去，因此該層中的各 節(jié)點(diǎn)不具有條件獨(dú)立性，即不滿足上述的性質(zhì)2,因而對(duì)這一層轉(zhuǎn)為考慮層內(nèi)相鄰節(jié)點(diǎn)間的關(guān)系.半樹模型和完 整的樹模型相比，層次減少了許多，這樣，層次間的信息傳遞快了，概率值也不會(huì)因?yàn)檫^多層次的逐層計(jì)算而小 到出現(xiàn)下溢.但第 0 層帶來了新的問題，我們必須得考慮節(jié)點(diǎn)間的交互，才能得出正確的推導(dǎo)結(jié)果，也正是因?yàn)樵?/SPAN> 第 0 層考慮了相鄰節(jié)點(diǎn)間的影響，使得該模型的塊現(xiàn)象要好于完整的樹模型.對(duì)于層次數(shù)的選取，我們認(rèn)為不宜多，太多則達(dá)不到簡(jiǎn)化模型的目的，其優(yōu)勢(shì)體現(xiàn)不出來，但也不能太少，因?yàn)榈?/SPAN>0 層的概率計(jì)算仍然要采用非迭代的算法，層數(shù)少表明第0 層的節(jié)點(diǎn)數(shù)仍較多，計(jì)算費(fèi)時(shí)，所以在實(shí)驗(yàn)中將 層數(shù)取為完整層次數(shù)的一半或一半稍少. MPM 算法 3半樹模型的 MPM 算法 圖像分割即已知觀測(cè)圖像 y,估計(jì) X 的配置，采用貝葉斯估計(jì)器，可由一個(gè)優(yōu)化問題來表示： ?x = arg min [E C ( x,x ）′ | Y = y],x其中代價(jià)函數(shù) C 給出了真實(shí)配置為 x 而實(shí)際分割結(jié)果為 x′時(shí)的代價(jià).在已知 y 的情況下，最小化這一代價(jià)的期 望，從而得到最佳的分割.代價(jià)函數(shù)取法不同得到了不同的估計(jì)器，若 C(x,x′）=1?δ(x,x′）（當(dāng) x=x′時(shí)δ(x,x′）=1,否則 δ(x,x′）=0)得到的是 MAP 估計(jì)器，它意味著 x 和 x′只要在一個(gè)像素處有不同，則代價(jià)為 1,對(duì)誤分類的懲罰比較重，汪西莉 等：一種分層馬爾可夫圖像模型及其推導(dǎo)算法 而在實(shí)際中存在一些誤分類是完全允許的.若將半樹模型的 MPM 算法記為 HT-MPM,它分為向上算法和向下算法兩步，向上算法自下而上根據(jù)式⑵、 式 ⑶逐層計(jì) 算P(yd(s)|xs)和 P(xs,xρ(s)|yd(s)），對(duì)最下層 P(yd(s)|xs)=P(ys|xs). 向下算法自上 而下根據(jù) 式 ⑴逐層計(jì)算 P(xs|y)，對(duì)最上層由 P(x0|y)采樣 x0⑴，…,x0(n), 馬爾可夫鏈，因安德烈·馬爾可夫(A.A.Markov,1856－1922)得名，是數(shù)學(xué)中具有馬爾可夫性質(zhì)的離散時(shí)間隨機(jī)過程。該過程中，在給定當(dāng)前知識(shí)或信息的情況下，過去（即當(dāng)期以前的歷史狀態(tài)）對(duì)于預(yù)測(cè)將來（即當(dāng)期以后的未來狀態(tài)）是無關(guān)的。 時(shí)間和狀態(tài)都是離散的馬爾可夫過程稱為馬爾可夫鏈，簡(jiǎn)記為Xn = X(n),n = 1,2,3,4····。 馬爾可夫鏈?zhǔn)?/SPAN>隨機(jī)變量的一個(gè)數(shù)列。這些變量的范圍，即他們所有可能取值的集合，被稱為“狀態(tài)空間”，而Xn的值則是在時(shí)間n的狀態(tài)。如果Xn + 1對(duì)于過去狀態(tài)的條件概率分布僅是Xn的一個(gè)函數(shù)，則 P(Xn+1=x|X0,X1,X2,...Xn)=P(Xn+1=x|Xn) 馬爾可夫鏈與布朗運(yùn)動(dòng)以及遍歷假說這兩個(gè)二十世紀(jì)初期物理學(xué)重要課題是相聯(lián)系的，但馬爾可夫?qū)で蟮乃坪醪粌H于數(shù)學(xué)動(dòng)機(jī)，名義上是對(duì)于縱屬事件大數(shù)法則的擴(kuò)張。 馬爾可夫鏈?zhǔn)菨M足下面兩個(gè)假設(shè)的一種隨機(jī)過程： 1、t+l時(shí)刻系統(tǒng)狀態(tài)的概率分布只與t時(shí)刻的狀態(tài)有關(guān)，與t時(shí)刻以前的狀態(tài)無關(guān)； 2、從t時(shí)刻到t+l時(shí)刻的狀態(tài)轉(zhuǎn)移與t的值無關(guān)。一個(gè)馬爾可夫鏈模型可表示為=(S,P,Q)，其中各元的含義如下： 1)S是系統(tǒng)所有可能的狀態(tài)所組成的非空的狀態(tài)集，有時(shí)也稱之為系統(tǒng)的狀態(tài)空間，它可以是有限的、可列的集合或任意非空集。本文中假定S是可數(shù)集（即有限或可列）。用小寫字母i,j（或Si,Sj)等來表示狀態(tài)。 2)P是系統(tǒng)的狀態(tài)轉(zhuǎn)移概率矩陣，其中Pij表示系統(tǒng)在時(shí)刻t處于狀態(tài)i,在下一時(shí)刻t+l處于狀態(tài)j的概率,N是系統(tǒng)所有可能的狀態(tài)的個(gè)數(shù)。對(duì)于任意i∈s,有。 3)Q是系統(tǒng)的初始概率分布,qi是系統(tǒng)在初始時(shí)刻處于狀態(tài)i的概率，滿足。 折疊基本性質(zhì) 馬爾可夫鏈模型的性質(zhì) 馬爾可夫鏈?zhǔn)怯梢粋€(gè)條件分布來表示的 P(Xn + 1 | Xn) 這被稱為是隨機(jī)過程中的“轉(zhuǎn)移概率”。這有時(shí)也被稱作是“一步轉(zhuǎn)移概率”。二、三，以及更多步的轉(zhuǎn)移概率可以導(dǎo)自一步轉(zhuǎn)移概率和馬爾可夫性質(zhì)： 同樣： 這些式子可以通過乘以轉(zhuǎn)移概率并求k?1次積分來一般化到任意的將來時(shí)間n+k。 邊際分布P(Xn)是在時(shí)間為n時(shí)的狀態(tài)的分布。初始分布為P(X0)。該過程的變化可以用以下的一個(gè)時(shí)間步幅來描述： 這是Frobenius-Perron equation的一個(gè)版本。這時(shí)可能存在一個(gè)或多個(gè)狀態(tài)分布π滿足： 其中Y只是為了便于對(duì)變量積分的一個(gè)名義。這樣的分布π被稱作是“平穩(wěn)分布”(Stationary Distribution)或者“穩(wěn)態(tài)分布”(Steady-state Distribution)。一個(gè)平穩(wěn)分布是一個(gè)對(duì)應(yīng)于特征根為1的條件分布函數(shù)的特征方程。 平穩(wěn)分布是否存在，以及如果存在是否唯一，這是由過程的特定性質(zhì)決定的。“不可約”是指每一個(gè)狀態(tài)都可來自任意的其它狀態(tài)。當(dāng)存在至少一個(gè)狀態(tài)經(jīng)過一個(gè)固定的時(shí)間段后連續(xù)返回，則這個(gè)過程被稱為是“周期的”。 離散狀態(tài)空間中的馬爾可夫鏈模型 如果狀態(tài)空間是有限的，則轉(zhuǎn)移概率分布可以表示為一個(gè)具有(i,j)元素的矩陣，稱之為“轉(zhuǎn)移矩陣”： Pij = P(Xn + 1 = i | Xn = j) 對(duì)于一個(gè)離散狀態(tài)空間,k步轉(zhuǎn)移概率的積分即為求和，可以對(duì)轉(zhuǎn)移矩陣求k次冪來求得。就是說，如果是一步轉(zhuǎn)移矩陣，就是k步轉(zhuǎn)移后的轉(zhuǎn)移矩陣。 平穩(wěn)分布是一個(gè)滿足以下方程的向量： 在此情況下，穩(wěn)態(tài)分布π * 是一個(gè)對(duì)應(yīng)于特征根為1的、該轉(zhuǎn)移矩陣的特征向量。 如果轉(zhuǎn)移矩陣不可約，并且是非周期的，則收斂到一個(gè)每一列都是不同的平穩(wěn)分布π * ，并且， 獨(dú)立于初始分布π。這是由Perron-Frobenius theorem所指出的。 正的轉(zhuǎn)移矩陣（即矩陣的每一個(gè)元素都是正的）是不可約和非周期的。矩陣被稱為是一個(gè)隨機(jī)矩陣，當(dāng)且僅當(dāng)這是某個(gè)馬爾可夫鏈中轉(zhuǎn)移概率的矩陣。 注意：在上面的定式化中，元素(i,j)是由j轉(zhuǎn)移到i的概率。有時(shí)候一個(gè)由元素(i,j)給出的等價(jià)的定式化等于由i轉(zhuǎn)移到j的概率。在此情況下，轉(zhuǎn)移矩陣僅是這里所給出的轉(zhuǎn)移矩陣的轉(zhuǎn)置。另外，一個(gè)系統(tǒng)的平穩(wěn)分布是由該轉(zhuǎn)移矩陣的左特征向量給出的，而不是右特征向量。 轉(zhuǎn)移概率獨(dú)立于過去的特殊況為熟知的Bernoulli scheme。僅有兩個(gè)可能狀態(tài)的Bernoulli scheme被熟知為貝努利過程 馬爾可夫鏈模型的應(yīng)用 折疊科學(xué)中的應(yīng)用 馬爾可夫鏈通常用來建模排隊(duì)理論和統(tǒng)計(jì)學(xué)中的建模，還可作為信號(hào)模型用于熵編碼技術(shù)，如算法編碼。馬爾可夫鏈最近的應(yīng)用是在地理統(tǒng)計(jì)學(xué)(geostatistics)中。其中，馬爾可夫鏈用在基于觀察數(shù)據(jù)的二到三維離散變量的隨機(jī)模擬。這一應(yīng)用類似于“克里金”地理統(tǒng)計(jì)學(xué)(Kriging geostatistics)，被稱為是“馬爾可夫鏈地理統(tǒng)計(jì)學(xué)”。這一馬爾可夫鏈地理統(tǒng)計(jì)學(xué)方法仍在發(fā)展過程中。 馬爾可夫鏈模型主要是分析一個(gè)人在某一階段內(nèi)由一個(gè)職位調(diào)到另一個(gè)職位的可能性，即調(diào)動(dòng)的概率。該模型的一個(gè)基本假設(shè)就是，過去的內(nèi)部人事變動(dòng)的模式和概率與未來的趨勢(shì)大體相一致。實(shí)際上，這種方法是要分析企業(yè)內(nèi)部人力資源的流動(dòng)趨勢(shì)和概率，如升遷、轉(zhuǎn)職、調(diào)配或離職等方面的情況，以便為內(nèi)部的人力資源的調(diào)配提供依據(jù)?！∷幕舅枷胧牵和ㄟ^發(fā)現(xiàn)過去組織人事變動(dòng)的規(guī)律，以推測(cè)組織在未來人員的供給情況。馬爾可夫鏈模型通常是分幾個(gè)時(shí)期收集數(shù)據(jù)，然后再得出平均值，用這些數(shù)據(jù)代表每一種職位中人員變動(dòng)的頻率，就可以推測(cè)出人員變動(dòng)情況。 具體做法是：將計(jì)劃初期每一種工作的人數(shù)量與每一種工作的人員變動(dòng)概率相乘，然后縱向相加，即得到組織內(nèi)部未來勞動(dòng)力的凈供給量。其基本表達(dá)式為： Ni(t)：t時(shí)間內(nèi)I類人員數(shù)量； Pji：人員從j類向I類轉(zhuǎn)移的轉(zhuǎn)移率； Vi(t)：在時(shí)間(t-1,t)I類所補(bǔ)充的人員數(shù)。 企業(yè)人員的變動(dòng)有調(diào)出、調(diào)入、平調(diào)、晉升與降級(jí)五種。表3 假設(shè)一家零售公司在1999至2000年間各類人員的變動(dòng)情況。年初商店經(jīng)理有12人，在當(dāng)年期間平均90%的商店經(jīng)理仍在商店內(nèi),10%的商店經(jīng)理離職，期初36位經(jīng)理助理有 11%晉升到經(jīng)理,83%留在原來的職務(wù),6%離職；如果人員的變動(dòng)頻率是相對(duì)穩(wěn)定的，那么在2000年留在經(jīng)理職位上有11人(12×90%），另外，經(jīng)理助理中有4人(36×11%）晉升到經(jīng)理職位，最后經(jīng)理的總數(shù)是15人(11+4)?？梢愿鶕?jù)這一矩陣得到其他人員的供給情況，也可以計(jì)算出其后各個(gè)時(shí)期的預(yù)測(cè)結(jié)果。 假設(shè)的零售公司的馬爾可夫分析，見下表： 1999~2000 商店經(jīng)理 經(jīng)理助理 區(qū)域經(jīng)理 部門經(jīng)理 銷售員 離職 商店經(jīng)理 (n=12) 90% 11 10% 1 經(jīng)理助理 (n=36) 11% 4 83% 30 6% 2 區(qū)域經(jīng)理 (n=96) 11% 11 66% 63 8% 8 15% 14 部門經(jīng)理 （n=288) 10% 29 72% 207 2% 6 16% 46 銷售員 （n=1440) 6% 86 74% 1066 25% 228 供給預(yù)測(cè) 15 41 92 301 1072 351 |
|
|
