HiddenMarkovModel에서의 state path 찾는방법의 한가지. Decoding의 한 방법.

서열 x에 대해, 많은 다른 state path가 존재할 수 있기때문에 이들 모든 가능한 path들의 더하여, full Probability of x를 다음처럼 구한다.

P(x) = SUM { P(x,π) }

가능한 path π는 서열의 길이가 증가함에 따라 지수적으로 증가함으로 모든 path를 고려하는 것은 불가능하다. 따라서, most probable path π*를 구한후, P(x)를 approximation한다. 사실 P(x)는 approximation할 필요가 없는데, ViterbiAlgorithm에 DynamicProgramming절차와 유사한 방법으로 계산될 수 있기 때문이다. 이것이 ForwardAlgorithm.

ViterbiAlgorithm의 vk(i)와 대응되는 변수로 fk(i)사용. 이것은 πi=k인 xi까지의 서열들이 관측될 JointProbability이다.

fk(i) = P(x1...xi, πi=k)

Recursion방법으로 다음식을 사용한다.

fl(i+1) = el(x(i+1)) SUM(k){ fk(i)akl }.

ForwardAlgorithm

Initialisation (i=0) :    f0(0)=1, fk(0)=0 for k>0.

Recursion (i=1...L) :     fl(i) = el(xi) SUM(k){ fk(i-1)akl }.

Termination :             P(x) = SUM(k){ fk(L)ak0 }.

See also: BackwardAlgorithm