11. Sampling Methods

많은 확률적 모델들에 대해서는 정확한 추론이 불가능하므로 근사를 해야 한다. 여기서는 몬테 카를로 법이라는 샘플링 기반 근사법을 다룬다. 많은 경우 우리가 관심 있는 문제는 사후분포 p(\mathbf{z})에 대한 특정한 함수 f(\mathbf{z})의 기댓값을 찾는 것이다. 이를 근사할 때는 p(\mathbf{z})에서 표본들을 추출한 뒤 이들의 평균 \hat{f} = \frac{1}{L} \sum_{l=1}^{L} f(\mathbf{z}_{l})로 근사한다. 이 때 결합분포를 그래프 모델로 나타내면 p(\mathbf{z}) = \prod_{i=1}^{M} p(\mathbf{z}_{i} | pa_{i})의 관계를 이용해 표본을 쉽게 추출할 수 있다. 이외에도 중요도 추출, 논리적 추출 등의 방법을 사용할 수 있다.

11.1. Basic Sampling Algorithms

기본적 추출 알고리즘을 알아보자.

11.1.1. Standard distributions

가장 간단한 방법은 누적밀도함수에 대해 역확률 변환을 하는 것이다.

11.1.2. Rejection sampling

누적밀도함수의 역함수 법을 쓸 수 없을 경우에는 기각 추출법을 사용한다. 기각 추출법에서는 적당한 M에 대해 Mq(x) \geq \tilde{p}(x) 을 만족하는 제안 분포 q(x)을 구성한다. 이후 x \sim q(x), u \sim U(0, 1)을 추출하고, u > \frac{\tilde{p}(x)}{Mq(x)}이면 이를 기각하고 아니면 이를 채택한다.

11.1.3. Adaptive rejection sampling

p(x)이 로그 오목이면 이에 접하는 구간적 선형함수로 타이트한 상한을 잡을 수 있다. 이를 적응적 기각 추출법이라 한다.

11.1.4. Importance sampling

중요도 추출법은 제안 분포 q(\mathbf{x})로부터 추출한 뒤 이를 이용해 기대값 적분을 다음과 같이 추정한다.

\mathbb{E}[f] = \simeq \frac{1}{S} \sum_{s=1}^{S} w_{s} f(\mathbf{x}_{s}) (w_{s} = \frac{p(\mathbf{x}_{s})}{q(\mathbf{x}_{s})})

11.1.5. Sampling-importance-resampling

p(x) 로부터 중요도 추출을 이용해 비가중 표본을 추출해 p(\mathbf{x}) \simeq \sum_{s} w_{s} \delta_{\mathbf{x}_{s}}(\mathbf{x}) 형태의 분포를 얻을 수 있다. 이 분포로부터 재추출을 한 뒤 먼저 추출했던 표본들을 대체할 수 있는데, 이를 추출 중요도 재추출이라 한다.

11.1.6. Sampling and the EM algorithm

전가 사후분포(IP) 알고리즘은 기대값 최대화의 몬테 카를로 버전이다. I 단계에서는 p(\mathbf{Z} | \mathbf{X}) = \int p(\mathbf{Z} | \mathbf{\theta}, \mathbf{X}) p(\mathbf{\theta} | \mathbf{X}) d\mathbf{\theta}의 관계를 이용해 p(\mathbf{\theta} | \mathbf{X})로부터 \mathbf{\theta}_{l}를 추출하고, 이를 이용해 p(\mathbf{Z} | \mathbf{\theta}_{l}, \mathbf{X})로부터 \mathbf{Z}_{l}을 추출한다. P 단계에서는 p(\mathbf{\theta} | \mathbf{X} = \int p(\mathbf{\theta} | \mathbf{Z}, \mathbf{X}) p(\mathbf{Z} | \mathbf{X}) d \mathbf{Z}로부터 p(\mathbf{\theta} | \mathbf{X})을 추정한다.

11.2. Markov Chain Monte Carlo

몬테 카를로 법은 고차원에 대해 잘 작동하지 않는다는 단점이 있다. 고차원 분포에서 샘플링하는 가장 널리 쓰이는 방법은 마르코프 연쇄 몬테 카를로이다. 

11.2.1. Markov chains

기본 아이디어는 목표하는 확률분포를 정지 분포로 갖는 마르코프 연쇄를 만든 뒤 상태 공간에서 무작위 걸음을 해서 각 상태 \mathbf{x}에서 소비하는 시간이 p^{\ast}(\mathbf{x})에 비례하도록 하는 것이다. 

11.2.2. The Metropolis-Hastings algorithm

깁스 샘플링은 간단하지만 적용가능한 모델이 제한되어 있으며 느리다는 단점이 있다. 그래서 이를 일반화한 메트로폴리스 헤이스팅스 알고리즘이 있다. 메트로폴리스 헤이스팅스의 기본 발상은 각 단계에서 제안 분포 q(\mathbf{x}^{\prime} | \mathbf{x})의 확률로 현 상태 \mathbf{x}에서 다음 상태 \mathbf{x}^{\prime}으로 이동하는 것이다. 

11.3. Gibbs Sampling

유명한 마르코프 연쇄 몬테 카를로법으로 깁스 샘플링이 있다. 이는 좌표 하강법의 마르코프 연쇄 몬테 카를로 버전이다. 기본 아이디어는 각 단계마다 하나의 변수를 다른 변수들은 분포에 존재한다는 조건하에 샘플링을 하는 것이다. 관측가능한 변수면 샘플링하지 않는다.

11.4. Slice Sampling

일변수 다최빈값 분포 \tilde{p}(x)를 생각해 보자. 보조 변수 u를 더해 이동의 크기를 크게 할 수 있다. 결합분포를 \hat{p}(x, u) = \frac{1}{Z_{p}} if 0 \leq u \leq \tilde{p}(x) (Z_{p} = \int \tilde{p}(x) dx) 이외 0으로 정의하면 x에서의 주변분포는 p(x) = \frac{\tilde{p}(x)}{Z_{p}}이 된다. 그러므로 \hat{p}(x, u)로부터 샘플링한 뒤 u를 무시하면 p(x)로부터 샘플링할 수 있다. 전체 조건부분포는 다음과 같다.

p(u | x) = U_{[0, \tilde{p}(x)]}(u)

p(x | u) = U_{A}(x) (A = \{x : \tilde{p}(x) \geq u \})

이를 절단 샘플링이라 한다. 

11.5. The Hybrid Monte Carlo Algorithm

연속된 상태 공간에서 로그 사후분포의 경사를 구함으로써 몬테 카를로 샘플링을 하는 방법이 있다.

11.5.1. Dynamical systems

기본 발상은 매개변수를 공간 내 입자로 보고 보조 변수를 이 입자의 모멘텀으로 정의하는 것이다.

11.5.2. Hybrid Monte Carlo

그리고 이 매개변수-모멘텀 쌍을 특정한 규칙에 따라 업데이트하는 것이다. 이를 혼성 몬테 카를로법이라 한다.

11.6. Estimating the Partition Function

중요도 샘플링을 통해 분할 함수의 비율을 구할 수 있다.

\frac{Z_{0}}{Z_{n}} \simeq \frac{1}{S} \sum_{s=1}^{S} w_{s} (w_{s} = \frac{f(\mathbf{z}_{s})}{g(\mathbf{z}_{s})}) f_{n}을 사후분포, f_{0}을 사전분포로 넣으면 사전분포의 표준화 상수 Z_{0}을 알 때 Z_{n} = p(\mathcal{D})을 추정할 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중