Markov Chain Monte Carlo (MCMC)

(1)

Markov Chain Monte Carlo (MCMC) Inference

Seung-Hoon Na

Chonbuk National University

(2)

Monte Carlo Approximation

• Generate some (unweighted) samples from the posterior:

• Use these samples to compute any quantity of interest

– Posterior marginal: 𝑝(𝑥₁|𝐷) – Posterior predictive: 𝑝 𝑦 𝐷 – …

(3)

Sampling from standard distributions

• Using the cdf

– Based on the inverse probability transform

(4)

Sampling from standard

distributions: Inverse CDF

(5)

Sampling from standard distributions:

Inverse CDF

• Example: Exponential distribution

cdf

(6)

Sampling from a Gaussian: Box-Muller Method

• Sample 𝑧₁, 𝑧₂ ∈ (−1,1) uniformly

• Discard (𝑧₁, 𝑧₂) that do not inside the unit-circle, so satisfying  𝑧₁² + 𝑧₂² ≤ 1

• 𝑝 𝑧 = ¹

𝜋 𝐼(𝑧 𝑖𝑛𝑐𝑖𝑑𝑒 𝑐𝑖𝑟𝑐𝑙𝑒)

• Define

(7)

• Polar coordinate상에서 sampling

• r을 normal distribution에 비례하도록 샘플  Exponential 분포

• 𝜃를 uniform하게 샘플  주어진 r에 대해 x,y 를 uniform하게 분포

(8)

• 𝑋 ~ 𝑁 0,1 𝑌 ~ 𝑁 0,1

• 𝑝 𝑥, 𝑦 = ¹

2𝜋 exp − ^𝑥²^+𝑦²

2 = ¹

2𝜋 exp − ^𝑟²

2

• 𝑟²~𝐸𝑥𝑝 ¹

2

• 𝐸𝑥𝑝 𝜆 = − log(𝑈 0,1 ) 𝜆

• 𝑟 ∼ −2 log(𝑈 0,1 )

https://theclevermachine.wordpress.com/2012/09/11/sampling-from-the-normal- distribution-using-the-box-muller-transform/

𝑃 𝑈 ≤ 1 − exp(−0.5𝑟²)

=𝑃 𝑟² ≤ −2𝑙𝑜𝑔𝑈

= 𝑃 𝑟 ≤ −2𝑙𝑜𝑔𝑈

• 𝑧 = 𝑟²

• 𝑃 𝑧 = 𝑃 𝑟 ^𝑑𝑟

𝑑𝑧 = 0.5 𝑃 𝑟

• 𝑃 𝑟 = 2𝑃 𝑧 = 𝑒𝑥𝑝 − ^𝑟²

2

(9)

• 1. Draw 𝑢₁, 𝑢₂ ∼ 𝑈 0,1

• 2. Transform to polar rep.

– 𝑟 = −2log(𝑢₁) 𝜃 = 2𝜋𝑢₂

• 3. Transform to Catesian rep.

– 𝑥 = 𝑟 cos 𝜃 𝑦 = 𝑟 cos 𝜃

(10)

Rejection sampling

• when the inverse cdf method cannot be used

• Create a proposal distribution 𝑞(𝑥) which satisfies

• 𝑀𝑞(𝑥) provides an upper envelope for ෤𝑝(𝑥)

• Sample 𝑥 ∼ 𝑞(𝑥)

• Sample 𝑢 ∼ 𝑈(0,1)

• If 𝑢 > ^𝑝(𝑥)^෤

𝑀𝑞(𝑥) , reject the sample

• Otherwise accept it

(11)

Rejection sampling

(12)

Rejection sampling: Proof

• Why rejection sampling works?

• Let

• The cdf of the accepted point:

𝑝(𝑥)

(13)

Rejection sampling

• How efficient is this method?

• 𝑃 𝑎𝑐𝑐𝑒𝑝𝑡 = ׬ 𝑞 𝑥 ׬ 𝐼 𝑥, 𝑢 ∈ 𝑆 𝑑𝑢 𝑑𝑥

