nlogn's log :: 천천히 달리기

 배신과 협력의 게임(1라운드의 죄수의 딜레마)

물주(게임 진행자) 한 명과 두 사람이 게임을 한다. 게임을 하는 두 사람의 손에는 '협력'과 '배신'의 카드 2장이 있으며 단 1라운드만 진행이 된다. 카드의 조합은 아래 표의 네 가지가 되며, 각각의 경우에서 이득과 손해는 아래와 같다.

가령 위의 예에서 상호 협력의 카드를 제출할 때는 상호 협력에 대한 보상으로 물주로부터 300달러를 받는 것이다. 이 때 배신에 대한 유혹료는 상호 협력의 보수보다 높아야 하고, 상호 협력의 보수는 상호 배신의 벌금보다는 좋아야 한다. 이 밖에 여러 가지 설정이 있지만 생략한다.

그럼 왜 '딜레마'일까? 누구든 낼 수 있는 카드는 '협력'과 '배신'이라는 카드 2장 밖에 없다. 만일 A가 '배신'을 냈다면 B는 최선의 카드로 '배신'을 내야 할 것이다. 만일 '협력'의 카드를 낸다면 B는 100 달러를 게임 진행자에게 줘야 한다. A가 '협력'의 카드를 냈을 경우에도 당신이 얻을 수 있는 최대의 이득은 '배신'의 카드를 내는 것이고 그 때 유혹료로 500달러를 얻을 것이다.

결론은 타인이 어느 카드를 내든 상관없이 당신의 최선 행동은 '항상' 배신이라는 것이다. 그러므로 두 사람의 이성적인 경기자가 만나면 모두 배신하여 같이 벌금 또는 운 좋으면 유혹료를 받게 될 것으로 끝난다. 두 사람 모두 만일 쌍방이 '협력'만을 낸다면 상호 협력으로 비교적 높은 보수를 받을 것을 확실히 알고 있다. 하지만 '배신'의 카드를 내는 것이 최선의 행동이라는 것이다. 쌍방이 서로 연락하거나 정보를 주고 받을 수 있다면, 서로 연락해서 '협력'의 카드를 제출하겠지만, 그렇지 않을 경우에는 '배신'을 하는 것이 합리적인 게임 진행이 될 것이다. 그러니 딜레마인 것이다.

딜레마 (dilemma) ①(논리학) ＝양도 논법(兩刀論法). 
②선택해야 하는 길은 2개뿐인데 그 어느 쪽도 바람직하지 못한 결과를 초래하는 상황.

 반복 죄수의 딜레마

'죄수'란 하나의 특별한 상징적인 예에서 유래한다. 이 경우는 돈이 아닌 죄수의 형기이다. 가령 A군과 B군이 자신들이 저지른 범죄 때문에 공범 혐의로 투옥되어 있다. 그 죄수들은 각각 독방 속에서 공범자에 대한 불리한 증언을 함으로써 동료를 배신하도록 유혹당했다. 처분은 두 사람의 죄수가 어떻게 하는가에 따라 결정되며, 어느 쪽도 상대가 어떻게 했는지 모른다. 만일 각각이 배신하면 양자 모두 죄가 인정되나 증거를 제공한 점으로 약간의 신용을 얻어 어느 정도 경감된 형기, 즉 상호 배신의 벌을 받게 된다. 만일 양자가 협력하여 증언을 거부하면 유죄가 될 충분한 증거가 없으므로 보다 경미한 죄로 짧은 형기, 즉 상호 협력의 보수를 받는다. '지불'이 돈이 아니라 형기였지만 이 게임을 기본적 특징이 보전되어 있는 것을 느낄 것이다.

1라운드의 게임에서는 상호 배신으로 끝나게 될 운명이 되고 만다. 그러나 그것이 '반복'된다면 그 때에도 '배신'을 할 것인지 생각해보자. 반복 게임은 동일한 경기자에 의해 제한없이 반복되어 행해질 뿐만 아니라 또한 두 사람은 서로 바라보고 있으며 그 사이에는 게임 진행자(판사)가 앉아 있다. 두 사람은 두 카드의 어느 한쪽을 냄으로써 승부를 내고 게임 진행자(판사)는 먼저 제시한 규칙에 따라 형기를 결정한다. 이제는 1 라운드의 게임으로 끝나는 대신에 우리는 또 다시 카드를 집어서 다음의 승부에 대비한다. ( 이와 같은 반복은 두 사람이 반복적으로 공범자로 잡힌다고 가정하면 간단히 설명된다. 단 서로의 연락은 되지 않는다.) 몇 번 승부를 계속하는 사이에 두 사람에게는 신용, 또는 불신이 쌓여 협력 또는 배신을 할 수 있는 기회가 주어진다. 제한없이 긴 게임에서 중요한 점은 서로가 손해를 볼 것 없이 쌍방이 협력의 보수를 받을 수가 있다는 것이다.

 전략

과연 위와 같은 게임을 할 경우 어떤 전략을 가진 자가 장기적으로 승리를 거둘 수 있을 것인가를 생각해보자. 몇 개의 교묘한 전략이 가능하나 승리를 거든 전략은 놀랍게도 가장 단순하고 표현적으로는 모든 것 중에서 가장 교묘함이 부족했다. 그것은 '당하면 갚는다(tit for tat)'라는 전략으로 불렸고 최초의 카드는 협력으로 시작하고 그 이후는 단순히 바로 전에 상대가 낸 카드를 흉내내는 것뿐이다. 즉, 상대가 배신을 하면 내가 배신을 하는 것이다.

다음은 '소박한 시험꾼(naive prober)'으로 '당하면 갚는다'와 같으나 10회중에 1회는 함부로 이유없이 배신하여 유혹료로서 높은 득점을 기대하는 전략이다. 그리고 '원한파'는 한번 상대방이 배신하면 끝까지 배신하는 전략이고, '항상 배신은 항상 배신만 하는 전략이다. 그 밖에 수많은 전략들이 생겨날 수 있어 이 게임의 다양성은 증가된다.

다음은 대표적 전략들을 간략히 설명한 표이다.

이러한 게임을 '액셀로드'라는 사람이 전략을 하나의 공통 프로그램 언어로 번역하여 대형 컴퓨터로 서로 대전시켰다. 각각의 전략은 다른 모든 전략과 순차적으로 짝지어져서 반복 죄수의 딜레마 게임을 하는 것이다.

액셀로드가 인정하고 있는 가장 중요한 범주는 '마음씨 좋은(nice)'이다. 마음씨 좋은 전략은 최초로 배신하는 일이 결코 없는 것으로 정의된다. '당하면 갚는다 (tit for tat)' 가 그 일례이다. 소박한 시험꾼은 때때로 배신을 하므로 간악한 전략이다. 토너먼트에 참가한 15개의 전략 중 득점이 높은 쪽부터 상위 8위까지 모두 8개의 '마음씨 좋은(nice)' 전략이 차지하고 있다는 사실이 의미 깊다고 할 수 있다.

 관용

전략이란 것은 보복하는 일은 있으나 단기의 기억밖에 없다. 그것은 오래된 나쁜 일을 바로 잊어버린다. '당하면 갚는다(tit for tat)'는 하나의 관용 전략이다. 배신자에 대해 즉시 한 때 보복으로 갚고 그 후에는 과거를 씻듯이 잊는다. 하지만 원한파는 절대로 용서하지 않는다. 그 기억은 게임의 전기간을 통해 지속된다. 한 번이라도 자기에게 배신한 적이 있는 상대에 대한 원한을 결코 잊지 않는다. 원한파와 같은 전략이 프리드만(friedman)이라는 호칭으로 대전이 되었지만 게임 성적이 별로 좋지 않다.

