###### tags: `ML數學分部`
# Markov Chain & HMM (隱藏馬可夫模型)

Markov Chain 常被用來描述一連串相關事件中，兩個狀態(事件)之間的轉換
而 HMM 隱藏馬可夫模型就是其延伸

## 1. Markov Chain

### - 定義
Markov Chain 是一連串的事件串接而成，在相關的事件當中會有其轉換的機率值
也就是狀態轉換的機率

# 以下所說的 [事件] 與 [狀態] 皆相同

:::warning
- **Example**
圖中為兩事件 [E]、[A] 的馬可夫鏈
- 當前事件 = E : 有 0.3 機率下一事件會轉移到相同事件，0.7 機率會轉移到事件 [A]
- 當前事件 = A : 0.6 會轉移到 [A]，0.4 轉移到 [E]

:::

<br>

### - 轉移矩陣

事件和事件的轉移機率可以寫成以下形式
也就是事件 $x_{i-1}$ 轉移到事件 $x_i$ 的機率

$$P(x_i|x_{i-1})$$

我們還可以將機率寫成一個轉移的矩陣
舉例上圖說明

:::warning
- **轉移矩陣**

利用此矩陣，即可在不同狀態之間轉移

| | A 事件 | E 事件 |
| -------- | -------- | -------- |
| A 事件 | 0.6 | 0.4 |
| E 事件 | 0.7 | 0.3 |

=

$\begin{bmatrix}
0.6 & 0.4 \\
0.7 & 0.3
\end{bmatrix}$

:::

<br>

## 2. HMM

### - 定義

HMM ( Hidden Markov Model )，是馬可夫鏈的延伸，
馬可夫鏈可以直接觀察到事件之間的關聯，HMM 則會將關聯事件[隱藏起來]

- **Ex** : 天氣與天氣之間有 Markov Chain 關係，John 的心情會根據天氣的不同而轉變
HMM 就是我們只觀察的到 John 的心情，而要去推估當前的天氣


X : 為隱藏的 Markov Chain
Y : 為可以觀察到的資訊，稱為 Observe Variable

<br>

### - 數學解釋

我們的目的就是利用 $Y$ 去找到最有可能的 $X$ ( $Y$、$X$ 皆是序列資料 )
=> 如果 $X$ 對應 $Y$ 的機率為 $P(X|Y)$
=> 就是要找出一個 $X$ 可以 maximize $P(X|Y)$

$$argmax(\ P(X=x_1,x_2...x_N|Y=y_1,y_2...y_N)\ )=argmax(\ P(X|Y)\ )$$

化簡後變為

$$argmax(\ \prod^N_i{P(y_i|x_i)}P(x_i|x_{i-1})\ )$$

這個就是可以由 $Y$ 預測出 $X$ 的目標函數

:::info
- 推導過程

=> $argmax(\ P(X=x_1,x_2...x_N|Y=y_1,y_2...y_N)\ )$

以上公式用貝氏定理化簡後變為

=> $argmax(\frac{P(Y|X)P(X)}{P(Y)})$

因為定值所以省略 P(Y)
並展開 $P(Y|X)$ 和 $P(X)$

=> $argmax({P(Y|X)P(X)})$

> $P(Y|X)=P(y_1|x_1)P(y2|x2)...P(y_N|x_N)=\prod{P(y_i|x_i)}$
> $P(X)=\prod{P(x_i|x_{i-1})}$

=> $argmax(\ \prod{P(y_i|x_i)}P(x_i|x_{i-1})\ )$
:::

<br>

## Reference

- [Hidden Markov Model](https://web.ntnu.edu.tw/~algo/HiddenMarkovModel.html#3)
- [Hidden Markov Model Clearly Explained! Part - 5](https://www.youtube.com/watch?v=RWkHJnFj5rY)