隱馬爾可夫模型

<image>

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

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

隱馬爾可夫模型在熱力學、統計力學、物理學、化學、經濟學、金融學、信號處理、資訊理論、模式識別（如語音識別、手寫識別、手勢識別、詞性標記、樂譜跟隨）、局部放電及生物資訊學等領域都有應用。

## 定義

令$X_n$、$Y_n$為離散時間隨機過程， $n\geq 1$。則$(X_n,Y_n)$是隱馬爾可夫模型的條件是：

- $X_n$是馬爾可夫過程，其行為不可直接觀測（「隱」）。
- $$\operatorname{\mathbf{P}}\bigl(Y_n \in A\ \bigl|\ X_1=x_1,\ldots,X_n=x_n\bigr)=\operatorname{\mathbf{P}}\bigl(Y_n \in A\ \bigl|\ X_n=x_n\bigr),$$

$\forall n\geq 1,\ x_1,\ldots, x_n,$，且對每個博雷爾集$A$。

令$X_t$、$Y_t$為連續時間隨機過程。則$(X_t,Y_t)$是隱馬爾可夫模型的條件是：

- $X_t$是馬爾可夫過程，其行為不可直接觀測（「隱」）。
- $\operatorname{\mathbf{P}}(Y_{t_0} \in A \mid \{X_t \in B_t\}_{ t\leq t_0}) = \operatorname{\mathbf{P}}(Y_{t_0} \in A \mid X_{t_0} \in B_{t_0})$,

$\forall t_0$、每個博雷爾集$A,$且每族博雷爾集$\{B_t\}_{t \leq t_0}.$

### 術語

過程狀態$X_n$（或$X_t$）稱作隱狀態，$\operatorname{\mathbf{P}}\bigl(Y_n \in A \mid X_n=x_n\bigr)$（或$\operatorname{\mathbf{P}}\bigl(Y_t \in A \mid X_t \in B_t\bigr)$）稱作條件概率或輸出機率。

## 馬爾可夫模型的演化

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

圖中箭頭方向則表示不同資訊間的關聯性，因此可以得知$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)$。

<image>

在這個圖中,每一個時間塊（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演算法解決。

### 具體實例

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

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

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

```python
 states = ('Rainy', 'Sunny')
 
 observations = ('walk', 'shop', 'clean')
 
 start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
 transition_probability = {
    'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
    'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
    }
 
 emission_probability = {
    'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
    'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
    }
```

在這些代碼中,`start_probability`代表了你對於你朋友第一次給你打電話時的天氣情況的不確定性（你知道的只是那個地方平均起來下雨多些）。在這裡，這個特定的機率分布並非平衡的，平衡機率應該接近（在給定變遷機率的情況下）`{'Rainy': 0.571, 'Sunny': 0.429}`。

`transition_probability` 表示基於馬爾可夫鏈模型的天氣變遷，在這個例子中，如果今天下雨，那麼明天天晴的機率只有30%。代碼`emission_probability` 表示了你朋友每天做某件事的機率。如果下雨，有50% 的機率他在清理房間；如果天晴，則有60%的機率他在外頭散步。

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

## 結構架構

下圖展示了實例化HMM的一般結構。橢圓形代表隨機變量，可採用多個數值中的任意一種。隨機變量$x(t)$是t時刻的隱狀態（圖示模型中$x(t)\in\{x_1,\ x_2,\ x_3\}$）；隨機變量y(t)是t時刻的觀測值（$y(t)\in\{x_1,\ x_2,\ x_3,\ y_4\}$）；箭頭表示條件依賴關係。

<image>

圖中可清楚看出，給定隱變量$x(t)$在時間t的條件概率分布只取決於隱變量$x(t-1)$的值，之前的則沒有影響，這就是所謂馬爾可夫性質。觀測變量$y(t)$同理，只取決於隱變量$x(t)$的值。

在本文所述標準HMM中，隱變量的狀態空間是離散的，而觀測值本身則可以離散（一般來自分類分布）也可以連續（一般來自正態分布）。HMM參數有兩類：轉移機率與輸出機率，前者控制$t-1$時刻的隱狀態下，如何選擇t時刻的隱狀態。

