我一直在寻找一个精确的逐步维特比算法的例子。了解维特比算法
与输入句子。考虑句子标签:
The cat saw the angry dog jump
而从这个我想生成最可能的输出为:
D N V T A N V
我们如何使用Viterbi算法来获得上述输出使用trigram-HMM?
(PS:我一步解释寻找一个精确的一步,而不是一段代码,或数学表示假设所有的概率为数字。)
由于一吨!
我一直在寻找一个精确的逐步维特比算法的例子。了解维特比算法
与输入句子。考虑句子标签:
The cat saw the angry dog jump
而从这个我想生成最可能的输出为:
D N V T A N V
我们如何使用Viterbi算法来获得上述输出使用trigram-HMM?
(PS:我一步解释寻找一个精确的一步,而不是一段代码,或数学表示假设所有的概率为数字。)
由于一吨!
我建议你在其中一本书中可以看到它, Chris Bishop“模式识别和机器学习”。维特比算法是一个非常基本的东西,并在文献中的各个层面详细描述。
对于维特比算法和隐马尔可夫模型,首先需要转换概率和发射概率。在你的例子中,转移概率是P(D> N),P(N> V),发射概率(假设二元模型)是P(D | the),P(N | cat) 。你需要遍历所有的训练数据以估计P(D | the),P(N()), | cat),P(N | car)。然后我们使用维特比算法找到最有可能的标签序列,如
D N V T A N V
给出你的观察。
这里是我的Viterbi实现。
def viterbi(vocab, vocab_tag, words, tags, t_bigram_count, t_unigram_count, e_bigram_count, e_unigram_count, ADD_K):
vocab_size = len(vocab)
V = [{}]
for t in vocab_tag:
# Prob of very first word
prob = np.log2(float(e_bigram_count.get((words[0],t),0)+ADD_K))-np.log2(float(e_unigram_count[t]+vocab_size*ADD_K))
# trigram V[0][0]
V[0][t] = {"prob": prob, "prev": None}
for i in range(1,len(words)):
V.append({})
for t in vocab_tag:
V[i][t] = {"prob": np.log2(0), "prev": None}
for t in vocab_tag:
max_trans_prob = np.log2(0);
for prev_tag in vocab_tag:
trans_prob = np.log2(float(t_bigram_count.get((t, prev_tag),0)+ADD_K))-np.log2(float(t_unigram_count[prev_tag]+vocab_size*ADD_K))
if V[i-1][prev_tag]["prob"]+trans_prob > max_trans_prob:
max_trans_prob = V[i-1][prev_tag]["prob"]+trans_prob
max_prob = max_trans_prob+np.log2(e_bigram_count.get((words[i],t),0)+ADD_K)-np.log2(float(e_unigram_count[t]+vocab_size*ADD_K))
V[i][t] = {"prob": max_prob, "prev": prev_tag}
opt = []
previous = None
max_prob = max(value["prob"] for value in V[-1].values())
# Get most probable state and its backtrack
for st, data in V[-1].items():
if data["prob"] == max_prob:
opt.append(st)
previous = st
break
for t in range(len(V) - 2, -1, -1):
opt.insert(0, V[t + 1][previous]["prev"])
previous = V[t][previous]["prev"]
return opt
维特比算法采用一系列输出并返回最可能的一系列隐藏状态以产生这些输出。那么,如果你已经知道隐藏的状态(这是D N V T等,对吧),你该怎么做? – chm