我需要编写一种算法来查找HMM中的前k个维特比路径(使用常规维特比算法来找到最佳路径)。
我想我可能需要为每个状态N保存一个大小为k的列表V_t，N，其中包含以状态N结尾的前K个路径，但是我不确定如何跟踪该列表。
有任何想法吗？谢谢
最佳答案
我们可以小心解决。通过查看hmm的网格结构，最容易看到:
在此示例中，隐藏状态为00、01、10、11，将这四个状态的集合表示为S。未显示观察值，但假定它们为0,1。
假设我们有正确的过渡矩阵:
transition[4][4]
排放概率:
emissions[4][2]
和初始概率:
p[2]
因此，每一列都代表隐藏状态，Viterbi的目标是根据观察结果计算最可能的隐藏状态序列。现在令alpha(i，t)=隐藏状态序列处于状态i(i是00、01、10、11中的一个)的最大概率，在时间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)和i，然后找出哪个最大，然后将其跟回以获取最可能的状态序列。
现在我们需要扩展它来存储顶部的k路径。目前，在每个alpha(i，t)中，我们仅存储一个父级。但是，假设我们存储了前k个前身。因此，每个alpha(i，t)不仅对应于最有可能发生变化的值及其从其转换过来的节点，而且还对应于其可能从其转换过来的前k个节点的列表及其值(按排序顺序)。
这很容易做到，因为它不做max，而只取一个在前的节点，而取前k个在前的节点并存储它们。现在，对于基本情况，没有前面的节点，因此alpha(i，1)仍然只是一个值。当我们到达任意列(例如t)并想找到在该列的节点(i)处结束的前k个路径时，我们必须找到前k个前辈来自和前k个前辈来自。
好像我们有以下问题一样，矩阵m的大小为4 x k，其中一行代表一个先前的状态，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)(我相信这是正确的复杂性)。
这可能很难执行，但是如果您有任何疑问，或者我做错了什么，请告诉我。