Sampling Based Inference(Forward/Rejection/Importance Sampling)

 - Learn basic sampling method

• Understand the concep of Markov chain Monte Carlo
• Able to apply MCMC to the parameter inference of Bayesian networks
• Know the mechanism of rejection sampling
• Know the mechanism of importance sampling

- Learn sampling based inference

• Understand the concept of Metropolis-Hastings algorithm
• Know the mechanism of Gibbs sampling

 

Forward Sampling in GMM

- Sample $z$ from $\pi$

• $z$ is the indicator of the mxture distribution

- With selected z, sample x from $N(\mu_z, \Sigma_z$)$

- After many, many sampling, you can draw the histogram of the mixture distribution

- You have an empirical PDF, so you can ask a query like $P(0\leq x\leq5|\pi, \Sigma)$

 

 

Rejection Sampling

- Iterate many times

- Generate a sample from the Bayesian network 

- Given part에 맞지 않는 sample은 쓰기가 어려움 -> reject

- Given part에 맞는 것만 가져와서 sampling

- Count of (sampleing된 갯수 / all instance) Samples

 

 

Rejection Sampling from Numerical View

- count = 0

- While count < N

• Sample $x_{(i)}~q(x)$
• Sample u~Unif(0, 1)
• if $u < \frac{p(x_{(i)})}{Mq(x_{(i)})}$
  • Accept $x_{(i)}$
  • Increate count
• Else
  • Reject and resample

 

Rejection Sampling in GMM

- Rejection sampling of GMM

• Sample $z$ from (1, 2, 3) with 1/3 change each
• Sample $x$ from $N(\mu_{q(z)}, \Sigma_{q(z)})$
  • $q(x)$~The Probability drawing $x$ from $N(\mu_{q(z)}, \Sigma_{q(z)})$
• Sample $u$ from Uniform(0, 1)
• if $M \times u \times q(x) < p(x)$
  • Accept the sample of (z, x)
• Else
  • Discard the sample

- 큰 scale의 bayesian network inference에는 적절하지 않음

 

 

Importance Sampling

- Huge waste from the rejection

- Is generating the PDF the end goal?

• No,, Usually, the question follows
  • Calculating the expectation of PDF
  • Calculating a certain probability
  • -> 위 두가지 목적만 잘 해결할 수 있으면 여러번 많이 하지 않아도 됨

- Let's use the wasted sample to asnwer the questions

수식의 가장 우 항은 not equal! 그 왼쪽의 식들은 무한대의 확률을 다 계산하는 것으로 나타내므로 현실적으로 불가능. (개별 instance를 sampling하면서 개별 인스턴스의 발생확률을 구함)

• 특정 함수에 대한 $E(f)$를 구할 때, f에 들어가는 random variable (z)가 있고, random variable을 generate하는 확률 분포 $p(z)$가 있음.
• L = # of samples, $z^l = a$ sample of Z
• Here. the importance weight plays the role
  • $f(z^l)$ 앞에 있는 $p(z^l)/q(z^l)$은 개별 sample $f(z^l)$에 대하여 weight라고 볼 수 있음 (가중평균)
  • $r^l = \frac{p(z^l)}{q(z^l)}$ (가중평균)
• What if $P(z^l)$ and $q(z^l)$ is not normalized, as they should be as probability distributions

$\frac{Z_q}{Z_p}$를 이용해 Normalize

 

• 특정 샘플이 1보다 클 확률을 구할때, $p(z)$가 1 이상은 case에 대해서만 summantion
• 이를 직접 계산하는 것이 쉽지 않으므로, $q(z)$라는 sampling distribution을 활용함.
• sampling을 한 하나하나의 instance가 $z^l$ 파트가 됨
• $f(z^l)$은 $1_{z>1}$의 identitiy 함수가 되고, $q$는 $z^l$을 샘플링하기 위해서 활용했던 sampling distribution 값
• $p(z^l)$은 sampling을 directly하게 계산하지 않아도 probability evaluation이 된다고 가정했으므로, 계산할 수 있다고 봄
• sample 결과가 1보다 크면 1이라고 하고, 1보다 작으면 0이라고 한 뒤 summation해서 계산

 

Likelihood Weighting Algorithm

- Discrete 한 경우에서

• SumSW = NormSW = 0으로 잡음
• Iteration many times
  
  • SW = SampleWeight = 1두고 시작하는데, 조금씩 discount가 됨
  • 어느 정도의 likelihood를 두고 발생할 수 있는지(얼만큼 Important 하게 발생할 수 있는지)로 sample weight를 잡음
  • Given들의 조건을 확인하면서 likelihood 계산
  • 조건에 맞는 경우, SumSW += SW
  • 그렇지 않은 case들의 Importance는 normalize를 하기 위해서 항상 NormSW += SW
• Return SumSW/NormSW