Week08 Viterbi Search

Viterbi Search

- 같은 상황일 때 최적의 경로를 찾을 때 사용된다.

EX) "나는 밥을" 이란 말 다음에 "먹는다" 와 "나는"이란 말중에 "먹는다"라는 말이 나올 확률이 높다.

 

알고리즘

initialization step : 처음의 상황의 확률을 초기화해주는 부분, pi는 가장 처음의 부분의 확률을 Markov model을 활용하여 구한 값이다.

 

recursion step : 다이나믹하게 상황을 돌며 최적의 경로를 매번 갱신하는 부분

 

termination step : 가장 마지막 부분의 값과 backtrace를 통해 최적의 경로를 구하는 부분

 

HMM(Hidden Markov Model)

Markov chain

- 어떤 상태의 확률을 정의할 때 그 이전 상태에 영향을 받는다.

 

HMM

- 각 상태가 Markov chain을 따르고 있으며 hidden되어 있다.

- 정확히 알 수 없는 정보들을 base로 확률을 구할 때 사용