Search
Duplicate

AI/ Importance Sampling, Annealed Importance Sampling(AIS)

Importance Sampling

Importance Sampling(IS)는 Monte Carlo 방법의 변형으로 확률 분포에서 직접 표본을 추출하기 어려울 때 이를 근사하는 방법으로 다음과 같은 형식을 갖는다.
E[φ(x)]=∫φ(x)π(x)dx\mathbb{E}[\varphi(\bold{x})] = \int \varphi(\bold{x})\pi(\bold{x})d\bold{x}
여기서 φ\varphi는 타겟 함수라고 하고 π(x)\pi(\bold{x})는 종종 π(x)=p(x∣y)\pi(\bold{x}) = p(\bold{x}|\bold{y}) 형식의 조건부 분포인 타겟 분포라고 한다. 일반적으로 타겟 분포에서 샘플링 하는 것이 어렵기 때문에 IS는 제안 분포(proposal distribution)라 부르는 q(x)q(\bold{x})에서 샘플을 뽑은 다음, 이 샘플들을 가중치를 이용해 재조정한다. 이것은 결국 weighted MC approximation이 된다.
E[φ(x)]≈∑n=1NWnφ(xn)\mathbb{E}[\varphi(\bold{x})] \approx \sum_{n=1}^N W_n\varphi(\bold{x}_n)
타겟이 정규화 된 경우와 정규화 되지 않은 경우에 대해 다음의 두 가지 접근 방법이 존재한다.

Direct Importance Sampling

우선 타겟 분포 π(x)\pi (\bold{x})가 정규화 되었고 평가 할 수 있지만 거기서 샘플링할 수 없는 경우 proposal q(x)q(\bold{x})에서 샘플링할 수 있다. 이것을 다음과 같이 작성할 수 있다.
∫φ(x)π(x)dx=∫φ(x)π(x)q(x)q(x)dx\int \varphi(\bold{x})\pi(\bold{x})d\bold{x} = \int \varphi(\bold{x}){\pi(\bold{x}) \over q(\bold{x})}q(\bold{x})d\bold{x}
타겟 π(x)\pi (\bold{x})이 0이 아닐 때마다 proposal q(x)q(\bold{x})도 0이 아니어야 한다. 즉 q(x)q(\bold{x})의 지지는 π(x)\pi(\bold{x})의 지지와 같거나 커야 한다.
여기서 타겟 π(x)\pi (\bold{x})과 proposal q(x)q(\bold{x})의 비율을 importance weight이라 하고 다음처럼 정의한다.
w~n=π(xn)q(xn)\tilde{w}_n = {\pi(\bold{x}_n) \over q(\bold{x}_n)}
xn∼q(x)\bold{x}_n \sim q(\bold{x})을 NsN_s 샘플하면 다음과 같이 작성할 수 있다.
E[φ(x)]≈1Ns∑n=1Nsπ(xn)q(xn)φ(xn)=1Ns∑n=1Nsw~nφ(xn)\mathbb{E}[\varphi(\bold{x})] \approx {1\over N_s} \sum_{n=1}^{N_s}{\pi(\bold{x}_n) \over q(\bold{x}_n)}\varphi(\bold{x}_n) = {1\over N_s}\sum_{n=1}^{N_s}\tilde{w}_n\varphi(\bold{x}_n)
결과는 실제 평균 E[φ(x)]\mathbb{E}[\varphi(\bold{x})]의 비편향 추정치가 된다.

Self-Normalized Importance Sampling

