베이즈 통계(번외): Markov Chains

(이 글은 몇 년 전에 포스팅한 (Bayes 학습)(6)마르코프 연쇄-(1)와 (Bayes 학습)(7)마르코프 연쇄-(2)을 합쳐서 재포스팅한 것임. 마르코프 연쇄에 관해서는 (Bayes 학습)(8) 마르코프 연쇄-(3)라는 글이 하나 더 있음)

학부나 대학원 수업에서 나는 마르코프 연쇄(Markov chains)에 관해 배운 적이 없다. 다만 대학원 재학시절 범주형 데이터 분석(categorical data analysis)을 혼자 공부하면서 책에서 스쳐 지나가듯이 읽었을 뿐이다.

그것은 나와는 전혀 관계가 없을 지식이고, 그것을 몰라도 내가 평생 동안 사회학자로서 사는 데 문제가 되리라 예상되지 않았다. 사회학에서는 횡단적 데이터(cross-sectional data)를 다루지 종단적 데이터(longitudinal data)는 거의 다루지 않는다. 그래서 경제학과는 달리 수업에서 시계열 데이터 분석(time-series data analysis)을 별로 가르치지 않는다. 그러니 마르코프 연쇄가 나의 관심에서 벗어나 있었던 것은 전혀 놀랍지 않다.

그러나 세월이 변했다. 지난 수십 년 동안 마르코프 연쇄는 온갖 분야에서 그것의 유용성을 드러냈다. 예컨대 구글의 검색 알고리즘인 페이지 랭크(PageRank)가 마르코프 모형을 사용하고 있고, 데이터 과학에서 마르코프 연쇄는 빼놓을 수 없는 부분이다. 오늘날 마르코프 연쇄 몬테카를로(Markov Chain Monte-Carlo, MCMC) 방법 없는 베이즈 추론은 상상하기 어렵다. 그것은 인공지능(Artificial Intelligence)의 원리인 기계학습(machine learning)에도 응용되고 있다. 이 정도면 데이터과학을 공부하는 학도가 마르코프 연쇄를 제대로 이해해야 함은 이론의 여지가 없어 보인다.

마르코프 연쇄는, 확률변수(random variable)가 어떤 상태(state)에 도달할 확률이 오직 바로 이전 시점의 상태(state)에 달려 있는 경우를 가리킨다. 만약 한 인터넷 사용자가 어떤 웹페이지에 있을 확률이 그 사람이 바로 직전에 어떤 웹페이지에 있었는가에 달려 있다면 인터넷 사용자의 웹페이지 방문은 마르코프 연쇄 모형을 따르고 있다고 말할 수 있다. 또 어떤 시점에서 한 청소년이 부모와 어떤 관계를 갖고 있는가가 그 바로 직전 시점에서 그 청소년이 부모와 어떤 관계를 갖고 있는가에 달려 있다면(더 이전에 그 청소년이 부모와 어떤 관계를 갖고 있었는가는 무시해도 될 정도라면), 청소년과 부모와의 관계는 마르코프 연쇄 모형을 따른다고 말할 수 있다.

마르코프 연쇄를 이해하는 가장 기본적인 개념은 상태(state), 추이(transition), 추이행렬(transition matrix), 추이도형(transition diagram), 의사결정 나무(decision tree), 정상 마르코프 연쇄(stationary Markov chain) 등이다. 그리고 행렬대수(Matrix algebra)에 관한 지식이 다소 필요하다.

마르코프 연쇄는 확률변수의 상태 변화(혹은 추이)에 대한 모형이다. 상태(state)는 물리적 위치, 심리적 상태, 재정적 상태, 경제적 상태, 정치적 상황, 시장 점유율, 사회적 관계 등 어떤 것이든 가리킬 수 있다. 그리고 특정 변수가 가질 수 있는 모든 상태를 상태 공간(state space), 변화가 멈춘 상태를 정상 상태(steady state 혹은 stationary state)라고 한다.

유튜브에 올라온 강의(Patrick JMT)의 사례를 가지고 살펴보자. 오렌지 쥬스(Brand A)를 생산하는 어떤 기업이 광고 캠페인을 전개해서 시장 점유율을 높이고자 한다. 광고를 시작하기 전 Brand A의 시장 점유율이 20%이고, Brand A에 관한 광고를 보고 어떤 사람이 계속 Brand A를 구입할 수도 있고, 다른 Brand 제품(Brand A’라고 하자)을 구입할 수도 있을 것이다. 어떤 사람은 다른 브랜드 제품을 사용하다가 광고를 보고 브랜드 A로 전환할 수도 있고, 그냥 그 브랜드 제품을 계속 사용할 수도 있을 것이다. 광고를 보고 브랜드 A를 마시던 사람이 계속 브랜드 A를 마실 확률이 0.9이고, 다른 브랜드 제품으로 갈아탈 확률이 0.1이며, 다른 브랜드 제품을 마시던 사람이 브랜드 A를 마시게 될 확률이 0.7이고, 그냥 기존의 브랜드 제품을 마실 확률이 0.3이라고 하자.  바로 그것이 소위 추이 확률(transition probability)로 표현된 광고의 효과이다. 이를 행렬로 표시하면,

