[강화학습] 마코프 프로세스(=마코프 체인) 제대로 이해하기

Research/ML, DL

[강화학습] 마코프 프로세스(=마코프 체인) 제대로 이해하기

bskyvision.com 2019. 10. 15. 12:49

이 포스팅은 어느 카테고리에 넣어야할지 고민이 된다. 확률과도 관련이 있고, 딥러닝의 강화학습과도 관련이 있고, 영상처리의 몇몇 알고리즘에서도 사용되기 때문이다. 짧은 고민 끝에 머신러닝, 딥러닝 카테고리에 넣기로 결정했다.

마코프 프로세스

마코프 프로세스(Markov process, MP)는 마코프 특성(Markov property)을 지니는 이산시간(discrete time) 확률과정(stochastic process)이다. 낯선 단어들에 당황하지 말고, 주요 단어들을 하나하나 살펴보자. 먼저 확률 과정은 시간에 따라 어떤 사건이 발생할 확률이 변화하는 과정을 의미한다. 이산시간은 시간이 연속적으로 변하지 않고 이산적으로 변함을 의미한다. 마코프 특성은 과거 상태들($s_1$, $s_2$,...,$s_{t-1}$)과 현재 상태($s_t$)가 주어졌을 때, 미래 상태($s_{t+1}$)는 과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다는 것을 의미한다. 다른 말로 표현하면, 과거와 현재 상태 모두를 고려했을 때 미래 상태가 나타날 확률과 현재 상태만을 고려했을 때 미래 상태가 발생할 확률이 동일하다는 것이다[1]. 이를 식으로 나타내면 다음과 같다.

$P[s_{t+1}|s_t] = P[s_{t+1}|s_1,\cdots , s_t]$

마코프 프로세스는 이처럼 과거 상태를 기억하지 않기 때문에 메모리리스(memoryless) 프로세스로 불린다. 또한 마코프 프로세스는 마코프 체인(Markov chain, MC)이라 불리기도 한다.

어떤 상태에서 다음 단계의 상태로 변화하는 것을 변이라고 하고, 그 확률을 상태변이확률(state transition probability)이라 한다. 시간 t에서의 상태를 s라고 하고, 시간 t+1에서의 상태를 s'이라고 할 때, 상태변이확률은 다음과 같이 나타낸다.

$P_{ss'}=P[s_{t+1}=s'|s_t=s]$

나의 하루를 마코프 프로세스로 나타내보자

내 일상을 마코프 프로세스(마코프 체인)로 표현해보려고 한다. 나의 일과를 연구, 독서, 과외, 웹서핑, 취침만으로 구성되어있다고 가정하자. 따라서 5가지의 상태가 있는 마코프 프로세스로 표현될 수 있다. 일반적으로 상태는 원으로 표기하고, 종료(terminal) 상태는 사각형으로 나타낸다. 종료 상태에 들어가면 다른 상태로의 이동은 더이상 없다.

위 마코프 체인에 한 상태에서 다른 상태로 변이하는 확률들을 모두 나타내었다. 예를 들어 연구 상태에서 독서 상태로 이동하는 상태변이확률을 0.3, 연구 상태에서 웹서핑으로 이동하는 상태변이확률을 0.4, 연구 상태에서 과외 상태로 이동하는 상태변이확률을 0.3으로 나타냈다. 여기서 주목할 것은 한 상태에서 다른 상태들로 변이할 확률의 합은 1이라는 것이다. 어떤 상태의 출력의 합은 1이지만, 입력의 합은 다양하다.

이 마코프 프로세스를 하나의 행렬로 나타낼 수 있다. 그것을 바로 상태변이확률 행렬이라고 부른다.

상태변이확률 행렬을 보면 모든 요소가 0이상이고 각 행의 요소를 더하면 모두 1이 된다는 것을 알 수 있다. 내 삶을 마코프 체인으로 나타낼 수 있고, 또 하나의 행렬로 나타낼 수 있다는 것이 흥미롭지 않은가?

마코프 프로세스 예제

마코프 프로세스를 좀 더 깊이있게 이해하기 위해 또다른 예를 하나 살펴보자. 어느 나라에 가더라도 꼭 있는 것이 있는데 그것은 바로 콜라다. 콜라에 있어서는 코카콜라와 펩시콜라가 전세계를 주름잡고 있다. 현재 시장의 상황이 아래와 같다고 가정하자.

