비터비(viterbi) 알고리즘

 

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

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

 

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

 

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://en.wikipedia.org/wiki/Viterbi_algorithm

매일 무슨 일을 했는지 전화로 알려주는 친구가 한명 있다고 가정합니다.
당신의 친구는 오직 3가지 활동에만 관심이 있습니다.
공원에 산택(walk), 쇼핑(shopping), 그리고 그의 아파트 청소(clean)
선택의 날씨에 따라서 독립적으로 결정합니다.
당신은 당신의 친구가 사는 곳의 날씨에 대한 명확한 정보를 알수 없습니다.
그러나 당신은 일반적인 경향을 알수 있습니다.
당신의 친구가 당신에게 매일매일 하는것에 이야기하는것에 기초하여 날씨가 어떤지를 추축할수 있습니다.
날씨는 이산 마코프 체인에 따라서 결정되어 진
다고 당신은 생각합니다.
날씨는 비(Rainy), 맑은(suny)의 두가지 경우만 있습니다.
그러나 당신은 날씨를 직접 관찰할수는 없습니다.
그 정보는 당신에게 숨겨져 있습니다.
날씨에 따라서 당신의 친구는 공원을 산책하거나, 쇼핑을 하거나 아파트를 청소합니다.
그리고 당신의 친구는 당신에게 자신의 행동에 대해서 이야기 해줍니다.
전체 시스템은 HMM에 의해 동작합니다.

그지역의 날씨변화에 대한 패턴을 알고 있고 친구가 평균적으로 무엇을 했는지를 알고 있습니다.
다른 말로 하면 HMM의 파라미터는 알려져 있고 당신은 아래쪽 Python programming language에 있는것과 같이 프로그래을 작성할수 있습니다.

 

 

 

viterbi.py

0.0MB

비터비.sxc

0.01MB

viterbi.c

0.0MB