隱狀態空間一般假設包含N個可能值，以分類分布為模型。這意味著，對隱變量在t時刻可能所處的N種狀態中的每種，都有到$t+1$時刻可能的N種狀態的轉移機率，共有$N^2$個轉移機率。注意從任意給定狀態轉移的轉移機率之和須為1。於是，轉移機率構成了N階方陣，稱作馬爾可夫矩陣。由於任何轉移機率都可在已知其他機率的情形下確定，因此共有$N(N-1)$個轉移參數。

此外，對N種可能狀態中的每種，都有一組輸出機率，在給定隱狀態下控制著觀測變量的分布。這組機率的大小取決於觀測變量的性質，例如，若觀測變量是離散的，有M種值、遵循分類分布，則有$M-1$個獨立參數，所有隱狀態下共有$N(M-1)$個輸出機率參數。若觀測向量是M維向量，遵循任意多元正態分布，則將有M個參數控制均值，$\frac {M(M+1)} 2$個參數控制協方差矩陣，共有$N \left(M + \frac{M(M+1)}{2}\right) = \frac {NM(M+3)} 2 = O(NM^2)$個輸出參數。（這時，除非M很小，否則限制觀測向量各元素間協方差的性質可能更有用，例如假設各元素相互獨立，或假設除固定多相鄰元素外，其他元素相互獨立。）

## 學習

HMM的參數學習任務是指在給定輸出序列或一組序列的情形下，找到一組最佳的狀態轉換和轉移機率。任務通常是根據一組輸出序列，得到HMM參數的最大似然估計值。目前還沒有精確解這問題的可行演算法，可用鮑姆-韋爾奇演算法或Baldi–Chauvin演算法高效地推導出局部最大似然。鮑姆-韋爾奇演算法是最大期望算法的特例。

若將HMM用於時間序列預測，則更複雜的貝葉斯推理方法（如馬爾可夫鏈蒙特卡洛採樣法，MCMC採樣法）已被證明在準確性和穩定性上都優於尋找單一的最大似然模型。由於MCMC帶來了巨大的計算負擔，在計算可擴展性也很重要時，也可採用貝葉斯推理的變分近似方法，如。事實上，近似變分推理的計算效率可與期望最大化相比，而精確度僅略遜於精確的MCMC型貝葉斯推理。

## 隱馬爾可夫模型的應用

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

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

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

- 時間點$t$的隱藏條件和時間點$t-1$的隱藏條件有關。因為人類語音擁有前後的關聯，可以從語義與發音兩點來看：
- 單字的發音擁有前後關聯：例如"They are"常常發音成"They're"，或是"Did you"會因為"you"的發音受"did"的影響，常常發音成"did ju"，而且語音辨識中用句子的發音來進行分析，因此需要考慮到每個音節的前後關係，才能夠有較高的準確率。
- 句子中的單字有前後關係：從英文文法來看，主詞後面常常接助動詞或是動詞，動詞後面接的會是受詞或介係詞。而或是從單一單字的使用方法來看，對應的動詞會有固定使用的介係詞或對應名詞。因此分析語音訊息時需要為了提升每個單字的準確率，也需要分析前後的單字。
- 馬可夫模型將輸入訊息視為一單位一單位，接著進行分析，與人類語音模型的特性相似。語音系統辨識的單位為一個單位時間內的聲音。利用梅爾倒頻譜等語音處理方法，轉換成一個發音單位，為離散型的資訊。而馬可夫模型使用的隱藏條件也是一個個被封包的$x(t)$，因此使用馬可夫模型來處理聲音訊號比較合適。

## 歷史

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

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

## 外部連結

- Hidden Markov Model (HMM) Toolbox for Matlab (by Kevin Murphy)
- Hidden Markov Model Toolkit (HTK) (a portable toolkit for building and manipulating hidden Markov models)
- Hidden Markov Models (an exposition using basic mathematics)
- GHMM Library (home page of the GHMM Library project)
- Jahmm Java Library (Java library and associated graphical application)
- A step-by-step tutorial on HMMs (University of Leeds)
- Software for Markov Models and Processes (TreeAge Software)