Dependent Sampling (Markov Chain Monte Carlo (MCMC) Methods)

Dependent Sampling - Types

• we could use dependent sampling to sample from a distribution without knowing the value of the normalizing constant 𝐏(𝐄=𝐞) of that density
  • 𝐏(𝐐=𝐪|𝐄=𝐞) = 𝐏(𝐄=𝐞|𝐐=𝐪)𝐏(𝐐=𝐪) / 𝐏(𝐄=𝐞)
  • 𝐏(𝐐=𝐪|𝐄=𝐞) ∝ 𝐏(𝐄=𝐞|𝐐=𝐪)𝐏(𝐐=𝐪)
• Markov Chain Monte Carlo (MCMC) methods:
  • Metropolis-Hastings (MH) Algorithm -
  • Gibbs Sampling -
  • Hamiltonian Monte Carlo -

TODO

assume we want to sample from a probability distribution:

• 𝐏(𝜃|𝑋) # this is an example of posterior probability query

where:

• 𝜃 - is a single random variable (later it can be extended to multiple variables)
• 𝑋 - is a set of observed variables

by bayesian rule we have:

• 𝐏(𝜃|𝑋) = 𝐏(𝑋|𝜃)𝐏(𝜃) / 𝐏(𝑋)

where:

• 𝐏(𝜃|𝑋) - the probability distribution in question
• 𝐏(𝑋) - denominator is the normalizing constant which scales the distribution 𝐏(𝜃|𝑋)
• 𝐏(𝑋|𝜃)𝐏(𝜃) - numerator determines the SHAPE of the distribution 𝐏(𝜃|𝑋)

computing 𝐏(𝑋) takes a long time and we typically want to avoid that

we could use dependent sampling to sample from a distribution without knowing the value of the normalizing constant 𝐏(𝑋) of the probability distribution 𝐏(𝜃|𝑋)

• 𝐏(𝜃|𝑋) = 𝐏(𝑋|𝜃)𝐏(𝜃) / 𝐏(𝑋)
• 𝐏(𝜃|𝑋) ∝ 𝐏(𝑋|𝜃)𝐏(𝜃)

the graph below shows 3 distributions of 𝐏(𝜃|𝑋) where each are divided by a different normalizing constant

diagram.draw.io

notice that:

• the shape between the 3 distributions are similar. The numerator 𝐏(𝑋|𝜃)𝐏(𝜃) determines the shape.
• the vertical scale between the 3 distributions are different. This scale is determined by the denominator 𝐏(𝑋)

all we need is to determine the shape, which is the distribution of 𝐏(𝑋|𝜃)𝐏(𝜃). We don’t care about the scale part, in other words no need to determine the normalizing constant 𝐏(𝑋)

Comparing Probability Value Between 𝜃₁ and 𝜃₂

we want to determine the probability ratio:

• 𝐏(𝜃₁|𝑋) / 𝐏(𝜃₂|𝑋)

using Baye’s Rule:

• 𝐏(𝜃₁|𝑋) / 𝐏(𝜃₂|𝑋) = [𝐏(𝑋|𝜃₁)𝐏(𝜃₁)/𝐏(𝑋)] / [𝐏(𝑋|𝜃₂)𝐏(𝜃₂)/𝐏(𝑋)]
• 𝐏(𝜃₁|𝑋) / 𝐏(𝜃₂|𝑋) = [𝐏(𝑋|𝜃₁)𝐏(𝜃₁)] / [𝐏(𝑋|𝜃₂)𝐏(𝜃₂)]

notice we don’t need to compute the normalizing constant 𝐏(𝑋)

notice that the ratio of un-normalized posteriors [𝐏(𝑋|𝜃₁)𝐏(𝜃₁)] / [𝐏(𝑋|𝜃₂)𝐏(𝜃₂)] reflects the ratio of normalized posteriors 𝐏(𝜃₁|𝑋) / 𝐏(𝜃₂|𝑋)

therefore, we could design a sampler that uses the ratio of un-normalized posteriors at 2 different points in parameter space [𝐏(𝑋|𝜃₁)𝐏(𝜃₁)] / [𝐏(𝑋|𝜃₂)𝐏(𝜃₂)] and we use that ratio to govern how we step around parameter space. This would give us an exact view of whats happening in the ratio of normalized posterior space 𝐏(𝜃₁|𝑋) / 𝐏(𝜃₂|𝑋). In other words we could sample from 𝐏(𝜃₁|𝑋) / 𝐏(𝜃₂|𝑋) solely from [𝐏(𝑋|𝜃₁)𝐏(𝜃₁)] / [𝐏(𝑋|𝜃₂)𝐏(𝜃₂)]

see video at time 7:23

Dependent Sampling - General Algorithm

do a series of local steps around parameter space

see video at time 7:23