HMM是利用觀測值來推斷狀態的一個算法，而狀態被稱為隱藏狀態(hidden state)是因為我們看不到狀態，只能看到觀測值，所以實際上我們對狀態是不了解的，例如：我們可以觀察到身體狀態是正常、咳嗽、暈眩，從而透過HMM推斷背後的狀態為健康還是生病。

HMM可以被用在許多應用上，例如語音識別，我們觀察得到聲波，但該聲波對應到的文字我們是不知道的，可以透過HMM從聲波推回狀態來得到可能的文字，除此之外，在許多序列型任務都有HMM的應用

我們雖然對隱藏狀態(hidden state)不了解，但我們知道狀態之間的轉移機率(transition probability)還有狀態對應到觀測值的發射機率(emission probability)，從這兩者搭配觀測序列

HMM 三大問題

---

根據此網站定義，我們定義HMM參數為$ \lambda $，包含初始機率 $\pi$ (Initial Probability)、轉移機率 $A$ (Transition Probability)、發射機率 $B$ (Emission Probability)，定義 $ \lambda = \left ( \pi , A, B \right )$

1. The Evaluation Problem: 根據觀察序列$O$及模型參數$\lambda$，得出此序列的機率$P(O \mid \lambda)$
2. The Decoding Problem: 根據觀察序列$O$及模型參數$\lambda$，得出最有可能的隱藏狀態序列(hidden state sequence)
3. The Learning Problem: 根據觀察序列$O$，調整模型參數$\lambda = \left [ A, B, \pi \right ]$ 使得 $P(O \mid \lambda)$ 最大化

另外，維基百科有寫出另外兩個經典問題

• 預測(filter): 根據觀察序列$O$及模型參數$\lambda$，求最後一時刻，各隱藏狀態的機率分布
• 平滑(smoothing): 根據觀察序列$O$及模型參數$\lambda$，求中間某一時刻，各隱藏狀態的機率分布

對於這些任務，很多地方的定義或使用的名詞都各有不同，我們先在這邊定義好，並且了解各個任務在做的事情，每個任務都會有對應的算法

推導 - Evaluation Problem

---

首先，讓我們回顧一下什麼是Markov Assumption

\[P(q_{t} \mid q_{t-1}, q_{t-2}, ...) = P(q_{t} \mid q_{t-1})\]

也就是假設我們現在的狀態$q_{t}$只依賴於前一個狀態$q_{t-1}$，$P(q_{t} \mid q_{t-1})$

在這樣的假設下，HMM擁有兩個機率，分別為轉移機率與發射機率，以矩陣的形式表示

1. 轉移矩陣(transition matrix)$ A_{k \times k}$
2. 發射矩陣(emission matrix)$ B_{k \times L}$

我們用三個參數來表示一個HMM Model，$A代表的是狀態之間的轉移矩陣，B代表的是狀態到觀測值的發射矩陣$，而$\pi$是我們的起始狀態

\[\Lambda = \{ A, B, \pi \}\]

假設我們現在有三個觀測值，我們想求這樣的觀測值出現的機率為多少

\[P(y_{1}, y_{2}, y_{3}) = \sum_{q_{1}=1}^{k} \sum_{q_{2}=1}^{k} \sum_{q_{3}=1}^{k} P(y_{1}, y_{2}, y_{3}, q_{1}, q_{2}, q_{3}) \\ = \sum_{q_{1}=1}^{k} \sum_{q_{2}=1}^{k} \sum_{q_{3}=1}^{k} P(y_{3} \mid q_{3}) P(q_{3} \mid q_{2}) P(y_{2} \mid q_{2}) P(q_{2} \mid q_{1}) P(y_{1} \mid q_{1}) P(q_{1})\]

在上面的式子中，我們第一步先將狀態$q$加進去，之後利用Bayes' rules的條件機率定義展開，並且藉由Markov Assumption將前面狀態及前面觀測值消除(狀態只跟前一個狀態有關，觀測也只跟現在這個狀態有關)，不過，這樣的結果還是非常難計算，我們需要做那麼多次的sum，假設我們現在觀測值不只三個的話，我們有$T$個觀測值

那我們總共需要做$T$的$sum$，每次做$k$次，所以總共有$k^{T}$的計算量，而且在現實應用中，$k$和$T$都是很大的值，因此，我們可以利用程式設計中的DP觀念來解決這個問題，我們稱之為Forward Algorithm, Backward Algorithm

首先，先定義兩個變數$\alpha , \beta$

\[\alpha_{i}(t) = P(y_{1}, ..., y_{t}, q_{t} = i \mid \lambda)\] \[\beta_{i}(t) = P(y_{t+1}, ..., y_{T}, q_{t} = i \mid \lambda)\]

稍微解釋一下，$\alpha$即狀態t跟觀測值1到t的joint probability，$\beta$則是狀態t跟觀測值t+1到T的joint probability

我們接下來從$\alpha_{i}(1)$開始推導，看能不能找出什麼規律

\[\alpha_{i}(1) = P(y_{1}, q_{1} = i \mid \lambda) = P(y_{1} \mid q_{1} = i) \times P(q_{1})\] \[\alpha_{j}(2) = P(y_{1}, y_{2}, q_{2} = j \mid \lambda) = \sum_{i=1}^{k} P(y_{1}, y_{2}, q_{1}=i, q_{2}=j) = P(y_{2} \mid q_{2} = j) \sum_{i=1}^{k} P(q_{2}=j \mid q_{1}=i) \times \alpha_{i}(1)\]

從此我們可以發現，可以找出規律寫出以下式子

\[\alpha_{i}(T) = P(y_{1}, .., y_{T}, q_{T} = i) = P(y_{T} \mid q_{T} = i) \sum_{i=1}^{k} P(q_{T}=j \mid q_{T-1} = i) \times \alpha_{i}(T-1) = b_{i}(T) \sum_{i=1}^{k} a_{i, j} \alpha_{i}(T-1)\]

Reference

---

1. 漫談HMM
2. 演算法筆記
3. 維基百科：HMM, Expectation-Maximization Algorithm, Baum–Welch algorithm
4. Youtube上講解HMM影片，UBC大學的影片
5. LDA數學八卦，關於馬可夫鏈的章節
6. 徐亦達機器學習課程