Markov Chains

본 글은 Setosa blog의 글을 이용하여 번역 및 재해석한 것이다.

Andrey Markov의 이름을 딴 Markov chain은 하나의”상태” (state; a situation or set of values) 에서 다른 상태로의 이동/전이를 나타내는 mathematical systems을 말한다. 예를 들며, 어린유아의 행동에 대한 Markov chain model을 만든다면, 상태로는 “playing,” “eating”, “sleeping,” 그리고 “crying” 등을 사용할것이고, 이 상태들로 이루어진 state space(a list of all possible states)를 생각해 볼 수 있다. 이와 더불어, state space상에서 Markov chain은 한 상태에서 다른 상태로의 이동 또는 전이(transitioning)할 확률(probabilitiy)에 관한 정보를 제공해 준다.

간단한 two-state Markov chain은 다음과 같이 나타낼 수 있다.

State space상에 두 개의 states (A and B)가 있다면, 총 4개의 가능한 transitions (not 2, because a state can transition back into itself)가 존재 한다. 위 그림 오른쪽에는 어느 상태에서 다른 상태로의 전이확률(probability of transitioning)을 나타낸 것이다. 이 확률에 근거해서 다른 상태로 전이하게 된다. 이러한 확률값들은 “transition matrix” 형태로 확률값을 표현 할 수 있다. 매트릭스 상의 확률값에 해당하는 상태의 전이는 row 상태에서 column상태로의 전이로 해석한다.

Markov chains을 여기에 소개하는 이유는 computer simulation을 통해 real-world phenomena 를 해석할 때 사용되기 때문이다. 예를 들어, 날씨(rainy (R) and sunny (S))에 따라 댐이 넘칠 빈도에 대해 알아 보고자 할 때, 맑은 날과 비가 오는 날의 확률이 각각 0.5라고 가정해보자. 이 때, 이 확률값에 따라 computer simulation을 하게 되면 무작위로 확률에 따라 sunny day와 rainy day값을 생성시킬 것이다. 그러나 실제 상황을 고려해 보면, 날씨가 맑으면 계속 맑을 가능성이 크고, 비가 오면 계속 비가 내릴 확률이 커진다. 즉 한상태에서 다시 그상태로 돌아 갈 확률이 더 높다는 것이다. 전체적으로 보면 rainy day와 sunny day가 가정된 확률 값(0.5)에 수렴하지만, 부분적으로 rainy day에서 sunny day로의 전이 확률은 0.5가 아니라는 의미이다(우리는 경험적으로 이 확률값이 0.5보다 낮다는 것을 안다). 반대로 rainy day에서 다시 rainy day로 갈 확률은 평균확률값(0.5) 보다 높다. 이러한 상태의 “stickyness”는 Markov chain으로 표현 할수 있는 것이다.

 

markov-chain-with-sequence

우리 주변에서 일어나는 여러 현상을 모델링해야 하는 연구자들에게, Markov chains은 매우 유용한 개념일 뿐아니라 강력한 도구이기도 하다. 예를 들어Google이 검색결과의 순서(PageRank)를 결정할 때 사용하는 것이 일종의 Markov chain이다. 이와 더불어, 강화학습(Reinforcement Learning)의 연구에 필요한 기본개념중의 하나로 state space를 정의할 때 필요한 것이 이 개념이다.

 

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중