비터비 알고리즘(viterbi)

참고 : http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html

         http://en.wikipedia.org/wiki/Viterbi_algorithm 

     

대학원때 POS 태거를 구현할때 처음 접했던 알고리즘인데 태거이외에도 많은 곳에서 사용되는듯하다.

HMM이 등장하는 곳에서는 처리 속도때문에 어김없이 따라 나오는 알고리즘으로 dynamic programming과도 밀접한 관련이 있다..

음성 처리와 언어처리에서 많이 사용되지만 HMM이 앞에 두분야 이외에도 확률이 수반되는 분야에는 빠지지 않고 등장하는것 같다.

c로 프로그램 하기에는 코딩시간도 오래걸리고 나중에 봐도 기억이 안나는 관계로 open office 스프레트 쉬트로 간단히 만들어 봤다.

open office로 아래 파일을 열면 데이터들이 보이는데 데이터들에 마우스 포인터를 찍으면 안에 수식이 나타난다. 수식은 곱셈이 전부이고 함수는 max()함수가 전부이다.

max()함수는 안에 인자들중 최대값을 선택하는 함수이다. 예를 들면(ex = max(1,2,3)) 이면 max의 리턴값은 3이 된다.

각 값들이 어떤 값을 참조했고 어떤 값에 종속적인지 보기 위해서

도구(alt+t->추적(alt+d)을 클릭하면 선례추적과 종속 추적이 있는데 항목별로 선택해보면 값들의 의존관계를 볼수 있다.

단축키 : shift + f7(선례), shift +f5(종속)


이미지 출처 :    http://www.telecom.tuc.gr/~ntsourak/demo_viterbi.htm