iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 22
1

上次我們講完在空間上,我們可以知道資料的區域性,並且利用 convolution 來萃取特徵。

這次我們來講時間,其實不一定要是"時間"序列資料,只要是有先後順序的資料就可以。

在時間序列分析及統計的領域中,我們有基礎的馬可夫模型(Markov chain)。

Markov chain

馬可夫模型是這樣的,他假設一個變數有不同種的狀態,例如下圖:

在這邊有4個狀態,一個圓圈代表一個狀態,狀態跟狀態之間會隨著時間改變,每個狀態會有一定機率變成其他狀態,或是維持原本的狀態不變。

我們可以把目前的狀態用一個向量來表達:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%7D%20%3D%20%20%5Cbegin%7Bbmatrix%7D%20y_1%26y_2%26y_3%26y_4%20%5C%5C%5C%5C%20%5Cend%7Bbmatrix%7D

注意:我們這邊使用的向量為列向量(row vector),一般在其他數學領域使用的則是行向量(column vector),兩者是可以藉由轉置來互換的,並不影響運算結果

我們這邊用 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%7D 代表他是可以被觀察到的。狀態變化我們可以用一個矩陣來表達:

https://chart.googleapis.com/chart?cht=tx&chl=A%20%3D%20%5Ba_%7Bij%7D%5D%20%3D%20%20%5Cbegin%7Bbmatrix%7D%20a_%7B11%7D%26%20a_%7B12%7D%26%20a_%7B13%7D%26%20a_%7B14%7D%20%5C%5C%5C%5C%20a_%7B21%7D%26%20a_%7B22%7D%26%20a_%7B23%7D%26%20a_%7B24%7D%20%5C%5C%5C%5C%20a_%7B31%7D%26%20a_%7B32%7D%26%20a_%7B33%7D%26%20a_%7B34%7D%20%5C%5C%5C%5C%20a_%7B41%7D%26%20a_%7B42%7D%26%20a_%7B43%7D%26%20a_%7B44%7D%20%5C%5C%5C%5C%20%5Cend%7Bbmatrix%7D

其中 https://chart.googleapis.com/chart?cht=tx&chl=a_%7Bij%7D 代表的是由狀態 i 變成狀態 j 的機率,這邊要注意的是,每一個列(row)的機率總和要是 1。

由於我們的向量都是 row vector,A 為一 right stochastic matrix,運算形式為 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%7D%20A
由狀態 i 變成其他狀態之機率和為 1(https://chart.googleapis.com/chart?cht=tx&chl=A%20%5Cmathbf%7B1%7D%20%3D%20%5Cmathbf%7B1%7D)。

所以不同時間點的狀態變化關係可以寫成以下式子:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t)%7D%7D%20%3D%20%5Cmathbf%7By%5E%7B(t-1)%7D%7D%20A

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t)%7D%7D 的意思是第 t 次(或是時間為 t)的狀態,https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t-1)%7D%7D 狀態會經過一次轉換或是運算轉變成 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t)%7D%7D

如果你把其中的第一項的運算拆開來看就會長這樣,可以自行檢驗狀態的變化:

https://chart.googleapis.com/chart?cht=tx&chl=y_1%5E%7B(t)%7D%20%3D%20a_%7B11%7Dy_1%5E%7B(t-1)%7D%20%2B%20a_%7B12%7Dy_2%5E%7B(t-1)%7D%20%2B%20a_%7B13%7Dy_3%5E%7B(t-1)%7D%20%2B%20a_%7B14%7Dy_4%5E%7B(t-1)%7D

從時間軸上來看,我們可以把狀態的轉變畫出來像是這樣:

每次的轉變我們都可以看成一個函數 f,他其實等同於上面提到的矩陣:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t)%7D%7D%20%3D%20f(%5Cmathbf%7By%5E%7B(t-1)%7D%7D)%20%3D%20%5Cmathbf%7By%5E%7B(t-1)%7D%7D%20A

所以他的意思是,https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t-1)%7D%7D 會經由 f 變成 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t)%7D%7D,所以這是單純的狀態變化。

上面的矩陣當中其實內容是機率,我們也可以把他轉成機率的寫法,但是解釋會變得不太一樣:

https://chart.googleapis.com/chart?cht=tx&chl=p%20%3D%20f(%5Cmathbf%7By%5E%7B(t)%7D%7D%20%5Cmid%20%5Cmathbf%7By%5E%7B(t-1)%7D%7D)%20%3D%20P(%5Cmathbf%7By%5E%7B(t)%7D%7D%20%5Cmid%20%5Cmathbf%7By%5E%7B(t-1)%7D%7D)

這邊的解釋是,https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t-1)%7D%7D 會經由 f 變成 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t)%7D%7D 的機率

下句跟上句的不同在於,上句的描述是肯定的,他只描述了狀態的改變,但是下句多加描述了 這件事會發生的機率,所以應該要把 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t)%7D%7D%20%5Cmid%20%5Cmathbf%7By%5E%7B(t-1)%7D%7D 理解成 這一件事,那麼 f 的輸出就是機率了。

我們可以把上圖 收起來,所以看起來會像這樣:

花了點時間把一些符號跟數學概念講完了,來談談他的假設,一般來說,馬可夫模型最大的假設在於:

https://chart.googleapis.com/chart?cht=tx&chl=P(%5Cmathbf%7By%5E%7B(t)%7D%7D%20%5Cmid%20%5Cmathbf%7By%5E%7B(1)%7D%7D%2C%20%5Cmathbf%7By%5E%7B(2)%7D%7D%2C%20%5Cdots%2C%20%5Cmathbf%7By%5E%7B(t-1)%7D%7D)%20%3D%20P(%5Cmathbf%7By%5E%7B(t)%7D%7D%20%5Cmid%20%5Cmathbf%7By%5E%7B(t-1)%7D%7D)

