维特比算法 python_通俗讲解维特比算法
维特比算法说白了就是动态规划实现最短路径，只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法
维特比算法之所以重要，是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。——《数学之美》
下面我通过一个例子来解释讲解一下维特比算法！
词性标注问题
首先介绍一下什么是词性标注问题，比如我们有一句已经分词好的句子。
dog chase mouse
那么我们就可以进行词性标注为：
其中nn为名词，vv为动词。通过上面例子，我们就很容易看出词性标注的任务。
那么我们来了一句话之后，比如我们的词性字典中有nn,vv,prp(代词)，我们怎么能够找到dog
chase mouse 所对应的词性标注呢，如果每一个单词有nn，vv，prp三种可能，那么将会有3*3*3=27种可能，我们如何去挑选呢？
如下图：
我们总共有27条路径，那么如何得到我们Dog chase mouse的最优路径呢？
我们至少可以遍历每一条路径，求出各自的概率值，然后挑选最大的即可，比如我们求第一条路径的时候，可以这么表示：
所求的路径对应如下图红色线条所示：
求第27条路径的时候，我们可以这么表示：
所求的路径对应如下图红色线条所示：
那么我们从上面可以知道，要求一个句子的最优词性标注，我们至少可以遍历所有的路径，然后挑选概率值最大的那条路径即可！！！
但是问题来了！
给定模型，求给定长度为T的观测序列(这里指的就是Dog Chase Mouse)的概率，直接计算法的思路是枚举所有的长度T(例子中是三个，Dog，Chase，Mouse总共三个单词)的状态序列，计算该状态序列与观测序列的联合概率(隐状态发射到观测)，对所有的枚举项求和即可。
在状态种类为N(例子中就是三个，NN，VV,PRP)的情况下，一共有
种排列组合，每种组合计算联合概率的计算量为T，总的复杂度为
，这并不可取。
于是维特比算法隆重登场了！！
维特比算法
好了，到现在为止，我们假定我们已经训练好了一个隐马尔可夫模型了(训练好的意思，也就是单词到词性的发射概率，词性与词性的转移概率都已经在训练数据中学习得到了)，来了一句话，Dog Chase Mouse，我如何得到它的词性标注序列？
首先先上一个维特比算法流程图：
是不是非常晕，好吧，我下面争取按自己的话帮助大家理解一遍，再附上相应逻辑的代码！
解释如下：
# We implement the viterbi decoding algorithm.
def viterbi(words, hmm):
'''Viterbi algorihtm.Parameters----------words: list(str)The list of wordshmm: HMMThe hmm modelReturn------result: list(str)The POS-tag for each word.'''
# unpack the length of words, and number of postags
N, T = len(words), len(hmm.postags)
# allocate the decode matrix
score = [[-float('inf') for j in range(T)] for i in range(N)]
path = [[-1 for j in range(T)] for i in range(N)]
for i, word in enumerate(words):
if i == 0:
for j, tag in enumerate(hmm.postags):
score[i][j] = hmm.emit(words, i, tag)
else:
for j, tag in enumerate(hmm.postags):
best, best_t = -1e20, -1
temp = 0
# Your code here, enumerate all the previous tag
for j2,tag2 in enumerate(hmm.postags):
if best < hmm.trans(tag2,tag)*score[i-1][j2]:
best = hmm.trans(tag2,tag)*score[i-1][j2]
best_t = j2
best*=hmm.emit(words,i,tag)
score[i][j] = best
path[i][j] = best_t
#
best, best_t = -1e20, -1
for j, tag in enumerate(hmm.postags):
if best < score[len(words)- 1][j]:
best = score[len(words)- 1][j]
best_t = j
result = [best_t]
best, best_t = -1e20, -1
best_t = result[0]
for i in range(len(words)-1, 0, -1):
# Your code here, back trace to recover the full viterbi decode path
result.append(path[i][best_t])
best_t = result[-1] #result[-1]代表的是挑选最后一个
# convert POStag indexing to POStag str
result = [hmm.postags[t] for t in reversed(result)]
return result
致谢：
郭江师兄
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！