markov chain(마르코프 체인) 이해하기

작성자:김정민 

monthly 세미나이긴 한데 방학중에 이런 수학적 내용을 공부해보고 싶어서 

준비해보았습니다. 강화학습에 사용되는 마르코프 의사결정? 이라는 내용이 있었는데 

전에 논문리뷰할 때도 마코프 체인 이야기가 나와서 찾아본적이 있습니다. 

그 때 이해가 가지 않아서 조사해보았는데 어렴풋이 이해가 가는것 같습니다. 

 

 

우선 대수의 법칙을 아실겁니다. 

동전을 무한번 던지면 반반 정도의 확률로 결국 수렴하게 되는 그 이론

중심 극한 정리(中心 極限 定理, 영어: central limit theorem, 약자 CLT)는 동일한 확률분포를 가진 독립 확률 변수 n개의 평균의 분포는 n이 적당히 크다면 정규분포에 가까워진다는 정리이다. 

 

콩이 떨어지고 있는데 하나의 콩이 떨어져서 분포하는것은 독립적인 사건이라고 생각할 수 있다.

검은콩과 흰색콩 3000개와 2000개를 넣고 섞은 후에 무한번 뽑았다가 다시 넣었다가를 반복하면 확률은 40퍼센트와 60퍼센트로 수렴하게 될것이다.

이것은 마치 동전 던지기와 비슷하다고 할 수 있는데 

콩이 떨어질 때 동전 던지기 처럼 이전의 사건의 영향을 받지 않는 독립 사건이고

무한히 시행했을 때 어떤 정확한 비율로 수렴한다는 것 이었다.

 

모든 사건의 관찰이 전체 무한대로 계속된다면, 세계의 모든 것이 정확한 비율과 지속적인 변화 법칙에 의해 지배된다는 것을 알 수 있었다. 

 

이에 네크로소프는 대수의 법칙에서 사건의 독립성은 필수적이라고 주장했습니다.

일상 생활에 일어나는 일들은 이전 사건의 영향을 받는 종속사건일 경우가 많습니다.

이에 마르코프는 대수의 법칙을 종속사건으로 까지 확장할 수 있는 아이디어를 내놓게 됩니다.

 

검은콩과 흰콩이 들어가 있고 검은콩이 나오면 0에서 시작하고 흰콩이 나오면 1에서 다시 시작하는것입니다.

이렇게 모델을 구현했을 때 검은돌 혹은 흰돌이 뽑힐 확률은 이전사건의 영향을 받기 때문에  독립적이지 않습니다.

하지만 이 모델을 계속 시행했을 때 검은돌과 흰돌이 뽑힐 확률은 평형을 유지하게 됩니다.

 

 

독립성이 있는 사건들만이 예측 가능한 분포에 수렴한다는 주장은 잘못된것

독립성이 보장되지 않는 사건들도 예측 가능한 분포에 수렴할 수 있다.

 

사건의 확률을 행렬로 표현할 수 있다.

 

 

 

 

A Markov process is a stochastic process that satisfies the Markov property[1] (sometimes characterized as "memorylessness"). In simpler terms, it is a process for which predictions can be made regarding future outcomes based solely on its present state and—most importantly—such predictions are just as good as the ones that could be made knowing the process's full history.[11] In other words, conditional on the present state of the system, its future and past states are independent.

 

간단히 말해 현재 상태만을 기반으로 미래의 결과에 대해 예측할 수있는 프로세스이며,

가장 중요한 것은 이러한 예측이 프로세스의 전체 history를 아는 것만큼의 예측을 할 수 있다는 것이다.

이것은 인공지능 분야에서 '마르코프 체인 몬테 카를로'으로 확장해서 이용한다는데.. 다음 시간에 다뤄보도록 하고

 

 

마코프 프로세스 예제

과거 상태가 미래 상태에 전혀 영향을 미치지 않고, 오로지 현재 상태만 미래 상태에 영향을 끼치기 때문에 현재 시장의 상황을 마코프 체인으로 나타낼 수 있다.

이렇게 진행된다면 삼성은 무엇인가 조치를 취해야 하지 않을까? 마코프 체인이 유용하게 사용되는 경우를 예제를 들어서 설명해보았다.

마코프 과정은 어떤 상태가 일정한 간격으로 변하고, 다음 상태는 현재상태에만 의존하며 확률적으로 변하는 경우의 상태의 변화를 뜻한다. 즉, 현재 상태에 대해서만 다음 상태가 결정되며, 현재 상태에 이르기까지의 과정은 전혀 고려할 필요가 없다.

마코프 과정에서 연속적인 시간 변화를 고려하지 않고, 이산적인 경우만 고려한 경우를 마코프 연쇄(Markov Chain) 이라고 한다.

 

이렇게 전체 hisory를 알지 않아도 다음 상태를 예측할 수 있기 때문에 비용자체가 cheap하기 때문에 인공지능 분야에서 선택되는것 같습니다.

마코프 체인.pptx

9.08MB