ㄚㄚHidden Markov Model (part 3)
深入了解 Hidden Markov Model 的訓練理論
在前面 part 2 有提醒大家慎入唷！有滿滿多出來的數學式，要 hold 住呀！
底下我們分成幾個部分來說明和演算法：
HMM 三大問題
a. Evaluation Problem — Forward-backward Algorithm
b. Decoding Problem — Viterbi Algorithm
c. Learning Problem — EM Algorithm
d. (補充) Continuous Hidden Markov Chain
在進入主題前，再重申一次問題，如下圖…
我們需計算在已知觀察序列 O(o₁, o₂, o₃, …, oₜ) ，但未知轉移矩陣的條件下，找出其對應的的所有可能狀態序列 Q(q₁, q₂, q₃, …, qₜ) ，以及其中最大機率之狀態序列。
HMM 三大問題
有些人大概覺得簡單吧！暴力法就可以解決了，窮舉出所有可能的路徑，並計算每條路徑的機率，不就結束了嗎？就是每條路徑都算過，痾....時間複雜度是O(N^TT)呀！大大，在文明的21世紀，我們不能這麼暴力呀！
以下的演算法要跟大家介紹，如何降低計算的時間複雜度
a. Evaluation Problem — Forward-backward Algorithm
一看到數學式，大概眼花了，所以在這邊要搭配圖來看，才不會錯亂。
forward 顧名思義，就是由前往後找路徑，直到第 t 秒，其實也不太難，看到上圖藍色經過的流程圖在這邊 forward 要計算的部分只有 αₜ(j)，意思就是在第 t 秒、第 j 個狀態，發生 oₜ 的所有可能路徑機率之加總值，所以只算第 t 秒和第 t 秒以前發生的可能路徑機率！
backward 用膝蓋想，就是由後往前算嘛，看看流程圖之綠色部分，βₜ(j)從第 t 秒開始，考慮由第 j 個狀態出發，直至第 T 秒結束的所有路徑機率之總和，由於不知道在 t 由 j 狀態出發的機率值，所以我們是從已知第 T 秒發生的機率值，往前回推至第 t 秒的路徑機率。
用圖示法來看，不嚴謹的說法是 forward 乘上 backward ，就恰巧是在觀察序列 O 時，發生第 t 秒，經過第 j 個狀態的所有可能路徑機率之總和。
疑？forward 往後算到底，不就是 backward 往前算到底的值嘛？恩，是的，所以要估算路徑機率，其實只要算一種就可以了。
何以利吾身？這樣算有什麼好處呢？時間複雜度大大的減少了呀！只剩下 O(N²T) 唷！時間就是金錢，顆顆….不過這個演算法既然有 forward 和 backward，算這兩個一定有原因呀！等等在底下會提到。
b. Decoding Problem — Viterbi Algorithm
看到這邊，應該都是會心一笑，其實和上個演算法差不多嘛！只是把 ∑ 變成 max 而已呀！是的，你沒有看錯就是這麼簡單，有別於上個演算法是要找出在第 t 秒，會經過第 j 個狀態的所有可能路徑機率總和，而這個演算法想表示的是，在第 t 秒，會經過第 j 個狀態之最大機率路徑。
c. Learning Problem — EM Algorithm
Learning Problem 翻譯一下，就是學習問題，學習要學什麼呢？用 part 2 的舉例說明一下吧！
過去一年來，我們以周為一個觀察序列單位，紀錄圓仔每天買飲料的習慣，因此我們想從圓仔的飲料習慣紀錄中，分析出「選擇買什麼東西」、「去哪間賣場購買的」，可惜的是，我們沒有紀錄到圓仔去哪間賣場買東西的誘因，亦即是「機率」，再換句話說，我們要尋找的訓練的目標是找到「狀態轉移矩陣 A」、「觀察轉移矩陣 B」、「起始值轉移矩陣 π」，而「圓仔的飲料習慣紀錄」是我們的訓練資料集。
了解問題之後，先來看一下離散問題的數學式，首先只考慮一周的飲料清單，透過 Forward-Backward Algorithm 我們可以求出 αₜ(i) 和 βₜ(i)，也就是把每一個時間點會經過每一個狀態及事件的所有可能路徑機率都算出來，求出來之後，自然就要開始訓練參數啦！
Training 囉！
在標題中看到 EM Algorithm，應該很快就聯想到了「分群」、「資料分布」，是的，我們這裡處理的手法其實也差不多啦！利用事件發生的平均機率，當作更新的轉移矩陣，接著反覆的尋找和更新，直到更新幅度很小這樣。
Comment：
- 沒有出現在資料集中的觀察值，在更新的過程中，會被更新為 0，一旦變成 0，此事件路徑發生的可能性即為 0，因此不論計算 Evaluate Problem 或是 Decording Problem 此路徑機率皆恆為 0，意思是不會再更新，所以通常不會讓沒出現過的觀察值機率為 0，常理來說，會預設一個比 0 大，但很小的數字。只有離散問題，會遇到此狀況，連續則無。
- 因為每次的 update，都只與當下計算的觀察序列有關，因此很容易看到第 n 個序列的時候，就忘掉一開始看到的幾個序列的樣子了，為了避免這樣的狀況產生，所以我們讓每次要更新的值，與將要被更新的值取一個比例平衡，既不忘了過去的觀察序列，也不會全然依照新的觀察序列更新，常用的方式如底下公式…
當然有些人會困惑， 之前我們討論的內容中，每個狀態都會有固定對應的 M 個觀察值，意思是，原先賣場飲料都是一罐一罐賣的，後來為了環保考量不用鋁罐裝，用一袋袋飲料裝？由於是一袋袋的，所以每一袋飲料的重量都有些許的誤差，長久下來，觀察值會由消費者買了架上第 k 種每瓶為 L ml 的飲料，變成是買了架上第 k 種每袋為 L ml 的飲料，因為不是每袋都能很準確的裝剛好 L ml 的飲料，所以會有一點點偏差— 「連續型隱藏式馬可夫模型 Continuous Hidden Markov Model」
d. (補充) Continuous Hidden Markov Model
上述的想法，大家思考一下，看到「bias 偏差」大家會想到啥？八九不離十，是令人腦昏的「統計」，統計數據會想到啥？「常態分佈 Normal Distribution」。沒錯，不管什麼狀態，未看先猜有「常態分佈」，先對一半。那什麼東西訓練中會與「常態分佈」有關，眼睛閉著，也猜得到「EM Algorithm」，接著聯想到的就是「Gaussian Distribution」、「Gaussian Mixture Model」。既然有這些聯想，那一切就好辦了。讓我們走下去….
於是乎我們訓練的目標中多了一個參數 — 在「狀態 sₜ」產生「觀察值 oₜ」的機率。目前我們以 Gaussian Mixture Model 為假設觀察值 oₜ 所屬分布，那馬上就會想到，多了的訓練參數是誰了吧!!!沒錯，就是「平均數 mean μ」和「變異數 covariance Σ」
有了這張圖，大概就清楚明瞭了吧！簡單敘述整個問題，就是….圓仔每天都會去買飲料，所以我們紀錄她每天買的飲料品項和飲料重量，然後每 7 天為一筆資料，目的是找出圓仔買東西的習慣和路徑，以及買到東西多寡的分析，所以影響的因素和對應的名詞有三個「賣場 →狀態」、「飲料 →觀察」、「飲料重量 →N( μ, Σ )」，目標是從這三者中計算出最可能是圓仔的習慣 — — 買東西的路徑機率、選擇買哪種飲料的機率、得到此飲料重量的機率。
一定會有人覺得緊張該怎麼辦，其實也不用怎麼辦啦!!!跟剛剛計算的方法差不多，只是多了要更新「平均值 μ」和「共變異數 Σ」而已
YA！我們終於結束 Hidden Markov Model 系列啦!!!給自己一個歡呼吧！其實一切都不難，不要看到數學是就害怕了啦啦啦~~~~
Reference:
(1)演算法筆記- Hidden Markov Model
(2)Hidden Markov Models — Stanford University
