加速维特比执行
Speeding up Viterbi execution
我已经为我观察到的基于 HMM 的信号实现了一个朴素的维特比算法。解码器的执行时间似乎对我的要求来说太慢了。我现在正试图了解如何加快执行速度。当我要确定算法的计算复杂性时，我看到它被提到具有 t * s^2 的复杂性，其中 t 是观察数，s 是状态数。我大约有 3500 个状态和 100 个观察值。每个州有 729 个排放概率。
我也看到这篇paper中提到，维特比解码在本文中是指数的（2^k，其中k是约束长度）。我不太理解这个解释。但是，我相信如果维特比关于状态是指数的，那么算法肯定会非常慢，即使我将它并行化。
我的问题是：
- 维特比的复杂度是多少algorithm/decoding？它们在两种情况下是否相同？
- 如何修改维特比算法以加快速度？
编辑：我正在用 C++ 实现它，希望将来对其进行修改和并行化。
回答第一个问题：
如果你有 t 个观察值、s 个状态，并且每个状态都有 e 个发射概率，那么网格将有 t*s 个节点，并且评估每个节点将花费 e 个操作，因此 a 的整体复杂度天真的实现将是 O(t*s*e).
维特比解码可用于解码位序列。如果观察依赖于前k个二进制位，那么k位不同序列的个数就是2^k。这表示进行流解码所需的状态数（每个状态表示先前位的一种配置）。但是，这不太可能与您相关。
您 link 的论文描述了一种减少需要扩展的节点数量的方法。这不会改善最坏情况下的复杂性，但可能会根据您的特定问题的性质在典型使用中显着改善。
Viterbi 算法的复杂度为 O(t|S|^{n+1})，其中 n 是马尔可夫模型的阶数（在您的例子中是 1），t 是观察序列的长度，并且|S| 隐藏状态的数量。因此，在您的情况下，您有一个 O(t)，其常数因子为 3500^2 = 12 250 000。最好建议您尝试减少模型中隐藏状态的数量，或者使用随机算法进行调查可以 运行 快得多，但不能保证总是 return 绝对最好的结果。
我已经为我观察到的基于 HMM 的信号实现了一个朴素的维特比算法。解码器的执行时间似乎对我的要求来说太慢了。我现在正试图了解如何加快执行速度。当我要确定算法的计算复杂性时，我看到它被提到具有 t * s^2 的复杂性，其中 t 是观察数，s 是状态数。我大约有 3500 个状态和 100 个观察值。每个州有 729 个排放概率。
我也看到这篇paper中提到，维特比解码在本文中是指数的（2^k，其中k是约束长度）。我不太理解这个解释。但是，我相信如果维特比关于状态是指数的，那么算法肯定会非常慢，即使我将它并行化。
我的问题是：
- 维特比的复杂度是多少algorithm/decoding？它们在两种情况下是否相同？
- 如何修改维特比算法以加快速度？
编辑：我正在用 C++ 实现它，希望将来对其进行修改和并行化。
回答第一个问题：
如果你有 t 个观察值、s 个状态，并且每个状态都有 e 个发射概率，那么网格将有 t*s 个节点，并且评估每个节点将花费 e 个操作，因此 a 的整体复杂度天真的实现将是 O(t*s*e).
维特比解码可用于解码位序列。如果观察依赖于前k个二进制位，那么k位不同序列的个数就是2^k。这表示进行流解码所需的状态数（每个状态表示先前位的一种配置）。但是，这不太可能与您相关。
您 link 的论文描述了一种减少需要扩展的节点数量的方法。这不会改善最坏情况下的复杂性，但可能会根据您的特定问题的性质在典型使用中显着改善。
Viterbi 算法的复杂度为 O(t|S|^{n+1})，其中 n 是马尔可夫模型的阶数（在您的例子中是 1），t 是观察序列的长度，并且|S| 隐藏状态的数量。因此，在您的情况下，您有一个 O(t)，其常数因子为 3500^2 = 12 250 000。最好建议您尝试减少模型中隐藏状态的数量，或者使用随机算法进行调查可以 运行 快得多，但不能保证总是 return 绝对最好的结果。