우리는 승리하는 전략에 두 가지 특징이 있다는 것을 상정할 수 있다. 즉 '마음씨 좋기'와 관용함이다. 다시 말해, 처음부터 배신하지 않는 전략과 단기의 기억밖에 없는 관용 전략이 그것이다. 거의 유토피아적인 경향의 이 결론은 '마음씨 좋은 사람이 성공한다' 라는 문구와 비슷한 의미를 담고 있다. 윤리가 논리로써 이끌어지는 순간이다.

위와 같은 전략은 평균적이고 반복적인 전략끼리의 대전이며, 여기가 중요한 사실은 그러한 전략의 성공은 어떤 전략이 서로 대전하는가에 달려 있다라는 것이다. 다시 말해 다른 모든 전략이 '항상 배신'이면 '마음씨 좋은' 전략이 당하기만 한다. 그러므로 '최초 구성이 어떤 전략으로 구성되었는가' 라는 요소와 전략들의 구성 비율도 각각의 전략에 대한 성공, 실패에 대한 영향을 미친다.

 ESS(Evolutionarily stable strategy, ESS)

위에서 언급한 것처럼 각 전략의 순위는 어떤 전략이 제출되었는가에 의존한다. 가령 대부분의 전략이 간악한 것이었다면 '당하는 갚는다'는 이기지 못 했을 것이다. 바꾸어 말하면 전략의 순위가 인간의 불안정하고 자의적인 것에 의존하고 있다. ( 인간이 어떤 전략을 대전시키느냐에 따라 전략의 순위가 결정될 수 있다.) 이 자의성을 어떻게 하면 줄일 수 있을 것인가? 그것은 ESS로 해결될 수 있다. ESS라는 메이나드-스미스가 제창하고 있는 중요한 개념은 '진화적으로 안정된 전략'이라는 불리는 것이며, 여기서 전략이라는 것은 미리 프로그램되어 있는 행동 방침이다. 쉽게 말하면, 정확치는 않지만 각각의 전략을 이루는 제 1세대를 만들고, 유전자 알고리즘으로 세대를 거쳐가면서 최종적으로 살아남는 전략들이 ESS가 될 수 있다.

액셀로드는 63개의 전략을 취하여 그것을 또 다시 컴퓨터에 입력해서 그것들을 제 1세대로 만들었다. 따라서 제 1세대의 풍토는 63개의 모두의 전략을 균등히 대표하는 것으로 되어 있었다. 제 1세대의 끝에 각 전략의 승자는 돈이나 득점이 아닌 그의 부모와 동일한 전략을 취하는 후손의 수로 지불된다. 세대가 진행함에 따라 어떤 전략은 수가 적어져서 최종적으로는 절멸한다. 다른 전략은 점점 수가 많아진다. 따라서 그 비율이 변함에 따라 전략들의 대전이 일어나는 풍토(전략들의 구성 비율)도 변한 것이다. 대전의 결과는 몇 개의 전략은 최초부터 절멸로 향하고 대부분은 200세대에 가서야 절멸한다. 재미난 사실은 해링턴(Harrington)이라 불리는 간악한 전략은 최초의 150세대쯤 급격하게 상승했다. 그것은 '두 발에 한발 갚기' 등의 연약한 상대가 주위에 있는 한은 그들을 착취했다. 그 후 연약한 상대가 절멸 당하게 되면 '해링턴(Harrington)'은 그들만의 포획물이 없게 되어 그들의 뒤를 쫓아 절멸하게 됐다. 싸움터는 '당하면 갚는다'처럼 마음씨 좋은 전략의 독무대로 됐다.

진화가 거듭되어 모든 간악한 전략이 절멸에 임박하게 되면 아무리 마음씨 좋은 다른(두 발에 한발 갚기) 전략도 '당하면 갚는다(tit for tat)'와 서로 상호간에 구별하는 방법이 없어지게 된다. 왜냐하면 그것들은 모두 마음씨가 좋기 때문에 서로 협력의 카드를 내놓기 때문이다. 이런 최종적인 전략들의 구성은 ESS와 닮았지만 엄밀하게는 ESS가 아니라는 것이다. 어떤 전략이 ESS가 되려면, 그것이 희소한 돌연변이의 전략에 변경되어서는 안 된다는 것을 생각해 주기 바란다.

프로그램적인 ESS는 마음씨 좋은 전략이 우세를 점하지만, 거의 무조건인 마음씨 좋은 전략( 두발에 한발 갚기, 세발에 한발 갚기 등) 이 숨어 있게 되어, 간악한 전략의 침입에 쉽게 변할 수 있기 때문에 액설로드는 다음과 같은 결론을 내린다.

"아마도 조금 간악한 전략과 마음씨 좋은 매우 관용한 전략과 
그리고 당하면 갚는다(tit for tat)와의 전략들의 혼합으로 ESS가 구성된다"

그런 전략들이 구성된 ESS는 어떤 다른 전략이 들어와도 ESS가 쉽게 변하지 않음을 알 수 있다. 다시 말해 전략들의 진화가 안정화되었다고 볼 수 있다. 최종적인 진화 상태임을 암시한다.

이것이 인간 생활에 흔한 양상을 반영하는 거울임을 알 수 있다. 즉, 어느 정도의 간악한 사람과 '당하면 갚는다(tit for tat)'와 같은 전략을 가진 사람들이 이 세상에 우세한 이유도 죄수의 딜레마라는 게임에서 유추할 수 있다.여기서 제 나름대로의 재미난 결론은 가장 이상적인 전략은 '당하면 갚는다(tit for tat)'이라는 전략이다. 한번 상대방이 배신을 하면 바로 배신을 하는 전략이 우리의 인생을 최소의 실패율을 가져다 줄 수 있는 전략이라는 것이다. 두 번을 참아서도 안 된다. 오직 한번만이 참을 뿐이다. 대신 관용을 유지해야 한다. 상대방의 잘못은 단기 기억으로 잊어버린다. 이제부터는 이것을 내 인생 전략으로 삼을까 싶다. ㅋㅋㅋ

참고자료 : 이기적 유전자, 리처드 도킨스 지음, 홍영남 옮김, 을유 문화사, 89-324-6025-6

[출처] 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로 만들어 볼 수도 있겠군요. ㅋㅋ

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

[참고] http://www.seanborman.com/publications/EM_algorithm.pdf

  보통 Maximum Likelihood estimate 방법을 사용해서 관측된 데이터에 알맞은 모델의 변수(parameter)를 추정한다. "

  즉, 어떤 모델의 변수를 모르는 경우에 이를 추정하는 방법이라는 건데,

  초기에 랜덤하게 혹은 어떤 다른 방법으로 모델 변수를 설정한 상태에서, 관측데이터(X)가 이 모델(ramda_0)로부터 생성되었을 확률을

  계산한다.

  P(X | ramda_0 )

  이제 모델 내부의 변수를 아주 조금 수정한 새로운 모델을 ramda_1 이라고 하자.

  그리고 나서 다시 관측데이터의 posterior 확률을 구하면

  P(X | ramda_1 )

  자, 이제 어떤것이 더 큰지 결정한다.

  만약 P(X | ramda_1 ) 이 더 크다면, 우리는 ramda_1이 ramda_0 보다 더 관측데이터(X)가 나올법한 모델이라는 것을 알 수 있다.

  그 다음에는 어떻게 하는가?

  위 작업을 계속 반복하는 것이다. 이것이 iterative procedure

  그러면 언제 멈추는가?  새로운 모델 ramda에 대한

  P( X | ramda ) 가 기존 모델보다 부적합한 경우(likelihood가 더 작은 경우)에 멈추면 된다.

  음...

  좀더 진행하면 현재보다 더 좋은 모델이 나올 가능성은 있지만 말이다. 그래서 local maximum을 찾는 다고 하는 것이다.

  다시 본론으로 들어가서,  그러면 E-step, M-step은 무엇인가?

  확실한 예가 없어서 이해하기 힘들기는 하다.

  계속 살펴보도록 하자.

  ramda 대신에 theta를 쓰면,

  P( X | theta ) 는 관측데이터 X가 있을 경우, theta에 대한 likelihood 이며

  로그 함수를 씌우면

  L(theta) = ln P( X | theta )

  이것을 일반적인 log likelihood function 이라고 부른다.

  "우리가 원하는 것은  L(theta)를 최대로 하는 모델 theta를 찾자는 것이다."

  EM 알고리즘의 iterative procedure에서는

  L(theta_current_max) > L(theta_n)

  theta_current_max가 현재까지 가장 L 값이 큰 모델이라면, 위와 같은 조건이 만족되는 경우, 정지하면 된다.

  음... 현재까지는 hidden variable에 대해 고려하지 않고 수식을 전개했는데, 이를 포함시켜보자.

