此條目需要
精通或熟悉相关主题的编者 参与及协助编辑。
(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 .
