forward algorithm

[Jiahn K]

I understand that forward algorithm costs more than Viterbi algorithm since forward algorithm sums up all possible paths. But I don’t know how just summing up all the paths show the most efficient path and it can be replaced by Viterbi algorithm

Thank you

[Simon]

The sum over all paths computed by the forward algorithm will include the single more likely path, the second most likely, and so on…

One way to understand Viterbi is that we can approximate a sum of many terms (here, path likelihoods) by just taking the largest term. This seems fine if we assume that the largest term is much bigger than all the rest. Try adding these numbers together as quickly as you can:

362823 + 2321 + 123 + 32 + 21 + 14 + 8 + 3 + 1

You could give a very quick answer: “The sum is about 362823”. You would be pretty close.

If that argument isn’t entirely convincing, then another way to understand Viterbi, at least for use in recognition, is to ask you to compute which of these sums will result in the largest value, as quickly as you can:

362823 + 12321 + 9123 + 632 + 321 + 14 + 12 + 3 + 1

221344 + 13234 + 1023 + 332 + 211 + 47 + 11 + 4 + 2

and you could do that just by looking at the largest term in each sum and comparing those, again avoiding actually doing the summation.

[Author]

Posts