Viterbi算法序列查找

Question

我在试着理解维特比算法。

状态是: S1，S2，S3，开始，结束

值是四舍五入和截断的。

平滑的状态转换表如下；

  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

从状态到红色、绿色、蓝色的平滑发射表；

  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

问题是:符号已经被看到了；红色，红色，绿色，蓝色，

最有可能的州是什么？

因此；

根据上述值建立了Viterbi算法矩阵；

第一行表示看到红色符号时的S1、S2、S3值，就像显示红色、绿色和蓝色时的S1、S2、S3值的其他行一样。

对于第一行，我计算了它；

值是通过取它们的自然对数来平滑的，所以我是在增加值而不是乘以。

第一次看到红色；

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

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

S3(δ)=最大{P(S3S3-B)+P(R=S3)+δ(B)}= -1.2 - 1.6 + 0= -2.8

就像上面一样，为下一次看到红色；

(S1)=最大{(P(S1_2)+P(R_(S_1))+δ(S1) )，(P(S_(S_1)_s_2)+P(R_(S_2)+δ(S2) )，(P(S_(S_1)\S_3)+P(R_(S_(3))+δ(S3) )} }

= MAX{ (-0.7-0.9-2.1)，(-1.6-1.6-2.8)，(-1.6-1.6-2.8) }=最大{-3.7，-6，-6}

因此，当看到红色时，最大值是-3.7，因此S1值；-3.7。其余的值按上面的方式计算。

Viterbi算法矩阵；

  S1  S2  S3 B E

红色-2.1-2.8-2.8 -INF -INF

红-3.7 -5.2 -5.2 -INF -INF

绿色-5.8 -6.3 -7.0 -INF -INF

蓝色-8.1 -8.6 -7.8 -INF -INF

这个例子的答案表明，最有可能的状态是: S1、S1、S2、S3

然而，不应该是；S1，S3?，因为第一个红色的最大值是-2.1，它属于S1，第二个红色的最大值又是S1，对于第三个红色，S1值最高，蓝色S3值最高。我可能错了，因为实际上我无法理解Viterbi的动态编程方法。

Answer 1

你应该开始相信可靠的算法;-)。说真的，您在计算前两个步骤时没有出错，而且随着算法以相同的方式进行，我想您在下面的步骤中也没有。

这是怎么回事？我想你的错误(国际海事组织，这不是一个错误，而是它是好的，你试着理解事情)在这里，你没有煽动进入你的想法的最后一步。实际上，如果您的状态序列为红色、红色、绿色，那么您的结果将是S1、S1、S1。

但是，当您现在添加下一个信号，蓝色时，算法考虑到转换S1->S3 (这是蓝色的首选状态)比S2->S3更不可能。因此，它倾向于S1、S1、S2、S3而不是S1、S3，尽管后者只会最小化前三个信号。