이번 주에 코카콜라를 사마신 사람의 80%가 다음 주에도 역시 코카콜라를 사마신다. 나머지 20%는 마음이 바뀌어 펩시콜라를 사마신다.

이번 주에 펩시콜라를 사마신 사람의 70%가 다음 주에도 역시 펩시콜라를 사마신다. 나머지 30%는 마음이 바뀌어 코카콜라를 사마신다.

이번 주에 10억명이 코카콜라를 마셨고, 8억명이 펩시콜라를 마셨다고 할 때, 10주 후와 50주(약 1년) 후에 코카콜라, 펩시콜라를 마시는 인구는 각각 어떻게 될까? (전세계에서 콜라를 마시는 인구는 18억명이라고 가정했고, 또한 비(非)콜라인 중에 새롭게 콜라를 마시기 시작하는 사람은 없다고 가정했다.)

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

이를 상태변이확률 행렬로 나타내면 다음과 같다.

n주 후 코카콜라를 구매하는 인구를 $Coca_n$, 펩시콜라를 구매하는 인구를 $Pepsi_n$이라고 나타내겠다. 이번주에 코카콜라를 사마신 인구가 10억이고, 펩시콜라를 사마신 인구가 8억이므로 $Coca_0 = 10$, $Pepsi_0 = 8$이 된다. 그러면 1주 후 코카콜라를 사마시는 인구와 펩시콜라를 사마시는 인구는 각각 식으로 어떻게 표현할 수 있을까? 우선 1주 후 코카콜라를 사마시는 인구는 이번주에 코카콜라를 사마신 인구의 80%와 이번주에 펩시콜라를 사마신 인구의 20%이므로 다음과 같이 나타낼 수 있을 것이다.

$Coca_1 = 0.8Coca_0 + 0.3Pepsi_0$

마찬가지로 1주 후에 펩시콜라를 사마신 인구는 이번주에 코카콜라를 사마신 인구의 20%와 이번주에 펩시콜라를 사마신 인구의 70%이므로 다음과 같이 표현 가능하다.

$Pepsi_1 = 0.2Coca_0 + 0.7Pepsi_0$

이 두 식을 모아서 행렬의 형태로 나타내보자.

$\begin{bmatrix}
Coca_1 & Pepsi_1
\end{bmatrix}
=
\begin{bmatrix}
Coca_0 & Pepsi_0
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}$...(1)

우변에 오른쪽 정방행렬이 상태변이확률 행렬과 같음에 주목하자.

이번에는 2주 후에 코카콜라와 펩시콜라를 사마신 인구가 어떻게 되는지 살펴보자. 2주 후의 상태는 1주 후의 상태에만 영향을 받으므로 다음과 같이 나타낼 수 있다.

$\begin{bmatrix}
Coca_2 & Pepsi_2
\end{bmatrix}
=
\begin{bmatrix}
Coca_1 & Pepsi_1
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}$...(2)

3주 후의 상태는 역시 2주 후의 상태에만 영향을 받는다.

$\begin{bmatrix}
Coca_3 & Pepsi_3
\end{bmatrix}
=
\begin{bmatrix}
Coca_2 & Pepsi_2
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}$...(3)

여기서 흥미로운 점은 식(3)에 식(2)를 대입시키고, 또한 이어서 식(1)을 대입시키면 현재 상태와 상태변이확률 행렬만을 이용해서 3주 후의 상태를 나타낼 수 있다는 것이다.

$\begin{align*}
\begin{bmatrix}
Coca_3 & Pepsi_3
\end{bmatrix} &= \begin{bmatrix}
Coca_2 & Pepsi_2
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}
\\
&= \begin{bmatrix}
Coca_1 & Pepsi_1
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}
\\
&= \begin{bmatrix}
Coca_0 & Pepsi_0
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}
\\
&= \begin{bmatrix}
Coca_0 & Pepsi_0
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}^3
\end{align*}$

이것을 n주 후로 일반화하면 다음과 같다.

$\begin{bmatrix}
Coca_n & Pepsi_n
\end{bmatrix}
=
\begin{bmatrix}
Coca_0 & Pepsi_0
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}^n$

