此條目需要
精通或熟悉相關主題的編者 參與及協助編輯。
(2018年11月18日 ) 請邀請 適合的人士改善本條目 。更多的細節與詳情請參見討論頁 。
前向式演算法 （Forward algorithm ），在隱藏式馬可夫模型 （HMM）中，是用於計算「置信狀態」的。置信狀態指根據既往證據推算出的當前狀態的機率分布。這個過程也被叫做「濾波」。前向式演算法和維特比演算法 緊密相關但又互不相同。
前向式演算法是用來解決解碼問題的演算法之一。自從語音辨識技術[ 1] 計算生物學 [ 2]
整個演算法的目標是計算聯合機率分布
p
(
x
t
,
y
1
:
t
)
{\displaystyle p(x_{t},y_{1:t})}
x
(
t
)
{\displaystyle x(t)}
x
t
{\displaystyle x_{t}}
(
y
(
1
)
,
y
(
2
)
,
.
.
.
,
y
(
t
)
)
{\displaystyle (y(1),y(2),...,y(t))}
y
1
:
t
{\displaystyle y_{1:t}}
p
(
x
t
,
y
1
:
t
)
{\displaystyle p(x_{t},y_{1:t})}
{
x
1
:
t
−
1
}
{\displaystyle \{x_{1:t-1}\}}
邊際分布 ，而它的數量和
t
{\displaystyle t}
條件獨立 性質，遞迴 地進行計算。
我們令
α
t
(
x
t
)
=
p
(
x
t
,
y
1
:
t
)
=
∑
x
t
−
1
p
(
x
t
,
x
t
−
1
,
y
1
:
t
)
{\displaystyle \alpha _{t}(x_{t})=p(x_{t},y_{1:t})=\sum _{x_{t-1}}p(x_{t},x_{t-1},y_{1:t})}
利用連鎖律 來展開
p
(
x
t
,
x
t
−
1
,
y
1
:
t
)
{\displaystyle p(x_{t},x_{t-1},y_{1:t})}
α
t
(
x
t
)
=
∑
x
t
−
1
p
(
y
t
|
x
t
,
x
t
−
1
,
y
1
:
t
−
1
)
p
(
x
t
|
x
t
−
1
,
y
1
:
t
−
1
)
p
(
x
t
−
1
,
y
1
:
t
−
1
)
{\displaystyle \alpha _{t}(x_{t})=\sum _{x_{t-1}}p(y_{t}|x_{t},x_{t-1},y_{1:t-1})p(x_{t}|x_{t-1},y_{1:t-1})p(x_{t-1},y_{1:t-1})}
由於
y
t
{\displaystyle y_{t}}
x
t
{\displaystyle x_{t}}
x
t
{\displaystyle x_{t}}
x
t
−
1
{\displaystyle x_{t-1}}
α
t
(
x
t
)
=
p
(
y
t
|
x
t
)
∑
x
t
−
1
p
(
x
t
|
x
t
−
1
)
α
t
−
1
(
x
t
−
1
)
{\displaystyle \alpha _{t}(x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha _{t-1}(x_{t-1})}
這樣，由於
p
(
y
t
|
x
t
)
{\displaystyle p(y_{t}|x_{t})}
p
(
x
t
|
x
t
−
1
)
{\displaystyle p(x_{t}|x_{t-1})}
輸出機率 和狀態轉移機率 我們可以很快計算用
α
t
−
1
(
x
t
−
1
)
{\displaystyle \alpha _{t-1}(x_{t-1})}
α
t
(
x
t
)
{\displaystyle \alpha _{t}(x_{t})}
前向式演算法可以很容易地被修改來適應其他的HMM變種，比如馬可夫跳躍線性系統 。
為了能夠使用「未來的歷史」（比如我們在試圖預測過去的某個時點的狀態），我們可以執行後向演算法，它是前向式演算法的一個補充。這一操作被稱為平滑[為何？ 。 前向-後向演算法 對
1
<
k
<
t
{\displaystyle 1<k<t}
P
(
x
k
|
y
1
:
t
)
{\displaystyle P(x_{k}|y_{1:t})}
為了解碼最可能的序列，需要使用維特比演算法 。它會從過去的觀測中試圖推測最可能的狀態序列，也即使
P
(
x
0
:
t
|
y
0
:
t
)
{\displaystyle P(x_{0:t}|y_{0:t})}
^ 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 ^ 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 .