위 (10) 번 수식은 현재까지 언급되던 theta를 hidden variable Z , known variable theta 로 분리시킨 것이다.

( 이 수식 전개는 partition theory 를 참고하면 된다. )

이를 이용하면, 위 (9) 번 수식을 아래와 같이 쓸 수 있다.

  음... 대충 수식 관련 눈팅만 했다.

  이제부터는 E-step, M-step에 대해서 좀더 알아보자.  

  [참고] http://en.wikipedia.org/wiki/Expectation-maximization_algorithm

  위에서 기술한 바와 같이,

  P( X | theta ) 에서 theta는 hidden variable을 포함하고 있다.  따라서, 처음 시작은

  그냥 아는 변수는 그대로 하고, 모르는 변수에 대해서만 랜덤하게 값을 설정해준다.

  즉, 다시 theta를 hidden variable z 와  known variable theta 로 분리하면

  P( X | Z, theta )

  여기서, Z에 대해서만 랜덤으로 설정해 준다는 것이다.

  그리고 나면,

  current parameter estimate를 알고 있으니, 이를 이용해서 hidden variable에 대한 expectation 값을 계산할 수 있다.

  즉, Z에 대한 expected estimate를 계산할 수 있다.

  이게 먼 말인고?  

  간단히 얘기하면, Z=(z1, z2, z3)  theta=(t1, t2, t3, t4)

  이렇게 element가 있다고 하면

  우리는 theta 값을 알지만, Z 값을 모르니

  t1, t2, t3, t4, 초기에 설정된 z1, z2, z3 에 대해서 평균값으로

  z1, z2, z3를 다시 설정하겠다는 것이다.

  그림으로 표현해보면

 초기에 swallow, bug, insect 는 모르는 변수이고, 그래서 전부 0으로 설정하고

 나머지에 대해서만 관측되었다고 했을 때,

 Expectation 단계에서는 (아는 것 + 모르는 것) 전체에 대한 평균값을 계산해서

 모르는 값에 평균값을 설정하겠다는 의미이다.

 이 부분은 사실 Maximum Entropy Model과 아주 비슷하다.

 오캄의 면도칼(ocam's razer)이라는 건데, 여러가지 가설중에서 가장 간단한 가설이 진리일 확률이 높다는 얘기다.

 즉, 잘 모르면 그냥 평균값을 사용하라는 것.

 그렇다면, Maximization 단계는 멀 하는 걸까?

 여기서는 앞서 Expectation 단계에서 우리가 모르는 Z값에 대해 추정해 뒀기 때문에, ln P( X | Z, theta )  값을 새롭게

 계산할 수 있을 것이다.

 이렇게 계산된 ln P( X | Z, theta ) 값이 기존 likelihood 값보다 더 크다면, 이것이 더 관측데이터에 적합한 모델이므로

 해당 모델을 교체한다.

 아니면 반복 과정을 정지시키던가....

 혹은, likelihood 값의 변화량이 어떤 음수값보다 더 커지면 정지하는 방법도 있다.

 이것은 search space를 탐색하는 이론을 참조하면 될 것이다.

 다른 그림을 이용해서 살펴보면 아래와 같다.

 [참고] http://www.cs.jhu.edu/~jason/465/PowerPoint/lect26-em.ppt

 동전던지기에 대한 EM 예제는 다음 URL을 참고하면 된다.

 [참조] http://www.nature.com/nbt/journal/v26/n8/full/nbt1406.html

위의 2번 화살표 아래쪽에 있는 값들은 아래와 같이 계산되었다.

A를 던졌을 때, 
앞면이 나올 확률 0.6
뒷면이 나올 확률 0.4

P( HTTTHHTHTH )

= 0.6^5 * 0.4^5 = 0.07776 * 0.01024 = 0.0007962624

B를 던졌을 때, 
앞면이 나올 확률 0.5
뒷면이 나올 확률 0.5

P( HTTTHHTHTH )

= 0.5^5 * 0.5^5 = 0.03125 * 0.03125 = 0.0009765625

0.0007962624                             0.0007962624
---------------------------- = ---------------- = 0.4491489261009364207373215482251
0.0007962624 + 0.0009765625        0.0017728249

따라서,

A를 0.449회

B를 0.551회

던졌을 것이다.

A를 0.45, B를 0.55 회 던졌다고 계산되었는데, 실제 H는 5회, T는 5회 나왔다.

그렇다면, A에 대해서

0.45 * 5 H = 2.2 H

0.45 * 5 T = 2.2 T

B에 대해서

0.55 * 5 H = 2.8 H

0.55 * 5 T = 2.8 T

위 그림을 프로그램으로 구현한 결과 참조 http://blog.daum.net/comefeel/6935672 

(동료분이 구현해 주셨음 ㅋㅋ)

 to be continued...

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

얼마전에 Markov Model에 대해서 주석을 달아서 올렸는데, 이번에는 HMM에 대해서 알아보자

지난번 글에서 언급되었듯이 MM과 HMM의 차이점은 상태(state)를 관측할 수 있는가에 달려있다.

날씨나 동전던지기와 같은 사건(event)에서는 쉽게 상태를 알 수 있지만, 그렇지 않는 사건들도 존재한다.

예를 들어,  아래와 같은 문제가 있다고 하자.

이와 같이 3개의 통(상태 1,2,3  -> N = 3)에는 빨간색, 파란색, 녹색 공들이 6개(M = 6)가 들어있는데, 하나의 통에 들어있는 서로다른 색의 공들은 같은 숫자로

들어있지 않다.

이 그림에서 나오는 화살표는 Markov Model에서 처럼 한 상태에서 다른 상태로 전이할 확률(transition probability)이다.

그런데, 각각의 상태에 도착하면 그 상태에서는 빨간, 파란, 녹색 공중 하나를 어떤 확률에 기반해서 뱉어낸다고 한다. 약간 crazy한 콜라 자판기를 생각해도 된다.

3개의 자판기에 빨간, 파란, 녹색 콜라캔이 위의 그림처럼 들어있고, 동전을 넣으면 어떤 확률에 의해서 지맘대로 토해내는 그런 자판기 말이다~

이렇게 어떤 확률에 의해서 콜라를 뱉어내는 자판기는 아래와 같이 generation process로 모델링 할 수 있다.

위 그림에서 ouput process가 바로 어떤 상태 q에서 어떤 ball  x 를 뱉어낼 확률이며 이는 조건부 확률 f(x | q)로 나태낼 수 있다.

그리고  1, 2, 3번 상태에 대한 전이 확률을 알고 있기 때문에 이 부분은 Markov Model을 이용해서 모델링할 수 있을 것이다.

자 그럼 이제 우리는 각 상태로의 전이 확률과 각 상태에서의 생성 확률을 모델링했다.  그렇다면 아래와 같은 문제를 생각해 볼 수 있을 것이다.

출력된다는 것을 관측했다(observed)

이러한 정보로 부터, 우리가 알고 싶은 것은 '과연 감춰진 state sequence는 무엇인가?'일 것이다.

음....  약간 거꾸로 생각해서 만약에 '빨간, 파란, 녹색' 공들 그 자체가 state이고 그들간의 전이 확률을 계산한다면 굳이 근본적인 상태들의 sequence를 알 필요가

없을 수도 있다. 하지만, 우리는 다음에 나올 공에 관심이 있는 것이 아니라 과연 어떤 근본적인 상태가 있었는지에 관심이 있기 때문에, 이런 가정은 필요없다.

아무튼 이 문제를 풀기 전에 우선, 전체적인 Notation을 정리하고 넘어갈 필요가 있다.

notation을 정리하고 들어가면 편하겠다.

다음으로 정리할 것은 Markov Model과 generation process를 결합한 그림이다. 이 그림이야 말로, HMM의 핵심이라 할 수 있다.

 이 그림이 나타내는 것은 MM에서도 배웠지만, 일단 기본적으로 Markov Model을 따른다는 것이고, 추가적으로

 어떤 상태 q에서 x를 출력할 확률은 그 이전 상태와는 완전히 독립적이라는 가설이다.

 (conditional independency assumption)

 근데 왜 'Bayesian network' 이라는 말이 있을까? 이는 HMM도 '베이지안 네트웍' 모델링 기법에 그 기반을 두었기 때문인데, 좀더 상위 모델 개념이라고

 이해하고 넘어가자.

 지금까지, 해결하려고 하는 문제를 정의하고 모델링까지 했으니, 이제 진짜 우리가 풀려고 하는 문제를 다시 정의해 보자.

이 그림에서 initial state distribution은 그 첨자가 1 이다. 이는 반드시 HMM의 경우 start state가 존재해야 한다는 의미이다. 그 시작 상태에서 어떤 output을

출력할 확률 분포가 필요한 이유이다.

그러면, 위와 같이 좀더 보기 좋게 정리된 문제를 가지고 우리는 실제 어떤 문제를 풀어야 할까? 

아래 그림에 잘 정리가 되어 있다.

첫째, 관측된 output들이 sequence에 대한 확률이다. 이건 약간 Markov Model을 계산할 때와 비슷해 보인다.

        ==> 다른 점은 모델 파라미터 '람다'가 들어가 있는 것이다.

둘째, 관측된 output sequence를 가지고 가장 그럴 듯한 state sequence를 찾아내는 것이다.

        ==> 사실 진짜로 알고 싶은 것은 바로 이것이다.

셋째, 학습에 관련된 이슈인데, 이는 학습 데이터를 가지고 있는 상태에서 모델 파라미터 '람다'를 적절하게 결정해야 할 필요가 있기 때문에

        학습 알고리즘을 통해서 '람다'를 최적화 해야 한다.

지금부터 기술되는 것은 이 세가지 문제를 푸는 방법이다. 관심없는 분은 넘어가시길 바란다. 좀 복잡하니....

이제 첫번째 문제를 해결해 보자.

하지만, 확률로 표현하면, 전부 OR 이기 때문에 단순히 더하면 된다. summation 안에 들어가 있는 수식은 조건부 확률을 Bayesian Theorem에 의해서

뒤집은 결과이다. 이 수식을 어떻게 계산할까?  머리가 약간 아플 수도 있지만  하나의 Q = q1 ~ qT에 대해서만 생각해 보면,

아주 위쪽에서 그려진 Bayesian network representation을 이용해서 아래와 같이 풀어 쓸 수 있다. 그리고 이 결과를 계산하면 된다.

멋지다 @.@

아무튼 이 수식에 Forward Algorithm이라는 말이 들어간 것은 계산 순서가 1부터 t까지 순차적으로 계산하기 때문에 그런거고 별 의미는 없다.

다시한번 정리하면

 DP 기법에서 자주 나오는 notation인데, 다시 한번 숙지하고 넘어가자. DP는 아래와 같이 구성되어 있다.

1. initialization

    - 고등학교때 수열 문제 풀때, 초기 a1, a2 등등을 지정하고 가는 것 처럼 초기값 설정

2. induction

    -  a(n)과 a(n-1)의 관계를 수식으로 표현

    - 그래서 귀납법(induction)이다.

    - 그래서 deduction이 아니다.

3. termination

    - 계산하려고 하는 대상이 a(100) 인 경우, a(101)은 계산할 필요가 없다. 그래서 종료 조건이 반드시 필요하다.

    - 프로그램으로 작성한다고 생각하면 recursive call이 되겠는데, 여기에 종료 조건이 없으면 무한루프에 걸리니까...

다시 원래 문제로 돌아가서, '아니 그럼 forward algorithm'이 있으니 'backward'도 있겠네? 하시는 분도 계실 것이다. 그렇다!

backward 방향으로 계산하면 똑같다. 다만, 초기 상태까지 와 봐야, 그 중간에 저장된 확률 값들을 알 수 있다는 단점이 있다.

 음... 사실 나는 backward는 별로 관심없지만, 뒤에 가면 HMM 학습에 backward가 필요하다  

 아무튼, 자 ~ 이제 첫번째 문제는 해결된 셈이다.  이젠 어떤 output sequence가 주어져도 그 확률을 계산할 수 있다.

 다음으로, 두번째 문제를 풀어보자. 관측된 output sequence로부터 가장 그럴듯한 state sequence를 구하는 문제인데, most probable sequence decoding

 이라고도 한다. 즉, 아래와 같은 문제이다.

 이 문제를 해결하는 데, 가장 잘 알려진 알고리즘이 바로 Viterbi Algorithm이다. 이것도 DP 방법을 사용해서 문제를 해결하는데,

 관점은 지금까지와는 조금 다르게, path의 확률을 계산하는 데 초점이 맞춰져 있다.

 단순하게 생각하면 시간 t의 여러개의 상태에서 시간 t+1의 어떤 상태 q(j)로 오는 path는 상태의 숫자만큼 존재한다. 그런데, 여러개의

 path에서 어떤 path로 오는 것이 가장 그럴듯 한가? 라는 문제를 생각해 보면, 아래와 같이 두가지를 고려해야 한다.

 1. t의 어떤 상태에서 t+1의 상태 q(j)로의 전이 확률  : a(i,j)

 2. q(j)에서 관측된 output x(t+1)의 확률 : b(j, x(t+1))

 즉, 이 두가지 확률을 곱한 값이 최대가 되는 path를 선택하면 된다.

 이 문제를 DP 문제로 확대시켜서 수학적 귀납법으로 표현하면 아래와 같이 되는 것이다.

 , 그 확률이 최대가 되는 이전 상태이다.  현재 어떤 output이 있는 지 고려하지 않고 계산한다.

음...?  그런데 여기서 path backtracking은 무엇인가?  HMM을 공부할때, 자주 하는 착각중에 하나는 바로

'그럼 처음 상태에서 다음 상태로 가는 path 중에서 path probability가 가장 높은 path를 선택해고, 선택된 그 상태에서 다음으로의 path들을

 계속해서 선택해 나간다면 최종적으로 가장 그럴듯한 path가 나오는 게 아닌가?' 이다.

 답은 '아니다' 이다. 이 방법은 그냥 단순히 local search를 하는 것 뿐이고, HMM은 global search를 하는 알고리즘이다. global search는

 모든 가능한 path를 전부 계산하기 때문에 너무 시간이 오래 걸린다. local search는 그냥 단순하게 현재 눈앞에 가장 이득인 놈을 선택해서 탐색하는 방법으로

 greedy search라고도 한다. '탐욕스런 탐색'이라니~ 정말 이름 잘 지었다!!  사설이지만, 우리의 인생의 방향을 선택할때도 가끔 이러지 않을까?

 아무튼, viterbi algorithm은 가장 optimal한 path를 선택해야 하기 때문에 끝까지 가본 이후, 마지막 상태부터 거꾸로  back tracking을 하면서

 가장 확률이 높게 나오는 이전 state를 선택해 가면서 처음 상태로 되돌아 가야 최종적인 결과가 나오는 알고리즘이다.

 그래서 path backtracking 공식이 있는 것이고...  위 그림에서 화살표가 거꾸로 되어 있는 이유도 이것 때문이다. ^^

 자 이제 여기까지 왔으면, HMM으로 모델링 된 어떤 문제에서 output sequence를 알면 대응되는 state sequence를 계산할 수 있겠다.

 대단하지 않은가?

 이제 마직막으로 세번째 '모델 학습'에 관련된 문제만 해결하면 되는데, 그러기 전에 우선 NLP에서는 어떤 응용이 있는 지 먼저 살펴보고 넘어 가자.

 NLP 분야에서 HMM이 쓰이는 대표적인 모듈은 POS(Part-of-Speech) Tagger이다. 즉, 아래와 같은 문제이다.

 [출처] 부산대학교  한국어 정보처리 연구실 - 품사태거 - 정성원 

 한국어 형태소 분석기는 어떤 어절에 대해 가능한 모든 형태소 분석 결과를 출력해 준다. 하지만, 우리가 필요한 것은 이중에서 진짜로 문맥에 맞는 형태소 분석

 결과이기 때문에, 이 문제도 HMM으로 모델링해서 해결할 수 있다.

 어절을 output , 형태소 조합을 state라고 한다면 HMM에 쉽게 대응해 볼 수 있을 것이다.

 태거를 HMM으로 모델링한다면, output과 state는 얼마나 될까?  일단 state는 그렇게 많지 않다. 형태소 분석기 내부에는 하나의 어절에 대해 구성 가능한

 형태소 결합 규칙을 기술해 두는데, 이 규칙의 수가 state의 수가 될 수 있다. 하지만, output의 숫자는 엄청나게 많다. 따라서, 일반적으로 태거를 구현할때는

 형태소 분석단계에서 최대한 분석의 수를 줄인 이후에 태거에서 HMM 기법을 통해 가장 적합한 품사를 결정한다. 즉, 중의성이 있는 어절들에 대해서만

 가능한 형태소 분석 결과를 출력하고, 그렇지 않은 경우는 고려하지 않는다.

 어쨌든, 이러한 품사 태거를 만들기 위해서는 대용량의 품사태깅된 학습 말뭉치가 필요한데, 이 말뭉치는 보통 아래와 같이 생겼다.

 나는 학교에 간다   -->   나/대명사+는/조사  학교/보통명사+에/조사  가다/동사+ㄴ다/종결어미

 하늘을 나는 새를 보았다 -->  하늘/보통명사+을/조사  날다/동사+ㄴ/관형형어미  새/보통명사+를/조사 보다/동사+았/선어말어미+다/종결어미

 .....

 우리는 이러한 학습 말뭉치를 가지고  상태전이확률(품사간 전이 확률, 편의상), 생성확률(어휘 생성 확률)을 계산할 수 있다.

 다시 본론으로 돌아가서, 세번째 문제는 모델의 파라미터를 학습 데이터로부터 최적화하는 것인데, 품사 태거를 학습시키는 문제에 적용해 보면 확률 데이터를 좀더

 정교한 방식으로 계산해서 얻겠다는 의미도 될 수 있다. 어떤 품사에서 출력되는 output의 숫자는 엄청나게 많아서 학습시킬 때 언제나, 데이터 부족 문제

 (data sparseness problem)가 생기는 것은 피할 수 없다. 즉, 관측된 데이터만으로는 관측되지 않은 확률 값을 계산하는 데 심각한 문제가 있다는 의미이다.

 이러한 문제를 해결하기 위해서 보통 우리가 하는 일은 "모델을 잘 만든다" 이다.

 조금 우습지만 이게 정답이다. 잘 만들어진 모델이 있으면, 잘 모르는 확률도 해당 모델을 기반으로 해서 좀 더 그럴듯하게 근사값을 계산할 수 있다.

 아주 대표적인 예가 있는 데, 바로 '정규분포(standard distribution)'이다. '학교 성적, 인구 분포 등등의 현상은 대부분 정규분포에 근사한다' 라는 게 우리의 가설이고

 이를 모델링한 것이 바로 정규분포이다. 따라서, 우리는 모든 사람을 일일히 호구조사하지 않아도 대충 몇살부터 몇살까지 몇명이 있는 지 근사값을 계산할 수

 있는 것이다. 그러니, 잘 모르면 모델을 잘 만들면 된다. 사설이지만, 가장 완벽한 모델은 무엇일까? 음... 바로 수학이다!!  한치의 오차도 없는 완벽한 모델 ^^

--------------------------------------------------------------------------------------------------------------------------------------------------

[여기서 잠깐]

Q) 위와 같은 품사 태깅된 말뭉치가 있는 경우에도 파라미터 '람다'를, 좀더 정확히 말하면 state transition 파라미터를, 학습시켜야 하나?