타겟 분포가 비정규화 된 경우 이를 다음과 같이 작성할 수 있다.
γ~(x)=Zπ(x)\tilde{\gamma}(\bold{x}) = Z\pi(\bold{x})
여기서 ZZ는 다음과 같이 정의되는 정규화 상수이다. 예컨대 π(x)=p(x∣y)\pi(\bold{x}) = p(\bold{x}|\bold{y})이면 γ~(x)=p(x,y)\tilde{\gamma}(\bold{x}) = p(\bold{x},\bold{y})이고 Z=p(y)Z= p(\bold{y})
Z=∫γ~(x)dzZ = \int \tilde{\gamma}(\bold{x})d\bold{z}
핵심 아이디어는 Importance Sampling으로 정규화 상수 ZZ를 근사하는 것이다. 이 방법을 Self-Normalized Importance Sampling(SNIS)이라고 한다. 결과 추정은 두 추정치의 비율이므로 편향이다. 그러나 Ns→∞N_s \to \infty으로 가면 어떤 약한 가정하에 편향이 0이 된다.
더 자세히 SNIS는 다음 근사에 기반한다.
E[φ(x)]=∫φ(x)π(x)dx=∫φ(x)γ~(x)dx∫γ~(x)dx=∫[γ~(x)q(x)φ(x)]q(x)dx∫[γ~(x)q(x)]q(x)dx≈1Ns∑n=1Nsw~nφ(xn)1Ns∑n=1Nsw~n\begin{aligned} \mathbb{E}[\varphi(\bold{x})] &= \int \varphi(\bold{x})\pi(\bold{x}) d\bold{x} = {\int \varphi(\bold{x})\tilde{\gamma}(\bold{x})d\bold{x} \over \int \tilde{\gamma}(\bold{x})d\bold{x}} ={\int \left[{\tilde{\gamma}(\bold{x}) \over q(\bold{x})} \varphi(\bold{x}) \right]q(\bold{x})d\bold{x} \over \int \left[{\tilde{\gamma}(\bold{x}) \over q(\bold{x})} \right]q(\bold{x})d\bold{x}} \\ &\approx {{1\over N_s} \sum_{n=1}^{N_s} \tilde{w}_n\varphi(\bold{x}_n) \over {1\over N_s} \sum_{n=1}^{N_s} \tilde{w}_n} \end{aligned}
여기서 unnormalized weights를 다음과 같이 정의한다.
w~n=γ~(xn)q(xn)\tilde{w}_n = {{\tilde{\gamma}}(\bold{x}_n) \over q(\bold{x}_n)}
위 가중치를 사용하면 근사 식을 다음과 같이 더 간략하게 작성할 수 있다.
E[φ(x)]≈∑n=1NsWnφ(xn)\mathbb{E}[\varphi(\bold{x})] \approx \sum_{n=1}^{N_s} W_n \varphi(\bold{x}_n)
여기서 normalized weights를 다음처럼 정의한다.
Wn=w~n∑n′=1Nsw~n′W_n = {\tilde{w}_n \over \sum_{n'=1}^{N_s} \tilde{w}_{n'}}
이것은 델타 함수의 가중합을 사용하여 타겟 분포를 근사한 것과 동등하다.
π(x)≈∑n=1NsWnδ(x−xn)≜π^(x)\pi(\bold{x}) \approx \sum_{n=1}^{N_s} W_n\delta(\bold{x}-\bold{x}_n) \triangleq \hat{\pi}(\bold{x})
이 알고리즘의 부산물로 정규화 상수에 대한 다음의 근사를 얻을 수 있다.
Z≈1Ns∑n=1Nsw~n≜Z^Z \approx {1\over N_s} \sum_{n=1}^{N_s} \tilde{w}_n \triangleq \hat{Z}

Annealed Importance Sampling (AIS)

