Markov chain [마코프 체인]

마르코프체인(Markov Chain)   AI / Tip  2010/02/02 01:58

원문출처 :  http://blog.naver.com/ojs83/120100904784   ::  http://happyengine.tistory.com/

[출처] 마르코프체인(Markov Chain)|작성자 ojs83

마르코프체인(Markov Chain)은 마르코프성질(Markov Property)을 지닌 이산 확률과정(discrete-time stochastic process)을 의미한다.

 

확률과정이란 무엇인가?

확률과정(stochastic process or random process)이란 어떤 확률분포에 의해 벌어지는 일련의 연속현상들을 수학적으로 모델링하는데 사용되는 개념이다.

가장 간단한 확률과정을 예로 들자면 베르누이과정이 있겠다. 베르누이과정(Bernoulli Process)은 독립적으로 수행되며 오로지 두 결과값만을 갖는 사건이 연속적으로 발생할때, 그 결과값의 열을 모델링하는데 사용된다. 베르누이실험(Bernoulli trial)이라는 것이 "결과가 랜덤하게 둘 중 하나만 나오는 실험"이고, 베르누이 랜덤변수(Bernoulli random variable)이라는것이 베르누이실험의 결과 중 하나는 1로 하나는 0으로 매핑시켜주는 함수니까, 베르누이과정을 좀 더 수학스럽게 얘기하자면, "베르누이 랜덤변수 값의 열" 이라고 할 수 있겠다.

그럼 베르누이과정으로는 무엇을 모델링할 수 있을까? 동전던지기의 결과열이 그 대표적인 예가 되겠다. "앞뒤뒤앞앞뒤앞뒤.." 와 같은 열. 이런 열은 어떤 모델에 의해 생성이 되었냐는 물음에, 바로 "베르누이과정"에 의해 생성되었다고 하면 된다는 얘기다. 이 베르누이 과정에 의해 생성되는 열은 "앞뒤뒤앞앞뒤앞뒤..."가 될 수도 있고, "뒤뒤앞뒤앞뒤앞..."이 될 수도 있겠다.

이보다 아주 조금 복잡한 확률과정을 들자면, 포아송과정(Poisson Process)가 있겠다. 이 과정은 시간축 위에서 독립적으로 랜덤하게 발생하는 사건들의 열을 의미한다. 예를 들자면, 어떤 서버에 있는 홈페이지가 방문되는 사건들이나, 내 전화기에 걸려오는 전화들 같은 것들이 되겠다.또 조금만 생각을 달리하면, 책한권에 있는 오타들 도 될 수 있다. 위에서 예를 든 동전던지기의 경우, 만일 "앞"이 나오는 사건들의 열을 생각한다면, 이것도 포아송과정이다.

왜 이것들이 포아송과정인가? 모두 얘기하자면 매우 수학적이 될것같다. 간단히만 얘기하자면, 몇가지 사소한 조건만 만족할 경우, 이 포아송과정에 의해 발생하는 사건들에는 포아송분포를 따르는 특징이 있기 때문이다. 무엇이 포아송 분포를 따르냐 하면, 바로 특정 시간동안에 발생하는 사건의 수이다.

예를 들어, 10분동안 홈페이지가 방문될 회수가 어떤 확률분포를 따를지 곰곰히 생각해보자. 평균잡아 10분에 5번정도 방문되더라 하는 기존의 계산이 있었다면, 아마도 5번 방문될 확률이 제일 클 것이다. 4번이나 6번은 그보다 조금 작고, 3번이나 7번은 좀 더 작고, 그럴것이다. 이 분포가 포아송분포를 따름이 증명이 되어 있다는 얘기다

베르누이과정이 이산 확률과정인데 반해 포아송과정은 연속 확률과정이다. 베르누이과정에서는 시간의 개념이 1회,2회,3회와 같이 이산적이지만, 포아송과정에서는 0초부터 무한대까지 연속공간의 특정위치이기 때문이다.

 