A) Linguist's Guide to Statistics [참고 : http://blog.daum.net/hazzling/16884279]

    여기에 보면 아래와 같은 내용이 나온다.

   즉, "underlying state sequence는 unknown이고 오직 signal sequence 즉, output sequence만 학습데이터로 가지고 있는 경우에만

    state transition probability parameter를 Baum-Welch reestimation 알고리즘 등을 이용해서 추정한다"

   따라서, '그럴 필요 없다'가 정답이다. 다만,  품사조합(state)들 간의 transition 데이터가 좀 부족하면 보정작업등을 해서

   학습 데이터의 부족문제를 약간 해결할 수 있을 것이다.

   아래에서 언급되는 내용은 우리가 오직 output sequence만을 학습 데이터로 가지고 있는 경우에 어떻게 state transition에 관한

   정보를 끄집어 낼 것인가에 대한 것이다.

--------------------------------------------------------------------------------------------------------------------------------------------------

 아무튼, 우리는 관측된 데이터만 가지고 모든 상태전이확률, 생성확률을 잘 구할 수 있도록 모델을 구해야 하며, 이것이 지금부터 언급될 내용이다.

 보통 HMM의 파라미터 '람다'라 하면 아래 3가지를 의미한다.

 1. 상태전이확률  : A

 2. 생성확률 : B

 3. 초기확률 : py

 따라서,  람다 = ( A, B, py )  이렇게 표현하고  실제 우리가 관측한 데이터를 X 라고 한다면,

 우리가 만들려고 하는 어떤 모델은 '람다'를 조건으로 할때, 관측 데이터 X를 가장 잘 표현해야 한다. 이런 종류의 문제는 Likelihood 를 최대한 높여야 한다고

 보통 얘기하는데, 잠깐 Likelihood에 대해서 알고 넘어가자.

 예를 들어서, 동전던지기 사건에서 앞면이 나올 확률 p를 동전던지기 사건 모델의 파라미터라고 하고, 1000번 던저 나온 결과값 즉, 관측 데이터를 우리가 가지고

 있다고 하자. 1000번의 550번은 앞면, 450번은 뒷면이 나왔다. 자~ 그럼 어떻게 하면 확률 p를 가장 잘 결정할까? 일단 p = 0 으로 해보자.

 엥?  만약 그렇다면 관측한 데이터와 완전히 동떨어진다. 그럼 p = 1 로 하면?  역시 마찬가지다. p = 0.5 로 해도 관측된 데이터와는 조금 미스매치다.

 그래서 관측데이터를 가장 잘 표현할 수 있도록 조금씩 p값을 앞뒤로 조정해 나가면 p = ( 550 ) / ( 1000 ) = 0.55 로 결정된다. 이런 조정 작업이 바로

 모델 파라미터 학습이라고 하고, 여기서 사용된 개념이 바로 'Likelihood를 최대로 해서 모델 파라미터를 결정한다'는 것이다.

 그런데, 관측데이터에 너무 지나치게 모델 파라미터를 학습시키면 어떨까? 사실 동전을 많이 던지면 p 는 0.5에 접근한다. 실험을 적게하면 Likelihood로

 계산한 모델 파라미터 p는 0.1일 수도 있다. 이것이 보통 우리가 얘기하는 overfitting 되었다는 것이고, 거꾸로 생각하면 학습 데이터가 부족하다는 것이다.  

 (data sparseness problem)

 기계학습의 아주 기초적인 개념이 사실 고등학교때 배운 동전던지기 확률 모델에 거의 다 들어있다는 것을 요새 새삼 깨닫게 된다 @.@

 다시 파라미터 학습 문제로 돌아가면, 결국 Likelihood를 최대화하도록 람다를 학습시켜야 하는데 이를 수식으로 풀어내면 위의 그림과 같다.

 P( X | 람다 ) 는 3가지 문제 중에서 첫번째 문제를 해결할 때, 위의 수식처럼 summation 형태로 바꿀 수 있는데, P( Q | 람다 ) 는 state transition이

 숨겨져 있어서 구하기 어렵다. 따라서, estimation을 해야 한다. 그럼 어떤 방법을 사용해야 할까? 

 일반적으로 이런 문제에서는 EM(Expected Maximization) 알고리즘을 사용한다. EM도 결국 Likelihood를 최대화 하도록 파라미터를 학습시키는

 방법론이라고 할 수 있는 데, 좀더 잘 정리되어 있다는 점이 다를 뿐이다.

 ( 위에서 기술된 Baum-Welch reestimation은 EM 프레임웍을 HMM에 최적화시킨 알고리즘이다. )

 EM 알고리즘 참조 ==> http://blog.daum.net/hazzling/17067790

 잘 이해하기 힘든 그림이다.  이것 말고, 다른 문서를 참고하자.

 Linguist's Guide to Statistics [참고 : http://blog.daum.net/hazzling/16884279]

 여기에 있는 HMM chapter를 보면

 output sequence  =  o1, o2, .... , oT

 이런 관측 데이터가 있을 때,

 time (t)의 상태가 si 이고

 time(t+1)의 상태가 sj 일 조건부 확률을 아래와 같이 정의할 수 있는데,

 이 확률 값은  forward, backward probability의 조합으로도 표현할 수 있다.  

 그리고,

 가장 아래 부분은 관측렬이 아래와 같고

 output sequence  =  o1, o2, .... , oT

 time ( t ) 일때 상태가 si 일 확률은 

 partition 이론으로 부터, summation으로 풀어쓸 수 있고

 이 풀어쓴 결과가

 결국

 위 그림의 마지막 라인과 같다는 것을 알려준다.

 이것으로 부터 아래와 같은 4가지 fact를 추출할 수 있다.

 0) time 1 에서 상태 si 로 시작할 확률값

 1) si --> sj 로 transition하는 횟수의 평균값

 2) si 로부터 어떤 다른 상태로의 transition 횟수의 평균값

 3) si 에서 어떤 시그널(output)을 뱉을 평균 횟수

 그리고, 위에서 나온 fact를 이용해서,

 초기 py 값 :  time 1 에서 각각의 상태 si로 시작할 확률값

 pij   :  ( time 1 ~ T-1  사이에서 si -> sj transition 평균값 )  /   (  time 1 ~ T-1 사이에서 si 로 시작하는 transition 평균값 )

          이것이 바로  si --> sj  전이 확률의 평균값(기대값)

 aij   :  ( time 1 ~ T 사이에서 상태 si가  signal(j)를 출력할 평균값 ) / ( time 1 ~ T 사이에서 si 로 시작하는 transition 평균값 )

  이와 같이 모델 ramda를 계산할 수 있다.

  우리가 만약 어떤 m개의 관측 데이터를 가지고 있다고 하자.

  o11  o21  o31 ....  oT1

  o12 o22  o32 ....  oT2

  .........

  o1m o2m  o3m ....  oTm

  BW 알고리즘은 이것으로 부터 transition proability를 추정해 내는 알고리즘이라 할 수 있는데,

  그럼 우선 어떤 것을 먼저 설정해 줘야 할까?

  일단, number of state ( N ) 값과 number of observation ( M ) 값을 설정해야 한다.

  M 값은 관측 데이터로 부터 자연스럽게 설정되고

  N 값은 미리 알고 있다고 가정하자 ( 문제의 종류에 따라 다르다.)

  초기 시작 상태에서의 emission probability py는 그냥 대충 설정해 주면 된다. 합이 1이 되도록....

  마지막으로, transition probability aij, emission proability pij 도 랜덤하게 설정해 둔다.

  이 상태의 모델이 바로 ramda(0)

  자 이제 이러한 상태에서, 위의 그림에 나온 공식을 사용해서 계속 parameter를 최적화하는 작업을 진행해야 한다.

  위의 공식을 뜯어보면, 결국 최종적으로 forward, backward probability(variable)을 알아야 계산 가능하다는 것을 알 수 있다.

  그렇다면, forward, backward 확률은 어떤 순서로 계산하는가?

  forward는 기본적으로 time 1에서 먼저 계산하고 그 다음 time 2, 그리고 그 결과를 이용해서 time3 ...

  이런 식으로 해서 최종적으로 time T 까지 계산한다.

  backward는 forward와는 반대로 time T 부터 계산하고 거꾸로 time 1 까지 가면서 계산한다.

  ( 물론, time T에서는 초기값은 확률 합이 1이 되도록 임의로 설정해 둔다)

  이러한 과정을 통해서 alpha(t), beta(t) 값을 전부 어떤 테이블에 저장해 두고 사용한다.

  아래 그림을 보자.

  [reter to] http://nlp.korea.ac.kr/~kshan/resources/AlgorithmsForHMM.ppt

 초기에 initial guessing을 통해서 설정된 전이확률 및 생성확률을 가지고

 alpha, beta를 계산하고

 이를 이용해서 다시  아래를 계산한다.

  그러면 전이확률 및 생성확률, 초기확률이 변화할 것이다.

   또, 변화된 모델에서 alpha, beta를 구한다.

   이 과정을 아래 그림과 같이 반복한다.

   [refer to]  http://www.facweb.iitkgp.ernet.in/~sudeshna/courses/ml08/hmmkanungo2.pdf 

  아... 이제 무한루프에서 탈출한 기분 ^^

  그런데 이러한 BW 추정에도 단점이 있다.

  [reter to] http://nlp.korea.ac.kr/~kshan/resources/AlgorithmsForHMM.ppt

 어쩔수 없는 문제이긴 하지만.... ^^;

 HMM을 이해하는 데 있어서 가장 헷갈리는 부분이 바로 이 BW 알고리즘이 아닐까 한다.

 흠... 직접 구현해 보지 않으니, 개념적으로만 맴돌고 약간 모호한 느낌이긴 하다.

 구현이라...

 이미 구현된 패키지를 사용하는 방법 관련해서

 --> [참고] http://blog.daum.net/hazzling/16781469

