Sampling algorithm 관계 정리 및 요약

 

요즘 데이터 양/컴퓨팅 파워의 증가와 머신러닝/딥러닝 증가로 인해 통계적 방법론, 확률론적 방법론이 주목받고 있다.

기존에 있던 확률 책을 보면 랜덤 변수를 추출하는 방법에 대한 이야기가 있는데 샘플링 방법론과 결을 같이 한다.

 

내가 알고 있는 분포가 있을 때 이 분포를 따르는 표본을 얻기 위해서는 어떤 알고리즘을 써야할까?

이에 관련된 내용이 sampling method이다.

 

 

 

 

아래의 Rejection sampling, importance sampling, inverse cumulative distribution function은 나중에 다룰 생각이다.

 

1. Markov chain

 

 

Markov chain은 stochastic dynamical environment를 모델링한 것으로

state

transition probability로 구성되어있다.

 

Markov decision process는 여기에서 action이 추가된 형태인데 여기서는 다루지 않는다.

위의 transition probability는 $P$ matrix로 정의된다.

어떤 state 확률 $\pi(s)$에 대해서 $\pi^{\top} P = \pi$과 같이 transition probability matrix를 곱해도 확률이 유지되는 확률 $\pi$를 stationary distribution라고 한다.

 

 

 

강화학습 등에서 다루는 Markov chain은 이러한 stationary distribution이 있다고 가정하고 이론을 진행한다.

이 stationary distribution을 구하는 것이 Markove chain에서 중요한 문제이다.

 

2. Monte Carlo

 

몬테 카를로 시뮬레이션은 해석적으로 구하기 어려운 함수값을 샘플링 통해 근사적으로 구하고자 하는 방법론이다.

활용되는 분야가 많고 역사가 길다.

 

다 알아본 것은 아니지만 Metropolis 저자의 The monte carlo method라는 논문이 그 시초이다.

 

 

 

그리고 이후에 markov chain monte carlo 개념이 등장한 것이

Hastings의 Monte Carlo sampling methods using Markov chains and their applications 이라는 논문이다.

 

 

 

 

1-1. Metropolis sampling

 

Metropolis sampling은 보통 Metropolis-Hastings (MH) sampling이라는 일반화된 버전으로 많이 쓰인다.

 

MH 방법보다 더 효율성을 높인 것이 Gibbs sampling이다.

 

 

 

1-2. Hamiltonian Monte Carlo (HMC)

 

Metropolis sampling에서 샘플링하는 방식을 Hamiltonian mechanics를 이용해서 더 효율적으로 수행한 연구이다.

이 방법에 이어 stochastic gradient Hamiltoniamonte carlo으로 발전했다.