컴퓨터 전공을 공부하다보면 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로 주었고,상황 자체도 맞지 않습니다. 단순한 이해를 위한 목적으로 예를 들었으니 너그럽게 이해해주셨으면 합니다.



'Computer Science > Machine Learning' 카테고리의 다른 글

HMM (Hidden Markov Model)  (14) 2012.10.31
  1. 좋은글 2013.04.12 19:22 신고

    영문 hmm설명서보다가 여기와서 읽어보니 단번에 이해되네요ㅎㅎ

  2. 해리s 2013.05.28 00:59 신고

    HMM을 혹시 구현하셨나요? ㅎㅎ
    포스팅을 보니까 주로 자바를 이용해서 개발을 하시는데 혹시 매트랩도 사용하세요?

    • shine_ing 2013.05.28 09:44 신고

      네 HMM은 자바로 구현되어있습니다^^;
      매트랩은 사용해본적이 없어서요 ㅠㅠ

  3. Hoo 2013.07.10 17:43 신고

    위에 그림에서 보면 시작 -> 도서관,강의실,기숙사,화장실 이렇게 가는 확률이 각각 1/2, 0, 1/2, 0인데 이것을 어떻게 구하죠???

  4. 나도공돌 2013.11.06 16:33 신고

    웃긴 예시로 잘이해하거갑니다 여친 생기실거에요

  5. 공대녀 2014.04.09 15:31 신고

    The best ever 이해가 쉬운 글이었습니다 감사합니다~
    그런데 HMM학습법에 관해서도 포스팅해주시면 더 좋을것같네요 :)

  6. 김영욱 2014.09.25 14:15 신고

    정말 많은 도움이 되었습니다. 감사합니다^^

  7. 강지훈 2014.10.09 10:21 신고

    히든이 없으므로 hmm이 아닌 mm이라능..

  8. 이다운 2015.06.24 17:52 신고

    감사합니다.

  9. 공돌이 2015.10.12 16:49 신고

    포스트 내용 잘 봤습니다. 다름이 아니라 시작에서 도서관,강의실,기숙사,화장실 갈 확률이 어떻게 1/2, 0, 1/2, 0 이 되는데 어떻게 해서 저 값이 나오는지 궁금해서 댓글 남깁니다... 감사합니다!

  10. 잡상인 2016.05.26 22:03 신고

    재미있게 설명하셨네요^^
    잘읽었습니다. 감사합니다.

  11. 오뉴 2018.03.26 09:15 신고

    괜찮다면, 글 좀 퍼갈게요~

+ Recent posts