主要發展
馬爾可夫在1906年首先做出了這類過程 。而將此一般化到可數無限狀態空間是由柯爾莫果洛夫在1936年給出的。
馬爾可夫鏈與布朗運動以及遍歷假說這兩個二十世紀初期物理學重要課題是相聯繫的，但馬爾可夫尋求的似乎不僅於數學動機，名義上是對於縱屬事件大數法則的擴張。
它們是後面進行推導必不可少的條件:(1)尺度間具有馬爾可夫性質.隨機場從上到下形成了馬爾可夫鏈,即Xi的分布只依賴於Xi,與其他更粗 糙的尺度無關,這是因為 Xi 已經包含了所有位於其上層的尺度所含有的信息.(2)隨機場像素的條件獨立性.若 Xi 中像素的父節點已知,則 Xi 中的像素彼此獨立.這一性質使我們不必再 考慮平面格線中相鄰像素間的關係,而轉為研究尺度間相鄰像素(即父子節點)間的關係.(3)設在給定 Xn 的情況下,Y 中的像素彼此獨立.(4)可分離性.若給定任一節點 xs,則以其各子節點為根的子樹所對應的變數相互獨立.
從只有一個節點的根到和圖像大小一致的葉子節點,建立了完整的四叉樹模型,各層間的馬爾可夫鏈的因 果關係使我們可以由非疊代的推導過程快速計算出 X的最大後驗機率或後驗邊緣機率.
完整的四叉樹模型也存在一些問題.(1)因機率值過小,計算機的精度難以保障而出現下溢,若層次多,這一 問題更為突出.雖然可以通過取對數的方法將接近於0的小值轉換成大的負值,但若層次過多、機率值過小,該 方法也難以奏效,且為了這些轉換所採用的技巧又增加了不少計算量.(2)當圖像較大而導致層次較多時,逐層 的計 算甚 為繁瑣 下 溢 現 象肯定 會出 現 , 存儲中 間變 量也 會占 用大 量空 間 , 在時 間空間 上都 有更 多的 開銷 .
(3)分層模型存在塊效應,即區域邊界可能出現跳躍,因為在該模型中,同一層隨機場中相鄰的像素不一定有同 一個父節點,同一層的相鄰像素間又沒有互動,從而可能出現邊界不連續的現象.
為了解決這些問題,我們提出一種新的分層MRF模型——半樹模型,其結構和圖1 5類似,仍然是四叉樹,
只 是層數比完整的四叉樹大大減少,相當於將完整的四叉樹截為兩部分,只取下面的這部分.模型最下層仍和圖像 大小一致,但最上層則不止一個節點.完整的四叉樹模型所具有的性質完全適用於半樹模型,不同點僅在於最上層,完整的樹模型從上到下構成 了完整的因果依賴性,而半樹模型的層間因果關係被截斷,該層節點的父節點及祖先均被刪去,因此該層中的各 節點不具有條件獨立性,即不滿足上述的性質2,因而對這一層轉為考慮層內相鄰節點間的關係.半樹模型和完 整的樹模型相比,層次減少了許多,這樣,層次間的信息傳遞快了,機率值也不會因為過多層次的逐層計算而小 到出現下溢.但第 0 層帶來了新的問題,我們必須得考慮節點間的互動,才能得出正確的推導結果,也正是因為在 第 0 層考慮了相鄰節點間的影響,使得該模型的塊現象要好於完整的樹模型.對於層次數的選取,我們認為不宜多,太多則達不到簡化模型的目的,其優勢體現不出來,但也不能太少,因 為第 0 層的機率計算仍然要採用非疊代的算法,層數少表明第 0 層的節點數仍較多,計算費時,所以在實驗中將 層數取為完整層次數的一半或一半稍少.
3半樹模型的 MPM 算法
圖像分割即已知觀測圖像 y,估計 X 的配置,採用貝葉斯估計器,可由一個最佳化問題來表示:
䲁x = arg min 【E C ( x, x )′| Y = y】 ,x其中代價函式 C 給出了真實配置為 x 而實際分割結果為 x′時的代價.在已知 y 的情況下,最小化這一代價的期 望,從而得到最佳的分割.代價函式取法不同得到了不同的估計器,若C(x,x′)=1䲁δ(x,x′)(當x=x′時δ(x,x′)=1,否則 δ(x,x′)=0)得到的是 MAP 估計器,它意味著 x 和 x′只要在一個像素處有不同,則代價為 1,對誤分類的懲罰比較重,汪西莉等:一種分層馬爾可夫圖像模型及其推導算法
而在實際中存在一些誤分類是完全允許的.若將半樹模型的MPM算法記為HT-MPM,它分為向上算法和向下算法兩步,向上算法自下而上根據式(2)、 式 (3)逐層計 算P(yd(s)|xs)和P(xs,xρ(s)|yd(s)), 對最下層P(yd(s)|xs)=P(ys|xs). 向下算法自上 而下根據 式 (1)逐層計算 P(xs|y),對最上層由 P(x0|y)採樣 x0(1),…,x0(n),
版本二
馬爾可夫鏈，因安德烈·馬爾可夫（A.A.Markov，1856－1922）得名，是數學中具有馬爾可夫性質的離散時間隨機過程。該過程中，在給定當前知識或信息的情況下，過去（即當期以前的歷史狀態）對於預測將來（即當期以後的未來狀態）是無關的。
時間和狀態都是離散的馬爾可夫過程稱為馬爾可夫鏈, 簡記為。
馬爾可夫鏈是隨機變數的一個數列。這些變數的範圍，即他們所有可能取值的集合，被稱為“狀態空間”，而Xn的值則是在時間n的狀態。如果Xn + 1對於過去狀態的條件機率分布僅是Xn的一個函式，則
這裡x為過程中的某個狀態。上面這個恆等式可以被看作是馬爾可夫性質。
馬爾可夫在1906年首先做出了這類過程 。而將此一般化到可數無限狀態空間是由柯爾莫果洛夫在1936年給出的。
馬爾可夫鏈與布朗運動以及遍歷假說這兩個二十世紀初期物理學重要課題是相聯繫的，但馬爾可夫尋求的似乎不僅於數學動機，名義上是對於縱屬事件大數法則的擴張。
馬爾可夫鏈是滿足下面兩個假設的一種隨機過程：
1、t+l時刻系統狀態的機率分布只與t時刻的狀態有關，與t時刻以前的狀態無關；
2、從t時刻到t+l時刻的狀態轉移與t的值無關。一個馬爾可夫鏈模型可表示為=(S，P，Q)，其中各元的含義如下：
1）S是系統所有可能的狀態所組成的非空的狀態集，有時也稱之為系統的狀態空間，它可以是有限的、可列的集合或任意非空集。本文中假定S是可數集(即有限或可列)。用小寫字母i,j(或Si,Sj)等來表示狀態。
2）是系統的狀態轉移機率矩陣，其中Pij表示系統在時刻t處於狀態i，在下一時刻t+l處於狀態i的機率，N是系統所有可能的狀態的個數。對於任意i∈s，有。
3）是系統的初始機率分布，qi是系統在初始時刻處於狀態i的機率，滿足。
[編輯]馬爾可夫鏈模型的性質
馬爾可夫鏈是由一個條件分布來表示的
P(Xn + 1 | Xn)
這被稱為是隨機過程中的“轉移機率”。這有時也被稱作是“一步轉移機率”。二、三，以及更多步的轉移機率可以導自一步轉移機率和馬爾可夫性質：
同樣：
這些式子可以通過乘以轉移機率並求k−1次積分來一般化到任意的將來時間n+k。
邊際分布P(Xn)是在時間為n時的狀態的分布。初始分布為P(X0)。該過程的變化可以用以下的一個時間步幅來描述：
這是Frobenius-Perron equation的一個版本。這時可能存在一個或多個狀態分布π滿足：
其中Y只是為了便於對變數積分的一個名義。這樣的分布π被稱作是“平穩分布”（Stationary Distribution）或者“穩態分布”（Steady-state Distribution）。一個平穩分布是一個對應於特徵根為1的條件分布函式的特徵方程。
平穩分布是否存在，以及如果存在是否唯一，這是由過程的特定性質決定的。“不可約”是指每一個狀態都可來自任意的其它狀態。當存在至少一個狀態經過一個固定的時間段後連續返回，則這個過程被稱為是“周期的”。
[編輯]離散狀態空間中的馬爾可夫鏈模型
如果狀態空間是有限的，則轉移機率分布可以表示為一個具有(i,j)元素的矩陣，稱之為“轉移矩陣”：
Pij = P(Xn + 1 = i | Xn = j)
對於一個離散狀態空間，k步轉移機率的積分即為求和，可以對轉移矩陣求k次冪來求得。就是說，如果是一步轉移矩陣，就是k步轉移後的轉移矩陣。
平穩分布是一個滿足以下方程的向量：
在此情況下，穩態分布π * 是一個對應於特徵根為1的、該轉移矩陣的特徵向量。
如果轉移矩陣不可約，並且是非周期的，則收斂到一個每一列都是不同的平穩分布π * ，並且，
獨立於初始分布π。這是由Perron-Frobenius theorem所指出的。
正的轉移矩陣（即矩陣的每一個元素都是正的）是不可約和非周期的。矩陣被稱為是一個隨機矩陣，若且唯若這是某個馬爾可夫鏈中轉移機率的矩陣。
注意：在上面的定式化中，元素(i,j)是由j轉移到i的機率。有時候一個由元素(i,j)給出的等價的定式化等於由i轉移到j的機率。在此情況下，轉移矩陣僅是這裡所給出的轉移矩陣的轉置。另外，一個系統的平穩分布是由該轉移矩陣的左特徵向量給出的，而不是右特徵向量。
轉移機率獨立於過去的特殊況為熟知的Bernoulli scheme。僅有兩個可能狀態的Bernoulli scheme被熟知為貝努利過程
[編輯]馬爾可夫鏈模型的套用
[編輯]科學中的套用
馬爾可夫鏈通常用來建模排隊理論和統計學中的建模，還可作為信號模型用於熵編碼技術，如算法編碼。馬爾可夫鏈也有眾多的生物學套用，特別是人口過程，可以幫助模擬生物人口過程的建模。隱蔽馬爾可夫模型還被用於生物信息學，用以編碼區域或基因預測。
馬爾可夫鏈最近的套用是在地理統計學（geostatistics）中。其中，馬爾可夫鏈用在基於觀察數據的二到三維離散變數的隨機模擬。這一套用類似於“克里金”地理統計學（Kriging geostatistics），被稱為是“馬爾可夫鏈地理統計學”。這一馬爾可夫鏈地理統計學方法仍在發展過程中。
[編輯]人力資源中的套用
馬爾可夫鏈模型主要是分析一個人在某一階段內由一個職位調到另一個職位的可能性，即調動的機率。該模型的一個基本假設就是，過去的內部人事變動的模式和機率與未來的趨勢大體相一致。實際上，這種方法是要分析企業內部人力資源的流動趨勢和機率，如升遷、轉職、調配或離職等方面的情況，以便為內部的人力資源的調配提供依據。
它的基本思想是：通過發現過去組織人事變動的規律，以推測組織在未來人員的供給情況。馬爾可夫鏈模型通常是分幾個時期收集數據，然後再得出平均值，用這些數據代表每一種職位中人員變動的頻率，就可以推測出人員變動情況。
具體做法是：將計畫初期每一種工作的人數量與每一種工作的人員變動機率相乘，然後縱向相加，即得到組織內部未來勞動力的淨供給量。其基本表達式為：
Ni(t)：t時間內I類人員數量；
Pji：人員從j類向I類轉移的轉移率；
Vi(t)：在時間（t-1,t）I類所補充的人員數。
企業人員的變動有調出、調入、平調、晉升與降級五種。表3 假設一家零售公司在1999至2000年間各類人員的變動情況。年初商店經理有12人，在當年期間平均90％的商店經理仍在商店內，10％的商店經理離職，期初36位經理助理有 11％晉升到經理，83％留在原來的職務，6％離職；如果人員的變動頻率是相對穩定的，那么在2000年留在經理職位上有11人（12×90％），另外，經理助理中有4人（36×83％）晉升到經理職位，最後經理的總數是15人（11＋4）。可以根據這一矩陣得到其他人員的供給情況，也可以計算出其後各個時期的預測結果。假設的零售公司的馬爾可夫分析，見下表：
1999~2000 商店經理 經理助理 區域經理 部門經理 銷售員 離職
商店經理
(n=12) 90%
11 10%
1
經理助理
(n=36) 11%
4 83%
30 6%
2
區域經理
(n=96) 11%
11 66%
63 8%
8 15%
14
部門經理
(=288) 10%
29 72%
207 2%
6 16%
46
銷售員
(=1440) 6%
86 74%
1066 25%
228
供給預測 15 41 92 301 1072 351
來自"http://wiki.mbalib.com/wiki/%E9%A6%AC%E7%88%BE%E5%8F%AF%E5%A4%AB%E9%8F%88%E6%A8%A1%E5%9E%8B"
