MCMC
mcmc란 markov chain monte carlo (마르코프 연쇄 몬테카를로 Markov chain에 기반한 확률분포로 부터 원하는 분포를 갖는 표본을 추출하는 알고리즘이다.
- Generative model $p(x)$
- $E_{x \sim p(x)}[f(x)] \approx \frac{1}{N} \sum_1^N f(x) $
Rejection sampling
분포를 잘 알 수 없는(표본을 쉽게 뽑을 수 없는) $f(x)$와 분포를 잘 아는(표본을 쉽게 뽑을 수 있는) $g(x)$가 있을때, $g(x)$를 이용해 $f(x)$를 샘플링하는 방법이다.
$f(x_1) < cg(x_2)$ 를 만족하는 $c$를 취한다.
임의의 점 $x_t$에 대해 $e(x_t) = 0.8$, $f(x_t) = 0.2$ 라고 하자. 이 경우 쉽게 추출할 수 있는$e(x_t)$에 대해 $ \frac{0.2}{0.8} = 0.75%$ 의 확률로 버리고 $0.25%$의 확률로 취한다.
- 문제점
- 차원이 높아질수록 버리는 표본의 수가 지수적으로 많아진다
- $f(x)$를 알 수 없기에 $g(x)$ (envelope) 를 찾기 어렵다
MCMC
임의의 시작점 $x_1$에서 $f(x_1)$을 추출한 후 그 인근에서 $x_2$를 샘플링한다.
Detailed Balance Sufficient Condition
$${p(x)q(x_2|x_1) = p(x_2)q(x_1|x_2) (p(x=x_1) (q(x): maximum 근처에서 움직임)}$$
${q(x_2|x_1)}$
step1. $x_2|x_1$ random하게 뽑기
step2. accept하면 이동, reject하면 다시 뽑기
Mixing
올라가는 방향은 항상 올라가고 내려가는 방향은 일정 확률로 내려간다.
Metropolis-Hastings
본 알고리즘은 직접적으로 표본을 얻기 어려운 확률 분포로부터 표본의 수열을 생성하는 데 사용하는 기각 표본 추출 알고리즘이다. (위키백과)
accept ratio
$$\alpha_{x_1 \rightarrow x_2} = min (1, \frac{p(x_2)T(x_1|x_2)}{p(x_1)T(x_2|x_1)}) $$
만약 $x_2 > x_1$ 일때는 1, 아니면 $\frac{p(x_2)}{p(x_1)}$
reject되면 한번 더 뽑는다.
MCMC 유의점
1. t >> 1 : Burning time
분포의 봉우리에서 멀리 시작하면 봉우리까지 오는데 많은 step이 들기에 앞부분을 버린다.
2. Markov Auto-correlation
$cor(x_t, x_t+1)\neq0$ 이므로 k step 마다 $x_t$를 취하는 Thinning을 한다.
Gibbs sampling
N차원 분포에서 N-1축을 고정하고 하나의 축에 대해서만 sampling한 다음, 또 다른 하나의 축에 대해서 sampling하는 방식. k개의 차원으로 decomposing 된다면 k개로 clustering해서 번갈아가며 뽑는다. (cluestering된 근처끼리는 뽑기 쉽다.)
MALA (Metropolis-Adjusted Langevin Algorithm)
MCMC는 봉우리로 가기위해 reject해야 하지만, MALA는 해당 지점에서의 기울기를 계산하므로 reject할 필요 없이 값을 갱신하면 된다. 이때, 봉우리 외의 지점에서도 샘플링하기 위해 noise를 추가한다.
(단, metropolis adjusted에 따라 가끔 reject 할 수 있다.)
cf. Hamiltonian MC, Fokker Plank Equation
Langevin Dynamics
$dx = \frac{1}{2}\Delta log P(x)dt + dw$ (dw : noise winner proccess) 에 따라 움직이는 것
MCMC의 시각화는 https://chi-feng.github.io/mcmc-demo/app.html?algorithm=RandomWalkMH&target=banana에서 볼수있다.
댓글