PageRank 와 구글 검색엔진

v1.0 2007/11/02 Copyleft by 전경헌@사이냅소프트


페이지랭크(PageRank)

비싼거라는데... 구구절절한 음식 설명보다는 먼저 먹어보는게 좋지 않겠나?
구글창업자중 한명인 래리페이지가 만든 페이지랭크의 정의는 아래와 같다.

그림1) 노드 A와 T1 ... Tn 사이의 관계

페이지랭크는 모든 노드에 대한 확률분포를 나타낸다.
따라서 모든 노드의 페이지랭크의 합은 1이다.

예제1) 링크가 하나뿐인 구조에서의 페이지랭크

 PR3(A) = 0.15 + 0.85 * 0 = 0.15
 PR3(B) = 0.15 + 0.85 * 0.15 = 0.28

더이상 값의 변화가 없이 수렴하므로,

PR(A) = 0.15 / 0.43 = 0.35
PR(B) = 0.28 / 0.43 = 0.65

예제2) 링크가 두개이며 서로 링크하는 구조에서의 페이지랭크

 PR1(A) = 0.15 + 0.85 * 1 = 1.00
 PR1(B) = 0.15 + 0.85 * 1 = 1.00

계산값이 수렴하므로,

PR(A) = 1.00/2.00 = 0.5
PR(A) = 1.00/2.00 = 0.5

