理解Viterbi算法

Question

我正在寻找一个精确的一步一步的例子维特比算法。

考虑使用输入句子标记的句子为：

The cat saw the angry dog jump

根据这一点，我想产生最可能的结果如下：

D N V T A N V

我们如何使用Viterbi算法获得上面的输出，使用trigram-HMM？

(PS:我正在寻找一个精确的一步一步的解释，而不是一段代码，或者数学表示。假设所有概率都是数字。)

谢谢你一吨！

Answer 1

我建议你查阅其中一本书，例如克里斯毕晓普“模式识别和机器学习”。Viterbi算法是一个非常基本的东西，在文献中已经有不同层次的详细描述。

Answer 2

对于Viterbi算法和隐马尔可夫模型，首先需要转移概率和发射概率。

在你的例子中，跃迁概率是P(D->N)，P(N->V)，发射概率(假设双图模型)是P(D_x_(？))，P(N_x~(Cat))。

当然，在现实世界的例子中，有更多的词比，猫，锯子，等等。你必须循环你所有的训练数据，以得到估计的P(D_X)，P(N_X_ cat )，P(N_S_Car)。然后，我们使用Viterbi算法查找最有可能的标记序列，如

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