algorithm - 在 HMM 中找到前 k 个 viterbi 路径

Question

我需要编写一个算法来查找 HMM 中的前 k 个维特比路径(使用常规维特比算法来查找最佳路径)。

我想我可能需要为每个状态 N 保存一个大小为 k 的列表 V_t,N，其中包含以状态 N 结尾的前 K 条路径，但我不太确定如何跟踪该列表。有任何想法吗？谢谢

Answer 1

我们可以小心解决这个问题。看hmm的格子结构最容易看出来:

在此示例中，隐藏状态为 00、01、10、11，将这四个的集合表示为 S。观察结果未显示，但假设它们为 0,1。

假设我们有正确的转移矩阵:

transition[4][4]

排放概率:

emissions[4][2]

和初始概率:

p[2]

因此每一列都代表隐藏状态，Viterbi 的目标是根据观察结果计算最可能的隐藏状态序列。现在让 alpha(i, t) = 隐藏状态序列在时间 t 处于状态 i(i 是 00、01、10、11 之一)的最大概率，其中时间 t 的观察值是 o_t(o_t 是一个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，找出最大的那个，然后顺着它返回得到最可能的状态序列。

现在我们需要扩展它来存储前 k 条路径。目前在每个 alpha(i,t) 中我们只存储一个父级。然而，假设我们存储了前 k 个前辈。因此，每个 alpha(i, t) 不仅对应于最可能的值和它从中转换的节点，而且还对应于它可能从中转换的前 k 个节点的列表以及它们的值按排序顺序。

这很容易做到，因为我们不做 max，只取一个前节点，而是取前 k 个节点并存储它们。现在对于基本情况，没有前面的节点，所以 alpha(i, 1) 仍然只是一个值。当我们到达任意列(比如 t)并想要找到以该列中的节点 (i) 结尾的前 k 条路径时，我们必须找到前 k 个来自它们的前任路径以及从它们获取的前 k 条路径。

这就好像我们有以下问题，一个大小为 4 x k 的矩阵 m，其中一行代表前面的状态，m[state] 代表路径结束于此的前 k 个概率。这样 m 的每一行都按照从大到小的顺序排序，问题就变成了查找:

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 smallest element in sorted matrix , 请注意，在我们的例子中，列没有排序，但那里的想法仍然适用。

如果您仍在阅读，请注意此方法的总体复杂度为 O((numStates log k) * numStates * t) = O(numStates^2 * t * log k)(我相信这是正确的复杂度) .

这可能很难理解，但如果您有任何疑问或我做错了什么，请告诉我。