CODEWITHSUNDEEP
machine-learningnlpdata-mininghidden-markov-modelsviterbi
yns
yns

Reputation: 450

Viterbi Algorithm Sequence finding

I am trying to understand Viterbi Algorithm.

The states are; S1, S2, S3, BEGIN, END

The values are rounded and truncated.

The smoothed State transition table is as follows;

  S1  S2  S3 B E

S1 -0.7 -1.6 -1.6 -INF -2.0

S2 -2.0 -1.3 -0.7 -INF -2.0

S3 -1.3 -0.7 -2.0 -INF -2.0

B -1.2 -1.2 -1.2 -INF -1.9

E -INF -INF -INF -INF -INF

The smoothed emission table from states to red, green, blue;

  RED GREEN BLUE

S1 -0.9 -1.2 -1.6

S2 -1.6 -0.9 -1.2

S3 -1.6 -1.6 -0.6

B -INF -INF -INF

E -INF -INF -INF

The question is; Symbols have been seen are; RED RED GREEN BLUE

what are the most likely states?

Therefore;

I created the Viterbi algorithm matrix according to values above;

First row represent the S1, S2, S3 values when RED symbol seen, just like that rest of rows for S1,S2,S3 values when red, green and blue seen.

For the first row I calculated it;

values are smoothed by taking natural logarithms of them therefore I am adding values instead of multiplying.

For the first red seen;

δ(S1) = MAX{P(S1|B)+P(R|S1)+δ(B)} = -1.2 - 0.9 + 0= -2.1

δ(S2) = MAX{P(S2|B)+P(R|S2)+δ(B)} = -1.2 - 1.6 + 0= -2.8

δ(S3) = MAX{P(S3|B)+P(R|S3)+δ(B)} = -1.2 - 1.6 + 0= -2.8

Just like above, for the next red seen;

δ(S1) = MAX{ (P(S1|S1)+P(R|S1)+δ(S1) ), ( P(S1|S2)+P(R|S2)+δ(S2) ), ( P(S1|S3)+P(R|S3)+δ(S3) )}

= MAX{ (-0.7-0.9-2.1),(-1.6-1.6-2.8), (-1.6-1.6-2.8) } = MAX{-3.7, -6, -6}

The maximum is -3.7 therefore S1 value when RED is seen; -3.7 . Rest of the values are calculated as above.

Viterbi Algorithm Matrix;

  S1  S2  S3 B E

RED -2.1 -2.8 -2.8 -INF -INF

RED -3.7 -5.2 -5.2 -INF -INF

GREEN -5.8 -6.3 -7.0 -INF -INF

BLUE -8.1 -8.6 -7.8 -INF -INF

The answer of this example shows that most likely states are; S1, S1, S2, S3

However shouldn't it be; S1, S1, S1, S3? Because maximum value for the first red is -2.1 which is belong S1 and for second red it is again S1, and for the third one again S1 value is highest and for the blue S3 value is the highest. I can be wrong because I actually couldn't understand the dynamic programming approach for Viterbi.

Upvotes: 0

Views: 534

Answers (1)

davidhigh
davidhigh

Reputation: 15528

You should begin to trust well-established algorithms ;-). Seriously, you made no mistake in the calculation of the first two steps, and as the algorithm proceeds in the same way, I guess you haven't either in the following steps.

So what is going on here? I guess your mistake (imo, it isn't a mistake, but rather it is good that you try to understand things) here is that you are not incoporating the last step into your thoughts. In fact, if you had the state sequence RED,RED,GREEN, your result would be S1,S1,S1.

However, when you now add the next signal, BLUE, the algorithm takes into account that transitions S1->S3 (which is the preferred state for BLUE) are much more unlikely than S2->S3. Thus it favors S1,S1,S2,S3 instead of S1,S1,S1,S3, even though the latter would minimize the first three signals alone.

Upvotes: 1

Related Questions