Zzong's Notes

importance sampling

2 min read

Importance Sampling

Importance sampling 은 효율적으로 기댓값을 추정하기 위해 고안된 방법이다.

Why We Need IS?

Rejection sampling 는 rejection 이 많을 경우 계산 비용이 많이드는 단점이 있다. 또한, 우리는 전체 분포에 대해서 알 필요가 없이, 어떤 확률 분포의 기댓값에 대해서만 관심이 있는 경우가 많다.

a.k.a. inverse propensity score - Importance sampling 은 기댓값 을 계산하고자 하는 확률 분포  의 [확률 밀도 함수](Probability Density Function) 를 알고있지만 샘플들을 생성하기 어려울 때, 비교적 쉬운 pdf 인  에서 샘플을 생성하여  의 기댓값을 계산하는 방법이다.

아래의 식을 보면, 에서 생성된 샘플을 통해 의 기댓값을 계산할 수 있다는 것을 알 수 있다.

에서 를 likelihood ratio 라고 하며,
를 nominal distribution, 를 importance distribution 이라고 한다.

Importance Sampling 과정

|600

Related

References

링크된 언급

6
inverse propensity score

정의 Importance sampling 이라고 불리며, IPS 는 expectation 을 계산하고자 하는 확률 분포 f(x) 의 PDF p 를 알고있지만 샘플들을 생성하기 어려울 때, 비교적 쉬운 PDF 인 q(x)...

Monte Carlo Method(RL)

...이 아닌 가중치를 적용한 평균이고, 이를 모두 더하면 1 이 된다. 결과적으로, 최대값에 대한 평균보다는 반드시 작거나 같아야한다. Off policy Prediction via Importance Sampling Off policy 는 두가지 policy 를 통한 전체 process 를 의미한다. target policy: optimal policy 를 위해 최적의 행동을 찾아서 수행하는...

Offline AB testing for Recommender Systems

...gging policy 로 얻은 reward 를 이용해서 target policy 의 expected reward 를 추정하는 방법이 importance sampling 또는 inverse propensity score 라고 불리는 방법이다. C) Related D) References arxiv.org/pdf/1801.07030.pdf

Pessimistic Reward Models for Off-Policy Learning in Recommendation

...loop off policy learning 에서 biased data 로 부터 unbiased learning 을 지향하는 방법에는 importance sampling or Inverse Propensity Score (IPS) weighting 이 존재함 value based models 1.1. Contributions off policy recommendation 을 위한 reward...

Rejection sampling

...을 최대화하여, Rejection sampling 의 실행 속도를 빠르게 만들기 위해서는 p(x)≤Mq(x) 를 만족하면서 가능한 작은 M 을 선택해야 한다. E) Related importance sampling F) References daum blog

value-based method

... 크게 영향을 받을때 A.2) 특징 importance sampling 보다 일반적으로 variance 가 낮지만, 일반적으로 biased 하다. Comparison with inverse propensity score and value based method \displaystyle\widehat{V} {\mathrm{IPS}}(\pi,\mathcal{D})=\sum {(c,a,r)\in\...