HMM((Hidden Markov model) (1)

안녕하세요.
제가 이번에 알려드리는 알고리즘은 패턴인식에서 많이 사용하는 HMM입니다.
HMM이란 확률에 따른 패턴의 일련을 모델링한 수학적 모델이며, 구축된 모델을 기반으로 다양한 시스템을
구축하는 기반 알고리즘을 제공합니다.
보다 자세한 사항은 사이트에서 확인 가능합니다.
HMM은 여러분야에서 사용합니다.
- on-line handwriting recognition
- speech recognition
- gesture recognition
- language modeling
- motion video tracking
- gene sequence allignment
- stock price prediction
게임에서 HMM의 활용방법에는 어떤것이 있을까요?
가장먼저 생각나는 것은 블랙엔화이트에서 마법을 사용할 때 입니다.
사용자가 마우스를 움직이면 시스템에서 어떤마법인지 인식하고 해당 마법을 사용하게 됩니다.

또하나의 예로는 음성인식에서인데요. 현재까지도 HMM에서 가장 많이 사용되는 분야가 음성인식분야입니다.
눈길을 끄는 게임은 슈팅게임 '파!'입니다. '파!'하고 외치면 총알이 나가 장애물을 처리하게 됩니다. 
뭐 공공장소에서 사용하기에는 다소 민망하겠군요.

아직 이해가 안된다구요? 그렇다면 하나더! 
HMM을 이해하기 위해 하나의 시나리오를 보도록 하겠습니다.
여자 친구의 삶
옛날에 같은 도시에 살았던 여자 친구와 이제는 멀리 떨어져 살고 있다.
그녀는 날씨에 따라 그날 할 일을 결정한다. 날씨는 크게 해와 비로 나누고, 하는 일은 산책, 쇼핑, 청소중의 하나이다.
그녀와는 매일 통화하는데 그날 한 일에 대해 이야기를 나눈다. 그녀가 한 일은 관측이 가능한 것이다.
하지만 날씨에 대해서는 말하지 않아 한 일을 가지고 추측하는 수밖에 없다. 날씨는 감추어져 있는 것이다.
기상대 정보 사이트를 뒤져 그녀가 사는 도시의 날씨 변화가 다음과 같다는 것을 알아내었다.

또한 기상대 자료를 추가로 조사하여 아래 정보도 알게 되었다.

옛날 같은 도시에 살았을 때 그녀를 면밀히 관측한 결과 날씨에 따른 그녀의 행동이 아래와 같다는 것을 알고 있다.

내가 가진 이런 정보를 이용하여 다음과 같은 질문에 대한 답을 구하고 싶다. 어떻게 하면 될까?
- 그녀가 일주일 연속으로 쇼핑만 할 확률은?
- 그끄저께 산책, 그저께 산책, 어제 청소했다는데 3일간 그곳 날씨는?
- 그끄저께 산책, 그저께 산책, 어제 청소했다는데 오늘과 내일 무얼할까?
Hooray! HMM을 사용하면 답을 구할 수 있다. 다음은 여자 친구의 삶을 모델링 한 HMM이다.

앞의 시나리오는 HMM의 핵심 아이디어를 이해하는데 결정적인 도움을 주었다고 생각됩니다.
그렇다면 이제 HMM을 어떻게 사용해야 할까요?
HMM의 사용
HMM을 실제 응용에 적용하기 위해서는 세 가지 문제를 풀어야 합니다. 이들 문제에 대한 자세한 사항은 [5]를 참고하시면 됩니다.
a) Evaluation(평가)
주어진 관찰 상태의 변화(sequence)를 가져올 확률값을 구하는 것이다. 또는 구성된 여러 개의 HMM 모델 중에서 주어진 관찰 상태의 변화를 가장 잘 표현하는 HMM 모델들을 선택할 수 있는 문제이다. 이를 위해 사용되는 알고리즘이 Forward 알고리즘이다. 위의 여자 친구의 삶에서 아래와 같은 질문이 평가 문제에 해당된다.
"여자친구가 오늘 산책, 내일 산책, 모레 청소, 글피 쇼핑할 확률은 얼마인가?"
b) Decoding(디코딩)
주어진 관찰 상태들의 패턴(Sequence)이 주어질 때, 합당한(그에 대응한) Hidden Pattern의 Sequence를 찾는 문제이다. 가장 많이 활용되는 방안이며, 이 방법을 알고리즘화 한 것이 Viterbi 알고리즘이다. 대표적인 활용은 자연어처리에서 형태소분석할 때 이용된다. 위의 여자 친구의 삶에서 아래와 같은 질문이 디코딩 문제에 해당된다.
"여자친구가 나흘간 산책, 산책, 청소, 쇼핑하였는데 그 나흘의 날씨를 추정해 보면?"
c) Learning(학습)
주어진 데이터로부터 HMM을 구성하는 것이다. 가장 어려운 작업이며, Learning의 결과를 Evaluation을 해서 검증을 한다.
-----------------------------------------------------------------------------------------------------------------
고생하셨습니다. 이렇게 간략하게(?) HMM에 대해서 알아봤습니다.
다음에는 위에서 말한 Forward 알고리즘과 Viterbi 알고리즘에 대해 알아보겠습니다.
감사합니다.
Reference
[1]http://semix2.tistory.com/404
[2]http://isnl.kaist.ac.kr/predictus/blog/?p=74
[3]http://blog.daum.net/_blog/BlogTypeView.do?blogid=09dDw&articleno=15669927
[4]http://shineware.tistory.com/entry/HMM-Hidden-Markov-Model
[5]패턴인식-오일석(7장 순차 데이터 인식) p209~p249 (http://ryan0802.tistory.com/100)