Viterbi Algorithm

Recall that to calculate the partial probability, at time t we only need the 's for time t-1. Having calculated this partial probability, it is thus possible to record which preceding state was the one to generate (i,t) - that is, in what state the system must have been at time t-1 if it is to arrive optimally at state i at time t. This recording (remembering) is done by holding for each state a back pointer which points to the predecessor that optimally provokes the current state.

Formally, we can write

Here, the argmax operator selects the index j which maximises the bracketed expression.