= න 𝑝 𝑥෤

𝑀𝑞 𝑥 𝑞 𝑥 𝑑𝑥 = 1

𝑀 න ෤𝑝 𝑥 𝑑𝑥

 We need to choose M as small as possible while still satisfying

න

0 1

𝐼 𝑢 ≤ 𝑦 = 𝑦

෤ 𝑝 𝑥 𝑀𝑞 𝑥

(14)

Rejection sampling: Example

• Suppose we want to sample from a Gamma

• When 𝛼 is an integer, i. e. , 𝛼 = 𝑘, we can use:

• But, for non-integer 𝛼, we cannot use this trick

& instead use rejection sampling

(15)

Rejection sampling: Example

• Use as a proposal, where

• To obtain 𝑀 as small as possible, check the ratio 𝑝(𝑥)/𝑞 𝑥 :

• This ratio attains its maximum when

𝑝(𝑥)

𝑞(𝑥) ≤ 𝑀 𝑝(𝑥)

𝑀𝑞(𝑥) ≤ 1

(16)

Rejection sampling: Example

• Proposal

(17)

Rejection Sampling:

Application to Bayesian Statistics

• Suppose we want to draw (unweighted) samples from the posterior

• Use rejection sampling

– Target distribution – Proposal:

– M:

• Accepting probability:

(18)

Adaptive rejection sampling

• Upper bound the log density with a piecewise linear function

(19)

Importance Sampling

• MC methods for approximating integrals of the form:

• The idea: Draw samples 𝒙 in regions which have high probability, 𝑝(𝒙), but also where |𝑓(𝒙)| is large

• Define 𝑓 𝒙 = 𝐼 𝒙 ∈ 𝐸

• Sample from a proposal than to sample from itself

(20)

Importance Sampling

• Samples from any proposal 𝑞(𝒙) to estimate the integral:

• How should we choose the proposal?

– Minimize the variance of the estimate መ𝐼

importance weights.

(21)

Importance Sampling

• By Jensen’s inequality, we have 𝐸 𝑢² 𝒙 ≥ 𝐸 𝑢 𝒙 ²

• Setting 𝑢 𝒙 = ^{𝑝 𝒙 𝑓 𝒙}

𝑞 𝒙 = 𝑤 𝒙 |𝑓 𝒙 |, we have the lower bound:

𝑢 𝒙 = ^{𝑝 𝒙 𝑓 𝒙}

𝑞 𝒙 가 상수이면 equality가 성립 𝑞 𝒙 ∝ 𝑝 𝒙 𝑓 𝒙

(22)

Importance Sampling:

Handling unnormalized distributions

• When only unnormalized target distribution and proposals are available without 𝑍_𝑝, 𝑍_𝑞?

• Use the same set of samples to evaluate ^𝑍_𝑞^{/ 𝑍}_𝑞:

unnormalized importance weight

(23)

Ancestral sampling for PGM

• Ancestral sampling

– Sample the root nodes,

– then sample their children,

– then sample their children, etc.

– This is okay when we have no evidence

(24)

Ancestral sampling

(25)

Ancestral sampling: Example

(26)

Rejection sampling for PGM

• Now, suppose that we have some evidence with interest in conditional queries :

• Rejection sampling (local sampling)

– Perform ancestral sampling,

– but as soon as we sample a value that is inconsistent with an observed value, reject the whole sample and start again

• However, rejection sampling is very inefficient

(requiring so many samples) & cannot be applied for real-valued evidences

(27)

Importance Sampling for DGM:

Likelihood weighting

• Likelihood weighting

– Sample unobserved variables as before,

conditional on their parents; But don’t sample observed variables; instead we just use their observed values.

– This is equivalent to using a proposal of the form:

– The corresponding importance weight: the set of observed nodes

(28)

Likelihood weighting

(29)

Likelihood weighting

(30)

Sampling importance resampling (SIR)

• Draw unweighted samples by first using importance sampling

