馬可夫鏈

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢
一條簡單嘅馬可夫鏈個有向圖圖解;條鏈有兩個可能狀態-

馬可夫鏈粵拼maa5 ho2 fu1 lin2英文Markov chain)係概率論統計學等領域上常用嘅一種隨機模型,個名嚟自 19 世紀俄羅斯數學家安德里·馬可夫(Andrey Markov)。簡單講嘅話,一條馬可夫鏈會將世界想像成一嚿抽象化又有隨機性數學物體,即係會將研究緊嘅世界諗做由以下呢兩樣嘢構成[1][2]

  • 若干個可能嘅狀態(state),
  • 每個狀態 都會褦住柞數 嚟表示世界由 呢個狀態變成另一個狀態嘅機會率

例如幅附圖入面嗰條簡單嘅馬可夫鏈就係噉:條馬可夫鏈有 兩個可能狀態;如果家陣世界嘅狀態係 ,下一刻狀態變成 嘅機率係 70%,狀態繼續維持係 嘅機率係 30%;如果家陣世界嘅狀態係 ,下一刻狀態變成 嘅機率係 40%,狀態繼續係 嘅機率係 60%。除此之外,馬可夫鏈仲可以按好多特性分做進階嘅類別,例如隱馬可夫模型就係一種特殊嘅馬可夫鏈,指條鏈當中有一部份嘅狀態係研究者觀察唔到嘅(隱藏狀態),研究者要齋靠觀察淨低嗰啲(觀察得到嘅)狀態嚟對隱藏狀態作出判斷[1][3]

喺好多科學工程學領域裏面,馬可夫鏈都係一種有用嘅分析工具,可以攞嚟模擬研究緊嘅現象[4],例如人工智能(AI)上嘅研究就好興教啲人工智能程式將世界抽象化噉諗做一條條嘅馬可夫鏈,用過往所得嘅數據建立心目中嘅馬可夫鏈模型-「根據過去經驗,而家狀態係 下一刻變 嘅機率係咁多咁多」,而人工智能程式跟住就會按「跟住落嚟世界變成呢個狀態嘅機率係幾多」等嘅資訊嚟做決策[5][6]

定義[編輯]

馬可夫鏈轉移矩陣嘅示意圖;表示返上高幅有向圖入面嗰啲轉移()。
內文:概率論
睇埋:隨機過程馬可夫性質同埋有限狀態機

定義上,一條基本嘅馬可夫鏈係具有以下呢三大特性嘅隨機過程[註 1][7][8][9]

  1. 有若干個可能狀態(state)。技術性啲噉講,即係話狀態 嘅可能數值組成 噉嘅一個狀態空間(state space;指一個系統啲可能狀態冚唪唥包埋一齊嘅一個)-
    • 呢個狀態空間係一個可數集 所有可能數值都係自然數),而且
    • 條馬可夫鏈仲要有個概率分佈表示每個狀態有幾大機率會係初始狀態,
  2. 有若干條規則指明狀態之間嘅轉移機率(transition probability);通常嚟講,馬可夫鏈啲狀態轉移會由時間決定,所以轉移機率可以寫做 噉嘅樣,當中 係指時間點,即係:
    • 用日常用語講嘅話,上面呢條式嘅意思如下: 嘅數值反映「如果已知呢一刻時間嘅狀態()係 ,噉下一刻時間嘅狀態()係 」嘅機率
  3. 滿足到馬可夫性質(Markov property),噉講意思即係話個系統冇「記憶」呢種功能,「下一刻狀態會變乜」完全淨係取決於而家呢刻嘅狀態,而家呢刻打前嗰啲時間點嘅狀態唔會影響下一刻嘅狀態係乜。技術啲噉講嘅話,馬可夫性質可以用以下噉嘅形式表達:
    • 當中 意係話「無論 處於邊個可能數值都好,條式都會成立」。

一條馬可夫鏈可以用最少兩種方法嚟表示:一方面,馬可夫鏈可以畫做有向圖,即係幅圖有若干個頂點(喺文頭幅圖當中係啲有字母喺裏面嘅圓圈),頂點之間有啲箭咀表示頂點之間可以點樣變化,而每個箭咀都褦住個喺 0 同 1 之間嘅數,表示個箭咀指定嘅嗰種狀態轉移發生嘅機率,當中可以有頂點係有箭咀指住自己嘅;另一方面,馬可夫鏈又可以記做轉移矩陣(transition matrix),即係話畫一啲 矩陣 畀條 鏈,當中 係啲可能狀態嘅數量,矩陣打戙行表示「而家啲狀態」,打橫行表示「跟住落嚟啲狀態」,而啲矩陣嘅每個元素都係一個 [8]

特性[編輯]

