【機(jī)器學(xué)習(xí)】馬爾可夫鏈 ▏小白都能看懂的馬爾可夫鏈詳解
共 5422字，需瀏覽 11分鐘
·
2024-05-23 12:00
1.什么是馬爾可夫鏈
在機(jī)器學(xué)習(xí)算法中，馬爾可夫鏈(Markov chain)是個(gè)很重要的概念。馬爾可夫鏈（Markov chain），又稱離散時(shí)間馬爾可夫鏈（discrete-time Markov chain），因俄國(guó)數(shù)學(xué)家安德烈·馬爾可夫（俄語(yǔ)：Андрей Андреевич Марков）得名，為狀態(tài)空間中經(jīng)過(guò)從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)換的隨機(jī)過(guò)程。該過(guò)程要求具備“無(wú)記憶”的性質(zhì)：下一狀態(tài)的概率分布只能由當(dāng)前狀態(tài)決定，在時(shí)間序列中它前面的事件均與之無(wú)關(guān)。這種特定類型的“無(wú)記憶性”稱作馬爾可夫性質(zhì)。馬爾科夫鏈作為實(shí)際過(guò)程的統(tǒng)計(jì)模型具有許多應(yīng)用。
在馬爾可夫鏈的每一步，系統(tǒng)根據(jù)概率分布，可以從一個(gè)狀態(tài)變到另一個(gè)狀態(tài)，也可以保持當(dāng)前狀態(tài)。狀態(tài)的改變叫做轉(zhuǎn)移，與不同的狀態(tài)改變相關(guān)的概率叫做轉(zhuǎn)移概率。隨機(jī)漫步就是馬爾可夫鏈的例子。隨機(jī)漫步中每一步的狀態(tài)是在圖形中的點(diǎn)，每一步可以移動(dòng)到任何一個(gè)相鄰的點(diǎn)，在這里移動(dòng)到每一個(gè)點(diǎn)的概率都是相同的（無(wú)論之前漫步路徑是如何的）。
2.一個(gè)經(jīng)典的馬爾科夫鏈實(shí)例
用一句話來(lái)概括馬爾科夫鏈的話，那就是某一時(shí)刻狀態(tài)轉(zhuǎn)移的概率只依賴于它的前一個(gè)狀態(tài)。
舉個(gè)簡(jiǎn)單的例子，假如每天的天氣是一個(gè)狀態(tài)的話，那個(gè)今天是不是晴天只依賴于昨天的天氣，而和前天的天氣沒(méi)有任何關(guān)系。
這么說(shuō)可能有些不嚴(yán)謹(jǐn)，但是這樣做可以大大簡(jiǎn)化模型的復(fù)雜度，因此馬爾科夫鏈在很多時(shí)間序列模型中得到廣泛的應(yīng)用，比如循環(huán)神經(jīng)網(wǎng)絡(luò)RNN，隱式馬爾科夫模型HMM等。
假設(shè)狀態(tài)序列為
由馬爾科夫鏈定義可知，
時(shí)刻Xt+1 的狀態(tài)只與Xt 有關(guān)，用數(shù)學(xué)公式來(lái)描述就是：
既然某一時(shí)刻狀態(tài)轉(zhuǎn)移的概率只依賴前一個(gè)狀態(tài)，那么只要求出系統(tǒng)中任意兩個(gè)狀態(tài)之間的轉(zhuǎn)移概率，這個(gè)馬爾科夫鏈的模型就定了?？匆粋€(gè)具體的例子。
這個(gè)馬爾科夫鏈?zhǔn)潜硎竟墒心Ｐ偷模灿腥N狀態(tài)：牛市（Bull market）, 熊市（Bear market）和橫盤（Stagnant market）。
每一個(gè)狀態(tài)都以一定的概率轉(zhuǎn)化到下一個(gè)狀態(tài)。比如，牛市以0.025的概率轉(zhuǎn)化到橫盤的狀態(tài)。這個(gè)狀態(tài)概率轉(zhuǎn)化圖可以以矩陣的形式表示。如果我們定義矩陣陣P某一位置P(i, j)的值為P(j|i)，即從狀態(tài)i變?yōu)闋顟B(tài)j的概率。另外定義牛市、熊市、橫盤的狀態(tài)分別為0、1、2，這樣我們得到了馬爾科夫鏈模型的狀態(tài)轉(zhuǎn)移矩陣為：
當(dāng)這個(gè)狀態(tài)轉(zhuǎn)移矩陣P確定以后，整個(gè)股市模型就已經(jīng)確定！
3.狀態(tài)轉(zhuǎn)移矩陣
從上面的例子不難看出來(lái)，整個(gè)馬爾可夫鏈模型的核心是狀態(tài)轉(zhuǎn)移矩陣P。那這個(gè)矩陣P有一些什么有意思的地方呢？接下來(lái)再看一下。
以股市模型為例，假設(shè)初始狀態(tài)為t0=[0.1,0.2,0.7] ，然后算之后的狀態(tài)。
最終輸出結(jié)果為
從第18次開(kāi)始，狀態(tài)就開(kāi)始收斂至[0.624,0.312,0.0625] 。最終數(shù)字上略有不同，只是計(jì)算機(jī)浮點(diǎn)數(shù)運(yùn)算造成的罷了。
如果我們換一個(gè)初始狀態(tài)t0 ，比如[0.2,0.3.0.5] 繼續(xù)運(yùn)行上面的代碼，只是將init_array變一下，最后結(jié)果為：
到第18次的時(shí)候，
又收斂到了[0.624,0.312,0.0625]
這個(gè)轉(zhuǎn)移矩陣就厲害了。不管我們的初始狀態(tài)是什么樣子的，只要狀態(tài)轉(zhuǎn)移矩陣不發(fā)生變化，當(dāng)n→∞ 時(shí)，最終狀態(tài)始終會(huì)收斂到一個(gè)固定值。
在矩陣分析，自動(dòng)控制原理等過(guò)程中，經(jīng)常會(huì)提到矩陣的冪次方的性質(zhì)。我們也看看這個(gè)狀態(tài)轉(zhuǎn)移矩陣P的冪次方有什么有意思的地方？直接上代碼。
代碼運(yùn)行結(jié)果為
從第20次開(kāi)始，結(jié)果開(kāi)始收斂，并且每一行都為[0.625,0.312,0.0625] 。
4.馬爾可夫鏈細(xì)致平穩(wěn)條件
首先，馬爾科夫鏈要能收斂，需要滿足以下條件：
1.可能的狀態(tài)數(shù)是有限的。
2.狀態(tài)間的轉(zhuǎn)移概率需要固定不變。
3.從任意狀態(tài)能夠轉(zhuǎn)變到任意狀態(tài)。
4.不能是簡(jiǎn)單的循環(huán)，例如全是從x到y(tǒng)再?gòu)膟到x。
以上是馬爾可夫鏈?zhǔn)諗康谋匾獥l件。
假設(shè)有一個(gè)概率的單純形向量
有一個(gè)概率轉(zhuǎn)移矩陣P PP，例如我們前面的例子：
其中，v0 每個(gè)元素的取值范圍為[0,1]，并且所有元素的和為1。而P 的每一行也是個(gè)概率單純形向量。
由前面的例子我們不難看出，當(dāng)v0 與P 的n次冪相乘以后，發(fā)現(xiàn)得到的向量都會(huì)收斂到一個(gè)穩(wěn)定值，而且此穩(wěn)定值與初始向量v0 無(wú)關(guān)！
那么所有的轉(zhuǎn)移矩陣P 都有這種現(xiàn)象嘛？或者說(shuō)滿足什么樣的條件的轉(zhuǎn)移矩陣P會(huì)有這種現(xiàn)象？
細(xì)致平衡條件（Detailed Balance Condition）：給定一個(gè)馬爾科夫鏈，分布π和概率轉(zhuǎn)移矩陣P，如果下面等式成立:
則此馬爾科夫鏈具有一個(gè)平穩(wěn)分布（Stationary Distribution)。
證明過(guò)程比較簡(jiǎn)單：
上式取j→∞ ，就可以得到矩陣表達(dá)式：
5.馬爾可夫鏈?zhǔn)諗啃再|(zhì)
如果一個(gè)非周期的馬爾可夫鏈?zhǔn)諗?，有狀態(tài)轉(zhuǎn)移矩陣P，并且任何兩個(gè)狀態(tài)都是連通的，那么
π是方程πP=π 的唯一非負(fù)解，其中：
? END ?
文章來(lái)源：CSDN博主「bitcarmanlee」
原文鏈接：https://blog.csdn.net/bitcarmanlee/java/article/details/82819860
往期精彩回顧
交流群
歡迎加入機(jī)器學(xué)習(xí)愛(ài)好者微信群一起和同行交流，目前有機(jī)器學(xué)習(xí)交流群、博士群、博士申報(bào)交流、CV、NLP等微信群，請(qǐng)掃描下面的微信號(hào)加群，備注：”昵稱-學(xué)校/公司-研究方向“，例如：”張小明-浙大-CV“。請(qǐng)按照格式備注，否則不予通過(guò)。添加成功后會(huì)根據(jù)研究方向邀請(qǐng)進(jìn)入相關(guān)微信群。請(qǐng)勿在群內(nèi)發(fā)送廣告，否則會(huì)請(qǐng)出群，謝謝理解~（也可以加入機(jī)器學(xué)習(xí)交流qq群772479961）