Data Analysis

마코프 행렬(Markov matrix)이란 무엇인가?

랭호(Langho) 2023. 3. 12.

들어가며

최근 팀에서 진행하는 업무 중에 분류된 유저 그룹 내에서 이동확률을 예측하기 위해 Markov matrix을 응용하는 업무가 있었다. 그리고 딥러닝에 대한 논문이나 자료에서 Markov chain, Markov decision process 등의 용어가 종종 나온다. 오늘은 앞에서 말했던 개념의 기초가되는 Markov matrix에 대해 알아 보겠다.

마코브 행렬과 마코브 체인

마코브 행렬(Markov matrix)은 1906년에 러시아의 수학자 Andrey Markov에 의해 처음으로 언급된 개념이다. 마코브 행렬은 마코브 체인(Markov chain)을 기술하기 위한 수학적 도구인데, 확률적 방법을 기반으로 하기 때문에 확률 행렬(stochastic matrix or probability matrix)로 불리기도 한다.

여기서 마코브 체인은 확률을 이용하여 어떤 객체 상태를 시간에 따라 어떻게 변화할지를 모델링(modeling)하는 것이다. 체인(chain)이라는 단어가 의미하듯이 객체의 시간에 따른 서로 다른 상태를 어떻게 연결할지를 기술하는 것이 마코브 체인이며, 이들을 연결시켜주는 매개체 역할을 마코브 행렬이 하는 것이다.

Markov matrix는 모든 요소가 0보다 크거나 같고, 각 열 벡터들의 요소들을 더하면 1이 되는 행렬이다. 마코브 행렬과 마코프 체인의 예를 아래의 그림을 통해 알아보자.

Fig. 1 삼성 갤럭시 핸드폰과 애플 아이폰의 시장 점유율 예측에 관한 마코브 체인 상태 전이 다이어그램(Markov chain state transition diagram)

Fig. 1은 물론 가상의 임의의 수치를 입력하였고, 삼성 갤럭시 핸드폰과 애플의 아이폰에 대한 시장 점유율을 마코브 체인으로 표현한 것이다.Fig. 1과 같은 도표를 마코브 체인 상태 전이 다이어그램(Markov chain state transition diagram)이라고 한다. 마코브 체인은 기본적으로 각 상태들이 다른 상태로의 전이(transition)가 얼마의 확률로 이루어질 것인가를 기술한다.

애플의 아이폰을 사용하는 것을 state 1, 삼성의 갤럭시 핸드폰을 사용하는 것을 state 2로 각각 정의했고, 각 상태가 다른 상태로 전이되는 행위를 화살표로 표시하였다. 상태전이는 자기 자신으로 될 수도 있는데, 아이폰의 경우 상태(state)가 자기 자신으로 전이되는 것은 현재 아이폰을 사용하고 있는 유저가 계속 아이폰을 사용하는 것을 의미한다.

우리가 이와 같이 마코브 체인을 구성한 이유는 앞선 문제의 경우엔 결국 핸드폰 사업에서 두 회사의 앞으로의 시장 점유율을 예측하기 위함이다. 마코브 방법을 이용하여 앞으로의 상태를 예측하기 위해선 먼저 위 그림과 같이 마코브 체인을 정의하고, 현재 시간의 상태와 그 다음 시간의 상태 사이를 연결시켜줄 수 있는 매개체인 마코브 행렬을 구해야한다.Fig. 1의 마코브 체인에 대한 마코브 행렬은 아래와 같다.

식 (1)의 좌측의 행렬 M이 바로 마코브 행렬(Markov matrix)이다. 행렬의 각 원소는 어떤 상태에서 자기 자신, 혹은 다른 상태로 전이될 확률값을 가진다.

행렬을 해석할 땐 column의 인덱스를 시작 상태로 보고, row의 인덱스를 전이 되는 상태로 보면 된다. 즉 M의 첫 번째 column인 Apple을 시작 상태로 봤을 때, 다시 Apple이 될 확률을 row 1로 보고 이때의 값은 0.714가 된다. Apple에서 Samsung으로 전이 될 확률은 row 2가 되며, 이때의 값은 0.286이다. 마찬가지로 두 번째 column인 Sam을 시작 상태로 봤을 때, Apple로 상태가 전이 될 확률은 row 1이 되고 그 값은 0.363이 되며, 다시 자기 자신인 Sam으로 될 확률은 row 2이고 값은 0.637이다.

식 (1)의 우측에 있는 u는 Fig. 1에서 Apple과 Samsung의 현재의 시장 점유율을 의미한다. 주어진 마코브 행렬의 우측에 u를 곱한 결과는 다음 시점에서의 시장 점유율의 예측값이 된다.

Markov matrix의 특성

Markov matrix는 모든 요소가 0보다 크거나 같고, 각 열 벡터들의 요소들을 더하면 1이 되는 행렬이다. Markov matrix인 A의 특성을 아래에 나열해봤다.

첫번째 고유값은 항상 1이다.
첫번째 고유벡터는 steady state이다.
다른 고유값들의 절대값은 1보다 작거나 같다.

하나의 예를 통해 이 특성들을 확인해보자. 아래와 같은 상황이 있다.

"매년 서울의 인구 중 10%는 부산으로 이동하고, 부산 인구의 20%가 서울로 이동한다. 현재 서울의 인구가 1000만, 부산의 인구가 400만이라고 하면 100년 후의 두 도시의 인구는 어떻게 될 것인가? (단, 서울, 부산에서 다른 도시로 인구의 이동은 없고, 다른 도시들에서 서울, 부산으로 인구의 이동도 없다.)"

이를 식으로 아래와 같이 나타낼 수 있다.

여기서 S0는 현재의 서울 인구, B0는 현재의 부산 인구, S1은 1년 후의 서울 인구, B1은 1년 후의 부산 인구를 나타낸다. 행렬을 이용하면, 아래와 같이 정리된다.

여기서 행렬

는 Markov matrix이다. 모든 요소가 0보다 크거나 같고, 각 열의 요소를 더했을 때 1이 되기 때문이다.

만약 행렬 A가 대각화가 가능하다면, 행렬의 대각화를 이용해서 이 차분방정식을 풀 수 있다. 대각화 가능의 조건은 행렬 A가 서로 독립인 n개의 고유벡터들을 갖는 것이다.

고유값들과 고유벡터들을 구해보면,

이 된다. 구한 고유값들을 보니 하나는 1이고 하나는 1보다 작다(특성1과 특성3). 또한 첫번째 고유벡터는 음이 아니고 steady state다.

두 고유 벡터가 서로 선형 독립이므로, 우리는 행렬의 대각화를 이용해서 위의 차분방정식을 풀 수 있다.

최종적으로 100년 후의 서울의 인구는 약 933만명이 되고, 부산의 인구는 약 466만명이 된다. 서울의 인구는 감소했고, 서울의 인구가 감소한 만큼 부산의 인구는 증가했다.

마치며

오늘은 마코브 행렬과 마코브 체인에 대해 알아봤다. 마코브 행렬은 기본적으로 확률을 기반으로 한 상태 전이 행렬이며, 어떤 상태의 변환 이후에도 상태의 총량은 유지된다는 특성이 있다. 상태 전이 과정에서 다른 시점에서의 상태와는 무관하고 오직 바로 이전상태에만 영향을 받는다는 것이다. 예측을 함에 있어 그 전전 상태까지 고려하는 2차 마코브 체인 등도 있지만 1차가 가장 보편적으로 사용된다.