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

ViterbiAlgorithm이 most probable path를 찾는 방법이긴 하나, 이것이 항상 적절하지는 않다.

주어진 서열 xi에 대한 state를 알기 원하나, 보다 일반적으로, 주어진 서열에 대해 state k로 부터 온 관측 xi의 Probability를 알기 원한다. 이것은 ConditionalProbability P(πi=k|x)이며, emitted sequence가 알려졌을 때, state k일 PosteriorProbability 이다.

ViterbiAlgorithm의 vk(i)와 대응되는 변수로 bk(i)사용.

bk(i) = P(x(i+1)...x(L) | πi=k)

BackwardAlgorithm

Initialisation (i=L) :       bk(L) = ak0 for all k.

Recursion (i=L-1,...,1) :    bk(i) = SUM(l){ akl el(x(i+1)) bl(i+1) }.

Termination:                 P(x) = SUM(l){ aol el(x1) bl(1) }.

ForwardAlgorithm의 fk(i)와의 관계. 여기서, P(x)는 forward or backward calculation의 결과.

               fk(i) bk(i)
P(πi=k | x) = ------------
                  P(x)