我需要编写一个算法来找到 HMM 中的前 k 个维特比路径（使用常规维特比算法来找到最佳路径）。
我想我可能需要为每个状态 N 保存一个大小为 k 的列表 V_t,N，其中包含以状态 N 结尾的前 K 个路径，但我不太确定如何跟踪该列表。有什么想法吗？谢谢
问问题
7875 次
2 回答
19
我们可以小心地解决这个问题。通过查看 hmm 的格状结构最容易看出：
在此示例中，隐藏状态为 00、01、10、11，将这四个的集合表示为 S。未显示观察值，但假设它们为 0,1。
假设我们有正确的转移矩阵：
transition[4][4]
排放概率：
emissions[4][2]
和初始概率：
p[2]
所以每一列都代表隐藏状态，维特比的目标是根据观察结果计算最可能的隐藏状态序列。现在让 alpha(i, t) = 隐藏状态序列处于状态 i 的最大概率（i 是 00、01、10、11 之一），在时间 t，其中时间 t 的观察结果是 o_t（o_t 是 1 0, 1)。让第一个观察值表示为 o_1。它可以有效地计算为：
alpha(i, 1) = p[i] * emissions[i][o_1]
alpha(i, t) = emissions[i][o_t] * max_{k in states} (alpha(k, t-1) * transition[k][i])
为了找到最佳路径，我们在 alpha(i, t) 步骤中保持指针向后，指向上面最大化 max 函数的状态。最后，我们只检查所有状态中的 alpha(i, T) 和 for i，找到最大的一个，然后再返回得到最可能的状态序列。
现在我们需要扩展它来存储 top k-paths。目前在每个 alpha(i,t) 我们只存储一个父级。然而，假设我们存储了前 k 个前辈。因此，每个 alpha(i, t) 不仅对应于最可能的值和它从其转换的节点，而且还对应于它可能从其转换的前 k 个节点的列表及其按排序顺序排列的值。
这很容易做到，因为我们不做 max，只取一个前面的节点，而是取前 k 个前面的节点并存储它们。现在对于基本情况，没有前面的节点，所以 alpha(i, 1)，仍然只是一个值。当我们到达任意列（例如 t）并想要找到在该列中以节点 (i) 结束的前 k 条路径时，我们必须找到前 k 个前辈来自的前k 条路径以及从它们中获取的前 k 条路径。
这就好像我们有以下问题，一个大小为 4 x k 的矩阵 m，其中一行代表前一个状态，m[state] 代表路径结束于那里的前 k 个概率。因此 m 的每一行都按从大到小排序，现在问题变成了 find：
Best_K_Values(t, i) = Top K over all i,preceding_state,k (emissions[i][o_t] * m[preceding_state][k] * transition[preceding_state][i])
现在这看起来令人生畏，但需要一些时间来理解它，我们通常可以使用 O(4 log k) 或 O(numStates log k) 中的堆来解决排序矩阵问题中的前 k 个问题。
看到排序矩阵中第 Kth 个最小元素的细微变化，请注意，在我们的例子中，列没有排序，但那里的想法仍然适用。
如果您仍在阅读，请注意此方法的总体复杂度为 O((numStates log k) * numStates * t) = O(numStates^2 * t * log k) （我相信这是正确的复杂度）。
这可能很难理解，但如果您有任何问题，或者我做错了什么，请告诉我。
于 2013-03-16T20:26:24.110 回答
3
这方面实际上有大量文献。它需要一些挖掘，但我发现了这个。
使用应用程序列出 Viterbi 解码算法
http://www.ensc.sfu.ca/people/faculty/cavers/ENSC805/readings/42comm02-seshadri.pdf
于 2014-12-22T04:08:03.457 回答