Hidden_Markov_models

**隱藏式馬可夫模型**（Hidden Markov Model；縮寫：**HMM**）或稱作**隱性馬可夫模型**，是統計模型，它用來描述一個含有隱含未知參數的馬可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數。然後利用這些參數來作進一步的分析，例如圖型識別。

在**正常的**馬可夫模型中，狀態對於觀察者來說是直接可見的。這樣狀態的轉換機率便是全部的參數。而在隱藏式馬可夫模型中，狀態並不是直接可見的，但受狀態影響的某些變數則是可見的。每一個狀態在可能輸出的符號上都有一機率分布。因此輸出符號的序列能夠透露出狀態序列的一些資訊。

## 馬可夫模型的演化

下邊的圖示強調了 HMM 的狀態變遷。有時，明確的表示出模型的演化也是有用的，我們用 _x_(_t_1) 與 _x_(_t_2) 來表達不同時刻 _t_1 和 _t_2 的狀態。

圖中箭頭方向則表示不同資訊間的關聯性，因此可以得知 $x(t)$ 和 $x(t-1)$ 有關，而 $x(t-1)$ 又和 $x(t-2)$ 有關。

而每個 $y(t)$ 只和 $x(t)$ 有關，其中 $x(t)$ 我們稱為隱藏變數（hidden variable），是觀察者無法得知的變數。

隱性馬可夫模型常被用來解決有未知條件的數學問題。

假設隱藏狀態的值對應到的空間有 $N$ 個元素，也就是說在時間 $t$ 時，隱藏狀態會有 $N$ 種可能。

同樣的， $t+1$ 也會有 $N$ 種可能的值，所以從 $t$ 到 $t+1$ 間的關係會有 $N^{2}$ 種可能。

除了 $x(t)$ 間的關係外，每組 $x(t),y(t)$ 間也有對應的關係。

若觀察到的 $y(t)$ 有 $M$ 種可能的值，則從 $x(t)$ 到 $y(t)$ 的輸出模型複雜度為 $O(NM)$ 。如果 $y(t)$ 是一個 $M$ 維的向量，則從 $x(t)$ 到 $y(t)$ 的輸出模型複雜度為 $O(NM^{2})$ 。

在這個圖中，每一個時間塊（_x_(_t_), _y_(_t_)）都可以向前或向後延伸。通常，時間的起點被設定為 _t_=0 或 _t_=1.

## 馬可夫模型的機率

假設觀察到的結果為 $Y$

$$
Y=y(0),y(1),...,y(L-1)
$$

隱藏條件為 $X$

$$
X=x(0),x(1),...,x(L-1)
$$

長度為 $L$ ，則馬可夫模型的機率可以表達為：

$$
P(Y)=\sum _{X}P(Y\mid X)P(X)\,
$$

由這個機率模型來看，可以得知馬可夫模型將該時間點前後的資訊都納入考量。

## 使用隱藏式馬可夫模型

HMM 有三個典型 (canonical) 問題:

* 預測 (filter)：已知模型參數和某一特定輸出序列，求最後時刻各個隱含狀態的機率分布，即求 $P(x(t)\ |\ y(1),\dots ,y(t))$ 。通常使用前向演算法解決。
* 平滑 (smoothing)：已知模型參數和某一特定輸出序列，求中間時刻各個隱含狀態的機率分布，即求 $P(x(k)\ |\ y(1),\dots ,y(t)),k<t$ 。通常使用前向 - 後向演算法解決。
* 解碼 (most likely explanation)：已知模型參數，尋找最可能的能產生某一特定輸出序列的隱含狀態的序列，即求 $P([x(1)\dots x(t)]|[y(1)\dots ,y(t)])$ 。通常使用 Viterbi 演算法解決。

此外，已知輸出序列，尋找最可能的狀態轉移以及輸出機率。通常使用 Baum-Welch 演算法以及 Viterbi algorithm 解決。另外，最近的一些方法使用聯結樹演算法來解決這三個問題。

### 具體實例