Annealed Importance Sampling(AIS)은 복잡한 멀티모달 분포에서 샘플링하는 방법으로 타겟 분포와 시작 분포 사이에 ‘온도’를 조절하며 일련의 중간 분포를 만들고 각 분포 사이에 Importance Sampling을 수행하는 방법이다. 이때 최종 샘플의 가중치는 모든 중간 단계의 샘플 가중치를 곱해서 얻는다. 참고로 Annealing이라는 용어는 물리학에서 물질을 가열한 후 천천히 식혀서 결정 구조를 개선하는 과정에서 유래했다.
AIS는 Energy Based Model(EBM)과 같이 복잡하고 정규화하기 어려운 분포에서 샘플링 방법으로 사용되거나 Restricted Boltzmann Machine(RBM)이나 Deep Belief Network(DBN) 같은 복잡한 로그 확률함수를 가진 딥러닝 모델에서 정규화 상수를 추정하는데 사용될 수 있다. AIS는 몬테카를로 방법 중에서 특히 분포의 꼬리를 잘 탐색할 수 있어서 다른 샘플링 방법에 비해 정확한 추정이 가능하다.
보다 형식적으로 어떤 타겟 분포 p0(x)∝f0(x)p_0(\bold{x}) \propto f_0(\bold{x})(여기서 f0(x)f_0(\bold{x})는 unnormalized)가 고차원이거나 멀티모달이라서 직접 샘플링하기 어렵지만 pn(x)∝fn(x)p_n(\bold{x})\propto f_n(\bold{x})라고 부르는 샘플링 할 수 있는 더 쉬운 분포가 있다고 가정하자. 예컨대 이것은 prior일 수 있다.
그러면 pnp_n을 시작 분포로 설정한 다음 온도 파라미터를 이용하여 타겟 분포 p0p_0 사이에 다음과 같은 일련의 중간 분포를 설정할 수 있다.
fj(x)=f0(x)βjfn(x)1−βjf_j(\bold{x}) = f_0(\bold{x})^{\beta_j}f_n(\bold{x})^{1-\beta_j}
여기서 1=β0>β1>...>βn=01 = \beta_0 > \beta_1 > ... > \beta_n = 0.
각 fjf_j에서 샘플하기 위해 p0p_0 불변량으로 유지하고 다음과 같은 마르코프 체인을 정의할 수 있다고 가정하자.
Tj(x,x′)=pj(x′∣x)T_j(\bold{x},\bold{x}')=p_j(\bold{x}'|\bold{x})
즉, ∫pj(x′∣x)p0(x)dx=p0(x′)\int p_j(\bold{x}'|\bold{x})p_0(\bold{x})d\bold{x} = p_0(\bold{x}').
이것이 주어지면 우선 vn∼pn\bold{v}_n \sim p_n을 샘플링하고 그 다음 vn−1∼Tn−1(vn,⋅)\bold{v}_{n-1} \sim T_{n-1}(\bold{v}_n,\cdot)을 샘플링하고 이것을 v0∼T0(v1,⋅)\bold{v}_0 \sim T_0(\bold{v}_1,\cdot)을 샘플링할 때까지 반복하여 p0p_0에서 x\bold{x}을 샘플링 할 수 있다. 마지막으로 x=v0\bold{x} = \bold{v}_0을 설정하고 가중치를 다음과 같이 부여한다.
w=fn−1(vn−1)fn(vn−1)fn−2(vn−2)fn−1(vn−2)...f1(v1)f2(v1)f0(v0)f1(v0)w = {f_{n-1}(\bold{v}_{n-1}) \over f_n(\bold{v}_{n-1})}{f_{n-2}(\bold{v}_{n-2}) \over f_{n-1}(\bold{v}_{n-2})}...{f_{1}(\bold{v}_{1}) \over f_2(\bold{v}_{1})}{f_0(\bold{v}_{0}) \over f_1(\bold{v}_{0})}
이것은 알고리즘을 확장된 상태 공간 v=(v0,...,vn)\bold{v} = (\bold{v}_0,...,\bold{v}_n)에서의 Importance Sampling의 형식으로 볼 수 있다.
AIS의 중요한 응용은 분할 함수(또는 정규화 상수)의 비율을 평가하는 것이다. Z0=∫f0(x)dx=∫φ(v)dvZ_0 = \int f_0(\bold{x})d\bold{x} = \int \varphi(\bold{v})d\bold{v}이고 Zn=∫fn(x)dx=∫g(v)dvZ_n = \int f_n(\bold{x})d\bold{x} = \int g(\bold{v})d\bold{v} 이므로
Z0Zn=∫φ(v)dv∫g(v)dv=∫φ(v)q(v)g(v)dv∫g(v)dv=Eg[φ(v)g(v)]≈1S∑s=1Sws{Z_0 \over Z_n} = {\int \varphi(\bold{v})d\bold{v} \over \int g(\bold{v})d\bold{v}}={\int{\varphi(\bold{v})\over q(\bold{v})}g(\bold{v})d\bold{v} \over \int g(\bold{v})d\bold{v}} = \mathbb{E}_g\left[{\varphi(\bold{v}) \over g(\bold{v})}\right]\approx{1\over S} \sum_{s=1}^S w_s
여기서 ws=φ(vs)/g(vs)w_s = \varphi(\bold{v}_s) / g(\bold{v}_s). f0f_0이 prior이고 fnf_n이 posterior인 경우, 알려진 정규화 상수 Z0Z_0을 갖는 prior를 제공하여 위의 방정식을 사용하여 Zn=p(D)Z_n = p(\mathcal{D})을 계산할 수 있다.

참고

Made with