Machine Learning

난다로~ 2008. 4. 6. 10:46

[출처] KISS ILVB Tutorial(한국정보과학회) 에서 발표( Dr. Sung-Jung Cho)된 내용 중 발췌

 

NLP 관련 응용 프로그램 중에서 가끔 Markov Model을 사용할 필요가 있는데, 이에 대해서 아주 잘 요약된 pt가 있어서 주석(?)을  달았다.

 

1. 문제의 종류 - 날씨 예측

 

  1) 날씨(state) = { sunny, cloudy, rain }

  2) 관측 데이터

 

  3) 가정 : 오늘 날씨(current state)는 어제 날씨(previous state)에만 영향을 받는다(dependent)  ==> Markov Assumption

 

  4) 이 문제를 시각적으로 표현하면

 

     -  각각의 상태에서 나가는 화살표(outgoing edge) 확률의 합은 1 이다.

 

2. 문제의 모델링 및 해결

 

  자 이제 위와 같이 관측 데이터(observation - 과거 데이터)을 가지고 있는 상태에서,  우리는 아래와 같은 문제를 실제 풀려고 한다.

  문제)  sunny  --> sunny --> cloudy --> rain --> sunny --> ? 

  물음표에는 어떤 날씨가 될 확률이 가장 높을까?

 

  이 문제를 모델링하면 아래와 같은 그림으로 표현할 수 있다.

 

 

  

 

   위의 3번째 줄에서 보면,  우리가 알고자 하는 것은 조건부 확률(conditional probability) 즉,  T=t  ( 현재 상태 )에서의 어떤 상태의 조건부 확률임을 알 수 있다.

   그런데, 이 조건부 확률은 first-order Morkov Assumption에 의해서 바로 이전 상태에 대한 조건부 확률만 계산하면 되는 것으로 축약된다.

 

   음.... 이건 너무 단순하잖아?   그렇다. 사실 오늘 날씨가 어떨지 계산하는 문제는 그냥 단순히 Morkov Assumption을 사용해서 계산하면 간단하다.

   하지만 우리가 실제로 풀려고 하는 문제는 이것이 아니라, 좀더 복잡한 문제이다.

 

   문제)  오늘 날씨가 sunny 인 경우,  다음 7일의 날씨 변화가(state sequence)가 'sunny-sunny-rain-rain-sunny-cloudy-sunny' 일 확률은?

 

   에구. 사실 우리는 과거를 통해서 미래를 예측하길 원하는 거지, 단순히 오늘만을 알려고 하는 것은 아니다.

 

   그렇다면, 이 문제의 답을 구하기 위해서 필요한 것은 무엇일까?  sequence probability를 계산하는 공식이다.

 

 

  이 수식을 이용해서 다시 한번 문제를 표현하면 아래와 같다.

 

  S1 =  rain  ,   S2 = cloudy  ,   S3 = sunny  인 경우

 

  엥? 근데  condition으로 있는 model 은 무엇이지?  가끔 확률 공식을 보면 이런식으로 수식을 계산하는데 배경으로 깔려있는 조건 전체를 지정하기도

  한다. 이는  관측 데이터에 따른 state transition probability ,  first-order Morkov Assumption 등등을 통칭하는 의미라고 할 수 있다.

 

  자~  이제 계산을 할 수 있다.      

 

  여기서 잠깐,  그런데 정말로 우리가 풀려고 하는 문제가 이것인가?  생각해 볼 필요가 있다.  다음 7일 동안의 날씨 변화(state sequence)를 아는 것은

  좋은데,  우리가 진짜로 알고 싶은 것은 바로 일주일 이후 바로 그날의 날씨가 아닌가?  예를 들어, 8일째 데이트를 하려고 하는데 날씨가 어떤가?

  알고 싶을 것이다.

 

  이 문제를 풀기 위해서 또 다시 문제를 모델링하면 아래 그림과 같이 표현될 수 있다.

 

 

    위 수식을 이용하면  8일째 맑을 확률을 알 수 있을 것이다. ㅎㅎ

 

    그런데, 왜 시간 T=t에서 상태 i인 모든 path( state sequence)의 확률을 전부 더한게 T=t 에서 날씨(state)가 i 일 확률일까?

 

    간단히 생각하면,  P(A OR B) = P(A) + P(B)  이기 때문이다. ^^

 

 