검색엔진 개요

PageRank는 검색과 관련이 없는 개념이라 볼 수 있지만,
관련 될 수 도 있다. 그래서 검색부터 설명하도록 한다.

(별로 중요한 것은 아니지만...)
많은 사람들이 네이버나 다음, 엠파스를 검색엔진이라 부른다.
이를 조금 덜 모호하게 말하자면 검색엔진을 장착한 포탈이다.
이 문서에서는 좁은 의미의 검색엔진에 대해서만 설명한다.

• 수집(Crawl) - 에이전트나 게이트웨이를 통하여 검색대상이 되는 문서를 모으는 작업
  (중복제거, 링크추출, 병렬처리, 암호화, 압축, DB연계 등이 문제가 됨)
• 색인(Index) - 수집된 문서를 분석하여, 검색하기 좋은 형태로 저장하는 작업
  (하부저장구조, 형태소분석, 사전관리, 색인 속도, 색인 용량, 온라인색인 등)
• 검색(Search) - 질의어에 부합하는 문서를 색인에서 찾아 유저에게 보여주는 작업
  (질의어분석/확장, 속도, 병렬처리, 재현률과 정확률, 랭킹, 소팅, 머징, 그룹핑 등)

각각에 대해서는 수도없이 많은 논문들이 있으므로, 깊이 알고자하면 쉽게 배울 수 있음.
특히, 요즘엔 검색엔진과 관련된 다양한 오픈소스가 존재하므로
좋은 오픈소스를 참조하여 공부하는 것을 권장함.

