Legacy/Machine Learning

HMM (Hidden Markov Model)

shine_ing 2012. 10. 31. 12:01

컴퓨터 전공을 공부하다보면 HMM이라는 말을 자주 접하게 된다.


특히 자연어처리, 패턴인식과 같은 분야에서는 HMM에 대해서 수백번은 들어보게 된다.


HMM은 위키피디아에 보면 정리가 잘 되어있다. (위키피디아 - HMM)


물론 한글로 정리를 잘 해놓으신 분도 계신다. (난다로 님의 블로그)


HMM을 언제 써야하는지 왜 써야하는지는 위에 링크들을 참조하면 큰 도움을 얻을 수 있을 것이다.


필자는 블로그에서 상세히 설명 하고자 하는 것은 아니기 때문에(물론 할 능력도 안되지만..)


단순한 예를 들어서 HMM에 대한 핵심만 정리하도록 하자.


이전 사건에서 현재 사건이 올 수 있는 확률과, 현재 사건 자체가 일어날 확률을 연속적으로 계산하면 된다.


실질적인 예를 들어보자.


공대 사람이 오늘 하루를 돌아다니다가 여자친구를 사귈 수 있는 최적의 장소를 물색해보자


여자친구를 사귀는 중요한 요인이 공대 사람의 행동이라고 가정하자.


공대 사람이 할 수 있는 행동은 "먹기, 놀기, 공부하기, 수면"만 있다고 하자.


과거의 여자친구를 사귄 공대 사람들의 행동과 그 행동을 취한 장소를 살펴보니 다음과 같았다. 


여자친구 있는 공대생 1


도서관    공부

도서관    수면

강의실    놀기

기숙사    먹기

화장실    놀기

기숙사    수면


여자친구 있는 공대생 2


기숙사    수면

강의실    공부

도서관    공부

강의실    수면

화장실    놀기

도서관    놀기

기숙사    수면


오늘도 슬픈 싱글 공대생은 지친 몸을 이끌고 자고->먹고->공부 하려고한다.


이 때 연속된 이 행동을 각각 어떤 장소에서 취해야지 여자친구가 생길 수 있을까?!


HMM으로 학습을 한 후 결과를 보니 도서관->기숙사->강의실 이였다.


어떻게 이러한 결과가 나왔는지 계산해보자.


먼저 주어진 데이터( 여자친구 있는 공대생들의 행동 및 거취 )를 토대로


슬픈 싱글 공대생이 행동할 수 있는 최적의 장소를 구해내야한다.


구하기 위해서는 아래 그림 중에서 가장 높은 값을 갖는 경로 하나를 선택하면 된다.


즉, 아래 그림을 다 계산하면된다. (사실은 다 계산하지 않아도 된다. 자세한 내용은 계속 읽다보면.. )






그러면 끝난다........음 쉽다.........머리는 좀 터질것 같지만 분명히 쉬운게야..


이제 한 스텝씩 해보자.


기본적인 규칙은 이전 장소에서 현재 장소로 올 확률과 현재 장소에서 행동이 일어날 확률을 곱하는 것이다.


먼저 "자고" 파트부터 살펴보자.


시작에서 각각 도서관, 강의실, 기숙사, 화장실로 갈 확률을 구한다. (붉은글씨)


그리고 도서관, 강의실, 기숙사, 화장실에서 각각 잘 확률을 구한다. (파란글씨)


그리고 두 가지 확률을 곱한다. (녹색글씨)






누적확률에 이어서 다음 행동인 먹고를 계산한다.


먹고에서 먼저 도서관부터 계산해보자.


도서관을 계산할 때 아까 자고에서 계산한 누적 확률과 각각의 이전 장소에서 현재 장소인 도서관으로 올 확률을 곱하여 그 중 최대값만 선택한다.


말로하면 어려우니 그림을 보면 쉽게 이해가 된다.






위 그림에서는 이전 누적확률인 1/8과 도서관에서 도서관으로 갈 확률인 1/4를 곱한 값 1/32가 가장 큰 값이다.


구해진 가장 큰 값 1/32와 도서관에서 먹을 확률인 0/4를 곱하면 먹고에서 도서관에 대한 계산은 끝난다.


이런식으로 하여 가장 최대값을 갖는 그래프만 남겨둔 결과는 아래 그림과 같이 된다.


0인 결과는 더 이상 계산하지 않겠다. ( 그림 그리기의 압박.... )






위 그림에서 가장 우측에 계산된 값이 새로운 누적 확률이 된다. 


그럼 이 누적 확률을 갖고 다시 마지막 행동인 공부하기를 계산해보자.


아놔..계산해보니 전부다 0이다. 망했다. 뭘해도 여친은 안생긴다....


사실 확률값을 누적해서 곱하는 알고리즘의 경우에는 대부분 확률값을 0으로 주지 않는다.


그렇기 때문에 여기서는 일단 0을 1/100으로 주고 다시 계산해보자. ( 실제로는 MLE와 같은 방법을 이용하여 0을 대체한다. 이와 관련된 방법은 상당히 매우 무궁무진하기 때문에 생략.... )


최종 결과를 보면 아래 그림과 같다. 





최종적으로 갖게되는 최대값은 0.000855078125 이다.


이 최대값으로부터 지금까지 밟아왔던 곳을 거꾸로 되돌아 가면 가장 최적의 경로가 구해지는 것이다.


지금 계산한 방법이 비터비 알고리즘이다.


초반에 얘기 했듯이 모든 경우의 수를 다 계산하지 않았다. 


이 정도만 대략적으로 살펴본다면 도서관에서 자고 기숙사에서 먹고 강의실에서 공부를 하면 여자친구가 그나마...아주 그나마..생길수도 있다는 기대를 해볼 수 있다.


위의 예를 들어 HMM을 이해하는데 큰 무리는 없을 것이다.


사실 HMM은 형태소 분석기의 품사태거에서 주로 쓰인다. 이전 품사가 현재 품사에 영향을 주기 때문에 HMM이 지향하는 바와 매우 흡사하다.


===================================================================================================


위의 예에서는 확률값 0도 대충 0.01로 주었고,상황 자체도 맞지 않습니다. 단순한 이해를 위한 목적으로 예를 들었으니 너그럽게 이해해주셨으면 합니다.