The Introduction of the Markov Chain

Kinna Chen
May 9 · 5 min read

在許多機器學習的章節中,常常遇見 HMM ,往往看到它的數學式子後,就當沒看到似的跳過去了,其實它的基礎理論並不難,尤其是 Markov Chain 在高中數學課本就已經出現過了,但….那麼久遠的事,相信大家都忘得差不多了,現在一起來回顧一下吧!!!

• Markov Chain

在狀態空間中,了解當前的狀態與下一個狀態發生的隨機過程。
(痾….有講等於沒講,來看一下 Key point 吧!)

Key point:
如左下圖,現有三間大型賣場在 AIA 附近,分別是 Costco、愛買、大潤發,已知顧客今日在各個賣場間流動的固定機率 (invariant),亦即圖上的數字,值得注意的是,從每間賣場畫出去箭頭上的數字相加起來為 1 (ex: Costco 0.7+0.2+1 = 1)。接著來看一下範例吧…

今天剛來 AIA 報到的學員圓仔,看到賣場廣告後,會到三間賣場的機率分別為 0.5、0.1、0.4 ,那麼上課第三天圓仔會到 Costco 逛的機率是多少?(解法如下)

Introduction:
透過上述例子可以知道,當前的狀態跟上一個狀態有關,是不是有些感覺了咧?接下來,就跟著一起走進數學的世界吧!!!!

符號介紹:
•假設有 N 個狀態,分別標示為 s₁, s₂, …, s_N
•假設從當前狀態 sᵢ 變成 sⱼ 的機率為 aᵢⱼ,可表示成轉移矩陣(Transition Matrix) A,如下…

•我們紀錄第 t 秒的狀態在第 i 個狀態為 qₜ = i
•起始時間選定某個狀態 sᵢ 的機率為 πᵢ ,又可標為 P(q₀ = j)

State Sequence:
一開始我們會選定一個起狀態,然後每過一個單位時間,就會選擇走過某一條與當下狀態相關的邊,到達下一個狀態,經過 T 秒後,我們就會得到一條有 T 條邊、 T+1 個狀態的有序路徑(亦稱之,state sequence)。

如果上述說的實在抽象,我們用3個狀態、5個時間單位說明吧!如左圖和表格,我們經過 5個時間點,會得到 6 個狀態的一條路徑,因此我們可以算得形成這條路徑的機率是多少?

機率 = π₁ a₁₃ a₃₂ a₂₂ a₂₁ a₁₃

上述的例子,應該可以讓大家比較有深刻的感觸吧!不免俗的,還是用數學式子寫一下….在有 T 個時間單位下….我們會得到 state sequence Q

最後,可以得到 Q 的機率為

Comment:
在固定狀態轉換 (invariant)的機率下,一切如上述,似乎單純,如果我們再加入一些變動因素,舉兩個常見的例子來看看啦!

(1)學員圓仔每日到賣場的機率,會加入他當日出差路線而有異動,即是與時間相關的非固定狀態 (time variant)啦!其實也沒那麼複雜,底下的圖,讓你秒懂這一切。

(2)學員圓仔每日到某賣場的機率,會受到前一日或是前兩日去過哪間賣場的影響,前者稱為 first-order,後者稱為 second-order,聽起來很難,其實也沒什麼,圖畫出來就知道簡單了。

這些東西到底哪時候才會用到呢?只要有時間關係的,例如,RNN、NLP、RL,都可以用 Markov chain 的變化形態來解釋喔!

下一章 Hidden Markov Model_part2 會帶大家認識聞風喪膽的「Hidden Markov Model」,敬請期待吧!!!

Reference:
(1)演算法筆記- Hidden Markov Model
(2)Hidden Markov Models — Stanford University

Taiwan AI Academy

news, tech reviews and supplemental materials

Kinna Chen

Written by

Taiwan AI Academy

news, tech reviews and supplemental materials

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade