0

我试图理解维特比算法。

各州是；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 -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

问题是; 已经看到的符号是； 红色 红色 绿色 蓝色

最有可能的状态是什么？

所以;

我根据上面的值创建了维特比算法矩阵；

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

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

通过取它们的自然对数来平滑值，因此我将值相加而不是相乘。

对于第一个看到的红色；

δ(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

就像上面一样，下一个看到的红色；

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

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

最大值为 -3.7，因此看到 RED 时的 S1 值；-3.7 。其余值如上计算。

维特比算法矩阵；

  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，S1，S1，S3？因为第一个红色的最大值是-2.1，属于 S1，第二个红色的最大值是 S1，第三个红色的最大值是 S1，蓝色的 S3 值是最高的。我可能是错的，因为我实际上无法理解 Viterbi 的动态编程方法。

4

1 回答 1

1

您应该开始信任完善的算法；-)。说真的，你在前两步的计算中没有错，随着算法以同样的方式进行，我猜你在接下来的步骤中也没有。

那么这里发生了什么？我猜您的错误（imo，这不是错误，而是您尝试理解事物是一件好事）是您没有将最后一步纳入您的想法。事实上，如果你有状态序列 RED,RED,GREEN，你的结果将是 S1,S1,S1。

但是，当您现在添加下一个信号 BLUE 时，算法会考虑到转换 S1->S3（这是 BLUE 的首选状态）比 S2->S3 更不可能发生。因此它有利于 S1,S1,S2,S3 而不是 S1,S1,S1,S3，即使后者会单独最小化前三个信号。

于 2014-05-11T21:46:36.900 回答