• Sample with replacement where the probability that we pick 𝒙_𝑠 is 𝑤_𝑠

(31)

Sampling importance resampling (SIR)

• Application: Bayesian inference

– Goal: draw samples from the posterior

– Unnormalized posterior:

– Proposal:

– Normalized weights:

– Then, we use SIR to sample from

Typically S’ << S

(32)

Particle Filtering

• Simulation based, algorithm for recursive Bayesian inference

– Sequential importance sampling  resampling

(33)

Markov Chain Monte Carlo (MCMC)

• 1) Construct a Markov chain on the state space X

– whose stationary distribution is the target density 𝑝^∗(𝒙) of interest

• 2) Perform a random walk on the state space

– in such a way that the fraction of time we spend in each state x is proportional to 𝑝^∗(𝒙)

• 3) By drawing (correlated!) samples 𝒙₀, 𝒙₁, 𝒙₂, . . . , from the chain,

perform Monte Carlo integration wrt p∗

(34)

Markov Chain Monte Carlo (MCMC) vs.

Variational inference

• Variational inference

– (1) for small to medium problems, it is usually faster;

– (2) it is deterministic;

– (3) is it easy to determine when to stop;

– (4) it often provides a lower bound on the log liklihood.

(35)

Markov Chain Monte Carlo

(MCMC) vs. Variational inference

• MCMC

– (1) it is often easier to implement;

– (2) it is applicable to a broader range of models, such as models whose size or structure changes depending on the values of certain variables (e.g., as happens in matching problems), or models

without nice conjugate priors;

– (3) sampling can be faster than variational

methods when applied to really huge models or datasets.²

(36)

Gibbs Sampling

• Sample each variable in turn, conditioned on the values of all the other variables in the distribution

• For example, if we have D = 3 variables

• Need to derive full conditional for variable I

(37)

Gibbs Sampling: Ising model

• Full conditional

(38)

Gibbs Sampling: Ising model

• Combine an Ising prior with a local evidence term 𝜓_𝑡

(39)

Gibbs Sampling: Ising model

• Ising prior with 𝑊_𝑖𝑗 = 𝐽 = 1

– Gaussian noise model with 𝜎 = 2

(40)

Gibbs Sampling: Ising model

(41)

Gaussian Mixture Model (GMM)

• Likelihood function

• Factored conjugate prior

(42)

Gaussian Mixture Model (GMM):

Variational EM

• Standard VB approximation to the posterior:

• Mean field approximation

• VBEM results in the optimal form of 𝑞 𝒛, 𝜽 :

(43)

[Ref] Gaussian Models

• Marginals and conditionals of a Gaussian model

• 𝑝 𝒙 ∼ 𝑁(𝝁, 𝚺)

• Marginals:

• Posterior

conditionals:

(44)

[Ref] Gaussian Models

• Linear Gaussian systems

• The posterior:

• The normalization constant:

(45)

[Ref] Gaussian Models: Posterior distribution of 𝝁

• The likelihood wrt 𝝁:

• The prior:

• The posterior:

(46)

[Ref] Gaussian Models: Posterior distribution of 𝚺

• The likelihood form of Σ

• The conjugate prior: the inverse Wishart distribution The posterior:

(47)

Gaussian Mixture Model (GMM):

Gibbs Sampling

• Full joint distribution:

(48)

Gaussian Mixture Model (GMM): Gibbs Sampling

• The full conditionals:

(49)

Gaussian Mixture Model (GMM):

Gibbs Sampling

(50)

Label switching problem

• Unidentifiability

– The parameters of the model 𝜽, and the indicator functions 𝒛, are unidentifiable

– We can arbitrarily permute the hidden labels without affecting the likelihood

• Monte Carlo average of the samples for clusters:

– Samples for cluster 1 may be used for samples for cluster 2

• Labeling switching problem

– If we could average over all modes, we would find 𝐸[𝝁_𝑘|𝐷] is the same for all 𝑘

(51)

Collapsed Gibbs sampling

• Analytically integrate out some of the unknown quantities, and just sample the rest.