也就是要預測第 t 單位時間的狀態,我們經歷了第 1~(t - 1) 單位時間,但是他只需要用前一個時間單位的狀態就可以預測下一個狀態,前面很多狀態都是不必要的,這我們稱為一階馬可夫模型(first-order Markov chain)。

當然可以推廣到 m 階馬可夫模型(m th-order Markov chain),那代表需要前 m 個狀態來預測下一個狀態,順帶一提,有零階馬可夫模型,那就跟我們一般的機率分佈模型(https://chart.googleapis.com/chart?cht=tx&chl=P(%5Cmathbf%7By%5E%7B(t)%7D%7D))一樣。

沒有特別提的話,通常大家談的馬可夫模型都是一階馬可夫模型。一般來說,他有個非常重要的特性,就是 無記憶性,也就是他不會去記住他所經歷的狀態,他只需要用現在的狀態就可以預測下一個狀態。

不過我要特別提一下這個模型的一些其他假設:

  • 狀態是離散的。在馬可夫模型的狀態空間中是離散的,也就是你可以用一個正整數來數出有幾種狀態存在。
  • 時間是離散的。我們剛剛有看到他計算的是第 t 單位時間,下一次就是乘上一個矩陣之後成為第 t+1 單位時間。
  • 狀態是可被觀察的。
  • 以一個隨機變數作為一個狀態。

接下來我們來談談另一個模型。

Hidden Markov model

接下來是進階版的隱馬可夫模型(hidden Markov model),他的假設是這樣的,在一個系統中存在一些我們看不到的狀態,是系統的內在狀態,隨著系統的內在狀態不同,他所表現出來的外在狀態也不同,而外在狀態是我們可以觀測到的。

大家可以看到這個圖跟剛剛的很相似,帶是又多了一些東西。較大的圈圈是內在狀態,小的圈圈是外在狀態。隨著時間改變,內在狀態會隨著變動,內在狀態的變動我們可以用一個矩陣來表示:

https://chart.googleapis.com/chart?cht=tx&chl=A%20%3D%20%5Ba_%7Bij%7D%5D%20%3D%20%20%5Cbegin%7Bbmatrix%7D%20a_%7B11%7D%26%20a_%7B12%7D%26%20a_%7B13%7D%26%20a_%7B14%7D%20%5C%5C%5C%5C%20a_%7B21%7D%26%20a_%7B22%7D%26%20a_%7B23%7D%26%20a_%7B24%7D%20%5C%5C%5C%5C%20a_%7B31%7D%26%20a_%7B32%7D%26%20a_%7B33%7D%26%20a_%7B34%7D%20%5C%5C%5C%5C%20a_%7B41%7D%26%20a_%7B42%7D%26%20a_%7B43%7D%26%20a_%7B44%7D%20%5C%5C%5C%5C%20%5Cend%7Bbmatrix%7D

裏面裝的一樣是機率。接下來,不同的內在狀態有不同的機率會噴出(emit)外在狀態,這也會用另一個矩陣表示:

https://chart.googleapis.com/chart?cht=tx&chl=B%20%3D%20%5Bb_%7Bij%7D%5D%20%3D%20%20%5Cbegin%7Bbmatrix%7D%20b_%7B11%7D%26%20b_%7B12%7D%26%20b_%7B13%7D%26%20b_%7B14%7D%20%5C%5C%5C%5C%20b_%7B21%7D%26%20b_%7B22%7D%26%20b_%7B23%7D%26%20b_%7B24%7D%20%5C%5C%5C%5C%20b_%7B31%7D%26%20b_%7B32%7D%26%20b_%7B33%7D%26%20b_%7B34%7D%20%5C%5C%5C%5C%20%5Cend%7Bbmatrix%7D

寫成狀態轉移的關係式的話會變成:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bh%5E%7B(t)%7D%7D%20%3D%20%5Cmathbf%7Bh%5E%7B(t-1)%7D%7D%20A

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bh%5E%7B(t)%7D%7D 代表在第 t 單位時間的內在狀態。

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t)%7D%7D%20%3D%20%5Cmathbf%7Bh%5E%7B(t)%7D%7D%20B

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7By%5E%7B(t)%7D%7D 代表在第 t 單位時間根據內在狀態噴出的外在狀態。

如果在時間軸上表達的話是這個樣子:

由於在這邊又多了一個內在狀態,所以在模型的表達力上遠遠超越馬可夫模型。舉個例子好了,假設小明很好奇在不同天氣的時候外面的人吃冰淇淋的狀況是如何,但是小明又很懶得出門看天氣,這時候他就假設天氣(晴天、陰天、雨天)是內在狀態(看不到),然後他觀察路上的人吃冰淇淋(外在狀態,吃、不吃)的多寡,這時候這麼模型就可以派上用場,他藉由持續觀察路人有沒有吃冰淇淋,可以推論外面天氣的變化狀況。

這時候我們也來總結一下,這個模型的假設:

  • 內在狀態跟外在狀態都是離散的。
  • 時間是離散的。
  • 內在狀態是不能被觀察的,外在狀態是可被觀察的。
  • 以一個隨機變數作為一個狀態。

上一篇
22 Convolutional encoder-decoder 架構
下一篇
24 Recurrent neural network
系列文
機器學習模型圖書館:從傳統模型到深度學習31

尚未有邦友留言

立即登入留言