馬可夫鏈可以具有以下呢啲數學特性[7][8]

  • 不可約性(irreducibility):如果有條馬可夫鏈,是但攞條鏈嘅兩個可能狀態 ),兩個狀態之間嘅轉移機率都會係大過 0 嘅話, 而且 ,噉條馬可夫鏈就算係不可約嘅(irreducible)-簡單噉講,即係話每一個狀態都有可能直接轉移去任何一個其他可能狀態嗰度。
  • 即逝性(transience)同恆常性(recurrence):如果有個狀態,一旦離開咗個狀態,就有機會永遠都唔再返去嗰個狀態嘅(「返去個狀態嘅機率 」係有可能嘅),噉呢個狀態就算係即逝嘅;相反嚟講,如果有個狀態係一旦離開咗最後實會返去一次嘅(返去個狀態嘅機率 ;即係話個狀態唔係即逝嘅),噉呢個狀態就算係恆常嘅
  • 例如以下呢條馬可夫鏈就係不可約嘅,而且由三個()恆常嘅狀態組成:
Elementarymarkow.png
  • 靜止分佈(stationary distribution):假想有個概率分佈 基於狀態空間 (簡單講嘅話,即係 表示緊「响每個時間點 ,每個狀態有幾大機率係條鏈身處嘅狀態」);如果話 係一個靜止分佈,意思即係話以下條式成立:
    • 簡化噉講嘅話,
      • 係指「而家呢個時間點處於 嘅機率」;
      • 係指「跟住嗰個時間點處於 嘅機率」;
      • 喺呢種情況下,條馬可夫鏈會「靜止」-雖然狀態係有可能變化,但成條鏈都唔會隨時間而演變,無論時間過咗幾耐,每個可能狀態成為條鏈嘅現時狀態嘅機率都唔會變。

... 等等。

建立方法[編輯]

內文:馬可夫鏈蒙地卡羅

馬可夫鏈蒙地卡羅(Markov chain Monte Carlo,MCMC)係一系列統計學上成日用嘅演算法,能夠由數據嗰度建立一條馬可夫鏈表達世界嘅狀態,跟手再靠用條馬可夫鏈做模擬嚟搵出想要嘅概率分佈[10]

類型[編輯]

參數學習[編輯]

睇埋:機械學習

對於攞 表示序號嘅一排 條序迾嘅集合 ,要學到個馬可夫鏈模型畀佢嘅話,所有啲要學到嘅概率可以參照上高聯合概率分佈,得表示成:

直白啲講,條式右手便第一匹連乘表示由所有啲序迾嘅初始狀態出發,第二匹表示行勻啲路線到 去,而初始同埋轉移兩匹概率都要學澌。由於一種初始態可能出好多次,某種轉移亦都可能出過好多次,所以可以分別合併啲一樣嘅初始狀態概率 與及一樣嘅轉移概率 各自到一齊,攞次數項 表示佢哋一隻各自出現過幾多次;再成條式求對數,即有:

其中兩個次數項分別係: 係某種初始狀態出現嘅次數, 係撞親某狀態 前提下有後續狀態 嘅次數。喺對數式上求最大化可以學得到啲參數(概率)。

對於一般嘅馬可夫鏈嚟講,因爲可能受時間影響所以有 咁多參數要學(學初始狀態佮埋學 嘅矩陣 );對於齊時馬可夫鏈來講即衹有 個要學。

應用[編輯]

簡史[編輯]

註釋[編輯]

  1. 有關呢啲數學符號嘅意思,詳情可以睇吓概率論

文獻[編輯]

睇埋[編輯]

[編輯]

  1. 1.0 1.1 Gagniuc, Paul A. (2017). Markov Chains: From Theory to Implementation and Experimentation. USA, NJ: John Wiley & Sons. pp. 1-8.
  2. Samuel Karlin; Howard E. Taylor (2 December 2012). A First Course in Stochastic Processes. Academic Press. p. 47.
  3. Satish L, Gururaj BI (April 2003). "Use of hidden Markov models for partial discharge pattern classification". IEEE Transactions on Dielectrics and Electrical Insulation.
  4. Gupta, Ankur; Rawlings, James B. (April 2014). "Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology". AIChE Journal. 60 (4): 1253–1268.
  5. Filar, J. & Vrieze, K. (1997). Competitive Markov Decision Processes. Springer-Verlag.
  6. Van Ravenzwaaij, Don; Cassey, Pete; Brown, Scott D. (2016-03-11). "A simple introduction to Markov Chain Monte-Carlo sampling". Psychonomic Bulletin & Review. 25 (1): 143–154.
  7. 7.0 7.1 Introduction to Markov chains. Towards Data Science.
  8. 8.0 8.1 8.2 Gagniuc, Paul A. (2017). Markov Chains: From Theory to Implementation and Experimentation. USA, NJ: John Wiley & Sons. pp. 1-235.
  9. Parzen, E. (2015). Stochastic Processes. Courier Dover Publications. p. 188.
  10. Andrieu, C., De Freitas, N., Doucet, A., & Jordan, M. I. (2003). An introduction to MCMC for machine learning (PDF). Machine learning, 50(1), 5-43.

[編輯]