隱藏式馬可夫模型

隱藏式馬可夫模型狀態變遷圖（例子）
x — 隱含狀態
y — 可觀察的輸出
a — 轉換概率（transition probabilities）
b — 輸出概率（output probabilities）

隱藏式馬可夫模型（英語：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(t₁) 與 x(t₂) 來表達不同時刻 t₁ 和 t₂ 的狀態。

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

Temporal evolution of a hidden Markov model

在這個圖中,每一個時間塊（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）寫下來：

 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}\}$）；箭頭表示條件依賴關係。

隱藏式馬可夫模型的時間演化

圖中可清楚看出，給定隱變數$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$的隱藏條件有關。因為人類語音擁有前後的關聯，可以從語義與發音兩點來看：

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逐漸成為一項不可或缺的技術。

參見

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

參考書目

• Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.
• Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1999. ISBN 0521629713.
• Kristie Seymore, Andrew McCallum, and Roni Rosenfeld. Learning Hidden Markov Model Structure for Information Extraction. AAAI 99 Workshop on Machine Learning for Information Extraction, 1999. (also at CiteSeer: [1] （頁面存檔備份，存於互聯網檔案館）)
• http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html （頁面存檔備份，存於互聯網檔案館）
• J. Li （頁面存檔備份，存於互聯網檔案館）, A. Najmi, R. M. Gray, Image classification by a two dimensional hidden Markov model, IEEE Transactions on Signal Processing, 48(2):517-33, February 2000.
• 隱藏式馬可夫模型(課件), 徐從富,浙江大學人工智能研究所 [2]

外部連結

• 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)