DBMS와 비교하여 검색엔진의 가장 큰 차이점을 말한다면,
정확히 일치하는 것이 아니라 유사한 정도를 가지고 문서를 찾아야 한다는 것과
DBMS가 백업/복구 등 다양한 관리기능을 중시하는 것과는 달리
검색엔진은 검색결과의 만족도와 검색속도를 중요시 한다.

3노드 페이지랭크

이제 노드가 3개있는 구조의 페이지랭크를 구해보자.

그림5) 3노드 직렬 링크 구조

먼저, PageRank 공식에 대입하여 써보자.

PRi(A) = 0.15
PRi(B) = 0.15 + 0.85(PRi-1(A)/1)
PRi(C) = 0.15 + 0.85(PRi-1(B)/1)

연습장에 손으로 풀어도 되겠고, 간단한 프로그램을 짜도 되겠으나,
엑셀이 가장 좋다.(초기값을 바꿔서 실행하기 최고 아닌가?)

따라서,
PR(A) = 0.18, PR(B) = 0.34, PR(C) = 0.47

PRi(A) = 0.15
PRi(B) = 0.15 + 0.85(PRi-1(A)/2)
PRi(C) = 0.15 + 0.85(PRi-1(A)/2 + PRi-1(B)/1)

페이지랭크는 다른 노드가 얼마나 괜찮은 지에 대한 투표를 하는 것이다.
참고로 이 투표는 누구나 여러표를 행사할 수 있고, 투표하지 않아도 된다.
예를 들어 A가 두표를 행사해서 B와 C에 표를 주었다면,
A의 지지도는 분산되며 B와 C는 A로부터 동일한 정도의 지지를 받은 것으로 판단한다.

그림에서 어느 노드가 가장 많은 지지를 받고 있는 지 생각해보고,
이를 수치화한 PageRank값과 비교해 보기 바란다.

구글 검색엔진의 구조

상대적으로 자료규모가 작은 기업용 검색엔진을 만들고자 하는 경우에는 DBMS와 유사한 정도의 많은 기능이 필요하다. 그러나 인터넷상의 많은, 정말로 많은 자료를 검색하고자 하는 대용량 검색엔진을 만들고자 하는 경우는 다양한 기능보다 검색이라는 하나의 기능이 할 수 있는한 최대한 빠르게, 정확하게 되는 것이 필요하다.

검색엔진은 일종의 유틸리티 집합처럼 작동한다. 사실 검색엔진 뿐만 아니라 대부분의 서비스들이 이처럼 작은 프로그램들로 구분되서 개발되어진다.

페이지랭크의 왜곡

구글이 제공하는 구글툴바를 사용하면 웹브라우저에서 현재 보고있는 페이지의 페이지랭크를 알 수 있다. 아래 그림에서 사이냅소프트 홈페이지의 PageRank는 5이다.

그림9) 구글툴바를 설치하면 페이지랭크를 볼 수 있다.

툴바가 제시하는 페이지랭크는 실제적인 값이 아니라, 실제값을 10개의 범위로 나뉘어 보여준 것이라서 정확한 값을 알기는 어렵다. 능력되시는 분은 구글 툴바를 해킹해서 실제 페이지랭크값을 볼 수도 있겠다.(구글툴바 라이센스 위반이라고 하네요, 설치시에 누가 라이센스 읽어보나...ㅡㅡ;)

페이지랭크는 웹페이지의 중요도 또는 괜찮은 정도를 나타낸다고 보면 되나,
아래와 같은 몇가지 경우에 왜곡 된다.

1) Reciprocal links - "내꺼 링크해줘, 나도 링크해줄께"
2) Link Requirements - "우리 스크립트를 사용하시려면 우리 홈페이지를 링크해주세요"
3) Friends and Family - "내 친구 성연이의 사이트입니다", "우리 개 사이트가 여기 있어요"
4) Free Page Add-ons - "이 카운터는 www.linktocounter.com 에서 제공된 것입니다"

검색엔진최적화 또는 마케팅 업체

페이지랭크 등 검색엔진에서 사용되는 랭킹알고리즘을 연구하여 특정페이지가 Top 10 페이지 안에 들어올 수 있도록 해주고 돈을 받는다.

대용량 검색결과

우리 모두가 정답을 알고 있다. 그렇다 잘 보여줘야 한다. 그러나 재현률과 정확률이 100%인 경우라도 "노무현"을 검색한 결과가 칠백삼십육만오천육백이십이개가 나왔다면 도대체 사용자에게 어떤 10개를 화면에 보여주는 게 좋을까? 여기에서 랭킹이 등장한다. 사용자가 더 원할 만한 것의 랭킹을 높여서 가장 랭킹이 높은 10개를 보여줄 방법이 필요하다.

