비터 비 알고리즘 이해

Question

저는 비터 비 알고리즘의 단계적인 예를 통해 정확한 단계를 찾고있었습니다.

D N V T A N V 

어떻게 우리가 얻을 수있는 비터 비 알고리즘을 사용합니까 :로 입력 문장과

고려 문장 태그 :로

The cat saw the angry dog jump 

그리고이에서 내가 좋아하는 것이 가장 가능성 출력을 생성합니다 위 출력은 trigram-HMM?

(PS :. 코드 또는 수학 표현의 I 단계의 설명에 의해 정확한 단계를 찾고 있어요,하지 조각 번호와 같은 모든 확률을 가정합니다.)

감사 톤!

Answer 1

사용 가능한 책 중 하나에서 찾으십시오. 크리스 비숍 (Chris Bishop) "패턴 인식 및 기계 학습" 비터 비 알고리즘은 정말 기본적인 것으로 문서의 다양한 세부 수준에서 설명되었습니다.

Answer 2

비터 비 알고리즘과 은닉 마르코프 모델의 경우 먼저 전환 확률과 방출 확률이 필요합니다.

예에서 전환 확률은 P (D-> N)이고 P (N> V)이고 배출 확률 (bigram 모델이라고 가정)은 P (D | .

물론 현실 세계의 예에서는 고양이, 톱 등과 같은 단어가 많이 있습니다. 모든 훈련 데이터를 반복하여 P (D |), P (N | | cat), P (N | 자동차). 그런 다음 Viterbi 알고리즘을 사용하여 사용자의 관찰에 따라

D N V T A N V 

과 같은 가장 가능성있는 태그 시퀀스를 찾습니다.

여기에 비터 비를 구현했습니다.

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