我需要编写一个算法，找到HMM中前K个维特比路径（使用常规的维特比算法找到最佳路径）。
我认为我可能需要为每个状态N保存大小为k的V_t,N列表，其中包含以状态N结尾的前K条路径，但我不太确定如何跟踪该列表.. 有什么想法吗？谢谢
在HMM中寻找前k个维特比路径
12
- John Smith
1
1你需要一个n-best解码器，通常使用波束搜索来实现。 - bmargulies
2个回答
19
我们可以通过一些小心处理来解决这个问题。最容易理解的方法是查看HMM的网格结构：
假设我们有正确的转移矩阵：
排放概率：
每一列代表着隐藏状态，维特比算法的目标是根据观测值计算出最可能的隐藏状态序列。现在，令 alpha(i, t) 为在时间 t 观测值为 o_t（o_t 为 0 或 1）时，隐藏状态序列在状态 i（i 是 00、01、10 或 11 中的一个）的概率最大值。将第一个观测值表示为 o_1。可以高效地计算如下：
为了找到最佳路径，我们在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条路径。
现在看起来很困难，但是花些时间理解它，我们可以使用堆在O(4 log k)或O(numStates log k)的时间内解决排好序矩阵问题。参见这个稍微变化的已排序矩阵中第K小的元素，只要注意到在我们的情况下列没有排序，但是那里的想法仍然适用。如果您还在阅读，请注意该方法的总体复杂度为O((numStates log k)* numStates * t) = O (numStates ^ 2 * t * log k)(我相信这是正确的复杂度)。这可能很难理解，但如果您有任何问题，请告诉我，或者我做错了什么。
假设我们有正确的转移矩阵：
transition[4][4]
排放概率：
emissions[4][2]
初始概率：
p[2]
每一列代表着隐藏状态，维特比算法的目标是根据观测值计算出最可能的隐藏状态序列。现在，令 alpha(i, t) 为在时间 t 观测值为 o_t（o_t 为 0 或 1）时，隐藏状态序列在状态 i（i 是 00、01、10 或 11 中的一个）的概率最大值。将第一个观测值表示为 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乘以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小的元素，只要注意到在我们的情况下列没有排序，但是那里的想法仍然适用。如果您还在阅读，请注意该方法的总体复杂度为O((numStates log k)* numStates * t) = O (numStates ^ 2 * t * log k)(我相信这是正确的复杂度)。这可能很难理解，但如果您有任何问题，请告诉我，或者我做错了什么。
- Anil Vaitla
2
你确定这是可证明的，可以找到前k个最优解，还是只是一个简单的启发式beam搜索方案？ - matanster
2其可证明，仅仅是动态规划的扩展（这些证明通常基于数学归纳法，证明n = 1，假设n - 1成立，再证明n成立）。 - Anil Vaitla
3
其实关于这个问题已经有很多文献了。我找到了这个，需要仔细查看。
列出了应用程序的Viterbi解码算法清单
http://www.ensc.sfu.ca/people/faculty/cavers/ENSC805/readings/42comm02-seshadri.pdf
- Madmartigan
1
有没有更现代的引用可以提供？ - matanster
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接