Viterbi algorithm (비터비 알고리즘)

비터비 알고리즘은 데이터와 모델 (주로 Hidden Markov Model)이 주어졌을때에 가장 확률적으로 높은 상태를 알아내는 방법입니다.

 

동적 프로그래밍 (Dynamic Programming)으로 구현할 수 있고요.

현재의 상태는 그 바로 이전의 상태에의해서만 영향을 받는다는 가정하에 동작합니다.

 

자세한 알고리즘은

Initialization (i = 0):

      v₀(0) = 1, v_k(0) = 0 for k > 0;

Recursion (i = 1…L):

      v_l(i) = e_l(x_i)max_k(v_k(i-1)a_kl);

      ptr_i(l) = argmax_k(v_k(i-1)a_kl);

Termination:

      P(x, π^*) = max_k(v_k(L)a_k0);

      π^*_L = argmax­_k(v_k(L)a_k0);

Traceback (i = L…1):

      π_i-1 = ptr(π_i^*)