Importance Sampling

Importance Sampling (중요도 샘플링)

어떤 분포 $p$ 하에서의 기댓값을 구하고 싶은데 $p$에서 샘플을 뽑기 어려울 때, 뽑기 쉬운 다른 분포 $q$에서 샘플링한 뒤 가중치(likelihood ratio)로 보정해 $p$ 하의 기댓값을 추정하는 기법.
핵심 도구는 가중치 $w(x)=\frac{p(x)}{q(x)}$. 통계적 추정·베이지안 추론·off-policy RL·생성모델 등 곳곳에 등장한다.

importance-sampling monte-carlo variance-reduction off-policy

문제 설정

어떤 함수 $f$의 분포 $p$ 하 기댓값을 구하고 싶다:

$${\mathbb{E}}_{x\sim p}[f(x)]=\int f(x)p(x)dx$$

Monte Carlo로는 $p$에서 $N$개를 뽑아 평균내면 된다: $\frac{1}{N}{\sum }_{i}f(x_i)$. 그런데 현실에서는—

• $p$에서 직접 샘플링이 불가능/어렵거나 (예: 정규화 상수를 모름),
• $f$가 큰 영역이 $p$에서 희귀해서(rare event) 무작정 뽑으면 분산이 폭발하거나,
• 이미 다른 분포 $q$에서 뽑아 둔 데이터밖에 없을 때(off-policy).

핵심 아이디어: 분포를 바꿔 적분하기

$p$를 곱하고 나누는 트릭으로 기댓값을 $q$ 하의 기댓값으로 다시 쓴다:

$${\mathbb{E}}_{x\sim p}[f(x)]=\int f(x)\frac{p(x)}{q(x)}q(x)dx={\mathbb{E}}_{x\sim q}\left[f(x)\frac{p(x)}{q(x)}\right]$$

따라서 $q$에서 뽑은 샘플 $x_i\sim q$로 추정한다:

$$\hat{\mu }=\frac{1}{N}\sum _{i=1}^{N}f(x_i)w(x_i),w(x_i)=\frac{p(x_i)}{q(x_i)}$$

• $q$를 proposal distribution(제안 분포), $p$를 target distribution이라 부른다.
• $w(x)$는 importance weight: $q$에서 과하게/덜 뽑힌 만큼을 보정. $q$가 실제보다 자주 뽑은 점은 가중치를 깎고, 드물게 뽑은 점은 키운다.
• 불편추정량(unbiased) 조건: $q(x)>0$ wherever $p(x)f(x)\ne 0$ (target이 질량을 갖는 곳을 proposal이 빠짐없이 덮어야 함, support 조건).

Self-normalized Importance Sampling

$p$나 $q$를 정규화 상수까지는 모르고 비율만 아는 경우(베이지안에서 흔함), 가중치를 정규화해서 쓴다:

$$\hat{\mu }=\frac{{\sum }_{i}f(x_i)\tilde{w}(x_i)}{{\sum }_i\tilde{w}(x_i)},\tilde{w}(x_i)=\frac{\tilde{p}(x_i)}{q(x_i)}$$

• 정규화 상수가 분자·분모에서 상쇄됨 → 미정규 밀도 $\tilde{p}$만 있으면 된다.
• 대신 약간의 **편향(bias)**이 생긴다(하지만 일치추정량, $N\to \infty$에서 사라짐). 실무에선 보통 분산이 더 작아 이 trade-off를 받아들인다.

분산이 전부다 (좋은 $q$ 고르기)

IS의 성패는 proposal $q$의 선택에 달려 있다.

분산 폭발

$q$가 $p$를 잘 못 덮으면(특히 $p$가 큰데 $q$가 작은 영역) 가중치 $w$가 폭발해 추정 분산이 발산한다. 소수의 거대한 가중치가 추정을 지배하는 weight degeneracy 현상.

• 이론적 최적 proposal: $q^{\ast }(x)\propto |f(x)|p(x)$. 즉 $f$가 큰 곳에 샘플을 몰아주는 분포가 분산을 최소화(0까지)한다. → IS는 단순 보정이 아니라 rare-event를 일부러 더 자주 뽑아 추정 효율을 높이는 기법이기도 하다(variance reduction).
• 실무 진단 지표: ESS(Effective Sample Size) $\approx \frac{({\sum }_i{w}_i{)}^2}{{\sum }_i{w}_i^2}$. $N$에 가까우면 건강, 1에 가까우면 소수 샘플이 지배 → proposal 교체 필요.
• $p$와 $q$가 멀수록(가령 KL divergence가 클수록) 가중치 분산이 커진다 — 두 개념이 연결된다.

RL에서의 importance sampling (off-policy)

가장 흔히 마주치는 응용. **행동을 만든 정책(behavior policy $\mu$)**과 **평가/개선하려는 정책(target policy $\pi$)**이 다를 때, $\mu$로 모은 경험으로 $\pi$의 가치를 추정한다.

$${\mathbb{E}}_{\tau \sim \pi }[G(\tau )]={\mathbb{E}}_{\tau \sim \mu }\left[G(\tau )\prod _{t=0}^T\frac{\pi (a_t|s_t)}{\mu (a_t|s_t)}\right]$$

• 한 trajectory의 가중치는 시점별 비율 $\frac{\pi (a_t|s_t)}{\mu (a_t|s_t)}$의 곱 → step이 길면 분산이 기하급수적으로 커지는 고질병.
• 완화책: per-decision IS, weighted IS(self-normalized), 그리고 비율을 잘라내는 clipping.
• Reinforcement Learning with Human Feedback(RLHF)의 PPO가 대표 사례: $\frac{{\pi }_{\theta }(a|s)}{{\pi }_{old}(a|s)}$ 비율을 surrogate objective에 쓰되 $[1-ϵ,1+ϵ]$로 clip해 분산/폭주를 막는다. (MCTS rollout 가치를 off-policy로 보정할 때도 등장.)

어디에 쓰이나 (요약)

분야	쓰임
Monte Carlo 적분	rare-event 확률, 꼬리 기댓값 추정의 분산 감소
베이지안 추론	posterior 기댓값 추정, particle filter(SIS/SIR)의 핵심
Off-policy RL	behavior로 모은 데이터로 target policy 평가·PPO
생성모델	VAE의 IWAE 등 tighter ELBO bound

Related

• Monte Carlo Tree Search(MCTS) — rollout 기반 추정이라는 같은 Monte Carlo 가족.
• KL divergence — proposal과 target의 괴리가 분산을 결정.
• Maximum Likelihood Estimation, Likelihood — 가중치 $p/q$가 곧 likelihood ratio.
• Basic RL