Reference
- 강의자료, 인터넷 여기저기
- Gibbs Sampling (by ratsgo, 201705)
Sampling
- 복잡한 확률 모델의 경우, 정확한 확률값을 계산하기 어려울 수 있으므로, 대략적인 값을 구하기 위해 샘플을 추출하는 방법.
- 데이터의 차원이 아주 클 경우, 샘플링 자체가 쉽지 않은 문제가 될 수 있음. 예를 들어, 특정 문서에 등장하는 단어들이 수십만개 일 때, 어떻게 샘플링하는 게 바람직한 지 고민될 수 있음.
Importance sampling (중요도 샘플링)
- Expected value를 계산하고자 하는 확률 분포 p(x)의 확률 밀도 함수는 알고 있지만, p에서 샘플 추출이 어려울 때, 상대적으로 샘플을 생성하기 쉬운 q(x)에서 샘플을 추출하여 p의 기대값을 계산하는 방식.
- 샘플들이 가지는 importance를 이용하여, 기대값의 근사치를 계산.
- p = normal distribution
- q = importance distribution
- p/q = likelihood ratio
- sampling-importance-resampling (SIR) = 확률 분포 q를 이용하여, p의 샘플을 생성하는 방법.
- Expected value를 계산하고자 하는 확률 분포 p(x)의 확률 밀도 함수는 알고 있지만, p에서 샘플 추출이 어려울 때, 상대적으로 샘플을 생성하기 쉬운 q(x)에서 샘플을 추출하여 p의 기대값을 계산하는 방식.
- 샘플들이 가지는 importance를 이용하여, 기대값의 근사치를 계산.
- p = normal distribution
- q = importance distribution
- p/q = likelihood ratio
- sampling-importance-resampling (SIR) = 확률 분포 q를 이용하여, p의 샘플을 생성하는 방법.
Monte Carlo Method
- 무작위로 추출된 난수(random number)를 이용하여, 원하는 함수의 대략적인 값을 산출하기 위한 시뮬레이션 방법.
- 대표적인 예시: 가로와 세로가 각각 2인 정사각형에 내접하는(즉, 반지름이 1이 되는) 원의 면적을 구할 때, 정사각형 내부를 채울 수 있는 1만개의 난수 순서쌍 (x, y)을 무작위로 추출한 뒤, 원의 범위에 포함된 비율을 계산하는 방식을 생각해 볼 수 있음.
- 난수의 개수를 늘릴수록 정확도는 높아지겠지만, 그만큼의 연산 시간이 소요됨.
- Manhattan Project에 참여했던 Los Alamos 국립 연구소의 핵무기 개발 관련 연구에서 유래함.
- Central limit theorem에 의해, MC에 의한 sampling의 분포는 normal distribution에 수렴함.
- Monte Carlo sampling: 모든 샘플이 독립(independent)이면서, 추출되는 확률 또한 random임.
Markov Chain Monte Carlo Method (MCMC)
- 특정한 확률분포에 수렴하는 (다시 말하면, 특정 확률 모델로부터) 난수들을 추출하는 몬테 카를로 방법.
- = Metropolis-Hasting algorithm
- Markov Chain = 시간이 흘러감에 따라, 현재 상태(random state x)에서 다음의 상태로 변화하는 과정을 전이 확률(transition probability)로 표현한 것.
- 러시아 과학자인 Andrey Markov에 의해, 1910년대에 개념이 등장함.
- 러시아어 문헌에 나오는 글자들의 순서에 관한 모델 구축을 위해 제안.
- Chain = 상태 값의 sequence. 즉, 다음의 상태는 바로 직전의 상태에 영향을 받음.
- 해당 체인이 무한하게 반복된다면, 특정한 확률 분포의 형태에 수렴하는 성질.
- 확률과 관련된 많은 시뮬레이션이 MCMC에 의해 수행되고 있음.
- 예를 들어, 내일의 날씨는 반드시 오늘의 날씨에 의해서만 결정되어야 한다는 가정에 기반하여 확률로 표현할 수 있는 데, 앞으로의 날씨를 무한히 확률 계산을 하면, 오늘의 날씨와 상관없이, 일반적으로 날이 맑거나 흐리거나 비가 오는 확률이 특정하게 수렴하여 평형 상태의 정적인 분포(stationary distribution)에 도달하게 됨.
- 특히 해당 평형상태는 초기값에 연연하지 않음.
- MCMC에 의한 sampling: 다음번 추출되는 샘플은 현재 샘플에 영향을 받음.
Gibbs sampling
- 두 개 이상의 확률변수의 결합 확률 분포로부터 일련의 표본을 생성하는 확률적 알고리즘.
- (MCMC에서처럼) 다음번 추출되는 샘플은 현재 샘플에 영향을 받지만, 여러개의 확률 변수 중에서 한번에 하나의 확률 변수에만 변화를 준다는 점에서 차이가 있음.
- basic 기법
- 한번에 하나의 확률 변수만 변화
- block 기법
- 하나 이상의 변수들을 그룹으로 묶는 방법
- collapse 기법
- 불필요한 일부 변수를 샘플링에서 생략하는 방법.
