在Python中应用隐马尔可夫模型

Question

我最近在计算生物学课上有一个作业，需要用到隐马尔可夫模型（HMM）。虽然我觉得我对HMM有一定了解，但在代码中应用它时却遇到了困难。简单来说，我需要把公平赌赌场问题应用到DNA中的CpG岛上——也就是利用观察到的结果来预测隐藏状态，使用一个转移矩阵。我最终找到了一个能正确工作的解决方案……但不幸的是，它的运行时间是指数级的。我的伪代码大概是这样的：

*注意：trans_matrix包含了从一个状态转移到另一个状态的概率，以及从一个观察结果转移到另一个观察结果的概率。

HMM(trans_matrix, observations):
  movements = {}
  for i in range(0,len(observations):
    movements[i] = #list of 4 probabilities, all possible state changes
  poss_paths = []
  for m in movements.keys():
    #add two new paths for every path currently in poss_paths
    #  (state either changes or doesn't)
    #store a running probability for each path
  correct_path = poss_paths[index_of_highest_probability]
  return correct_path

我意识到，当我查看所有可能的路径时，就会导致运行时间呈指数增长#为当前在poss_paths中的每条路径添加两条新路径。不过，我不太确定如何在不查看所有路径的情况下找到概率最高的路径。

谢谢！

编辑： 在做作业时，我确实找到了很多关于维特比算法的信息，但我对它是如何给出最佳答案感到困惑。似乎维特比（我当时主要关注的是前向算法）会查看一个特定的位置，然后向前移动一到两个位置，再决定“正确”的下一个路径增量，只看了几个后续的概率。我可能理解错了；维特比算法就是这样工作的吗？伪代码会很有帮助。谢谢！

Answer 1

隐马尔可夫模型的一个好处是，你通常可以在不逐一考虑所有可能路径的情况下完成你需要做的事情。你现在尝试的方法看起来像是在寻找最可能的单一路径，而这可以通过动态规划来实现，使用的是维特比算法——你可以参考这个链接：http://cs.brown.edu/research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.html。在类似的文档中，还有其他有趣的内容，比如计算某个位置的隐藏状态的概率，或者所有位置的概率。通常这涉及到一些叫做“alpha”和“beta”的过程，这也是一个不错的搜索关键词，和隐马尔可夫模型一起使用。

在这里有一个详细的描述：http://en.wikipedia.org/wiki/Viterbi_algorithm，里面有数学伪代码，还有我认为是Python的代码。像大多数这样的算法一样，它利用了马尔可夫性质，也就是说，一旦你知道某个时刻的隐藏状态，你就知道了回答那个时刻问题所需的一切——你不需要知道过去的历史。就像动态规划一样，你是从左到右处理数据，利用之前计算的输出结果来推导当前的输出结果。你在每个状态j的时刻k想要计算的是，直到时刻k的观察数据的概率，这个概率是沿着最可能的路径到达状态j的。这个概率是由观察数据在时刻k给定状态j的概率，乘以前一个时刻k-1的某个状态转移到j的概率，再乘以在时刻k-1的所有观察数据的概率（前提是你在时刻k-1时处于之前的状态）——这个最后的部分是你刚刚为时刻k-1计算的。你会考虑所有可能的前一个状态，选择那个给你最高综合概率的状态。这就给了你在时刻k的状态j的答案，同时你也保存了给你最佳答案的前一个状态。虽然看起来你只是在处理时刻k和k-1的输出，但你现在有了一个反映了所有数据直到时刻k的答案。你会继续这个过程，直到k是你数据中的最后一个点，这时你就得到了每个最终状态的概率。选择这个时刻给你最高概率的状态，然后根据你保存的信息追溯到时刻k-1，找出你用来计算直到k的数据的概率的前一个状态j。