자, 그러면 이제 n대신에 10을 대입하면 10주 후의 코카콜라인구와 펩시콜라인구를 예측할 수 있고, 50을 대입하면 50주(약 1년) 후의 상태를 예측할 수 있다.

$\begin{bmatrix}
Coca_{10} & Pepsi_{10}
\end{bmatrix}
=
\begin{bmatrix}
10 & 8
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}^{10} = \begin{bmatrix}
10.7992 & 7.2008
\end{bmatrix}$

이와 같이 10주 후에 코카콜라 인구는 10억 7천9백9십2만명이 되고, 펩시콜라 인구는 7억 2천8만명이 된다. 코카콜라 인구는 늘었고, 펩시콜라 인구는 줄어들었다. (참고로 나는 매틀랩을 이용해서 정방행렬의 거듭제곱을 계산했는데, 고유값 분해를 이용해서 충분히 손으로도 계산이 가능하다. 이에 관해서 더 자세한 사항은 예전 포스팅 https://bskyvision.com/127를 참고하자.)

$\begin{bmatrix}
Coca_{50} & Pepsi_{50}
\end{bmatrix}
=
\begin{bmatrix}
10 & 8
\end{bmatrix}
\begin{bmatrix}
0.8 & 0.2\\
0.3 & 0.7
\end{bmatrix}^{50} = \begin{bmatrix}
10.8 & 7.2
\end{bmatrix}$

그리고 50주 후에는 코카콜라 인구가 10억 8천만명이 되고, 펩시콜라 인구는 7억 2천만명이 된다. 코카콜라 인구는 조금 더 늘었고, 펩시콜라 인구는 그만큼 줄어들었다.

매주 콜라인구에 어떤 변화가 일어나는지 알기 위해 n을 0에서부터 50까지 1단위로 증가시킨 결과를 그래프로 나타내보았다.

이 그래프를 통해 확인할 수 있는 것은 약 5주만 지나도 일정한 값들로(10억 8천만 명, 7억 2천만 명) 수렴한다는 것이다. 결론적으로 펩시콜라 인구중 8천만명의 사람이 코카콜라로 유입된다는 것을 알 수 있다. 코카콜라 회사에 있어서는 좋은 일이고, 펩시콜라 회사 입장에서는 손실을 겪게 된다. 이러한 위기를 타계하기 위해 펩시콜라 회사는 적절히 손을 써야할 것이다.

위 그래프를 그리기 위해 나는 다음과 같이 매틀랩 코드를 작성했다.

clc, clear, close all

Coca_0 = 10;
Pepsi_0 = 8;

P = [0.8 0.2; 
    0.3 0.7]; 

figure,

plot(0, Coca_0, 'bo', 'MarkerFaceColor', 'b')
grid on
hold on
plot(0, Pepsi_0, 'r^', 'MarkerFaceColor', 'r')

for n = 1:50
    population = [Coca_0 Pepsi_0]*(P^n);
    plot(n, population(1), 'bo');
    plot(n, population(2), 'r^');
end

xlabel('n')
ylabel('population')
axis([0 50 5 12])
legend('coca', 'pepsi')

마코프 프로세스(Markov process, MP)에 "보상"의 개념을 추가하면 마코프 보상 프로세스(Markov reward process, MRP)가 되고, 마코프 보상 프로세스에 "행동"의 개념을 추가하면 마코프 디시즌 프로세스(Markov decision process, MDP)가 된다. 마코프 디시즌 프로세스를 푸는 것이 강화학습의 핵심이다. 조만간 마코프 보상 프로세스와 마코프 디시즌 프로세스에 관한 글도 쓰도록 하겠습니다.

여기까지 잘 읽어주셔서 감사합니다! 도움이 되셨다면 공감 혹은 댓글 부탁드립니다^^

<참고자료>

[1] 김의중 지음, "알고리즘으로 배우는 인공지능, 머신러닝, 딥러닝 입문", 위키북스(2016)

[2] https://ko.wikipedia.org/wiki/%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84_%EC%97%B0%EC%87%84, 위키백과, "마르코프 연쇄"

[3] https://sumniya.tistory.com/3?category=781573, 숨니야, "[ch.2] Markov Decision Process"

[4] https://rfriend.tistory.com/184, R Friend, "[선형대수] 마아코프 과정, 대각화 적용하여 계산하기"

저작자표시 비영리 변경금지