加快Viterbi的执行

Question

对于我观察到的基于HMM的信号，我实现了一个朴素的Viterbi算法。对于我的要求，解码器的执行时间似乎太慢了。我现在正试着了解如何加快执行速度。当我确定算法的计算复杂性时，我看到它被称为具有s^2的复杂性，其中t是观察数，s是状态数。我大概有3500个州，100个观测。每个州有729个排放概率。

我还注意到，在这个纸中，维特比译码是指数的(2^k，其中k是约束长度)。我不太理解这个解释。但是，我相信如果Viterbi对于状态是指数型的，那么这个算法肯定会非常慢，即使我并行它。

我的问题是：

1. Viterbi算法/解码的复杂度是多少？在这两种情况下它们是一样的吗？
2. 如何修改Viterbi算法以加快速度？

编辑:我正在C++中实现它，希望将来修改它并并行化它。

Answer 1

要回答第一个问题：

如果您有t个观察，s状态，并且每个状态都有e个发射概率，那么网格将有t*s节点，评估每个节点将花费e个操作，所以简单实现的总体复杂性将是O(t*s*e)。

Viterbi译码可以用来解码比特序列。如果观察依赖于前面的k个二进制位，那么不同的k位序列的数目是2^k，这代表了您需要进行流解码的状态数s(每个状态代表以前比特的一个配置)。然而，这不太可能与你相关。

您链接到的论文描述了一种减少需要扩展的节点数量的方法。这将不会改善最坏的情况复杂性，但很可能会给典型的使用带来很大的改进，这取决于您的具体问题的性质。

Answer 2

维特比算法的复杂性是O(t|S|^{n+1})，其中n是马尔可夫模型的阶数(在你的例子中是1)，t是观察序列的长度，|S|是隐藏的状态数。因此，在您的例子中，有一个O(t)，其巨大的常数因子为3500^2 =12250 000。最好是尝试减少模型中隐藏的状态数，或者使用随机算法进行调查，这些算法可以运行得更快，但不能保证总是返回绝对最佳的结果。