隱藏式馬可夫模型

马尔可夫统计模型

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

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

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

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

定義

  為離散時間隨機過程 。則 是隱藏式馬可夫模型的條件是:

  •  馬可夫過程,其行為不可直接觀測(「隱」);
  •  
 ,且對每個鮑萊耳集 

  為連續時間隨機過程。則 是隱藏式馬可夫模型的條件是:

  •  是馬可夫過程,其行為不可直接觀測(「隱」);
  •  ,
 、每個鮑萊耳集 且每族鮑萊耳集 

術語

過程狀態 (或 )稱作隱狀態, (或 )稱作條件機率或輸出機率。

馬可夫模型的演化

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

圖中箭頭方向則表示不同資訊間的關聯性,因此可以得知  有關,而 又和 有關。

而每個 只和 有關,其中 我們稱為隱藏變數(hidden variable),是觀察者無法得知的變數。

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

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

同樣的, 也會有 種可能的值,所以從  間的關係會有 種可能。

除了 間的關係外,每組 間也有對應的關係。

若觀察到的  種可能的值,則從  的輸出模型複雜度為 。如果 是一個 維的向量,則從  的輸出模型複雜度為 

 
Temporal evolution of a hidden Markov model

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

馬可夫模型的機率

假設觀察到的結果為 

 

隱藏條件為 

 

長度為 ,則馬可夫模型的機率可以表達為:

 

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

使用隱藏式馬可夫模型

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

  • 預測(filter):已知模型參數和某一特定輸出序列,求最後時刻各個隱含狀態的機率分布,即求  。通常使用前向演算法解決。
  • 平滑(smoothing):已知模型參數和某一特定輸出序列,求中間時刻各個隱含狀態的機率分布,即求  。通常使用前向-後向演算法解決。
  • 解碼(most likely explanation):已知模型參數,尋找最可能的能產生某一特定輸出序列的隱含狀態的序列,即求  。通常使用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的一般結構。橢圓形代表隨機變數,可採用多個數值中的任意一種。隨機變數 t時刻的隱狀態(圖示模型中 );隨機變數y(t)是t時刻的觀測值( );箭頭表示條件依賴關係。

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

圖中可清楚看出,給定隱變數 在時間t條件機率分布只取決於隱變數 的值,之前的則沒有影響,這就是所謂馬可夫性質。觀測變數 同理,只取決於隱變數 的值。

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

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

此外,對N種可能狀態中的每種,都有一組輸出機率,在給定隱狀態下控制著觀測變數的分布。這組機率的大小取決於觀測變數的性質,例如,若觀測變數是離散的,有M種值、遵循分類分布,則有 個獨立參數,所有隱狀態下共有 個輸出機率參數。若觀測向量是M維向量,遵循任意多元常態分布,則將有M個參數控制均值 個參數控制共變異數矩陣,共有 個輸出參數。(這時,除非M很小,否則限制觀測向量各元素間共變異數的性質可能更有用,例如假設各元素相互獨立,或假設除固定多相鄰元素外,其他元素相互獨立。)

學習

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

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

隱藏式馬可夫模型的應用

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

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

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

歷史

隱藏式馬可夫模型最初是在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

參考書目

外部連結