【機(jī)器學(xué)習(xí)】馬爾可夫鏈 ▏小白都能看懂的馬爾可夫鏈詳解

在機(jī)器學(xué)習(xí)算法中，馬爾可夫鏈(Markov chain)是個(gè)很重要的概念。馬爾可夫鏈（Markov chain），又稱離散時(shí)間馬爾可夫鏈（discrete-time Markov chain），因俄國數(shù)學(xué)家安德烈·馬爾可夫（俄語：Андрей Андреевич Марков）得名，為狀態(tài)空間中經(jīng)過從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)換的隨機(jī)過程。該過程要求具備“無記憶”的性質(zhì)：下一狀態(tài)的概率分布只能由當(dāng)前狀態(tài)決定，在時(shí)間序列中它前面的事件均與之無關(guān)。這種特定類型的“無記憶性”稱作馬爾可夫性質(zhì)。馬爾科夫鏈作為實(shí)際過程的統(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)，每一步可以移動到任何一個(gè)相鄰的點(diǎn)，在這里移動到每一個(gè)點(diǎn)的概率都是相同的（無論之前漫步路徑是如何的）。

用一句話來概括馬爾科夫鏈的話，那就是某一時(shí)刻狀態(tài)轉(zhuǎn)移的概率只依賴于它的前一個(gè)狀態(tài)。

舉個(gè)簡單的例子，假如每天的天氣是一個(gè)狀態(tài)的話，那個(gè)今天是不是晴天只依賴于昨天的天氣，而和前天的天氣沒有任何關(guān)系。

這么說可能有些不嚴(yán)謹(jǐ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é)公式來描述就是：

既然某一時(shí)刻狀態(tài)轉(zhuǎn)移的概率只依賴前一個(gè)狀態(tài)，那么只要求出系統(tǒng)中任意兩個(gè)狀態(tài)之間的轉(zhuǎn)移概率，這個(gè)馬爾科夫鏈的模型就定了?？匆粋€(gè)具體的例子。

這個(gè)馬爾科夫鏈?zhǔ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)確定！

從上面的例子不難看出來，整個(gè)馬爾可夫鏈模型的核心是狀態(tài)轉(zhuǎn)移矩陣P。那這個(gè)矩陣P有一些什么有意思的地方呢？接下來再看一下。

以股市模型為例，假設(shè)初始狀態(tài)為t0=[0.1,0.2,0.7] ，然后算之后的狀態(tài)。

最終輸出結(jié)果為

從第18次開始，狀態(tà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)始終會收斂到一個(gè)固定值。

在矩陣分析，自動控制原理等過程中，經(jīng)常會提到矩陣的冪次方的性質(zhì)。我們也看看這個(gè)狀態(tài)轉(zhuǎn)移矩陣P的冪次方有什么有意思的地方？直接上代碼。

代碼運(yùn)行結(jié)果為

從第20次開始，結(jié)果開始收斂，并且每一行都為[0.625,0.312,0.0625] 。

首先，馬爾科夫鏈要能收斂，需要滿足以下條件：

1.可能的狀態(tài)數(shù)是有限的。

2.狀態(tài)間的轉(zhuǎn)移概率需要固定不變。

3.從任意狀態(tài)能夠轉(zhuǎn)變到任意狀態(tài)。

4.不能是簡單的循環(huán)，例如全是從x到y(tǒng)再從y到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)得到的向量都會收斂到一個(gè)穩(wěn)定值，而且此穩(wěn)定值與初始向量v0 無關(guān)！

那么所有的轉(zhuǎn)移矩陣P 都有這種現(xiàn)象嘛？或者說滿足什么樣的條件的轉(zhuǎn)移矩陣P會有這種現(xiàn)象？

細(xì)致平衡條件（Detailed Balance Condition）：給定一個(gè)馬爾科夫鏈，分布π和概率轉(zhuǎn)移矩陣P，如果下面等式成立:

則此馬爾科夫鏈具有一個(gè)平穩(wěn)分布（Stationary Distribution)。

證明過程比較簡單：

上式取j→∞ ，就可以得到矩陣表達(dá)式：

如果一個(gè)非周期的馬爾可夫鏈?zhǔn)諗?，有狀態(tài)轉(zhuǎn)移矩陣P，并且任何兩個(gè)狀態(tài)都是連通的，那么

π是方程πP=π 的唯一非負(fù)解，其中：

?  END  ?

文章來源：CSDN博主「bitcarmanlee」

原文鏈接：https://blog.csdn.net/bitcarmanlee/java/article/details/82819860

往期精彩回顧




適合初學(xué)者入門人工智能的路線及資料下載
(圖文+視頻)機(jī)器學(xué)習(xí)入門系列下載
機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印
《統(tǒng)計(jì)學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專輯

機(jī)器學(xué)習(xí)交流qq群955171419，加入微信群請掃碼