3.  계산의 최적화

 

  그런데 위의 수식을 가만히 보면, state sequence가 길어지면 질수록, state가 많아지면 많아 질수록 느려짐을 알 수 있다.

 

  전문용어(?)로 말하면 exponential time complexity가 있다고 하는데

 

  그냥 사용하기 느리다는 거다.

 

  이 문제는 또 어떻게 해결해야 할까? (  사실 Morkov Model과는 다른 문제다. 최적화 문제 )

 

  우리의 연구자들은 이미 해결책을 찾아두셨다. ㅋㅋ 

 

  Dynamic Programming 기법을 사용하는 것인데, 이미 한번 계산한 확률은 다시 계산하지 않고 그대로 재활용하자는 개념이다.

 

  (DP 기법은 프로그램으로 나타내면 거의 recursive callcuation이다. 고등학교때 배운 수학적 귀납법 공식을 떠올리면 쉽게 이해가 갈 것이다)

 

  이를 수식으로 정리하면 아래와 같다.

 

    자~~  이제 위의 간단해진 수식을 사용하면 좀더 빨리 계산할 수 있겠다. 

 

    여기서 aji는 상태 j에서 상태 i로의 전이 확률(transition probability)이다. 즉, 모델의 prior probability 이다.

 

    prior는 확률이론에서 아주 자주 나오는데, 그냥 우리가 이미 알고있는 사실을 기반으로 어떤 확률을 계산할 때, 그 알고있는 사실에 대해서 표현하는 단어이다.

 

    배경지식이랄까?  '동전던지기에서 앞면이 나올 확률은 0.5 이다'라는 것도 경험을 통해 얻어진 prior 라고 할 수 있다.

 

    음... 그러면  아주 재미있는 문제를 생각해 볼 수도 있겠다. 

 

    문제) 

             앞면이 나오고 앞면이 나올 확률이 0.6 ,  뒷면이 나올 확률이 0.4

             뒷면이 나오고 뒷면이 나올 확률이 0.3,   앞면이 나올 확률이 0.7 인

             조금 기형적인 동전이 있다고 하자.

             여기서 상태는 { 앞면, 뒷면 }

             이때, 앞으로 3번 더 던졌을 때, 그 결과가 앞면이면 내가 이길 것 같다. 그럼 그 확률은?

             (단, 처음 동전을 던졌을 때, 앞면과 뒷면이 나올 확률은 같다)

             이 확률을 Morkove Model를 이용해서 계산해 보자.

 

    답)  P(q3 = 앞면) =  P(q2 = 앞면) * P(앞면|앞면) +  P(q2 = 뒷면) * P(앞면|뒷면)

          P(q1=앞면) = 0.5

          P(q1=뒷면) = 0.5

          P(q2 = 앞면) = P(q1 = 앞면) * P(앞면|앞면) +  P(q1 = 뒷면) * P(앞면|뒷면)

                            = 0.5 * 0.6 + 0.5 * 0.7 = 0.3 + 0.35 = 0.65

          P(q2 = 뒷면) = P(q1 = 뒷면) * P(뒷면|뒷면) +  P(q1 = 앞면) * P(뒷면|앞면)

                             = 0.5 * 0.3 + 0.5 * 0.4 =  0.15 + 0.2 = 0.35

          P(q3 = 앞면) = 0.65 * 0.6 + 0.35 * 0.7 = 0.39 + 0.245 = 0.635

 

          오옷!  확률이 0.635나 되넹~~ ㅋㅋ  당근 걸어야쥐~~

 

 

4. 결론

 

 Morkov Model에 대해서 이해하는 데 있어, 핵심은 바로

 

"우리는 과거를 통해서 미래를 알고 싶다" 일 것이다.

 

 그리고 가끔 Hidden Morkov Model과 헷갈리는 응용이 있는데, 이를 구분하는 방법은 미래 상태(state)를 관측할 수 있는가에 달려있다.

 

예를 들어, part-of-speech tagging 에서는 상태가 바로 품사(POS)이다.  그런데 우리는 아래와 같은 문제에서 품사는 관측 못하고 품사에서

 

생성된(generated) 형태소만을 알 수 있다.

 

문제) '나는 학교에 간다' 라는 문장을 태깅하시오.

 

그래서 HMM에서는 emition probability 혹은 generation probability 라는 개념이 추가적으로 들어간다.

 

5. 마지막으로, Markov Model을 가지고 응용할 수 있는 문제들은 어떤게 있을까?

 