이  행렬은 광고를 시작하기 전 오렌지 쥬스 시장에서의 Brand A(A)와 여타 제품(A’)의 시장 점유율을 나타낸다. (참고: 행렬 안에는 숫자만 들어가지만, .2와 .8이 무엇을 나타내는가를 보여주기 위해 A와 A’을 넣어서 표시했다. 다음에는 이라고만 표시하겠다.)

이 를 추이 행렬(transition matrix)라고 부른다. 그것은 광고의 효과를 나타내는 확률이기 때문에 광고 기간 동안 동일하다고 가정할 수 있을 것이다. (참고: 이 행렬에도 행(row)과 열(column)이 무엇을 나타내는가를 보여주기 위해 행렬 안에 A, A’를 넣었다. 행은 시작하는 상태를, 열은 도달하는 상태를 나타낸다. .9는 A가 A로 바뀌는(사실 A가 그대로 남는 경우) 확률, .1은 A가 A’으로 바뀌는 확률, .7은 A’가 A로 바뀌는 확률, 그리고 .3은 A’가 A’로 바뀌는 확률을 가리킨다. 이제 간단히 로만 표시하겠다.)

만약 매주 광고 효과를 시장점유율로 측정한다면, 광고가 나간 1주 후 Brand A의 시장점유율은 어떻게 될까? 그것은 아래와 같이 계산할 수 있다.

일주일 후 Brand A의 시장 점유율은 74%이다! 광고를 하고 일주일만에 시장점유율이 20%에서 74%로 오른 것이다. 그 다음 일주일 후에는 시장 점유율이 어떻게 될까?

84.8%가 되었다! 광고 효과가 여전히 놀랍다. 그렇다면 머지않아 Brand A는 오렌지 쥬스 시장을 싹쓸이 할 수 있을까?

광고 후 3주일째 Brand A의 오렌지 쥬스 시장의 점유율은 어떻게 될까? 아래 식에서 보는 것처럼 86.96%이다.

시장 점유율이 여전히 증가하고 있으나 첫 두 주만큼 인상적이지는 않다. 광고효과가 동일하다고 가정하면 광고 후 4주부터 10주째까지 Brand A의 오렌지 쥬스 시장의 점유율은 각각 아래와 같이 예상된다.

Brand A의 시장점유율은 광고 후 5주차에 87.50%(반올림한 결과)에 도달한 이후 10주차까지 미세한 증가가 있으나 반올림하면 여전히 87.50%이다! 즉, Brand A의 시장점유율은 광고 후 5주차에 거의 불변상태에 도달할 것으로 예상된다(이는 대단히 흥미 있는 현상이다). 따라서 Brand A의 시장점유율은 광고 후 초반의 급속한 증가에도 불구하고 그 증가 속도가 빠르게 감소되되기 때문에 결코 100%에 도달하지 못할 것으로 판단된다.

이 사례는 마르코프 연쇄에 있어 정상 상태(steady state, stationary state, invariant state)가 존재함을 보여준다. 마르코프 연쇄에서 정상 상태에 도달하는 과정을 정상 상태에 수렴한다(convergence)고 표현한다.

그렇다면 모든 마르코프 연쇄가 정상 상태의 특성을 갖고 있는가? 그것은 아니다. 추이행렬(transition matrix)이 정칙(regular)인 마르코프 연쇄(그것을 정칙 마르코프 연쇄, regular Markov chains라고 부른다) 같이 특정한 유형의 마르코프 연쇄만이 그러한 속성을 갖고 있다. 어떤 추이행렬의 거듭제곱한 결과가 오직 양의 원소(only positive entries)만을 지닌 행렬일 때 그 추이행렬은 정칙이다.

정칙 마르코프 연쇄는 다음과 같은 속성을 갖는다.

(1)   (는 정상 행렬, 는 추이행렬)   이 공식으로 정상 행렬(stationary matrix)을 구할 수 있다.

(2) 초기 행렬  에 어떤 값이 주어지든 상태 행렬들(state matrices) 는 정상 행렬 에 수렴된다.

(3)추이행렬의 거듭제곱  는 하나의 극한 행렬(limiting matrix) 에 수렴한다. 의 각 행(row)은 정상 행렬 와 같다.

 공식을 이용해서 위 광고의 정상 행렬을 구해보자.

이 식을 과 에 관해서 풀면 다음 두 식을 얻는다.

 —–(1)

 —–(2)

그리고  —–(3)

(1)식과 (2)식 중 하나와 (3)식을 가지면 과 를 구할 수 있다. (1)과 (3)을 가지고 풀자.

(3)의 양변에서 를 빼면, 

이 것을 (1)에 대입하면,

양변에서 를 더하고 0.9를 우변으로 옮기면,

양변을 0.8로 나누면,

 이 된다. 이 값을 (3)에 대입하면, 이 구해진다. 이 값들로 행렬을 구하면,  이다. 이를 소수로 전환하면 이다.

위에서 일일히 행렬 계산을 통해서 구했던 정상 행렬이 공식을 사용해서 훨씬 쉽게 구해졌다. 정상 행렬(stationary matrix). 정상 상태(stationary state), 정상 분포(stationary distribution)라는 개념들은 MCMC에 응용된다. (2020-11-19)