Forward–backward algorithm: Difference between revisions

Revision as of 08:10, 26 November 2019

Revision as of 19:25, 30 November 2019

Line 293:

==Pseudocode==

<pre>

'''algorithm''' forward_backward '''is'''

Backward(guessState, sequenceIndex):

'''input:''' guessState

if sequenceIndex is past the end of the sequence, return 1

int * Backward(n, ''sequenceIndex+1)''

if (guessState, sequenceIndex) has been seen before, return saved result

'''output:''' ''result''

result = 0

for each neighboring state n:

'''if''' ''sequenceIndex'' is past the end of the sequence, return 1'''then'''

result = result + (transition probability from guessState to

'''return''' 1

n given observation element at sequenceIndex)

'''if''' (''guessState'', ''sequenceIndex'') has been seen before, return saved result'''then'''

* Backward(n, sequenceIndex+1)

'''return''' saved result

save result for (guessState, sequenceIndex)

return result

''result'' := 0

</pre>

'''for each''' neighboring state n:

''result'' := result + (transition probability from ''guessState'' to

n given observation element at ''sequenceIndex'')

× Backward(n, ''sequenceIndex'' + 1)

Backward save result for (''guessState'', ''sequenceIndex''):

'''return''' ''result''

==Python example==