跳至內容

前向式演算法

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

前向式演算法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.