跳至內容

前向式演算法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

前向算法Forward algorithm),在隱馬爾可夫模型(HMM)中,是用於計算「置信狀態」的。置信狀態指根據既往證據推算出的當前狀態的概率分布。這個過程也被叫做「濾波」。前向算法和維特比算法緊密相關但又互不相同。

發展歷史

[編輯]

前向算法是用來解決解碼問題的算法之一。自從語音識別技術[1]和模式識別技術發展以來,它也越來越普遍地被用在像計算生物學[2]這樣的使用HMM的領域內。

算法

[編輯]

整個算法的目標是計算聯合概率分布 。為了方便,我們把 簡寫做 ,將 簡寫做 。直接計算則需要計算所有狀態序列 邊緣分布,而它的數量和 成指數相關。使用這一算法,我們可以利用HMM的條件獨立性質,遞歸地進行計算。

我們令

.

利用鏈式法則來展開,我們可以得到

.

由於 和除了 之外的一切都條件獨立,而 又和 之外的一切都條件獨立,因此

.

這樣,由於 由HMM的輸出概率狀態轉移概率我們可以很快計算用 計算出,並且可以避免遞歸計算。

前向算法可以很容易地被修改來適應其他的HMM變種,比如馬爾可夫跳躍線性系統

平滑處理

[編輯]

為了能夠使用「未來的歷史」(比如我們在試圖預測過去的某個時點的狀態),我們可以運行後向算法,它是前向算法的一個補充。這一操作被稱為平滑[為何?]前向-後向算法 計算 ,因此使用了過去和未來的全部信息。

解碼算法

[編輯]

為了解碼最可能的序列,需要使用維特比算法。它會從過去的觀測中試圖推測最可能的狀態序列,也即使 最大化的狀態序列。

參考文獻

[編輯]
  1. ^ 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. 10.1109/5.18626
  2. ^ 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.