음...  예를 들자면, 전국민의 놀이 로또(lotto)가 있을 수 있겠다.

 

로또의 경우는

 

관측 가능한 상태 = { 1, 2, ....., 45 }

 

초기 prior 확률은 현재 297회까지 진행되었으니, 이를 통해서 구할 수 있을 것이다.

 

따라서, 6개의 번호에 대해서 선택한 경우, 이 sequence의 확률을 계산할 수 있겠다.

  

45개에서 6개를 순서있게 선택하는 경우의 수를 45P6 인데, 이 모든 경우에 대해서 sequence probability를 구해서

 

가장 확률이 높은 순서열을 구한다면 어떨까?

 

요새 웹에 떠돌아 다니는 로또 번호 자동 생성기는 아마도 이걸 응용한 프로그램이라고 생각된다. 혹시 다른 방법을

 

사용했을 수도... ㅋㅋ

 

관심있는 분은 만들어 보시길~~ ^^

 

아 참고로, 유전자 알고리즘(genetic algorithm)을 이용해서 로또 생성기를 만드는 경우도 있을 겁니다.

 

짧게 설명하면, 유전자 알고리즘은 아래 그림(참조 URL)과 같이 설명될 수 있는데,

 

 

 

   여기서 population 부분은 feature vector로 일종의 유전 형질이라고 할 수 있다. 좋은 유전 인자는 계속 유전되고, 그렇지 않은 열성 인자는 자연 도태된다.

   세대를 거치면 거칠 수록 말이다. selection, cross-over, mutation 등의 기본 연산은 자연의 유전 법칙을 시뮬레이션 한 것이라 할 수 있다.

 

   로또의 경우는 279회차 까지의 당첨 번호를 가지고  길이가 45인 279개의 feature vector를 만들어 낼 수도 있을 것이다.

   해당 회차에 당첨된 번호는 우성 번호이고, 그렇지 않은 번호는 열성 번호로....

 

   이를 이용해서 유전자 알고리즘을 수행하고 몇 세대 이후 남아있는 feature vector를 decoding해서 적절하게 원하는 번호를 선택하는 방법입니다.

 

   이 방법과 Markov Model을 결합해서 hybird로 만들어 볼 수도 있겠군요. ㅋㅋ

 

   물론, 학술적인 연구와는 거리가 있고 그냥 단순히 '재미로'겠지만 말입니다. ^^

 

 

 

음성인식을 공부하고 있는데 많은 도움이 됐습니다.
감사합니다. ^^
스크랩 부탁드립니다. MM에 대해서 설명이 너무 잘 되어 있어서 훔쳐 갑니다. ^^
타겟주소는 http://loadgun.tistory.com/235 입니다. ^^
넹~~
P(q2 = 뒷면) = P(q1 = 뒷면) * P(뒷면|앞면) +P(q1 = 앞면) * P(뒷면|앞면)
= 0.5 * 0.4 + 0.5 * 0.6 = 0.2 + 0.3 = 0.5

P(q3 = 앞면) = 0.65 * 0.6 + 0.5 * 0.7 = 0.39 + 0.35 = 0.74

이부분 계산에 약간 실수가 있네요.

P(q2 = 뒷면) = 0.5 * 0.4 + 0.5 * 0.3 = 0.2 + 0.15 = 0.35 가 되구요.

최종 확률은
P(q3 = 앞면) = 0.65 * 0.6 + 0.35 * 0.7 = 0.635 입니다.
오옷~ 그렇네요 ^^; 감사감사 ^^
모래알님을 여기서 뵙게 되네요..^^;;;;
좋은 포스팅 잘 보고 갑니다. 퍼 갈께요^^
많은 도움 됐습니다. 감사합니다~~^^
별말씀을 ^^
많은 도움됐습니다. 감사합니다.
^^
많은 도움이 되었어요, 스크랩 해도 될까요?
넵~~
좋은 자료 감사합니다~
잘봤습니다. 감사히 담아갈게요.^^
정말 알기쉽게 쓰여져있네요! 진짜 도움 됬어요 ㅎㅎ 감사합니다~!
좋은 글 감사합니다
너무 정리를 잘해주셨네요~ 정말 유용했습니다. 가벼운 질문인데.. 말씀하신 로또예제는 markov assumption을 적용하기 애매하지 않나요~? 이전 회차의 당첨번호가 다음회차의 당첨번호에 영향을 준다고 보기 어려우니까요..^^