구글이 검색결과에 사용하는 기본적인 랭킹은 다음과 같다.
1) 검색에 사용된 키워드와 매치되는 모든 페이지를 찾는다
2) 각 페이지에 있는 키워드와 같은 요소를 중심으로 랭킹을 한다.
3) 인바운드(페이지로 들어오는) 앵커텍스트를 계산한다.
4) 페이지랭크 점수를 랭킹점수에 곱해서 높은 순서대로 10개를 보여준다.

Final Rank Score = (score for all Non-PageRank factors) * (actual PageRank score)

보다시피 페이지랭크는 랭킹에 반영되는 하나의 요소일 뿐이지 절대적인 것은 아니다.
또한, 예전에 비해서 페이지랭크가 반영되는 정도가 계속 감소하고 있는 추세이다.

PageRank는 구글이 검색결과의 정렬에 사용하는 100여개의 알고리즘 중의 하나이다.

우리가 만든 페이지가 특정키워드의 검색결과페이지(SERPs)에 나타나기를 바란다면,

먼저 해당 키워드가 우리 페이지에 있어야 한다. 이 키워드가 Title Tag에 등장하거나
Body Text에 강조된 형태로 나오면 더 좋다.

그리고 우리 페이지를 링크하는 외부 페이지들에서 해당 키워드가 앵커텍스트로 등장해주면
더 좋다.(앵커텍스트의 가중치가 더 높다)

끝으로 페이지 랭크가 높아야 한다.

4노드 페이지랭크

따라서, 
PR(A) = 0.35, PR(B) = 0.14, PR(C) = 0.37, PR(4) = 0.14

초기값이 얼마여도 최종 결과에는 관계가 없다.
노드 수가 많아질수록 반복계산량이 많아진다.

2600만개 노드에 대한 PR계산에 워크스테이션 한대에서 몇시간정도 소요(1998, 구글)

반복횟수를 줄이기 위하여 수렴오차범위를 넓게 잡거나,
매번 새로운 PageRank를 계산하는 게 아니라 이전에 계산했던 값을 유지할 수도 있고,
여러개의 컴퓨터를 이용하여 병렬로 계산할 수도 있다(컴퓨터간에 서로 Sync를 맞춰야 한다)

비 PageRank Factor Threshold

검색결과의 랭크에 있어서 페이지랭크를 제외한 다른 요소들은 특정한 기준 점수(Non-PageRank Factor Threshold) 이상만 되면 크게 차이가 나지 않는다. 다시말하면 앵커텍스트가 두배가 된다고 해도 그다지 점수가 높아지지 않는다. 마치 로그함수의 그래프를 생각하면 되겠다.

아래 수식의 Non-PageRank는 로그적으로 증가한다고 보면 맞다.
Final Rank Score = (score for all Non-PageRank factors) * (actual PageRank score)

그래서 이때부터는 PageRank가 매우 중요해진다. PageRank를 모아서 값이 높아져야만 SERPs에 등장할 수 있다.

정말로 중요할 것 같지 않은가? 어느정도 수준이 되는 페이지들이라면 이때부터는 페이지랭크 값이 결정적이다.

SERPs에서 그릇된 페이지를 발견했을 경우

검색결과페이지내에 각 항목별로 버튼을 두어서
버튼이 눌리면...

해당페이지의 PageRank를 0으로 하여 검색결과의 제일 뒤로 보낸다.
해당페이지와 관계된 링크들을 Links에서 제거해버린다.

참고문헌

1) Sergey Brin and Lawrence Page, "The Anatomy of a Large-Scale Hypertextual Web Search Engine"
2) Chris Ridings and Mike Shishigin, "PageRank Uncovered"

부록. 직접 검색엔진을 만들고자 하는 분들에게...

아주 간단한 검색엔진을 직접 만들어 보고 싶다면, 수집 프로그램은 직접 만들기보다는(검색엔진에서 수집기가 가장 어려운 부분일지 모른다, 잘하려면 거의 인터넷 익스플로러를 다 만들어야 할 수도 있다) 인터넷 검색에서 "open source crawler"를 검색해서 나오는 것 중에 오래되고 자주 업데이트되는 것을 하나 골라서 쓰도록 하고, 특별히 나는 남의 코드 보는 능력이 뛰어나다고 자신한다면, Mozilla 소스를 커스터마이징해서 쓰기를 권장한다. 남의 것은 죽어도 싫다면... 구글처럼 파이썬으로 만들어라.

색인 프로그램을 만들기 위해서는 어떤 검색기능이 필요한 지를 알아야 한다. 단순 키워드 검색이면 되는 것인지, 멀티 키워드 검색이 가능해야 하는지, 키워드간의 근접성(proximity)이 필요한 것인지 등 색인과 검색은 사실 하나의 틀에서 개발이 이루어져야 한다. 가장 단순한 검색을 한다고 하고, 하부저장구조로는 버클리DB나(포탈에서 좋아한다) 위스콘신대학의 Shore를(연구소에서 좋아한다) 사용하도록 하고, 국문법에 대한 상당한 이해가 필요한 형태소분석보다는 N-Gram방식을 이용하라. 인터넷을 찾아보면 N-Gram 소스코드도 찾을 수 있다.

대용량 처리가 필요하다면, 모든 자료구조를 숫자화하도록하고, 다양한 저장구조가 있겠지만 그 중에서도 해쉬를 사용하기 바란다. 음... 좀 더 직접적으로 설명하자면, 키워드를 모두 숫자형태의 id로 맵핑해서 사용하고, 문서도 마찬가지로 모두 숫자형태의 id로 맵핑해서 사용한다, 그리고 미리 소팅해놓을 필요가 있는 것들은 b-tree같은 구조를 사용하는 것도 좋고, 할 수만 있다면 hash를 쓰도록한다. 어떠한 자료구조라도 이론적으로는 hash보다 빠를 수는 없다.

수집할 데이타가 얼마 안된다면(일반적으로 기업체 내부에서 쓰이는 자료) DBMS와 유사한 아주 다양한 검색기능을 만들어야 유저가 행복해 할 것이다. 그러나 수집할 데이타가 아주 방대하다면(대형 포탈에서 대상으로 하는 자료) 유저는 단순한 검색기능이라도 결과가 잘 나오면 기뻐할 것이다.

어떤 경우에도 검색 결과의 만족도와 검색 속도는 절대로 훼손하면 안되는 것이다. 검색결과의 만족도가 낮으면 누구도 쓰려고 하지 않을 것이고, 검색 속도가 느리면 많은 사용자들이 동시에 검색할 경우 거의 사용불가능 상태가 될 수가 있다.

검색결과의 만족도라는 것은 사람마다 다르고 정성적인 것이라 일종의 인공지능에 관련된 문제다. 처음 검색엔진을 만들 때는 인공지능성격의 문제는 아예 접근하지 않는 게 좋다. 상업용이 아니라 연습용이라면 처음에는 검색결과의 만족도를 무시하라.

검색 프로그램은 사용자의 질의를 색인시에 사용했던 N-Gram을 써서 분리하고, 해당 키워드의 id로 맵핑해서 질의어의 키워드 id 목록을 만든다. 이제 이 키워드 id목록을 가지고 각각의 키워드 id에 해당하는 문서 id들을 모아와서 하나로 결과를 하나로 합쳐서 사용자의 화면에 보여준다.

검색/색인 개발과정은 클라이언트/서버 개발과정과 비슷하다. 검색이 좀 편하려면, 색인을 잘해줘야 하고, 색인을 부실하게 하면 검색이 힘들다. 색인과 검색을 나눠서 개발하고 서로 일을 미루면 잘 개발 안된다.

-끝-


[출처 : http://blog.bagesoft.com/661]