그럼 이제 마르코프체인을 알아보도록 하자.

마르코프체인도 어쨌건 이산확률과정이므로 뭔가 1회,2회,3회에 발생하는 사건의 열을 의미하겠다. 중요한건 마르코프성질을 지닌다는 것이다. 그럼 마르코프성질이란 무엇인가? 마르코프성질이란 n+1회의 상태(사건의 결과)가 오로지 n회에서의 상태(사건의 결과)에만 영향을 받는것을 의미한다. 결과가 랜덤하게 나오는 동전던지기는 분명 마르코프성질을 따르지 않는다. 지금 던졌을때 나온 결과가 다음 던졌을때의 결과에 전혀 영향을 주지 않기 때문이다.

그러나 세상에는 그렇게 해석될 수 없는 "사건의 열"이 더 많다. 예를 들어, 1일날씨, 2일날씨, 3일날씨 라던가, 아니면 지금 이 글에서 첫번째단어,두번째단어, 세번째단어 등을 생각해보자. 2일의 날씨는 1일의 날씨와 완전히 무관하게 나타나는 현상일까? 아니면 (말이 되는 문장을 쓰지는 않는다고 가정할 때) 다음에 쓸 단어는 바로 이전 단어와 전혀 독립적으로 나타날까? 그렇지 않다. 그렇다고 위에서 든 두가지 예가 마르코프성질을 지니고 있다고 단정하는 것은 아니다. 3일의 날씨가 2일의 날씨와만 상관있다고 할 수 있지도 않고, 다음에 쓸 단어가, 몇단어 이전의 단어와 상관이 있을 수도 있는 것이기 때문이다. 그러나 이러한 현상들을 단순하게 모델링할때는 마르코프체인이라고 가정한다. 이러한 가정이 실제로 모델을 매우 단순하게 만들며, 때로는 이렇게 단순하게 만들어진 모델이 엄청난 위력을 발휘하기도 한다.

마르코프체인을 약간 다르게 해석하자면, n개의 상태가 있고, 그 상태들 중 임의의 상태로 시간에 따라 변해가는 과정을 생각할 수 있다. 예를 들어 상태가 {R, G, B} 이렇게 세개가 있다면, 첫번째는 G, 두번째는 R, 세번째는 G, 네번째는 G, 다섯번째는 B, 여섯번째는 B, 일곱번째는 R ... 이렇게 말이다.

물론 마르코프 성질을 지니니까, 두번째에 어떤 상태를 가질지는 첫번째 상태가 무엇이었냐에 따라 결정되고, 세번째는 두번째 상태에, 네번째는 세번째 상태에 의해 결정된다. 여기서 주의할것이 있다. 위 예를 보면, 첫번째 상태는 G였고 두번째상태는 R인 경우도 있고, 세번째 상태가 G일때 네번째 상태가 G인 경우도 있다. 즉, 마르코프체인은 "상태가 G일때 무조건 X상태로 간다" 이렇게 만들어지는게 아니라, "상태가 G일때 다음 상태가 R일 확률은 얼마, G일 확률은 얼마, B일 확률은 얼마" 이런식으로 정의된다.

따라서, 마르코프체인에서는 "상태전이확률"(state transition probability) 행렬이 핵심이 되고, 이 확률들을 사용하면 아래와 같은 다이어그램이 그려진다. 

이 게 머냐하면, 아주 간단한 영어문장뼈대의 생성과정을 Markov Chain으로 묘사한 그림이다. <start>는 시작상태, ART는 관사상태, V는 동사상태, N은 명사상태, P는 전치사상태이다. 즉 <start>상태에서 관사상태와 명사상태로 갈 확률이 각각 71%, 29%이고, 명사상태에서 다시명사, 동사, 전치사상태로 갈 확률은 각각 13%, 44%, 46% 라는거다. 이 모형에 따르면, 아주 여러가지 형태의 문장들이 생성될 수 있을 것이다. 이 모형은 음성인식과 자연언어처리의 품사태깅(각 형태소에 적절한 품사를 자동으로 부착하는 작업)의 근간으로 아주 오랫동안 사용되어져왔으며, 지금도 사용되고 있다. 시간이 되면 Hidden Markov Model(은닉 마르코프 모형)이라고 하는 잘 알려진 모형에 대해서도 한번 써보려 한다.

