在HMM中找到top-k维特比路径

Question

我需要编写一个算法,在HMM中找到top-k维特比路径(使用常规维特比算法找到最佳路径).

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

Answer 1

我们可以小心解决这个问题.通过查看hmm的格子结构最容易看到:

在这个例子中,隐藏状态是00,01,10,11,表示这四个集合为S.观察结果未显示,但假设它们是0,1.

假设我们有正确的Transition矩阵:

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)步骤中将指针向后保持到最大化上述最大函数的状态.最后,我们只检查状态中的所有alpha(i,T)和i,并找出哪一个最大,然后再跟回以获得最可能的状态序列.

现在我们需要将其扩展为存储顶部k路径.目前在每个alpha(i,t),我们只存储一个父.但是假设我们存储了前k个前辈.因此,每个alpha(i,t)不仅对应于最可能的值和它从其转换的节点,而且对应于它可以从其转换的前k个节点的列表以及它们按排序顺序的值.

这很容易做到,因为它不是做max,而只取一个前面的节点,我们采用前面的前k个节点并存储它们.现在对于基本情况,没有前面的节点,因此alpha(i,1)仍然只是一个值.当我们到达任意列(比如说t)并且想要找到在该列中的节点(i)处结束的前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个.

在排序矩阵中看到这个微小变化Kth最小元素,请注意,在我们的例子中,列没有排序,但那里的想法仍然适用.

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

这可能很难遵循,但如果您有任何问题,或者我做错了什么,请告诉我.