• Suppose we sample 𝒛 and integrate out 𝜽

• Thus the 𝜽 parameters do not participate in the Markov chain;

• Consequently we can draw conditionally independent samples

 This will have much lower variance than samples drawn from the joint state space

Rao-Blackwellisation

(52)

Collapsed Gibbs sampling

• Theorem 24.2.1 (Rao-Blackwell)

– Let 𝒛 and 𝜽 be dependent random variables, and 𝑓(𝒛, 𝜽) be some scalar function. Then

 The variance of the estimate created by analytically

integrating out 𝜽 will always be lower (or rather, will never be higher) than the variance of a direct MC estimate.

(53)

Collapsed Gibbs sampling

After integrating out the parameters.

(54)

Collapsed Gibbs: GMM

• Analytically integrate out the model parameters 𝝁_𝑘, 𝚺_𝑘 and 𝝅, and just sample the indicators 𝒛

– Once we integrate out 𝝅, all the 𝑧_𝑖 nodes become inter-dependent.

– once we integrate out 𝜽_𝑘, all the 𝑥_𝑖 nodes become inter-dependent

• Full conditionals:

(55)

Collapsed Gibbs: GMM

• Suppose a symmetric prior of the form 𝝅 = 𝐷𝑖𝑟(𝜶) and 𝛼_𝑘 = 𝛼/𝐾

• Integrating out 𝝅, using Dirichlet-multinormial formula:

෍

𝑘=1 𝐾

𝑁_𝑘,−𝑖 = 𝑁 − 1

(56)

[ref] Dirichlet-multinormial

• The marginal likelihood for the Dirichlet- multinoulli model:

(57)

Collapsed Gibbs: GMM

All the data assigned to cluster 𝑘 except for 𝒙_𝑖

To compute , we remove 𝒙_𝑖’s statistics from its current cluster (namely 𝑧_𝑖), and then evaluate 𝒙_𝑖 under each cluster’s posterior predictive. Once we have picked a new cluster, we add 𝒙_𝑖’s statistics to this new cluster

(58)

Collapsed Gibbs: GMM

• Collapsed Gibbs sampler for a mixture model

(59)

Collapsed Gibbs vs. Vanilla Gibbs

a mixture of K = 4 2-d Gaussians applied to N = 300 data points 20 different random initializations

(60)

Collapsed Gibbs vs. Vanilla Gibbs

logprob averaged over 100 different random initializations.

Solid line: the median

thick dashed: the 0.25 and 0.75 quantiles, thin dashed: the 0.05 and 0.95 quintiles.

(61)

Metropolis Hastings algorithm

• At each step, propose to move from the current state 𝒙 to a new state 𝒙′ with

probability 𝑞(𝒙′|𝒙)

– 𝑞: the proposal distribution – E.g.)

Random walk Metropolis algorithm independence sampler

(62)

Metropolis Hastings algorithm

• The acceptance probability if the proposal is symmetric,

• The acceptance probability if the proposal is asymmetric

– Need the Hastings correction

Given target distribution

(63)

Metropolis Hastings algorithm

• When evaluating α, we only need to know unnormalized density

•

(64)

Metropolis Hastings algorithm

(65)

Metropolis Hastings algorithm

• Gibbs sampling is a special case of MH, using the proposal:

• Then, the acceptance probability is 100%

(66)

Metropolis Hastings: Example

An example of the Metropolis

Hastings algorithm for sampling from a mixture of two 1D Gaussians

MH sampling results using a Gaussian proposal with the variance 𝑣 = 1

(67)

Metropolis Hastings: Example

(68)

Metropolis Hastings: Example

(69)

Metropolis Hastings: Gaussian Proposals

• 1) an independence proposal

• 2) a random walk proposal

MH for binary logistic regression

(70)

Metropolis Hastings: Example

• MH for binary logical regression

Joint posterior of the parameters

(71)

Metropolis Hastings: Example

– Initialize the chain at the mode, computed using IRLS – Use the random walk Metropolis sampler

(72)