여하간, 중요한 수식 등 자세한건 좀 더 인터넷을 찾아보면 공부할 수 있을 것이고...

그렇다면, 마르코프체인과 구글의 페이지랭크는 어떤 관계가 있을까?

이 제 페이지랭크와 이 마코프체인의 관계를 생각해보자. 그러기 위해 지구상에 존재하는 모든 웹페이지들과 그 페이지간에 걸려있는 링크들을 위의 다이어그램에 매핑시켜보자. 그리고 임의의 한 페이지에서 링크를 따라 아무데로나 페이지를 따라가는 Random Surfer(랜덤서퍼)를 생각해보자. 링크에 위에서처럼 확률값이 붙어야 하는데, 확률값은 대충 준다. 어떻게 주냐면, 어떤 페이지에 링크가 2개면 각 링크를 따라 다른페이지로 갈 확률은 각각 50%, 50%라고 하고, 10개면 10%, 10%..., 10% 라고 그냥 하자. 

대충 저 위의 다이어그램하고 매핑이 되는지?

페이지랭크는 웹을 이런 단순한 구조로 추상화하는데서 시작됐다. 웹을 각 페이지가 노드이고 링크가 간선이며, 간선위의 확률값은 그 간선이 출발한 노드(페이지)에 위치한 링크수분의 1로 단정짓고, 일단 마르코프 체인을 그린거다. 그리고 어떤 문제를 푸냐하면, 이런 마르코프체인 위에서 Random Surfer가 마구 이동을 해대다가 누군가 Stop! 이라 외쳤을때, 각 노드(페이지)에 위치할 확률을 구한것이다. 그 값이 제일 높은 노드가 바로 인터넷상에서 가장 권위있는 페이지라는 것이다!

이렇게 한번 예를 들어보자. 나랑 내 친구 철수랑 그의 친구 영희랑 그의 오빠 영철이랑 네명이 각각 홈페이지를 갖고 있고 거기에 네이버 홈페이지, 이렇게 딱 다섯개의 웹페이지가 있는 공간을 생각해보자. 상식적으로 이 다섯개의 웹페이지에 링크들이 어떻게 서로가 서로를 가리키고 있을지 가정해보고, Random Surfer를 그 마르코프체인위에 올려놓고 돌아다니라고 해보자. 그리고 몇분후에 Stop했을때, 그 Random Surfer가 어디있을 가능성이 제일 클것같은가?

거의 예외없이 네이버홈페이지라 생각할 것이다. 왜냐하면 머리속에 그린 그림은, 네이버가 제일 화살표를 많이 받고 있었기 때문일 것이다. 대충 그렇다. 근데 꼭 많이 받고 있는다고 거기에 머물 확률이 제일 큰건 아니다. 여기서부터 이제 임의의 순간에 각 페이지에 머물러 있을 확률을 구하기 위한 몇가지 수학공식들이 나오게 되는 것이다. 

좀 더 수식적으로 깊이 이해하려면, 구글의 창업자 중 한명인 세르게이 브린이 직접 쓴 논문 (번역판) 이나, 기타 여러가지 강의자료 등을 직접 구해 읽어보는게 제일 좋을것이다. 

세 르게이 브린의 논문에는 Markov Chain이라는 용어가 언급도 되어 있지 않은데, 많은 사람들은 브린이 논문을 쓸 당시 Markov Chain에 대해서는 모르고 있었다는 얘기가 있다. 바꿔 말하면, Markov Chain에 대해 열심히 연구하던 사람들은 따로 있고, 세르게이는 그와 똑같은 생각을 해서, 시스템을 만들고 막대한 부를 거머쥐었다고나 할까~