Background: Markov Chain
2 minute read

Definition

연속되는 확률변수 $X_1, X_2, \dots X_n$을 가정해보자. 이때 각 $X_i$의 $i$는 연속되는 시간속의 시점을 나타내고, 시점은 $1$부터 $n$까지 존재한다. 그리고 우리는 이 모든 사건이 동시에 일어날 확률을 알고싶다. 즉 전체 시퀀스(sequence)의 Joint Probability를 계산해야하는 것인데, 여기서 Chain Rule of Probability를 이용하면 총 교사건의 확률을 다음과 같이 계산할 수 있다.

$$p(X_1, X_2, \dots X_n) = p(X_1) \cdot p(X_2\mid X_1) \cdot p(X_3 \mid X_2, X_1) \cdot \dots \cdot p(X_n \mid X_{n-1}, X_{n-2}, \dots, X_2, X_1)$$

이 식에서는 어떤 시점에 일어난 사건 $X_t$의 확률이 그 이전에 일어난 모든 사건에 영향을 받는다.

이때 마코프 체인(Markov Chain)은 여기에 마코프 가정(Markov Assumption)을 추가시켜 이 과정을 단순화시킨 것이다. 마코프 가정은 확률변수의 총 시퀀스가 주어졌을때, 어떤 확률변수 $X_t$의 분포는 바로 직전에 나타난 확률변수 $X_{t-1}$에만 의존한다는 것이다. 즉, $X_{t-1}$가 $X_1$부터 $X_{t-2}$까지의 역사도 전부 포함하고 있다고 가정하는 것이다. 아래의 수식은 이 가정을 표현하고 있으며 모든 $t = 2, \dots, n$에 대해 성립한다.

$$p(X_{t+1} \mid X_t, X_{t-1}, \dots , X_2, X_1) = p(X_{t+1}\mid X_t)$$

$X_t$ captures all relevant information for predicting the future.

여기서 퀴즈.

주사위를 던지는 것과 같이 모든 시행이 독립적이고, 동일한 확률분포를 가지고 이루어지는 i.i.d.(independent, and identically distributed) 사건 $X_1, X_2, \dots X_n$은 마코프과정일까?

정답은 ‘그렇다’이다.

확률과정 ${X_n, n \geq 1}$이 독립과정이면

이므로 엄밀히 말하면

$P(X_{n+1} \mid X_1=x_1, \dots, X_n = x_n) = P(X_{n+1} \mid X_n = x_n)$

라는 Markov Chain의 정의가 성립하기 때문이다.

그리고 이 정의를 이용해 전체 사건의 Joint Probability를 좀 더 간단한 식으로 구할 수 있다.



이 식은 initial distribution, 최초의 사건이 가지는 확률분포 $p(X_1)$ 하나와 $p(X_t\mid X_{t-1})$의 꼴을 한 $(n-1)$개의 transition probability로 이루어져있다.

여기서 추가적으로 ‘Transition Probability는 시간에 따라 변하지 않는다’는 가정이 하나 더 붙는다. 다시 말해 시점 $t$에서 $t+1$로의 transition은 오직 $X_t$의 에 의해서만 결정된다는 것이다. 오늘 비가 왔을 때 내일 비가 오지 않을 확률이나, 다음주 목요일날 비가 왔을 때 그 다음날 비가 오지 않을 확률이 같다는 것이다. 그리고 이 성질은 마코프 체인이 time-invariant / stationary / homogeneous 하다는 말로도 표현된다.

결국 $p(X_2\mid X_1), \dots p(X_n \mid X_{n-1})$ 은 transition probability $(n-1)$개가 다른 시점에 나타났을뿐 같은 모수를 공유하는 확률변수라는 것인데, 이 점에 주목해 이 과정을 ‘parameter tying’이라고도 한다.

모든 상태에 대한 Transition Probability를 담고 있는 행렬을 Transition Matrix $(T)$라고 한다. 가능한 상태의 수가 $k$일때 $T$는 $k \times k$ 행렬이 되는데, 행은 출발상태, 열은 도착상태를 나타낸다. 따라서 $T_{1,2}$는 상태 1에서 상태 2로 전이될 확률이 된다.

날씨의 세 상태를 {sun, cloud, rain} 라고 한다면, 날씨에 대한 transition matrix는 다음과 같이 표현될 수 있다.

날씨에 대한 transition matrix

이때 각 행의 합이 $1$이라는 것에 주목하자. 이 성질을 따라 transition matrix를 stochastic matrix라고도 한다.


번역에 참고한 원글 출처 : Coursera의 Bayesian Statistics: Techniques and Models 강의 자료

그외 참고문헌
<Machine Learning: A Probabilistic Perspective>, Kevin P. Murphy

Recent Posts

Lazy learning vs Eager learning
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Perplexity of Language Models
Matrix Calculus
Inverted Indexing