[Algorithm]Viterbi algorithm

주어진 것들이 다음과 같을 때:

-observation space (=O)

-observation sequence (=Y=(y_1, y_2, ..., y_T)

-state space (=S)

-initial state probability (=Π)

-transition matrix (=A)

-emission matrix (=B)

(transition matrix a_(i,j)는 state i에서 state j로 바뀔 확률(직전 시점에서 다음 시점의 state 전이 확률로, markov property를 전제하는 상황)

 

구하고자 하는 것:

The most likely state sequence X=(x_1, x_2, ..., x_T)

 

이상적이나 불가능한 상황:

t=1, 2, ..., T까지 모든 가능한 경로를 계산하고 argmax취하자.

->|S| = 13이고 T가 10이라면

가능한 경로의 개수가 13^10, 약 5x10^14,

경로별 계산량이 덧셈, 곱셈이 20회, 

총 필요한 계산량이 10^16회 정도,

초당 10^11회 계산 가능하다면 모든 경로를 계산하는데에 있어서 약 1.15 day가 소모

 

알고리즘의 핵심:

-initial, 첫 observation을 보고 가장 높은 확률을 갖는 (state, probability)를 찾는다.

-recursive, 직전(t-1)에 구한 (state, probability) 모든 case에 대해 observation(t)을 통해 현재(t)에 (state, probability)를 찾고 max값과 argmax(state)를 저장한다.

 

알고리즘의 결과:

-마지막 시점(T)에 argmax(state)을 얻고, 그때(T)에 사용한 T-1시점의 state을 얻고, 그때(T-1)에 사용한 T-2시점의 state을 얻고....

따라서 (x_1, x_2, ..., x_T)을 얻는다.

 

Complexity of this implementation:

O(Tx|S|^2), 즉 T에 대해서는 차수가 1인게 관건

(이상적이나 불가능한 상황은 O(|S|^T), 같은 |S|=13, T=10을 비교하면 1,690과 13^10)

 

참고자료:

-en.wikipedia.org/wiki/Viterbi_algorithm

Viterbi algorithm - Wikipedia

-post.naver.com/viewer/postView.nhn?volumeNo=17867939&memberNo=11190852

#3 비터비와 비터비 알고리즘

-cs.kangwon.ac.kr/~leeck/NLP/06-2_viterbi.pdf