[Sampling] Markov Chain Monte Carlo (MCMC) (1) - Markov chains

 

Motivation

(앞에서와 마찬가지로) Monte-Carlo method로 기댓값을 근사하고 싶다.

\[ \cfrac{1}{n} \sum_{i=1}^{n} f(x_i) \overset{\text{a.s.}}{\to} \mathbb{E}_{p(x)}[f(x)], \quad x_1, \dots, x_n \overset{\text{i.i.d.}}{\sim} p(x) \]

 

rejection sampling과 importance sampling은 $p(x)$ 대신 샘플링이 쉬운 $q(x)$를 이용했다. (indirectly sample from distributions easier to sample)

 

그러나 i.i.d. 샘플링은 고차원 데이터(high-dimensional data)에는 적합하지 않다. 

이전 샘플을 통해 현재 새로운 샘플을 추출하는 방법을 고안하게 된다.

반응형

Markov chains

sequence of random variable $(x^{(t)})_{t \ge 1}$에 대하여, 오직 직전 상태에만 고려하면 markov chain이라 한다.

\[ \mathbb{P}(x^{(t+1)} | x^{(1)}, \dots, x^{(t)}) = \mathbb{P}(x^{(t+1)} | x^{(t)}) \]

 

이런 정의 때문에 markov chain은 memoryless discrete time process라고도 불린다.

 

inition distribution: $p_1(x) = \mathbb{P}(x^{(1)} = x)$

transition probability (전이 확률): $T_t(x'|x) = \mathbb{P}(x^{(t+1)}=x' | x^{(t)}=x)$ for $t \ge 1$

 

Homogenouse Markov chains

transition probability가 $t$에 독립이면 homogeneous라고 한다. 즉

\[ T_1(x'|x) = T_2(x'|x) = \cdots = T(x'|x) \]

또는 이렇게도 표현하기도 한다.

\[ T_{ij} = \Pr(x^{(t+1)} = j | x^{(i)}=i) \]

 

Transition probability는 아래에 더 자세히 설명한다.

※ 앞으로 (그리고 대부분의 경우) 특별한 언급이 없으면 homogeneous markov chain이라고 가정한다.

 

Discrete State Space

Markov chain의 확률변수가 무한 가산(countably infinite)하다면 discrete state space를 갖는다고 한다.

편의상 음이 아닌 정수로 discrete state space를 표현한다. ($\{ 1, 2, 3, \dots \}$)

※ 확률변수를 $0$부터 시작하여 표기할 수 있다.

Finite State Space

Markov chain의 확률변수가 유한집합이면 finite하다고 한다.

편의상 음이아닌 집합으로 표현한다. ($\{ 1, 2, \dots, n \}$)

※ 확률변수를 $0$부터 $n-1$로 표현할 수 있다.

 

 

Transition Probability

transition probability는 markov chain을 결정한다.

이번 포스팅에서는 finite-space에서 정의하고 $E=\{ k \}_{k=1}^{S}$ 로 표기하여 markov chain을 probability vector로 표현할 수 있고 다음과 같다.

\[ p_1 \in \mathbb{R}^{S}: \ p_{1,k}=\mathbb{P}(x^{(1)}=k) \]

 

transition probability 역시 matrix로 표현하면 다음과 같다. ($T_{ij}$는 $i$에서 $j$로 전이되는 확률이다.)

\[ T \in \mathbb{R}^{S \times S} : \ T_{ij} = \mathbb{P}(x^{(t+1)}=j|x^{(t)}=i) \]

 

Multiple Step Transition Probability

양수 $m$ (확률변수에 따라 음이 아닌 수)에 대하여 m-step transition probability를 정의할 수 있다. state가 $i$에서 $j$로 전이되는데 정확히(exactly) $m$번 전이되는 확률이다.

\[ T_{ij}^{m} = \Pr(x^{(t+m)}=j | x^{(t)}=i) \]

 

Accessible States

$T_{ij}^{n} > 0$을 만족하는 어떤 정수 $n \ge 0$가 존재하면 $i$ 에서 $j$로 accessible하다고 한다.

두 state $i$와 $j$가 서로 accessible하다면, communicate라고 하며 $i \leftrightarrow j$ 로 표기한다.

 

Irreducible Markov Chains

모든 state들이 하나의 communication class에 속하면 markov chain은 irreducible하다고 한다.

반대로, 2개 이상의 communication class가 있다면 markov chain은 reducible하다고 한다.

 

irreducible markov chain은 모든 state들이 서로 도달할 수 있다는 것을 의미한다.

수식으로 표현하면 다음과 같다.

finite-state markov chain에서, 모든 $i,j \in E$에 대하여 $T_{ij}^{n_{ij}} > 0$인 $n_{ij} < \infty$가 존재하면 irreducible하다고 한다.

Example of Irreducible; Left: reducible, Right: irreducible

좌측 markov chain의 경우, state $2$에서 어떠한 state로도 도달할 수 없다. 따라서 reducible하다.

우측 markov chain의 경우, 모든 state에서 어떠한 state로 도달할 수 있다. 따라서 irreducible하다.

(이미지 출처) https://people.engr.tamu.edu/andreas-klappenecker/csce658-s18/markov_chains.pdf

Period and Aperiodic

state $k$의 period는 다음과 같이 정의한다. 

\[ d_k = \text{gcd} \{ n | T_{kk}^n > 0 \} \]

※ $d(k)$ 또는 $d_k$로 표기한다.

state $k$는 모든 $d_k$ step마다 되돌아올 수 있다는 것을 의미한다.

 

모든 state들이 $d_k=1$이면 주어진 markov chain은 aperiodic 이라 한다. (no period, no pattern)

Example for Period

4개의 state들의 period는 $d_0=d_1=d_2=d_3=1$이므로 aperiodic markov chain이다.

 

Invariant (stationary) distributions of Markov chains

어떤 분포 $\pi(x)$가 다음을 만족하면 invariant distribution이라 한다.

\[ \pi(x) = \int \pi(x')T(x|x') dx' \]

 

Detailed balance

Markov chain이 $\pi$에 대하여 다음을 만족하면 detailed balance라고 한다.

\[ \pi(x)T(x'|x) = \pi(x')T(x|x') \]

이러한 Markov chain은 time-reversible하다고 한다. 또한 위 성질을 만족하는 Markov chain의 $\pi$는 invariant distribution이다. 

 

$\int \pi(x)T(x'|x) dx' = \pi(x) \int T(x'|x) dx' = \pi(x) \cdot 1 = \pi(x)$

 

invariant distribution $\pi \ \mathbb{R}^{S}$ 역시 probability vector로 나타낼 수 있고 $\pi = T \pi$를 만족한다.

Basic idea of Markov chain Monte Carlo (MCMC)

MCMC를 이용한 $\mathbb{E}_{p(x)}[f(x)]$를 근사하는 방법은 다음과 같다.

• $p(x)가 invariant distribution이 되도록 Markov chain을 만든다.
• Markov chain으로부터 $(x^{(t)})_{t \ge 1}$을 샘플링한다. (how?)
• Monte Carlo 근사를 계산한다. 

\[ \cfrac{1}{n}\sum_{t=1}^{n}f(x^{t}) \approx \mathbb{E}_{T^n p_1(x)}[f(x)] \approx \mathbb{E}_{p(x)}[f(x)] \]