machine-learning - 维特比算法 序列查找

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-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) )}

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

最大值为 -3.7，因此看到红色时的 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值是最高的。我可能是错的，因为我实际上无法理解维特比的动态规划方法。

Answer 1

您应该开始信任成熟的算法;-)。说真的，你在前两步的计算中没有犯错，并且由于算法以同样的方式进行，我猜你在接下来的步骤中也没有犯错。

那么这是怎么回事呢？我猜你的错误(在我看来，这不是一个错误，而是你尝试理解事物是件好事)是你没有将最后一步纳入你的想法中。事实上，如果您有状态序列 RED，RED，GREEN，您的结果将是 S1，S1，S1。

但是，当您现在添加下一个信号“蓝色”时，算法会考虑到转换 S1->S3(这是蓝色的首选状态)比 S2->S3 的可能性要小得多。因此，它有利于 S1,S1,S2,S3 而不是 S1,S1,S1,S3，即使后者会单独最小化前三个信号。