假設你有一個住得很遠的朋友，他每天跟你打電話告訴你他那天做了什麼。你的朋友僅僅對三種活動感興趣：公園散步，購物以及清理房間。他選擇做什麼事情只憑天氣。你對於他所住的地方的天氣情況並不了解，但是你知道總的趨勢。在他告訴你每天所做的事情基礎上，你想要猜測他所在地的天氣情況。

你認為天氣的執行就像一個馬可夫鏈。其有兩個狀態「雨」和「晴」，但是你無法直接觀察它們，也就是說，它們對於你是隱藏的。每天，你的朋友有一定的機率進行下列活動：「散步」、「購物」、「清理」。因為你朋友告訴你他的活動，所以這些活動就是你的觀察資料。這整個系統就是一個隱藏式馬可夫模型（HMM）。

你知道這個地區的總的天氣趨勢，並且平時知道你朋友會做的事情。也就是說這個隱藏式馬可夫模型的參數是已知的。你可以用程式語言（Python）寫下來：

在這些代碼中，`start_probability` 代表了你對於你朋友第一次給你打電話時的天氣情況的不確定性（你知道的只是那個地方平均起來下雨多些）。在這裡，這個特定的機率分布並非平衡的，平衡機率應該接近（在給定變遷機率的情況下）`{'Rainy': 0.571, 'Sunny': 0.429}`。
`transition_probability` 表示基於馬可夫鏈模型的天氣變遷，在這個例子中，如果今天下雨，那麼明天天晴的機率只有 30%。代碼 `emission_probability` 表示了你朋友每天做某件事的機率。如果下雨，有 50% 的機率他在清理房間；如果天晴，則有 60% 的機率他在外頭散步。

這個例子在維特比演算法頁上有更多的解釋。

### 隱藏式馬可夫模型的應用

* 語音辨識、中文斷詞 / 分詞或光學字元辨識
* 機器翻譯
* 生物資訊學 和 基因組學
  * 基因組序列中蛋白質編碼區域的預測
  * 對於相互關聯的 DNA 或蛋白質族的建模
  * 從基本結構中預測第二結構元素
  * 通信中的解碼過程
  * 地圖匹配演算法
* _還有更多..._

### 隱藏式馬可夫模型在語音處理上的應用

因為馬可夫模型有下列特色：

* 時間點 $t$ 的隱藏條件和時間點 $t-1$ 的隱藏條件有關。因為人類語音擁有前後的關聯，可以從語義與發音兩點來看：

　
: 1. 單字的發音擁有前後關聯：例如 "They are" 常常發音成 "They're"，或是 "Did you" 會因為 "you" 的發音受 "did" 的影響，常常發音成 "did ju"，而且語音辨識中用句子的發音來進行分析，因此需要考慮到每個音節的前後關係，才能夠有較高的準確率。
2. 句子中的單字有前後關係：從英文文法來看，主詞後面常常接助動詞或是動詞，動詞後面接的會是受詞或介係詞。而或是從單一單字的使用方法來看，對應的動詞會有固定使用的介係詞或對應名詞。因此分析語音訊息時需要為了提升每個單字的準確率，也需要分析前後的單字。

* 馬可夫模型將輸入訊息視為一單位一單位，接著進行分析，與人類語音模型的特性相似。語音系統辨識的單位為一個單位時間內的聲音。利用梅爾倒頻譜等語音處理方法，轉換成一個發音單位，為離散型的資訊。而馬可夫模型使用的隱藏條件也是一個個被封包的 $x(t)$ ，因此使用馬可夫模型來處理聲音訊號比較合適。

## 歷史

隱藏式馬可夫模型最初是在 20 世紀 60 年代後半期 Leonard E. Baum 和其它一些作者在一系列的統計學論文中描述的。HMM 最初的應用之一是開始於 20 世紀 70 年代中期的語音辨識。

在 1980 年代後半期，HMM 開始應用到生物序列尤其是 DNA 的分析中。此後，在生物資訊學領域 HMM 逐漸成為一項不可或缺的技術。

## 參見

* 安德雷・馬可夫
* 貝氏推論
* 估計理論
* 條件隨機域
* 排隊理論
* 馬可夫決策過程

## 註解

## 參考書目

## 外部連結