隱馬爾可夫模型

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

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

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

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

定義

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

• ${\displaystyle X_{n}}$是馬爾可夫過程，其行為不可直接觀測（「隱」）；
• ${\displaystyle \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 )},}$

${\displaystyle \forall n\geq 1,\ x_{1},\ldots ,x_{n},}$，且對每個博雷爾集${\displaystyle A}$。

令${\displaystyle X_{t}}$、${\displaystyle Y_{t}}$為連續時間隨機過程。則${\displaystyle (X_{t},Y_{t})}$是隱馬爾可夫模型的條件是：

• ${\displaystyle X_{t}}$是馬爾可夫過程，其行為不可直接觀測（「隱」）；
• ${\displaystyle \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}})}$,

${\displaystyle \forall t_{0}}$、每個博雷爾集${\displaystyle A,}$且每族博雷爾集${\displaystyle \{B_{t}\}_{t\leq t_{0}}.}$

術語

過程狀態${\displaystyle X_{n}}$（或${\displaystyle X_{t}}$）稱作隱狀態，${\displaystyle \operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\mid X_{n}=x_{n}{\bigr )}}$（或${\displaystyle \operatorname {\mathbf {P} } {\bigl (}Y_{t}\in A\mid X_{t}\in B_{t}{\bigr )}}$）稱作條件概率或輸出概率。

馬爾可夫模型的演化

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

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

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

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

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

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

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

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

Temporal evolution of a hidden Markov model

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

馬爾可夫模型的機率

假設觀察到的結果為${\displaystyle Y}$

${\displaystyle Y=y(0),y(1),...,y(L-1)}$

隱藏條件為${\displaystyle X}$

${\displaystyle X=x(0),x(1),...,x(L-1)}$

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

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

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

使用隱馬爾可夫模型

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

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

此外，已知輸出序列，尋找最可能的狀態轉移以及輸出概率.通常使用Baum-Welch算法以及Viterbi algorithm（英語：Viterbi algorithm）解決。另外,最近的一些方法使用聯結樹算法（英語：Junction tree 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的一般結構。橢圓形代表隨機變量，可採用多個數值中的任意一種。隨機變量${\displaystyle x(t)}$是t時刻的隱狀態（圖示模型中${\displaystyle x(t)\in \{x_{1},\ x_{2},\ x_{3}\}}$）；隨機變量y(t)是t時刻的觀測值（${\displaystyle y(t)\in \{x_{1},\ x_{2},\ x_{3},\ y_{4}\}}$）；箭頭表示條件依賴關係。

隱馬爾可夫模型的時間演化

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

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

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

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

學習

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

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

隱馬爾可夫模型的應用

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

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

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

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

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

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

歷史

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

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

參見

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

註解

1. Google Scholar. [2023-10-27]. （原始內容存檔於2022-09-30）.
2. Thad Starner, Alex Pentland. Real-Time American Sign Language Visual Recognition From Video Using Hidden Markov Models （頁面存檔備份，存於網際網路檔案館）. Master's Thesis, MIT, Feb 1995, Program in Media Arts
3. B. Pardo and W. Birmingham. Modeling Form for On-line Following of Musical Performances 網際網路檔案館的存檔，存檔日期2012-02-06.. AAAI-05 Proc., July 2005.
4. Satish L, Gururaj BI (April 2003). "Use of hidden Markov models for partial discharge pattern classification （頁面存檔備份，存於網際網路檔案館）". IEEE Transactions on Dielectrics and Electrical Insulation.
5. Li, N; Stephens, M. Modeling linkage disequilibrium and identifying recombination hotspots using single-nucleotide polymorphism data.. Genetics. December 2003, 165 (4): 2213–33. PMC 1462870 . PMID 14704198. doi:10.1093/genetics/165.4.2213.
6. Ernst, Jason; Kellis, Manolis. ChromHMM: automating chromatin-state discovery and characterization. Nature Methods. March 2012, 9 (3): 215–216. PMC 3577932 . PMID 22373907. doi:10.1038/nmeth.1906.
7. Sipos, I. Róbert. Parallel stratified MCMC sampling of AR-HMMs for stochastic time series prediction. In: Proceedings, 4th Stochastic Modeling Techniques and Data Analysis International Conference with Demographics Workshop (SMTDA2016), pp. 295-306. Valletta, 2016. PDF
8. Chatzis, Sotirios P.; Kosmopoulos, Dimitrios I. A variational Bayesian methodology for hidden Markov models utilizing Student's-t mixtures (PDF). Pattern Recognition. 2011, 44 (2): 295–306 [2018-03-11]. Bibcode:2011PatRe..44..295C. CiteSeerX 10.1.1.629.6275 . doi:10.1016/j.patcog.2010.09.001. （原始內容 (PDF)存檔於2011-04-01）.
9. Rabiner, p. 258
10. Durbin

參考書目

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