瞭解維特比算法

Question

我一直在尋找一個精確的逐步維特比算法的例子。

與輸入句子。考慮句子標籤：

The cat saw the angry dog jump 

而從這個我想生成最可能的輸出爲：

D N V T A N V 

我們如何使用Viterbi算法來獲得上述輸出使用trigram-HMM？

（PS：我一步解釋尋找一個精確的一步，而不是一段代碼，或數學表示假設所有的概率爲數字。）

由於一噸！

Answer 1

我建議你在其中一本書中可以看到它， Chris Bishop「模式識別和機器學習」。維特比算法是一個非常基本的東西，並在文獻中的各個層面詳細描述。

Answer 2

對於維特比算法和隱馬爾可夫模型，首先需要轉換概率和發射概率。在你的例子中，轉移概率是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